Nonce-Based Public Key Crypto: Closing the Assumed RNG Window

By William Kleinhenz


In this time of the internet, public key encryption has become part of a user’s everyday usage. It provides security through its usage in things like TLS/SSL and has been accepted by the security community and the computing community. As cryptography, itself is a science that is constantly being researched, new things are being proposed to address potential weaknesses of the algorithms being used. One recent paper released authored by Mihir Bellare and Björn Tackmann proposed that the current methods of public key encryption have a potential weakness due to their reliance on random number generates that are only assumed to be secure and propose that these algorithms can be made secure regardless of their RNG with the use a nonce. With this post, I hope to provide some basics surrounding why weak RNG is an issue and highlight the work done to address it with the use of nonce without diving into too deep into the underlying mathematics.

The Problem

Current Public key encryption schemes utilize Pseudo-Random number generators that are assumed to be secure. To be secured the PRNG must be able to produce perfectly random numbers with a low likelihood of repeated values. Currently, the random number generators used in most case are assumed to have these properties and thus allowing an attacker to guess the RNG number generated and then break the encrypted data.

There are two main ways in which randomness can fail and lead to full cryptographic failures. The first way is through bugs in the system utilizing the encryption. A good example of this was the Debian vulnerability in which a developer deleted lines of code for the OpenSSL source that cause the seed of the PRNG to only have 15 bits of entropy. This reduces the number of seed values that the PRNG can output. This makes it much easier for an attacker to determine the keystream used for encryption and compromise the encrypted data.

The second way in which randomness can fail is the intentional weakening of the RNG by an outside organization in order to provide some form of the backdoor. A good example of this is Dual EC. This  RNG designed by the NSA and was becoming part of many standards but was discovered to have a backdoor that allowed only the algorithms designed to securely steal data asymmetrically. This issue, while serious, is not in any way new in the field of cryptography, but still, act as a source of concern for those involved in the development and testing of cryptographic systems.

Previous Solutions

Applying the use of a nonce to Public key cryptography is not the first attempt to close the security weaknesses of using PRNGs that are assumed to be secure. The first and simplest way of removing the risk that the PNG might fail is by removing it altogether. This is how deterministic public key infrastructure attempts to fix the risk of RNGs, however, deterministic PKE only provides security when the message being encrypted meets a certain level of entropy. This becomes problematic as most “real world” data has low entropy making the use of deterministic PKI insecure for most messages.

A second option would be the uses of Hedged PKE. This takes deterministic PKE so that it provides security as long as the combined minimum entropy of the message and the random number meet a certain level. While this address one of the problems face by deterministic PKE, deterministic PKE and by extension Hedged PKE, don’t provide security for messages that depend on a public key. Both this and the reliance on a meeting a min-entropy may not be practical and are designed with the mindset that the only weakness in the RNG is due to bugs but fail to increase protection when the RNG is subverted.

Nonces: What Are They?

Now that we have looked at the other methods and why they may not be practical, we turn to nonces. Nonces themselves are nothing new to the field of encryption as they are used in symmetric key encryption but are seldom used in public key encryption. What are nonces? Nonces were first used for symmetric key encryption that was deterministic in nature, nonces and was originally suggested as it would provide security while also being simple to implement. This nonce value could be as simple as a packet sequence, number, or time stamp. The application to public key takes a broader approach with the goal of protecting against poor randomness.

Using nonces in the same as in symmetric key encryption doesn’t apply to PKE as it creates a security issue. When applying nonces in symmetric key encryption the algorithm used is deterministic but using a deterministic algorithm for PKE would benefit the attacker. This is due to how public key encryption function, say we have a deterministic encryption algorithm E, the encryption key Ek, a nonce n, the message bit Mb and the ciphertext C in the formula C = E(Ek, n, Mb). This formula would provide an attacker with an oracle that could be used to discover the bit. This is because the attacker knows the encryption key and can encrypt a chosen value, this means an attacker can query the oracle with any message bit. Allowing the attacker to use the above formula to calculate the first message bit’s ciphertext of C0 and compare it to the chosen ciphertext of Cb and if equal then the challenge bit is 0 and if not equal the challenge bit is equal to 1, thus allowing an attacker to decipher the message.

