# Tag Info

16

By the modern definition of a cipher, it must be possible to encipher several messages with the same secret key. That's also a practical necessity, due to the difficulty of securely establishing a shared secret key. That issue is solved with the nonce, which is not secret, and can be transferred as part of the ciphertext (typically: at the beginning). ...

14

Yes, a nonce is a number not used more than once. In its purest sense there should be no other requirements than this, i.e. randomness or unpredictability should not be necessary. However, in certain settings stronger requirements are put on the nonces; like for instance in the CBC-mode of operation for block ciphers the IV (nonce) needs to be ...

14

Even a single AES-GCM nonce reuse can be catastrophic. A single nonce reuse leaks the xor of plaintexts, so if one plaintext is known the adversary can completely decrypt the other. This is the same as for a two-time pad. In messages up to $\ell$ blocks long, after a single nonce reuse the adversary can narrow the authentication key down to $\ell$ ...

13

I am using here the description and terminology from RFC 7539. ChaCha20 is meant to process messages, each message being a sequence of bytes; ChaCha20 produces pseudorandom blocks of 64 bytes each, which are XORed with the data to encrypted or decrypt. The crucial security property is that all invocations of the ChaCha20 block function for a given key use ...

12

The article on NaCl by its authors touches this subject. I'll quote here the relevant bit: Nonces. The crypto_box API leaves nonce generation to the caller. This is not meant to suggest that nonce generation is not part of the cryptographer’s job; on the contrary, we believe that cryptographers should take responsibility not just for nonces but also for ...

12

With CBC mode the initialization vector is referred to as IV, because it is not nonce. There are ways to construct nonce so that it does not meet the needs of CBC mode. Random IV is one generation choice which is usually fine. Nonce can also be a counter, which is not ok here. Definitions Nonce means number used once. IV means initialization vector. CBC ...

12

If a nonce $N_i$ is even, then the binary numeral for it its increment $N_{i+1} = N_i + 1$ differs from $N_i$ only in its least significant bit; and if $N_i$ is odd, its increment is even. This means we can adapt chosen-plaintext attacks against CBC with counter nonces (e.g., from section 4 of this Rogaway paper) to target your scheme. Given an block ...

11

If you reuse a nonce, you lose confidentiality for the messages with that nonce. Messages with other nonces retain their confidentiality. However, the attacker can also attack the MAC part (Poly1305) and generate a third and more messages with the same nonce. See: Why is Poly1305 popular given its 'sudden death' properties? So unless you have a way ...

11

No, it doesn't need a random nonce. Yes, if you use an incrementing counter, that works. As the RFC says, the only requirement is uniqueness; as long as you make sure that each nonce you use is different, you have met the requirements - an incrementing counter does that quite nicely (and, in fact, is commonly used in practice)

10

