Re: [Cfrg] Poly1305 and timing attacks

On Sun, Mar 9, 2014 at 7:56 AM, Yoav Nir <ynir.ietf@gmail.com> 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).
>
> So can anyone on this list comment on this argument?

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
> Cfrg@irtf.org
> 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