the ability to crack current public encryption.

[proudhon]

[1713549660]

1713549660

[1713549660]

1713549660

[1713549660]

1713549660

[1713549660]

1713549660

[1713549660]

1713549660

[Etlase2]

The only reason you need better than 128-bit is if quantum crypto becomes available, AND can perform Shor's Algorithm fast (like, 1 billion ops per second).  In that case it could crack 128-bit in a few hundred years.  If that scares you, use 256-bit which will simply never be brute-forced.

I don't think you need 1 billion ops to use shor's algorithm. I am not that well-versed in this stuff, but my understanding is that Shor's can be used to break the "hard problems" of the discrete logarithm and such rather easily with a sufficient amount of qubits. This seriously affects public key cryptography (in reference to the thread title and the worry as it applies to bitcoin), but not AES and SHA and so on other than making it easier. Either way, it is still probably useless to build a bigger and badder ass computer when the keys are 80+ bits of protection at this point. But historical stuff, who knows.

[Revalin]

Sorry, it's Grover's algorithm, not Shor's, that can be used to break AES.  With Grover's, breaking n-bit symmetric crypto takes 2^(n/2) operations, one "operation" being a full run of the algorithm.  In other words, your key length is halved.

If you are able to do 1 billion full-grover-runs per second it would take about 500 years to break AES-128.

[kloinko1n]

No NSA can break 256bit AES by brute force.

How about cracking your encrypted e-mail message 100 years from now? Assume
1. Moore's law (doubling speed every year) ==> 2^100 times faster in 100 years.
2. Yearly doubling budget ==> another 2^100 times faster in 100 years.
3. Quantum computer ==> X * faster ?

For instance, only considering 1. & 2., breaking AES 128, assuming a speed as mentioned here, then 100 years from now the AES 128 would be cracked within 1.5 femtosecond (2^128 year)/(4^100).
AES 256 would take 'slightly' longer: still 10^16 years, so AES 256 still looks safe for me to use.

[DeathAndTaxes]

No NSA can break 256bit AES by brute force.

How about cracking your encrypted e-mail message 100 years from now? Assume
1. Moore's law (doubling speed every year) ==> 2^100 times faster in 100 years.
2. Yearly doubling budget ==> another 2^100 times faster in 100 years.
3. Quantum computer ==> X * faster ?

For instance, only considering 1. & 2., breaking AES 128, assuming a speed as mentioned here, then 100 years from now the AES 128 would be cracked within 1.5 femtosecond (2^128 year)/(4^100).
AES 256 would take 'slightly' longer: still 10^16 years, so AES 256 still looks safe for me to use.

Well this brings up a good point that when using encryption one must be sure the data will remain protected for as long as is necessary.  For example your wallet only needs to be encrypted long enough for you to transfer funds.  Details of a crime would need to remain encrypted long enough for statute of limitations to expire.  Military secrets would need to remain encrypted long enough for them to no longer have value.  This is why TOP SECRET information is encrypted at a higher strength than SECRET.  Neither can be decrypted today but those SECRET docs if stolen "may" be brute forced in a couple centuries.

If you don't want the attacker to break something even a couple centuries from now you should size your encryption appropriately.

[Hawkix]

Spreading a FUD about "we can read your communication, we can decrypt your data". That's the goal of the message.

They simply want to scan all e-mail and web traffic and build a semantic graphs to get a clue whats happening on the Internet. Cool project, but no cracking of ciphers, IMHO.

[kloinko1n]

Spreading a FUD about "we can read your communication, we can decrypt your data". That's the goal of the message.

They simply want to scan all e-mail and web traffic and build a semantic graphs to get a clue whats happening on the Internet. Cool project, but no cracking of ciphers, IMHO.

I'm not sure. If they get enough messages from you which are encrypted with the same key, they might be able to guess the key much faster.

[DeathAndTaxes]

Spreading a FUD about "we can read your communication, we can decrypt your data". That's the goal of the message.

They simply want to scan all e-mail and web traffic and build a semantic graphs to get a clue whats happening on the Internet. Cool project, but no cracking of ciphers, IMHO.

I'm not sure. If they get enough messages from you which are encrypted with the same key, they might be able to guess the key much faster.

If by "enough" you mean a couple quadrillion a year for the next century and you are stupid enough not to use salt then they likely could brute force the key "faster".  As in "only" a century not a million years.

Strong well executed encryption with sufficient key strength can't be brute forced.  Not by the NSA datacenter, not by a plentary sized supercomputer.  Now they can brute force a lot of other things like poorly constructed passphrases, weak encryption, OS which leave plaintext fragments lying around, the weak passwords in a server password list.

[Tomatocage]

Ships in 4-6 weeks?

[BubbleBoy]

In practical terms, NSA is more interested in data-mining than encryption. The huge datacenters are most likely running voice recognition and text classification algorithms, searching for things like: bomb, nuclear, enrichment, anthrax, jews, intifada, jihad etc. (hehe, a huge false positive there...).

If they are doing large scale crypto cracking, they are most likely concentrating on attacking key distribution, public key and key derivation algorithms. They are most likely not brute-forcing AES, that would a stupid waste of taxpayers money.

[rjk]

that would a stupid waste of taxpayers money.

Sounds like a perfect government project.

[foggyb]

No NSA can break 256bit AES by brute force.

How about cracking your encrypted e-mail message 100 years from now? Assume
1. Moore's law (doubling speed every year) ==> 2^100 times faster in 100 years.
2. Yearly doubling budget ==> another 2^100 times faster in 100 years.
3. Quantum computer ==> X * faster ?

