Category: Mobile

Consistent Results from Inconsistent Data

This post is a continuation of my report on the NIST Cryptographic Key Management Workshop. In the previous post I said I had more to say about Rene Struik’s presentation [1] because there are multiple connections between his talk and our own presentation [2].

Dr. Struik proposed to use a physical uncloneable function (PUF) to generate a cryptographic key when the device is turned on. A PUF is a function implemented by a physical device that is difficult to predict and difficult to duplicate in a different device. One way of implementing a PUF is by applying stimuli to a device such as a chip, and reading responses that are not determined by the design of the chip, but depend instead on small random variations of the fabrication process within the tolerances of the process specification. For key generation, one stimulus is applied to the device, viz. power, and one response is produced, an uncloneable key.

One problem with this key generation method is that the response of the chip will be slightly different each time the device is turned on. Struik proposed an elegant method of removing these differences in order to obtain the same key consistently, and using these same differences as an entropy source for true random number generation.

I saw an interesting connection between Struick’s uncloneable key and the hardware key used by Apple for data protection in iOS, which I discussed during my talk.

Both keys are intended to be difficult to extract from the device where they are used. The hardware key is built into the silicon of a hardware encryption chip, whose interface does not allow the key to be exported from the chip; but no claims are made as to the chip being tamper resistant, so a well-equipped attacker may be able to read the key by probing the silicon. By contrast, the uncloneable key is not present in the device when the device is turned off and thus cannot be extracted by probing the silicon; but custom code running on the device could obtain the key when the device is turned on.

The two methods could be combined. For example, a device could contain an encryption chip that would generate an uncloneable key when power is applied, and the interface of the chip could prevent the key from being exported. However, custom code running on the device could still make use of the key, just like forensic tools are able to use the hardware key in the iPhone in brute-force attacks to crack the user’s passcode [3] [4].

Another connection between the two presentations is that they both proposed regenerating keys instead of storing them. In Struik’s presentation a symmetric key was regenerated from the physical properties of the device. In our presentation an RSA key pair was regenerated from user input (a PIN and/or a biometric sample). Our regeneration method is not applicable if there is no user, while Struik’s is; on the other hand, when used in a user-controlled mobile device, our method has the advantage that the key pair caonnot be obtained by custom code running on a device that has been lost or stolen.

But the most interesting connection, for me, was between Struik’s method for consistently producing the same uncloneable key from a succession of slightly different physical responses to power-on, and the method of Hao, Anderson and Daugman [5] for producing a consistent biometric key from a succession of genuine but slightly different iris image samples. (In our presentation, we proposed to use the method of Hao et al. in two- and/or three-factor authentication.) Both methods are based on the same ingenious adaptation of the error correction paradigm for producing consistent results from inconsistent data (which was pioneered by Juels and Wattenberg [6] for implementing fuzzy commitments as explained below).

Error correction techniques were originally intended, and are most often used, for correcting errors caused by the transmission of data over a noisy channel. Redundancy added to the data at the source makes it possible to correct a small number of errors at the destination. (A unit of data to which redundancy has been added is called a codeword.)

The small variations that occur between successive biometric samples or between successive samples of an uncloneable key are similar to errors produced by channel noise, but there is no correct source data to which redundancy could be added to eliminate errors. If fact, no errors are involved because, although one particular sample may serve as a reference, no sample is more correct than any other sample.

To remove data variations, error correction is used as follows:

  1. A random codeword c is generated by adding redundancy to a random string. The random codeword is of same length as a data sample, but is otherwise unrelated to any data sample.
  2. The random codeword c is bitwise x-ored with a reference sample r to produce helper data h:
    h = c ⊕ r.
  3. When a new sample s is obtained, it is bitwise x-ored with the helper data to produce
    (c ⊕ r) ⊕ s.
    Since x-or is associative, this is the same as
    c ⊕ (r ⊕ s)
    and since r and s are similar, i.e. differ only in a few bits, the bit-string
    d = r ⊕ s
    consists mostly of zeros. Bitwise x-oring c with d flips a few bits in c, thus having the same effect that could be produced by transmitting c over a noisy channel.
  4. Error correction is applied to recover the random codeword c from c ⊕ d. If desired, c can then be bitwise x-ored with h = c ⊕ r to obtain r.

