Re: [Cfrg] Poly1305 and timing attacks (clarification)

[David Jacobson <[e-mail]>]

On 3/10/14 7:38 AM, David Jacobson wrote:
> On 3/10/14 6:19 AM, Yoav Nir wrote:
>>
>>
>>
>> On Mon, Mar 10, 2014 at 12:48 AM, Watson Ladd <[e-mail] 
>> <mailto:[e-mail]>> wrote:
>>
>>     On Sun, Mar 9, 2014 at 3:00 PM, Yoav Nir <[e-mail]
>>     <mailto:[e-mail]>> wrote:
>>     >
>>     > On Mar 9, 2014, at 6:45 PM, Watson Ladd <[e-mail]
>>     <mailto:[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.
>>
>> Do you have a reference I can point to on how to make the Poly1305 
>> calculations constant-time?
>>
>> Yoav
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> 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
Before somebody else pounces on me and tries to generalize to 
demolishing my entire point, one more condition needs to be added. And 
that is that in things like the discard method where the generated value 
is going to be a secret, it is sensitive right from the beginning of its 
generation.  Thus the generation and validation of a successful 
candidate must run in constant time.

    --David