Subject: Re: [TLS] Safe ECC usage

From: Dan Brown <[email-masked]>
Date: Mon, 4 Nov 2013 20:21:19 +0000

Hi again ECC in TLS enthusiasts,

Sorry to raise this very theoretical issue yet again, but I realized a 
stronger argument for one of my claims in this thread.

Claim:

The Brainpool 256-bit curve, as a remedy to a hypothetically manipulated P256, 
provides more security assurance than Curve25519, assuming faultless 
implementations.

Mildly formal argument for the claim above:

P256: Let us call the curve weakness, which we are hypothesizing here that the 
P256 seed has been exhaustively searched, i.e. manipulated, to have: the 
spectral weakness (a term inspired by spectre and prism).  For simplicity, let 
us initially assume that the best available process to manipulate P256 was 
exhaustive search of seed, and this had an a priori expected running time of 
2^w trial seeds.  (A more complex analysis might go further and postulate a 
weakness in the P256 curve generation algorithm, perhaps even in the SHA1 hash 
function used, but in this case I will still use 2^w for the number of seeds 
that must be tried under this more complicated situation.)

Brainpool: Under the fairly reasonable heuristic assumptions below, one can 
argue that the probability the Brainpool 256-bit curve is affected by the 
spectral weakness with probability about 2^(-w).   The heuristic assumptions 
here are the independence of spectral weakness from the curve generation 
algorithm and from the digits of pi and e, or any similar fundamental 
constants (with the wiggle contributing the about).   These assumptions are 
fairly mild assumption about the spectral weakness, in my opinion.

Curve25519: It can also be argued (and, as I understand it, has already been 
argued on the list) that Curve25519 is affected by the spectral weakness with 
probability about 2^(-w), under the either of the following assumptions: (1) 
the spectral weakness affects curves uniformly, or (2) the spectral attack 
would be very similar to known attacks, e.g. PH, MOV and SASS, and that the 
non-random features that Curve25519 displays, such as small coefficients, have 
no bearing whatsoever on those attacks, thereby rendering Curve25519 as safe 
as any random curve.

Brainpool vs Curve25519: Both of the assumptions above made for Curve25519 on 
the spectral attack are formally, and intuitively, stronger than the mild 
assumption made for Brainpool curve, therefore the assurance that Curve25519 
provides is weaker than that of Brainpool.

Much more informal asides:

As I, and others, have noted already in this thread, Curve25519 has very good 
resistance to 1st person attacks, i.e. it has rigidity, perhaps even more than 
Brainpool.  Unfortunately, that does not sufficient to rule out the spectral 
weakness affecting Curve25519, at least under the arguments above, except 
under quite strong assumptions.  Besides, I find it unreasonable to suspect a 
1st person attack from Curve25519 because even in the very unlikely event that 
DJB knew what the spectral weakness, or even some other weakness, was, I feel 
certain he would reveal it, not exploit it.

At one point in this thread, I mistakenly tried to apply something like the 
semiformal argument above for future attacks, rather than for the spectral 
weakness.  Indeed, under the spectral attack hypothesis, it is unnecessary to 
argue, or even further speculate, about the nature of a future attack, e.g. 
whether they are more likely to affect random or special curves.  Rather, 
under the spectral attack hypothesis, we presume that an attack already 
affects P256, and we may attempt to avoid it when choosing alternative curves, 
and must avoid it as best as possible if we offer those curves as being safe 
against the spectral attack.  In other words, when I argued that it was more 
prudent to use random curves, e.g. Brainpool than to use special curves, e.g. 
Curve25519, merely because one has to be pessimistic as possible in one's 
assumptions, I was right about spectral attack, but wrong about future 
attacks.  Just to be clear, this is not to say that I think it likely, or that 
the evidence points to it being likely, for the spectral weakeness to affect 
Curve25519.  What I am saying is that Brainpool seems to be designed, whether 
intentionally or not, in such a way to offer better assurance of avoiding the 
spectral weakness.

The Brainpool curve is a fixed curve, but seems to be nearly as pseudorandom 
as a fixed curve could be.  Nonetheless, using a random curve for every 
exchange, or pair of users, ought to be even safer than Brainpool, but would 
be too inefficient, for example, due to the cost of point counting.  But that 
issue seems to independent of the arguments for the claim above.

I alluded above to a more complicated situation in which the curve generation 
algorithm is weak.  This seems unlikely for many reasons, but this issue is 
independent of the main claim that Curve25519 relies on a strong assumption 
about the spectral attack.  Also, this issue starts to become a different one 
from pure manipulation.  Further, if this hypothesis goes so far as to 
postulate invertibility of SHA1, then we may need further consider other 
criteria on elliptic curves, such as resisting Cheon-type attacks.

Of course, many reasons remain to doubt the existence of a spectral attack, 
including: the extensive research efforts into ECC, the risk of standardizing 
curves one knows to be weak, many other curves and algorithms from the same 
sources not known to be weak or subject to manipulation.

It may be worthwhile for TLS to offer its users more guidance than just "here 
are some safe algorithms you can use".  Some TLS users may have a reasonable 
expectation of security from the available TLS algorithms, and perhaps even 
security levels, which is reasonable if only because of the S in TLS.  Some 
users may want to make their own decisions about security.  Yet others may 
seek guidance for specific security goals, hoping to find it the TLS specs. 
Naturally, nobody has a very strong incentive to commit to too strong security 
claims.  If TLS is to offer various curves as providing 128-bit security, then 
it might point to what the provisos behind each to guide users in their 
choice.

Suggestions for further discussion:

Perhaps, I am missing or misunderstanding an argument for Curve25519 avoiding 
the hypothesized spectral weakeness.  Please correct me as needed.

Perhaps, my security analysis for Brainpool is unconvincing or too vague. 
Maybe we can discuss further.  I suspect one could formalize it better, i.e. 
random oracle model, pseudorandom functions, etc.  Certainly, there is a 
logical leap from pseudorandom fixed to random, but this independent of the 
arguments above.

Perhaps, one really can quantify the amount of wiggle room in the curves for 
Brainpool and Curve25519 to get slightly different probabilities from 2^(-w), 
with Curve25519 having a lower probability.  That does not override the 
stronger assumptions being necessary, but may be an argument that the relative 
security between the two is incomparable.

Best regards,

Dan

---------------------------------------------------------------------
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.