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.

[zappepcs]

It occurs to me to think that real encryption is not beatable, but workable encryption is. The problem is not who has the best or admits to not having it, it's who has best real encryption that is workable between arbitrary peers. I can easily encrypt a drive that you will NEVER decrypt, but then neither will I be able to. It's the secrecy of the key that is the quest, not the encryption particularly. Hiding the key when it is shared publicly is a problem, will always be a problem, and the race is not necessarily one brain trust against another for the best hiding technique, but rather a race to figure out the best way to hide it for a reasonable amount of time from the most people. The fastest car on the planet is not declared the Indy500 winner, only the car that conforms to the rules of the race is. This race is not winable in the long term, and only valid as a race in the very short term. Don't count on your encrypted hard drive to protect your data from everyone, for all time. That's simply not going to happen.

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

[Anonymous Coward]

Yes, really and truly, never in all time.

A 256 bit key has 2^256 possibilities. That's 1.15x10^77 possibilities. If you can try 10 million keys in a second, then you "only" need 1.15x10^70th seconds. If you can multiply that speed by a factor of a thousand, then you "only" need 1.15x10^67th seconds. That's 3.67x10^59th years. The universe is only 1.3x10^10 years old.

So never is more than fair. You would literally have to generate universes to generate universes to decrypt via brute force. By our current understanding of reality, impossible is correct, and anything shy of that is literally science ficition.

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

[Holmwood]

Except he's (more or less) right. James Ellis, at GCHQ (roughly the UK equivalent of NSA) had developed the basics of public key cryptography by the end of 1969. This was about 6 years ahead of Diffie Hellman and Merkle. In 1973, a GCHQ cryptographer, Clifford Cocks, realized that one-way functions would be an elegant way of achieving Ellis' insight. See http://cryptome.org/ukpk-alt.htm for example. This was some years ahead of RSA.

GCHQ and the NSA definitely would have exchanged this information. It's also quite possible that the US made some of these breakthroughs even earlier than the British; I've not paid much attention to anything NSA-related that has declassified in the last 5+ years.

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

[JasterBobaMereel]

Public key encryption, that would be the crypto system invented at GCHQ in the UK by public servants .... but not published and then re-invented (independently) by RSA 6-7 years later ...

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

[Ed Avis]

You would literally have to generate universes

Isn't that what quantum computing does?

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.

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

[Agripa]

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.

But that is randomly generating a specific protein without working from an earlier protein. Asimov called that the hemoglobin number and used it as an example of why evolution could not work using blind chance. Hemoglobin is just part of a family of proteins called globins and the actual differences among them are relatively small. The evolution of hemoglobin did not happen by chance all in one step but by accumulating change via many much smaller steps from an existing protein.

Strong cryptographic algorithms are specifically designed to be resistant to the type of analysis which would allow you to derive parts of the key until you have the whole thing. Either you have it all, or you have nothing. Evolution of proteins does not work that way.

Their latest decoded message:

[WegianWarrior]

Be sure to drink your Ovaltine.

Whatever!

[martin-boundary]

"We know Saddam has WMD, but we can't show you what we know because it's secret!". Everybody knows how that argument went in Iraq.

I'm with Shamir, the only correct response here is: "Yeah, right, whatever", not "OMGOMGOMG, the NSA cAn readz my stuffz!!1".

Frankly, I don't see how any mathematician would want to waste his talent working for the NSA.

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.

Re:Whatever!

[jpmorgan]

Academia is not the only profession that provides job satisfaction and a sense of fulfillment. Guess what, 99.9% of the world's population lives a happy life without ever publishing anything.

Re:Whatever!

[Sir_Lewk]

Who says the best always have to get their kicks off with public masturbation? While they may never be able to publish, it is also quite likely they will be exposed to concepts and ideas they never would have had the chance to be exposed to otherwise. I'm sure a very large percentage of these sorts of people are driven by a desire to self-improve.

Re:Whatever!

[Bakkster]

lives may be saved by your hard work.

Considering the way the NSA has behaved in the last 9 years

You mean, considering the reports we have heard. There's a pretty obvious selection bias, in that only the illegal activities (which there certainly are, sanctioned or otherwise) will be notable enough to publish and publicize. I highly doubt that illegal activities accounted for more than 1% of work performed by the NSA (again, including both sanctioned and unsanctioned activities), let alone 51% for cryptologic work to be 'more likely' to be used illegaly.

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

Crypto is only the Beginning

[introspekt.i]

Crypto's not the weak link in security anymore, nor has it been for a long time. I think the real security money now is in automated (or proven) software verification and model checking. Private industry is only beginning to understand this, and as a whole, probably will not employ it for some time to come. Why bother testing for security errors when you can prove they don't exist?

Re:Crypto is only the Beginning

[phantomfive]

Crypto's not the weak link in security anymore

That's what you think.

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

NSA vs. PUBLIC

[muckracer]

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

Nevermind the intellectual "my code's better than yours" games
between arguably otherwise brilliant researchers.

Where the NSA certainly has 'maintained the upper hand' is in real
life versus ordinary people. The technology of surveillance has
gotten orders of a magnitude better and surrounding laws have been
adapted to make it fully legal to use that technology to the max
against The People (whereever they may be). Who in this discussion
encrypts their e-mails or uses 'sophisticated crypto schemes' as a
matter of course? At best it's maybe SSH here and there and the
occasional SSL site. The vast majority of traffic is plain-text, as
it's been since the days of papyrus. Hell, back in those days at
least only a few people could read it and thus had better privacy
than we mostly have today. Nevermind the ramifications of Facebook
and similar tools.

Mr. Shamir can engage in discussions of who developed Public Key
Cryptography first or not. It's all nonsense, because as brilliant
as the concept is, the PUBLIC has no part in it to 99.99% and
therefore we can consider it a complete FAILURE on grounds of lack
of acceptance and widespread use. Meanwhile the NSA sits back and
laughs, as their electronic tentacles filter through PUBLIC('s)
traffic...any traffic...and mostly doesn't have to bother with
breaking anything. Cuz we 'oh-so-clever' geeks have failed
miserably. If the NSA has any problem, then it's to store and
process/search through the data they get...not the acquisition.

Re:NSA vs. PUBLIC

[gazbo]

THANK YOU!

I'm never happy with the way my browser handles line-breaking, so I'm eternally grateful to you for taking the initiative and doing it yourself.

Re:Until

[base3]

I can factor large primes for you, no sweat, no quantum computer required. Now composites of large primes, there a quantum computer might help you.