Subject: [Cfrg] Truncation of tag for ChaCha/Poly1305

From: "Jim Schaad" <[email-masked]>
Date: Fri, 7 Aug 2015 11:14:11 -0700

I was looking at this algorithm for inclusion in a document that I am
working on and I came up with the following question.

Are there any security considerations that are involved with truncating the
tag?   I expect the standard warning that the odds of forgery are related to
the length of the tag.  My question is are there any other issues that I am
missing.  I did not see anything in RFC7539 about truncating the tag.

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 7 Aug 2015 21:29:21 +0300

> missing.  I did not see anything in RFC7539 about truncating the tag.

I presume Poly1305 has similar vulernability as GCM with truncated tags: If
attacker can produce few forgeries of partial tags, the attacker gains enough
information to forge authentication tags.

Because the way GCM mode (and also Poly1305-AES) is set up, the information
gained is enough to forge tag for any nonce after you see a valid message for
that nonce.

However, the way Chacha20-Poly1305 AEAD uses Poly1305, that attack seemingly
only works for each individual nonce. So one would have to forge the tag for
the same nonce multiple times to gain information on how to forge tag for that
nonce.

-Ilari

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 7 Aug 2015 18:34:04 +0000

Date: Fri, 7 Aug 2015 11:14:11 -0700
   From: "Jim Schaad" <[email-masked]>

The forger's one-time success probability is proportional to 2^-f(n)
where n is the length of the tag in bits and f(n) is something like n
- 25.

The critical part is `one-time'.  For many packets, provided you
discard packets with reused nonces, e.g. by rejecting packet sequence
numbers other than the current one you expect, this is still all you
have to worry about.

This is different from not reusing nonces yourself: the legitimate
parties may be careful not to reuse nonces, but if the forger succeeds
for a single (key, nonce) pair, then the forger can forge any number
of other messages under the same (key, nonce) pair.  So, e.g., if you
randomize nonces and don't list the ones you've seen, this is likely
to be a problem.

The problem is different for AES-GCM and other schemes with
Carter-Wegman MACs: a single forgery enables arbitrarily many
re-forgeries even if you are careful to reject packets with nonce
reuses.

See p. 30 of <http://cr.yp.to/highspeed/naclcrypto-20090310.pdf> for
details.