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

[David Benjamin via RT]

On Fri, Mar 25, 2016 at 3:07 PM Andy Polyakov via RT <rt at openssl.org> wrote:

> > For x86-64, this seems to be the bug:
> >
> > $ git diff
> > diff --git a/crypto/poly1305/asm/poly1305-x86_64.pl
> b/crypto/poly1305/asm/
> > poly1305-x86_64.pl
> > index 3c810c5..bc14ed1 100755
> > --- a/crypto/poly1305/asm/poly1305-x86_64.pl
> > +++ b/crypto/poly1305/asm/poly1305-x86_64.pl
> > @@ -97,6 +97,7 @@ $code.=<<___;
> >         add     $d3,%rax
> >         add     %rax,$h0
> >         adc     \$0,$h1
> > +       adc     \$0,$h2
> >  ___
> >  }
>
> Correct. Testing is done on all platforms.
>
> > 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? If it were,
that would require one more reduction.

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. Wouldn't that cause a
problem? Or is this situation impossible?

David

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