Jefferson's Wheel

British Prime Minister Gordon Brown has issued a long overdue apology to Alan Turing on behalf of the British government. The full text is here.

Turing was a quite brilliant mathematician, most famous for his work on breaking the German Enigma codes. It is no exaggeration to say that, without his outstanding contribution, the history of World War Two could well have been very different. He truly was one of those individuals we can point to whose unique contribution helped to turn the tide of war. The debt of gratitude he is owed makes it all the more horrifying, therefore, that he was treated so inhumanely. In 1952, he was convicted of ‘gross indecency’ – in effect, tried for being gay. His sentence – and he was faced with the miserable choice of this or prison – was chemical castration by a series of injections of female hormones. He took his own life just two years later.

… But even more than that, Alan deserves recognition for his contribution to humankind. For those of us born after 1945, into a Europe which is united, democratic and at peace, it is hard to imagine that our continent was once the theatre of mankind’s darkest hour. It is difficult to believe that in living memory, people could become so consumed by hate – by anti-Semitism, by homophobia, by xenophobia and other murderous prejudices – that the gas chambers and crematoria became a piece of the European landscape as surely as the galleries and universities and concert halls which had marked out the European civilisation for hundreds of years. It is thanks to men and women who were totally committed to fighting fascism, people like Alan Turing, that the horrors of the Holocaust and of total war are part of Europe’s history and not Europe’s present.

So on behalf of the British government, and all those who live freely thanks to Alan’s work I am very proud to say: we’re sorry, you deserved so much better.

The apology grew out of an online petition initiated by John Graham-Cumming (also known for writing the Geek Atlas travel guide). Britain has a long tradition of citizens being able to petition the government, which is now supported by an e-petitions website. The petition asking for an apology to Alan Turing is currently the fourth-most signed petition with 31,349 signatures (all of whom must be British citizens).

Some news coverage:

• BBC: PM apology after Turing petition
• The Guardian: No 10 apologises for “appalling” treatment of Alan Turing
• John Graham-Cumming’s blog: “Hello John, It’s Gordon Brown”

Technology Review has an article surveying the state of RFID security: RFID’s Security Problem, Technology Review, January/February 2009. It focuses on security and privacy issues related to RFID-enabled passports and driver’s licenses.

Excerpt: (bolding is mine)

Meanwhile, although experts say that some RFID technologies are quite secure, a University of Virginia security researcher’s analysis of the NXP Mifare Classic (see Hack, November/December 2008), an RFID chip used in fare cards for the public-­transit systems of ­Boston, London, and other cities, has shown that the security of smart cards can’t be taken for granted. “I think we are in the growing-pains phase,” says Johns Hopkins University computer science professor Avi Rubin, a security and privacy researcher. “This happens with a lot of technologies when they are first developed.”

…
As long as the remaining problems are ignored, though, it’s unlikely that the technology will become good enough to protect international borders without compromising the privacy of thousands or millions of people. Tadayoshi Kohno, for one, says that at this point, he is not convinced that RFID even offers security advantages over the old IDs. Technology used on this scale, and for purposes this important, should be clearly better than what it’s replacing: the U.S. experience with electronic voting systems shows what can happen when it’s not. If officials continue to advocate band-aids such as privacy sleeves rather than working to address the full extent of critics’ concerns, they will ultimately undermine the very technology that they hope to promote. While new ID technology seems likely to stay, it could become a fiasco if officials don’t pay attention to the work of hackers and security researchers. These people try to expose weaknesses before they can be exploited maliciously. It’s much less painful to swallow the news from them than to wait until a problem becomes embarrassing–or devastating.

Jonathan McCune successfully defended his PhD thesis at Carnegie Mellon University last week. Jon (sorry, that’s “Dr. McCune”) was an undergraduate researcher in our group from 2001-2003, when he worked on agent-based software (for our RoboCup team) and adaptable sensor network security, before joining CMU’s PhD program in 2003. Dr. McCune’s recent research has focused on leveraging trusted hardware to build secure systems.

Congratulations Dr. McCune!

