Re: [TLS] draft on new TLS key exchange

[Rene Struik <[e-mail]>]

Dear colleagues:

The discussion re draft-harkins-tls-pwd-00 seems to focus on two
elements, viz.:
1) use case of password-based key agreement schemes and differentiation
w.r.t. other IETF work products (EKE, etc.);
2) the mapping from passwords to elliptic curve points.

As to #2, indeed, the procedure in Section 4.1.1 for mapping a password
to a point on the curve ("hunting and pecking") has indeed a
non-deterministic running time, due to "trial-and-error" approach and
may, therefore, by vulnerable to a side channel attack. Note, however,
that there are also deterministic methods for mapping a a value to a
curve as introduced, e.g., in the Crypto 2010 paper by Icart, Coron, et
al (cf. also IACR ePrint 2009-340) and the CRYPTO 2009 paper by Icart et
al. The CRYPTO 2009 paper discusses the probabilistic method Dan Harkins
describes (cf. Section 1.1 - Try and Increment Method; Section 5 -
Practical Implementations). Table 1 of Section 6 (Try and Increment v3)
provides results for an implementation that supposedly prevents
potential leakage of information from determining whether x^3 + a x + b
is a quadratic residue in GFp via the Legendre symbol computations.
Thus, that paper suggests that side channel resistance can be dealt
with, at the expense of time latency. The paper also illustrates that
the deterministic method for "hashing to a curve" has better performance
(again, refer to Table 1 of Section 6 of the CRYPTO 2009 paper).

I hope this helps.

Best regards, Rene


On 07/10/2011 1:58 PM, Martin Rex wrote:
> Dan Harkins wrote:
>> The relation-- yours is "faster" than the unknown one-- means nothing.
>> That knowledge doesn't help. Knowing how many iterations the hunting-
>> and-pecking loop went through to find PE for an unknown password might
>> but the relationship between two means nothing.  In fact, since both
>> sides are contributing randomness into the hunting-and-pecking loop
>> yours might be "faster" one time and considerably slower the next time.
>> That knowledge doesn't really help.
> The number of iterations for the hunting and pecking is visible in the
> timing unless a reliable response time blending is employed (which would
> have to account for an attacker running multiple requests in parallel to
> slow down server-side processing).
>
> Although both sides contribute randomness into the process, the only
> unknown in the low-entropy password, everything else is revealed.
> Since it is revealed, the attacker can use the timing "distance"
> between processing his own password and processing guessed passwords
> with the EXACT same parameters to sort out unlikely candidates.
>
> -Martin
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls


-- 
email: [e-mail]
Skype: rstruik
cell: [phone]
USA Google voice: [phone]