[Ach] NSA throws out Suite B

[Aaron Zauner]

Errata:

* Aaron Zauner <azet at azet.org> [23/10/2015 19:23:13] wrote:
> 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 :)

I wanted to write quantum computing apocalypse, of course.

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

Pasting the PDF to mutt(1) killed some of the LaTeX math symbols,
exponentiation symbols etc, re-check with the paper. Sorry about
that.

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/bfa3bf97/attachment.sig>