Click to expand challenge code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| package main
import (
"bufio"
"crypto/rand"
"encoding/hex"
"fmt"
"log"
"math/big"
"net"
"strings"
)
const LEN = 31
const MASK = (1 << LEN) - 1
const FLAG = "FL1TZ{?????????????????????????????}"
var taps1 = []int{/*?, ?, ?, ?*/}
var taps2 = []int{/*?, ?, ?, ?*/}
type LFSR struct {
state uint64
taps []int
count int
}
func (l *LFSR) rekey(newseed uint64) {
l.state = newseed
}
func newLFSR(taps []int) *LFSR {
seed := genRandSeed()
return &LFSR{state: seed, taps: taps}
}
func (l *LFSR)lfsrStep() uint8 {
feedback := uint64(0)
if l.count % 420 == 0 { //nice
l.rekey(genRandSeed())
}
for _, tap := range l.taps {
feedback ^= (l.state >> tap) & 1
}
l.count++
output := l.state & 1
l.state = ((l.state >> 1) | (feedback << (LEN - 1))) & MASK
return uint8(output)
}
func genRandSeed() uint64 {
max := new(big.Int).Lsh(big.NewInt(1), LEN)
newseed, err := rand.Int(rand.Reader, max)
if err != nil {
log.Fatalf("Failed to generate random seed: %v", err)
}
return newseed.Uint64()
}
func encrypt(pt []byte, lfsr1 *LFSR, lfsr2 *LFSR) []byte {
ct := make([]byte, len(pt))
for i, ptByte := range pt {
byteVal := byte(0)
for bit := 0; bit < 8; bit++ {
b1 := lfsr1.lfsrStep()
b2 := lfsr2.lfsrStep()
ksb := b1 ^ b2
ptb := (ptByte >> (7 - bit)) & 1
ctb := ptb ^ ksb
byteVal |= (ctb << (7 - bit))
}
ct[i]= byteVal
}
return ct
}
func sa55enLkarhba(l1, l2 *LFSR) {
for i := 0; i < 1337; i++ {
l1.lfsrStep()
l2.lfsrStep()
}
}
func handleConnection(conn net.Conn) {
defer conn.Close()
l1 := newLFSR(taps1)
l2 := newLFSR(taps2)
sa55enLkarhba(l1, l2)
conn.Write([]byte("How far can you go, before cycling back to your beginnings...\n> "))
reader := bufio.NewReader(conn)
hexStr, err := reader.ReadString('\n')
if err != nil {
log.Printf("Read error: %v", err)
return
}
hexStr = strings.TrimSpace(hexStr)
cipher, err := hex.DecodeString(hexStr)
if err != nil {
conn.Write([]byte("Invalid hex input\n" + err.Error() + "\n"))
return
}
plain := encrypt(append(cipher,[]byte(FLAG)...), l1, l2)
conn.Write([]byte(hex.EncodeToString(plain)))
conn.Write([]byte("\n"))
}
func main() {
ln, err := net.Listen("tcp", ":5012")
if err != nil {
log.Fatalf("Failed to listen: %v", err)
}
defer ln.Close()
fmt.Println("Oracle listening on port 5012")
for {
conn, err := ln.Accept()
if err != nil {
log.Printf("Accept error: %v", err)
continue
}
go handleConnection(conn)
}
}
|
This is the only LFSR challenge in the ctf (but not the only prng one). It’s also a new concept for many tunisian crypto players, so I wanted to introduce it in a unique way, with a Double LFSR!!
Analysis
Functionality
We need to understand what the challenge server does in the first place:
- It has 2 internal LFSRs to supply a constant stream of pseudorandom bits
- Each LFSR starts with a random state, that gets refreshed to a new random one every
420 bits - The 2 output bits of the LFSRs are xored before using the resulting bit to encrypt the plaintext
- At the start, the first
1337 output bits are discarded - We can enter an arbitrary length plaintext, and we’ll get out
plaintext+FLAG xored with the LFSR stream
With this intuition, we should know that we have a 420 bit window to “break” the LFSR state (meaning, we should supply offset+(420-288)bits of plaintext to leave some area for the flag before the next reset)
The offset is a stream of random data with length = 1337 % 420 and lenght = 4n, this will align our actual payload close to the start of the next radom reset, giving us the maximum possible number of bits to work with.
Berlekamp Massey
LFSR are a really interesting primitive: They may not look like it, but they translate elegantly into finite field arithmetics where taps can be expressed as as polynomial in $GF(2)$ where $tap_i$ tranlates to a coefficient of $1$ for the $x^i$ monomial of the feedback polynomial.
This lets us calculate the expected order of the LFSR aswell as openig the door to all the whacky trick in the realm of finite fields.
One of those trick is to translate two interacting LFSR states (with taps $T_1$ and $T_2$) into a single LFSR with taps $T_3$ and order $n_3 \le n_1 + n_2$ with $n_1$ and $n_2$ being equal to $31$ in this case.
The algorithm responsible for collapsing the two LFSRs into one is called the Berlekamp Massey, which spits out a feedback polynomial equivalent to the combined output of the input polynomials.
To do so though, we need enough information to reconstruct the states ($n_{bits} > 2n_3$ bits of the keystream to be exact)
That comes out to at least 124 bits, which we can recover easily.
To my surprise, sagemath already includes a builtin implementation for this algorithm, so it’ll be doing the heavy lifting for us!
Solution
Plan
- Send appropriate length payload of
0 bits - Discard the offset and save the ecrypted flag
- Recover the feedback polynomial
- Rebuild the LFSR with the new taps
- Xor the ciphertext with the resulting keystream
Solver
Click to expand solver code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| import copy
from pwn import *
from sage.all import *
from sage.matrix.berlekamp_massey import berlekamp_massey
L = 62
MASK = (1 << L) - 1
io = remote("20.218.234.6", 1004)
payload = b"0" * (86 + 128//4)
io.sendlineafter(b"> ", payload)
t = io.recvline().strip()
print(f"Received hex: {t.decode()}")
bb = bytes.fromhex(t.decode())
tb = bb[43:-37]
bits = []
G = GF(2)
for byte in tb:
for i in range(8):
bits.append(G((byte >> (7 - i)) & 1))
poly = berlekamp_massey(bits)
print(f"Polynomial: {poly}")
coefs = poly.list()
print(coefs)
coefs.pop(-1)
print(coefs)
coefs= coefs[::-1]
taps = []
for i in range(len(coefs)):
if coefs[i]:
taps.append(61-i)
print(f"Taps: {taps}")
class LFSR:
def __init__(self, seed, taps):
self.state = copy(seed)
self.taps = taps
def next(self):
newbit = 0
for tap in self.taps:
newbit ^= (self.state >> tap) & 1
out = self.state & 1
self.state = ((self.state >> 1) | (newbit << (L - 1))) & MASK
return out
def get_bytes(self, n):
result = []
for _ in range(n):
next_byte = 0
for i in range(8):
next_byte |= (self.next() << (7-i))
result.append(next_byte)
return bytes(result)
seed = int(''.join(str(b) for b in bits[:62])[::-1], 2)
output = ""
lf = LFSR(seed, taps)
stream = lf.get_bytes(128*2)
print(f"Generated bits: {stream.hex()}")
print(f"Received hex : {tb.hex()}")
rest = bb[43:]
print(len(rest))
pt = bytes([b ^ s for b, s in zip(rest, stream)])
print(f"Recovered plaintext: {pt}")
|
FL1TZ{C4nT_g3t_th3_C1ty_0UT_th3_m4n}
