Stealing Bob’s idea
This is another writeup of one of the challenges in GovTech CSG’s STACK the Flags CTF. This one appeared to be relatively easy once the theory had been figured out.
The challenge in question is the first one under the cryptography section. Cryptography was not exactly the team’s strong suit, but we took a look at it regardless:
A single packet capture file was provided with this challenge.
At first, given the references to “‘protected’ idea” and what we would tend to expect from a packet capture, we originally thought that the challenge involved breaking some weak/vulnerable version of encryption. An inspection of the TCP streams in Wireshark, however, showed that this wasn’t the case:
The conversation between Bob and Alice is followed by an FTP upload:
The file signature of the uploaded item 50 4b 03 04 is consistent with that of zip archives,[1] so it does look like this is the archive we are looking for. Dumping the contents of that TCP stream to file and attempting to open it as a zip archive reveals that it is password protected, as expected.
To solve the challenge, some degree of understanding about the Diffie-Hellman key exchange (DH) is essential. At a high level, DH involves the generation of a shared secret between parties without needing to exchange anything private. This makes the method ideal for use over an insecure channel (as with the case now).
Thankfully for us, the specific implementation of DH in this challenge is weak. To recap the parameters used:
p = 298161833288328455288826827978944092433
g = 216590906870332474191827756801961881648
g^a = 181553548982634226931709548695881171814
g^b = 64889049934231151703132324484506000958p in this case is only 128 bits, which is not sufficiently secure, as demonstrated previously in the Logjam attack. We used this discrete logarithm calculator that was available publicly to calculate the value of Alice’s private key. Following which, deriving the shared secret (and the value of the flag) can be done by calling pow(g^b, alice_private, p) from a Python console:
alice_private = 211631375588570729261040810141700746731
g^b = 64889049934231151703132324484506000958pow(g^b, alice_private, p) = 246544130863363089867058587807471986686
Extracting the contents of the archive with 7-Zip revealed a single image file, which contained details vital to the subsequent cryptography challenge. Unfortunately, we were unable to solve that one.
