# What is the use of a nonce in public-key encryption if it's meant to be shared?

I'm using PHP. The guys over at paragonie have made encryption easy for the PHP eco-system.

Now, on my computer, Alice, when I encrypt a message using Alice's private key and Bob's public key, I am also given a nonce. Its use? I don't know. I just trust the guys that it's needed and safe.

Thing is, this got me thinking - a nonce, in my book is a protection against forgery, but here I am giving it away. Clearly, if you go to this article: https://paragonie.com/book/pecl-libsodium/read/05-publickey-crypto.md and check the //Bob's computer part, you can see that Bob also needs that nonce Alice generated.

So, what am I missing here?

• – Eugene Styer Feb 25 at 16:26

Forget about of the notion that there's a useful thing called "public key encryption". There's "public-key authentication" (signing/verifying) and "public-key shared secret exchange" (Diffie-Hellman & Key Encapsulation) but direct encryption of arbitrary data doesn't happen in modern systems. The outdated notion that it does is a source of much confusion.

The system they're using has two portions: signing and boxing. Signing is straightforward, doesn't use a nonce, and isn't what you're asking about.

Boxing is the part of interest. It's not only public-key, it's also secret-key. First, Alice and Bob generate key pairs and exchange public keys. Then they can use boxing/unboxing.

Boxing uses public-key shared secret exchange and a nonce to be able to use a (fast) Authenticated Encryption with Associated Data (AEAD) cipher to encrypt and authenticate the message. The public keys aren't actually used for encryption, only for creating/exchanging the shared secret key that then encrypts the message.

AEAD ciphers are far faster than public-key ciphers, provide data integrity guarantees, and provide security guarantees that public-key encryption wouldn't.

The nonce ensures that sending the same message twice does not result in the same ciphertext or the same authentication tag, and thus prevents certain attacks. It's a public value, not a secret. It's not really to prevent forgery, that's (part of) what the authentication tag is for, but to provide ciphertext indistinguishability which is a fancy term that intuitively means that an attacker shouldn't be able to learn anything (other than possibly the length) about the message from seeing the ciphertext.

• Fuck. You know how you sometimes read some stuff and then you realize just how dumb/small you are? That's how I'm feeling right now. Thanks for the explanation. – Daniel M Feb 25 at 17:33
• Don't worry, it's a complex subject. That's why libraries like libsodium (what you're using) try to hide the complexity behind things like "box" instead of making you do all the steps manually. It took me a few revisions to simplify it as much as I did, and I'm still worried it's too confusing. – SAI Peregrinus Feb 25 at 18:28
• I kept coming back to your answer, even if I accepted it and something struck me. In their example, they straight up send a message to each other, that message is the contents, but you're saying that boxing with a nonce simply facilitates the sharing of the secret key that then encrypts the message. If you go to paragonie.com/book/pecl-libsodium/read/05-publickey-crypto.md crypto_box_open, it seems as if the work is done, based on only the public key of Bob, Alice can send encrypted messages to him..so..my work isn't done, yet? – Daniel M Feb 25 at 21:02
• At this point, I've done the exchange. Alice can send a message to Bob using his public box key. What's next? My goal is to simply have Bob identify himself as Bob (Bob is my developer server, which has to be recognzied by multiple Alice(s) as being Bob). – Daniel M Feb 25 at 21:03
• 2nd to last comment: Look at the signature of crypto_box_open(): it takes ciphertext, nonce, and the keys, not just the ciphertext. For the last comment, this depends on what you're doing. Alice might send some challenge (say, a 16-byte random number) in her first message, and Bob might sign that challenge and send the signed value back to Alice (using a box as before). Or you might use PKI certificates and verify their signatures back to a trusted root like HTTPS does. Or you might hard-code the server's public key in the client application. The right answer depends on the application. – SAI Peregrinus Feb 26 at 15:53

