SHA-256 is designed by the NSA - do they have a backdoor?

[cypherdoc]

as evidence Linux is gaining in popularity:

http://blog.cryptographyengineering.com/2013/09/on-nsa.html

[1715014026]

1715014026

[1715014026]

1715014026

[TippingPoint]

By the way: What might have been the reason that Mr. Nakamoto decided to use an NSA algorithm (SHA-256) for Bitcoin?

There are more than a few hints that Mr Nakamoto himself (themselves) may be linked to NSA. just saying...

A cite?  The only comments I remember is when Gavin went to CIA for a presentation on Bitcoin, Satoshi wasn't interested.

This is quoted from the defunct Bruce Wagner Bitcoin podcast:

Bruce Wagner : When was the last time you chatted to satoshi <laugh>
Gavin Andresen: Um... I haven't had email from satoshi in a couple months actually. The last email I sent him I actually told him I was going to talk at the CIA. So it's possible , that.... that may have um had something to with his deciding

Link to source/timestamp?

I'd love to hear this part, but not enough to listen through Bruce Wagner's podcast.

http://itunes.apple.com/us/podcast/onlyonetv.com-bitcoin-show/id464967190

It should be around 17:53. First episode.

[Come-from-Beyond]

The US government uses SHA-2 in secure cryptographic systems including SIPERNet.  I know this from personal experience.

Quoted for future references when I prove that
1. D&T = Satoshi
2. Bitcoin was created by NSA

Hehe

[marcus_of_augustus]

Are you really that naive?

Do you underestimate the brightest minds in the world? Do you believe that the minds in the NSA are somehow brighter than those outside of it?

It is not who is brighter or has the most talent ... it is about an asymmetry of knowledge (as it has always been, the designer of the lock is the guy who knows where it is vulnerable.)

NSA designed the SHA256 algorithm, you don't think they had an eye on what their hardware is capable of whilst doing so?

[marcus_of_augustus]

Why would the NSA ever release a 'secure' algorithm? It's like shooting yourself in the foot, it would make their job so much harder. They would only ever release something that they could control. It's just the way the world works.

Because you can never definitively prove a cryptographic system is secure.  The only way to "know" a cipher is secure is to make it publicly available and let the best in the world take a crack at it.  It is very easy to write a cryptographic system that you yourself can't break but that is next to useless.  Secret cryptography usually is weak cryptography.  History is littered with examples of failed "strong" systems.  One classic one is WEP which is so unbelievably broken it is hard to believe cryptographers came up with it.  Security through obscurity doesn't work.  Had the specs for WEP been made publicly available in the design phase people would have found the flaws in a matter of weeks and saved everyone a ton of problems down the road.  For every good cipher there are dozens and dozens of flawed ones.  No matter how smart a single developer is the combined intellect of the planet is better, that is the entire rationale for open source.  The NSA is not only responsible for finding the secrets of others they are responsible for ensuring others don't find the secrets of the United States. 

The US government uses SHA-2 in secure cryptographic systems including SIPERNet.  I know this from personal experience.

Hmmm, you are sounding more and more like a spook or ex-spook ... doth protest too much?

[Dabs]

Well, SHA-512 was also designed by the NSA right? And HMAC-SHA-512 uses the same hash function. Does anyone think they can crack that better than brute-force?

[QuantPlus]

as evidence Linux is gaining in popularity:

http://blog.cryptographyengineering.com/2013/09/on-nsa.html

These are SSL servers.

But in the PC world it's:

Windows... 86.0%
Apple......... 7.5% 
Linux.......... 1.5%

You're average person has never seen or used a Linux box.

http://en.wikipedia.org/wiki/Usage_share_of_operating_systems

[drawingthesun]

I have a sneaking suspicion that the NSA's alleged superpowers are overrated. Maybe they once were way ahead of the curve back when crypto was a nerd curiosity. But now? In 2013, when the whole world understands the importance of crypto and scads of people are interested in it, including hackers who stand to become fabulously wealthy if they could find a flaw? I just don't buy it. More likely the government just wants people to think there's no point in using cryptography.

And we have a winner! Ding ding ding!

After Prism we started to hear lots of stories coming from two sides.

Side 1) We need to start using crypto in everything now! Secure all the things! (This is us, the geeks)

Side 2) Oh fudge if people start securing everything the future is going to be very dark indeed. Very dark because our capturing data centers will be redundant. (This is the NSA)

If the NSA had really broken core cryptographic functions they would be neutral on people using encryption as it wouldn't matter. They would stay in the dark like they always do. Just watching us.

However instead we started to get FUD all over the place about encryption. I remember reading that the government recommended people not to use encryption because it would mean the NSA would keep your data forever, and when that didn't work they started to give hints that all this encryption is useless anyway.

