A Gentle Introduction to LFSRs
What is an LFSR?
An LFSR is a Linear Feedback Shift Register. It’s a simple way of generating a sequence of numbers that look random.
Used in cryptography and in generating pseudo-random numbers, they are interesting because they are so simple. Shift bits and feed a few of them back into the sequence. That’s it.
Important note: LFSRs are not cryptographically secure on their own. ESPECIALLY 8-bit LFSRs. More on that in the next post on this topic.
How does it work?
An LFSR is a shift register at heart. It’s a series of bits that are shifted in one direction. You can shift left or right. I picked right for this one. If you go left, then reverse everything.
The rightmost bit is the least significant, and the leftmost bit is the most significant. The bits are shifted to the right, and the leftmost bit is replaced with a new bit. The new bit is calculated by XORing together some of the bits in the register. The bits that are XORed together are called the “taps.”
The taps are usually chosen so the LFSR will cycle through all the numbers from 1 to 2^n - 1, where n is the number of bits in the register. This is called a maximal length LFSR. After it cycles through all the numbers, it repeats.
Most of the time, you want the maximum period, but sometimes you want a shorter period; you may want a relatively predictable bad-guy pattern in a game. It’s the same process; use different taps.
Hardware LFSR
These are very easy to do in hardware. We’ll use a 74LS164 shift register and a 74LS86 XOR gate.
The shift register is an 8-bit shift register. It has one input, eight outputs, and a clock input. When the clock input goes from low to high, the bits are shifted to the right (or left if you wire it backward).
The shift register is wired so that the output of the XOR gate is fed back into the input of the shift register.
This one is wired so that the last bit is the output. I’ve duplicated it with a yellow LED to make it stand out.
Python
We can do this in Python to see how it works in software. We’ll use the same taps as the hardware version and the same seed value of 129, which is 0b10000001.
n = 0b10000001
for i in range(260):
nb = (n ^ (n >> 6) ^ (n >> 5) ^ (n >> 4)) & 1
print(f"{i} n: 0b{n:08b} - {n:03d} {nb}")
n = (n >> 1) | (nb << 7)
We printed the loop index, the number in binary, and the number in decimal. The least significant bit, which is also the random bit we’d use if we were using this, is a random number generator.
We can see that the number cycles through 255 numbers and then repeats. Zero is not valid in an LFSR because it would cause the LFSR to get stuck at zero.
We can check that this is a maximal length LFSR by grabbing every number and checking if they are all unique.
n = 0b10000001
states = []
for i in range(260):
print(f"{i} n: 0b{n:08b} - {n:03d}")
nb = (n ^ (n >> 6) ^ (n >> 5) ^ (n >> 4)) & 1
n = (n >> 1 ) | ( nb << 7)
states.append(n)
def check_unique_integers(integer_list):
# Convert the list to a set to remove duplicates
unique_integers = set(integer_list)
# Check if the length of the set is 255 and the range is 1-255
if len(unique_integers) == 255 and min(unique_integers) == 1 and max(unique_integers) == 255:
return True
else:
return False
result = check_unique_integers(states)
print("All integers are unique and in range 1-255:", result)
This returns True, so we know this is a maximum LFSR length.
Vintage computer
You didn’t expect to come to this site and NOT see this done on a vintage computer, did you?
On the Commodore 64, we don’t have XOR in BASIC, and we’ll need to print the binary output to the screen. We’ve done both XOR in BASIC and printing binary in BASIC before, so we’ll use those routines.
10 N=129: REM SET SEED VALUE SO HIGH BIT IS SET
20 T1=2^(8):T2=2^(6):REM TAP 8&6
30 T3=2^(5):T4=2^(4):REM TAP 5&4
40 MASK=2^8-1
50 L=260:REM NUM OF LOOPS
60 FORI=1TOL
70 N = N AND MASK:REM WRAP AT 255
80 PRINTITAB(5)"N:"NTAB(12);
90 GOSUB 250;:PRINTN AND 1
100 NB=0:REM NEW BIT
110 F1=0:F2=0:F3=0:F4=0:REM FEEDBACK BITS
120 IF N AND T1 THEN F1=1
130 IF N AND T2 THEN F2=1
140 IF N AND T3 THEN F3=1
150 IF N AND T4 THEN F4=1
160 NB=(N OR F1) AND NOT (N AND F1): REM XOR
170 NB=(NB OR F2) AND NOT (NB AND F2): REM XOR
180 NB=(NB OR F3) AND NOT (NB AND F3): REM XOR
190 NB=(NB OR F4) AND NOT (NB AND F4): REM XOR
200 NB=NB*2^7:REM 0 OR 128 FOR HIGH BIT
210 N=INT(N/2):REM SHIFT
220 N=NORNB
230 NEXT
240 END
250 REM ::::::::::::::
255 REM PRINT BINARY N
260 FORJ=7TO0STEP-1
270 B=0
280 IFNAND2^JTHENB=1
290 PRINTMID$(STR$(B),2);
300 NEXT
310 RETURN
You might have noticed that we also don’t have a shift operator on the Commodore in BASIC, so we must do that manually. We use the INT function to round down to the nearest integer. In Python, the Commodore shift would look like this:
# 8,6,5,4
n = 0b10000001
for i in range(260):
print(f"{i} n: 0b{n:08b} - {n:03d}")
nb = (n ^ (int(n / 2**8)) ^ (int(n / 2**6)) ^ (int(n / 2**5)) ^ (int(n / 2**4))) & 1
n = (n >> 1 ) | ( nb * 2**7)
Also, the ^ in the code is the up arrow character on the Commodore. You know, this one:
Rust for the fun of it
Let’s give it a shot in Rust. Seems like bringing a gun to a knife fight, but let’s do it anyway.
fn main() {
let mut n: u8 = 0b10000001;
for i in 0..260 {
println!("{:03} n: 0b{:08b} - {:03}", i, n, n);
let nb = (n ^ (n >> 6) ^ (n >> 5) ^ (n >> 4)) & 1;
n = (n >> 1) | (nb << 7);
}
}
It’s close in syntax to the Python version and gives the same output. I’m sure there’s a better way to do it, but this is a good start. It’s also insanely fast. Not that it matters much for an 8-bit LFSR, but it might make a difference for something like a 128-bit LFSR. (double dog dare you to try that)
Extra credit
If you’re building the hardware LFSR, you could do a 16-bit LFSR. Just chain the 74LS164s together. It’ll be up to you to determine the polynomial and the tap positions.
I’d also like to see someone do this on an FPGA. I did it on one of mine and would happily share notes with anyone who wants to try it.
To be continued…
Next, we will explore the 23-bit LFSR in the Commodore 64 SID chip and build a 23-bit LFSR in hardware to determine the tap positions and polynomials. This should allow us to show how LFSRs, when used on their own, are not cryptographically secure. Stay tuned to this bat channel.