Cryptographic pseudo random number generator in embedded system?

Question

I am working on the STM32L152xx that has a peripheral to perform AES128 (CBC) encryption. However, to initialize a random IV I am looking for a good scheme to create cryptographically secure random number sequence. I'm using a simple LCRG (linear congruential generator) as a place holder for now, but this is weak.

I am new to implementing encryption on an embedded platform, so I wonder what's the common practice out there to generate cryptographic PRNG? Or what is a good strategy for choosing the key and the IV?

Most of the answers on StackOverflow for cryptographic PRNG refers to 3rd party library that isn't available on this platform. However, if it's worth the try, I can attempt to port it. Links and pointers to resources would be helpful too!

I have access to the system clock and accelerometers on board. I'm running FreeRTOS. Thanks!

Answer 1

I know this is a rather old question, but since no one mentioned cryptographically secure PRNG yet, I thought I'd like to chime in. "Cryptographically secure" IVs and keys shall be generated using crypto PRNG, e.g. HMAC_DRBG or CTR_DRBG. The former is based on HMAC, the latter is based on AES in CTR mode. These two PRNGs are available in PolarSSL, which also runs on FreeRTOS. Take care NOT to use DUAL_EC_DRBG, this is backdoored by the NSA and shall never be used anymore.

Most importantly, you need an entropy source to seed these PRNGs. Unfortunately this is the difficult part on embedded devices. You can find some ideas in this blog, e.g. taking the ADC output.

Specifically on IVs, another important criterion is that it should be unpredictable. That is, there should be no systematic way for an attacker to predict the IV of the next ciphertext, given the current ciphertext. This is to avoid BEAST-like attack on TLS 1.0.

Finally, for this sort of questions, you'd have a better chance of getting excellent answers on crypto.stackexchange.com.

Answer 2

You're probably going to need to define "Cryptographically Secure" or your application a little better. If this were for a game on a mobile phone, you could probably use the accelerometer as a source of randomness. If you're trying to sign x.509 certificates, you would might consider some attached hardware that measures radioactive decay.

In all seriousness, depending on the strength of the "Randomness" that you need consider the following:

1. The current 32-bit value of a clock that ticks every nanosecond (Period of about 4 seconds - probably "Random" enough depending on how frequently you need seeds). You'll need to make sure that you don't grab this value in a deterministic way. If when you grab it is based on user input, then it's probably OK.
2. An Avalanche Noise Generator fed into a Schmitt trigger input.
3. The Exclusive OR of all of the axes of you're accelerometer (May not be good if the thing sits still all the time, unless it picks up vibrations in its normal application). If this is for a radio that gets carried around, then this is probably OK.
4. The value of a large chunk of uninitialized memory (you'll probably want to hash it because large sections of uninitialized memory can contain similar values from power-on to power-on). Also, if your device doesn't get completely powered off, then this is probably no good.
5. Some combination of one or more of the above (Exclusive OR is probably the easiest way to combine two of the above outputs)
6. Comedy option: A CCD Camera pointed at a lava lamp

Any of the above methods may need to have some sort of de-bias algorithm applied to them. The simplest one is to consider your input 2-bits at a time. If the 2 bits are equal, discard them. 0b10 becomes 1 and 0b01 becomes 0. That will ensure that you get more-or-less the same number of 1s and 0s in your final random value.

Finally, if this is for something serious you should disregard all of the above advice and NOT ROLL YOUR OWN CRYPTO. Find some API for your platform that has been vetted already and use that. Testing an algorithm for randomness is very difficult to do.

Perhaps consider the F‑2 series of the STM32 core which apparently contains a hardware RNG

Answer 3

Pete Braughman's answer covers what a good answer to this question should: unbiasing and combining weak sources of entropy. I'd be a bit hesitant to use uninitialised memory in the process; I can think of scenarios where a system based on the assumption that uninitialised memory isn't previously used by a malicious user might end up compromised. Other than that, there isn't much I can disagree with.

In the interest of saving you time reinventing a possibly already invented wheel, my suggestion would be to take a brief look at cryptlib providing you haven't already done so; "cryptlib's highly portable nature means that it is also being used in a variety of custom embedded system environments including AMX, ChorusOS, eCos, FreeRTOS/OpenRTOS, uITRON, MQX, PalmOS, RTEMS, ThreadX, T-Kernel, uC/OS II, VDK, VxWorks, and XMK." This library likely does most of the work for you; Assuming it's feasible to use cryptlib, you may only need to feed it with random information (from multiple sources): "The random-data-gathering operation is controlled with the cryptAddRandom function, which can be used to either inject your own random information into the internal randomness pool or to tell cryptlib to poll the system for random information."