## Wednesday, March 5, 2014

### Boston Key Party CTF 2014 - Door 1 - Crypto 500 - [Team SegFault]

Description:
You need to open door no 5 in a secret facility. We have been trying to brute-force the door without success. One of our agents was able to infiltrate the control room and take a picture. The server is known to use some kind of problematic random number generator for the authentication. Open the door. The service is accessible on 54.186.6.201:8901, good luck with your mission. UPDATE/HINT: LFSR.

We were given an image file with some info, showing the challenge and response communication.
To start with, it was my friend who asked me to look into this problem and said, the challenge received might be seed for LFSR and output sequence might be the expected reply. Lets see.

[*] The challenge received is a 4 byte value. If it has to be seed for LFSR, then the LFSR should have 32 registers to deal with 4 bytes
[*] The screen capture shows a big number which might be a possible output sequence

Below is the number:
```0xe4ca194f7b2ab2b3fbe705c
```
This is how the bitstream looked like:
```11100100110010100001100101001111011110110010101010110010101100111111101111100111000001011100
```
With 92 bits of output sequence in hand and a possible 32 register LFSR, we can find the LFSR feedback function by feeding the Berlekamp-Massey algorithm with 64 bits(2 * length of LFSR) of the output sequnce.

The feedback function found is:
```1 + x + x^4 + x^5 + x^6 + x^16 + x^19 + x^31 + x^32
```
The degree of the polynomial is 32, which supports the possible length of LFSR being 32.

Now, if the sequence 0xe4ca194f7b2ab2b3fbe705c can be generated using the above function and seed 0xf2985327, then we are on right track.
```#!/usr/bin/env python

chall = 0xf2985327
seed = [int(i) for i in bin(chall)[2:]]
# x + x^4 + x^5 + x^6 + x^16 + x^19 + x^31 + x^32 + 1
feedback_function = [1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

output = ''
for i in range(96):
feedback = 0
output += str(seed[-1])
for i in range(len(seed)):
feedback = (seed[i] * feedback_function[i] + feedback) % 2
seed = [feedback] + seed[:-1]

print hex(int(output,2))
```
```[ctf@renorobert BKP]\$ python cry500.py
0xe4ca194f7b2ab2b3fbe705ccL
```
The generated output sequence is equal to the one in the screen capture, so we got the LFSR design right!
Now the amount of bits to be sent as response should be bruteforced. I incremented byte by byte from 96 bits, but soon I was told in IRC that 296 bits is all thats needed. Sending a 296 bits reply gave us the flag.
```0x8d3c22ea
0x57443cb1e7daf6a45be190d11d3a1b4902633133d62d5900fd134c3caa91d5c233342fce62
response
> Door open: n0t_s0_r4nd0m_029210
```
Flag for the challenge is n0t_s0_r4nd0m_029210