UVa Today has an article about our (myself, abhi shelat, John Lach, and Ben Calhoun) recent NSF Cybertrust grant on RFID security and privacy: U.Va. Team Receives $1 Million Grant To Improve RFID Security, by Brevy Cannon, 9 January 2009.

Some excerpts:

To address the problematic use of custom cryptography, the U.Va. research team will develop an encryption scheme that is relatively strong — providing some measure of privacy and security — but that can be implemented at almost zero cost by repurposing the meager hardware resources already available on common RFID tags. Providing a solution that adds virtually no cost is crucial, because these RFIDs are made by the billions, at such low costs (5 cents or less apiece) that there is no margin for any added expense.

…

The team is breaking new ground by using a holistic design approach that considers how all the various levels of the design — the hardware, the encryption algorithm and how it is used — work together, mindful of how an attacker will target the single weakest link in the design.

…

The research team hopes their research will forestall that possibility, enabling RFIDs to be used in countless ingenious applications not yet dreamt of, without sacrificing privacy and security in a Faustian bargain.

The November/December 2008 Technology Review Hack, How Smart Is a Smart Card?”, describes Karsten Nohl’s work on reverse engineering the Mifare Classic. In includes a video of a card dissolving, and some great images.

The full details of the Crypto-1 cipher (initially exposed back in December) have now been released.

They are published in Appendix A of Henryk Plötz’s thesis report: Mifare Classic – Eine Analyse der Implementierung. The thesis is in German, but the algorithm is published as a C program (by Karsten Nohl, Henryk Plötz and Sean O’Neil), so should be understandable to non-German code readers.

Also yesterday, the paper, Dismantling MIFARE Classic, by Flavio D. Garcia, Gerhard de Koning Gans, Ruben Muijrers, Peter van Rossum, Roel Verdult, Ronny Wichers Schreur, and Bart Jacobs of Radboud University Nijmegen, The Netherlands, appeared at ESORICS 2008. This is the paper that was the subject of NXP’s failed lawsuit.

The publication of these details remove any remaining doubts about the insecurity of the Mifare Classic.

News articles:

D-Day for RFID-based transit card systems, c|net News, 6 October 2008.

“Combining these two pieces of information, attacks can now be implemented by anyone,” RFID researcher Karsten Nohl told CNET News. “All it takes is a $100 (card) reader and a little software.”
…
Security systems like the Mifare Classic that are not peer reviewed are not as trustworthy as systems that can be openly analyzed by researchers looking for flaws, Johanson and Nohl said.

“Developing your own proprietary security mechanisms and not getting public scrutiny on it does not work,” Nohl said.

Boffins (finally) publish hack for world’s most popular smartcard, The Register, 6 October 2008.

Two research papers published Monday have finally made it official: The world’s most widely deployed radio frequency identification (RFID) smartcard – used to control access to transportation systems, military installations, and other restricted areas – can be cracked in a matter of minutes using inexpensive tools.

The two documents combined mean that virtually anyone with the time and determination can carry out the attacks, said Karsten Nohl, a PhD candidate at the University of Virginia and one of the cryptographers who first warned of the weakness in December.

“Now the weakness that we and others have been talking about for months can be verified independently by really anybody,” he said. “The flip side is that everybody can now attack Mifare-based security systems.”

Over the past six months, many organizations that rely on the Mifare Classic have upgraded their systems, but Nohl said he is personally aware of a “handful” of systems used by government agencies or large multinational companies that have been unable to make the necessary changes because of the logistical challenges of issuing new badges to employees.

“One hopes that just based on the announcement, most operators of critical security systems have adopted other technologies besides Mifare,” Nohl said.

Update: (10 Oct) Another article from the CBC: Security flaw in smart cards poses risk for transit, building access, CBC News, 10 October, 2008.

Verayo is the second company to announce the "World’s first unclonable RFID tag" based on a physically unclonable function (PUF), after Veratag announced a similar product based on PUF technology. The security claims of these and other PUF-based products seem dubious since the current realization of PUFs defies basic principles of cryptography. The announcement states:

This new RFID chip is based on recently announced breakthrough technology called Physical Unclonable Functions (PUF). PUF technology is a type of electronic DNA or fingerprinting technology for silicon chips that makes each chip unclonable.