Moore's Law (transistor count increase in same surface area, NOT computing power) MUST be broken. The laws of physics guarantee it. To keep up with Moore's Law, a 1-billion transistor count must increase to 1 trillion in just 10 cycles (15 years), and 10^15th transistors (1 billion times greater) in 30 cycles (45 years).

[BubbleBoy]

Well, there are 10^23 atoms per cubic cm of silicon. If you were God, how many atoms would you need to make a transistor and the adjacent insulation and electric connections ? Let's say ten thousand, add or take another zero. So an absolute density limit is on the order of 10^19 transistors per cubic cm. That still leaves enormous headroom for Moore's law to unfold, what we are hitting are technological limits of the photolithographic chip fabrication process, not physical limits.

[DeathAndTaxes]

No NSA can break 256bit AES by brute force.

How about cracking your encrypted e-mail message 100 years from now? Assume
1. Moore's law (doubling speed every year) ==> 2^100 times faster in 100 years.
2. Yearly doubling budget ==> another 2^100 times faster in 100 years.
3. Quantum computer ==> X * faster ?

Moore's Law (transistor count increase in same surface area, NOT computing power) MUST be broken. The laws of physics guarantee it. To keep up with Moore's Law, a 1-billion transistor count must increase to 1 trillion in just 10 cycles (15 years), and 10^15th transistors (1 billion times greater) in 30 cycles (45 years).

By your logic current chips are "impossible".  Transistor density has increased by a factor of ~1 billion over the prior 40 years.

Note Moore's law holds that cost effective transistor density will double every 2 years.  Not every 1.5 years ad indicated in your post and not every 1 year as indicated in the prior one.

[Littleshop]

Moore's Law (transistor count increase in same surface area, NOT computing power) MUST be broken. The laws of physics guarantee it. To keep up with Moore's Law, a 1-billion transistor count must increase to 1 trillion in just 10 cycles (15 years), and 10^15th transistors (1 billion times greater) in 30 cycles (45 years).

That is not Moore's Law, it is close though.  It is the doubling of the number of transistors PER CHIP not per surface area.  Die sizes have grown and 3d stacking is also happening.  Since Moore's law is not specific, even stacked dies (like Apple uses) can be called a single chip.  It can continue.  Maybe not for 45 years, but for 15 yes.  

While the link below is not truly Moore's law, it is on topic here:

http://en.wikipedia.org/wiki/File:PPTMooresLawai.jpg

I you put GPU computing on this map, it would arch up at an even faster rate. 

[marcus_of_augustus]

I like the way this thread is trending, some real guestimates to the NSA abilities ... (animated blonde gifs anybody?)

[foggyb]

By your logic current chips are "impossible".  Transistor density has increased by a factor of ~1 billion over the prior 40 years.

Note Moore's law holds that cost effective transistor density will double every 2 years.  Not every 1.5 years ad indicated in your post and not every 1 year as indicated in the prior one.

Your logic doesn't follow. You argue that Moore's Law will continue because the future will be like the past. That is flawed logic. If the future is like the past for Moore's Law, you should expect the number of transistors on a chip to go to zero, because that's where we started. Infinite doubling of transistor density is a foolish thing to assume.

Wikipedia says it's "approximately two years".

[DeathAndTaxes]

Moore's law won't continue forever but certainly another 1 million fold increase is possible.

You were just pointing out that 1 million fold increase makes it "impossible".  Of course someone in 1970 could have said the same thing.

A 4040 CPU has 2700 transistors.  To maintain this doubling every 18 months would require 2.7 BILLLIIIIIOOOOONN gates by 2010.  Impossible I say.

[foggyb]

Moore's law won't continue forever but certainly another 1 million fold increase is possible.

You were just pointing out that 1 million fold increase makes it "impossible".  Of course someone in 1970 could have said the same thing.

I didn't say that.

A 4040 CPU has 2700 transistors.  To maintain this doubling every 18 months would require 2.7 BILLLIIIIIOOOOONN gates by 2010.  Impossible I say.

You wake up every morning. That must mean you will wake up every morning for AT LEAST 150 more years. Right?

The US dollar has been devalued approximately 95% in about a century. Will it continue devaluing into infinity, because after all, 'the future is like the past'?

[DeathAndTaxes]

One last time foggyb.  NOBODY SAID FOREVER.  NOBODY.  NOT ONE PERSON IN THE ENTIRE THREAD.

It is my belief (and the belief of others) that we will continue to double transistor count for many decades, likely a century.  A million fold increase in transistor density is certainly possible.  Maybe it will never be economical but it is possible.

Silicon atom is 0.117nm we are working at a feature size of 32nm.  Roughly 247 silicon atoms.  There are significant challenges as we get smaller but there are ways to increase density without even getting smaller.

One option is to turn the gates vertically.  One can achieve (theoretically) a 9 fold density increase by building gates vertcially instead of horizontally.  Another options to to build layers of circuits.  Densities a hundred times higher are potentially possible.  Lastly one can move to graphene based chips which has significantly better semiconductor properties.  Intel has made stable test circuits at <1 nm.

We are at 32nm now.  Move down to 1nm over the next three decade and that is 10 doublings of density.  Along the way turn gates "sideways" and build chips with 100 layers and you got your 1 million fold transistor density.

Of course that ignores the reality that in the context it was used we are more interested in Koomey's law (performance per watt).  Moving to graphene gives us a significant boost, improved instruction sets can provide another larger boost, and we may even go sub 1nm feature size so 30 years from now it is certainly possible to have a 4 million+ multiple in computing performance density.

I get you disagree but so did a lot of people in 1970s.  We will see in 30 years until then I think we are done.