This is what they want people to think, that its all broken so why waste your time? Just go back to using closed source please.

If there is something they have done, that is they are "cheating" in that they are compromising many communication lines, certificates and closed source software.

NSA most likely have access to gmail, skype, perhaps even windows backdoors.

This is a campaign of FUD from the government.

EDIT: I think SSL is compromised because they rely on certificates which is trivial for the NSA to acquire.

[domob]

I have a sneaking suspicion that the NSA's alleged superpowers are overrated. Maybe they once were way ahead of the curve back when crypto was a nerd curiosity. But now? In 2013, when the whole world understands the importance of crypto and scads of people are interested in it, including hackers who stand to become fabulously wealthy if they could find a flaw? I just don't buy it. More likely the government just wants people to think there's no point in using cryptography.

And we have a winner! Ding ding ding!

After Prism we started to hear lots of stories coming from two sides.

Side 1) We need to start using crypto in everything now! Secure all the things! (This is us, the geeks)

Side 2) Oh fudge if people start securing everything the future is going to be very dark indeed. Very dark because our capturing data centers will be redundant. (This is the NSA)

If the NSA had really broken core cryptographic functions they would be neutral on people using encryption as it wouldn't matter. They would stay in the dark like they always do. Just watching us.

However instead we started to get FUD all over the place about encryption. I remember reading that the government recommended people not to use encryption because it would mean the NSA would keep your data forever, and when that didn't work they started to give hints that all this encryption is useless anyway.

Very good points!  I also believe that they are very far from actually breaking the algorithms themselves.  (Except possibly if they managed to build a quantum computer, which I see as faint possibility.)

EDIT: I think SSL is compromised because they rely on certificates which is trivial for the NSA to acquire.

Very true.  SSL/TLS may be secure by itself, but the CA infrastructure is not.  In fact, not only the NSA but a lot of other governments also directly or indirectly "own" a CA which is trusted by all major browsers/systems.

[Dabs]

I use gmail. But I also use GPG with 4096 bit RSA keys. They can store my encrypted message and keep it for all eternity, but they'll never read it.

[domob]

I use gmail. But I also use GPG with 4096 bit RSA keys. They can store my encrypted message and keep it for all eternity, but they'll never read it.

I wouldn't be so sure that RSA with 4096 bits will really never be cracked.  Especially asymmetric algorithms seem quite vulnerable, given enough time for new methods and hardware to develop.  (Nevertheless I also consider my GPG mails with this setting to be reasonable secure.)

[Come-from-Beyond]

I use gmail. But I also use GPG with 4096 bit RSA keys. They can store my encrypted message and keep it for all eternity, but they'll never read it.

Even with their quantum computer?

[dave111223]

A friend of mine's son has studied maths at Cambridge in the UK, he is now doing a PHD over in the US at MIT. She had her son's friend stay with her over the holiday, and told me that this girl was also studying for a PHD also. This girl is apparently ridiculously intelligent, to the point of being autistic, she has no social skills. She has already been approached by GCHQ and has done a summer placement there. She has been offered a place after completing her PHD.

It's true...the NSA drives around on campus' in black vans looking for people with bad haircuts and mismatching orange and pink socks.  They then throw a bunch of matches out the car window, if the target starts frantically counting the matches and repeating the total sum they put a brown bag over their head and bring them to area 51 for some super secret smart ass shit.

[manfred]

They would be dump as hell if there is no chance in at all to access it if there is a need to do so. As it stands there is no need to blow the cover and sacrifice years of work and huge amounts of money spend. In the big picture S.R. is laughable and Bitcoin is endorsed by the system at the moment (growing economy: hardware sales, exchanges, new products...).
Any rough element or country could simply send encrypted messages back and forth using a few satoshis and they would be totally defenceless defending themselves and country using a tool they created. If u believe this, well Santa Clause is coming to town too. If they see the need to switch the switch then they will.

[Dabs]

I use gmail. But I also use GPG with 4096 bit RSA keys. They can store my encrypted message and keep it for all eternity, but they'll never read it.

Even with their quantum computer?

Even with their quantum computer. If you live long enough to read my email, you are effectively immortal. That, or someone stole my private key.

[DeathAndTaxes]

I use gmail. But I also use GPG with 4096 bit RSA keys. They can store my encrypted message and keep it for all eternity, but they'll never read it.

I wouldn't be so sure that RSA with 4096 bits will really never be cracked.  Especially asymmetric algorithms seem quite vulnerable, given enough time for new methods and hardware to develop.  (Nevertheless I also consider my GPG mails with this setting to be reasonable secure.)

