Re: [Cfrg] Status of DragonFly

[Rene Struik <[e-mail]>]

Hi Kevin:

I do share some of your timing attack concerns. Unless I missed 
something here, your suggested fix does not seem to work, however:

Suppose A and B use ECDH with as generator the point G(p):= pG, where 
p:=kdf(..) {I use small-case p ("password") rather than capital-case X 
below (so as to separate scalars and elliptic curve points)}. Now, 
suppose A and B exchange X:=xG(p) where p is the correct password and 
where Y:= y G(p'), where p' is any guess for p by B (or just takes 
p":=1). Then A (the legitimate party holding password p) computes Ka:= 
(xy) G(p')= (xy p') G and B computes Kb:=(yx) G(p)= (yxp) G. In other 
words, Ka:= p' K, Kb:= p K, where K:= (xy)G. So, Ka:= (p'/p) Kb. Now, 
once A sends B a key confirmation message, B can just cycle through the 
password space, compute a candidate key that A could have computed and 
check the validity of his guess via verification of the key confirmation 
message just received.

As to implementing Dragonfly, one has to be careful in case of active 
attacks: as an example, if one uses multiple-point multiplications, one 
may end up at the point of infinity as intermediate point in the 
computation, thus forcing implementations to use exception handling 
routines for point addition/doubling along the entire computational path 
(Note: if one hits the point at infinity, this exposes the password 
used, thus leaking the entire password in an observable way). If one 
does not use multiple-point multiplications, this attack seems much 
harder but requires two full scalar multiplications (rather than one 
scalar multiplication as, e.g., SPEKE requires).

Best regards, Rene

==
A possible fix is to use the KDF to generate a random X, 1<X<q, where q 
is the size of the cryptographic
subgroup of the curve, and take PE = X*G, where G is the generator of 
the cryptographic subgroup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it is VERY 
unlikely that more than 1 call to the
KDF will be needed.


On 12/13/2012 1:42 PM, Igoe, Kevin M. wrote:
> I'd like the reading list's input on DragonFly (hereafter called DF), 
> Dan Harkins' Password Authenticated
> Key Exchange design (draft-irtf-cfrg-dragonfly-00).  I'd like to point 
> out that draft-harkins-tls-pwd-03
> is a proposal to useDF in  TLS that differs slightly from the CFRG draft.
> Here is where I believe we stand:
>
>  1. Confidentiality: The proof that the confidentiality of the key
>     generated by the DF
>     protocol is reducible to the standard Diffie-Hellmann problem is
>     quite straight
>     forward, so the resulting shared secret value is at least as
>     secure as with  standard DH/ECDH.
>  2. Authentication: Obviously the system can be no more secure than
>     the password
>     being used. I believe the most viable attack is to guess a
>     password, use this password
>     to initiate the  DF protocol with the endpoint being attacked, and
>     see if it works.
>     Monitoring the system logs should easily detect such an attack.
>  3. Timing: I'm particularly concerned about the method used to
>     generate the PE (password
>     dependent base point) in the ECDH case. Inside a while loop,
>     several parameters,
>      including the identities of the two endpoints, the shared
>     password, and a counter are
>     passed to a KDF to produce an n-bit output, where the curve is mod
>     an n-bit prime p.
>     The resulting n-bit value X is checked to see if 0 <= X < p and
>     X^3+a*X+b is a quadratic
>     residue mod p (an event of probability ½).  If both these tests
>     are passed, the while
>     loop is exited and X is used as the x-coordinate of our PE.
>
>     The problem I see with (3) is that the number of times through the
>     loop gives an opponent a
>     check  on any putative value for the password.  E.g.  if their
>     current guess for the password
>     takes many passes through the while loop to generate the PE, but
>     they observe that the DF response
>      time is inconsistent with that, they have eliminated that guess
>     for the password.
>
> When DF is applied to TLS in as described in draft-harkins-tls-pwd-03, 
> two nonces are used as
> inputs to the KDF, which has two consequences:
>
>  1. the PE MUST be computed online
>  2. each DF exchange gives an independent timing check on the password.
>
> The opponent can passively sit back, monitoring the timing of DF 
> exchanges on various links until
> they stumble across one where the timings match up with the timings 
> associated with one of the
> passwords they are testing. They've now are able to bypass the 
> authentication provided by DF.
>
> A possible fix is to use the KDF to generate a random X, 1<X<q, where 
> q is the size of the cryptographic
> subgroup of the curve, and take PE = X*G, where G is the generator of 
> the cryptographic subgroup.  For
> most cryptographic curves,  q  is very, very close to 2^n, so it is 
> VERY unlikely that more than 1 call to the
> KDF will be needed.
> Another fix would be to require PE generation be done offline, which 
> would eliminate any possibility of
> using nonces in the DF protocol.  One could, however, mix the nonces 
> in after the completion to the
> DF based Diffie-Hellmann exchange.
> ----------------+--------------------------------------------------
> Kevin M. Igoe   | "We can't solve problems by using the same kind
> [e-mail]_ <mailto:[e-mail]>  | of thinking we used when 
> we created them."
>                 |              - Albert Einstein -
> ----------------+--------------------------------------------------
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]