Bitcoin Forum

The plan was launched in 2004 as a modern-day Manhattan Project. Dubbed the High Productivity Computing Systems program, its goal was to advance computer speed a thousandfold, creating a machine that could execute a quadrillion (1015) operations a second, known as a petaflop—the computer equivalent of breaking the land speed record. And as with the Manhattan Project, the venue chosen for the supercomputing program was the town of Oak Ridge in eastern Tennessee, a rural area where sharp ridges give way to low, scattered hills, and the southwestward-flowing Clinch River bends sharply to the southeast. About 25 miles from Knoxville, it is the “secret city” where uranium- 235 was extracted for the first atomic bomb. A sign near the exit read: what you see here, what you do here, what you hear here, when you leave here, let it stay here. Today, not far from where that sign stood, Oak Ridge is home to the Department of Energy’s Oak Ridge National Laboratory, and it’s engaged in a new secret war. But this time, instead of a bomb of almost unimaginable power, the weapon is a computer of almost unimaginable speed.
 
At the DOE’s unclassified center at Oak Ridge, work progressed at a furious pace, although it was a one-way street when it came to cooperation with the closemouthed people in Building 5300. Nevertheless, the unclassified team had its Cray XT4 supercomputer upgraded to a warehouse-sized XT5. Named Jaguar for its speed, it clocked in at 1.75 petaflops, officially becoming the world’s fastest computer in 2009.
 
Meanwhile, over in Building 5300, the NSA succeeded in building an even faster supercomputer. “They made a big breakthrough,” says another former senior intelligence official, who helped oversee the program. The NSA’s machine was likely similar to the unclassified Jaguar, but it was much faster out of the gate, modified specifically for cryptanalysis and targeted against one or more specific algorithms, like the AES. In other words, they were moving from the research and development phase to actually attacking extremely difficult encryption systems. The code-breaking effort was up and running.
 
The breakthrough was enormous, says the former official, and soon afterward the agency pulled the shade down tight on the project, even within the intelligence community and Congress. “Only the chairman and vice chairman and the two staff directors of each intelligence committee were told about it,” he says. The reason? “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”

http://www.zerohedge.com/news/%E2%80%9Cwe-are-far-turnkey-totalitarian-state-big-brother-goes-live-september-2013

Can we post this article ten more times please?

zerohedge was just highlighting some of the good stuff. its in wired april - cover story i believe.

...or were you saying that because it has been posted a lot already? admittedly, i didn't check before i posted.

the wired article is here:
http://www.wired.com/threatlevel/2012/03/ff_nsadatacenter/all/1

there are already 2 threads regarding same article on Discussion.

searching but not coming up with much. care to link?

https://bitcointalk.org/index.php?topic=69178

... and you get to bitch about it being posted ten more times, ten more times? ... no thanks.

Why don't you put yourself up for moderator if you feel the need to be policeman so badly?

LOL!

At the DOE’s unclassified center at Oak Ridge, work progressed at a furious pace, although it was a one-way street when it came to cooperation with the closemouthed people in Building 5300. Nevertheless, the unclassified team had its Cray XT4 supercomputer upgraded to a warehouse-sized XT5. Named Jaguar for its speed, it clocked in at 1.75 petaflops, officially becoming the world’s fastest computer in 2009.

Meanwhile, over in Building 5300, the NSA succeeded in building an even faster supercomputer. “They made a big breakthrough,” says another former senior intelligence official, who helped oversee the program. The NSA’s machine was likely similar to the unclassified Jaguar, but it was much faster out of the gate, modified specifically for cryptanalysis and targeted against one or more specific algorithms, like the AES. In other words, they were moving from the research and development phase to actually attacking extremely difficult encryption systems. The code-breaking effort was up and running.

The breakthrough was enormous, says the former official, and soon afterward the agency pulled the shade down tight on the project, even within the intelligence community and Congress. “Only the chairman and vice chairman and the two staff directors of each intelligence committee were told about it,” he says. The reason? “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”


