In the challenge Aron II, you will find the fixed version of Aron! Let’s see if you can still do it easily?!
nc 167.71.62.250 23549
After completing a POW, we get
*********************************************************************************
| 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 = 28263878878495216476934212429573877467, and with these PRF parameters:
| (p, g) = (0xc2ee925bebe76d157e982b61d4de1fcb, 0x4801a1c59d396321ed359e9773f33faa)
| the five consecutive random numbers generated by our secure PRF are:
| f_a(n + 0) = 171299656158256438070356161225092239773
| f_a(n + 1) = 151540109405892052005223571068469542509
| f_a(n + 2) = 142426843534236061578507279799807510323
| f_a(n + 3) = 105102553997975750166225720659782451264
| f_a(n + 4) = 97247915425750207624219823209998753612
| Options:
| [G]uess next number!
| [P]RF function
| [N]ew numbers
| [Q]uit
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
The function basically computes pow(g,a.X,p) where a is a secret vector, X is the binary expansion of the number, basically 0 or 1 and . is basically a dot prodct
To find a.X, DLP needs to be solved, fortunately a.X is small so bruteforcing is very fast
Another restriction is that we cannot input numbers that are too small
If we input 2^127, we simply calculate the dlp and we get a[127], similar for 2^126
For other numbers, to avoid the numbers going to small and getting rejected, we input 2^126+2^x to find a[x]
script.py automates the calculation of the vector a, which probably is the original intent?
Flag:
CCTF{___Naor-Reingold___p5euD0r4ndOM_fuNc710N__PRF__} / CCTF{___Naor-Reingold___fix3d_V3r5I0n___}