Comments

Johannes Berg • November 6, 2013 6:57 AM

“With the clock ticking that fast, ECC may be left as the only reasonable alternative.”

I hear there’s some interesting work now on lattice-based cryptography, does anyone know any good explanations of that?

Brock • November 6, 2013 7:53 AM

Did we have any insight from the Snowden papers if the NSA has identified any vulnerabilities in this?

Brian • November 6, 2013 8:29 AM

“Elliptic curve cryptography (ECC) is one of the most powerful but least understood types of cryptography in wide use today.
…
If you’re worried about ensuring the highest level of security while maintaining performance, ECC makes sense to adopt.”

Funny, but I feel like, “least understood” + “highest level of security” = contradiction.

Bruce Schneier • November 6, 2013 8:35 AM

“Did we have any insight from the Snowden papers if the NSA has identified any vulnerabilities in this?”

We do not — at least not yet — but I strongly believe that the NSA has a significant advantage in breaking ECC. This doesn’t mean it’s bad, but I think we need to 1) make sure we know where our curves come from, and 2) build in a hefty security margin.

Rich • November 6, 2013 8:58 AM

Did we have any insight from the Snowden papers if the NSA has identified any vulnerabilities in this?

I’m guessing people with Snowden’s (former) access at NSA wouldn’t hear about that until there was a tool to decrypt ECC automatically.

Douglas Knight • November 6, 2013 9:20 AM

Bruce, why do you believe NSA has advantages in breaking ECC that they did not design?

Scott • November 6, 2013 9:48 AM

@Douglas Knight

The biggest red flag is that we don’t know where the constants used to generate the curves came from. Given the NSAs influence, they could have easily influenced them. The constants are hashed, so I find it unlikely that they were computed, but it is possible that the NSA knows of an attack on some curves that occur with a brute forcible probability.

I’ve also never gotten over the fact that they chose 521 bit prime curves instead of 512 bit prime curves (where every other prime curve is a multiple of 32 or (in one case) 16) the only reason I can think of for that is that weak 512 bit curves are significantly less likely than for other prime curves.

Brian M. • November 6, 2013 10:17 AM

@Douglas Knight:

One point that has been in the news recently is the Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG). This is a random number generator standardized by the National Institute of Standards and Technology (NIST) and promoted by the NSA. Dual_EC_DRBG generates random-looking numbers using the mathematics of elliptic curves. The algorithm itself involves taking points on a curve and repeatedly performing an elliptic curve “dot” operation. After publication, it was reported that it could have been designed with a backdoor, meaning that the sequence of numbers returned could be fully predicted by someone with the right secret number.

The NSA has a legion of mathematicians and better-than-Google computing power. While the “backdoor” might not result in a “fully predicted” sequence, it could narrow the possibilities significantly, such that what should be a steel vault is only a cardboard box.

Elliptic curve cryptography is supposed to reduce processor effort and give us higher security. While in the past a change from the NSA resulted in the strengthening an algorithm (and it took seven years for people to figure out that’s what the change was for), with the Snowden leaks the NSA’s motives have become debatable.

“Trust us, we’re your government,” just doesn’t reassure many people.

Douglas Knight • November 6, 2013 10:19 AM

Scott, read Bruce’s comment. He has two points (1) and (2). Point (1) says to worry about design of curves. But (2) is that he worries even about NSA breaking ECC even when it had no role in design, like curve25519.

Some_Guy_In_A_Diner • November 6, 2013 10:22 AM

Hey, I have a great idea. Why don’t we increase ssl cipher strength by moving from SSL_RSA_WITH_RC4_128_SHA to DHE-RSA-AES256-SHA256 or ECDHE-RSA-AES128-SHA256 or (insert your favorite cipher here)?

ECC may have theoretical problems involving NSA/NIST curves. There are some “safer” curves out there. Until then lets crank it up to 11. I’m still leaning RSA until we get “safer” curves are widely adopted.

albatross • November 6, 2013 10:22 AM

The end of the article comment about integer crypto maybe being broken any day now is sensationalistic BS, as far as I can tell.

Douglas Knight • November 6, 2013 10:30 AM

Some_Guy_In_A_Diner, are you condemning schneier.com’s choice of RC4?

But you mention ECDHE-RSA-AES128-SHA256. That is ECC. That’s why the first two letters are the same.

Some_Guy_In_A_Diner • November 6, 2013 10:35 AM

@Doug

Yes, I know that. I’m thinking there may be cases that you still would want to use ECC.

Some_Guy_In_A_Diner • November 6, 2013 10:38 AM

Actually, disregard the cipher choices list in my post. I’m still researching and testing now.

Maglio • November 6, 2013 12:10 PM

@Bruce Schneier:
…I strongly believe that the NSA has a significant advantage in breaking ECC.

@Douglas Knight:
[Bruce] worries even about NSA breaking ECC even when it had no role in design, like curve25519.

Does this mean that NSA has made sufficient advances to use math to break the ciphers?

Does it also mean that there is thus less reason to trust the math?

Bryan • November 6, 2013 3:38 PM