So can you hazard an answer if NSA are routinely cracking AES?? ... the point of question before you stuck your oar in and diverted the conversation ....

can't you understand that there is already a thread started on this subject from yesterday?  there was no conversation going on in this thread:

https://bitcointalk.org/index.php?topic=69178.msg806495#msg806495

It was different question, for a different topic ... or didn't you read the forum properly?

The article is long and many faceted. There are several (actually many) topics in there relevant to bitcoin that could be discussed separately .... the other discussion was a lame "gee whiz", "but who cares" meandering thread with no topic in the OP that I could discern.... animated chanesque pictures of blondes to boot.

Thanks for being the concerned bitcoin web citizen though, we are all richer for it!

it wasn't a different question.  the OP already said he was surprised that there was a reference to this article already posted and there is only a quoted passage in the post; no question.

all this is quibbling so why don't we just consolidate all discussions relating to this article in the original thread like we usually do?

1000x wow, so now we need 16 more bits or something to get the same security.

Some botnets have more than petaflop of procesing power and you can rent them for less than 100 bitcoins per 24 hours. Unlike the nuclear bomb that was urgently needed in war, the so called supercomputers are used to pump out the funds from national budget to build impressive but extremely expensive gizmos.

No NSA can break 256bit AES by brute force.

That statement is slightly ambiguous (especially if you have omitted a comma) ... do you think NSA can or cannot break AES?

I agree with the boondoggle aspect of these huge govt. projects. Also the inevitable centralised nature of the resulting installations is cringeworthy.

Looking at the schematics here, it would only take a simple failure or attack on either the chillers (6) or the power substations (7) to render the entire complex useless.


http://www.wired.com/threatlevel/wp-content/gallery/20-04/ff_nsadatacenter2_f.jpg

.... a botnet or bitcoin is mush more resilient in that sense. Now if bitcoin hashing function could be homeomorphic to AES cracking ....

AES might contain yet undisclosed mathematical flaw that renders the encryption next to useless. Actually from all three symmetric ciphers I consider 100% safe (Serpent, Twofish, AES), the AES have the greatest potential to contain undiscovered flaws.

But I'm 99,99999999999999999999999999999999999999999999999999999999% sure that NSA cannot search in reasonable time the entire 256-bit keyspace to rediscover key used for encryption. Or even the 50% of keyspace to get 50% chance of success. The laws of physics and thermodynamics makes this impossible.

I'm 99.lotsofnines% certain that the NSA can't brute force even a 128-bit key.  Assuming they can try 1 trillion keys per second - that's 1 million machines each making 1 million tries per second which is probably a reasonable guess of their abilities - it would still take 2^128 / (1T * seconds_per_year) = 10^16 years.  Take a few zeroes off the end if you want to be really paranoid.

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.

Most likely this new datacenter is for a) breaking weak keys (like if you seed your deterministic wallet from a short passphrase), which isn't really news - everyone already assumes they're able to do that; or b) data mining non-encrypted information, which shouldn't come as any surprise - I'd be shocked if this isn't just an expansion of an existing project, or c) other NSA stuff that doesn't involve brute-forcing 128+ bit keys.

Oh, as for breaking AES by non-brute force:  no, I don't think they can.  AES is pretty good - not the best (Serpent probably had the best overall security of the finalists, but it came in second for performance reasons), but it's still a top-tier algorithm, and it has held up for a decade with no significant full-rounds attacks.  The best so far lets you break AES-128 in 2^126.1 operations.