Proposed solution

With the direct application of nonces to a public key encryption system allowing for a break of the system, a different approach must be taken. So, say we have a nonce based PKE scheme NPE. First, as in normal PKE, the receiver generates both an encryption and decryption key. Then the sender will run a seed generation algorithm to get some seed. Then for encryption, the sender use a deterministic algorithm that takes the encryption key, the message, a nonce and the generated seed. Decryption is the same as normal PKE using just the decryption key and the message. The seed is unknown by the receiver, is independent form the keys and can be reused or regenerated as the sender chooses.

This system provides security in two cases if the requirements are met. First, this scheme provides security against chosen plaintext attacks if the same nonce message pair is never reused and if the seed generated by the sender remains secret. The second way that security is provided is that if the seed of the sender becomes compromised the security of the system remains if the nonces are generated in such a way that they cannot be predicted by the attacker.

In this system, the nonce generated would be comprised of multiple elements including the current time, previous ciphertexts, and random value generated by the system RNG which is required to keep the nonces unpredictable. This means a couple of things, first it means that an RNG with structed or correlated inputs would not directly weaken the encryption if the nonce is unpredictable and second that if the RNG was weakened through bugs or through subversion the attacker would still be required to bre4ak into the sender’s system and retrieve the seed used.

Hedged Extractors

Meeting the requirements of the two cases described above is simple in when done in isolation but, to meet the requirements of both case simultaneously, hedged extractors must be used. This hedged extractor takes the seed value generated by the sender, the message being sent and the nonce and outputs a string. This extractor has two properties, first, it is a pseudo random function meaning that the output string appears random to an attacker if the seed given is kept secret and is random. This holds true even when the attacker can choose the values of both the message and the nonce. Second, as this is an extractor if the seed is random but has been revealed then the output still appears random if both the message and nonce are unpredictable.

To ensure these properties are maintained simultaneously the paper suggests two solutions, the first using the random oracle model and the other using the standard model. The ROM solution is simple and practical and applies a random oracle to the seed and the message-nonce pair. The standard model combines a pseudo random function with an extractor with strong randomness using XOR. The solution using the random oracle provides the best security while the solution using the standard model is weaker due to the limitation of the extractors used being that they require that the seed inputs maintain min-entropy.

Considerations and Application to Current Systems

The system proposed in theory is simple and modular, allowing it to be applied to any existing PKE system with little modification. If applied using the ROM standard variant the resulting scheme preserves the efficiency of the original PKE scheme and does not require the receiver to change any of their software as the decryption process doesn’t change and the nonce is not needed by the receiver. This scheme can be easily deployed on the receiver side and provides security in the face of week RNG due to the combined use of both a nonce and a generated seed.

Applications to Signatures

As with regular PKE system, this nonce based system can generate signatures that provide authenticity for a message. However, the nonce based signature like the nonce based PKE use a nonce and seed in addition to the signing key and message. Also like with nonce based PKE, the nonce based signatures require that if the seed is hidden the generation of the nonces is not important and that if the seed is exposed then security is maintained if the nonces remain difficult to predict.

In terms of schemes the elliptical curves version of DSA, El Gamal and Schnorr are common due to their relative speed and short signature size, however, these become easily broken is bad randomness is used. Due to this failure in the face of bad randomness, many in the IETF’s Crypto Forum Research Group support the change of these schemes to become deterministic in nature. This can be easily done by using a pseudorandom function that uses a seed value as part of the secret key or by applying a random oracle to the secret key and message. Using these applications to make a scheme nonce based de-randomizes the scheme while retaining the benefits of deterministic signing while also adding the additional protections from using nonces and seeds.


The application of nonce onto traditional PKE and signing schemes seems to be something that would be a reasonable idea to pursue as the two causes of weak randomness, bugs, and subversion, are not likely to disappear anytime soon and the application of nonce based PKE may be simple and practical to pursue. At the time of this blog this paper was released last year, 2016, and is still mostly theory, I believe that it will be interesting to see if this will be applied to PKE scheme or if a new scheme/algorithm will be developed around this idea.



Bellare and B. Tackmann, Nonce-Based Cryptography: Retaining Security When Randomness Fails, 1st ed. University of California, 2016.




Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s