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
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)
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.
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_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
So what I did was using sympy in python to find
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
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.