Tags: prng crypto

Rating: 0

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, p) % p, which we could then solve or bruteforce for a.

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).