Cheapest possible true random number generator

Other Hardware General Electronics
1

I want to build a mini cryptography assistant tool out of my Arduino Leonardo. There is no way any real life crypto like AES can run on this in reasonable time but it do have some easy way to build an true random number generator which is not so easy on a computer (and not so secure given the involvement of NSA in those companies who produces those RNGs for computers.)

I am here to ask your opinion about the cheapest possible way of doing this, preferably use only my existing stock and a perfboard. My existing stock semiconductor includes LM358 dual op-amps, 74HCxx logic chips, 555 timers, unbranded photodiodes, unbranded LEDs, 1N4007 rectifier diodes, 1N4148 signal diodes, 2N7000 MOSFETs, 2N3904, 2N3906 and 2N2222 bipolar transistors, and I have a stock of common values of resistors, ceramic and polyester caps.

Possible ways I can think of:

  • Use an op-amp to amplify the non-common-mode noise of two reverse biased diodes from the same batch. This should have quantum randomness as it is based on electrons tunnelling across the reverse biased PN junction, and it was used in some Intel chip. BOM: 1x LM358, 2x diode, several passives.
  • Use an op-amp to amplify the thermal noise across a resistor. Not quantum random, but chaos theory random. Good enough for my not-so-CIA crypto. BOM: 1x LM358, several passives.
  • Use several 555s free running at different frequencies, and try to extract randomness out of them. VIA used this design. BOM: several 555s and passives.
  • Heat-shrink a photodiode into a makeshift geiger counter and place something with some non-lethal radioactivity near it. This is also quantum random as it is based on the event of radioactivity. BOM: 1x photodiode, 1x heat shrink, 1x radioactive source.
2

Sounds like you already have it covered.... :slight_smile:

One thing you should probably do is implement two different RNGs then combine the result (XOR the two readings together).

Very often the best RNGs are just the combination of outputs from two or three simpler ones, eg. George Masaglia's KISS generator

3

Zener diode noise is traditional, amplify. However how to turn analog noise into
unbiased numbers is the tricky part. You need to consider monitoring for failure,
ie performing continuous statistical analysis. You also need to filter against external
signal injection into the noise circuitry if your threat model warrants it.

Low voltage zeners are true zeners (tunneling), higher voltages are just reverse-biased
avalanche breakdown.

BTW what is your threat model?

4

fungus:
Very often the best RNGs are just the combination of outputs from two or three simpler ones, eg. George Masaglia's KISS generator

We're talking cryptographic randomness levels, the KISS generator is not cryptographic.

One of the important requirements of cryptographic randomness is freedom from state
leakage - you don't want someone to be able to compute past or future output of the
generator given any feasible amount of output from it. Statistical performance is
a necessary but not sufficient condition for cryptographic randomness.

5

MarkT:
Zener diode noise is traditional, amplify. However how to turn analog noise into
unbiased numbers is the tricky part. You need to consider monitoring for failure,
ie performing continuous statistical analysis. You also need to filter against external
signal injection into the noise circuitry if your threat model warrants it.

Low voltage zeners are true zeners (tunneling), higher voltages are just reverse-biased
avalanche breakdown.

BTW what is your threat model?

So another random source is to pick a Zener diode and amplify that reverse noise? Seem like an idea but how (I would assume that an op-amp is called for?)

I think I can feed the two random sources into two analog inputs of the Arduino and let it do some basic stream merging, fault tracing and whitening. I can ask the computer to do some further bitstream processing.

I have a peeping tom of a government (PRC, or I should say a Big Brother of a government) and I don't want them to mess with my correspondence. By implementing this TRNG I can use my Arduino to generate key files for TrueCrypt, feed quality entropy into my OS X or Linux system to improve their crypto (especially GPG) and use that is a quality source for SSH keys.

6

sorry to go slightly off topic, but it made me think of this one:

7

https://code.google.com/p/avr-hardware-random-number-generation/

8

even most randomness is pseudo random not true?
But to save space in SW would go with a HW simple circuit that should meet most needs.
http://www.freeinfosociety.com/electronics/schemview.php?id=1362

9

But once you've encrypted it, what then? If you're going to encrypt it in such a fashion that it can NEVER be retrieved, you might just as well delete it in the first place.

If you're going to send the encrypted data to someone else to retrieve, whatever method you use, has to be reversible. If it's based on some truely random chaotic phenomenon, how are you going to build a decryption algorithm to make it retrievable?

10

MarkT:
We're talking cryptographic randomness levels, the KISS generator is not cryptographic.
http://eprint.iacr.org/2011/007.pdf

Did I claim it was?

11

technix:
I have a peeping tom of a government (PRC, or I should say a Big Brother of a government) and I don't want them to mess with my correspondence. By implementing this TRNG I can use my Arduino to generate key files for TrueCrypt, feed quality entropy into my OS X or Linux system to improve their crypto (especially GPG) and use that is a quality source for SSH keys.

OS X ... Linux?

If you're using big machines then just point a webcam at a lava lamp (or a street) and cryptographically hash the output images.

12

fungus:

technix:
I have a peeping tom of a government (PRC, or I should say a Big Brother of a government) and I don't want them to mess with my correspondence. By implementing this TRNG I can use my Arduino to generate key files for TrueCrypt, feed quality entropy into my OS X or Linux system to improve their crypto (especially GPG) and use that is a quality source for SSH keys.

