Wednesday, October 3, 2012

Schneier's Skein Loses out at SHA-3

The SHA-3 winner has been announced by NIST.  It appears Bruce Schneier (and his team's) entry of Skein did not win.  Instead the winner is Keccak.

Many people thought Skein might be a lock this time because of some of it's interesting design features, as well as the fact that it included it's own block cipher (Threefish) along with it.  On the other hand, Schneier himself said just a few days ago on his blog that he didn't think Skein would win (though he didn't give a reason).  He also said he doesn't think we actually need a new hashing standard because SHA-2 has held up much better than people thought it would back when the SHA-3 competition started.  Contrast this with DES, which was utterly broken (due to a small key) when the AES competition started back in the late 90's.  AES was a necessity, SHA-3 is not, according to Schneier.

In a way he has a point -- if it ain't broke and still performs reasonably well on the speed and efficiency front, then don't change.  After all, older and more well tested algorithms are almost always preferable because they have survived more scrutiny.

On the other hand, SHA-2 is an NSA designed algorithm, and to be frankly honest, that makes me nervous.  It is widely believed that NSA is a number of years more advanced in cryptology than the academic world.  Indeed, Brain Snow, a former NSA cryptologist has said as much publicly.  Therefore, there is always a chance they have engineered some clever backdoor (or skeleton key) into the algorithms they release for public consumption.  A lot of academics will scoff at the notion and say "it's hard to design a backdoor when we know exactly how the algorithm works and can study it openly."  What these guys fail to consider is that their "state of the art" is almost certainly a number of years behind NSA's.  And there doesn't really need to be a "backdoor" per se for the algorithm to be vulnerable.  It could be the NSA knows "short-cuts" around the design that they know full well haven't been discovered publicly.

This phenomenon was evident back in the 1970's when NSA knew about differential cryptanalysis, which the public academic world didn't discover until 20 years later.  A number of years ago Neils Ferguson (who is a cryptologist at Microsoft) discovered some strange going's on with an NSA CSPRNG (random number generator) known as Dual_EC_DRBG.  He discovered that with the way it was designed, there could be "up my sleeve" constants the author has that allows him to recover keys generated by the RNG.  A much more recent example is the MD5 collision used to forge certificates in the Flame malware.  It is true MD5 collisions have been discovered publicly and known about for some time, but the technique used by Flame was unknown to academia.  Indeed, one of the researchers who has worked on breaking MD5 said "the MD5 collision Flame uses is not the same one I discovered, but a new technique."  He went on to say, "The Flame creators have world class cryptologists working for them."   And everyone is pretty much in agreement that Flame, like Stuxnet, was a DoD/Israeli operation.

My point is, it never made sense to me that NSA would release their best and strongest designs to the public.  Keep in mind that they have a dual role: to secure America's digital infrastructure (COMSEC) but also to break other people's communications systems (SIGINT).  So, do you really think they would release a cipher or a hash algorithm to the public knowing it was impervious to their own attacks?  Would they really release an algorithm they can't break knowing it will find its way offshore to enemy nation-states and terrorist organizations?  (Most of the USA's intelligence, after all, comes from SIGINT).  What makes more sense is they release algorithms just "state-of the art" enough to be unbreakable by anyone but themselves (and there is some evidence that SkipJack was designed this way).  This solves the COMSEC problem here at home while also ensuring they don't hamper their SIGINT activities abroad.

So, when it comes to algorithms designed by NSA -- there are two ways to look at it:  If they are putting their COMSEC hats on and making their designs as resistant to attacks as they know how, then there are probably no better algorithms out there.  If, however, they are putting on their SIGINT hats, the algorithms, while strong, are probably not resistant to their own attacks.  Such algorithms in category 2 are probably strong enough for all cases except for trying to keep information secure from them.

Keccak was not designed by NSA, but was designed by independent researchers in an open competition (as was AES).  This means it has no backdoors.  It also means we can be sure it is state-of-the-art and likely to remain that way for years to come.  However, it does not mean NSA hasn't found weaknesses already with it.  It is well known that NIST, in their selection process, works closely with NSA.  Does this mean NSA is selecting weaker algorithms?  Or are they putting on their COMSEC hats and picking the most secure option?  We will probably never know.  The best we can say is that these algorithms (like AES and Keccak) are secure from the cryptanalysis techniques that are publicly understood.  We can never be sure what the army of mathematicians at Ft. Meade can or cannot do and I'm sure they prefer it remain that way.

