Protecting Derived Credentials without Secure Hardware in Mobile Devices

NIST has recently released drafts of two documents with thoughts and guidelines related to the deployment of derived credentials,

and requested comments on the drafts by April 21. We have just sent our comments and we encourage you to send yours.

Derived credentials are credentials that are derived from those in a Personal Identity Verification (PIV) card or Common Access Card (CAC) and carried in a mobile device instead of the card. (A CAC card is a PIV card issued by the Department of Defense.) The Electronic Authentication Guideline, SP 800-63, defines a derived credential more broadly 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.

A PIV/CAC card may carry a PIV authentication credential, a digital signature credential, a current key management credential and up to 20 retired key management credentials, each credential consisting of a private key and an associated certificate that contains the corresponding public key. The digital signature private key is used for signing email messages, and the key management keys for decrypting symmetric keys used to encrypt email messages. The retired key management keys are needed to decrypt old messages that have been saved encrypted. The PIV authentication credential is mandatory for all users, while the digital signature credential and the current key management credential are mandatory for users who have government email accounts.

A mobile device may similarly carry an authentication credential, a digital signature credential, and current and retired key management credentials. Although this is not fully spelled out in the NIST documents, the current and retired key management private keys in the mobile device should be able to decrypt the same email messages as those in the card, and therefore should be the same as those in the card, except that we see no need to limit the number of retired key management private keys to 20 in the mobile device. The key management private keys should be downloaded to the mobile device from the escrow server that should already be in use today to recover from the loss of a PIV/CAC card containing those keys. On the other hand the authentication and digital signature key pairs should be generated in the mobile device, and therefore should be different from those in the card.

In a puzzling statement, SP 800-157 insists that only an authentication credential can be considered a “derived PIV credential”:

While the PIV Card may be used as the basis for issuing other types of derived credentials, the issuance of these other credentials is outside the scope of this document. Only derived credentials issued in accordance with this document are considered to be Derived PIV credentials.

Nevertheless, SP 800-157 discusses details related to the storage of digital signature and key management credentials in mobile devices in informative appendix A and normative appendix B.

Software Tokens

The NIST documents provide guidelines regarding the lifecycle of derived credentials, their linkage to the lifecycle of the PIV/CAC card, their certificate policies and cryptographic specifications, and the storage of derived credentials in several kinds of hardware cryptographic modules, which the documents refer to as hardware tokens, including microSD tokens, UICC tokens, USB tokens, and embedded hardware tokens. But the most interesting, and controversial, aspect of the documents concerns the storage of derived credentials in software tokens, i.e. in cryptographic modules implemented entirely in software.

Being able to store derived credentials in software tokens would mean being able to use any mobile device to carry derived credentials. This would have many benefits:

  1. Federal agencies would have the flexibility to use any mobile devices they want.
  2. Federal agencies would be able to use inexpensive devices that would not have to be equipped with special hardware for secure storage of derived credentials. This would save taxpayer money and allow agencies to do more with their IT budgets.
  3. Mobile authentication and secure email solutions used by the Federal Government would be affordable and could be broadly used in the private sector.

The third benefit would have huge implications. Today, the requirement to use PIV/CAC cards means that different IT solutions must be developed for the government and for the private sector. IT solutions specifically developed for the government are expensive, while private sector solutions too often rely on passwords instead of cryptographic credentials. Using the same solutions for the government and the private sector would lower costs and increase security.

Security

But there is a problem. The implementation of software tokens hinted at in the NIST documents is not secure.

NISTIR 7981 describes a software token as follows:

Rather than using specialized hardware to store and use PIV keys, this approach stores the keys in flash memory on the mobile device protected by a PIN or password. Authentication operations are done in software provided by the application accessing the IT system, or the mobile OS.

And SP 800-157 adds the following:

For software implementations (LOA-3) of Derived PIV Credentials, a password-based mechanism shall be used to perform cryptographic operations with the private key corresponding to the Derived PIV Credential. The password shall meet the requirements of an LOA-2 memorized secret token as specified in Table 6, Token Requirements per Assurance Level, in [SP800-63].

Taken together, these two paragraphs seem to suggest that the derived credentials should be stored in ordinary flash memory storage encrypted under a data encryption key derived from a PIN or password satisfying certain requirements. What requirements would ensure sufficient security?

