Author: Kevin He
Team: 3PAC
Challenge Category: Crypto
Points: 98
Attachments: See challenge.py and output.txt in this Gist.
Chunk Norris is black belt in fast random number generation.
Start off by examining the code for challenge.py. It uses RSA — a modern public key cryptography algorithm — to encrypt the flag. The idea behind public key cryptography is that given the public key, everyone can encrypt plaintext messages, but only the party who possesses the secret private key can decrypt the ciphertext back into plaintext. In this challenge, only the public key is given, and it consists of the modulo n — a product of 2 large prime numbers — and the exponent e. However, the security of RSA heavily depends on the fact that its public key modulo n cannot be factored into its constituent primes p and q. Once p and q are known, the private key d can be computed easily (d = (p - 1) * (q - 1)) and decrypting is trivial.
Therefore, in a secure RSA implementation, n must be large enough to make factoring infeasible, and the challenge uses a 2048-bit n (product of two 1024-bit primes) to meet this security criterion. However, I exploited the fact that the code uses an insecure prime number generator to generate p and q, which allowed me to obtain p and q without factoring the gigantic n directly, by deriving p and q from 2 significantly smaller integers called P, and Q.
The code responsible for generating primes is in the gen_prime function of challenge.py. To generate each prime, the code uses a naïve LCG to generate 16 pseudorandom 64-bit chunks. And in each iteration of the while loop, it pieces the chunks together to form a 1024-bit integer. It then checks whether the generated number is prime, and if not, it repeats the whole process again. The process ends when the generated number is prime and that prime number is returned.
The code actually uses a much more simplified version of LCG, having a multiplier a but no increment in each step:
for _ in range(bits // chunk_size):
p = (p << chunk_size) + s
s = a * s % 2**chunk_sizeThis LCG works by performing the last line repeatedly, and in each step s is the generated pseudorandom number. The last line multiplies s by a and take the result modulo 2^chunk_size (from now on ^ denotes exponentiation, equivalent to Python's **). Pseudorandom number generators like LCG are not truly random, it is deterministic once we know the initial value of s. Moreover, since the code includes all 64 bits of s into the generated prime, actually knowing any 64-bit chunk in the prime would allow full recovery of the prime number. It is easy to see that once we know one chunk, we immediately know what the next chunks will be by simulating the LCG steps (multiply by a and mod) ourselves. The following diagram demonstrates this idea:
MSB LSB
p = |chunk|chunk|chunk|chunk|...|chunk |
= | R | R*a |R*a^2|R*a^3|...|R*a^15|
Definition of Variables
R: the leftmost (most significant) chunk ofpa:afromchallenge.py, the multiplier in LCGp: the prime generated, representsporq- From now on including the diagram above, operations in every chunk is computed modulo
2^64(|R*a|means(R*a)%(2^64)) unless stated otherwise.
If there's multiplication in modulo arithmetic, then should there be "division", an operation modulo 2^64 that effectively undoes the multiplication by a, too? The answer is to multiply by the modular multiplicative inverse of a mod 2^64, which I define as b. That is, R*a*b = R mod 2^64
b can be computed efficiently using the Extended Euclidean Algorithm, and it exists as an already implemented function in PyCryptodome:
from Crypto.Util.number import inverse
chunk_size = 64
a = 0xe64a5f84e2762be5
print('b =', hex(inverse(a, 1 << chunk_size)))and here is the value of b:
b = 0xc14c0c90d01019edSince multiplying by b is the inverse operation of multiplying by a, we can compute p and q backwards from their least significant (rightmost) 64-bit chunks, called uppercase P and Q respectively:
MSB LSB
p = |chunk |chunk |...|chunk|chunk|chunk |
= |P*b^15|P*b^14|...|P*b^2|P*b |P |
q = |Q*b^15|Q*b^14|...|Q*b^2|Q*b |Q |
This establishes a deterministic formula for p and q (both 1024-bit) in terms of P and Q (both 64-bit). Therefore, the effective randomness of the primes is 64-bit (2^64 possible values) rather than 1024-bit (2^1024 possible values), but 64 bits is enough to make brute-forcing combinations of p and q infeasible. However, factoring a 128-bit integer (product of two 64-bit integers) is practical. This is a key piece of information that leads me to the next step, where I managed to extract the 128-bit P*Q, which is significantly easier to factor than the 2048-bit public key n.
When we perform multiplication on numbers (Let's say 1111 * 1111) by hand, we perform this procedure:
1111
* 1111
-------
1111
1111
1111
1111
-------
1234321
Think of multiplying p and q as multiplying base 2^64 arithmetic, or that 64-bit chunks of p and q are digits, then:
P*b^15 ... P*b^2 P*b P
* Q*b^15 ... Q*b^2 Q*b Q
--------------------------------------------
P*Q*b^15 ... P*Q*b^2 P*Q*b PQ
...P*Q*b^16 P*Q*b^15 ... P*Q*b^2 P*Q*b
... ... ... ... ... ... ... ...
--------------------------------------------
.................................2*P*Q*b PQ
Define:
n0as the the lowest 64-bit (rightmost chunk) of n (bit 0 to 63)n1as the the chunk to the left ofn0(bit 64 to 127)
And we know that the product of p and q is n, so
n0 = P*Q mod 2^64andn1 = 2*P*Q*b + floor(PQ/(2^64)) mod 2^64.
Note that since both P and Q are 64-bit, their product is 128-bit. The lower 64 bits of P*Q is P*Q mod 2^64 while the upper 64 bits of P*Q are floor(PQ/(2^64)). The upper 64 bits are carried over to the chunk to its left.
So immediately we know the lower 64 bits of P*Q, which is just the lower 64 bits of n, to find the upper bits, I applied some modular arithmetic tricks:
2*P*Q*b + floor(PQ/(2^64)) % 2^64 == n1
(2*P*Q*b % 2^64) + (floor(PQ/(2^64)) % 2^64) == n1
2*b*(P*Q % 2^64) + (floor(PQ/(2^64)) % 2^64) == n1
since floor(PQ/(2^64) is the upper 64 bits of P*Q and thus cannot exceed 2^64, we can remove the modulo:
2*b*(P*Q % 2^64) + floor(PQ/(2^64)) == n1
floor(PQ/(2^64)) == n1 - 2*b*(P*Q % 2^64)
So now we have a formula for the entire P*Q. I wrote a script to solve it: getPQ.py which is in this gist
It turns out that it can easily be factored (which is natural given that they are randomly generated numbers and only lowercase p and q are supposed to be primes, P and Q can be composite) using the GNU coreutil factor:
$ factor 3463373886635289660353622154000952089
3463373886635289660353622154000952089: 11 13 109 223 1290533 4608287 167541865434116759
Then we just have to try all possible combinations of P and Q using these factors, which is trivial: there are only 2^7=128 combinations to try, and we can easily compute the lowercase letters (p, q) from the uppercase ones:
p = ... (P*(b^2) % (2^64)) << 128 + (P*(b^1) % (2^64)) << 64 + P
to check whether our guess is correct we just multiply p and q and see if it is equal to n, an implementation of this is in proc_pq_factors.py
and finally we have the flag:
$ python3 proc_pq_factors.py
Flag: b'CTF{__donald_knuths_lcg_would_be_better_well_i_dont_think_s0__}\n'
It is a big no-no to use pseudorandom number generators (PRNGs) in cryptography, instead, use random devices like /dev/urandom or even /dev/random to get better sources of randomness. The deterministic property of PRNGs sometimes make cryptanalysis possible, especially with old and low quality PRNGs. I managed to get the flag thanks to the simple theory behind LCG.