Crypto-Gram

October 15, 2012

by Bruce Schneier
Chief Security Technology Officer, BT
schneier@schneier.com
http://www.schneier.com

A free monthly newsletter providing summaries, analyses, insights, and commentaries on security: computer and otherwise.

For back issues, or to subscribe, visit <http://www.schneier.com/crypto-gram.html>.

You can read this issue on the web at <http://www.schneier.com/crypto-gram-1210.html>. These same essays and news items appear in the “Schneier on Security” blog at <http://www.schneier.com/>, along with a lively comment section. An RSS feed is available.

In this issue:

Keccak Is SHA-3

NIST has just announced that Keccak has been selected as SHA-3.

It’s a fine choice. I’m glad that SHA-3 is nothing like the SHA-2 family; something completely different is good.

Congratulations to the Keccak team. Congratulations—and thank you—to NIST for running a very professional, interesting, and enjoyable competition. The process has increased our understanding about the cryptanalysis of hash functions by a lot.

I did say before this announcement that NIST should choose “no award,” mostly because too many options make for a bad standard. I never thought they would listen to me, and—indeed—only made that suggestion after I knew it was too late to stop the choice. Keccak is a fine hash function; I have absolutely no reservations about its security. (Or the security of any of the four SHA-2 function, for that matter.) I have to think more before I make specific recommendations for specific applications.

Again: great job, NIST. Let’s do a really fast stream cipher next.

http://csrc.nist.gov/groups/ST/hash/sha-3/…

http://keccak.noekeon.org/

What I Wrote Just Before the SHA-3 Announcement

NIST is about to announce the new hash algorithm that will become SHA-3. This is the result of a six-year competition, and my own Skein is one of the five remaining finalists (out of an initial 64).

It’s probably too late for me to affect the final decision, but I am hoping for “no award.”

It’s not that the new hash functions aren’t any good, it’s that we don’t really need one. When we started this process back in 2006, it looked as if we would be needing a new hash function soon. The SHA family (which is really part of the MD4 and MD5 family), was under increasing pressure from new types of cryptanalysis. We didn’t know how long the various SHA-2 variants would remain secure. But it’s 2012, and SHA-512 is still looking good.

Even worse, none of the SHA-3 candidates is significantly better. Some are faster, but not orders of magnitude faster. Some are smaller in hardware, but not orders of magnitude smaller. When SHA-3 is announced, I’m going to recommend that, unless the improvements are critical to their application, people stick with the tried and true SHA-512. At least for a while.

I don’t think NIST is going to announce “no award”; I think it’s going to pick one. And of the five remaining, I don’t really have a favorite. Of course I want Skein to win, but that’s out of personal pride, not for some objective reason. And while I like some more than others, I think any would be okay.

Well, maybe there’s one reason NIST should choose Skein. Skein isn’t just a hash function, it’s the large-block cipher and a mechanism to turn it into a hash function. I think the world actually needs a large-block cipher, and if NIST chooses Skein, we’ll get one.

http://csrc.nist.gov/groups/ST/hash/sha-3/index.html

http://www.schneier.com/skein.html
http://www.schneier.com/threefish.html

News

It’s a known theft tactic to swallow what you’re stealing. It works for food at the supermarket, and it also can work for diamonds. Here’s a twist on that tactic:
http://www.bbc.co.uk/news/world-asia-19556612
This reminds me of group pickpocket tactics against tourists: the person who steals the wallet quickly passes it to someone else, so if the victim grabs the attacker, the wallet is long gone.

An analysis of 3.4 million four-digit PINs. (“1234” is the most common: 10.7% of all PINs. The top 20 PINs are 26.8% of the total. “8068” is the least common PIN—that’ll probably change now that the fact is published.)
http://www.datagenetics.com/blog/september32012/

