Subject: [Cfrg] Poly1305 and timing attacks

From: Yoav Nir <[email-masked]>
Date: Sun, 9 Mar 2014 16:56:14 +0200

Hi

I mentioned this during the meeting, but there was no discussion on this
subject there, so I thought I'd raise it here.

I got a private message in response to draft-nir-cfrg-chacha20-poly1305
that questions the text about constant time implementations for Poly1305.
The argument can be outlined as follows:

Side channels in general and timing vulnerabilities in particular are bad
because they reveal either parts of the plaintext they work on, or parts of
the key that is used. However, Poly1305 works on the ciphertext that is
sent on the wire anyway, so exposing that does not matter. Also, Poly1305
requires a different one-time key for each invocation, so revealing some
information about that one-time key doesn't matter, because it will not be
used again. So in summary, timing attacks on Poly1305 don't matter.

This argument is very attractive to me, because if it is valid, it makes
the security considerations much simpler, and significantly reduces the
complexity of implementing these algorithms (the "competent" vs "good"
coder from slide 2).

So can anyone on this list comment on this argument?

Thanks

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Sun, 9 Mar 2014 09:45:18 -0700

On Sun, Mar 9, 2014 at 7:56 AM, Yoav Nir <[email-masked]> wrote:
> I got a private message in response to draft-nir-cfrg-chacha20-poly1305 that
> questions the text about constant time implementations for Poly1305. The
> argument can be outlined as follows:
>
> the key that is used. However, Poly1305 works on the ciphertext that is sent
> on the wire anyway, so exposing that does not matter. Also, Poly1305
> This argument is very attractive to me, because if it is valid, it makes the
> security considerations much simpler, and significantly reduces the
> complexity of implementing these algorithms (the "competent" vs "good" coder
> from slide 2).
>

An implementation of Poly1305 that isn't constant time imposes a
significant additional burden on callers to generate the entire key
pseudorandomly, as opposed to changing the last part. In the AEAD or
MAC as defined here that's okay.

The place where Poly1305 leaks information is likely in the polynomial
evaluation. It is acceptable to have (r, s1), (r, s2) ... with r
unchanging and the s generated pseudorandomly. But in an
implementation which isn't constant time could eventually reveal r
over multiple messages.

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.

Two sidenotes: IVs are not nonces, and there is a typo where "times
might be great then 2^256 or less then 2^256".

Sincerely,
Watson Ladd
>
> Thanks
>
> Yoav
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Yoav Nir <[email-masked]>
Date: Mon, 10 Mar 2014 00:00:03 +0200

> MAC as defined here that's okay.

Understood.

> implementation which isn't constant time could eventually reveal r

Agree. However, from what I have heard in both the IPsec and TLS working groups, there is little to no interest in the stand-alone versions of chacha20 and poly1305, only the AEAD combination, So I might divide the security considerations into stuff that is for poly1305 stand-alone, and other considerations for the AEAD, which can possibly be less onerous.

> 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).

> might be great then 2^256 or less then 2^256”.

Yes, “sometimes” is a single word.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sun, 9 Mar 2014 22:22:38 +0000

Hi Yoav,

I disagree with the argument as it is currently stated. Suppose 96 bits of a 128-bit MAC key leak via a side channel analysis from a single invocation of the MAC. (Somewhat extreme but within the scope of the scenario you mention.)

Then an active MITM adversary can successfully inject a modified packet for the same key/sequence number with probability 2^{-32}, simply by guessing the missing key bits. That is, the effect of partial key leakage on security is not "null", even in the scenario where keys are only used once.

The argument you cite needs to be more carefully stated to properly account for this weakness.

Cheers

Kenny

Sent from my iPad

On 9 Mar 2014, at 14:56, "Yoav Nir" <[email-masked]<mailto:[email-masked]>> wrote:

Hi

I mentioned this during the meeting, but there was no discussion on this subject there, so I thought I'd raise it here.

I got a private message in response to draft-nir-cfrg-chacha20-poly1305 that questions the text about constant time implementations for Poly1305. The argument can be outlined as follows:

Side channels in general and timing vulnerabilities in particular are bad because they reveal either parts of the plaintext they work on, or parts of the key that is used. However, Poly1305 works on the ciphertext that is sent on the wire anyway, so exposing that does not matter. Also, Poly1305 requires a different one-time key for each invocation, so revealing some information about that one-time key doesn't matter, because it will not be used again. So in summary, timing attacks on Poly1305 don't matter.

This argument is very attractive to me, because if it is valid, it makes the security considerations much simpler, and significantly reduces the complexity of implementing these algorithms (the "competent" vs "good" coder from slide 2).

Thanks

Yoav

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Sun, 9 Mar 2014 15:48:52 -0700

> On Mar 9, 2014, at 6:45 PM, Watson Ladd <[email-masked]> wrote:
<snipped agreement>
> 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…

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. The
security of a system using the second is far less evident than one
using the first. While implementing the second might be easier, it's
less trustworthy, and hence using it in a system requires more, rather
than less, analysis. The stronger the building blocks of a protocol
are, the easier it is to argue for its security.

Sincerely,
Watson Ladd

---

From: Yoav Nir <[email-masked]>
Date: Mon, 10 Mar 2014 15:19:33 +0200

On Mon, Mar 10, 2014 at 12:48 AM, Watson Ladd <[email-masked]> wrote:

> > 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).
>
> 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

---

From: David Jacobson <[email-masked]>
Date: Mon, 10 Mar 2014 07:38:00 -0700

On 3/10/14 6:19 AM, Yoav Nir wrote:
>
>
>
> On Mon, Mar 10, 2014 at 12:48 AM, Watson Ladd <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     On Sun, Mar 9, 2014 at 3:00 PM, Yoav Nir <[email-masked]
>     <mailto:[email-masked]>> wrote:
>     >
>     > On Mar 9, 2014, at 6:45 PM, Watson Ladd <[email-masked]
>     <mailto:[email-masked]>> wrote:
>     <snipped agreement>
>     >
>     > 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).
>
> Hey, no need to pile it on. You've already convinced me that the text 
> needs to stay.
>
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

---

From: David Jacobson <[email-masked]>
Date: Mon, 10 Mar 2014 08:32:10 -0700

On 3/10/14 7:38 AM, David Jacobson wrote:
>>     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
> 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.
>
> 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.)
>
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

---

From: Watson Ladd <[email-masked]>
Date: Mon, 10 Mar 2014 08:44:07 -0700

On Mon, Mar 10, 2014 at 6:19 AM, Yoav Nir <[email-masked]> wrote:
>> > 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

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

> 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