tl;dr
 Find the corelation between variables in the LFSR equation
 d == out (75%)
 a == b (75%)
 c^d == out (75%)
 (d!= out) => (c==1) always
 Solve for the seed using 2000 output bits
 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?
Attachment
1   [keygen2.py](../InCTFi20FaultyLFSR/keygen2.py) 
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.
1  def generate() : 
We know the value of SECRET and the fact that the 2nd seed divides the fourth.
1  SECRET = 14810031 
Finding correlation
The challenge description speaks about the lfsr equation being statistically unsafe.(a^b)^(ac)^(bc)^(cd)
Truth Table
1   a  b  c  d out 
From the truth table we find out the following :
 Probability distributions of [a,b,c,d] = [50%,50%,50%,75%]
 a == b (75%)
 d == out (75%)
 (d!= out) => (c==1) always
Finding seedd (& seedb)
Bitlength of d = 18
Thus range is [2**17,2**18  1]
We know two of the seeds are in the initial part of their range. Assuming this is the one :
We also know that the second seed divides this one. We shall also incorporate this fact into the script.
1 

We end up with the pair bd = [(839, 136757)]
Finding seedc
For this we use the relations :
 c^d == out (75%)
 (d!= out) => (c==1) always
 Probability of c is 50%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24def solve_c() :
pair = []
poss_d = solve_d()
for b,d in tqdm(poss_d) :
for i in tqdm(range(2**14,2**15)) :
dt = lfsr(d,masks[3],masks[3].bit_length())
ct = lfsr(i,masks[2],masks[2].bit_length())
ct1 = ct2 = 0
for j in range(160) :
dt.next()
ct.next()
for j in remdata[:2000] :
dtmp = dt.next()
ctmp = ct.next()
if dtmp!=j and ctmp!=1 :
break
if ctmp == j :
ct1+=1.0
if ctmp^dtmp == j :
ct2+=1.0
if ct1/2000 > 0.45 and ct1/2000<0.6 and ct2/2000>0.74 :
pair.append((b,i,d))
print (i,ct1/2000,ct2/2000)
return pair
Finding seeda
The bitlength of a is 6 thus fairly easy to brute force :
1 

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!