Interesting article on how the NSA is approaching risk in the era of cool consumer devices. There’s a discussion of the president’s network-disabled iPad, and the classified cell phone that flopped because it took so long to develop and was so clunky. Turns out that everyone wants to use iPhones.
http://www.aclu.org//technology-and-liberty/…
Ed Felten has two posts about accountable algorithms. Good stuff.
https://freedom-to-tinker.com//felten/…
https://freedom-to-tinker.com//felten/…
Security vulnerability in Windows 8 Unified Extensible Firmware Interface (UEFI). This is the first one discovered, I think.
http://www.theregister.co.uk/2012/09/19/win8_rootkit/

Good summary article on homomorphic encryption.
http://www.americanscientist.org/issues/pub/2012/5/…
Long article on quantum cryptography and cryptanalysis.
http://arstechnica.com/security/2012/09/…
Kay Hamacher and Stefan Katzenbeisser, “Public Security: Simulations Need to Replace Conventional Wisdom,” New Security Paradigms Workshop, 2011. Both the methodology and the conclusions are interesting.
http://www.nspw.org/papers/2011/nspw2011-hamacher.pdf

A proposal to replace cryptography’s Alice and Bob with Sita and Rama:
http://profpartha.webs.com/publications/alicebob.pdf

Interesting Talk of the Nation segment on biometric data collection.
http://www.npr.org/2012/09/18/161355293/…

This Android malware story sounds pretty scary: surreptitiously using the phone’s camera to map a house for later burglary. It’s just a demo, of course. but it’s easy to imagine what this could mean in the hands of criminals. It seems to be a mashup of two things. One, the increasing technical capability to stitch together a series of photographs into a three-dimensional model. And two, an Android bug that allows someone to remotely and surreptitiously take pictures and then upload them. The first thing isn’t a problem, and it isn’t going away. The second is bad, irrespective of what else is going on.
http://gizmodo.com/5947385/…

Funny security question cartoon:
http://www.bizarrocomics.com/?p=8762

The 2013 U.S. Homeland Security budget:
https://www.schneier.com/blog/archives/2012/10/…

Anecdotes from Asia on seals versus signatures on official documents.
http://languagelog.ldc.upenn.edu/nll/?p=4230

Tradecraft and terrorism:
http://www.stratfor.com/weekly/terrorism-tradecraft

The folks at F-Secure have plotted ZeroAccess botnet infections across the U.S. and across Europe. It’s interesting to see, but I’m curious to see the data normalized to the number of computers on the Internet.
http://www.f-secure.com/weblog/archives/00002430.html

In the never-ending arms race between systems to prove that you’re a human and computers that can fake it, here’s a captcha that tests whether you have human feelings.
http://gizmodo.com/5949686/…
The easy way to attack this system is to create a library with all the correct answers.

This is a fascinating story of a CIA burglar, who worked for the CIA until he tried to work against the CIA. The fact that he stole code books and keys from foreign embassies makes it extra interesting, and the complete disregard for the Constitution at the end makes it extra scary.
http://www.smithsonianmag.com/history-archaeology/…

Article on the insecurity of networks. Not computer networks, networks in general. It’s a pretty good primer of current research into the risks involved in networked systems, both natural and artificial.
http://www.sciencenews.org/view/feature/id/343939/…

Sites in Taiwan that are blacked out for security reasons on Google Maps are shown on Apple’s mapping app. Which demonstrates the flaws in “ask nicely” as a security mechanism.
http://shanghaiist.com/2012/10/09/…

Apple turns on phone tracking in iOS6:
http://www.businessinsider.com/…

Recent Developments in Password Cracking

A recent Ars Technica article made the point that password crackers are getting better, and therefore passwords are getting weaker. It’s not just computing speed; we now have many databases of actual passwords we can use to create dictionaries of common passwords, or common password-generation techniques. (Example: dictionary word plus a single digit.)

This really isn’t anything new. I wrote about it in 2007. Even so, the article has caused a bit of a stir since it was published. I didn’t blog about it then, because I was waiting for Joe Bonneau to comment. He has, in a two-part blog post that’s well worth reading.

Finally, there are two basic schemes for choosing secure passwords: the Schneier scheme and the XKCD scheme.

Ars Technica article:
http://arstechnica.com/security/2012/08/…

My essay on password cracking:
https://www.schneier.com/blog/archives/2007/01/…

