STACK the Flags CTF Write-up — Can COVid steal Bob’s idea?
Introduction
STACK the Flags was a CTF organised by GovTech’s Cyber Security Group (CSG) over the weekend from 4th — 6th of December. I took part in this CTF in hope to hone my skills in various aspects of cyber security and the challenges in this CTF were certainly insightful. My team and I have definitely learnt a lot from this CTF. Here is the write-up for the cryptography challenge to give you some insights of this challenge and hopefully allow you to take away some knowledge regarding cryptography. Let’s get started!
Challenge Name: Can COVid steal Bob’s idea?
Challenge Description: Bob wants Alice to help him design the stream cipher’s keystream generator based on his rough idea. Can COViD steal Bob’s “protected” idea?
Challenge Category: Cryptography
This challenge comes with a pcap file capturing traffic between Alice and Bob. I decided to analyse the TCP streams in the file to see if there are any packets shared between Alice and Bob regarding the proposed idea. There were 3 TCP streams between Alice and Bob, one of which revealed the initial exchange of Bob’s request to Alice for a keystream generator.
In this stream, we were given p, g, gᵃ, gᵇ and in Bob’s message, it was mentioned that the file to be shared would be password protected using the shared Diffie-Hellman key in digits. With this in mind, I continued to analyse the other TCP streams to find the file shared by Bob to Alice. In the second stream, I discovered that it contained the FTP traffic for the file transferred between Bob and Alice.
We could see that the file transferred is a zip file and the type transferred is binary. With that, the last stream contained the zip file that was transferred as we could see a CryptoDesign.png when the packet was displayed in ASCII format.
I decided to export the data from the last stream first before going back to the first TCP stream to solve for the shared secret key between Bob and Alice. Keeping in mind that the data type shared was binary and it was a zip file, I exported the data in raw and renamed it to contain a .zip extension format.
After the zip file was exported, what was left is figuring out the shared secret key between Alice and Bob.
For readers who might not have heard of Diffie-Hellman key exchange, here is a short summary of how the protocol works and how the same shared secret key can be obtained by both Alice and Bob.
In a Diffie-Hellman key exchange, both parties will agree on a multiplicative inverse of integers modulo prime p as well as a generator g (or otherwise known as a primitive root modulo of p).
From there, each party will then generate an integer known to only themselves. In this case, the secret integer generated by Alice is represented by a, while that of Bob is b. Afterwards, Alice will send gᵃ mod p to Bob while Bob sends gᵇ mod p to Alice. In the given stream, this is shown as simply gᵃ and gᵇ. Both parties will be able to compute the shared secret by computing gᵇᵃ mod p or gᵃᵇ mod p for Alice and Bob respectively. Resulting value computed by Alice and Bob respectively will be the same since gᵇᵃ mod p is equals to gᵃᵇ mod p. This allows them to arrive at the same shared secret key.
Going back to the first stream, as noticed previously, p, g, gᵃ mod p and gᵇ mod p was provided. In order to obtain the secret shared key, one has to solve the discrete logarithm problem. This is where given h, where h equals to say gᵇ mod p, we have to find out the value of b. Knowing b, one can compute the secret shared key by computing (gᵃ)ᵇ mod p which is equals to gᵃᵇ mod p.
There are a few known ways to solve the discrete logarithm problem. I first tried to implement the baby-step giant-step algorithm to obtain b from gᵇ given. However, such an algorithm requires a huge amount of space for computation and given such a large value for p, g and gᵇ, b could not be obtained before the memory in my desktop/laptop runs out.
I decided to use another algorithm known as Pollard’s rho algorithm for logarithms. This algorithm uses a smaller amount of memory than baby-step giant-step algorithm. However, this was still not good enough.
Finally, I read about the use of Sage to solve discrete logarithm problem. In Sage, discrete logarithms are computed in finite fields. This allows us to obtain the results much more quickly with less memory than algorithms such as baby-step giant-step and Pollard’s rho algorithm mentioned above.
Sage would solve this similar to a Pohlig-Hellman algorithm. This is possible if p-1 could be factorised into smaller factors. In this case, a quick check on factordb shows that it is possible to factorise p-1 as shown below:
With that, I decide to write up a program using Sage to compute the value of b once again. This time, the algorithm ran much faster, with a lower memory used. The script is shown below:
Eventually, the value of b and shared secret key was found in the output below:
Following which, the secret shared key was used as the password to extract the zip file exported from the last stream (as described above). The extraction was successful since the shared secret key obtained was correct. CryptoDesign.png was found inside the zip file as expected and the CryptoDesign which will be used for the next challenge is shown below:
Conclusion
Since the challenge is titled as Can COVid steal Bob’s idea?, the flag obtained for this challenge is:
govtech-csg{246544130863363089867058587807471986686}This challenge was certainly insightful for me as I learnt about Sage and how to use them to solve discrete logarithm problem. I was stumped while solving this challenge when I could not solve them using baby-step giant-step algorithm as well as Pollard-rho’s algorithm which worked previously in other CTFs. It was definitely interesting to learn about Pohlig-Hellman algorithm which I did not learn before. Such a challenge reminded me that there are various ways to solve a problem and if one way does not work, try harder and think of other methods! 😄
