# 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

**. Afterwards,**

*b***Alice**will send

**to**

*gᵃ mod p***Bob**while

**Bob**sends

**g**to

*ᵇ*mod p**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

*ᵇ***or**

*gᵇᵃ mod p***for Alice and Bob respectively. Resulting value computed by**

*gᵃᵇ mod p***Alice**and

**Bob**respectively will be the same since

**is equals to**

*gᵇᵃ mod p***. This allows them to arrive at the**

*gᵃᵇ mod p***same shared secret key**.

Going back to the **first stream**, as noticed previously, **p, g, gᵃ mod p **and

**was provided. In order to obtain the**

*gᵇ mod p***secret shared key**, one has to solve the

*discrete logarithm problem*. This is where given

**, where**

*h***equals to say**

*h***, we have to find out the value of**

*gᵇ mod p***. Knowing**

*b***, one can compute the secret shared key by computing**

*b***which is equals to**

*(gᵃ)ᵇ mod p*

*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

**from**

*b***given. However, such an algorithm requires a**

*gᵇ***huge amount of space**for computation and given such a large value for

**p, g**and

**g**,

*ᵇ***could not be obtained before the memory in my**

*b**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

**, discrete logarithms are computed in**

*Sage***finite fields**. This allows us to obtain the results much

*more quickly*with

*less memory*than algorithms such as

**and**

*baby-step giant-step***mentioned above.**

*Pollard’s rho algorithm*** Sage** would solve this similar to a

*Pohlig-Hellman***. This is possible if**

*algorithm***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:**

*p-1*With that, I decide to write up a program using ** Sage** to compute the value of

**once again. This time, the algorithm ran**

*b**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

**as well as**

*baby-step giant-step algorithm***which worked previously in other CTFs. It was definitely interesting to learn about**

*Pollard-rho’s 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,**

*Pohlig-Hellman algorithm***and think of other methods! 😄**

*try harder*