What this accomplishes is that the same result is consistently produced from the variable sample s, as long as s in not too different from r. Either c or r can be used as the consistent result. Struik uses r, but I believe he could equivalently use c. Hao et al. use c, as their biometric key. In biometric applications, it is important to use c rather than r to avoid revealing the user’s biometric sample r, which could be a privacy violation. The codeword c contains no biometric information.

Juels and Wattenberg [6] used the same technique for implementing fuzzy commitments; as far as I can tell, they were the original inventors of the technique. In a cryptographic commitment scheme, a sender commits to a value by combining it with a witness to produce a blob, and sends the blob to a receiver. The sender can later reveal the value by providing the witness, which the receiver uses to compute the blob and verify that it coincides with the one received earlier. The receiver cannot derive the committed value from the blob without the witness, and only one value, the original committed value, can be successfully revealed by the sender. Juels and Wattenberg used the above technique to devise a fuzzy commitment scheme that tolerates small variations in the witness. With the above notations (different from their own), the committed value is the codeword c, the witness is r, and the blob is an ordered pair consisting of a conventional cryptographic hash of c and the helper data h. When the sender provides s to decommit the value, the receiver computes c as above and verifies that the hash of the computed c coincides with the hash in the blob received from the sender.

In their paper [6], Juels and Wattenberg made the connection with biometric authentication, but not with physical uncloneable functions.

References

[1] Rene Struik. Secure Key Storage and True Random Number Generation – An Overview. NIST Cryptographic Key Management Workshop, September 2012.
 
[2] Francisco Corella and Karen Lewison. Key Management Challenges of Derived Credentials and Techniques for Addressing Them. NIST Cryptographic Key Management Workshop, September 2012.
 
[3] Andrey Belenko. Overcoming iOS Data Protection to Re-enable iPhone Forensics. Black Hat USA, July-August 2011.
 
[4] Jean-Baptiste Bedrune and Jean Sigwald. iPhone data protection in depth. HITB Security Conference, May 2011.
 
[5] Feng Hao, Ross Anderson and John Daugman. Combining Cryptography with Biometrics Effectively. IEEE Transactions on Computers, volume 5, number 9, pages 1081 – 1088, 2006. Available as a Cambridge Computer Laboratory technical report.
 
[6] Ari Juels and Martin Wattenberg. A Fuzzy Commitment Scheme. ACM Conference on Computer and Communications Security, 1999.
 

Report on the NIST Cryptographic Key Management Workshop

This is a belated report on the Cryptographic Key Management Workshop that was held by NIST on September 10-11. Karen Lewison and I went to Washington DC for the workshop, where we presented a talk on techniques for addressing the key management challenges of derived credentials.

Cryptographic key management may seem to be a dry topic, but the workshop was quite interesting, especially the second day, which looked at the future. It was attended by about 50 cryptographers, and was webcast. It began with a fascinating keynote address by Whitfield Diffie on the history of cryptographic key management. His presentation is online, but slides cannot do justice to the wealth of stories and anecdotes that he narrated.

A Framework for Designing Cryptographic Key Management Systems

