CRYPTO-GRAM
October 15, 2012
by Bruce Schneier
Chief Security Technology Officer, BT
[email protected]
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/blog>, along with a lively comment section. An
RSS feed is available.
** *** ***** ******* *********** *************
In this issue:
Keccak Is SHA-3
What I Wrote Just Before the SHA-3 Announcement
News
Recent Developments in Password Cracking
Master Keys
Schneier News
When Will We See Collisions for SHA-1?
** *** ***** ******* *********** *************
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/winner_sha-3.html
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/blog/technology-and-liberty/president-reads-his-daily-brief-ipad-and-other-lessons-nsa
or http://tinyurl.com/99rade7
Ed Felten has two posts about accountable algorithms. Good stuff.
https://freedom-to-tinker.com/blog/felten/accountable-algorithms/
https://freedom-to-tinker.com/blog/felten/accountable-algorithms-an-example/
or http://tinyurl.com/8e4ygsz
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/alice-and-bob-in-cipherspace
or http://tinyurl.com/cygopj8
Long article on quantum cryptography and cryptanalysis.
http://arstechnica.com/security/2012/09/quantum-cryptography-yesterday-today-and-tomorrow/
or http://tinyurl.com/8ecr6u4
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/the-pros-and-cons-of-gathering-biometric-data
or http://tinyurl.com/8dq9c2v
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/scary-new-malware-uses-your-smartphone-to-make-a-map-of-your-house-for-robbers
or http://tinyurl.com/9yjblog
Funny security question cartoon:
http://www.bizarrocomics.com/?p=8762
The 2013 U.S. Homeland Security budget:
http://www.schneier.com/blog/archives/2012/10/2013_us_homelan.html
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/prove-youre-a-human-by-telling-this-captcha-you-have-the-right-feelings
or http://tinyurl.com/9kakknf
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/The-CIA-Burglar-Who-Went-Rogue-169800816.html
or http://tinyurl.com/8qj3z5m
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/title/When_Networks_Network
or http://tinyurl.com/cz2zkf4
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_maps_lets_users_see_all_of_ta.php or
http://tinyurl.com/9w4nprt
Apple turns on phone tracking in iOS6:
http://www.businessinsider.com/ifa-apples-iphone-tracking-in-ios-6-2012-10
or http://tinyurl.com/9yk4v5f
** *** ***** ******* *********** *************
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/passwords-under-assault/
My essay on password cracking:
http://www.schneier.com/blog/archives/2007/01/choosing_secure.html
Bonneau's comments:
http://www.lightbluetouchpaper.org/2012/09/03/password-cracking-part-i-how-much-has-cracking-improved/
or http://tinyurl.com/8gqrye9
http://www.lightbluetouchpaper.org/2012/09/04/password-cracking-part-ii-when-does-password-cracking-matter/
or http://tinyurl.com/9oos9kj
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/open_door_to_terrorism_skC6uYlsymrLMKsXh4s2GM%22
or http://tinyurl.com/9dg8reu
http://www.huffingtonpost.com/2012/10/01/daniel-ferraris-new-york-master-keys_n_1928826.html
or http://tinyurl.com/9kgybyr
http://www.washingtonpost.com/business/mayor-nj-ex-locksmith-wont-sell-master-keys-for-nyc-construction-sites-lamppost-lights/2012/10/01/ff961d4c-0c10-11e2-97a7-45c05ef136b2_story.html
or http://tinyurl.com/9s8fx5k
http://gothamist.com/2012/09/30/ny_post_terrorist_dream_come_true_a.php
** *** ***** ******* *********** *************
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/article/114-preparatory-process/927-igf-2012
or http://tinyurl.com/98x6f78
I usually don't post reviews of Liars and Outliers, but I am
particularly proud of this one.
http://clcjbooks.rutgers.edu/books/liars_and_outliers.html
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.
** *** ***** ******* *********** *************
To unsubscribe, click this link:
http://listserv.modwest.com/cgi-bin/wa?TICKET=NzM0ODIwIGFyY2hpdmVATUFJTC1BUkNISVZFLkNPTSBDUllQVE8tR1JBTS1MSVNUIO5QLasjL3G1&c=SIGNOFF
