Tags: diffie-hellman crypto
Rating:
We are allowed to control DHKE's prime number `p`. It is known that if `p` is weak (`p - 1` consists of small factors), we can easily solve discrete log problem using Pohlig–Hellman algorithm.
Here's [the code](https://github.com/CTF-STeam/ctf-writeups/blob/master/2021/UIUCTF/dhkeadv_primegen.py) I used to generate weak prime number:
```python
while True:
p = 2
while p.bit_length() < 1024:
p *= getPrime(16)
if p.bit_length() < 2048:
p = p + 1
if isPrime(p):
print(p)
break
else:
print('Failed')
```
Now use the prime generated to [break the key exchange and recover the flag](https://github.com/CTF-STeam/ctf-writeups/blob/master/2021/UIUCTF/dhkeadv_solve.sage):
```python
from binascii import unhexlify
from Crypto.Cipher import AES
from hashlib import sha256
p = 13235062921662694429211184891220141973285969028958016790661658609292023032453887458389574420664371217218833375173082540739555090686687826551693380798574629365254210787419070348340076227508521415632755789594367616391764583712987637766374230688082101873347891400341145784790200266806419168972691757367828474132879
g = 2
# dio = pow(g,a,p)
dio = 3792084934906248564383234181650035598772615324676195889910857921102049947444713668894077270359500041848160892283875666632138773227678174413239166356643157564701755290320942846789533398104751824380490988637885367504561459997920826443858290627891230160540485823054473058723700613322991694411069864630317229002911
# jotaro = pow(g,b,p)
jotaro = 1264790617152365852095129131541764881757215378660064894337475150769922800524031374528216985077846999998895522436779903552749896067733534664389692778794818553787963498827277500298297339946818247400174112120794559981652711640384257027450857601018904217492079212562792889181540706049350288847341968603810689566739
ct = 'a7a7cb1f26d3d2770f82d5fb45710ed4519ba04dd7ec5950ba8f2b4a9e013a194b265ba3233e5d288702'
ct = unhexlify(ct)
F = IntegerModRing(p)
a = discrete_log(F(dio), F(g))
print(a)
key = pow(jotaro, a, p)
key = sha256(str(key).encode()).digest()
iv = b'uiuctf2021uiuctf'
cipher = AES.new(key, AES.MODE_CFB, iv)
pt = cipher.decrypt(ct)
print(pt)
```
Flag: `uiuctf{give_me_chocolate_every_day_7b8b06}`
