[cryptography] A question about public keys

Nico Williams nico at cryptonector.com
Sun Sep 29 16:08:44 EDT 2013

I should add that the ability to distinguish public DH keys from
random is a big deal in some cases.  For example, for EKE: there's a
passive off-line dictionary attack that can reject a large fraction of
possible passwords with each EKE iteration -- if that fraction is 1/2
then after about 20 rounds of EKE you'll have a very high likelihood
of having recovered the user's password.  This example is hinted at in
the Elligator paper (the paper's focus being on privacy protocols).
With Elligator (and randomly setting the one bit that is always zero
in curve25519 public keys), the passive attacker would have to observe
a very large number of EKE rounds before having enough evidence to
reject enough possible passwords (that yield public keys larger than
2^256 - 19) to have a good chance of recovering the actual password.
Elligator will be a great advance indeed, when it is available.


More information about the cryptography mailing list