Smart phones are frequently stolen, therefore we must assume that an adversary will be able to capture the mobile device. After capturing the device the adversary can immediately place it in a metallic box or other Faraday cage to prevent a remote wipe. The contents of the flash memory storage may be protected by the OS, but in many Android devices, the OS can be replaced, or rooted, with instructions for doing so provided by Google or the manufacturer. OS protection may be more effective in some iOS devices, but since a software token does not provide any tamper resistance by definition, we must assume that the adversary will be able to extract the encrypted credentials. Having done so, the adversary can mount an offline password guessing attack, testing each password guess by deriving a data encryption key from the password, decrypting the credentials, and checking if the resulting plaintext contains well-formed credentials. To carry out the password guessing attack, the adversary can use a botnet. Botnets with tens of thousands of computers can be easily rented by the day or by the hour. Botnets are usually programmed to launch DDOS attacks, but can be easily reprogrammed to carry out password cracking attacks instead. The adversary has at least a few hours to run the attack before the authentication and digital signature certificates are revoked and the revocation becomes visible to relying parties; and there is no time limit for decrypting the key management keys and using them to decrypt previously obtained encrypted email messages.

To resist such an attack, the PIN or password would need to have at least 64 bits of entropy. According to Table A.1 of the Electronic Authentication Guideline (SP 800-63), a user-chosen password must have more than 40 characters chosen appropriately from a 94-character alphabet to achieve 64 bits of entropy. Entering such a password on the touchscreen keyboard of a smart phone is clearly unfeasible.

SP 800-157 calls instead for a password that meets the requirements of an LOA-2 memorized secret token as specified in Table 6 of SP 800-63, which are as follows:

The memorized secret may be a randomly generated PIN consisting of 6 or more digits, a user generated string consisting of 8 or more characters chosen from an alphabet of 90 or more characters, or a secret with equivalent entropy.

The equivalent entropy is only 20 bits. Why does Table 6 require so little entropy? Because it is not concerned with resisting an offline guessing attack against a password that is used to derive a data encryption key. It is instead concerned with resisting an online guessing attack against a password that is used for authentication, where password guesses can only be tested by attempting to authenticate to a verifier who throttles the rate of failed authentication attempts. In Table 6, the quoted requirement on the memorized secret token is coupled with the following requirement on the verifier:

The Verifier shall implement a throttling mechanism that effectively limits the number of failed authentication attempts an Attacker can make on the Subscriber’s account to 100 or fewer in any 30-day period.

and the necessity of the coupling is emphasized in Section 8.2.3 as follows:

When using a token that produces low entropy token Authenticators, it is necessary to implement controls at the Verifier to protect against online guessing attacks. An explicit requirement for such tokens is given in Table 6: the Verifier shall effectively limit online Attackers to 100 failed attempts on a single account in any 30 day period.

Twenty bits is not sufficient entropy for encrypting derived credentials, and requiring a password with sufficient entropy is not a feasible proposition.

Solutions

But the problem has solutions. It is possible to provide effective protection for derived credentials in a software token.

One solution is to encrypt the derived credentials under a high-entropy key that is stored in a secure back-end and retrieved when the user activates the software token. The problem then becomes how to retrieve the high-entropy key from the back-end. To do so securely, the mobile device must authenticate to the back-end using a device-authentication credential stored in the mobile device, which seems to bring us back to square one. However, there is a difference between the device-authentication credential and the derived credentials stored in the token: the device-authentication credential is only needed for the specific purpose of authenticating the device to the back-end and retrieving the high-entropy key. This makes it possible to use as device-authentication credential a credential regenerated on demand from a PIN or password supplied by the user to activate the token and a protocredential stored in the device, in a way that deprives an attacker who captures the device of any information that would make it possible to test guesses of the PIN or password offline.

The device-authentication credential can consist, for example, of a DSA key pair whose public key is registered with the back-end, coupled with a handle that refers to a device record where the back-end stores a hash of the registered public key. In that case the protocredential consists of the device record handle, the DSA domain parameters, which are (p,q,g) with the notations of the DSS, and a random high-entropy salt. To regenerate the DSA key pair, a key derivation function is used to compute an intermediate key-pair regeneration key (KPRK) from the activation PIN or password and the salt, then the DSA private and public keys are computed as specified in Appendix B.1.1 of the DSS, substituting the KPRK for the random string returned_bits produced by a random number generator.

To authenticate to the back-end and retrieve the high-entropy key, the mobile device establishes a TLS connection to the back-end, over which it sends the device record handle, the DSA public key, and a signature computed with the DSA private key on a challenge derived from the TLS master secret. (Update—April 24, 2014: The material used to derive the challenge must also include the TLS server certificate of the back-end, due to a recently reported UKS vulnerability of TLS. See footnote 2 of the technical report.) The DSA public and private keys are deleted after authentication, and the back-end keeps the public key confidential. An adversary who is able to capture the device and extract the protocredential has no means of testing guesses of the PIN or password other than regenerating the DSA key pair and attempting online authentication to the back-end, which locks the device record after a small number of consecutive failed authentication attempts that specify the handle of the record.

