NSA Still Ahead In Crypto, But Not By Much

Hugh Pickens writes "Network World summarizes an RSA Conference panel discussion in which former NSA technical director Brian Snow said that cryptographers for the NSA have been losing ground to their counterparts in universities and commercial security vendors for 20 years, but still maintain the upper hand in the sophistication of their crypto schemes and in their ability to decrypt. 'I do believe NSA is still ahead, but not by much — a handful of years,' says Snow. 'I think we've got the edge still.' Snow added that that in the 1980s there was a huge gap between what the NSA could do and what commercial encryption technology was capable of. 'Now we are very close together and moving very slowly forward in a mature field.' The NSA has one key advantage (besides their deep staff of Ph.D. mathematicians and other cryptographic experts who work on securing traffic and breaking codes): 'We cheat. We get to read what [academics] publish. We do not publish what we research,' he said. Snow's claim of NSA superiority seemed to rankle some members on the panel. Adi Shamir, the "S" in the RSA encryption algorithm, said that when the titles of papers in NSA technical journals were declassified up to 1983, none of them included public key encryption; 'That demonstrates that NSA was behind,' said Shamir. Snow replied that when technologies are developed separately in parallel, the developers don't necessarily use the same terms for them."

Comments

they aren't very well going to admit defeat.

[timmarhy]

what else would you expect from a public servant. he won't admit the private sector has them beat because it'd be the end of his job.

Re:they aren't very well going to admit defeat.

[bytesex]

If you're never going to be able to decrypt the data, then you might as well cat /dev/random > /dev/sda. Because it's indistinguishable from random chaos.

Re:they aren't very well going to admit defeat.

[xtracto]

You are assuming that whoever wants to break the encryption is doing a brute force attack.

The classical

encryption breaking methods are mainly based on frequency and statistics. I am sure nowadays the NSA and other entities in charge of breaking encrypted content have more sophisticated methods.

Re:they aren't very well going to admit defeat.

[CODiNE]

That's 1.15x10^77 possibilities.

Are you aware that randomly generating a specific protein is much more difficult than that? I've heard a number around 1 in 10^113. That would be just ONE of the proteins we need for life.

So. Either it needs to be rethought what is actually numerically possible, or that the genetic make-up of life was guided by chance.

Re:they aren't very well going to admit defeat.

[vlm]

Currently the best theories we got suggests there's a lower entropy limit of kT*ln 2 (the Von Neumann-Landauer limit) per operation, which is on the order of 10^-23 joule. The energy of the sun via E=mc^2 is on the order of 10^47 joule. So at most you can do is 10^70 operations but 2^256 = ~10^77. In other words you can't get through the keyspace before you run out of energy, even taking ideal assumptions.

Well, if your strategy is guess and check, sure, OK. Wouldn't this plan be a hell of a lot cheaper:

Estimate the total number of operations a genius level human brain can accomplish per second. I will be wildly optimistic and give it 10^3. Lets assume all thought is directed toward crypto and no daydreaming about the young lady working in accounting, or arguing about which was better, Kirk or Picard.

Estimate the age of the NSA. Wikipedia claims formed in 1952 but theres plenty of cloak and dagger stuff going on before, so we'll round it to 10^3 years

Estimate the total number of geniuses the NSA has hired over the years. The holy font of all wisdom, wikipedia, claims the number of employees is classified. However, they claim there's 18000 parking spaces at HQ. What the hell they do with 18K people is a mystery to me. My guess is theres 17990 supervisors, managers, directors, HR personnel, diversity directors, marketing personnel, and other executives and about 10 guys with pocket protectors doing all the work, in between their slashdot breaks. But lets say on a very long term average they have 10^5 geniuses working at any given instant.

Lets further assume they never eat, sleep, have sex (duh, they're math majors). That gives us 31 million seconds per year. Well, we'll round that down for time to watch star trek reruns, eat pizza rolls, and read slashdot, so call it 10^7 seconds per year.

So, you need to do about 10^3 * 10^3 * 10*5 * 10^7 = about 10^18 crypto related thought operations over the total lifetime of the NSA.

In conclusion, you need to run WELL under 10^18 thought operations to figure out the back door they put into your encryption algorithm and/or reverse engineer their top secret decryption technology. A wee bit less than your 10^70 operations required to brute force one message. Plus, when you crack the entire algorithm, you've cracked all messages ever sent with it, not just one message.

NSA didn't know about public key crypto?

[jpmorgan]

I don't think so... public key cryptography was discovered by the GCHQ at least a decade before it was discovered in the public sphere: http://cryptome.org/ukpk-alt.htm

Re:Sure

[Anonymous Coward]

Yeah, but the way most intelligence services work is that it's not like the employees show up at the NSA building every day and sit in a cubicle doing encryption research. At least with the CIA and DOD they just put civilian academic researchers on the payroll and get "first dibs" on new stuff and also get to direct their research. The CIA does this with journalists too. They still work at the NY Times etc. but the CIA sees all their information first and decides what will get printed and what will stay private.

Re:Crypto is only the Beginning

[bytesex]

Nah. The money is now in electromagnetic remote sensing; reading your screen and listening to your keyboard from a mile away. That, and psy-ops. Humans still control keys. Humans always make at least one mistake. Google's mail accounts were cracked because their subjects could be coaxed to visit malicious websites, after all.

Re:Whatever!

[chuckymonkey]

Let me tell you from firsthand experience. You cannot even fathom the awesomeness that goes on inside the cube unless you work there. It is not like Hollywood portrays it, but there is a whole lot of cool going on in there. That is why people work for the NSA. Now, I have philosophical disagreements with how the NSA ran business during the Bush years and I left that industry for aerospace. That being said if any of my former colleagues tell me that things have changed I think that I would go back.