22

Poly1305 is a universal hash function. The output of that function cannot be used safely without being encrypted. In order to encrypt it, any cipher can be used. AES was used as an example in the paper, but the very same paper mentioned: Users can switch from Poly1305-AES to Poly1305-AnotherFunction, with an identical security guarantee. All the efforts ...


14

The library uses XChaCha20Poly1305 and that requires a nonce of 192-bit (24-byte). It is an extension of ChaCha20Poly1305 to increase the nonce size, ChaCha20 had 96-bit nonces. There is no standard for it, only a draft in ietf.org The nonce is an acronym for 'number used once'. The crucial point is that one must never use the (Key, nonce) pair again. We ...


13

What are those existing constructions? Usually people consider three to four scenarios for authenticated encryption for embedded environments: Constrained for ROM + RAM In this case you probably would want to use as few primitives as possible and using something like the EAX or CCM mode to use your block cipher for both authentication and encryption. (...


12

Can the $AES_k(n)$ portion be simply replaced with $k \oplus n$? No, but you're close, it would be replaced with $k + n$, where $+$ is addition modulo $2^{128}$; then it becomes informational theoretic. Here's why: Poly1305 is based on a polynomial universal hash. This is a hash where we select a finite field $GF(p^i)$, select a private value $x \in GF(p^...


12

At least in the case of NaCl, Poly1305's "sudden death" properties aren't much worse than XSalsa20's. With any stream cipher, if you reuse the same stream with two messages, then the XOR of the ciphertexts gives you the XOR of the plaintexts. So your security is already ruined by nonce reuse, whether or not you rely on Poly1305.


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

Do all TLS cipher suites using "ChaCha20-Poly1305" use Poly1305-AES? Nope, AES is indeed replaced with ChaCha20 in TLS. The Poly1305 one-time key is generated pseudorandomly using the ChaCha20 block function. The ChaCha20-Poly1305 TLS cipher suite spec draft uses the AEAD construction from RFC 7539, which defines exactly how this works: The ...


11

The first 32 bytes of XSalsa20 output are used as key for the one-time-mac Poly1305. Poly 1305 needs a new 32 byte key for each message, using part of the key-stream is a natural way to obtain those. Requiring those empty bytes makes implementing the API easier. The implementer only needs to call XSalsa20 on the zero padded input buffer once, receiving both ...


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

No, they are not distinguishable from random. The Poly1305-AES authenticator is defined as: $$ (((c_1 r^q + c_2 r^{q−1} + ... + c_q r^1 ) \bmod {(2^{130} - 5)}) + \operatorname{AES}_k (N)) \bmod 2^{128} $$ Since it is the sum of an AES output and some other number modulo $2^{128}$, it is PRF if: the AES output is PRF and the two numbers are independent. ...


9

One particularly interesting aspect of Poly1305 is that its security is guaranteed, assuming the underlying cipher is secure. In other words, Poly1305-AES is guaranteed to be secure, as long as AES has not been broken. In the event that AES is broken, AES could be replaced with another cipher, and get a similar security guarantee. DJB talks about his ...


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

Poly1305-AES is a message authentication code. AES-GCM is an authenticated cipher. So it isn't a meaningful comparison. But we could compare Poly1305-AES with AES-GMAC, which is a message authentication code. They're both Carter–Wegman–Shoup MACs built out of the block cipher AES and a universal hash family based on polynomial evaluation with ...


8

Poly1305 is not based on AES, it was used together with AES in Bernstein's first description http://cr.yp.to/mac/poly1305-20050329.pdf. For pseudocode of the Poly1305 algorithm see e.g. https://www.rfc-editor.org/rfc/rfc7539#section-2.5.1. GHASH is the 'hash function' in AES/GCM. So if Poly1305 is faster than GHASH on some hardware this is no contradiction. ...


7

A 2-pass authenticated cipher is a mode of operation that uses two full (block) cipher operations for each byte in the message. There is also a mode of operation, OCB mode, which uses a single pass to provide both message confidentiality and message integrity / authentication (it has been encumbered by IP-rights issues, so it isn't used that much). A 1.5 ...


7

You do not require a new key. You use a different initialization vector (IV) for every message. As long as you use a different pair of (key, nonce) for each message you retain the confidentiality and integrity of messages. The nonce is the initialization vector.


7

Poly1305 today is generally used as part of some AEAD construction alongside Salsa20/ChaCha20, because the key advantage of all of these algorithms is excellent performance in platforms that don't have hardware AES support. Most notably these days, that would be low-end phones and tablets. And one of the big pushers for the standardization and adoption of ...


6

As a comment points out, it’s most probably a mistake/error in the docs. If you look at “What is the PRG period of stream ciphers such as RC4 or Salsa20?”, you’ll find an answer which explicitly points out the limits of Salsa20 (quote) …Salsa20 used as a stream cipher, it uses a 64-bit block counter and 64-bytes blocks, limiting its capacity to $2^{73}$ ...


6

No. Consider the simple universal hash function $H(k, x) = k \cdot x \in \mathbb{F}_{2^n}$. It is universal as $\text{Pr}[H(k, x) = H(k, y)] \le 1/(2^n - 1)$ for a randomly-selected $k$; polynomial evaluation degenerates to this function when run on a single block. If you run this in counter mode you get as ciphertext $k \cdot 0$, $k \cdot 1$, $\ldots$, ...


6

OK, so the core ChaCha primitive (for any fixed number of rounds) is a function $\operatorname{ChaCha}: \{0,1\}^{256}\times \{0,1\}^{64}\times\{0,1\}^{64}\to \{0,1\}^{512}$ which is believed to be a secure PRF when the first input is the key. So now that we know what ChaCha is, for the three desired functionalities: MAC. Of course a PRF is also immediately ...


5

Yes, Poly1305-AES can safely be modified to use AES-256 rather than AES-128; but if AES is implemented in software beware of not introducing a timing vulnerability in the implementation. Change of the cipher in Poly1305-AES is explicitly endorsed; quoting D. J. Bernstein's The Poly1305-AES message-authentication code There is nothing special about AES ...


5

The reason for the padding (and re-positioning of the AAD length) in the later draft is to make implementations easier and faster - i.e. not for a security reason. The rationale for this change was actually documented on the CFRG mailing list by Alyssa Rowan: Instead of the lengths directly following their ciphertexts: draft-agl-tls-chacha20poly1305-...


5

ChaCha20-Poly1305-SIV is not well defined, and does not have the advantages of SIV-mode if you do define it. The SIV mode is essentially MAC-then-encrypt, with the MAC reused as nonce. The MAC in ChaCha20-Poly1305 requires a nonce, because it uses ChaCha20 to encrypt the Poly1305 authenticator (you cannot reveal the raw authenticator). So you cannot use it ...


5

You can use methods for hiding the output of the polynomial hash that don't require nonces, such as encrypting with a block-cipher of matching block-size or hashing it with a keyed hash (PRF). Not using a nonce reduces the security bounds (security decreases as the attacker sees more messages using the same key), makes it incompatible with stream ciphers ...


5

This is not specific to this construction, but generally, you want to split the stream in smaller chunks, that are individually encrypted and authenticated. If the encrypted stream doesn't have a valid authentication tag, this is not something you want to discover at the very end, after having decrypted terabytes of data. Some precautions have to be taken ...


5

Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305? Performance. Poly1305 is extremely cheap to compute, and the computation can be essentially arbitrarily parallelized, because it's just evaluating a polynomial modulo $2^{130} - 5$. In contrast, functions like BLAKE2 and Rumba20 can't be parallelized ...


5

what is the minimum amount of bitflips on the message that can be corrected Zero bits, Poly1305 doesn't provide error correction (at least Bernstein doesn't claim that property in the original paper). (or at least detected) by someone who knows the corrupt message, the mac code, and the key? One bitflip is already detectable, it will change all bits of ...


5

Yes, AES is just used as a 128 bit / 16 byte block cipher in this scheme. The paper specifies: Poly1305-AES feeds each nonce $n$ through $AES_k$ to obtain the 16-byte string $AES_k(n)$. There is no mention of AES without this key $k$ or nonce $n$. So, as far as AES - the block cipher - is concerned, $k$ is the key and the nonce $n$ is the data / message. ...


5

There are probably a handful of keys which could be detected by swapping blocks in an authenticated message that is a few tens of millions of blocks long. There's also the trivial zero weak key and the trivial 1 key. Recall that the Poly1305 MAC additive is calculated as $$\left(\sum_i c_i r^i\pmod{2^{130}-5}\right)\pmod{2^{128}}$$ where $c_i$ is a mild ...


4

For the complete picture, as was pointed out, you should use the final RFC, not drafts. There are two relevant RFC here: RFC 7539 describes the stream cipher ChaCha20, the MAC algorithm Poly1305, and an Authenticated Encryption with Associated Data mode that combines ChaCha20 and Poly1305 in a safe way (in particular, it uses ChaCha20 to provide the secret ...


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