It might be besides the point that neither DNA, nor fingerprints are unclonable. The failure of proprietary security, which has been a constant theme on this blog, has led many to conclude that only well-reviewed security primitives can be strong. PUF technology tries to achieve security in exactly the opposite way: the PUF circuit is designed in a way so that not even the designer understands how outputs are derived from inputs. Security-by-obscurity par excellence.

Every circuit, including PUFs, is a deterministic function; the only difference in PUF circuits is that some inputs to the function vary across different tags. For a PUF to be cryptographically strong, one would hence need to show that

1. the fixed part of the circuit (the cipher) is strong by cryptographic metrics,
2. the number of device-dependent inputs (the secret key) is large and
3. the entropy of these inputs is high.

PUFs are a wonderful idea for using manufacturing variance constructively, but in their current realization, PUFs fail to convince that they are strong building blocks for security systems.

NXP is suing Radboud University in the Netherlands to prevent them publishing a paper (in ESORICS 2008 in October) containing details on the Mifare classic encryption algorithm (and various flaws they have found in the algorithm). Perhaps the title of the paper, “Dismantling MIFARE Classic”, got NXP’s attention. A hearing is scheduled for July 10.

Articles:

• Dutch chipmaker sues to silence security researchers, c|new News, 9 July 2008.
• NXP sues academic research team – what are they afraid of?, The Tech Herald, 10 July 2008.
• NXP sues to prevent hackers from releasing MIFARE flaws, Secure ID News, 10 July 2008.
• Chipmaker sues to quash research on RFID smart card security flaws, Computer World, 10 July 2008.

[Update 18 July] The judge has denied NXP’s request for an injunction, ruling that “limitations to the freedom of speech are allowed only if there is urgent and obvious threat to society”: Judge denies NXP’s injunction against security researchers, Industry Standard, 18 July 2008.

[Update 21 July] Another article: Dutch court allows publication of Mifare security hole research, CNet News, 18 July 2008. This one includes a picture of Karsten Nohl’s presentation at the Last HOPE Conference.

KIRO TV (Seattle) has a story on RFID privacy issues: Credit Cards Stolen Without Leaving Wallet (it includes a video demonstration).

German-born Karsten Nohl is a security consultant and PhD student at the University of Virginia. He was in Seattle recently to speak at a technology conference and is known worldwide for hacking into transit systems.

He’s exposed significant security problems with transit cards commuters were told held their personal information secure, but Nohl showed, did not

“Is it all that inconvenient to swipe a card? Does it really have to be tapping? Would, for that perhaps tiny added benefit, now expose your data to everybody in your vicinity? Perhaps not. So, that is a discussion that has to be had. And not just by the companies introducing something new and fancy and forcing everybody to use it, but rather by the consumers, too,” said Nohl.

Our upcoming USENIX Security Symposium paper is now available: Reverse-Engineering a Cryptographic RFID Tag by Karsten Nohl, David Evans, Starbug, and Henryk Plötz.

The paper describes the methods used to reverse engineering the encryption on the Mifare Classic RFID tag and some of the things we learned by doing it. Karsten Nohl will present the paper at the USENIX Security Symposium in San Jose on July 31.

Abstract

The security of embedded devices often relies on the secrecy of proprietary cryptographic algorithms. These algorithms and their weaknesses are frequently disclosed through reverse-engineering software, but it is commonly thought to be too expensive to reconstruct designs from a hardware implementation alone. This paper challenges that belief by presenting an approach to reverse-engineering a cipher from a silicon implementation. Using this mostly automated approach, we reveal a cipher from an RFID tag that is not known to have a software or micro-code implementation. We reconstruct the cipher from the widely used Mifare Classic RFID tag by using a combination of image analysis of circuits and protocol analysis. Our analysis reveals that the security of the tag is even below the level that its 48-bit key length suggests due to a number of design flaws. Weak random numbers and a weakness in the authentication protocol allow for pre-computed rainbow tables to be used to find any key in a matter of seconds. Our approach of deducing functionality from circuit images is mostly automated, hence it is also feasible for large chips. The assumption that algorithms can be kept secret should therefore to be avoided for any type of silicon chip.

Full paper (9 pages): [PDF] [HTML]