Re: [Cfrg] Poly1305 and timing attacks

On 3/10/14 6:19 AM, Yoav Nir wrote:
>
>
>
> On Mon, Mar 10, 2014 at 12:48 AM, Watson Ladd <watsonbladd@gmail.com 
> <mailto:watsonbladd@gmail.com>> wrote:
>
>     On Sun, Mar 9, 2014 at 3:00 PM, Yoav Nir <ynir.ietf@gmail.com
>     <mailto:ynir.ietf@gmail.com>> wrote:
>     >
>     > On Mar 9, 2014, at 6:45 PM, Watson Ladd <watsonbladd@gmail.com
>     <mailto:watsonbladd@gmail.com>> 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.
>
> Do you have a reference I can point to on how to make the Poly1305 
> calculations constant-time?
>
> Yoav
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
I do want to disagree with this approach that everything should be 
constant time.

Sometimes the constant time approach is very onerous and inefficient.

For example, the binary method of inversion in a prime modulus field 
makes many data-dependent branches and the running time is not 
constant.  The constant time approach is to do a modular exponentiation 
to the p-2 power, which is very expensive.  But is is really easy to 
compute  b * inverse(b*x), where b is a randomly chosen blinding value.

In other cases it doesn't matter at all.

For example (and I mentioned this just a couple of days ago) consider 
the case of picking a random field element in a prime modulus field, 
were the modulus p is public.   Just pick random values less that the 
smallest power of 2 >= p-1  Repeat until you have a value < p.   That 
doesn't run in constant time, but it is perfectly safe.  The reason is 
that all it does is at worst reveal something about random numbers that 
you are not going to use. (Watson objected to this, but his objection 
was based on the distinctly different problem of getting a workable 
non-random value based on some other secret, as you might want to do for 
k in ECDSA.)

So in summary, I think it better to say that good crypto-engineering 
practice requires the avoidance of data-dependent branches and array 
indexes unless the data does not depend on any secret or is blinded.  
This is a simple rule that doesn't require complicated analysis.

     --David Jacobson