# Can COViD steal Bob’s idea?

This is the first challenge from the Cryptography section of Stack-The-Flag 2020 by govtech-csg. The challenge wants us to break vulnerable Diffie-hellman parameter

## Statement

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?

The challenge is attached with a pcapng file (which can be opened with WireShark)

## Observation

I found out the following texts by analyzing the packages.

p = 298161833288328455288826827978944092433
g = 216590906870332474191827756801961881648
g^a = 181553548982634226931709548695881171814
g^b = 64889049934231151703132324484506000958


Hi Alice, could you please help me to design a keystream generator according to the file I share in the file server so that I can use it to encrypt my 500-bytes secret message? Please make sure it run with maximum period without repeating the keystream. The password to protect the file is our shared Diffie-Hellman key in digits. Thanks.

Besides the texts, there are also 2 packages that are exceptionally big compare to others. This indicate that maybe some kind of file had sent through the network.

## Solution

First of all, I extract out the 2 large data from WireShark and run file command on it.

$file file_1.bin file_1.bin: Zip archive data, at least v5.1 to extract$ file file_2.bin
file_2.bin: data


It tells that file_1.bin is a zip file and file_2.bin is just some random data.

This suggests that the file sent by Bob might be the combination of file_1.bin and file_2.bin as it was splitted during the process of transferring the file.

So now I combine both of the file together.

\$ cat file_1.bin file_2.bin > file.zip


I open it using 7zip and it then requests for a password.

From the text sent by Bob, he told Alice that the password of the file is Diffie-Hellman key in digits.

So this explains why p, g, g^a, g^b are sent in the network.

Diffie-Hellman depends on the hardness of computing discrete logarithm problems. However, in this case Bob’s p seems to be small enough to find a and b.

So what I did was using sympy in python to find a and b.

from sympy.ntheory.residue_ntheory import discrete_log

g = 216590906870332474191827756801961881648
p = 298161833288328455288826827978944092433
A = 181553548982634226931709548695881171814
B = 64889049934231151703132324484506000958

a = discrete_log(p,A,g)

assert pow(g,a,p) == A

print(pow(B,a,p))


And it works! (took around 30 sec)

From the tips given by the admin on discord, the flag format is in govtech-csg{shared_secret}

I got stuck around here for like an hour because I didn’t know what the question wants LOL. Thank god my teammate @mimomomi saw the tips and told me about it.

Flag: govtech-csg{246544130863363089867058587807471986686}

Updated: