Analysis

In this crypto challenge, we are given 3 files: chall.py, secrets.py, and output.txt. Chall.py:

1
2
3
4
5
6
7
8
9
10

from Crypto.Util.number import getPrime, bytes_to_long as b2l
from secrets import sUp3r_s3cr3t_value as x

p = getPrime(16)
g = 2
y = pow(g, x, p)

print(f"{p = }")
print(f"{g = }")
print(f"{y = }")

Secrets.py

1

 sUp3r_s3cr3t_value = 0 # fake_secret_value

output.txt

1
2
3

p = 49211
g = 2
y = 16752

In order to get the flag, we need to recover the secret value x and hash it using SHA256.

By analyzing the source code, we observe that the prime p is generated using:

1



This produces a 16-bit prime number, which is extremely small for cryptographic purposes. A secure implementation would use primes of at least 2048 bits.
Because of this weakness, the discrete logarithm problem becomes trivial to solve using brute force.



Exploitation



We can simply try every possible value of x until 2^x mod 49211 = 16752 matches.



The solve script:


1
2
3
4
5
6
7
8
9
10
11
12

from Crypto.Util.number import getPrime, bytes_to_long as b2l

# Output.txt values
p = 49211
g = 2
y = 16752

# Burte forcing the x value
for x in range(p):
    if pow(g, x, p) == y:
        print(f"Found secret: {x}")
        break



Running it we get the x value:


1
2

$ python exploit.py
Found secret: 44917




Flag



OSC{08eab99d92e1552eead8da191e5da60e7e6979fbc3cd82eef1f8aef70bd57979}




        
        
          

            Tags:
            
              crypto
            
              brute-force