The ChaCha cryptographic random number generator (CSPRNG) is in the news thanks to Google’s Adiantum project. I’ll discuss what’s going on, but first a little background.
The name of the project comes from a genus of fern. More on that below as well.
One-time pads
The one-time pad is a provably unbreakable way to encrypt things. You create a sheet of random bits and give your counterpart an exact copy. Then when it comes time for you to send an encrypted message, you convert your message to a stream of bits, XOR your message with the random bits you exchanged previously, and send the result. The recipient then takes the XOR of the received message with the pad of random bits, and recovers the original message.
This is called a one-time pad because it’s a pad of bits that you can only use one time. If you reuse a pad, it’s no longer unbreakable.
One-time pads are impractical for a couple reasons. First, it’s hard to generate truly random bits, especially in bulk. Second, exchanging the pads is almost as difficult as exchanging messages.
Stream ciphers
So here’s a bright idea: we’ll get around both of the problems with one-time pads by using pseudorandom bits rather than random bits! The both parties can generate their own random bits.
Many people have had this idea, and it’s not necessarily a bad one. It’s called a stream cipher. The problem is that most pseudorandom number generators are not up to the task. You need a cryptographically secure RNG, and most RNGs are far from secure. The ChaCha RNG, however, appears to be good enough to use in a stream cipher, given enough rounds of scrambling [1], and Google is using it for full disk encryption in Android devices.
Full disk encryption
If you forget your password to your computer, you may not be able to access your data, but a thief still could by removing the hard drive and accessing it from another computer. That is, unless the disk is encrypted.
Full disk encryption on a laptop, such as BitLocker on Windows or FileVault on OSX, is usually implemented via AES encryption with hardware acceleration. If you don’t have special hardware for encryption, AES can be too slow.
Adiantum: ChaCha encryption on Android
On low-end devices, ChaCha encryption can be around 5x faster than AES. So Google is using ChaCha for Android devices, using what it calls Adiantum.
You can read the technical details in [2], and you can read more about the ChaCha random number generator in [3].
So where does the name Adiantum come from? It’s a Victorian name for a genus of maidenhair ferns, symbolic of sincerity and discretion.
More on CSPRNGs
[1] Adiantum using ChaCha with 12 rounds. TLS 1.3 uses ChaCha with 20 rounds.
[2] Adiantum: length-preserving encryption for entry-level processors by Google employees Paul Crowley and Eric Biggers.
Dr. Cook,
Is there any way to use machine learning to decipher RNG? In theory the idea seems possible , but I couldn’t find so much in literature. What’s your take on the matter?
Thanks.
Jeff, I doubt it. There may be some indirect way to use machine learning, but machine learning works at an abstract, black-box level. “We don’t know what makes this thing tick, but let’s try assuming that the inputs are mapped to the outputs by something with this shape.” Cryptographic attacks are much more specific, trying to exploit fine details. For example, timing attacks try to squeeze information out of how long it takes code to run.
Dr. Cook,
Thank you so much for your reply. Considering the fact that RNGs are not truly random, I think it is possible to employ machine learning to identify patterns in very large dataset generated by a random number generator.
This is an interesting article recently published about this issue:
Learning from Pseudo-Randomness with an Artificial Neural Network –Does God Play Pseudo-Dice? by Fenglei Fan and Ge Wang1.
Here is the link to the paper:
https://arxiv.org/ftp/arxiv/papers/1801/1801.01117.pdf
Thanks.
It seems RNG algorithms will become less important, as more modern processors and microcontrollers incorporate TRNGs, “True Random Number Generators.” These are hardware-based devices that turn random noise ibn analog circuits into bits, and thus aren’t based on algorithms. I don’t know if they are as good as generators based on radioactive decay, but they are claimed to be good enough for cryptography.
I’ve used (well, investigated, I didn’t have a real use) the one in the STM32F4 microcontroller on an ST “discovery” board. It generated about 900,000 32-bit random numbers per second.
TRNGs are great for generating keys, but not for encryption since the encryption has to be reversible.
I have some comment on the use of test suites and the forthcoming NIST recommendations, that are likely subjected to binary symbol communications and information processing. I’m one that designed a generator but also saw the fallacy of de-correlating streams. My generator does not have any routine to have the ‘fractional equalness’ of FIPS tests imposed.
I wrote a document for the Open Source community
Please read If you can find the time, it’s not yet finished but I need words to back this up, it’s a about the /dev/entropy cryptographic (formulating interactive strategic re-seeding/stream designing) facility that will do some of the tests that are mentioned on this site.
https://www.datamorgana.net/page/labs-pseudorandom-generators