Re: [TLS] Safe ECC usage

[Dan Brown <[e-mail]>]

D. J. Bernstein writes
> Dan Brown writes:
> > it is also reasonable to assume that NSA knows of an attack A but is
> > unwilling to reveal it, and manipulated P256 to avoid A
> 
> Sure. In BigBrotherLand, the eavesdropper Eve is actually a big fan of
> the innocent users Alice and Bob, and is helping protect them against
> hidden weaknesses in their communication system.
> 
> However, our job as _cryptographers_ is to tell Alice and Bob how to
> protect themselves against the possibility of _bad_ behavior by Eve.
> That's why all these ECC standards are advertising the "verifiable"
> randomness of the NIST curves---they're claiming that the curves are
> protected against bad behavior by NSA's Jerry Solinas. That's also why

Aside, and smaller point: To me, the fact that the NIST Koblitz curves and
the curves

http://cacr.uwaterloo.ca/techreports/2001/corr2001-68.ps
 
seem just as free from manipulation as Curve25519, seems like mild evidence
against a backdoor in P256.  Publication of these alternatives would
undermine a plan to get one's adversary to use backdoors unwittingly.  I
think I already made this point on the TLS list.


> people are unhappy to learn that the advertising is false.

Good point: I did not realize most people were unaware that the seeds had no
explanation, yet still concluded verifiably random ruled out every possible
mischief.  I also agree that "verifiably random" is a misnomer, but did
consider it a minor one.  Do you have a better suggestion?  

Also, this is why I am trying to understand what you are advertising about
Curve25519.

You gave an example that, under reasonable assumptions, with 2^(-30)
probability the ECDLP in Curve25519 could be solved in 2^64 computations.  I
do not see how those assumptions are reasonable, but even so, if 2^30 people
use Curve25519, then is that a good risk?  Do you feel that the system-wide
risk for RSA, or integer DH is comparable?


> 
> When we see a protocol that turns out to have Eve as a trusted third
> party with the power to compromise security, we fix the protocol. We
> don't say "Well, gee, maybe Eve is actually helping our security."

Yes, but I think already implied this when I said should assume the worst,
etc.  

> 
> > The Brainpool curves have some kind of justification, albeit maybe
> not
> > a full-fledged proof.  In other words, to me, the Brainpool approach
> > presents some kind of best-we-can-do-effort to resist attacks not yet
> > known to us.
> 
> No, it doesn't. Maybe an unknown attack is _more_ likely to break
> brainpoolP256r1 than to break Curve25519. You keep using words like
 
Maybe.  Maybes will always exist in crypto.  We just try to reduce them,
whenever and however we can.

> "best" and "prudence" and "advantage"; but you have zero justification
> for any of this. You keep
> 
>    * misrepresenting brainpoolP256r1 as a random curve and
>    * stating the "random is safer" myth in several different ways;
> 
> do you not realize that this myth was solidly debunked several years
> ago? Section 11 of http://eprint.iacr.org/2008/390.pdf presents several
> clear counterexamples; do you dispute those counterexamples?

Thanks, I had completely forgotten about that paper, probably because I
don't see ether issue as very important.  In other words, we're splitting
hairs.

Anyway, the eprint of Koblitz, Koblitz and Menezes [KKM] lumps brainpool
into the class of random curves, similarly to me.  

Of course, the brainpool curve is a fixed curve.  (I don't think ever
misrepresented that fact.)  If the brainpool and nist seeds were kept
secret, then these pseudorandom curves would be hard to distinguish from
some class of random curves, or do you dispute that?  I don't think that
"maybe" attack against brainpool curve that you hypothesize above, is
intended to be a such distinguisher (although it could be, since we're
talking possibilities now), but rather one that, by some fluke, affects that
particular seed used in the brainpool.

The KKM paper does not say "myth", it says "conventional wisdom".  Yes, I am
just applying the conventional wisdom.  KKM do not claim to "solidly debunk"
that wisdom, and instead say we are left to make our "best guess" about
future attacks.

Their examples about prime-field curves make "plausible" assumptions about a
future attack.  Well, one could "plausibly" assume that a future attack
affects a random curves uniformly at random, and then conclude that one
fixed curve is just as good as any other.  But, this seems to me almost like
circular reasoning. In other words, I do have some trouble with their
example: their assumptions may be artificial.

I also dispute the implicit KKM contention that conventional wisdom did not
admit any possibility special curves could be safer.  Rather I see
conventional wisdom already looked at the evidence and made its "best guess"
that random curves would be safer, admitting the possibility that it could
be otherwise.

Also, I don't fully agree with the implicit KKM contention that just because
some attacks are unknown, and that various attacks will always be possible,
therefore we should totally rely on intuition.  I agree that intuition, as
in "best guess" is a good start, but a careful algorithm selection should
try to formalize this initial intuition, isolate and reduce assumptions,
prove what little can be proved and so on. 