It's always possible the NSA has something they're not telling us, but in the past they have chosen security over being able to decrypt others' communications:  when DES was adopted they modified it a little to protect against differential cryptanalysis, which was not publicly known at the time.  There's too much to lose by blindly hoping that the Bad Guys won't find the bug - AES is certified to protect Top-Secret information.  I would expect them to start the process for a new algorithm if the existing standard was found insecure.

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.

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.

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 (http://en.wikipedia.org/wiki/Brute_force_attack), 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.

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.

Ships in 4-6 weeks?

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.

Sounds like a perfect government project.

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

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.

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.

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. 

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

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

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.

I didn't say that.


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'?

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.

Physics is not the only problem. Economic motivators may well play a bigger role. Will the budgets for chip R&D always be sufficient to follow Moore's Law? What if there is a prolonged depression, or a materials shortage? Who knows what new exotic semiconductor raw materials will be required in the future.

Will there be adequate demand to finance ever increasingly powerful chips? We are already seeing lower demand for desktop PC's, and a shift to mobile devices with low-power, thermally efficient CPU's. If server farms/supercomputers need more power, they can just keep stacking the latest modular hardware.

You could increase the density of transistors many times, but they simply could not search large enough portion of 256-bit keyspace to recover the encryption key. You absolutely need some mathematical means to attack AES or any other cipher.

And the Microsoft Windows that will be around that time will be slow on that processor.

Moore's law has already survived depression and materials shortages. 

The one trend you site... lower demand for desktops may do it.  Devices like iPads are taking more and more of a share, and custom built high end computers seem to be dwindling outside of specialty things like bitcoin and high end gaming. 

#2 makes no sense. You seem to be implying that Moore's law will double the speed of chips every year (that's off, but close enough if it makes your calc easier), and that every year the budget will double so you can buy twice as many chips. IE, this year you can do X, next year you can do 4X, the year after you can do 16x, etc.

The doubling of budget every year is ridiculous though. If they spend $250M in 2011 to finish this $2B project, will they then spend $500M in 2012? $4B in 2015? $131T in 2030? $6.4x10^38 in 2112? Of course not. If chip prices rise at about the same price as inflation, and you make the assumption that performance follows a version of Moore's law (doubles every 2 years instead of the 1 year you have listed), using standard brute force methods in 100 years you would be 2^50 faster than today, not 4^100 (2^200).

Don't forget that the algorithms have historically improved at a pace comparable to moore's law, at least for the cases of factoring large numbers and discrete logarithms.       

Mmmm, Moore's Law hasn't met a full-blown depression yet. Not depressed consumer syndrome, I mean a no jobs/ no money/gas & food shortage scenario aka 1930's level.

Or hey, what about a world war? That would certainly put a damper on R&D.

What materials shortage has occurred in the past?

Not sure if serious...

Exact opposite actually.

More of a redirection ... although more focussed and done at cheaper rates (military pay).

It would put a damper on R&D for increasing chip densities. Notice i said a WORLD war? Not USA takeover of camel jockey capital.

That isn't supported by history. In the past, increased war spending has meant floods of war-money into both manufacturing and also R&D efforts for things the military wants. In an increasingly information-centric world, computing power is a resource wielded by powerful nations just as much as missiles and armies are.

To support rjk, WWII spawned a whole host of computers to do everything from breaking German codes to designing better bomber targeting scopes.

What a shitload of fearmongering.

The dilemma with rumors like this is, if they are true, is that once the agency starts using it on large scale people will notice, or it will leak, and people switch to different encryption schemes. It is at most a temporary advantage. Attained at high cost and very easy to lose. So if they have found a ways to crack AES256/RSA/ECC it will be a well-kept secret and only used for really high-profile cases such as government-to-government espionage. They certainly won't put it in a press release.

During world war 1 and 2 research skyrocketed.
War is a great motivator for R&D

Unless everyone dies.

Solid-state transistors were not manufactured before 1948. So much for chip density R&D. :P


Your position isn't supported by history either, if you're arguing for Moore's Law. We have never seen a world war while Moore's Law was in effect. Of course I agree that the military needs better tech. But they won't necessarily see an immediate benefit to increased transistor count during a war. Its a long-term thing. R&D will be focused on very specialized things, and re-directed from where the money was going before. Shifted priorities is the key phrase.

Although I disagree with foggyb larger view and I think Moore's law (or more correctly we are interested in Koomey's law as it relates to encryption) is good for at least three or four decades and possibly a century he likely is right about war.

