Jefferson's Wheel

Our paper, Hiding in Groups: On the Expressiveness of Privacy Distributions by Karsten Nohl and David Evans, is now available: PDF (15 pages). Karsten Nohl will present the paper at the 23^rd International Information Security Conference (SEC 2008, Co-located with IFIP World Computer Congress 2008) in Milan, Italy, 8-10 September 2008.

Abstract

Many applications inherently disclose information because perfect privacy protection is prohibitively expensive. RFID tags, for example, cannot be equipped with the cryptographic primitives needed to completely shield their information from unauthorized reads. All known privacy protocols that scale to the anticipated sizes of RFID systems achieve at most modest levels of protection. Previous analyses found the protocols to have weak privacy, but relied on simplifying attacker models and did not provide insights into how to improve privacy. We introduce a new general way to model privacy through probability distributions, that capture how much information is leaked by different users of a system. We use this metric to examine information leakage for an RFID tag from the a scalable privacy protocol and from a timing side channel that is observable through the tag’s random number generator. To increase the privacy of the protocol, we combine our results with a new model for rational attackers to derive the overall value of an attack. This attacker model is also based on distributions and integrates seamlessly into our framework for information leakage. Our analysis points to a new parameterization for the privacy protocol that significantly improves privacy by decreasing the expected attack value while maintaining reasonable scalability at acceptable cost.

Full paper (15 pages): [PDF]

Extended Technical Report (18 pages): [PDF]

The Associated Press has an article by Martha Irvine, Social networking applications can pose security risks, that is based on Adrienne Felt’s analysis of Facebook platform privacy.

Still, it’s an honor system, says Adrienne Felt, a computer science major at the University of Virginia. A Facebook user herself, she decided to research the site’s applications and even created her own so she could see how it worked.

Most of the developers Felt polled said they either didn’t need or use the information available to them and, if they did, accessed it only for advertising purposes.

But, in the end, Felt says there’s really nothing stopping them from matching profile information with public records. It also could be sold or stolen. And all of that could lead to serious matters such as identity theft.

“People seem to have this idea that, when you put something on the Internet, there should be some privacy model out there — that there’s somebody out there that’s enforcing good manners. But that’s not true,” Felt says.

(Note: there wasn’t actually any “polling” of developers, just examining what applications do to determine how they appeared to use information.)

The story has been picked up by some other places including BusinessWeek, CNNMoney (From games to virtual gifts, social networking applications popular — but at what risk?), Forbes, International Herald Tribune, National Public Radio, San Jose Mercury News, Philadelphia Inquirer, Las Vegas Sun, Fort Worth Star-Telegram, Houston Chronicle, San Francisco Chronicle, Seattle Post-Intelligencer, MyFOX, and The Sydney Morning Herald.

The Colorado Daily wins the best title award for MySpace is your space (and yours, and yours…) (but its the same story).

Pantagraph (Central Illinois) has it currently as their top article and includes a picture their front page.

[Added 13 May] Pew Internet and American Life Project has a post on this: Securing Private Data from Network ‘Zombies’ by Mary Madden.

ComputerWorld has an article about the new cryptanalysis of Crypto-1 results:
MiFare RFID crack more extensive than previously thought: Seconds, not hours, to effect; plus version tappable too, ComputerWorld, 15 April 2008.

The ubiquitous MiFare Classic RFID chip — used daily by millions worldwide in access control keys, subway passes and other applications — is even easier to crack than previously thought, according to security researchers who announced the development Tuesday at EuroCrypt, an international cryptography conference in Istanbul.

Mere seconds are all that is required to crack the chip’s security — not a few hours, as estimated last month. Karsten Nohl, a computer science graduate student and one of the masterminds behind reverse-engineering MiFare security, said in an interview that it now takes only 12 seconds to recover the key on a MiFare Classic card on an ordinary laptop.

On Monday, the Dutch government issued a final report arriving at the decisive conclusion that the chips, used by millions of citizens in the Netherlands, must be replaced. An earlier Dutch report had stated that a security breach on the MiFare cards was possible, but would be too unwieldy for the average attacker to accomplish.

There is also a series of articles in the Brisbane Times (Austrailia):

• Go cards ‘doomed’ over security, Brisbane Times, April 11, 2008.
• Reveal contract details: Opposition, Brisbane Times, April 11, 2008. (This one is mostly political.)
• New report slams go card security, Brisbane Times, April 16, 2008.

Other articles include: Dutch transit card crippled by multihacks, The Register, 16 April 2008.

EETimes and RFID-world.com published an op-ed piece by me that discusses the current lack of security in NFC cell phone standards.

Near Field Communication (NFC) phones automatically exchange data with other phones and objects in their vicinity. These phones are the latest example of a new technology developed with a strong focus on potential applications, but without sufficient thought to security and privacy concerns.
…
Adding sound security and privacy protection will slow down the deployment process and most likely increase the cost. Perhaps, security has this intrinsic cost that cannot be avoided as long as technologies create new incentives for thieves. NFC phones will attract misuse and computer fraud unless strong protection is included as a mandatory part of the NFC standards, similar to e-mail that promised simple, cheap, world-wide communication for everyone, but is now spoiled for many by spam, viruses and phishing.

