[Easy] Blunt

Blunt

​ 29^th Jan 2024 / Document No. D24.102.27

​ Challenge Author(s): ir0nstone

Synopsis

Blunt is an Easy crypto challenge that involves a small $p$ value, meaning it is easy to solve the DLP to retrieve the private exponents.

Description:

Valuing your life, you evade the other parties as much as you can, forsaking the piles of weaponry and the vantage points in favour of the depths of the jungle. As you jump through the trees and evade the traps lining the forest floor, a glint of metal catches your eye. Cautious, you creep around, careful not to trigger any sensors. Lying there is a knife - damaged and blunt, but a knife nonetheless. You’re not helpless any more.

Skills Required

• Basic understanding of the Diffie-Hellman Key Exchange

Skills Learned

• Solving the DLP in small groups
• Using SageMath

Enumeration

We are given the following script:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime, long_to_bytes
from hashlib import sha256

from secret import FLAG

import random


p = getPrime(32)
print(f'p = 0x{p:x}')

g = random.randint(1, p-1)
print(f'g = 0x{g:x}')

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

A, B = pow(g, a, p), pow(g, b, p)

print(f'A = 0x{A:x}')
print(f'B = 0x{B:x}')

C = pow(A, b, p)
assert C == pow(B, a, p)

# now use it as shared secret
hash = sha256()
hash.update(long_to_bytes(C))

key = hash.digest()[:16]
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print(f'ciphertext = {encrypted}')

This looks like a typical Diffie-Hellman Key Exchange:

• A generator $g$ is defined in a finite field $F_p$
• The private exponents $a$ and $b$ are kept secret
• $g$ is put to the power of $a$ and $b$ to form $A$ and $B$ respectively
• The values are exchanged (printed out) and then both sides calculate put the values they receive to their private power to calculate $g^{ab}$
• This value is used as a shared secret for encryption

The values are found in output.txt:

p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9
ciphertext = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'

Solution

The weakness here is the generation of the public prime number $p$:

p = getPrime(32)

We can see that $p$ is a 32-bit number - far too small to provide any security! We can calculate the private exponent $a$ by calculating the discrete logarithm of $A$, which is easy since $p$ is so small. We're going to use SageMath's discrete_log functionality to do this.

p = 0xdd6cc28d
F = GF(p)

g = F(0x83e21c05)
A = F(0xcfabb6dd)
B = F(0xc4a21ba9)
ciphertext = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'

# get a, and from there C
a = discrete_log(A, g)
C = B^a

Once we're retrieved the shared secret $C$, the decryption is simple - it's basic AES decryption.

# decrypt
hash = sha256()
hash.update(long_to_bytes(int(C)))

key = hash.digest()[:16]
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
cipher = AES.new(key, AES.MODE_CBC, iv)

decrypted = cipher.decrypt(ciphertext)
flag = unpad(decrypted, 16)
print(flag)

And we get the flag!