OS X ... Linux?

If you're using big machines then just point a webcam at a lava lamp (or a street) and cryptographically hash the output images.

It is a notebook we are talking about. I need it to be portable. That is why Arduino kicks in here, being a portable device.

13

KenF:
But once you've encrypted it, what then? If you're going to encrypt it in such a fashion that it can NEVER be retrieved, you might just as well delete it in the first place.

If you're going to send the encrypted data to someone else to retrieve, whatever method you use, has to be reversible. If it's based on some truly random chaotic phenomenon, how are you going to build a decryption algorithm to make it retrievable?

For data in storage after I encrypted it I can store it safely. I have an SD card full of cryptographic keys (and it is encrypted and usually not in my computer) and several spare hard drives for storing encrypted data. Also by using this true RNG I can enhance the quality of GPG, SSH and SSL/TLS session keys (amount of entropy in cryptographic keys used for data in motion) generated by my computer, allowing better quality of encryption of my Internet access and communication (HTTPS, SSH-tunneled traffic and GPG-encrypted correspondence all improves)

For example: I can pay a visit to the friend of mine that I want to send secrets to, and perform a GPG public key exchange offline. Then if sensitive data is to be send, it is encrypted using this TRNG enhanced cryptographic symmetric key and the key is sent asymmetrically encrypted. Unless the algorithms used in GPG is broken (my default: RSA-4096 and AES-256, both are good enough for CIA) or my friend is a "blabbermouth" my secrets are safe.

14

spicetraders:
even most randomness is pseudo random not true?
But to save space in SW would go with a HW simple circuit that should meet most needs.
http://www.freeinfosociety.com/electronics/schemview.php?id=1362

There is no SW TRNG. No software can implement that, only PRNG and I do have some quality CSPRNG on my computer already. I even designed my own out of SHA-512.

There is no way CSPRNG can beat TRNG in entropy and randomness quality.

15

technix:
For example: I can pay a visit to the friend of mine that I want to send secrets to...

In which case a one-time pad is the obvious choice.

16

OTP would be a bit too challenging to implement as there are difficulties that I can't visit him too frequently to refresh OTPs, and if I ever want to implement the OTP I still need this TRNG to generate the pad.

17

technix:

spicetraders:
even most randomness is pseudo random not true?
But to save space in SW would go with a HW simple circuit that should meet most needs.
http://www.freeinfosociety.com/electronics/schemview.php?id=1362

There is no SW TRNG. No software can implement that, only PRNG and I do have some quality CSPRNG on my computer already. I even designed my own out of SHA-512.

There is no way CSPRNG can beat TRNG in entropy and randomness quality.

That's never the point though, the point is always "does it address the threat model"
being sidetracked about the elegance or theoretical properties is always a
way to forget what a real attacker will attack, which is always the weakest
link in the chain.

A CSPRNG seeded with enough entropy is a powerful tool, but like all sources
of randomness the weakest point is the platform you run the thing on - run it on
a general purpose computer and you're at the mercy of every security breach and
deliberate back-door on that software ecosystem. Run it on a dedicated hardware
module with no internet access and tempest-proofing and you start to get somewhere.
And this applies to the keys generated from it and all your plaintext too...

The simplest way for a powerful adversary to bypass your security is to install
keyboard and audio sniffers surruptiously in your machine, so unless you defend
against that by intrusion-detection software you might be wasting your effort
improving encryption... And unless you use protocols that are robust against
man-in-the-middle attacks all your encryption gives is a false sense of security
on the network too...

I have an SD card full of cryptographic keys (and it is encrypted and usually not in my computer)

Using a pre-computed SDcard full of randomness is a nightmare, never do this.

Firstly it can be lost/stolen and then all past keys are potentially exposed. In particular
session keys should never be stored after the session has completed.

Secondly someone might snarf a copy without you knowing. You do have
to sleep sometime! Then all future keys are exposed too. Hey, they might
even change the keys to all zeroes...

Thirdly you risk re-using the same key(s), again compromising all security
on those sessions. Generating randomness on the fly cannot accidentally
repeat a key.

True some of these problems also apply to the state of a CSPRNG, but the state
is a lot smaller than a cache of thousands of keys, and can regularly have more
entropy mixed into it to give forwards secrecy.

Also if you have bad sectors on the card (not that unusual) you could
end up using zero-entropy keys without even knowing it as the card firmware
remaps sectors and exposes all 0xFF's in the middle of your data.

18

I do intend to use this Arduino as an offline TRNG. I also do not keep state in EEPROM so even if the device is stolen and the sketch get reverse engineered (actually I would even publish the sketch, as it contain only nothing-up-my-sleeve numbers and program logic) it is near impossible to guess its output sequence.

The SD card are used to store symmetric key for data kept in store (TrueCrypt key files), as well as asymmetric keys for session keys for data both in motion and in store (GPG keychain). The symmetric key files are only used once for each TrueCrypt volume. The SD card itself is TrueCrypt encrypted with a passphrase.

Speaking of IDS, I do have one on my Linux-based router that is constituted of what I can obtain from Debian software repository.

Moderator edit: quote reduced to something reasonable