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,

• NISTIR 7981, Mobile, PIV, and Authentication, and
• NIST Special Publication 800-157, Guidelines for Derived Personal Identity Verification (PIV) 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.