BsidesSF 2017 - []root (crypto, 250 pts)
15 Feb 2017 - jeremy- Competition: https://scoreboard.ctf.bsidessf.com/
- Challenge Name: []root
- Type: Crypto
- Points: 250 pts
- URL: https://scoreboard.ctf.bsidessf.com/attachment/fd74c568c3bfd6e5fb4f07c03db322f0ace8fd0e68ff4d2c106f1518e2109231
Our guy inside e-corp was able to get that packet capture of their backend PKI you asked for. Unfortunately it seems they’re using TLS to protect the modulus fetch. Now, I have been told that the best crackers in the world can do this in 60 minutes. Unfortunately I need someone who can do it in 60 seconds.
Note: Flag does not follow the “Flag:” format but is recognizable
We are provided with a packet capture file containing a TLS exchange. Loading it up in Wireshark, we can quickly identify a TLS handshake, with a “server hello” message containing the server certificate, itself containing the RSA public key (modulus + public exponent):
We need to recover the private key by factoring the modulus. We used Fermat’s factorisation method to recover the two prime factors with the script below:
import gmpy2
def fermat_factors(n):
assert n % 2 != 0
a = gmpy2.isqrt(n)
b2 = gmpy2.square(a) - n
while not gmpy2.is_square(b2):
a += 1
b2 = gmpy2.square(a) - n
factor1 = a + gmpy2.isqrt(b2)
factor2 = a - gmpy2.isqrt(b2)
return int(factor1), int(factor2)
e = 31337
n = """
726f6f740000000000000000000000
0000000000001b0000000000000000
00000000001ffffb00000000000000
00000000001ffffb00000000000000
00000000001fffff7777777b000000
00000000001ffffffffffffb000000
00000000001ffffffffffb00000000
00000000001ffffffffffb00000000
00000000001ffffffffffffb000000
00000000001fffff2222222b000000
00000000001ffffb00000000000000
00000000001ffffb00000000000000
00000000001ffffb00000000000000
00000000001ffffb00000000000000
00000000001ffffb00000000000000
00000000001ffffb00000000000000
00000000001ffffb00000000000000
265293c4422be3532638feeb2a635e
865e5bccd4862d1491f8e46ed41afd
ab32ab1e913c296c45a723a371cc4a
d218d273a494ac501a1c677576b84d
3a1700b24e38f3d7c8090c952767f8
a9da532eb4496a953fa2b2641f93af
58321e491ad6b3e1f6600ea1757635
a2d47562dff2f245bfc8ed51142093
1de246d56334d8897d6465b227f6c0
95ece1ad994c7551f08dbc21f8b406
91ee51f5f72d052d9352062f90b0e7
c52c2eb18196c2c985101af4eac674
99396c6241ad4f2439ed11f87d67e7
3a239b865c45d65a61cf0f56082de8
31b97fb28ae8222a7195e0ec06c082
81ffc16e7106e77e68b8c4510424be
eb5582fe21cc345f53534682b75c36
8d73c9""".replace('\n', '')
p, q = fermat_factors(int(n, 16))
print "p =", p
print "q =", q
This quickly yielded values for p and q. Plugging those values into rsatool, we were able to reconstruct the server’s private key:
$ python ./rsatool.py -p 345709341936068338730678003778405323582109317075021198605451259081268526297654818935837545259489748700537817158904946124698593212156185601832821337576558516676594811692389205842412600462658083813048872307642872332289082295535733483056820073388473845450507806559178316793666044371642249466611007764799781626418800031166072773475575269610775901034485376573476373962417949231752698909821646794161147858557311852386822684705642251949742285300552861190676326816587042282505137369676427345123087656274137257931639760324708350318503061363031086796994100943084772281097123781070811610760735943618425858558459014484742232019973 -q 345709341936068338730678003778405323582109317075021198605451259081268526297654818935837545259489748700537817158904946124698593212156185601832821337576558516676594811692389205842412600462658083813048872307642872332289082295535733483056820073388473845450507806559178316793666044371642249466611007764799781626418800031166072773475575269610775901034485376573476373962417949231752698909821646794161147858557311852386822684705642251949742285300552861190676326816587042282505137369676427345123087656274137257931639760324708350318503061363031086796994100943084772281097123781070811610760735943618425858558459014484742232018933 -e 31337 -o priv.key
[...]
Saving PEM as priv.key
The next step was to load this private key back into Wireshark to see decrypted TLS traffic. We could see a GET /modulus HTTP request with some form of ASCII art:
Nice ASCII art key we thought… But then we looked closely to the first non-zero bytes towards the end: 66 6c 61 67. This looks like ASCII for “flag”! And indeed:
>>> '66:6c:61:67:3a:77:68:65:6e:5f:73:6f:6c:76:69:6e:67:5f:70:72:6f:62:6c:65:6d:73:5f:64:69:67:5f:61:74:5f:74:68:65:5f:72:6f:6f:74:73:5f:69:6e:73:74:65:61:64:5f:6f:66:5f:6a:75:73:74:5f:68:61:63:6b:69:6e:67:5f:61:74:5f:74:68:65:5f:6c:65:61:76:65:73'.replace(':','').decode('hex')
'flag:when_solving_problems_dig_at_the_roots_instead_of_just_hacking_at_the_leaves