Bonneau’s comments:
http://www.lightbluetouchpaper.org/2012/09/03/…
http://www.lightbluetouchpaper.org/2012/09/04/…

Schneier scheme:
http://www.schneier.com/essay-246.html

XKCD scheme:
http://xkcd.com/936/

Master Keys

Earlier this month, a retired New York City locksmith was selling a set of “master keys” on eBay:

Three of the five are standard issue for members of the FDNY, and the set had a metal dog tag that was embossed with an FDNY lieutenant’s shield number, 6896.

The keys include the all-purpose “1620,” a master firefighter key that with one turn could trap thousands of people in a skyscraper by sending all the elevators to the lobby and out of service, according to two FDNY sources. And it works for buildings across the city.

That key also allows one to open locked subway entrances, gain entry to many firehouses and get into boxes at construction jobs that house additional keys to all areas of the site.

The ring sold to The Post has two keys used by official city electricians that would allow access to street lamps, along with the basement circuit-breaker boxes of just about any large building.

Of course there’s the terrorist tie-in:

“With all the anti-terrorism activities, with all the protection that the NYPD is trying to provide, it’s astounding that you could get hold of this type of thing,” he said.

He walked The Post through a couple of nightmare scenarios that would be possible with the help of such keys.

“Think about the people at Occupy Wall Street who hate the NYPD, hate the establishment. They would love to have a set. Wouldn’t it be nice to walk in and disable Chase’s elevators?” he said.

Or, he said, “I could open the master box at construction sites, which hold the keys and the building plans. Once you get inside, you can steal, vandalize or conduct terrorist activities.”

The Huffington Post piled on:

“We cannot let anyone sell the safety of over 8 million people so easily,” New York City Public Advocate Bill de Blasio said in a statement. “Having these keys on the open market literally puts lives at risk. The billions we’ve spent on counter-terrorism have been severely undercut by this breech [sic].”

Sounds terrible. But—good news—the locksmith has stopped selling them. (On the other hand, the press has helpfully published a photograph of the keys, so you can make your own, even if you didn’t win the eBay auction.)

I found only one story that failed to hype the threat.

The current bit of sensationalism aside, this is fundamentally a hard problem. Master keys are only useful if they’re widely applicable—and if they’re widely applicable, they need to be distributed widely. This means that 1) they can’t be kept secret, and 2) they’re very expensive to update. I could easily imagine an electronic lock solution that would be much more adaptable, but electronic locks come with their own vulnerabilities, since the electronics are something else that can fail. I don’t know if a more complex system would be better in the end.

http://m.nypost.com/p/news/local/…
http://www.huffingtonpost.com/2012/10/01/…
http://www.washingtonpost.com/business/…
http://gothamist.com/2012/09/30/…

Schneier News

I’m speaking at the b:Secure Conference in Mexico City on Oct 18.
http://bsecureconference.com.mx/

I am speaking at the Public Voice conference associated with the Privacy Commissioners Conference, in Maldonado, Uruguay on Oct 22.
http://thepublicvoice.org/events/uruguay12/

I am speaking at the CEP Round Table Meeting in New York on Nov 2:
http://www.globalcep.com/

I’m speaking at the Internet Governance Forum in Baku on Nov 7-9.
http://www.intgovforum.org/cms/component/content/…

I usually don’t post reviews of Liars and Outliers, but I am particularly proud of this one.
http://clcjbooks.rutgers.edu/books/…

And also this one, in Science.
http://www.schneier.com/book-lo-review-001.html

All the other reviews are here:
http://www.schneier.com/book-lo-reviews.html

When Will We See Collisions for SHA-1?

On a NIST-sponsored hash function mailing list, Jesse Walker (from Intel; also a member of the Skein team) did some back-of-the-envelope calculations to estimate how long it will be before we see a practical collision attack against SHA-1. I’m reprinting his analysis here, so it reaches a broader audience.

According to E-BASH, the cost of one block of a SHA-1 operation on already deployed commodity microprocessors is about 2^14 cycles. If Stevens’ attack of 2^60 SHA-1 operations serves as the baseline, then finding a collision costs about 2^14 * 2^60 ~ 2^74 cycles.

