Tags: crypto
Rating:
# Randomness (Crypto)
We're given the file below:
```python
from Crypto.Util.number import *
from random import *
flag="TODO"
p=getPrime(64)
a=getrandbits(64)
b=getrandbits(64)
X=[]
X.append((a*getrandbits(64)+b)%p)
c=0
while c<len(flag):
X.append((a*X[c]+b)%p)
c+=1
output=[]
for i in range(len(flag)):
output.append(ord(flag[i])^X[i])
print (output)
#output:[6680465291011788243L, 5100570103593250421L, 5906808313299165060L, 1965917782737693358L, 9056785591048864624L, 1829758495155458576L, 6790868899161600055L, 1596515234863242823L, 1542626304251881891L, 8104506805098882719L, 1007224930233032567L, 3734079115803760073L, 7849173324645439452L, 8732100672289854567L, 5175836768003400781L, 1424151033239111460L, 1199105222454059911L, 1664215650827157105L, 9008386209424299800L, 484211781780518254L, 2512932525834758909L, 270126439443651096L, 3183206577049996011L, 3279047721488346724L, 3454276445316959481L, 2818682432513461896L, 1198230090827197024L, 6998819122186572678L, 9203565046169681246L, 2238598386754583423L, 467098371562174956L, 5653529053698720276L, 2015452976526330232L, 2551998512666399199L, 7069788985925185031L, 5960242873564733830L, 8674335448210427234L, 8831855692621741517L, 6943582577462564728L, 2159276184039111694L, 8688468346396385461L, 440650407436900405L, 6995840816131325250L, 4637034747767556143L, 3074066864500201630L, 3089580429060692934L, 2636919931902761401L, 5048459994558771200L, 6575450200614822046L, 666932631675155892L, 3355067815387388102L, 3494943856508019168L, 3208598838604422062L, 1651654978658074504L, 1031697828323732832L, 3522460087077276636L, 6871524519121580258L, 6523448658792083486L, 127306226106122213L, 147467006327822722L, 3241736541061054362L, 8781435214433157730L, 7267936298215752831L, 3411059229428517472L, 6597995245035183751L, 1256684894889830824L, 6272257692365676430L, 303437276610446361L, 8730871523914292433L, 6472487383860532571L, 5022165523149187811L, 4462701447753878703L, 1590013093628585660L, 4874224067795612706L]
```
Looking at this code, we realize that this code first generates random numbers using a linear congruential generator (LCG) and adds sequential numbers to a list. Then it xors the first flag character with the first element, second character with the second element, and so on.
They give us the output after the flag has been xor, and since xor is self inverting, figuring out the original random numbers from the
LCG would give us the flag.
output = LCG xor Flag_character
Flag_character = LCG xor output
## Cracking the LCG
Using this website that pretty much answered my prayers: https://tailcall.net/blog/cracking-randomness-lcgs/, we now have
functions that can crack LCG given a set of sequential numbers generated by LCG. In short, the code finds differences between the random numbers to determine the modulus of the LCG, which can then be used to crack the multiplier and incrementer using algebra.
### Code from the [same website](https://tailcall.net/blog/cracking-randomness-lcgs/) mentioned above
```python
def crack_unknown_increment(states, modulus, multiplier):
increment = (states[1] - states[0]*multiplier) % modulus
return modulus, multiplier, increment
def crack_unknown_multiplier(states, modulus):
print (modinv(states[1] - states[0], modulus))
multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
return crack_unknown_increment(states, modulus, multiplier)
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
def modinv(b, n):
g, x, _ = egcd(b, n)
if g == 1:
return x % n
def gcd(a,b):
r=a%b
while r:
a=b
b=r
r=a%b
return b
def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gcd, zeroes))
return crack_unknown_multiplier(states, modulus)
```
Since we know that the format of the flag is FwordCTF{...}, we can xor the first we numbers of the output and plug this into the LCG breaker
```python
output_first_nine = [6680465291011788243, 5100570103593250421, 5906808313299165060, 1965917782737693358, 9056785591048864624, 1829758495155458576, 6790868899161600055, 1596515234863242823, 1542626304251881891]
newOutput = []
flag = "FwordCTF{"
for i in range(len(flag)):
newOutput.append(ord(flag[i])^output_first_nine[i])
print (newOutput)
print (crack_unknown_modulus([5100570103593250306, 5906808313299165163, 1965917782737693404, 9056785591048864532, 1829758495155458643, 6790868899161600099, 1596515234863242753, 1542626304251881944]))
```
Throwing newOutput into crackLCG gives us our modulus, multiplier, and incrementer. For some reason running the LCG breaker didn't work the first time
because it couldn't find a mod inverse, but removing the first value from output_first_nine worked fine).
<br>
Thus we get the results:
mod = 9444729917070668893
mult = 7762244320486225184
increment = 731234830430177597
Now that we have our LCG, we can just generate the numbers and xor with the corresponding output to determine the flag!
## Recreating the LCG
```python
prexor = [6680465291011788181]
i = 0
while i + 1 < len(output):
prexor.append((prexor[i] * 7762244320486225184 + 731234830430177597) % 9444729917070668893)
i += 1
# xor to get the flag
ans = []
for i in range(len(output)):
ans.append(output[i] ^ prexor[i])
for i in range(len(ans)):
print(long_to_bytes(ans[i]).decode(), end = "")
```
Running this results in the mythical flag we have been searching for:
FwordCTF{LCG_easy_to_break!That_was_a_mistake_choosing_it_as_a_secure_way}
