Did NSA Put a Secret Backdoor in New Encryption Standard?

tck

Very interesting article in wired magazine by Bruce Schneier

http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115

It throws up alot of questions indeed!

mick.fr

I would not be surprised at all.
Do you know which software/applications might be affected, if any has already implemented them?

Martyr

it sounds like one of those keygen solutions

• If an attacker knows d such that d*P = Q then they can easily compute e such that e*Q = P (invert mod group order)
• If an attacker knows e then they can determine a small number of possibilities for the internal state of the Dual Ec PRNG and predict future outputs.
• We do not know how the point Q was chosen, so we don’t know if the algorithm designer knows d or e.

read this mick.fr
http://rump2007.cr.yp.to/15-shumow.pdf

seamus

I wouldn't be surprised that an agency would go for this, but I would be surprised if they had the backing of their experts. Doesn't U.S. law require that the U.S. government is given or has access to "back doors" for any encryption implemented in that country?

Any security expert would be well aware that leaving a back door in any system is simply providing a weak point where any determined attacker will get in eventually.

Capt'n Midnight

google for nsakey for fun

The NSA have made helped improve some encryption techniques in the past

:D http://www.austinlinks.com/Crypto/break-pgp.html :D <--- Foil hats

looks like the psudo random number generator is suggested to be compromised
http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115

I'd still maintain that it's probable that an employee at a major software house is in fact a secret agent belonging to some government and may even have put a back door into a system.

and then there was the dell keyboard controller to LAN thing - can anyone confirm ?


how about a hard wired back door ?
http://en.wikipedia.org/wiki/Clipper_chip

Black Swan

Can't remember where, but months back there was a magazine article that mentioned NSA required access to all programmes developed in the USA, especially those that infaced on the Internet and WWW.

mick.fr

Average Joe wrote: »

read this mick.fr
http://rump2007.cr.yp.to/15-shumow.pdf

I have checked on those guys, one is a researcher at Microsoft R&D and the other one is a Microsoft developer (Security products).

I am a bit surprised those guys have published such info because surely the senior staff at Microsoft would have been aware about this "issue" as I am sure Microsoft has been put under pressure (or not) to include such algo. into Longhorn.

mick.fr

Blue_Lagoon wrote: »

Can't remember where, but months back there was a magazine article that mentioned NSA required access to all programmes developed in the USA, especially those that infaced on the Internet and WWW.

I am sure it is, anyway a couple of months ago I also read an article about an UK based company that managed to decrypt SSL traffic in real time with a compute cluster.

Martyr

got a link? companies these days usually have some motive for making claims..and there is also a problem with the way media reports such details, because its perfectly fine to decrypt ssl in realtime, if you say used some MITM attack, or were simply using the private data used to decrypt info encrypted with public..etc

For example of bad reporting, recently at the kiwicon 2k7 conference, Nick Breese appeared on tv3.nz with reports of 1.4 billion md5 hashes a second could be created on a ps3, making it a hackers dream machine for password attacks.

then in other sites, it states normally a cpu is capable of 10-15 million cpu cycles a second, whereas the ps3 is capable of 1.4 billion cycles... increase by a factor of 100.

a cycle is not an iteration to the best of my knowledge.

then it claims in other reports than Nick can compute 8 million a second on pc using sse2/x86, which is alot less than 10-15 million. -
who is telling the truth??

because there is no presentation material available, no code..nothing.

in another related story in october, elcomsoft claims to have increased cracking by 25 times normal speed, or 200,000,000, using the new GeForce 8 series GPU, which are now fully equipped to handle integer operations - - then is quoted saying normally cpu compute 10 million a second..25x 10 = 250 million..ok, close enough, +5 is actually more exciting.

basically you get lots of company making wild inaccurate claims to bring attention unto themselves in the media..etc but at the end of the day, they're FOS.

Capt'n Midnight

Average Joe wrote: »

a cycle is not an iteration to the best of my knowledge.

Let's say it takes N cycles to complete an instruction. If you have N separate parts of the chip to process each part of an instruction the when you pipeline properly you can get one instruction per clock cycle coming out the far end (after the initial N cycle delay)

Having more bits like in a 64 bit CPU means in some cases you can process more than one data value in parallel per instruction. with GPU's a very wide bus means a huge speedup for CERTAIN instruction types.

Other instructions require more of the processor silicon and so don't lend themselves to pipelining - usually because they are rarely used and the chip makers don't try to optimize for them.

So with out knowing the code you can't tell how many instructions an iteration takes or how many cycles all the instruction per interation would take.

Martyr

So with out knowing the code you can't tell how many instructions an iteration takes or how many cycles all the instruction per interation would take.

exactly..we don't know
all we've been told by the media is that the ps3 does 1.4 billion cycles a second compared to normal x86 chip, yet are also led to believe that it is the number of md5 iterations computed a second.

Did Nick develop the PS3 Cell Processor?
Did he make it do 1.4 billion cycles a second, or is that what its capable of anyway?

if one site claims that Nick computed 8,000,000 k/s using sse2/x86, but another says that cpu is normally capable of 10-15,000,000 million cycles a second..another site then claims that he increased the speed by 100 times - none of the reports answers the important question "how many iterations a second"? which would give us the true performance gain.

the ps3 cell processor is RISC, with multiplexer instructions like SELB, which can compute equivilant of 2 XORs, 1 AND and 1 MOV on x86 hardware, but in just 1 cycle.

so how many cycles does it take for 1 round of md5? we don't know, because Nick hasn't told us..well, maybe he told people at the conference, i don't know.
Or maybe he did tell the media, and they decided that 1.4 billion cycles sounded better..

i wrote an x64 md5 routine 6 months ago, which created 15 hashes in parallel. it was a lengthy process to prepare each buffer, and in the end it was quicker to create just 5 hashes at once, which ended up at about ~13,500,000 k/s for single core 2.0ghz amd64 3200+

RAW calls to the x64 function were running at about ~17,000,000 k/s on single core.
i don't know how better performance would be on CORE2, but since these can execute 1 SIMD instruction in 1 cycle, which is 2x faster than pentium4
i imagine it to be alot faster..and even better with multiple cores.

but it doesn't account for time to prepare buffers, and then check the hash we're trying to crack....

i really don't believe that a ps3 can compute 1.4 billion hashes a second in a cracking procedure, but thats what the media are reporting - - even if it could, thats alot of hashes to check, not something that can be done quickly.

same thing with elcomsoft, claiming that they had increased speed of cracking NTLM1 (md4) using GeForce 8600GT.
they said 25x faster, yet mentioned normal speed on cpu was 10,000,000 k/s compared with the gpu computing 200,000,000 k/s

what about the time needed to check 200,000,000 hashes?
also, there is 1 program available already which can compute 16,000,000 ntlm k/s using x86 instructions by using some reversing/early abort procedures.
add in sse2, and you could compute 25,000,000 k/s - on a quad core, thats 100,000,000 k/s or more.

so using gpu only really gives 2x performance increase over intel hardware??..but that doesn't sound as sexy as 25x increase.

i just think alot of media are very misleading on technical issues, and i wouldn't pay too much attention to them, including the story that some uk based company decrypted ssl in realtime.

i'm not saying its impossible, but it all depends on the details, surely that would be something we would be made aware of immediately, to protect people who shop or bank online..etc

if attacker had private key for some banks online server, then obviously they could decrypt any ssl session between the client and server.