A core today provides about 2^31 cycles/sec; the state of the art is 8 = 2^3 cores per processor for a total of 2^3 * 2^31 = 2^34 cycles/sec. A server typically has 4 processors, increasing the total to 2^2 * 2^34 = 2^36 cycles/sec. Since there are about 2^25 sec/year, this means one server delivers about 2^25 * 2^36 = 2^61 cycles per year, which we can call a “server year.”

There is ample evidence that Moore’s law will continue through the mid 2020s. Hence the number of doublings in processor power we can expect between now and 2021 is:

3/1.5 = 2 times by 2015 (3 = 2015 – 2012)
6/1.5 = 4 times by 2018 (6 = 2018 – 2012)
9/1.5 = 6 times by 2021 (9 = 2021 – 2012)

So a commodity server year should be about:

2^61 cycles/year in 2012
2^2 * 2^61 = 2^63 cycles/year by 2015
2^4 * 2^61 = 2^65 cycles/year by 2018
2^6 * 2^61 = 2^67 cycles/year by 2021

Therefore, on commodity hardware, Stevens’ attack should cost approximately:

2^74 / 2^61 = 2^13 server years in 2012
2^74 / 2^63 = 2^11 server years by 2015
2^74 / 2^65 = 2^9 server years by 2018
2^74 / 2^67 = 2^7 server years by 2021

Today Amazon rents compute time on commodity servers for about $0.04 / hour ~ $350 /year. Assume compute rental fees remain fixed while server capacity keeps pace with Moore’s law. Then, since log_2(350) ~ 8.4 the cost of the attack will be approximately:

2^13 * 2^8.4 = 2^21.4 ~ $2.77M in 2012
2^11 * 2^8.4 = 2^19.4 ~ $700K by 2015
2^9 * 2^8.4 = 2^17.4 ~ $173K by 2018
2^7 * 2^8.4 = 2^15.4 ~ $43K by 2021

A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021.

Since this argument only takes into account commodity hardware and not instruction set improvements (e.g., ARM 8 specifies a SHA-1 instruction), other commodity computing devices with even greater processing power (e.g., GPUs), and custom hardware, the need to transition from SHA-1 for collision resistance functions is probably more urgent than this back-of-the-envelope analysis suggests.

Any increase in the number of cores per CPU, or the number of CPUs per server, also affects these calculations. Also, any improvements in cryptanalysis will further reduce the complexity of this attack.

The point is that we in the community need to start the migration away from SHA-1 and to SHA-2/SHA-3 now.

SHA-3 mailing list:
http://csrc.nist.gov/groups/ST/hash/email_list.html

E-BASH:
http://bench.cr.yp.to/ebash.html

Stevens’ attack:
http://2012.sharcs.org/slides/stevens.pdf

Since 1998, CRYPTO-GRAM has been a free monthly newsletter providing summaries, analyses, insights, and commentaries on security: computer and otherwise. You can subscribe, unsubscribe, or change your address on the Web at <http://www.schneier.com/crypto-gram.html>. Back issues are also available at that URL.

Please feel free to forward CRYPTO-GRAM, in whole or in part, to colleagues and friends who will find it valuable. Permission is also granted to reprint CRYPTO-GRAM, as long as it is reprinted in its entirety.

CRYPTO-GRAM is written by Bruce Schneier. Schneier is the author of the best sellers “Liars and Outliers,” “Beyond Fear,” “Secrets and Lies,” and “Applied Cryptography,” and an inventor of the Blowfish, Twofish, Threefish, Helix, Phelix, and Skein algorithms. He is the Chief Security Technology Officer of BT, and is on the Board of Directors of the Electronic Privacy Information Center (EPIC). He is a frequent writer and lecturer on security topics. See <http://www.schneier.com>.

Crypto-Gram is a personal newsletter. Opinions expressed are not necessarily those of BT.

Copyright (c) 2012 by Bruce Schneier.

Sidebar photo of Bruce Schneier by Joe MacInnis.