A full DarkNet is needed. Email, is just the start.

BTW: The DarkMail Kickstarter already has $54k pledged of $197k after only a couple days. 🙂

Perseid • November 6, 2013 6:21 PM

RSA and Diffie-Hellman were so powerful because they came with rigorous security proofs. The authors proved that breaking the system is equivalent to solving a mathematical problem that is thought to be difficult.

That is just plain wrong? We still don’t have a proof in a reasonable setting that breaking RSA is as difficult as factoring, or have I missed something? And the Diffie-Hellman hypothesis has its name for a reason, instead of just being the discrete logarithm problem. Even stuff like the probabilistic signature scheme came years after the original RSA.

ted • November 6, 2013 8:03 PM

“A growing number of sites use ECC to provide perfect forward secrecy, which is essential for online privacy.”

Is there a list of financial institutions using ECC and/or PFS? My bank and CC provider are not.

Jonathan Wilson • November 6, 2013 8:33 PM

According to one online SSL checker, my bank only supports TLS 1.0 and SSL 3.
It also says “RC4 Yes NOT DESIRABLE” and “Forward Secrecy No NOT DESIRABLE”

That said, my bank did recently roll out a new online baking upgrade with better password requirements (not only do they actually treat upper and lower case letters differently but they actually require upper case, lower case AND numbers in the password.

Perseid • November 7, 2013 1:21 AM

@Jeff Epler:
I was citing a passage from the Ars Technica article. The reason it’s typically thought to be same is probably that the best known attack to RSA is factoring the modulus and to ElGamal is calculating the discrete logarithm.

Mike the goat • November 7, 2013 5:12 AM

I have nothing but rumors and whispers to base my distrust of EC crypto on, but nonetheless I have no plans to shift away from “conventional” asymmetric crypto (whether tied to integer factorization like RSA or the discrete logarithm problem like ElGamal and Cramer-Shoup) any time soon.

That said I am considering using ECDSA (or the ec based digital SIG system Nick spoke of on Friday) for my blogsig project. This is due to the need to fit both a signature and metadata into an 80 character (a single standard length line) signature. Given I have stated that non-repudiation and absolute certainty are not part of the brief I think it is a reasonable enough choice. A blogsig is designed only to certify that there is a high (not absolute or legally provable) probability the signed post was composed by the keyholder and has not been modified (except for reformatting, a concession we must make with blogs).

Autolykos • November 7, 2013 6:26 AM

@Scott:

I’ve also never gotten over the fact that they chose 521 bit prime curves instead of 512 bit prime curves (where every other prime curve is a multiple of 32 or (in one case) 16) the only reason I can think of for that is that weak 512 bit curves are significantly less likely than for other prime curves.

I’d rather expect it the other way round (but that’s based on nothing but intuition; I think round numbers are more likely to lead to vulnerabilities). Remember that weakening crypto isn’t the NSA’s only interest; they want codes in use that
a) they can break if needed
b) nobody else can break
So they may well have fixed an obvious (to them) vulnerability they expected to become public knowledge soon, like they did with DES. That doesn’t mean they didn’t introduce another, less obvious, vulnerability…

Wm • November 7, 2013 7:00 AM

Title: ‘A (relatively easy to understand) primer on elliptic curve cryptography’

Vertigo! Vertigo!

Adam • November 8, 2013 12:13 PM

Pretty good indeed. However the keys for the ‘toy RSA algorithm’ are poorly chosen. The cypher can be decoded with key 29 as well as 5 and 17. In this case PUB == PRIV. OOOPS.
Perhaps better key selection would be MAX: 55, PUB: 7, PRIV: 3.
This again shows how easy it is to weaken the system by mistake in implementation (unless some three letter agency was selecting the particular coefficients ;-).

Mike Amling • November 8, 2013 2:32 PM

@Adam:

Yeah, I noticed that, too. I daresay the idea that the RSA private exponent must be an inverse of the public exponent modulo phi(pq) is the most enduring myth in all cryptography. Of course the truth is that the private exponent must be an inverse of the public exponent modulo lambda(pq).

MarkH • November 9, 2013 5:56 PM

@Mike Amling:

I was about to offer a small correction — that the idea is not strictly a myth — but I looked at US patent 4405829 A filed in 1977, and it does indeed specify that the decryption exponent be computed as the inverse of encryption exponent mod lcm(p-1, q-1), which is identical to lambda(p*q) [also known as the Carmichael function]. So I’m in your debt — I was not aware that RSA was originally specified that way!

That being said, computing the decryption exponent by the usual weaker criterion of inverse mod phi(p*q) is sufficient to guarantee the property of completeness; and further, to my knowledge, the potential non-uniqueness of the decryption exponent d does not give rise to any practical attack.

A purely academic question would be the historical inquiry into how phi came to be substituted for lamdba in the many textbooks, websites and other presentations.

In practice, security applications of RSA choose one exponent to be small (that is, representable in a number of bits far less than the length of the modulus n=p*q). With this constraint, the embarrassing collision e=d is not possible.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.