These challenges were solved by and the writeups were written by one of my teammates, @ngg.
There was an encryption scheme, we had to calculate encrypt(‘admin’) based on that we could encrypt anything other than the string ‘admin’.
The scheme looked like this:
md5 length is exactly a block size, so
This means that
If we cut the first block out from this then the rest is exactly
encrypt('admin') with the
iv set to
Sending this to the server gave me
OneTimePad1 && OneTimePad2
Both tasks were about breaking a random generator. The hardest part was to understand the ideas and math based on the given python codes.
They were based on finite field arithmetics of GF(2)[x]/P(x).
If you do not know what I’m talking about then visit https://en.wikipedia.org/wiki/Finite_field_arithmetic first.
- For OneTimePad1
P(x) = x**256 + x**10 + x**5 + x**2 + 1, which meant that the field is
P(x)is irreducible over
P(x) = x**128 + x**7 + x**2 + x + 1, which is the standard GCM polynomial (the field is
- In OneTimePad1 the
process(m, k)function did the math, it calculated
kare field elements.
- In OneTimePad2 the two helper functions were
kare field elements and
bare 2x2 matrices over this field.
In both problems the random generated worked like the following pseudo-python code:
In OneTimePad1 the calculate function returned (process(next, seed), seed) and the flag and two known strings were one time pad encrypted
with its first 3 outputs respectively. Based on the second and third encrypted string we knew the second and third generated random numbers (
r3), we had to calculate the first (
r3 = process(r2, seed) = (r2+seed)**2, this means that
seed = sqrt(r3)+r2.
Calculating square roots over binary fields are easy because squaring is a linear function.
(This might seem strange, but
(x+y)**2 = x**2 + 2*x*y + y**2 = x**2 + y**2 so it’s really linear).
Being linear means that there exists a matrix
S such that
x**2 = x*S for every
S is straightforward, it happens to be invertible so we can calculate square roots as well (every field element has exactly 1 square root).
We now know seed and we also know that
r1 = sqrt(r2)+seed so we can decrypt the flag:
In OneTimePad2 the calculate function was more complicated.
B were two known constants, the function calculated
M = [[A,B],[0,1]]**seed and returned
M*next + M and it also changed
We can see by induction that
[[A,B],[0,1]]**seed = [[A**seed, B*(1+A+A**2+...+A**(seed-1))],[0,1]] = [[A**seed, B*(A**seed - 1)/(A - 1)],[0,1]].
One time pad was used here as well but know we knew the first 4 plaintexts and we had to calculate the following ones.
r2 = A**seed * r1 + B*(A**seed - 1)/(A-1)
To get seed from this we first calculated
((A-1)*r2 + B)/((A-1)*r1 + B) and then had to calculate the discrete logarithm
seed = Log(A, A**seed).
This last part was the hardest for me as I couldn’t get Sage to solve it (I tried in lots of different ways but it always threw NotImplementedExceptions…).
After the competition I’ve read hellman’s writeup, he found a way to do this in Sage.
I knew that Mathematica cannot do this either, so I had no better idea than to look for any implementation on the web and read articles on how solve this if I have to implement my own.
Fortunately I found some promising references in Magma’s documentation and I could solve this with the free online version at http://magma.maths.usyd.edu.au/calc/ with the following script:
After this we knew r1 and seed, so I just modified the original code to use these and to encrypt the ciphertext instead (one time pad is an involution).
This gave me