Compass crew members just got back to work from a fun weekend/night at Insomni’hack (Geneva) where hackers met [0] to solve puzzles and enjoying the hacker community. On the way back home was sufficient time to clean-up systems and to reflect on some of the challenges.
There was a variety of brain teasing puzzles relating to application, network and computer security, digital forensics, reversing or steganography. During the contest the team gets more challenging puzzles unlocked by the time they hand in solutions. The solutions was always some sort of special formattet string a.k.a. token or nugget.
I decided to write-up one of the puzzles to have it documented of course and to provide you with an idea how such a puzzles looks like. So, let’s dig into it.
Challenge: “An ancient device is sending beacons. Let’s see whether we can derive information from it.”
The beacons received were
52568362028447315123743948788053644459577411882456257531616135268537279675960870614430475573303102032918797133050913 52727929746007441720068082686756949179073655255531676829839480670880742558336965750100665996845187331498825064459186 201158324192401598932420659686637057233217007355201796046752494579206057840824741418635158750620395621617197903012628 28130137328108864733654457574649869546226965870669213292484603118885398856280073620722817153185715356950196877471039 80484565918589639155839282503441828047447393078860552265541334592733372319489211090676853869300071705818380141734553 327884935077457453113605219951670824692959814316520336632744473695392968704109006664884646461226287506677371413786816 71320589399616119392997612087604459808872826741986236180026121617993570092370114471863111200409714142046077511450033 222751634152401318446067973538013344568447280940195394615901147009774216683554748179893081969917861424112117226026325 28130137328108864733654457574649869546226965870669213292484603118885398856280073620722817153185715356950196877471039 80484565918589639155839282503441828047447393078860552265541334592733372319489211090676853869300071705818380141734553 139898042261876853301455727625774012475698643685395021760275568789054192063562822563098057540361718346301097569068285 290458508376731263921252055316868138470702882414424357263569140840448897025047660176505033785801971649974769416580828 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 39752644457197524816840681265913188543326108820355516805599867640545430987920927262238504378204278859183980221246355 301118090575689790044304143985657097761186152450376594357207609156541662901869839587261599850312495649532760148859125 80484565918589639155839282503441828047447393078860552265541334592733372319489211090676853869300071705818380141734553 222751634152401318446067973538013344568447280940195394615901147009774216683554748179893081969917861424112117226026325 76309999578481760278134186167064490139180297738713651148555706607615754191408415493954631393292274058258783002375297 312440510356542990832274139310717029606738136784317835051579720866508272813085512326169432510915628987511601361100755 312440510356542990832274139310717029606738136784317835051579720866508272813085512326169432510915628987511601361100755 76309999578481760278134186167064490139180297738713651148555706607615754191408415493954631393292274058258783002375297 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 39752644457197524816840681265913188543326108820355516805599867640545430987920927262238504378204278859183980221246355 71320589399616119392997612087604459808872826741986236180026121617993570092370114471863111200409714142046077511450033 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 39752644457197524816840681265913188543326108820355516805599867640545430987920927262238504378204278859183980221246355 301118090575689790044304143985657097761186152450376594357207609156541662901869839587261599850312495649532760148859125 71320589399616119392997612087604459808872826741986236180026121617993570092370114471863111200409714142046077511450033 39752644457197524816840681265913188543326108820355516805599867640545430987920927262238504378204278859183980221246355 301118090575689790044304143985657097761186152450376594357207609156541662901869839587261599850312495649532760148859125 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 71320589399616119392997612087604459808872826741986236180026121617993570092370114471863111200409714142046077511450033 231618262599702676973845832517759334021176525056072833529569269456564473604609355284495911481371096877656941135244359 139898042261876853301455727625774012475698643685395021760275568789054192063562822563098057540361718346301097569068285 76309999578481760278134186167064490139180297738713651148555706607615754191408415493954631393292274058258783002375297 28130137328108864733654457574649869546226965870669213292484603118885398856280073620722817153185715356950196877471039 301118090575689790044304143985657097761186152450376594357207609156541662901869839587261599850312495649532760148859125 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 231609473505895645459311620779424869497767062819966540784040891362418669395322439617108666258332519877710534676878307 139898042261876853301455727625774012475698643685395021760275568789054192063562822563098057540361718346301097569068285 80484565918589639155839282503441828047447393078860552265541334592733372319489211090676853869300071705818380141734553 222751634152401318446067973538013344568447280940195394615901147009774216683554748179893081969917861424112117226026325 181895177774870499268628883221214310423523857203344119754826804608066049315978476367118679395919668261312392452153631 231618262599702676973845832517759334021176525056072833529569269456564473604609355284495911481371096877656941135244359 231609473505895645459311620779424869497767062819966540784040891362418669395322439617108666258332519877710534676878307 205884448854259361864211375336005072036904149095927464741554161540888665349683555934701608904819901412468420531999589
Interestingly, the number of beacons matches the number of characters required for submition to the nugget verification application of that hacking challenge and for some reason we also have a copy of a public key.
-----BEGIN PUBLIC KEY----- MEwwDQYJKoZIhvcNAQEBBQADOwAwOAIxCGVV/7bWB7CH0Z2UsUJgM/s6zW2UCiid twBq/aXZxGfqX0gBgwwgAAAAAAAAAGFvjQIDAQAB -----END PUBLIC KEY-----
As we all know, we can’t use that key to get any plaintext from information protected with an asymmetric cryptographic algorithm. However, let’s have a quick look on the parameters of the key:
$ openssl rsa -pubin -in pubkey.txt -modulus -text Public-Key: (388 bit) Modulus: 08:65:55:ff:b6:d6:07:b0:87:d1:9d:94:b1:42:60: 33:fb:3a:cd:6d:94:0a:28:9d:b7:00:6a:fd:a5:d9: c4:67:ea:5f:48:01:83:0c:20:00:00:00:00:00:00: 00:61:6f:8d Exponent: 65537 (0x10001) Modulus=86555FFB6D607B087D19D94B1426033FB3ACD6D940A289DB7006AFDA5D9C467EA5F4801830C2000000000000000616F8D ...
Usually, for sufficiently large and properly chosen keys, the derivation of the private key from its public coutnerpart is not possible. In this case, the key size is obviously not that large and as we have no other information so far, let’s try to bluntly factorize the modulus N.
You could either try to do so online [1] or use CryptTool [2].
The result clearly shows that an unfortunate combination of primes was chosen as the base of the key material.
p=13331 q=24815323469403931728221172233738523533528335161133543380459461440894543366372904768334987264000000000000000000479
So let’s see whether we can calculate the RSA private key from the parameters we have already.
The private key d can be calculate from e and phi whereby
e which is the exponent (see public key dump) phi(N) which is based on the factorized primes and calculates as (p-1)(q-1)
Hint: Depending on your code, you might want to put e in decimal rather than in hex 0x10001 to avoid spending to much time on debugging :)
Finally you will need to compute d = e^-1 mod phi(N) in order to get the private key.
Hint by M. «If you’re already using CrypTool anyway, you could also use it to calculate d from p,q,e without having to code anything on your own: Indiv. Procedures > RSA Cryptosystem > RSA Demonstration.»
If your prefer to solve it in python it’s far more challenging. I have not been very successfull in finding a python RSA library that allows for that specific calculation. Luckily there are lot’s of websites actually providing hints on how to calculate the modular inverse based on the extended euclidean algorithm. Thus I went for a copycat approach [3].
def egcd(a, b): x,y, u,v = 0,1, 1,0 while a != 0: q, r = b//a, b%a m, n = x-u*q, y-v*q b,a, x,y, u,v = a,r, u,v, m,n return b, x, y def modinv(a, m): g, x, y = egcd(a, m) if g != 1: return None else: return x % m
Finally, we will need to try whether the generated private key yields some resonable results on the beacons. The plaintext pt calculates as follows:
pt = beacon^d mod N
In python this is pow(beacon,d,n) rather than (beacon**d) mod n. Mathematically, both python statements should return the same result. However, pow is optimized to handle large factors whereas (beacon**d) mod n will take forever for RSA like calculations.
Finally, we get ASCII characters from each beacon which turned out to be the correct format and plaintext to qualify for a solution (python script – calculation.py).
I N S 1 4 ...
And it did !!
Thanks to the SCRT team who actually built not only this but also other fun and challenging puzzles and thanks to those who were sufficiently patient to discuss twist and turns while battling!
For those interested in solving puzzles and hands-on security training join us for our awsome courses or sign-up for a free remote hacking-lab.com [4] account and get knee deep into our virtual pwnable lab. Hacking-lab features a wide variety of information security, penetration testing, security assessment and forensics hands-on training exercises to educate students and information security professionals. Give it a try.
References
[0] European hackers hit Geneva competition http://www.skynews.com.au/tech/article.aspx?id=960593
[1] Online factor DB at http://www.factordb.com/
[2] CryptTool http://www.cryptool.org/en/download-ct1-en
[3] Extended Euclidean Algorithm Snippet http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
[4] Hacking-Lab http://www.hacking-lab.com/
Leave a Reply