*These challenges were solved by and the writeups were written by one of my teammates, @ngg.*

# Integrity

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 `md5(...)`

.

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`GF(2**256)`

because`P(x)`

is irreducible over`GF(2)`

. -
For OneTimePad2

`P(x) = x**128 + x**7 + x**2 + x + 1`

, which is the standard GCM polynomial (the field is`GF(2**128)`

). - In OneTimePad1 the
`process(m, k)`

function did the math, it calculated`(m+k)**2`

where`m`

and`k`

are field elements. - In OneTimePad2 the two helper functions were
`process1(m, k)`

calculated`m*k`

where`m`

and`k`

are field elements and`process2(a, b)`

calculated`a*b`

where`a`

and`b`

are 2x2 matrices over this field.

In both problems the random generated worked like the following pseudo-python code:

## OneTimePad1

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 (`r2`

and `r3`

), we had to calculate the first (`r1`

).

`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 `x`

.

Calculating `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:

## OneTimePad2

In OneTimePad2 the calculate function was more complicated.

`A`

and `B`

were two known constants, the function calculated `M = [[A,B],[0,1]]**seed`

and returned `M[0][0]*next + M[0][1]`

and it also changed `seed`

to `seed**2`

.

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**seed`

as `((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