[openssl-dev] [openssl.org #4483] Wrong results with Poly1305 functions

Andy Polyakov via RT rt at openssl.org
Tue Mar 29 13:46:59 UTC 2016

>>> In the final reduction, $h1 is all ones, so there is one more carry to
>>> propagate. Though $h2 can then overflow its two bits, I think? I expect
>>> that and the cleared bits of r mean the imulqs in poly1305_iteration are
>>> still safe, so we can pick up that slack in poly1305_emit, but I'm not
>> sure
>>> about all the complex switching back and forth in the SIMD codepaths.
>> Does
>>> __poly1305_block need to follow up with one more reduction?
>> That additional adc goes to a perl subroutine that is used in both
>> poly1305_blocks and __poly1305_blocks, so modification covers both. Pure
>> SIMD paths (or FP) are not affected...
> Right. What I meant is that a fully reduced h has $h2 < 4. Is it possible
> that $h2, after that adc, ends up at 4, exceeding that bound?

The question is somewhat ambiguous. I mean you write < 4 and then wonder
if it can end up at 4. If you meant to write $h2 < 3, then it wouldn't
be ambiguous. Anyway...

> If it were,
> that would require one more reduction.

It can (one of suggested test vectors actually exposes it), but no
special treatment is required. If it happens anywhere in the middle it's
handled naturally. If it happens as last step, then final "comparison
with modulus" step effectively takes care of it, because after adding 5
value would still appear as "overflow", and so it will choose value with
5 added. Note that it does mean that *final* $h2 is at most 4. It can
become larger that 4 in the *middle*, but not larger than 6.

> In the non-SIMD paths, I believe this is fine because $r0's and $r1's
> cleared high bits mean we should have plenty of slack to leave that
> unreduced. (And indeed its normally not reduced on input from the
> addition.) Then poly1305_emit's reduction after adding s will resolve
> things before output. But, in the SIMD paths, __poly1305_blocks is called
> and then bits are shifted without any reduction.

What do you mean shifted without any reduction? There is reduction step
after base 2^26 -> 2^64 conversion (which also needs additional adc, but
there *is* reduction step) *prior* call to __poly1305_block. And there
naturally is reduction step at the end of __poly1305_block, so that base
2^64 -> 2^26 conversion *after* __poly1305_block is performed at reduced

> Wouldn't that cause a
> problem? Or is this situation impossible?

If neither of above answers questions, then please elaborate.

Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4483
Please log in as guest with password guest if prompted

More information about the openssl-dev mailing list