Thing is, this got me thinking - a nonce, in my book is a protection against forgery, but here I am giving it away.

The primary purpose of nonces is not protection against forgery, but rather, to ensure that encrypting the same plaintext many times with the same key does not produce the same ciphertext (which risks the possibility that an eavesdropper might learn something from frequency analysis). For a very simplistic example, imagine encrypting the plaintexts YES and NO over and over and they always encrypted to XUW and EG.

There are protocols that secondarily exploit nonces in some fashion to avoid replay or reordering attacks (a kind of forgery). For example, when encrypting a large volume of data, one strategy is to break it into smaller sequential chunks and encrypt each one separately with the same key but a nonce that encodes:

• The chunk number
• A flag indicating for each chunk whether it's the last one

...so that when you decrypt the file, you verify as you go that no chunks have been reordered and that it hasn't been truncated. But that's an optional thing an application may (wisely) choose to use chunks for, not a basic requisite like the ciphertext diversification.

I must say that I find the documentation that you link rather confusing in its treatment of nonces, because:

• For ciphers popular today (and used by the Libsodium C library this PHP package is seemingly based on), encrypting two textually different plaintexts with the same key and nonce can result in a catastrophic security loss;
• The linked page don't seem to sufficiently warn of the danger inherent to nonce reuse;
• It also doesn't explicitly specify over what scope the library expects nonces to be unique.

Compare what the Paragonie docs say:

Each message sent requires a nonce (a unique large number represented as a binary string that should only be used once).

...with its counterpart in the documentation of Libsodium library:

The nonce doesn't have to be confidential, but it should be used with just one invocation of crypto_box_easy() for a particular pair of public and secret keys.

One easy way to generate a nonce is to use randombytes_buf(), considering the size of the nonces the risk of any random collisions is negligible. For some applications, if you wish to use nonces to detect missing messages or to ignore replayed messages, it is also acceptable to use a simple incrementing counter as a nonce. A better alternative is to use the crypto_secretstream() API.

When doing so you must ensure that the same value can never be re-used (for example you may have multiple threads or even hosts generating messages using the same key pairs).

Much, much better, and the recommendation to use random nonces is safe, but the alternative suggested of using a simple incrementing counter is a bit scary, it's much too easy to implement that wrong e.g. across multiple executions of the same program. They suggest the use of their newer crypto_secretstream() API instead, but that uses shared-key encryption, not public key, leaving the user the highly non-obvious task of figuring out how to wire those together.

Caveat emptor. Cryptography is a minefield.

• Thank you. What I'm taking from this is there's no way to match the decrypted plain-text to what was the encrypted string. For example, assume Alice encrypted the string heyo using her private key and Bob's public key, all together with the nonce. If Bob sends this plain-text back to Alice, given she only has the encrypted string stored and asks her Hey, Alice, you have my public key, your private keys...but can you re-encrypt this plain-text such that it matches what you sent me?. I'm sorry if it's confusing, in other words, I'm wondering if I can reverse the crypting process. – Daniel M Feb 27 at 7:36
• In other words Alice sends a challenge string to Bob, Bob can, in fact decrypt it, gets its plain-text, then Bob sends this plain-text back to Alice who has this encrypted string stored, now she's given this plain-text to compare to hopefully reach the conclusion of Yup, Bob has sent me a plain-text and if I re-encrypt it, I'd get the same string, which means Bob for sure is who he says he is.. Kind of like how password hashing and logging in works (you never store plain-text). – Daniel M Feb 27 at 7:39
• I'm thinking that I can actually mitigate that by storing the encrypted string using a very strong hashing algorithm. I use public-key encryption to verify that whoever is getting this encrypted string (so I can post it publically) can only decrypt it if he has Bob's private keys, then, on Alice's computer, I simply store the original plain-text string using bcrypt, once Bob sends the plain-text, I just simply check if the plain-text matches the bcrypt string in my database. – Daniel M Feb 27 at 7:51