Tags: crypto

Rating:

python
def enc(a):
f = {str: str.encode, int: int.__str__}.get(type(a))
return enc(f(a)) if f else a

def H(*args):
data = b'\0'.join(map(enc, args))
return SHA256.new(data).digest()

def F(h, x):
return pow(h, x, q)

################################################################

def go(publicB,verB):

private_A = 40*random.randrange(2**999)
publicA = F(generator, private_A)
print(f'{publicA = :#x}')

if not 1 < publicB < q:
exit('nope')

shared = F(publicB, private_A)

verA = F(generator, shared**3)
print(f'{verA = :#x}')

if verB == F(generator, shared**5):
flag = "this is a test"
aes = AES.new(key, AES.MODE_CTR, nonce=b'')
encrypted = aes.encrypt(flag.encode()).hex()
print(f'flag:', encrypted)
return (publicA,verA,encrypted)
else:
print(f'nope! {shared:#x}')
return (publicA,verA,shared)


We can query the oracle go three times, but one query already succeeds.

## Observations

Seems like a DH-exchange where an additional value (verA and verB) will be compared. However, we do not even know the generator on which the exchange is based on. Therefore, we first have to get the generator in order to solve the puzzle verB == F(generator, shared**5). After receiving the encrypted flag, we can just bruteforce all possible passwords because it is at max $10^6$

### Step 1) Getting the generator

We do this by setting P_B := publicB to q-1. This will lead to the following:

$shared = P{_B}^{sk_A} = (q-1)^{40 \cdot rnd} = (q-1)^{2^{20 \cdot rnd }} = 1 \mod q$ because $(q-1)^2 = q^2 - 2q + 1= 1 \mod q$

We then receive verA which is the generator in our case because shared is one. Then we just send verA for verB in order to receive the encrypted flag.

### Step 2) Bruteforce flag

python
flags = []

import string
pable = set(bytes(string.printable.encode()))

for i in range(10**6):
key = H(i,1)
aes = AES.new(key, AES.MODE_CTR, nonce=b'')

plaintext = aes.decrypt(ciphertext)

# check if chars are printable
if set(plaintext).issubset(pable):
flags.append(plaintext)

list(filter(lambda x:b"{" in x,flags))


Outputs

 hxp{ju5T_k1ddIn9_w3_aLl_kn0w_iT's_12345}

At first I was unaware of the flag format such that I tested every value for the password. This took roughly 30 seconds.