This.  There is a high probability that 4096 bit asymmetric encryption will eventually be broken (by classical computing).  Various agencies estimate a high probability that 4096 bit will no longer be secure after 2030-2060.   That being said 4096 bit RSA provides reasonable security for the intermediate future however "never" is a long time.  If it must be longer than your lifespan you should be looking at something like 15,360 bit RSA or 512 bit ECC.

[Dabs]

Ok. I stand corrected. The word "never" was used as hyperbole. 2030 to 2060 is just about right, and maybe even sooner. Obligatory cartoon here:

http://xkcd.com/538/



However, those same studies find 256 bit symmetric keys and hashes going far beyond the year 2080. We can already start using 512 bit hash functions.

[DeathAndTaxes]

Ok. I stand corrected. The word "never" was used as hyperbole. 2030 to 2060 is just about right, and maybe even sooner. Obligatory cartoon here:

No problem I personally use 4096 bit keys for PGP and don't worry.  I does what its name says it does "pretty good privacy".  I also agree even if 4096 bit can be broken someday it is more likely someone is going to beat me with a wrench instead.    Someone uninformed however might reach the wrong conclusion.  I guess it all depends on how secret your secrets are or maybe more importantly how long they need to remain a secret.

However, those same studies find 256 bit symmetric keys and hashes going far beyond the year 2080. We can already start using 512 bit hash functions.

Symmetric cryptography and hashing functions (assuming the algorithm itself is secure) don't have the same attack vectors that public key cryptography does.  They also aren't vulnerable to Shor's algorithm. It is very like we will never need larger than 256 bit symmetric encryption or 512 bit hashes due to thermodynamics*.   Public key is always going to be trickier to keep secure as they all rely on assumptions, and that will lead to a never ending "arms race".  BTW I like that cartoon I have a signed print on my wall.  Good reminder to see the forest from the trees when dealing with security.


* Brute forcing a 256 bit key is a "never" scenario (more energy than available in our star system).  
https://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html

[gmaxwell]

Public key is always going to be trickier to keep secure as they all rely on assumptions, and that will lead to a never ending "arms race".

Well, careful, symmetric ciphers depend on the existence of one way functions. If P happened to practically equal NP, then one way functions couldn't exist and I could solve for the symmetric keys that turns your ciphertext into ascii (there is probably only one).

NOT. BLOODLY. LIKELY.  (kinda sadly, there would be a lot of other befits to such a world)

It's possible to construct public key signature systems that depend only on the existence of one way functions.  (Lamport!)

The soundness assumptions in error correcting code crypto-systems are also generally pretty solid (well, we keep breaking them trying to make their overheads tolerable…)  (solving for random linear codes is NP-HARD ... the only question is can the attacker turn your public key back into an easy linear code)

Considering that for encrypted messages overhead is mostly immaterial I'm surprised that no one has created a stone soup protocol that just takes "one from each column":

NIST-521 bit ECDH, just in case the NSA made it stronger
1024 bit ECDH with parameters selected the best known public art techniques (e.g. like the brainpool curves)
Supersingular isogenies key agreement
Wrapped up inside an error correcting code public key encryption
And that encrypted with a symmetric key which is from the recipient, a starter one is in the public key.. though thats not very useful.
Feed it to a pair of orthogonal strong KDFs which then feed separate passes of multiple standard ciphers (unrelated keys) in some long block modes.

Then inside the encrypted messages you send symmetric keys generated using H(random, data_thats_part_of_your_private_key) which your receiver will save and use as an additional key in your KDFs in messages they send to you in the future (perhaps up to N of them with octave spacing, so a spy that can break the public key stuff will get locked out with high probability if they miss any of your messages).

Perhaps then the whole message gets thrown through a gnarly unkeyed cryptographic permutation and coded up with a RS code and you replace it with the non-systematic outputs and, at your option send, the message in as many parts as you like over different communications channels... so an attacker who can't snoop all of them learns almost nothing about the whole message.

Care would need to be taken to avoid interactions that hurt security.. but for encrypted messages.. who gives a crap if there is 50K of overhead and it takes a half second to decrypt?  There are plenty of applications where thats totally unacceptable, like Bitcoin... but also plenty where it is.

... wait. what board is this?? woah .. way offtopic.

[hashman]

I use gmail. But I also use GPG with 4096 bit RSA keys. They can store my encrypted message and keep it for all eternity, but they'll never read it.

Even with their quantum computer?

Even with their quantum computer. If you live long enough to read my email, you are effectively immortal. That, or someone stole my private key.

Or, they were reading the email as you typed it using

1) Rootkit
2) Tempest
3) Robotic mosquito flying behind your head