Since WWII at least in the US (and I would imagine around the world) military tactics have changed.  The goal is no longer to secure territory, land, strategic points ("take the hill") it is to utterly dominate the enemy and destroy both their ability to wage war (kill troops instead of taking land) and their ability to finance the war.

WWII defenses and offenses were fairly matched.  B-52 bombers for example could level a factory but they often missed and routinely bombers would be destroyed enroute.  Since WWII the destructive capacity of offensive weapons has improved by magnitudes but defensive systems haven't.

In a modern global war of full spectrum dominance you simply couldn't defend your industrial assets.  Stealth bombers, high speed drones, ground hugging cruise missiles, bunker buster ordinances, ballistic missiles, long range pinpoint accurate field artillery, etc would rapidly overwhelm any defensive systems.

How many cruise missiles can a Intel FAB take before it is a $20B pile of rubble?  How many stealth bomber runs can a nuclear power plant take before it is molten radioactive slag and there is no power to run your $20B Silicon chip FAB?

The most effective way to "win" is destroy the enemies ability to wage war so both (all?) sides will.

The good news is all the nations capable of waging such a war have nuclear weapons and unstoppable delivery systems.  Any such war would inevitably escalate to nuclear force.  Either pre-emptively to "end the war before it starts" or defensively as one side starts to lose and sees nuclear weapons as the only way to regain a fighting chance.  Nuclear escalation wouldn't stop (when 1 million of your citizens die as a leader you will strike back with similar force).  Limited "strategic exchanges" would escalate to "counterforce" (google it) strikes and eventually full scale "countervalue" strikes. 

So yes when 90%+ of human race is wiped out and technological progress is pushed backwards 200 or so years as humans cling to a shattered and poisoned planet then foggy is likely right Moore's law won't continue and your encrypted file is likely safe.


Still now that we are WAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAYYYYYYYYYYYYYYYYYYYYYY off topic.

Hoping for a nuclear war (or any other improbable scenario) to keep your encrypted secrets safe really doesn't have much value.   It would be like not getting fire insurance, counting on the fact that the day your house catches fire it will be raining ... hard. :)

Any estimate for the long term strength of a cipher should be based on the most plausible and likely scenario.  That scenario is that Moore's law (or more accurately Koomey's law) will continue for next 30+ years.  So if your secret must remain protected even 30 year from now you should assume computers will eventually have 1 million times as much performance per watt (30 years at doubling ever 18 months).  When choosing a cipher strength that should be your target.

Now if your assumption is WRONG well most likely it is wrong on the short side (nuclear war, lack of demand for faster chips, technological brick wall) and your file is still safe.  On the other hand if your assume Moore's law won't hold and it does well you are fracked.

It is all about being conservative.

No one is hoping for a nuclear war (well....except maybe Donald Rumsfeld et al.). But war is an inevitable scenario, only one of several possible scenarios that would 'encourage' people to be less fascinated with decryption and more focused on say, putting food on the table, or otherwise perpetuating the human race.

Right but the point being that is an unlikely scenario.

Which is why I said you are RIGHT but it is irrelevant.  The most likely scenario is Moore's law hold, there is no global war wiping out technological progress and your encryption must be able to handle 1 million fold increase in computing power over the next three decades.

Agreed, it is irrelevant if people use strong encryption.

"The most likely scenario is Moore's law hold".

So there's at least a 51% chance that Moore's Law will hold? How did you calculate that? But I'm off-topic.  ;)

[EDIT]: Another nail in the coffin - The High Cost of Upholding Moore's Law (http://www.technologyreview.com/computing/25141/)

https://www.technologyreview.com/files/40001/chart72x220.jpg

They don't need to break AES/twofish/serpent because almost always it is implemented insecurely, allowing for side channel attacks and other methods to get at the keys. At least according to Bruce Schneier