Blunt

1KB

crypto_blunt.zip

archive

Open

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.

Source.py :

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}')

and we have this output

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{'

first we have to find the shared secret C and to calculate it we need either the variable a or b

1. we know p,g,A,B

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

To find $a$, we need to solve the discrete logarithm problem, which is generally a difficult problem. However, for small primes like this one, we can solve it efficiently.

We can use the Baby-step Giant-step algorithm

Baby-step Giant-step algorithm Implementation :

from math import ceil, sqrt

def baby_step_giant_step(g, A, p):
    m = ceil(sqrt(p - 1))
    # Precompute giant step
    giant_step = {pow(g, j, p): j for j in range(m)}
    
    # Compute the value for the baby step
    g_inv_m = pow(g, -m, p)
    baby_step = A
    for i in range(m):
        if baby_step in giant_step:
            return i * m + giant_step[baby_step]
        baby_step = (baby_step * g_inv_m) % p

    return None

p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9

# Find a
a = baby_step_giant_step(g, A, p)

# Find b
b = baby_step_giant_step(g, B, p)

print("a =", a)
print("b =", b)

┌──(kali㉿kali)-[~/ctf/crypto/blunt]
└─$ python step_giant.py
a = 2766777741
b = 1913706799

now that we have a and b we can calculate the shared secret C and then calculate the key finally decrypting the ciphetext using the same AES cipher mode used in encryption. let's decrypt the ciphertext

solve.py :

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

# Given values
p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9
# a and b found using Baby-step Giant-step algorithm
a = 2766777741
b = 1913706799
ciphertext = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'

# Calculate shared secret
shared_secret = pow(A, b, p)

# Derive AES key from shared secret
hash = sha256()
hash.update(long_to_bytes(shared_secret))
key = hash.digest()[:16]

# Decrypt ciphertext
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(ciphertext)

# Unpad the decrypted message
decrypted = unpad(decrypted, 16)

# Print the decrypted plaintext
print("Decrypted plaintext:", decrypted.decode('utf-8'))

┌──(kali㉿kali)-[~/ctf/crypto/blunt]
└─$ python solve.py                         
Decrypted plaintext: HTB{y0u_n3ed_a_b1gGeR_w3ap0n!!}

Flag :

HTB{y0u_n3ed_a_b1gGeR_w3ap0n!!}