[Ach] NSA throws out Suite B

[Aaron Zauner]

Hey,

First off: Some might have seen some crazy news posts about a
possible quantum cryptography apocalypse, let's not go there in
this thread please :)

koblitz and menezes have recently published a non-acedemic (read:
non ECC math) paper on a recent NSA statement
(https://www.nsa.gov/ia/programs/suiteb_cryptography/), deprecating
their recommended P-256 curves and pushing new adopters for
post-quantum algorithms instead (theirs aren't public yet).

I _really_ recommend reading this paper instead of any news or blog
post, it's execelltly written by two of the fathers of ECC and has a
lot of insider information and background on stuff happening in NSA
that you won't read anywhere else: https://eprint.iacr.org/2015/1018

(Besides a short intro to ECC in some sections it's very easily
readable for people following these topics in my opinion, it's 14
pages)

I'm just going to quote some sections here without commenting:

```
Since the Snowden revelations, many people have cast doubts on the
NSA-generated NIST elliptic curves even though no concrete
weaknesses in them have been discovered since they were proposed in 1997. These
people speculate that NSA researchers might have known classes of weak
elliptic curves in 1997. With this knowledge, the NSA people could have
repeatedly selected seeds until a weak elliptic curve was obtained.
This scenario is highly implausible for several reasons. First, the
class of weak curves must be fairly large in order to obtain a weak curve
with the seeded-hash method. For concreteness, suppose that p is a fixed
256-bit prime. There are roughly 2257 isomorphism classes of elliptic
curves defined over Fp. Let s be the proportion of elliptic curves over Fp
that are believed (by everyone except hypothetically the NSA in 1997) to
be safe. This class of curves includes essentially all elliptic curve
of prime order (with the exception of prime-field anomalous curves and those that
succumb to the Weil/Tate pairing attack). Since the proportion of 256-bit
numbers that are prime is approximately 1/(256 ln 2) ≈ 2^−8 , the proportion of curves
that are strong is at least 2−8  . Now suppose that the proportion of these
curves that the NSA knows how to break is 2−40. Then it can select
such a weak curve by trying about 248 seeds. The number of NSA-weak curves
is thus approximately 2209. The discovery today of such a large class
of weak curves would certainly cast doubt upon the general security of
elliptic curves and would be a good reason to abandon ECC altogether.

A second reason for the implausibility of the above scenario is that
it is highly unlikely that such a large family of weak elliptic curves
would have escaped detection by the cryptographic research community since
1997. It is far-fetched to speculate that NSA would have deliberately
selected weak elliptic curves in 1997 for U.S. government usage (for both
unclassified and classified communications [38]), confident that no one else would be
able to discover the weakness in these curves in the ensuing decades.
```

(From a footnote)
```
Dattani and Bryans [15] say: “It is well known that factoring large
numbers on classical computers is extremely resource demanding, and that Shor’s algorithm
could theoretically allow a quantum computer to factor the same number with drastically
fewer operations. However, in its 20-year lifespan, Shor’s algorithm has not gone far
in terms of factoring large numbers. Until 2012 the largest number factored using Shor’s
algorithm was 15, and today the largest is still only 21. Furthermore, these
factorizations were not genuine implementations of Shor’s algorithm because they relied on prior
knowledge of the answer to the factorization problem being solved in the first place.”
```

[...]

(But please read the whole text before replying)

The appendix gives a one-paragraph per scheme introduction to
post-quantum cryptography proposals currently being considered by
researchers. There's also quite some commentary about possible
"quantum computers" (i.e. there're none for the next 20+ years).


Aaron
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Digital signature
URL: <http://lists.cert.at/pipermail/ach/attachments/20151023/d3cfaabf/attachment.sig>