description
We at Singapore Sloop just got 4 more tenders for our OTOT and D4 machine’s randomness generator; We think they are just 4 more Terrible OTOT Tenders (TOTOTTs as we call them) but we need proof. That’s where you come in kiddo.
Files given:
We are given the task to prove that 4 PRFs are not IND-CPA secure by correctly distinguishing them from random functions:
Welcome to your Distinguisher station.
There is a truely random function f, and using that, the tenders created pseudo-random F
In each round, you are trying to guess if F is the pseudo-random function or a truely random one
You get to query the function up to 127 times. Query the function by entering 'F(xxx)', where xxx is your guess (without the quotes)
When you are ready to guess, type 'Truly-Random' if you think F is a truely random function, or 'Pseudo-Random' if you think F is pseudo-random
Each level lasts 30 rounds, and you need to get at least 22 correct each stage to move on
There are 4 tenders, all of which we think are terrible. The fate of Otot and D4 rests in your hands kiddo.
Level 1: F(x) = f(x||0) || f(1||x), || is concatenation
Input to x is 64 bits. Output is 64 bits
This is simple to distinguish, we compare the last half of \(F(0)\) with first half of \(F\left(2^{63}\right)\), if they are the same there’s an extremely high chance that \(F(x)\) is the function given. This allows us to pass the first level.
Level 2: F(x) = f(k) ^ x, ^ is binary XOR
Input to x is 48 bits. Output is 48 bits
This is also quite easy to distinguish, notice that \(f(k)\) is a constant, hence we just check if \(F(0)\oplus F(1)=1\). This allows us to pass the second level.
Level 3: F(x) = f(x & k) ^ f(x V k), & is binary AND, V is binary OR
Input to x is 32 bits. Output is 32 bits
This task is slightly harder. It’s reasonable to assume that \(k\) has both \(0\) and \(1\) bits. Suppose that \(k\land 2^a\neq k\land 2^b\), i.e. the \(a^{th}\) and \(b^{th}\) bits are different. Let \(x_{ij}=i2^a+j2^b\). Then notice that
\[f\left(x_0{00}\land k\right)\oplus f\left(x_0{01}\land k\right)=f\left(x_0{10}\land k\right)\oplus f\left(x_0{11}\land k\right)\] \[f\left(x_0{00}\lor k\right)\oplus f\left(x_0{01}\lor k\right)=f\left(x_0{10}\lor k\right)\oplus f\left(x_0{11}\lor k\right)\]
This allows us to distinguish \(F\) from a random function! We can simply fix \(b=0\) and vary \(a\) between \(1\) and \(48\), letting us pass level 3.
Level 4: F(x) = f\*\*31(x) = f(f(f...f(f(x))...)), 31 times
Input to x is 16 bits. Output is 16 bits
A key point to notice is that \(f\) is a random function, not a random permutation, this means that multiple inputs can have the same output, i.e. it is not injective. Iterating \(f\) would only make its image smaller, i.e. ‘less injective’, increasing the chance for a collision. Hence we just check if \(F(x)\) repeats any values for a small number of inputs and this is a reasonable gauge if \(F\) is truely random or not. Using this we finally solve level 4 and obtain the flag:
I KNEW IT, THOSE ARE TOTTOTTOTs!
Thank you kiddo, you have saved Singapore Sloop.
Here's a flag of our appreciation: CTFSG{W4lao_h0w_7o_p5eVdo_RanDOm_Th3_sp1n_sPiN_b4ll_mAch1n3}
The solution script can be found at solve.py
Flag:
CTFSG{W4lao_h0w_7o_p5eVdo_RanDOm_Th3_sp1n_sPiN_b4ll_mAch1n3}