Chris Soghoian has a new article, Hackers target Facebook apps, March 27, 2008, that follows up his earlier article about Adrienne Felt’s analysis of privacy issues for the Facebook platform. Unsurprisingly, many Facebook applications are written without basic security protections; since they have access to private user data, flawed (but not intentionally malicious) Facebook applications can be exploited to compromise other user accounts.

The SecureIDNews podcast has an interview with Karsten Nohl about the Mifare cryptanalysis, as well representatives from NXP and the Smart Card Alliance: Episode 8: Interview with Mifare hacker Karsten Nohl, SecureIDNews Podcast, 2 April 2008.

Karsten Nohl is presenting talks this week in Vancouver:

Proprietary RFID Systems (with Jan “starbug” Krissler) at CanSecWest, Vancouver, Thursday, March 27.

and Seattle (at the University of Washington):

The (Im)possibility of Hardware Obfuscation, Monday, March 31

Here is the abstract for the talk at UW:

We will discuss several different approaches to reverse-engineering proprietary algorithms from hardware. The focus will be on a mostly automated approach I developed to reconstructing functionality by using a combination of image analysis of circuits and protocol analysis. The cryptography my approach finds on a widely deployed “secure” RFID token has several vulnerabilities including weaknesses in the random number generator and very low resistance against brute-force attacks. I will further raise the question of how small cryptography can be implemented and present our design for a small hash function that reuses circuitry already found on RFID tags.

(I believe the talk is open to the general public, but if you are interested in attending from outside the UW community, check with Evan Welbourne.)

From Trend Micro’s Malware Blog: Hacked RFIDs Render Smart Cards Less Smarter [sic]:

Falling into the wrong hands, this security loophole can be and will surely be used in high profile heists and break-ins, seemingly straight from a James Bond movie.

NXP has released two statments about Mifare security: Information for end users and Information for system integrators.

The statements appear to be nearly identical. The excerpt below is from the statement for end users:

In December 2007 a group of researchers at the 24th Chaos Computer Club in Berlin claimed that they reverse engineered a MIFARE Classic chip and partially discovered the encryption algorithm of the chip. At the same time, they stated that they were not yet able to recover any keys from the chip.

NXP has come to the conclusion that two research groups have by now retrieved the algorithm and developed attacks which can be done with faster means of breaking keys than brute force. Although we are trying to prevent this, there is a risk of the full algorithm becoming publicly known and we feel it is appropriate to inform you about the potential consequences and necessary measures to be taken to minimize the impact of such eventuality for your system infrastructure.

Although we trust that you have worked with a system integrator who has implemented in your systems effective mechanisms to detect fraudulent cards (which we understand is possible in a number of ways), we want to inform you that we are investigating scenarios how MIFARE Classic systems can be protected Mindful of the above, we ask you to contact your system integrator to assess whether your systems would need any additional security measures.

It is our assessment that for transport ticketing installations, end-to-end security systems can be designed with the MIFARE Classic chip such that the residual risk of fraud not being detected in time can be drastically reduced. Whether or not those scenarios are acceptable in your risk assessment depends on the assets to be protected which only you and your system integrator can determine.

End to end measures should also be applied for access management infrastructures, which are often complemented by additional measures e.g. camera surveillance, security personnel, etc. when valuable assets need to be protected. We recommend that your assessment of the impact of the recent and expected developments takes into account the particular way that the system is implemented and used, its relation to other protection in place, and specifically whether there is a need to prevent unauthorized single time access or access during a limited period of time.
…

RFID Journal has an article about NXP’s new Mifare Plus chip, which supports AES encryption and is backward-compatible with the Mifare Classic:
NXP Announces New, More Secure Chip for Transport, Access Cards by Mary Catherine O’Connor, 14 March 2008.

This is an interesting development, but its not clear to me exactly what “backward-compatible” means: readers need to be upgraded to interact with the new tags. According to the article,

An RFID interrogator can employ the AES encryption deployed on the Mifare Plus chip to authenticate that chip before accepting its data and triggering a function, such as opening a locked door or allowing a commuter to pass through a transit turnstile. A number of additional security features, through the support of secure random identifiers, can prevent individuals from being identified and tracked by nefarious parties with RFID readers, NXP reports.

The chip’s encryption scheme uses a 128-bit key, whereas the Mifare Classic’s security algorithm employs a 48-bit key. The larger an encryption key, the longer it will take hackers to determine the key through reverse engineering.

NXP declines to reveal pricing for the Mifare Plus chip, but a chip’s price generally increases in step with its security features, so it will most likely cost more than the Classic chip. NXP says it will continue to manufacture and sell the Mifare Classic chip. Compared with other chips in the Mifare product family, the Classic supports the fewest security features. According to Manuel Albers, NXP’s director of regional marketing in the Americas, the Plus is more secure than the Classic but less secure than the Mifare DESfire chip, which uses a very robust data protection scheme called triple-DES.

Note: the comment that, “The larger an encryption key, the longer it will take hackers to determine the key through reverse engineering.” isn’t quite technically correct. If the key is larger, the time required to do a brute force key search is longer (it scales exponentially with the key size). The time to reverse engineer the algorithm scales with the complexity of the logic. The key size gives some minimum size for this complexity, and ciphers with longer keys are likely to have more complex logic, but this is not necessarily the case.