Tags: prng crypto
Rating:
Apart from the obvious hack (which we didn't notice at first at which wasn't fixed properly in aron2), the intended solution for aron was quite interesting.
Basically we got a POW leading to a pseudo random number generator:
```
*********************************************************************************
| hey! I have developed an efficient pseudorandom function, PRF, but it needs |
| deep tests for security points!! Try hard to break this PRF and get the flag! |
| In each step I will compute the f_a(n), f_a(n + 1), f_a(n + 2), f_a(n+3), and |
| f_a(n + 4) for secret verctor a, and for your given positive number 0 < n < p |
*********************************************************************************
| for n = 184113299190345435057106844406533197843, and with these PRF parameters:
| (p, g) = (0xd696dda3cd30cebc1a81813fb2b13931, 0x987265868e3c69e26c5ee34ba9d82f83)
| the five consecutive random numbers generated by our secure PRF are:
| f_a(n + 0) = 141652518279999000396303568109848898358
| f_a(n + 1) = 28639803954408977165975477439641803981
| f_a(n + 2) = 158977698017440824547805031811313118697
| f_a(n + 3) = 62551549237931052851287463007086539304
| f_a(n + 4) = 63319421242963154645393127856149009876
| Options:
| [G]uess next number!
| [P]RF function
| [N]ew numbers
| [Q]uit
```
and we had access to the function generating the numbers:
```
def gg(tup, a, x):
(_, p, g), n = tup, len(a)
assert len(bin(x)[2:]) <= n
X = bin(x)[2:].zfill(n)
f_ax = g
for i in range(1, n):
f_ax *= pow(g, a[i] * int(X[i]), p)
return f_ax % p
```
which took as arguments 3 numbers, p, g, n which were given, and a vector a. The challenge was, given `f_a(n)` through `f_a(n + 4)`, to guess `f_a(n + 5)`. Given that we could ask for new numbers with the same p and g but providing a new n, it was easy to ask for n-1 then, and enter the `f_a(n + 4)` that was given to us just before, but that's not interesting. Instead, let's try and figure out what the vector a is.
Our first idea was to use a new `n` with one 1 and 0 everywhere else so that `pow(g, a[i] * int(X[i]), p)` would be 1 except for the place where the 1 was, for example providing `n = 2^(len(a)-2)` (because the for loop in the gg function starts at 1) would give us `f_ax = g*pow(g, a[1], p) % p`, which we could then solve or bruteforce for a[1].
There were two restrictions on the `n` that we could input for new numbers though, one was in the PRF, that the binary size of n was not greater than the size of a (the vector), so we had an upper bound, and the second restriction was from another function, which basically said `Sorry, your input integer is small :P` for n < 2^65, so we had to provide a number bigger than 64 bits. These restrictions prevented us from inputting n = 2^i for `1 <= i < len(a)` as it would go below 2^64. But if we worked from 1000...000 through 11000...000 to 111...111, we'd be alright.
The first task was to bruteforce the length of a, which we did by inputting larger and larger powers of 2 until we got an EOF and this:
```
Traceback (most recent call last):
File "/home/aron5/aron/aron_server.py", line 121, in <module>
main()
File "/home/aron5/aron/aron_server.py", line 96, in main
pr("| f_a(n + 0) = %s\n| f_a(n + 1) = %s\n| f_a(n + 2) = %s\n| f_a(n + 3) = %s\n| f_a(n + 4) = %s " % (gg((l, p, g), a, n), gg((l, p, g), a, n+1), gg((l, p, g), a, n+2), gg((l, p, g), a, n+3), gg((l, p, g), a, n+4)))
File "/home/aron5/aron/aron_server.py", line 39, in gg
assert len(bin(x)[2:]) <= n
AssertionError
```
After finding out that `len(a) == 128`, we started the work on a itself, bruteforcing value by value, assuming that they all were under 255, which they were, and voilà, we get a, now we just have to compute `f_a(n + 5)` ourselves and send it!
```
[+] Opening connection to 167.71.62.250 on port 12439: Done
[+] Cracking POW...
[+] Computing the secret vector a...
[+] Done, f_a(n + 5) is 177871485800397954143952761967181761502!
[!] Congratz! :) You got the flag: CCTF{___Naor-Reingold___p5euD0r4ndOM_fuNc710N__PRF__}
[*] Closed connection to 167.71.62.250 port 12439
```
You will find the script [here](https://github.com/arty-hlr/CTF-writeups/tree/master/2019/cryptoctf/aron).
