Random Numbers Matter: Ode to LFSR, And The Future?
Random Numbers Matter: Ode to LFSR, And The Future?
At the core of your online security is the generation of random numbers. If these numbers are not random, there’s a good chance your security will be compromised. Every day trillions of random numbers are created and used in the creation of secure tunnels for our data.
So, are our random numbers actually random? Well, they are not actually truly random numbers but are pseudo-random. This is where we have a mathematical process for creating the random number and based on a random seed value. This random value is typically based on some random activity within the operating system. Now a new presentation by Jason Donenfel (zx2c4) outlines some of the flaws contained within the Linux Kernel for creating random numbers [here] [presentation]:
The method uses LFSR (Linear Feedback Shift Register), and which goes back to 1994. It is still generally old code that has been modified to suit a wide variety of needs. Overall, we have a given state for our random number generation (S), and where the next state is computed by taking a matrix (A) and multiplying it with the current state, and then EX-ORing this with X:
S’= A.S ^X
Take a state vector, S, multiply it by some matrix, A, and add an input vector, X, to produce new state. For example, we could have a state, matrix (A) and X defined by four-byte values, and then compute the current and the next states with:
import numpy
S=[5,7,4,2]
A=[8,2,3,4]
X=[6,3,9,5]
S = (numpy.multiply(S,A)^X) % 256
print (S)
S = (numpy.multiply(S,A)^X) % 256
print (S)
S = (numpy.multiply(S,A)^X) % 256
print (S)
In this case, we have a 32-bit state value. The output of this is:
[46 13 5 13]
[118 25 6 49]
[182 49 27 193]
Typically we represent these values as polynomials, such as for [46, 13, 5, 13] as:
p = 45x³+13x²+5x+13
With our random number generation, we represent with GF(2), and where our polynomial factors are either 0 or 1. And, so a bit value (k) of 1001 0110 is represented as:
k = x⁷ + x⁴ + x² + x
We can then operate on polynomials for our random number generation. Here is an example of GF(2) multiplication:
https://asecuritysite.com/principles/mod2
The presentation outlines some of the weaknesses and history of LFSR, but looks to the future, and proposes an improved method using the BLAKE2s random stream method, and ChaCha20 to scramble up the randomization method. Go watch for yourself:
Conclusions
A single bit that is revealed drops the security level of an encryption key by a half. Another bit, by a quarter. If we have a 128-bit encryption key and discover a single bit, we reduce the security level to 64 bits. As the limits of cracking are around 72 bits, this makes it possible to crack a 128-bit key. So, we need truly unguessable numbers. If you want to learn more about random numbers, try here: