Description:⌗

Small numbers are bad in cryptography. This is why.

dhkectf_intro.py⌗ 

import random
from Crypto.Cipher import AES

# generate key
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)

# print("Diffie-Hellman key exchange outputs")
# print("Public key: ", g, p)
# print("Jotaro sends: ", aNum)
# print("Dio sends: ", bNum)
# print()

# pad key to 16 bytes (128bit)
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')

with open('flag.txt', 'rb') as f:
    flag = f.read()

iv = bytes("kono DIO daaaaaa", encoding = 'ascii')
cipher = AES.new(key, AES.MODE_CFB, iv)
ciphertext = cipher.encrypt(flag)

print(ciphertext.hex())

output.txt⌗ 

b31699d587f7daf8f6b23b30cfee0edca5d6a3594cd53e1646b9e72de6fc44fe7ad40f0ea6

Let’s look at the python script:

The script contains a list of tuples of prime numbers and chooses one tuple randomly. The primes will be used for a Diffie-Hellman key exchange. The first prime will be used as generator and the second one as module.

gpList = [ [13, 19], [7, 17], [3, 31], [13, 19], [17, 23], [2, 29] ]
g, p = random.choice(gpList)

After agreeing on the generator, each party generates its secret:

a = random.randint(1, p)
b = random.randint(1, p)

Normally the following would happen:

  • Alice calculates g^a % p and sends it to Bob, Bob calculates g^b % p and sends it to Alice
  • Alice calculates with the received value from Bob (g^b % p)^a % p, Bob does the same
  • Now Alice and Bob have the same secret key: (g^b % p)^a % p = (g^b)^a % p = g^(b*a) % p = g^(a*b) % p = (g^a)^b % p = (g^a % p)^b % p.

As the authors use Diffie-Hellman just to generate a key locally, they simplified this:

k = pow(g, a * b, p)

After that the key is converted to string for later use:

k = str(k)

As we now have generated a secret key with Diffie-Hellman this key is used in AES for encrypting the flag.

As AES needs a 128-bit key, we have to blow up our key. The script chooses the easy way and adds constant padding in front of the key:

# pad key to 16 bytes (128bit)
key = ""
i = 0
padding = "uiuctf2021uiuctf2021"
while (16 - len(key) != len(k)):
    key = key + padding[i]
    i += 1
key = key + k

Then the key is converted to bytes for the AES-Function:

key = bytes(key, encoding='ascii')

After that the flag is read from file:

with open('flag.txt', 'rb') as f:
    flag = f.read()

AES needs an initialization vector. The authors decided to use a constant initialization vector. This has the advantage, that the initialization vector must not be stored with the encrypted text, so that we can handle the output.txt easier. On the other side this destroys the reason for the initialization vector which should prevent that all messages with the same first block have the same first ciphertext block. As we have only one message, this is irrelevant.

iv = bytes("kono DIO daaaaaa", encoding = 'ascii')

Now the flag is encrypted:

cipher = AES.new(key, AES.MODE_CFB, iv)
ciphertext = cipher.encrypt(flag)

Finally, the encrypted text is written in hex to the given output.txt:

print(ciphertext.hex())

Now we can try to decrypt the flag. First we need to read the encrypted flag:

with open("output.txt", "r") as f:
    output = bytearray.fromhex(f.read())

As gpList is short and the used modules are small, we can simply test all tuples:

for pair in gpList:
    g, p = pair
    print(g, p, pair)

As the module is small, we can test all possible a and b. Without loss of generality we can assume b >= a, since multiplication is commutative.

    for a in range(1, p+1):
        for b in range(a, p+1):

We have to use p+1, because randInt(a,b) uses the interval [a, b] whereas range(a,b) uses the interval [a, b).

Now we can copy the computation of the key from the provided encryption script:

    #a = random.randint(1, p)
    #b = random.randint(1, p)
            k = pow(g, a * b, p)
            k = str(k)

    #print("Diffie-Hellman key exchange outputs")
    #print("Public key: ", g, p)
    #print("Jotaro sends: ", aNum)
    #print("Dio sends: ", bNum)
    #print()

            #pad key to 16 bytes (128bit)
            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')

After initializing AES

            cipher = AES.new(key, AES.MODE_CFB, iv)

we can try to decrypt the flag.

            cleartext = cipher.decrypt(output)

As we know the beginning of the flag, we can filter the output:

            if cleartext[:7] == b'uiuctf{':
                print(cleartext)

When we now execute the script, we will see the correct flag can be decrypted with different tuples and even multiple times per tuple:

[13, 19]
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
[7, 17]
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
[3, 31]
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
[13, 19]
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
[17, 23]
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
[2, 29]
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'
b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'

This has multiple reasons:

  1. We can redistribute the prime factors of a*b nearly arbitrary between a and b.
  2. Because of the module, the resulting k will always be in the interval [0, p-1]. Since the greatest common divisor between g and p is 1, the 0 cannot be reached. So k will be always in the interval [1, p-1]

With this knowledge, we can simplify the script:

  1. Search the greatest module and use only this module.
  2. Iterate over the interval [1, p-1] and try each for k.

With this adjustments, we get the following script:

from Crypto.Cipher import AES

# find greatest module
gpList = [ [13, 19], [7, 17], [3, 31], [13, 19], [17, 23], [2, 29] ]
mod = 0
for g, p in gpList:
    if p > mod:
        mod = p

# open encrypted flag
with open("output.txt", "r") as f:
    output = bytearray.fromhex(f.read())

# iterate over all possible keys
for i in range(1, mod):
    k = str(i)

    #pad key to 16 bytes (128bit)
    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')

    # initialize AES
    iv = bytes("kono DIO daaaaaa", encoding = 'ascii')
    cipher = AES.new(key, AES.MODE_CFB, iv)

    # decrypt flag
    cleartext = cipher.decrypt(output)

    # check if cleartext is flag and print flag
    if cleartext[:7] == b'uiuctf{':
        print(cleartext)

Now we get the flag only once.

b'uiuctf{omae_ha_mou_shindeiru_b9e5f9}\n'

Due to the small numbers the time difference between both scripts is negligible (0.90s vs. 0.83s).