# Faulty LFSR - InCTF Internationals 2020

tl;dr

1. Find the co-relation between variables in the LFSR equation
1. d == out (75%)
2. a == b (75%)
3. c^d == out (75%)
4. (d!= out) => (c==1) always
2. Solve for the seed using 2000 output bits
3. Try out which among the four possible combinations decrypt the flag

Challenge Points: 804
Challenge Solves: 22
Challenge Author: ph03n1x

## Challenge description

My friend who claims to be someone who is good in statistics, had my new encryption scheme analysed. He claims that there are some problems with my encryption scheme and challenged me to find it out myself. I tried checking the seeds and found that two of them were in the inital parts of their range. But that couldnt be the problem right? Can you try to prove that this scheme is faulty by trying to find out the flag?

## Keygen file

The generate() function generates seeds from the using

The masks for the seeds of the LFSR are provided. Bitlength of the masks are same as those of its corresponding seed.

We know the value of SECRET and the fact that the 2nd seed divides the fourth.

## Finding correlation

The challenge description speaks about the lfsr equation being statistically unsafe.

## | a | b | c | d ||out|

| 0 | 0 | 0 | 0 || 0 |
| 0 | 0 | 0 | 1 || 1 |
| 0 | 0 | 1 | 0 || 1 |
| 0 | 0 | 1 | 1 || 1 |
| 0 | 1 | 0 | 0 || 0 |
| 0 | 1 | 0 | 1 || 1 |
| 0 | 1 | 1 | 0 || 0 |
| 0 | 1 | 1 | 1 || 0 |
| 1 | 0 | 0 | 0 || 0 |
| 1 | 0 | 0 | 1 || 1 |
| 1 | 0 | 1 | 0 || 0 |
| 1 | 0 | 1 | 1 || 0 |
| 1 | 1 | 0 | 0 || 0 |
| 1 | 1 | 0 | 1 || 1 |
| 1 | 1 | 1 | 0 || 1 |
| 1 | 1 | 1 | 1 || 1 |

We end up with the pair bd = [(839, 136757)]

## Finding seed-c

For this we use the relations :

1. c^d == out (75%)
2. (d!= out) => (c==1) always
3. Probability of c is 50%

## Finding seed-a

The bitlength of a is 6 thus fairly easy to brute force :

## Flag

FLAG: inctf{l00k5_l1k3_y0u_r_a_pr0_1n_LFSR}

## Conclusion

Never use a pseudo random sequence which violates Golomb’s principles to generate a key.
Hope you enjoyed the challenge!