The main purpose of the workshop was to discuss the current drafts of NIST Special Publication 800-130, and NIST Special Publication 800-152 and solicit comments on them. (Instructions for sending comments on draft NIST publications can be found at http://csrc.nist.gov/publications/PubsDrafts.html.) SP 800-130 is a comprehensive framework of topics that should be considered by anybody who has to specify a Cryptographic Key Management System (CKMS); since key management is an essential aspect of cryptography, the framework should be invaluable to anybody designing a system that incorporates cryptographic functionality. SP 800-152 profiles the framework for cryptographic key management systems that will be used in US Federal agencies, but goes beyond the systems themselves to cover their procurement, installation, management, and operation.

The two publications were discussed during the first day of the workshop. I cannot possibly go over the very detailed discussions that took place, so I will limit myself to repeating one comment I made regarding Section 4.7 of SP 800-130, “Anonymity, Unlinkability and Unobservability”, and expanding upon it.

Anonymity, unlinkability and unobservability are privacy features that may not be directly relevant to the authentication of Federal employees in the course of their work, but they are very relevant to the authentication of both consumers on the Web at large, and citizens who access Federal information systems. Traditional authentication by username and password provides these three privacy features; but passwords have well-known security and usability drawbacks, one of them being the difficulty of remembering many different passwords. One way of reducing the number of passwords to be remembered is to rely on a third-party identity provider (IdP), so that one password (presented to the IdP) can be used to authenticate to any number of relying parties. The Federal Government allows citizens to access government web sites through redirection to several Approved Identity Providers.

But third party login has privacy drawbacks. In usual implementations, anonymity is lost because the relying party learns the user’s identity at the IdP, unlinkability is lost by the use of that identity at multiple relying parties, and unobservability is lost because the IdP is informed of the user’s logins. Profiles of third-party login protocols approved for citizen login to government sites mitigate some of these drawbacks by asking the identity provider to provide different identities for the same user to different relying parties. This mitigates the loss of anonymity, and the loss of unlinkability to a certain extent. (Relying parties by themselves cannot track the user, but they can track the user in collusion with the IdP.) But the loss of unobservability is not mitigated, because the IdP is still informed of the user’s activities.

I believe that the Government should work to develop and promote authentication methods that eliminate passwords while preserving anonymity, unlinkability and unobservability. Cryptographic authentication with a key pair, using different key pairs for different relying parties, can be a basis for such methods.

A Look at the Future

The second day of the workshop featured presentations on capabilities of future cryptographic key management systems, ranging from innovative to futuristic. (Both days’ presentations can be found in the workshop web page.)

Tim Polk, manager of the Cryptographic Technology Group at NIST, motivated the talks that followed by going over challenges identified during the development of the CKMS framework, related to interoperability across security domains, algorithmic agility, constrained devices, privacy, and scalability. He also stressed the need to develop CKMSs that are resilient to quantum computing attacks before it is too late.

Dennis Branstad of NIST discussed security policies, stating as a goal their automated specification, negotiation and enforcement.

Anna Lysyanskaya of Brown University discussed her work on anonymous credentials. She mentioned a new technique for revocation of anonymous credentials that was presented at Crypto 2012 by Libert, Peters and Yung, and said she thought it deserved the best paper award. I believe a full version of the conference paper can be found at http://eprint.iacr.org/2012/442. I haven’t read the paper yet. Revocation of privacy-enhancing credentials is practically difficult; I have discussed the topic in several earlier posts.

Paul Lambert of Marvell Semiconductors discussed authentication and privilege management for devices connected by wireless area networks. I was glad to hear him propose the use of a raw key pair as a credential. I later proposed the same thing in the talk on derived credentials.

Lily Chen of NIST discussed the difficult key management problem of handing over a secure link as a smart phone travels from one network to another, when the networks use technologies that may be as different as UMTS and WiFi.

Sarbari Gupta of Electrosoft discussed key management in a cloud environment. She argued that the Federal Risk and Authorization Management Program (FedRAMP) does not have sufficient requirements for secure key management, and advocated the establishment of a Federal Profile for Cloud Key Management.

Elaine Barker of NIST went over the intricacies and subtleties of random bit generation, and solicited comments on Draft Special Publication 800-90B (entropy sources) and Draft Special Publication 800-90C (RBG Constructions, DRBGs and NRBGs). Comments are due December 3rd.

Rene Struik discussed a method of secure key storage and true random number generation using physical unclonable functions (PUFs). The idea is to use accidental properties of a device to generate a unique key when the device is turned on. (So I would say that his technique is closer to key generation than key storage.) Error correction is used to remove minor differences in subsequent key generations. As an additional benefit, those differences are used for random number generation. This very interesting work is related in multiple ways to our own work on mobile authentication and derived credentials; I plan to discuss it in more detail in the next blog post.

Mary Theofanos of NIST went over two case studies of usability of key management procedures: a PKI deployment, and a PIV pilot. My personal getaways: the designer of a key management system must know the users and their mental models of security; must provide multiple authentication methods, e.g. by retaining username-password as a backup for a cryptographic credential; and must not require frequent PIN changes.

The usability talk was followed by a panel that presented three use cases of cross-domain interactions. Bob Griffin of RSA discussed key management in the cloud. Saikat Saha of SafeNet discussed virtualized hardware security modules. John Leiseboer of Quintessencelabs discussed quantum key distribution; this was the first presentation I’ve attended related to quantum cryptography, and it motivated me to find out more about this futuristic topic.

Derived Credentials

Finally, I gave a presentation on mobile authentication and derived credentials, co-authored with Karen Lewison. Even though this was the last presentation at the end of a long day of talks, I was gratified that, as far as I know, nobody snuck out early to the Dogfish Head brewery across the street from the NIST campus 🙂 . Derived credentials is a NIST concept referring to credentials that, in the future, will be installed in a mobile device after the user of the device authenticates with a PIV card. Our presentation went over three techniques for implementing derived credentials that we proposed earlier in a blog post and a white paper, viz. public key cryptography without certificates, key pair regeneration as an alternative to tamper resistance, and encapsulation of cryptographic and biometric processing in a “prover black box” and a “verifier black box” to insulate app developers from the complexities of cryptography and biometrics.

But we also went beyond derived credentials, in response to a request made by Elaine Barker on behalf of Dennis Branstad before the workshop. We discussed extensions of our techniques, for authentication across security domains, for social login without passwords, and for data protection at rest without tamper resistance. Since then we have put online a whitepaper on the data protection work. We have not yet written whitepapers on authentication across security domain or social login without passwords.

Wrap-up

Tim Polk wrapped up the workshop by encouraging everybody to send comments. Although there is an official comment period for each draft publication, NIST welcomes comments at any time.

Like the workshop on privacy-enhancing technology I attended last year, this workshop was both enjoyable and very useful. I’m glad to be on the email distribution list, and I’m looking forward to the next cryptography workshop at NIST.

Effective Data Protection for Mobile Devices

With iOS 4 Apple introduced a new method for protecting the data stored in an iPhone, an iPad or an iPod when the device is lost or stolen and the user has locked the device with a passcode (usually a 4-digit PIN) [1]. Different categories of data are encrypted under different keys, which are arranged in a key hierarchy. Some of the keys in the hierarchy are derived from the user’s passcode. However, every key that is derived from the passcode is also derived from a hardware key, which is hardwired into the silicon of a “hardware encryption chip” and cannot be extracted from the device by a casual attacker. This means that an attacker who steals a mobile device, opens it, and extracts data encrypted under the passcode cannot mount an offline attack against the passcode. That is, the attacker cannot try passcodes at high speed to find the one that decrypts the data, because trying passcodes requires the hardware key.

But the protection provided by the hardware encryption key, at least in iOS 4 and 5, has been defeated [2] [3] [4]. An attacker who steals an iPhone does not need to open it. The attacker can exploit an OS vulnerability or a firmware vulnerability to run custom code on the device. The custom code can read the encrypted data and, although it cannot extract the hardware key, it can use it to mount an “offline” attack on the device itself. The practical effect of the hardware key is only to force the attacker to run the attack on the CPU of the device, which is relatively slow. But it only takes 40 minutes to try all 4-digit PINs [2].

Would the hardware encryption key provide effective protection if Apple succeeded in eliminating all vulnerabilities that make it possible to run custom code? (It does not seem to have eliminated them in iOS 6, used in the recently released iPhone 5 [5].) An attack would be more difficult, but probably still possible. The attacker would have to open the phone to read the contents of the flash memory. The attacker might be able to not just read but also modify the contents of the flash memory, and thus run custom code, which could then use the hardware key to mount an offline attack against the passcode. The attacker might even be able to probe the silicon of the hardware encryption chip and extract the hardware key. Nobody has claimed to have done any of these fancy attacks, but that’s because exploiting vulnerabilities is much easier.

In the white paper

we have proposed a data protection method for mobile devices that does not require a hardware key, or any tamper resistance, and is effective even if the attacker is able to run custom code on the device. The data is encrypted under a (symmetric) data encryption key that is entrusted to an online server provided by the mobile network operator, or by the mobile device manufacturer, or by the provider of the mobile operating system, or by an independent data protection service provider trusted by the user. (The key can also be split using Shamir’s secret sharing technique into n “portions” entrusted to n different servers, so that k portions are needed to reconstruct the key. For example, with n = 5 and k = 3, portions of the key can be distributed to 5 different servers, and any 3 of those portions can be used to reconstruct the key.)

The key, or the portions of a split key, are retrieved when the user authenticates to unlock the phone, with a PIN, an iris image taken by a camera carried by the device, or both. User authentication regenerates an RSA key pair which the device uses to authenticate to the server(s). When a PIN is used, it is not vulnerable to an offline attack by an attacker who tampers with the phone; and when an iris image is used, no biometric sample or template is stored anywhere.

References

[1] Apple. iOS: Understanding data protection. October 28, 2011.
 
[2] Vladimir Katalov. ElcomSoft Breaks iPhone Encryption, Offers Forensic Access to FileSystem Dumps. March 23, 2011.
 
[3] Andrey Belenko. Overcoming iOS Data Protection to Re-enable iPhone Forensics. 2011.
 
[4] Jean-Baptiste Bedrune and Jean Sigwald. iPhone data protection in depth.
 
[5] Emil Protalinski, The Next Web. The Apple iPhone 5 has reportedly been jailbroken. September 22, 2012.
 

Techniques for Implementing Derived Credentials on Mobile Devices

Update (April 3, 2013). There is a more recent blog post with important new information on the topic of derived credentials.

Update (September 25, 2012). We made a presentation on this topic at the Cryptographic Key Management Workshop that was held on September 10-11 at NIST.

We live in the Age of Mobile, and US Federal agencies, like all enterprises, want their employees to use smart phones and tablets. But they face a serious obstacle: how to authenticate users on mobile devices securely.

As I noted in the previous post, ordinary passwords are even less secure on mobile devices than on desktops and laptops, and one-time passwords provide only limited security because they can be intercepted or observed and they remain valid for several minutes. Authentication of federal employees requires the much stronger cryptographic and biometric security provided by Personal Identity Verification (PIV) smartcards in civilian agencies and Common Access Cards (CAC) in the Department of Defense.

It is difficult to use a smartcard to authenticate a user who is accessing an application on a mobile device. A contactless card could communicate with the device via Near Field Communication (NFC), but some mobile devices, including the iPhone, are not equipped with NFC today. A card reader could communicate with the mobile device via Bluetooth or WiFi, but that requires the user to carry three pieces of equipment: the card, the phone and the card reader.

NIST is working on a better authentication solution: derived credentials, which would provide the same security strength as PIV credentials but would be stored in the mobile device rather than in a separate smartcard. The Electronic Authentication Guideline defines a derived credential as a credential issued based on proof of possession and control of a token associated with a previously issued credential, so as not to duplicate the identity proofing process.

Derived credentials are a very good idea, but they present several challenges. One challenge is the cost of verifying a client certificate chain, in terms of bandwidth, latency and battery life. Another challenge is the lack of tamper resistant storage for credentials and biometric data in mobile devices. Yet another challenge is the complexity of cryptographic and biometric technology, which most app developers are not familiar with.

I believe that these challenges can be addressed using three techniques used in the mobile authentication methods that we described in the white paper

which I summarized in the previous post. We have written another white paper,

that describes each technique separately.

The first technique eliminates the costs associated with verifying client certificate chains by using public key cryptography without certificates. The device demonstrates knowledge of a private key, and the application verifies that the hash of the associated public key matches a field of a device record stored in an enterprise directory. The device record, in turn, contains a reference to a user record, identifying the user as the owner of the device.

The second technique obviates the need for tamper-resistant storage. Tamper-resistant storage is usually needed when a PIN and/or a biometric sample is used to enable the use of a key pair, so that an attacker cannot extract the key pair and use it without providing the PIN and/or the biometric, or extract the biometric template, or mount an offline attack against the PIN. We avoid the need for tamper resistance by regerenating the key pair from the PIN or from a biometric key derived from a biometric sample and an auxiliary string. An attacker who tampers with the device gains no advantage because the only way to know if a regenerated key is the correct one is by using it for online authentication.

The third technique shields app developers from the complexities of cryptography and biometrics by encapsulating the cryptographic and biometric computations in a Prover Black Box, which can be provided as a separate native app on the mobile device, and a Verifier Black Box, which can implemented as a server appliance. The application, which may interact with the user via a browser or via a native front-end, outsources authentication to the black boxes using interapp communication facilities available at least in iOS and Android.

The white paper has figures and more details.

Convenient One-, Two- and Three-factor Authentication for Mobile Devices

Authentication methods used today on mobile devices are both inconvenient and insecure.

Ordinary passwords are difficult to type on small touch-screen displays that require switching keyboards for entering digits or punctuation. They provide even less security on mobile devices than on desktops or laptops. Due to the difficulty of typing on mobile keyboards, each character is prominently displayed after it is typed, circumventing the security provided by password input boxes that displays dots in lieu of characters. And users are motivated to choose shorter and simpler passwords, which have less entropy.

One-time passwords are often used on mobile devices due to the lack of security of ordinary passwords. Authenticating with a one-time password requires entering a PIN, obtaining the one-time password from a hard token, a soft token, a text message, or an email message, and entering the one-time password. This is a very cumbersome procedure. A one-time password is a two-factor authentication method, and is thus more secure than an ordinary password. But they have limited entropy, and they can be replayed within a time-window of several minutes. An attacker who observes or intercepts a one-time password has several minutes during which he or she can use it to log in as the legitimate user.

Social login avoids some of the inconvenience of ordinary and one-time passwords by outsourcing authentication to a social network. If the user is already logged in to the social network, he or she does not have to enter a password again. Current standards for social login are a mess, as I said in the previous post, and as confirmed by the recent resignation of the editor of the OAuth protocol. In the previous post I linked to a white paper where we propose a better social login protocol, SAAAM, well suited for mobile devices.

But while social login is useful in some cases, it is not always appropriate. There is no reason why applications should always rely on social networks to authenticate their users, or why a user should have to surrender his or her privacy to a social network in order to authenticate to an unrelated application. Also, social login does not completely solve the authentication problem, since the user still has to authenticate to the social network.

So there is a need for good authentication methods on mobile devices that do not rely on a third party. We have just written a white paper proposing one-, two- and three-factor authentication methods for mobile devices that provide strong security and are more convenient to use than ordinary or one-time passwords. They are particularly well suited for enterprise use, but are suitable for consumer use as well.

The proposed authentication methods are based on public key cryptography, but they are easy to implement and deploy. They are easy to implement because all cryptography is encapsulated in black boxes, so that developers do not have to program any cryptographic operations. They are easy to deploy because they avoid the use of certificates and do not require a public-key infrastructure.

In our one-factor authentication method the user does not have to provide any input. The device authenticates by demonstrating knowledge of a private key. A hash of the associated public key is stored in a device record, which is linked to a user record in an enterprise directory or user database.

In our two-factor authentication method, the user provides a PIN, which is used to regenerate the key pair. Because any PIN results in a well-formed key pair, the user’s PIN is not exposed to an exhaustive offline guessing attack by an attacker who steals the mobile device, opens it, and reads its persistent memory.

In our three-factor authentication method, the user provides a PIN and a biometric such as an iris scan. No biometric template is stored in the mobile device. Instead, the device contains an auxiliary string that is used in conjunction with the biometric to provide a biometric key. The biometric key is used to regenerate the key pair. The auxiliary string is encrypted by the PIN for additional security.