Reusing an IV once opens you up to someone finding the XOR of those two plaintext, seriously compromising their confidentiality. Moreover, with GCM, a single IV reuse leaks significant information about the key used for authentication; if there are even a few pairs of reused IVs (not even one IV used many times; a few IVs each of which are used twice is ...

10

This additional 32 bit nonce acts as a salt, and makes multicollision attacks $2^{32}$ times harder. In this attack, the attacker collects a huge number of TLS sessions, each with a record encrypted with the same nonce. He then selects a random key, and generates the counter mode keystream for the key (and the fixed nonce); he then checks if that key ...

10

The documentation on libsodium AEAD constructions provides more details. Namely, it lists Hk(random ‖ m) as a way to compute a synthetic XChaCha20 nonce. Even if random is not unique, the nonce is unlikely to be the same for different messages. Even more relevant are the sections on nonce-misuse resistance and short nonces. Note that like all other nonce-...

9

However, if a nonce can provide all the protection a timestamp does, why would they ever be used together? If you use a timestamp in combination with a nonce, it can help mitigate the risk of nonce reuse. Guaranteeing that nonces are never duplicated within the relevant scope can often make a system more complicated, because it needs to maintain state ...

9

Yes, but to use a known algorithm that specifies precisely that, take a look at the SIV mode of operation . "SIV" stands for Synthetic IV. IV is the initialization vector, which is the nonce (or the nonce and initial counter value, depending on the definitions). Unsurprisingly it relies on CTR mode for confidentiality and CMAC for the authentication tag ...

9

First, this is not safe with ChaCha because the ChaCha nonce is only 64 bits long, since ChaCha nonces are normally chosen sequentially, so there would be a nonnegligible danger of collision with a reasonable number of messages. Let's say XChaCha instead, with a 192-bit nonce, which is large enough to choose at random without danger of collision. The ...

8

The synthesized IV does not need to be random. AES-SIV is a deterministic authenticated encryption mode: it can be used without any nonce when it is not a concern if the attacker can tell that the same message is being transmitted (under the same key) multiple times. Privacy and authentication are still guaranteed. SIV recommends to use a nonce (more ...

8

The answer is that you can do exactly what you say. Initialize the counter to a random 16 byte number and start counting. Wikipedia (not sure if that is where you got the idea that it must be 8 bytes and 8 bytes) has the following note: The IV/nonce and the counter can be combined together using any lossless operation (concatenation, addition, or XOR) to ...

8

Definition 10.9 in Chapter 10 of Handbook of Applied Cryptography. A nonce is a value used no more than once for the same purpose. It typically serves to prevent (undetectable) replay. Continuing on, there is some additional info that you might find interesting. The term nonce is most often used to refer to a “random” number in a challenge-response ...

8

This is a trickier question than you might think. The first thing to note is that your scheme doesn't respect record boundaries. TLS 1.2 seems to have been rewritten to use a random IV for CBC mode encryption for each record (to avoid certain attacks). It is therefore likely that the idea of TLS 1.2 is to respect record boundaries. The document "AES Galois ...

8

The Intel post which I think you mean was discussed in this question and as I wrote there, the limitation only applies in the case of trying to combine PRNG outputs into values larger than the seed entropy (two 256-bit values in their case). Also mentioned there: cryptographic mixing does not increase the entropy you have, so if concatenation is insecure, ...

8

You can safely use HMAC-SHA256 instead of the SIV mode custom PRF to derive the nonce/authentication tag. There's some caveats: HMAC-SHA256 gives a 256-bit output; you'll have to truncate it to the nonce size. HMAC-SHA256 takes in a single bit string, so it can't distinguish the boundary between a header (unencrypted associated data) and payload (encrypted ...

8

Usually. However, if you are using 128-bit AES in CTR mode (remember that GCM is essentially just CTR with authentication), then a kind of attack called a multi-target attack can become possible. This attack is realistic when an attacker has a huge amount of stored ciphertext, each with a random key. While breaking a specific key requires performing up to ...

7

Under the assumption that $(K,\text{Msg})\to H_K(\text{Msg})$ is a secure MAC (be it HMAC or any other MAC), and $\text{Nonce}$ does not repeat and is of fixed size, both $H_K(\text{Msg}||\text{Nonce})$ and $H_K(\text{Nonce}||\text{Msg})$ are demonstrably secure, in the sense that an adversary not knowing $K$ can't distinguish either from random, even for ...

7

I assume you mean AES-GCM. Nonces must be unique for any use of a key. Given that $n = H(k)$ is constant for constant key $k$, this implies that such a nonce may only be used once, ever. Nonce reuse is particularly catastrophic in GCM mode (as with any other CTR-based mode), as it causes the keystream to be identical. Essentially, you wind up with two (or ...

7

In your description, AES/GCM is always used with a new, fresh key, different from all previous keys. Thus, you are not reusing IV with the same key. In that sense, this should be fine from a security point of view. However, this seems overly complex and begs the question of: why? The simple way would be to use the static key "as is" and to use a random IV ...

7

Besides the IV, ChaCha20 takes a random number and a counter as input. No it doesn't (sec. 2.4): The inputs to ChaCha20 are: A 256-bit key A 32-bit initial counter. This can be set to any number, but will usually be zero or one. It makes sense to use one if we use the zero block for something else, such as generating a one-time authenticator ...

6

Let $2^m$ be the average message length in blocks. When using an independent random nonce for the whole 128-bit IV of each block, you would expect a collision after $2^{64}$ blocks, i.e. $2^{64-m}$ messages. (But you double the data size.) When using a 96-bit nonce and a 32-bit counter, you would expect a nonce collision after $2^{48}$ messages. This is ...

6

There may be some particular scenarios where an unpredictable nonce is better than just a unique nonce. For example suppose you have access to an oracle that can generate the correct response to an authentication request that involves a nonce, but you don't have real time access; in particular by the time you get the response from the oracle, the challenge ...

6

Yes, it is safe. The only requirement for the nonce in Salsa/Chacha is to be unique; being predictable is not an issue, so a counter is fine. Like CodesInChaos indicated, I believe extending XSalsa20 to XChaCha20 would also work if you want to a larger nonce, but have nothing concrete so will leave the details to him/her.

6

What you're describing is pretty similar to the SIV block cipher mode. It also uses a deterministic function of the message to derive the nonce for CTR encryption. Under some pretty widely accepted assumptions about HMAC-SHA256 this is a perfectly fine way of achieving deterministic authenticated encryption. It doesn't meet IND-CPA (as you pointed out) but ...

Only top voted, non community-wiki answers of a minimum length are eligible