How Diffie-Hellman Fails in Practice

[beero1000]

It is 45 million core-years to pre-compute the values for a 1024 bit prime, using standard theory and hardware. Once that computation is done, any cryptographic protocol that uses the discrete-log problem (DH, PGP, TLS, HTTPS) for that specific prime is cracked.

Another way to say it: if anyone wants to read your (uncompromised) 1024 bit encrypted files, it might cost them months and many millions of dollars, but they could do it.

On top of the 45mil core*years?
I think I can live with that. I mean can make my browser to generate new set of primes for every fake https gmail session and it will cost them millions each time.

No, the 45 million core years is the cost in time and money. The link argues that the cost can be reduced by a few orders of magnitude using specialized hardware, so say half a million core-years. I'd bet that the NSA already has at least one supercomputer with more than a million cores, they only cost $500 mil...

The main compromising vulnerability is that even though many protocols use varying keys, they often use the same primes repeatedly, so the NSA only needs to do this for a few primes to read a large fraction of encrypted internet traffic.

I can see why servers would like to reuse it, but client (desktop) computers can afford to generate new ones each time.

These are the shared primes, not the keys. They must be agreed upon by all parties and announced in public key cryptography.

 

[barbos]

On top of the 45mil core*years?
I think I can live with that. I mean can make my browser to generate new set of primes for every fake https gmail session and it will cost them millions each time.

No, the 45 million core years is the cost in time and money. The link argues that the cost can be reduced by a few orders of magnitude using specialized hardware, so say half a million core-years. I'd bet that the NSA already has at least one supercomputer with more than a million cores, they only cost $500 mil...

Many millions of dollars but only one time is nothing to them.
I want to know how much it costs to crack particular https session after that.

The main compromising vulnerability is that even though many protocols use varying keys, they often use the same primes repeatedly, so the NSA only needs to do this for a few primes to read a large fraction of encrypted internet traffic.

I can see why servers would like to reuse it, but client (desktop) computers can afford to generate new ones each time.

These are the shared primes, not the keys. They must be agreed upon by all parties and announced in public key cryptography.

I understand that. I am just saying that desktops can take that load from the webservers.

 

[NobleSavage]

Is there a standard definition for "core" yet? It's being thrown around more and more as a standard unit of measure.

 

[beero1000]

Is there a standard definition for "core" yet? It's being thrown around more and more as a standard unit of measure.

Nah, I was just being consistent with the OP quote, since it was dealing with back-of-envelope approximations anyway. I don't think there's any reason to standardize cores when we already have flops.

 

[bilby]

There seems to have been a few "codes" that were undecipherable. Egyptian hieroglyphs resisted all attempts to read them until the Rosetta Stone was found that gave the same text in three writing styles, two that had been deciphered and Egyptian hieroglyphics. The Voynich manuscript has baffled the world's best code breakers for a few hundred years so far. But the funny one (to me) is that the Germans during WWII were never able to break an extant language - that used by our "Navajo code talkers".

Well it seems that Voynich has fallen.

https://phys.org/news/2019-05-bristol-academic-voynich-code-century-old.html

(Also the main reason the Germans didn't break Navajo is that they didn't hear it - it was used in the Pacific theatre, against the Japanese).

 

[bilby]

There seems to have been a few "codes" that were undecipherable. Egyptian hieroglyphs resisted all attempts to read them until the Rosetta Stone was found that gave the same text in three writing styles, two that had been deciphered and Egyptian hieroglyphics. The Voynich manuscript has baffled the world's best code breakers for a few hundred years so far. But the funny one (to me) is that the Germans during WWII were never able to break an extant language - that used by our "Navajo code talkers".

Well it seems that Voynich has fallen.

https://phys.org/news/2019-05-bristol-academic-voynich-code-century-old.html

Or perhaps not.

https://arstechnica.com/science/2019/05/no-someone-hasnt-cracked-the-code-of-the-mysterious-voynich-manuscript/

 

[Tigers!]

But the funny one (to me) is that the Germans during WWII were never able to break an extant language - that used by our "Navajo code talkers".

Not that funny. We sent them all to the Pacific to fight the Japanese. We used Comanche code talkers against the Germans. But the operation in Europe was much smaller scale. We never really trusted the Germans not to be able to break the codes, because we'd already used code talkers in WWI, and the Germans remembered, and they sent anthropologists to the U.S. in the 1930s to study American Indian languages.

AHA! Thanks. I always like to learn something especially if it corrects what I incorrectly thought was right.

Churchill was reputed on occasions to have used Hindustani speakers on both ends of some of his conversations during WW2. The odds of the Germans having fluent Hindustani speakers in the right space at the right time was considered very remote. Even if it was listened too and transcribed the odds of it being transcribed correctly were extraordinarily low.

 

[steve_bank]

I have no idea what the NSA does.

I do know that thousands of cheap computers can be built, networked and dedicated to breaking encryption.

In the 80s built a Personal Scientific Computer. A rack of processors and memory boards linked with Ethernet.

I just assume that the govt can if it wants to read Internet encrypted communications.

There is an old saying. When protecting data the goal is to have it remain hidden long enough that revelation does not matter.

There are close to unbreakable text encryption methods. The 'one time pad'. Use of code books with random selection of symbol for symbol. Theoretically no patterns to analyze. Depends on the random number generator.

 

[Gun Nut]

If you really want to send secret messages, then invent your own method. That way anyone trying to break it would have to start from scratch. Just make sure that there are no weaknesses. You might want to also try to break it yourself just to be sure.

That's a terrible idea. Read up on why open-source is more secure than proprietary...
Like Phillips did with the first anti-copy method for audio CDs.... Phillips spent millions of dollars and years researching a means to record music onto a CD that could not be copied by a computer. After a ton of resources were spent, they finnally unveiled their super-secret manufacturing method that protected the intellectual property of all musicians and positioned them to be THE provider of all physical music media!
Within 3 hours of their release of the first "copy-proof" audio CD, their protection was foiled... with a $0.99 Sharpie marker. All you had to do to be able to copy their CDs is darken the edge. That's it. Draw on the CD with a marker and you can copy it.

It takes a village... never forget that.