An example of a derived credentials architecture that uses this solution can be found in a technical report.

Other solutions are possible as well. The device-authentication credential itself could serve as a derived credential, as we proposed earlier; SSO can then be achieved by sharing login sessions, as described in Section 7.5 of a another technical report. And I’m sure others solutions can be found.

Other Topics

There are several other topics related to derived credentials that deserve discussion, including the pros and cons of storing credentials in a Trusted Execution Environment (TEE), whether biometrics should be used for token activation, and whether derived credentials should be used for physical access. I will leave those topics for future posts.

Update (April 10, 2014). A post discussing the storage of derived credentials in a TEE is now available.

New Research on Mobile Authentication

This is the first of a series of posts discussing the paper A Comprehensive Approach to Cryptographic and Biometric Authentication from a Mobile Perspective

In the next few posts I will be reporting on research that we have been doing over the last six months related to cryptographic and biometric authentication, focused on mobile devices. I have held off from writing while we were doing the research but now I have a lot to say, so stay tuned.

By the way, in the last six months we have also moved from San Diego to San Jose. I used to work in Silicon Valley, so it’s nice to be back here and renew old friendships. If you are interested in cryptographic and/or biometric authentication and you are based in Silicon Valley or passing by, let me know; I would be happy to meet for coffee and chat.

The starting point of the this latest research was the work we presented at the NIST Cryptographic Key Management workshop last September (Key Management Challenges of Derived Credentials and Techniques for Addressing Them) and at the Internet Identity Workshop last October (New Authentication Method for Mobile Devices), and wrote up in the paper Strong and Convenient Multi-Factor Authentication on Mobile Devices.

In that early work we devised a mobile authentication architecture where the user authenticates with an uncertified key pair, and a method for regenerating an RSA key pair from a PIN and/or a biometric key. The architecture facilitates implementation by encapsulating the complexities of cryptography and biometrics in a Prover Black Box located in the device and Verifier Black Box located in the cloud, while the key pair regeneration method protects the credential against an adversary who captures the user’s mobile device, by preventing an offline attack against the PIN and/or the biometric key. The architecture was primarily intended for mobile devices but could be adapted for use in traditional PCs by means of browser extensions.

The early work left three questions open:

  1. Can the key pair regeneration method be adapted to cryptosystems other than RSA? This question is practically important because RSA can be used for encryption, and is therefore subject to export controls. The export restrictions have been relaxed a lot since the nineties, but they are so complex that consultation with a lawyer may be required to figure out whether and to what extent they are applicable to a particular product.
  2. Can the mobile authentication architecture accomodate credentials other than uncertified key pairs, including public key certificates and privacy-enhancing credentials such as U-Prove tokens and Idemix anonymous credentials? Uncertified key pairs are ideal for returning-user authentication, but they cannot be used to provide evidence that the user is entitled to attributes asserted by authoritative third parties.
  3. Does the architecture support single sign-on (SSO)? SSO is an essential usability feature when multiple frequently used applications require multifactor authentication.

I am happy to report that we have found good answers to all three questions. First, we have found efficient regeneration methods for DSA and ECDSA key pairs; since DSA and ECDSA can only be used for digital signature, they are not subject to export restrictions. Second, we have found a way of extending the architecture to accomodate a variety of credentials, including public key certificates and privacy-enhancing credentials, without giving up on the strong security properties of the original architecture. Third, we found have found two different ways of providing SSO, one of them well suited for web-wide consumer SSO, the other for enterprise SSO; and both applicable to a mix of web-based apps and apps with native front-ends.

An unanticipated result of the research was the discovery of a defense against an adversary who has succeeded in spoofing a TLS server certificate. Spoofing a certificate is difficult, but not unheard of. The defense, which relies on a form of mutual cryptographic authentication, prevents a man-in-the-middle attack and helps the user detect that a server controlled by the adversary is masquerading as a legitimate server using the spoofed certificate.

We have written all this up in a technical whitepaper,

The paper is quite long, because we thought it was important to describe everything in one place, showing how it all fits together. It would be difficult to discuss the entire paper at once, but in the next few posts I will go one by one over some of the topics in the paper; hopefully that will make it easier to discuss each topic. Watch for the next post in a few days.

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.