> -----Original Message-----
> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of
> Dan Harkins
> Sent: Monday, December 17, 2012 5:54 PM
> To: Igoe, Kevin M.
> Cc: Dan Harkins; cfrg@irtf.org
> Subject: Re: [Cfrg] Status of DragonFly
> 
> 
>   Hi Kevin,
> 
> On Mon, December 17, 2012 1:10 pm, Igoe, Kevin M. wrote:
> > OK folks, we are still on the hook to provide the TLS WG with our
> > analysis of DragonFly as it currently exists.  Here's what I see:
> >
> > 1)      The confidentiality provided by DragonFly is at least as good as
> > Diffie-Hallmann.
> >
> > 2)      Impersonation is a different matter. The nefarious Eve can run
> > through a list
> > of likely passwords, attempting to run the DragonFly protocol once for
> > each guess until she hits one where the DragonFly protocol runs to
> > completion, meaning Eve has almost certainly found the correct
> > password.  Proper monitoring of the error logs should detect such an
> > attack.
> >
> > In the EC case, the situation is a bit muddier.  The use of the nonces
> > in the
> > generation of PE leads to a timing attack.   Assuming the observer can
> > determine
> > precisely how many passes have been made through the  while-loop, each
> > observed instance of the DragonFly protocol between Alice and Bob
> > provides 2 bits of information about their common password.  If the
> > adversary has a list of 2^M passwords which is likely to contain the
> > password in use, passively observing about M+8 or so DragonFly
> > exchanges betwixt Alice and Bob provides enough information to
> > uniquely identify the password (if it is on the list) with high
> > probability.  This is not without cost to the attacker, they need to
> > test the putative passwords one at a time until they find one that
> > generates the observed pattern of number of passes through the while
> > loop. It all comes down to how well the passwords are chosen, and we
> > all know how good users are at picking passwords.
> >
> > Scott Fluhrer proposed an elegant change to DragonFly that fixes this.
> > In the EC case, replace  the while-loop with a for-loop, say "for t =
> > 1,,,,40".  On each pass through this for-loop generate a possible x-
> > coorodinate as in DragonFly,  saving off the first x value which
> > corresponds to a point on the curve.  The only thing that can go wrong
> > here is doing all 40-iterations without finding a good x-coordinate.
> > This is quite unlikely to occur (~ 10^-12), but when it does occur it
> > gives 40 bits of information about the password.  In some VERY high
> > volume applications it might be prudent to choose a value larger than
> > 40.
> 
>   This technique is already used in draft-harkins-tls-pwd-03.

Hmmm, I see it in the ECC section, but not the MODP section.  It would seem appropriate for MODP groups as well, at least in the case where q = (p-1)/2 (e.g. the standard IKE groups).  I believe that either you need to prohibit such groups, or modify the algorithm to handle such groups (possibly making a distinction between those groups, and the 'small subgroup' case; alternatively, just note that k=1 is fine in cases where q<<p).

Also, I suggested 'the middle value' (so that if we scanned through the 40 values, and found that 20 of them were quadratic residues, we'd take number 10).  This was intended to make sure that a well-meaning engineer wouldn't attempt to 'optimize' the search (after all, why keep searching once you've found your result?).  However, it does mean that the value 'k' needs to be agreed to be everybody; everyone can't have their own value; it'd need to be part of the cipher-suite.

I'm not sure whether this idea or your original one (with a stern warning not the 'optimize' the search) is better.

> There is an
> additional security parameter, k, that is used to ensure that k iterations of
> the loop are performed. There are no interoperability issues with any
> particular value of k and I do not recommend a value.

I do believe that you should (at least) offer a solid suggestion; after all, that value will be chosen by people who will read this RFC and nothing else; they may not appreciate all the implications of the below statement.

And, if someone does pick a value that's too low, they're in danger of exposing the secret on behalf of everyone who shares that secret; not just them.

> But I do make this
> statement in the Security Considerations:
> 
>       "The probability that a password will require more than k
>        iterations is roughly (q/2p)^k so it is possible to mitigate a side
>        channel attack at the expense of a constant cost per connection
>        attempt."
> 
> where q is the order of the group formed by the generator and p is the
> prime. Is that statement correct and is it adequate?

Actually, for MODP groups, the probability that k modular-exponentiations is required is about (q/p)^k ; for ECC groups, your listed probability on the number of QR tests is correct, but it can be more easily stated as about (1/2)^k

However, your random 'hunt-and-peck' method for forming the pwd-value also doesn't take constant time, at least for some groups.  For primes p which are just under a power of 2 (standard IKE groups, NIST ECC curves), it's fine; however, other groups (IKE group 24, Brainpool curves), it'll take a variable number of iterations, and hence potentially leaking some information. You might consider the algorithm in B.4.1 from FIPS 186-3 as an alternative; this essentially generates a random number 64 bits larger than what you need, and then modulo-reduce that into the range you want; that gives you an (almost) uniform random number in the range in pretty close to constant time.

Also, if you want to put in a potential optimization in the ECC side, you can note that attempting the compute the square-root is not always the most efficient way to compute whether a number has a square root (aka "is a quadratic residue"); it would be adequate to compute the Legendre symbol (the number is a quadratic residue if the symbol is 1); you would need to take the square root only on the pwd-value we would actually use.  Since computing the Legendre symbol is potentially cheaper than computing the square root (and also does not modify the constant time aspect of the algorithm, at least, no more than computing the square root), you may want to mention that as an acceptable alternative implementation.

If you want a reference on how to compute the Legendre symbol, well, if we're pointing them to FIPS 186-3 anyways, a reference would be the algorithm in C.5 (they call it the Jacobi symbol; it's the same algorithm).

> 
>   regards,
> 
>   Dan.
> 
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg