mti

Even assuming D-Wave actually achieves quantum annealing (a highly uncertain proposition at this point), the implications for cryptography are inexistent. Quantum algorithms relevant to cryptography (mostly Shor's and Grover's) require a general purpose quantum computer, which the D-Wave machine is emphatically not.

Someone interested in a serious, rather than derisive, attempt at selecting good curves with cofactor 1 may want to look at the recent paper by Bos, Costello, Longa and Naehrig[0].

[0]: http://eprint.iacr.org/2014/130

To clarify some of these points further:

- As mentioned elsewhere in the discussion, the algorithm does have an impact on some elliptic curve-based cryptosystems, but it is an indirect one. The attack is against the discrete logarithm problem in small characteristic finite fields; that isn't a security concern for the elliptic curve DLP (even over fields of small characteristic), except in the special case when ECDLP reduces to finite field DLP. That reduction is called the Menezes-Okamoto-Vanstone attack, and only applies to a restricted class of elliptic curves: so-called "pairing-friendly" curves, which are used in pairing-based crypto.

- In particular, the attack has no impact on even small characteristic NIST curves, or basically on any curve used for "traditional" (as opposed to "pairing-based") elliptic curve cryptosystems, including ECDH, ECDSA, ECIES, etc.

- On the other hand, the paper is a huge deal for people interested in the implementation of pairing-based crypto / cryptographic bilinear groups, because small characteristic fields (mainly supersingular curves over GF(3^m)) were the preferred approach for implementation in hardware, and even in software if you wanted symmetric pairings. Joux's original L(1/4) paper meant that people had to take a closer look at the trade-off between characteristic 3 and large characteristic in hardware (and it was also very important as the most significant algorithmic advance on the DLP since GNFS), but it wasn't quite "apocalyptic". This paper, on the other hand, has a quasi-polynomial attack, which means pairing-based crypto in small characteristic is dead (and more generally, symmetric pairings have become very unattractive).

- Whether this affects "real-world crypto" depends on were you set the limits of the real world.　SSL connections and credit cards are unaffected, sure, but there are limited deployments of things like group signatures that have to take a close look at the math used in their implementation.

- The first preprint did appear publicly last summer, so it's true that this is not fresh news to the community, although I think it's great that this result gets some publicity beyond academic circles (and IMHO it fully deserves its best paper award).

Most of the midrange and high-end models at the time did support over 64 MB of RAM (the Centris 650/Quadra 800 supported 136 MB, the Quadra 950 supported 256 MB, etc.). In fact, even the 1987 Macintosh II could be pushed to 68 MB (or 128 MB with a ROM upgrade).

tptacek makes a number of good points but I find it hard to agree with this one:

> there is concern that the NIST curves are backdoored and should be disfavored and replaced with Curve25519 and curves of similar construction.

Of course, "there is concern" is pretty vague, but it should be made clear that such concerns are in the realm of pure speculation at this point. There is simply no known way of constructing a "backdoored" elliptic curve of prime order over a prime field (in particular, the closest thing resembling such a backdoor, namely Teske's key escrow technique based on isogenies from GHS-weak curves, cannot work over a prime field). Scientifically speaking, I don't see more reasons to believe the assertion that "NIST parameters are backdoored because they aren't rigid" than the (equally unfounded) speculation that "Curve25519 may be weak because it has small parameters/a special base field/composite order/etc.".

Moreover, to say that the NSA has backdoored the NIST curve parameters is to assume that they have known, for quite a long time now, a serious weakness affecting a significant fraction of all elliptic curves of prime order over a given base field that has so far escaped the scrutiny of all mathematicians and cryptographers not working for a TLA. Being leaps and bounds ahead of the academic community in an advanced, pure mathematical subject doesn't quite align with what we know about NSA capabilities.

Don't take this the wrong way: there are good reasons to favor Curve25519 and other implementation-friendly elliptic curves (namely, they are faster, and they are fewer ways of shooting yourself in the foot if you implement them), but "NIST curves are backdoored" is not a very serious one.

Says the Guardian[0]: "Tany Lokshina has confirmed that the US embassy called her before the meeting to ask her to pass on to Snowden the message that he was not a whistleblower."

So forget about Wikileaks. It's either Human Rights Watch's Tany Lokshina lying, or the US Ambassador.

[0]: http://www.guardian.co.uk/world/2013/jul/12/edward-snowden-t...

As far as France is concerned, this seems to be an incorrect statement by unnamed Foreign Affairs Ministry officials.

Le Monde reports[0] that government spokeswoman Najat Vallaud-Belkacem says that France "eventually allowed the plane to fly through its airspace", implying that they denied it at first. A more detailed official account of the incident is supposedly forthcoming.

[0] http://www.lemonde.fr/ameriques/article/2013/07/03/une-rumeu...

The signing key for Gmail's certificate is a 1024-bit RSA key. That key size is simply not safe against an attacker like the NSA today, so we may as well assume they have the private key even if Google didn't voluntarily give it to them.

But while the signing key may allow them to impersonate Google in some circumstances, it doesn't really help decrypting passively recorded TLS traffic to the real Google. For that, they would need to break the ECDH key exchange, and if Google uses reasonable elliptic curve parameters, that's presumably much harder than factoring a 1024-bit RSA modulus, at least with known cryptanalytic techniques.

>How are they getting the DH keys without cooperation from at least one of the SSL endpoints involved?

One possibility is to actually compute discrete logarithms.

Does anyone know what elliptic curve parameters Gmail uses for key exchange? If the parameters are large, it is not feasible to break discrete logs using known methods, but while I'm usually wary of claims that the NSA is miles ahead of the academic research community, I could perhaps believe they have faster algorithms for e.g. some NIST curves.