In any case, I will take a publicly designed and open algorithm over an NSA designed one.  At least with the public algorithm, we know it is as strong as can be made with publicly known techniques.  NSA may or may not have techniques to break these public designs.  I would rather take that gamble than have a cipher they designed from the get-go.


  1. Excellent article. I agree on all points except for the (as was AES) reference to it being safe. I think they long ago broke it internally and wouldn't trust it. I 'm currently stuck (on a decision, not on not knowing how to install) at the beginning of a gentoo install on my new laptop and I cannot decide which encryption method to go for. Maybe you could offer some advice? I always used to use LUKS FDE with whirlpool -s 512 and 20000 iter-time oh and --use-random. However from what I've read online there are better ciphers out there now as well as much better hash algorithims, while I respect the whirlpool project I feel I can no longer trust it not due to any malevolence on the part of the wonderful devs who put in the effort to be as open as possible but the fact that it's based on AES which is probably known inside and out by the NSA. The last box I did had --cipher Twofish-XTS-Plain64 --hash whirlpool -s 512 --use-random --iter-time 20000 luksFormat /dev/sdX. However LUKS doesn't seem to support any of these new ciphers or algorithms. Is there another FDE method for linux that can be auto loaded at boot, preferably something that supports a keyfile encrypted with gpg-largekeys (the patched version that lets you generate 16kbit keypairs rather than 4096bit max. Or even better external boot/gpg'd keyfile on a thumb drive (backed up on an offsite location as they do break) that then lets me unlock the GPG keyfile with the staitc pass channel (basically any password method will wokr fine for this as yubikey emulates a keyboard) and then some of either using the webcam for facial rec + fingerprint scanner for another factor + Yubikey's OTP. Sounds awesome but I just don't know where to start on implementing it, I can't even find out which are the strongest ciphers these days. I learned of scrypt which is apparently one of the best hashing algoths but LUKS doesn't support it hence my uninstalled computer sitting there while I use Porteus in RAM on an old shitty computer when I have a nice one with an SSD just waiting to be encrypted. Speed matters not to me, i'll wait 20-30min for it to boot up np. I just want to figure out a method uncorrupted by the NSA/Shadow Government so I can get on with the rest of the ever pleasant gentoo install. I plan on doing my home folder up as well with entomb? i think it's called, some really neat open source crypto project I just read about earlier, zulucrypt was another idea. But I'd not even bother with the second layer if I could just figure out a fDE method that supports the latest and greatest ciphers/hasehs (for instance I heard about something called Tiger but can't find any meth od of implementing it) I don't do anything more illegal online at present than the average person I'm just an extremely paranoid person with very bad GAD ever since I learned pieces of the truth of the world and how democracy is really just an illusion to keep you happy in your wage slavery, yeah that sent me down a rabbit hole that ended me living on the street but that's a tale for another day. Please excuse any typos My fingers are too big for this keyboard and I'm on so many stims I'm typing 1k wps.

  2. NSA might be a number of years ahead back in 70s and 80s when only they did crypto.

    Now there are thousands of security experts and cryptologists working for hundreds of companies like Google, Microsoft and other smaller companies. Things are so 100% today. The talent crypto outside NSA is far (far) bigger now. It's outright idiotic to suggest that NSA is decades ahead of everyone else in 21st century. .

    It's also idiotic to suggest that SHA2 and AES algorithm have some secret sauce that only NSA can see but the rest of the world can't. That's just a stupid statement along the lines of earth is flat or no human landed on the moon.

  3. "So, do you really think they would release a cipher or a hash algorithm to the public knowing it was impervious to their own attacks?"

    Yes, it makes sense that NSA would release SHA2 to public so it can be scrutinized by the entire world. That way NSA would be more confident the SHA2 they are using in their own system is secure

    Look up Kerckhoffs's principle on Wikipedia.

    If security is a concern, we should use SHA2 and AES. A talented cryptanalyst simply gets more “bang for the buck” finding a flaw in AES then he does for the much less known and used twofish and serpent. Obscurity provides no protection in encryption. More eyes looking, studying, probing, attacking an algorithm is always better. You want the most “vetted” algorithm possible and right now that is AES and SHA2. If an algorithm isn’t subject to intense and continual scrutiny you should place a lower confidence in its strength.

    That's probably why NSA released SHA2 to public.

  4. This blog is related to Engineering and Computer science topics. Many of my Friends are related to this field so, I am going to recommend this post to all of them.