The KKM example about isogenies between curves is very interesting, of
course.  Maybe I am mistaken, but I think that brainpool curves address that
via the c(E) thing.  Have you considered the equivalent for Curve25519?  It
would be interesting to know if the ECDLP in Curve25519 is, via isogenies,
equivalent to the ECDLP in many other curves (perhaps only of the same
size).  They we could focus our debate a little better.

> 
> If you think there's some reason that brainpoolP256r1 is more like the
> examples where randomness helps security, rather than the examples
> where randomness hurts security, then you should say what that reason
> is. You can't simply pretend that the counterexamples don't exist.

I was not pretending, but I did make a bad mistake: when I assumed that
worst for Curve25519, I forgot to assume the worst for random curves.  In
other words, I supplied the wrong reason for my position.  So, I have being
thinking a little more about why I hold this position. Here's what I have so
far, all of which is informal.  Also, I am restricting this to prime-field
elliptic curves.


1. Suppose some extremes: if an attack affects all random curves, excluding
Curve25519, then basically ECC would be no more, and Curve25519 would now
belong to the class "Special Elliptic Curve Cryptography".  How logical
would it be for SECC to inherit the previously believed security of ECC?
Maybe it SECC would be secure, but clock would have to started anew to build
up trust.  The opposite extreme is that some attack affects only a special
class of curves, as in the MOV and SASS attacks.  Then ECC goes on, with not
much worry, and we just drop those affected curves.  This has happened twice
already.


2. So far, there no are 0 (*) attacks against random curves, and 2 against
special curves: the MOV and SASS attacks.  I view this as quite good
evidence in favour of random curves, over special curves.  Of course, the
next attack could be against random curves.  Of course, with only 2 attacks,
the evidence is slim.  In addition to this evidence of these two attacks,
consider these attacks are rather old, and no new ones have been published
for many years.

Regarding this point (#2), I have a hard time reconciling some of your
views: 

"zero justification": you keep saying this phrase, and applied against
random safer than special.  Is this referring to fact that there's always a
possibility of something completely surprising and unlike past experiences? 

"overwhelming evidence": you used this phrase, I think in reference to the
MOV and SASS attacks, to support the argument that Curve25519 belong to a
different special class than the known weak special classes.  (I.e.
something about the field sizes, the curve sizes and coefficient sizes being
irrelevant, because they do not figure much in the MOV and SASS attacks).


What I am having trouble with is how the same fact set (MOV+SASS) presents
both "zero justification" for arguments that favour brainpool over
Curve25519 and "overwhelming evidence" for brainpool incomparable to
Curve25519.  Could you elaborate? 


3. This next reason is very informal, but I think it affected my thoughts.
Curve25519 is a newcomer to TLS, compared to the NIST curves and brainpool
curves, and as such, warrants scepticism.  The burden is on any new
algorithm presented to TLS is to identify its advantages, and these claims
should be scrutinized by the TLS WG.  Curve25519 may have sufficient other
advantages over alternatives for adoption in TLS: efficiency, secure
implementation, and so on.  I suggest that offering Curve25519 as a means to
provide algorithm agility, e.g. if RSA, integer DH, and random EC including
brainpool collapse, then maybe Curve25519 will be sole survivor.  Certainly
possible.


//

On the other hand, after reading Section 11 of KKM, I remembered something
else that is a slight shred of evidence that special curves are safer than
random curves (although not with respect to the ECDLP):

The Cheon-type attacks affect random curves slightly more adversely than
certain special curves.  That is, some special curves in which n-1 and n+1
are nearly prime resist Cheon-type attacks, but these curves are rare among
random curves (or sizes), so could be viewed as special.  

Although this is a very weak attack, and arguably moot if one assumes
one-way KDFs, it exists, unlike the hypothetical attack as in the KKM
examples on prime-field elliptic curves.  

I don't think that this is enough evidence to override the other evidence
favouring random curves, though.


//


If we move far away from prime-field elliptic curves, say to hash functions,
then I do not see any evidence that random is safer special.  Indeed, if one
defined a random hash function by random sequence of bit operations, perhaps
formalizing this through straight line programs, then, I would imagine the
security would be very bad.  In that case, special seems safer than random.
(Going yet farther astray, I think there's results in coding theory that
random codes can do as well as special codes.)  Anyway, to argue random over
special in the case ECC, we have to look at the evidence particular to ECC.


> 
> By the way, I also don't see anything in the Brainpool document along
> the lines that you're claiming. For example, the document never claims
> that its primes are more secure than "special" primes; it clearly
> states that it avoids "special" primes "to avoid patented fast
> arithmetic."
> 
 
Yes, I already acknowledged most of that previously in this thread.

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.