Re: [Cfrg] Poly1305 and timing attacks

[Watson Ladd <[e-mail]>]

On Mon, Mar 10, 2014 at 6:19 AM, Yoav Nir <[e-mail]> wrote:
>
>
>
> On Mon, Mar 10, 2014 at 12:48 AM, Watson Ladd <[e-mail]> wrote:
>>
>> On Sun, Mar 9, 2014 at 3:00 PM, Yoav Nir <[e-mail]> wrote:
>> >
>> > On Mar 9, 2014, at 6:45 PM, Watson Ladd <[e-mail]> wrote:
>> <snipped agreement>
>> >
>> >> For Poly1305 as used in this draft, I am very, very hesitant about
>> >> approving any draft that says not-constant time is okay. However, if
>> >> the entire keys are being generated pseudorandomly, then I think, if
>> >> the side channel isn't gratuitously large, it's possibly safe. Saying
>> >> anything more concrete would require a lot of painful analysis of what
>> >> is leaked and how it can be used.
>> >>
>> >> Personally, I don't understand why making the crypto not constant
>> >> time, and thus open to attacks, simplifies the security
>> >> considerations. It might make the job of the implementor easier, but
>> >> it makes the job of the person who builds on top harder.
>> >
>> > It makes the security considerations simpler because it makes all the
>> > talk about constant time implementations go away and eliminates the need for
>> > pointing people at how to accomplish this. I agree I probably can’t do this,
>> > as this implementation might later be used as part of a library for other
>> > things. It’s not generally good to instruct people on how to make an
>> > implementation with a warning label (that they will later ignore).
>>
>> Well, I have to fundamentally disagree with this. A constant-time,
>> constant-memory access, constant-control flow implementation is far
>> more reassuring than one which doesn't have these properties.
>
>
> Hey, no need to pile it on. You've already convinced me that the text needs
> to stay.

Ah, I was disagreeing with the claim that this makes "security
considerations simpler". But yes, I think we are in agreement.

>
> Do you have a reference I can point to on how to make the Poly1305
> calculations constant-time?

Yes, DJB's Poly1305-AES paper. But that uses the FPU heavily: It uses
2^26 as a base, taking advantage of the mantissa being 2^53 bits, and
uses special rounding instructions for carries. This is because the
integer multiplier on 32 bit Intels had issues.

In assembler one can use saturated word arithmetic, taking care to
avoid data dependent loops. Barrett reduction always involves a
maximum of three reductions, so you write a constant time
reduce_if_necessary function, and apply to the product during the
cleanup. But this isn't the fastest. It's a small modification to the
usual method.

On a 64-bit machine 5 limbs of 26 bits, base 2^26 works fine. One does
the addition, with no need to reduce as the limbs grow to only 27
bits, then does the multiplication, getting 10 44 bit limbs. These
represent a number at most 2^262, so after carrying the top limb is a
maximum of 28 bits. Using the fact that we are modulo 2^130-5, limb 6
is multiplied by 5 and added to limb 1 and so on. Finally a carry
chain is used, and some analysis has to be done to see if you reduce
back to something you can add again. This still might not be optimal:
I've skimmed over the multiplication, and the carry chain can be
tricky.

On a 32-bit machine I'm not sure what one does. There are a lot of
options, but I don't know which is best.

As a sidenote blinding is just too slow: it doubles the number of
multiplications that have to be done. It's also not clear that it can
eliminate the side channel because you need to operate on two values,
not just one.

Sincerely,
Watson Ladd