zer0lfsr 2021 Quick Solutions/Thoughts

This is an extremely rough sketch.

 

Problem 1 : zer0lfsr-

• only need to solve 2 out of 3 generators

Generator1

• h can be calculated without the last input with high probability
• bruteforce LFSR 16 bits, then directly recover NFSR 48 bits with 48 output bits

Generator2

• h is zero with high probability
• f has nonlinearity 16, so f is equal to a linear function with 3/4 probability
• therefore, a fast correlation attack can be used

Generator3

• f is very close to a linear function, so a fast correlation attack can be used
• f has a degree 2 annhilator, so we can use this as well to solve the problem

I solved Generator1 and Generator3 with annhilators.

 

Problem 2 : zer0lfsr+

 

We solve from Generator3 to Generator2 to Generator1. 

• An important note in the KDF function (found by barkingdog)
• If we know $KDF(K_0 || K_1 || K_2 || K_3)$ and $K_0 \oplus K_1$, then we know $K_2 \oplus K_3$
• we also have a symmetry, if we know $K_2 \oplus K_3$ then we know $K_0 \oplus K_1$

Also, note that the output value is the majority of the three outputs, so we have 75% correlation.

 

Generator3 can be solved by a fast correlation attack, similar to Problem 1. This works around 50% of the time.

 

For Generator2, fast correlation attack on bits that we know for sure (i.e. bits where Generator3 and actual output are different, forcing Generator1 and Generator2 to be equal to the actual output) can be used. This is supposed to be used to find all 48 bits of the LFSR, but to do so we need all 48 bits to be perfectly sound, or have very few of them to be incorrect. This is hard to do, so what I did was find 32 bits that we can guarantee its value, assume that at most one of them is wrong. This gives us about $2^{16}$ possibilities for the initial LFSR. Then, we bruteforce all possibilities for LFSR. By the KDF property, we can uniquely recover the NFSR initial state.

This gives us an attack that works around 20 seconds in Python with success probability of around 20%. 

 

For Generator1, we do something like the following - 

• bruteforce all 16 bits of the LFSR part
• we know about 24 guaranteed bits of the Generator1
• this gives about 24 bits of the NFSR part (by the solution of zer0lfsr-)
• combined with the KDF property, we can get around $2^{24}$ possibilities for the key

For Generator1, I used C++ with multicore programming to fit in time. 

 

Problem 3 : zer0lfsr++

 

Generator3 is the same. We will use the 16bit hint on Generator1. This gives us something like

• bruteforce all 16 bits of the LFSR part, and we know first 16 bits of the NFSR part
• we know 8 guaranteed bits out of the first 16 bits of the Generator1 output
• by checking this, around $2^8$ possibilities for the LFSR remain
• out of the 32 remaining NFSR parts, we know 16 of them with the LFSR and the guaranteed Generator1 bits
• so 16 of them remains, and bruteforcing gives us around $2^{24}$ keys

Therefore, we need to do Generator2 without any extra information. To do this,

• A very careful fast correlation attack using all bits (including non-guaranteed bits) can be done
• I was able to find 44 bits that we can guarantee with at most one incorrect bit
• we brute force the remaining 20 bits, so something like $2^{20} \cdot 44$ possibilities, doable

I believe with C++ with multicore programming and some luck, we can definitely solve it with this strategy.

 

UPD : Apparently there are multiple solutions for Generator2, so we need to use the hint on Generator2.