We start by downloading the source files.
We are give a
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 is a simple Diffie-Hellman key exchange. To decrypt the message we need
We use the following script to bruteforce
#include <stdio.h>
unsigned long mod_pow(unsigned long base, unsigned long expo, unsigned long mod) {
unsigned long result = 1;
base = base % mod; // Ensure base is within the modulus
while (expo > 0) {
// If exp is odd, multiply result with base and take the remainder with mod
if (expo % 2 == 1)
result = (result * base) % mod;
// exp must be even now
expo = expo >> 1; // Divide exp by 2
base = (base * base) % mod;
}
return result;
}
int main() {
unsigned long p = 0xdd6cc28d;
unsigned long g = 0x83e21c05;
unsigned long A = 0xcfabb6dd;
unsigned long B = 0xc4a21ba9;
// Brute force for a
for (unsigned long a = 1; a < p; ++a) {
if (mod_pow(g, a, p) == A) {
printf("a = %lu\n", a);
break;
}
}
// Brute force for b
for (unsigned long b = 1; b < p; ++b) {
if (mod_pow(g, b, p) == B) {
printf("b = %lu\n", b);
break;
}
}
return 0;
}
After running the script we get
./bruteforce
a = 2766777741
b = 1913706799
We can now write a small python script to decrypt the output:
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime, long_to_bytes
from hashlib import sha256
import random
p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9
a = 2766777741
b = 1913706799
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)
ciphertext = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'
decrypted = cipher.decrypt(ciphertext)
print(decrypted.decode())
Running this script gives us the flag.
python3 decrypt.py
HTB{y0u_n3ed_a_b1gGeR_w3ap0n!!}