The Stack Overflow podcast is back! Listen to an interview with our new CEO.
11

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^...


10

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 ChaCha20 and ...


10

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 ...


10

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 ...


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

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.


9

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)


8

Numbers get represent as in base 256, i.e. $h = \sum_{i=0}^{17} h_i \cdot 256^i$. Since ints are used which are significantly larger than bytes you don't need to propagate carries immediately. If you forget about modular reduction, then the $i$th digit of the result is computed as $\sum_{j=0}^i h_j\cdot r_{i-j}$. Apart from the lack of carry this is pretty ...


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://tools.ietf.org/html/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

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 ...


7

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 ...


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

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

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 ...


6

To answer your original question: no, you can't presume that you can replace the addition mod $2^{128}$ within $Poly1305$ with XOR, and not change the security properties (at least, not without some serious analysis). The security of the MAC depends on the fact that, given any two distinct messages $M_1$ and $M_2$, and any integer $\Delta$, then the ...


6

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.


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

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 ...


4

Q2: No, Poly1305 not limited to stream ciphers. Yes, Poly1305 can be used with block ciphers running in CTR mode, if you use it appropriately. I don't know whether the NaCl use is secure (whether NaCl uses it appropriately); I haven't tried to analyze NaCl. Given that NaCl was built by reputable cryptographers, I would be inclined to guess that it's ...


4

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 ...


3

In your link next to the cipher suites with poly1305 you find a link to http://www.iana.org/go/draft-ietf-tls-chacha20-poly1305 That in turn links to rfc7539 which in Section 2.6 describes generating the key for poly1305 using chacha20. So my answers would be: No. It is being used so it's probably and hopefully not a problem.


3

(Note: this answer is partly an analysis of Colin's Percival's writings, and partly my own opinion. I use indirect speech for Percival's recommendations and direct speech for mine.) These recommendations are geared towards someone who will write the whole code, including the cryptographic primitives. Before these slides, Colin Percival wrote a blog post and ...


3

First off, it sounds like you already have an opinion and should talk to Colin directly. My take is, at least at the time, he was very much in favor of tried-and-true (and easy, relatively) encrypt-then-mac schemes. Namely, he advocated CTR+HMAC. This is easy and known to be secure. You pay for it a little by deriving more key material than otherwise ...


3

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 ...


3

You're mixing up various concepts of security, and that - in general - just doesn't work. First, universal hashing on its own does not have any security property. Universal hashing is used in some constructions, for example UMAC. Secondly, you used the term GHASH, which is an internal function of GMAC or GCM. The security property holds for the entire ...


3

I wound up finding RFC 7539, and using the test vector from section 2.8.2 of that document. I present the same vector here, in a more code-friendly format: # test vector courtesy https://tools.ietf.org/html/rfc7539 vector = { key: "808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9f", input: "...


3

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 ...


3

From the standpoint of integrity and proof of origin, signature is a superset of MAC, with the tremendous operational benefit that no secret is required for verification (drawbacks include larger size, slower generation, and typically slower verification with the possible exception of RSA/Rabin signature). Thus the poly1305 MAC in theory is redundant. From ...


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