dhke_intro Writeup
Uiuctf 2021
Solved by : choco
“Small numbers are bad in cryptography. This is why.”
This is a DK cipher with just 28 possible keys to find For a given p and g from the random list, even if the generated k is randomized and dependant on p and g, we know that k should be lesser than p because of modulus operation
gpList = [ [13, 19], [7, 17], [3, 31], [13, 19], [17, 23], [2, 29] ]
g, p = random.choice(gpList)
a = random.randint(1, p)
b = random.randint(1, p)
k = pow(g, a * b, p)
k = str(k)
since the maximum value of p is 29, k is from 0 to 28
the padded key is also predictable
padding = "uiuctf2021uiuctf2021"
while (16 - len(key) != len(k)):
key = key + padding[i]
i += 1
key = key + k
key = bytes(key, encoding='ascii')
so key can be from b’uiuctf2021uiuct0’ to b’uiuctf2021uiuct9’ and b’uiuctf2021uiuc10’ to b’uiuctf2021uiuc28’
the VI is fixed, so with the small possible set of keys and a fixed VI we can easily bruteforce into getting the decrypted flag from the dk cipher
import binascii
from Crypto.Cipher import AES
cf = "b31699d587f7daf8f6b23b30cfee0edca5d6a3594cd53e1646b9e72de6fc44fe7ad40f0ea6"
unhcf = bytes.fromhex(cf)
for k in range(0,28):
k = str(k)
key = ""
i = 0
padding = "uiuctf2021uiuctf2021"
while (16 - len(key) != len(k)):
key = key + padding[i]
i += 1
key = key + k
key = bytes(key, encoding='ascii')
iv = bytes("kono DIO daaaaaa", encoding = 'ascii')
cipher = AES.new(key, AES.MODE_CFB, iv)
flag = cipher.decrypt(unhcf)
try:
print(flag.decode("ASCII"))
print(key)
except:
i = 0
key: b’uiuctf2021uiuct9’
flag: uiuctf{omae_ha_mou_shindeiru_b9e5f9}