2
$\begingroup$

Given a message $m$ of size $n$, a key $k$, and a message authentication code $mac = poly1305(m, k)$ what is the minimum amount of bitflips on the message that can be corrected (or at least detected) by someone who knows the corrupt message, the mac code, and the key?

$\endgroup$
  • 2
    $\begingroup$ @MaartenBodewes cacr.uwaterloo.ca/techreports/2002/corr2002-19.ps and pdfs.semanticscholar.org/c561/… suggest some MACs which they claim to be usable for error correction. $\endgroup$ – 8321992485 Feb 6 at 23:03
  • $\begingroup$ These error-correcting MACs make me nervous. The first acknowledges a reduction of security compared to the standard way (an error-correcting code at the line level, and a MAC on top of that); it also admits being impractical for large messages, since the error-correction requires a DLOG. The second gives a security proof (5.1) of information-theoretic nature; actual security is that of the associated stream cipher, which is required to make the scheme a true MAC (much like Carter-Wegman is not a MAC all by itself). This is not clear enough in the abstract IMHO. $\endgroup$ – fgrieu Feb 7 at 16:47
5
$\begingroup$

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 the resulting hash with a 0.5 chance.

Of course, there is always a negligible chance that the data does result in the correct hash (a chance of 1 in $2^{128}$ for the full MAC output). However, that's not dependent on how many bits are flipped.

Generally, it is recommended to keep the full output of the MAC calculation as an authentication tag.


If you also want error correction against changes, you could include a block of error-correcting code over the message + authentication tag. That way both are protected against non-malicious changes. Or you could use a specialized MAC algorithm as indicated within your own comment.


Personally I don't see a direct way to add error correction capabilities to the Poly1305 calculations, but I'm not the best person to indicate if that's possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.