Building a Software RNG v1.0 with Timers, LFSR, XOR Shift, and FNV Hash algorithms

-

Why a Software Random Number Generator?

The STM32F401 microcontroller lacks a hardware Random Number Generator (RNG), making a Software RNG necessary for generating random numbers. While hardware RNGs provide higher-quality randomness, a Software RNG can still achieve essential functionality by generating unique cryptographic keys, mimicking real-world randomness, and introducing system unpredictability.





How the Software RNG Generates Random Numbers

The execution of the Software RNG begins by Generating a Hardware seed using the STM32 timers, providing a source of entropy based on system behavior. Then, a Linear Feedback Shift Register (LFSR) is applied to the seed to add a bit of randomness by shifting and modifying the seed value. The result of the LFSR operation is then combined with the hardware seed using the XOR (Exclusive OR) operation. Finally, the combined result is processed using the FNV Hash function, which generates a 32-bit random number.

Extracting Hardware-based Seed 




To generate the hardware seed, TIM2 is set up to Count Upwards at 16 MHz, while TIM3 counts down at 25 kHz. The counter values from both timers are then XORed together to produce a combined seed value, which is then returned.

LFSR Transformation of Seed




The LFSR operation extracts the least significant bit (LSB) of the input seed and the seed is then right-shifted by one bit. If the original LSB was set, a feedback value (0xB400) is XORed with the shifted seed. The resulting value is returned as the new LFSR output. 

Performing XOR Shift on Seed




The XOR Shift algorithm performs three bitwise operations on the variable, state. First, it XORs  state with itself shifted left by 13 bits, then XORs it with  state shifted right by 17 bits, and finally XORs it again with  state shifted left by 5 bits. These bitwise operations mix the bits of the seed, producing a new value, which is then returned.

Combining Results and Generating Hash




It generates a hash value using the FNV Hash Algorithm. It starts by initializing a constant hash value (2166136261U). The input value (val) is then XORed with this hash value. After that, the result is multiplied by the FNV prime constant (16777619). The final hashed value is returned.

Analyzing the Randomness of the Generated Values 

To assess the effectiveness of the RNG library, I generated a sample of 10,000 random numbers and stored them in the W25Q64 Flash memory for analysis. Each 32-bit random number was saved on a separate page, with one entry per page, for clarity. The library exhibited remarkable performance, generating 100,000 32-bit random numbers in just 1.58 seconds, with the system clock running at 16 MHz. Below are the scatter plots of the 10,000 random numbers across three different test cases.

This scatter plot represents the random numbers generated using a single entropy source, with only TIM2 counting up at 16 MHz. The output was then XORed with a seed constant to introduce variability.

This scatter plot depicts the random numbers generated using two entropy sources: TIM2 counting up and TIM3 counting down. The counter values were XORed together and then XORed with the seed constant to introduce variability.

The previous two samples were collected consecutively without any delay, which could potentially introduce predictability in the long-term behavior of the random numbers. To address this, I introduced variability in the sampling process by adding an adaptive delay between each call to the SoftRNG_Generate() function in every iteration of the loop.

Refinements to the Existing algorithms

The scatter plots suggest that the effectiveness and randomness of this Software RNG library are limited. The entropy values in the three cases were 6.67 bits, 6.53 bits, and 6.54 bits, respectively. When random numbers were generated with an adaptive delay, the autocorrelation showed improvement compared to the previous two cases.

To enhance randomness, an additional entropy source, such as the onboard temperature sensor, could be incorporated. During hardware seed processing, we could interleave the bits from the LFSR and XOR operation outputs, apply multiple rounds of hashing, and implement a stateful RNG design that maintains a seed state between successive calls to the SoftRNG_Generate() function.

Checkout my GitHub repository for the source code (v1.0) of this library

Popular posts from this blog

Cifradopro: A baremetal Hardware Security Module using the STM32L4S5 Cortex-M4 MCU

-
Image
What is CifradoPro? Cifradopro is a baremetal Hardware Security Module based on the STM32L4S5ZI microcontroller. It is capable of generating Random Keys in various sizes, Encrypting plaintext, and Decrypting ciphertext using the Advanced Encryption Standard. Additionally, it can create One-Time Pads of different lengths and generate a Hash of input data using the Secure Hashing Algorithm. The module can store the generated cryptographic keys in an external memory device. As a safeguard against physical tampering, the device is designed to erase the contents of the external memory if the enclosure is breached. The device leverages the Random Number Generator , AES Hardware Accelerator , and HASH Processor of the STM32L4S5ZI for cryptographic operations. It employs the built-in UART peripheral for device control via a serial terminal application such as PuTTY. The external memory, a  256kBit EEPROM from Microchip , is interfaced using the STM32L4's onboard I2C Peripheral. A GPIO pin...
Read more

Capturing images using the Digital Camera Interface | STM32L4 | DCMI | CMSIS

-
Image
Digital Camera Interface The DCMI (Digital Camera Interface) is a synchronous parallel interface designed to receive a high-speed data stream from an external CMOS camera module. It offers compatibility with 8-bit, 10-bit, 12-bit, or 14-bit camera modules.  The DCMI peripheral supports Embedded Line and Frame synchronization methods in addition to the Hardware Synchronisation from the CMOS Camera Module. It has two operating mode, namely Continuous or Snapshot mode. Additionally, it offers a crop feature and supports various data formats, including 8/10/12/14-bit progressive video (Monochrome or Raw Bayer), YCbCr 4:2:2 Progressive Video, RGB 565 Progressive Video, and Compressed Data in JPEG format.   For more information on the DCMI peripheral, read the Training material for DCMI on STM32L4 from STMicroelectronics . DCMI Registers The DCMI peripheral has Control and Status registers for the DCMI Core and Interrupts. It also has a few registers for handling Data synchronizatio...
Read more

Designing a Software-Based Wear Leveling Subsystem for W25Q64FV Serial Flash Memory

-
Image
NOR Flash Memories & the Need for Wear Leveling NOR Flash is a type of non-volatile memory used to store data that needs to persist even when a device is powered off. NOR Flash is typically organized into sectors or blocks, which can be individually erased and reprogrammed.  Due to the physics of flash cell structure, memory cells suffer from “wear” with every Program/Erase cycle (P/E cycle). This means flash memory has a finite usable life. If a flash memory exceeds this limit, the storage capability becomes unreliable. Wear Leveling is a common technique used by storage media  to enhance the longevity of the storage media. Flash memory cells can only be programmed from a 1 to a 0 state. In order to set any cell from 0 to 1 state, the cell has to be erased to a 1. In order to update any already programmed memory sectors/blocks, the sectors/blocks have to be first erased and then reprogrammed, hence the P/E cycle. Depending on how of...
Read more