NIST Omits Encryption Requirement for Derived Credentials

This is Part 2 of a series of posts reviewing the public comments received by NIST on Draft SP800-157, Guidelines for Derived Personal Identity Verification (PIV) Credentials, their disposition, and the final version of the document. Links to all the posts in the series can be found here.

In the first post of this series I discussed how NIST failed to address many concerns expressed in the 400+ comments that it received on the guidelines for derived credentials published in March of last year as Draft Special Publication (SP) 800-157, including concerns about insufficient discussion of business need, lack of guidance, narrow scope, lack of attention to embedded solutions, and security issues. But I postponed a discussion of what I think is the most critical security problem in SP800-157: the lack of security of the so-called software tokens, a concern that was raised in comments including 111 by the Treasury, 291, 311 and 318 by ICAMSC, 406 by PrimeKey AB, 413 by NSA, and 424 by Exponent. This post focuses on that problem.

The concept of a software token, or software cryptographic module is defined in Draft NISTIR 7981 (Section 3.2.1) 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.

What does it mean for the keys to be “protected by a PIN or password“?
Continue reading “NIST Omits Encryption Requirement for Derived Credentials”

NIST Fails to Address Concerns on Derived Credentials

This is the first of a series of posts reviewing the comments received by NIST on Draft SP800-157, their disposition, and the final version of the document. Links to all the posts in the series can be found here.

In March 2014, NIST released the drafts of two documents on derived credentials, Draft NISTIR 7981 and Draft SP800-157, and requested comments. Last month it announced that it had received more than 400 comments and released a file with comments and their dispositions.

The file is hard to read, because it contains snippets of comments rather than entire comments (and snippets of comments by the same organization are not always consecutive!). But we have made the effort to read it, and the effort was worth it. The file contains snippets from companies, individuals, industry organizations, and many US Federal government organizations, including the Consumer Financial Protection Bureau (CFPB), the Coast Guard, the Department of Justice (DOJ), the Department of the Treasury, the Department of Agriculture Mobility Program Management Office (USDA MPO), the Department of State (DOS) the Social Security Administration (SSA), the National Aeronautics and Space Administration (NASA), the Department of Homeland Security (DHS), the Air Force Public Key Infrastructure System Program Office (AF PKI SPO), the Identity, Credential, and Access Management Subcommittee (ICAMSC), the Centers for Disease Control and Prevention (CDC), the Federal Public Key Infrastructure Certificate Policy Working Group (FPKI CPWG) and the Information Assurance Directorate of the National Security Agency (NSA). Continue reading “NIST Fails to Address Concerns on Derived Credentials”

Implementing Virtual Tamper Resistance without a Secure Channel

Last week I made a presentation to the GlobalPlatform 2014 TEE Conference, co-authored with Karen Lewison, on how to provide virtual tamper resistance for derived credentials and other data stored in a Trusted Execution Environment (TEE). I’ve put the slides online as an animated PowerPoint presentation with speaker notes.

An earlier post, also available on the conference blog, summarized the presentation. In this post I want to go over a technique for implementing virtual tamper resistance that we have not discussed before. The technique is illustrated with animation in slides 9 and 10. The speaker notes explain the animation steps.

Virtual tamper resistance is achieved by storing data in a device, encrypted under a data protection key that is entrusted to a key storage service and retrieved from the service after the device authenticates to the service using a device authentication credential, which is regenerated from a protocredential and a PIN. (Some other secret or combination of secrets not stored in the device can be used instead of a PIN, including biometric samples or outputs of physical unclonable functions.) The data protection key is called “credential encryption key” in the presentation, which focuses on the protection of derived credentials. The gist of the technique is that all PINs produce well-formed device authentication credentials, Continue reading “Implementing Virtual Tamper Resistance without a Secure Channel”

Smart Cards, TEEs and Derived Credentials

This post has also been published on the blog of the GlobalPlatform TEE Conference.

Smart cards and mobile devices can both be used to carry cryptographic credentials. Smart cards are time-tested vehicles, which provide the benefits of low cost and widely deployed infrastructures. Mobile devices, on the other hand, are emerging vehicles that promise new benefits such as built-in network connections, a built-in user interface, and the rich functionality provided by mobile apps.

Derived Credentials

It is tempting to predict that mobile devices will replace smart cards, but this will not happen in the foreseeable future. Mobile devices are best used to carry credentials that are derived from primary credentials stored in a smart card. Each user may choose to carry derived credentials on zero, one or multiple devices in addition to the primary credentials in a smart card, and may obtain derived credentials for new devices as needed. The derived credentials in each mobile device are functionally equivalent to the primary credentials, and are installed into the device by a device registration process that does not need to duplicate the user proofing performed for the issuance of the primary credentials.

The term derived credentials was coined by NIST in connection with credentials carried by US federal employees in Personal Identity Verification (PIV) cards and US military personnel in Common Access Cards (CAC); but the concept is broadly applicable. Derived credentials can be used for a variety of purposes, Continue reading “Smart Cards, TEEs and Derived Credentials”

Forthcoming Presentation at the GlobalPlatform TEE Conference

I’m happy to announce that I’ll be making a presentation at the forthcoming GlobalPlatform 2014 TEE Conference (September 29-30, Santa Clara, CA). Here are the title and abstract:

Virtual Tamper Resistance for a TEE

Derived credentials are cryptographic credentials carried in a mobile device that are derived from credentials carried in a smartcard. The term was coined by the US National Institute of Standards and Technology (NIST) in connection with US Federal employee credentials, but the concept is generally applicable to use cases encompassing high-security enterprise IDs, payment cards, national identity cards, driver licenses, etc.

The Trusted User Interface feature of a TEE can protect the passcode that activates derived credentials from being phished or intercepted by malware, the user being instructed to only enter the passcode when a Security Indicator shows that the touchscreen is controlled by the Secure OS of the TEE. Besides protecting the passcode, it is also necessary to protect the derived credentials themselves from an adversary who physically captures the device. This requires resistance against tampering. Physical tamper resistance can be provided by a Secure Element accessed from the TEE through the TEE Secure Element API, thus combining protection of the passcode against malware with protection of the credentials against physical capture.

Derived credentials can also be protected against physical capture using cloud-based virtual tamper resistance, which is achieved by encrypting them with a key stored in a secure back-end. The device uses a separate credential derived in part from the activation passcode to authenticate to the back-end and retrieve the encryption key. A novel technique makes it possible to do so without exposing the passcode to an offline guessing attack, so that a short numeric passcode is sufficient to provide strong security.

Physical tamper resistance and virtual tamper resistance have overlapping but distinct security postures, and can be combined, if desired, to maximize security.

Identity-Based Protocol Design Patterns for Machine-to-Machine Secure Channels

Cryptography is an essential tool for addressing the privacy and security issues faced by the Web and the Internet of Things. Sadly, however, there is a chronic technology transfer failure that causes important cryptographic techniques to be underutilized.

An example of an underutilized technique is Identity-Based Cryptography. It is used for secure email, although not broadly. But, to my knowledge, it has never been used to implement secure channel protocols, even though it has the potential to provide great practical advantages over traditional public key infrastructure if put to such usage. We pointed this out in our white paper on TLS. Now we have also shown the benefits of identity-based cryptography for machine-to-machine communications, in a new paper that we will present at the Workshop on Security and Privacy in Machine-to-Machine Communications (M2MSec, San Francisco, October 29, 2014). Machine-to-machine communications fall into many different use cases with very different requirements. So, instead of proposing one particular technique, we propose in the paper four different protocol design patterns that could be used to specify a variety of different protocols.

Update (August 4). I should point out that there is a proposal to use Identity-Based authenticated key exchange in conjunction with MIKEY (Multimedia Internet KEYing), a key management scheme for SRTP (Secure Real-Time Transport Protocol), which itself is used to provide security for audio and video conferencing on the Internet. The proposed authenticated key exchange protocol is called MIKEY-IBAKE and is described in RFC 6267. This is an informational RFC rather than a standards-track RFC, so it’s not clear if the proposed authenticated key exchange method will be eventually deployed. Interestingly, MIKEY-IBAKE uses identity-based encryption rather than identity-based key agreement. This is also what we do in the M2MSec paper, but with a difference. MIKEY-IBAKE uses identity-based encryption to carry ephemeral Elliptic Curve Diffie-Hellman parameters, and thus does not reduce the number of roundtrips. We use identity-based encryption to send a secret from the initiator to the responder, and we eliminate roundtrips by simultaneously sending application data protected with encryption and authentication keys derived from the secret. This gives up replay protection and forward secrecy for the first message; but replay protection, as well as forward secrecy in two of the four patterns, are provided from the second message onward.

Invited Talk at the University of Utah

I’ve been so busy that I haven’t had time to write for more than three months, which is a pity because things have been happening and there is much to report. I’m trying to catch up today.

The first thing to report is that Prof. Gopalakrishnan of the University of Utah invited Karen Lewison and myself to give a joint talk at the University, on May 29. We talked about the need to replace TLS, which I’ve discussed earlier on this blog. The slides can be found at the usual location for papers and presentations at the bottom of each page of this web site.

The University of Utah has a renowned School of Computing and it was quite stimulating to meet with faculty and discuss research after the talk. We were happy to discover common research interests, and we have been exploring the possibility of doing joint research work with Profs. Ganesh Gopalakrishnan, Sneha Kasera, and Tammy Denning; we are thrilled that the prospects look promising.

Other things to report include that we had papers accepted at the forthcoming M2MSec workshop and the forthcoming GlobalPlatform TEE conference. I will report on that in the next two posts.

Patent Illustrates Five Different Problems with Software Patents

I recently looked at a patent issued last January in the area of secure messaging, US 8,625,805. It uses the term “Digital Security Bubble” (the title of the patent) to refer to a concept which, in my opinion, is no different from the concept of digital envelope or enveloped data found in RFC 5652 (Cryptographic Message Syntax) or the earlier RFC 2315 (PKCS #7). I posed a question on Ask Patents, asking what could be done to challenge the patent short of obtaining a Post Grant Review, which would cost $30,000 or more just in USPTO fees (including a $12,000 request fee and a $18,000 post-institution fee for challenging up to 15 claims, plus $250 for each additional claim being challenged beyond 15). Phoenix88 suggested submitting prior art under 37 CFR 1.501 and 35 USC 301, which requires no fee. Following his advice, I studied the patent in detail and I have submitted as prior art PKCS #7 as well as RFC 1422, an RFC related to Privacy Enhanced Mail (PEM) that PKCS #7 relies upon. If the USPTO accepts the submission, it will be entered into the patent file. In the meantime, it can be found online on the Pomcor site.

But the reason I’m writing this post is that US patent 8,625,805 can serve to identify and illustrate five different problems with software patents, some well known, some that may not have been identified before. Here are those five problems.

1. The Vocabulary Problem

Whereas disciplines such as medicine, biology, chemistry and the various branches of engineering have developed mature and well-established vocabularies for their subject matters, software engineers like to invent their own fanciful vocabulary as they go. Think for example of the invention of the term cookie by Netscape to refer to a data item that stores server state in an HTTP client.

Inventing a new term is justified when the term is applied to a new concept, or when existing terminology is inadequate. But it is deplorable when there exists adequate terminology for the same concept.

Creation of unnecessary terminology may be due to ignorance of existing terminology. But in their comments on prior art resources, which can be found in a USPTO web page, Public Knowledge, the Electronic Frontier Foundation and Engine Advocacy have said that “applicants are able to use invented terminology in order to avoid prior art.” Without judicial discovery it is not possible to tell whether the term “digital security bubble” was used in US 8,625,805 instead of “digital envelope” for the purpose of obfuscation, or simply because the inventors were not familiar with standard secure messaging terminology.

The lack of stable and broadly accepted terminology drastically reduces the ability to find relevant documents by keyword search, i.e. it reduces what is known as recall in information retrieval. The patent file of US 8,625,805 includes a Search Strategy entry (SRNT) showing that 13 out of 26 prior art search queries contained the keyword “bubble”; the useless keyword “bubble” thus took up 50% of the time and effort spent by the examiner on keyword search. (The search strategy entry can be found using the Image File Wrapper tab in the Public Patent Application Information Retrieval tool — Public PAIR — of the USPTO.)

Besides poor recall, keyword searches of software literature also suffer from the opposite problem, poor precision. This is due to the fact that some popular words are used for many different purposes. The word token, for example, has a large number of different meanings. The combination of poor recall and poor precision means that keyword search is not well suited to finding prior art relevant to software patent applications.

The USPTO has launched a Glossary Pilot that provides incentives for applicants to include a glossary section in the specification. While a glossary section may be useful for other purposes, it does not prevent or discourage the use of non-standard terminology.

2. The Search Corpus Problem

The second problem with software patents has to do with the databases that examiners use to search for prior art.

Although the Search Notes entry (SRFW) in the patent file of US 8,625,805 indicates that the examiner did some Non-Patent Literature (NPL) searching, all 26 queries documented in the Search Strategy entry (SRNT) were run on patent literature databases. Since few software patents were granted or applied for before the late nineties, documentation of fundamental software inventions such as secure messaging, cannot be found in the patent literature.

3. Lack of “Full, Clear, Concise and Exact” Descriptions

A patent is supposed to embody a quid pro quo: the inventor gets a monopoly on the use of the invention, and in exchange discloses the invention so that the public can use it once the patent has expired. The inventor’s side of the bargain is codified in 35 USC 112(a):

The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.

But too often, software patents make claims without providing a “full, clear, concise and exact description” of what is being claimed. Claim 15 of US 8,625,805 is a good example. Here is the claim:

15. The system of claim 1 wherein the processor is configured to perform the encapsulation at least in part by performing a spreading function.

And here is what the specification has to say on what it means to “perform the encapsulation at least in part by performing a spreading function”:

In some embodiments (e.g., as is shown in FIG. 5), a spreading function is used to spread the encrypted symmetric keys inside the DSB (as shown in region 512), by spreading the bits of the encrypted key in a spreading function generated pattern, with the default function being a sequential block or data. The spreading function also contains the cryptographic hashed representation of the recipient usernames that are used by the server to identify the recipients of the message and to set the message waiting flag for each of them.

I don’t understand this at all, and FIG. 5 does not help. If you understand it and would like to explain it in a comment, I would appreciate it.

Lack of compliance with 35 USC 112(a) seems to be a common problem. Software engineers often complain that software patents are incomprehensible. Sometimes, software engineers do not even understand their own patents, written up by patent attorneys:

Against my better judgement, I sat in a conference room with my co-founders and a couple of patent attorneys and told them what we’d created. They took notes and created nonsensical documents that I still can’t make sense of.

A “person skilled in the art” of software is called a software engineer or a software developer. Hence patents that are incomprehensible to software engineers, by definition, do not comply with 35 USC 112(a). Unfortunately, the USPTO does not seem to be keen on enforcing compliance with 35 USC 112(a). Sometimes I wonder if examiners read the patent specification at all, or only read the claims.

4. The Means-or-Step-Plus-Function Problem for Security Claims

US 8,625,805 also illustrates a tricky problem specific to security claims. Here is claim 16:

16. The system of claim 1 wherein only a designated recipient, having a device with applicable device characteristics, is able to decrypt the message.

I believe this claim is objectionable under 35 USC 112(b) because it does not point out any subject matter. It should have been written in means-plus-function form, e.g. “the system of claim 1, further comprising a means of preventing the decryption of the message other than by a designated recipient having a device with applicable characteristics,” with “means” referring to the following portions of the specification:

At 208, a device identifier (“deviceID”) is created from captured hardware information. Examples of captured hardware information include: hard drive identifiers, motherboard identifiers, CPU identifiers, and MAC addresses for wireless, LAN, Bluetooth, and optical cards. Combinations of information pertaining to device characteristics, such as RAM, CACHE, controller cards, etc., can also be used to uniquely identify the device. Some, or all, of the captured hardware information is run through a cryptographic hash algorithm such as SHA-256, to create a unique deviceID for the device. The captured hardware information can also be used for other purposes, such as to seed cryptographic functions.

FIG. 10 illustrates an example of a process for accessing a message included inside a digital security bubble. In some embodiments, process 1000 is performed on a client device, such as Bob’s client device 114. The process begins at 1002 when a DSB is received. As one example, a DSB is received at 1002 when app 138 contacts platform 102, determines a flag associated with Bob’s account has been set, and downloads the DSB from platform 102. In such circumstances, upon receipt of the DSB, client 114 is configured to decrypt the DSB using Bob’s private key (e.g., generated by Bob at 202 in process 200).

At 1004 (i.e., assuming the decryption was successful), hardware binding parameters are checked. As one example, a determination is made as to whether device information (i.e., collected from device 114) can be used to construct an identical hash to the one included in the received DSB. If the hardware binding parameters fail the check (i.e., an attempt is being made to access Alice’s message using Bob’s keys on a device that is not Bob’s), contents of the DSB will be inaccessible, preventing the decryption of Alice’s message. If the hardware binding parameter check is successful, the device is authorized to decrypt the symmetric key (i.e., using Bob’s private key generated at 202) which can in turn be used to decrypt Alice’s message.

This is very vague, and I don’t think it qualifies as a full, clear, concise, and exact description. But the gist of it seems to be that an encrypted message is accompanied by a hash of hardware parameters of a destination device. When the message is received, an app checks whether the hash matches a hash of the hardware parameters of the device where the app is running. If the check fails, the app refuses to decrypt the message.

The point I really want to make, however, is that this method of “hardware binding” does not work. An adversary who has Bob’s private key is not prevented from decrypting the message on a device other than Bob’s device just because an app on Bob’s device is programmed to check the hash of hardware parameters. The adversary can do anything he or she wants on his or her own device. The adversary can, for example, use an app that behaves the same as the app used by Bob except that it omits the check.

This illustrates an important point, specific to security claims, that I have not seen discussed before. It is practically impossible to verify that a means-or-step-plus-function claim is supported by the specification, if the function being claimed is to achieve a security goal. It may be easy to see that a claim like the above is NOT supported. But establishing that a security claim IS supported would require writing and verifying a mathematical proof that the security goal is achieved based on a mathematical model of the a system described in the specification, something which is theoretically possible but not realistically achievable today. Furthermore the statement of the goal would have to be probabilistic, since security is rarely absolute.

This is important because allowing a security claim supported by a description of a technique that does not work does a lot of damage. Somebody else may later invent a technique that does work. Then the person who has been granted a patent on the security claim based on the technique that does not work will be able not only to prevent the person who has found the technique that works from obtaining a patent, but also to prevent everybody from using the technique that works.

5. A Loophole for Avoiding Third-Party Preissuance Submissions

The America Invents Act (AIA) has introduced Preissuance Submissions of Prior Art, which allow third parties to submit prior art to the examiners, and the USPTO is keen on crowdsourcing access to prior art. This a is good thing. But US 8,625,805 avoided third-party scrutiny because the application underwent a Prioritized, a.k.a. Track I, Examination and, like many Track I applications, was not published until granted. (The fact that US 8,625,805 was a Track I patent was noted by George White in a comment on Ask Patents.)

Prioritized Examination, which requires an additional fee of $2,000 for a small entity, has the effect of shortening the waiting time before an examiner takes up the application from years to a few months. Before AIA this was already an extremely unfair and undemocratic procedure, shortening the process for corporations and rich inventors who could afford it while lengthening it for everybody else. Now, after AIA, it can also be used as a loophole to shield those who can afford the fee from third party submissions of prior art, making it easier for them to obtain low quality and overly broad patents which they can inflict on society.

A second loophole for preventing preissuance submission is simply for the applicant to request non-publication of the application. This loophole costs nothing, but it precludes filing in foreign countries that require publication.

More generally, preissuance submission must take place after pre-grant publication, so there can be no preissuance submission if there is no pre-grant publication. The above loopholes prevent preissuance submission by eliminating pre-grant publication. But pre-grant publication may also fail to take place in the normal course of business. By default, it takes place no earlier than 18 months after the earliest benefit date. If the application does not claim the benefit of any earlier application, in an ideal world the USPTO should be able to examine it in less than 18 months, in which case there would be no pre-grant publication, and hence no possibility of preisssuance submission.

Since the 18 months delay in publication and the non-publication request provision are statutory, allowing preissuance submission for all applications requires a change in the law. Since preissuance submission is essential for improving the quality of software patents, such a change is badly needed. I would suggest introducing a minimum 3-month time period between publication and allowance. A request for non-publication would hold publication in abeyance until the examiner thinks the claims are allowable; but then the application would be published and open to preissuance submission of prior art and comments for three months before actual allowance.

While waiting for legislation to be enacted, the Post-Grant Review fees should be drastically reduced, and the onerous requirements on Post-Grant Review petitions should be simplified so that it is not necessary to hire a patent lawyer to file a petition.


The problem of poor quality software patents is difficult and multi-faceted, and many ideas have been proposed for addressing it. Here I would just like to make a few suggestions related to the above observations.

  • Prioritized Examination should be eliminated.
  • The Post Grant Review request fee should be no greater than the Appeal Forwarding fee for a small entity ($1,000). There should be no post-institution fee and no per-claim fee, and a refund of 50% of the request fee should be given if the request is found to have merit and the review is granted.
  • Examiners of software patents should be instructed to direct at least half of their search efforts towards non-patent literature, and to document the non-patent literature queries that they run. Some searchable sources of non-patent literature have been suggested by others in comments on prior art resources. I would add the collection of IETF RFCs and Internet Drafts, which can be searched by restricting a web search to the site
  • In addition to crowdsourcing the search for prior art, the USPTO should accept and encourage comments by persons skilled in the art, such as software engineers in the case of software patents, on whether specifications are comprehensible, provide a full, clear, concise, and exact description of the invention, and support the claims.
  • The specification of every patent application containing one or more means-or-step-plus-function claims should be required to contain a separate section explaining in detail how each claimed function is provided. This will not guarantee that every security goal asserted by a means-or-step-plus-function claim is achieved by the invention, but it will at least help third-party reviewers and examiners to identify unsupported claims.

The USPTO has requested comments on “The Use of Crowdsourcing and Third-Party Preissuance Submissions To Identify Relevant Prior Art,” and more generally on “ways the Office can use crowdsourcing to improve the quality of examination.” They are due by April 25. We are sending ours. Please consider sending yours.

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.


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.


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.

It’s Time to Redesign Transport Layer Security

One difficulty faced by privacy-enhancing credentials (such as U-Prove tokens, Idemix anonymous credentials, or credentials based on group signatures), is the fact that they are not supported by TLS. We noticed this when we looked at privacy-enhancing credentials in the context of NSTIC, and we proposed an architecture for the NSTIC ecosystem that included an extension of TLS to accommodate them.

Several other things are wrong with TLS. Performance is poor over satellite links due to the additional roundtrips and the transmission of certificate chains during the handshake. Client and attribute certificates, when used, are sent in the clear. And there has been a long list of TLS vulnerabilities, some of which have not been addressed, while others are addressed in TLS versions and extensions that are not broadly deployed.

The November SSL Pulse reported that only 18.2% of surveyed web sites supported TLS 1.1, which dates back to April 2006, only 20.7% supported TLS 1.2, which dates back to August 2008, and only 30.6% had server-side protection against the BEAST attack, which requires either TLS 1.1 or TLS 1.2. This indicates upgrade fatigue, which may be due to the age of the protocol and the large number of versions and extensions that it has accumulated during its long life. Changing the configuration of a TLS implementation to protect against vulnerabilities without shutting out a large portion of the user base is a complex task that IT personnel is no doubt loath to tackle.

So perhaps it is time to restart from scratch, designing a new transport layer security protocol — actually, two of them, one for connections and the other for datagrams — that will incorporate the lessons learned from TLS — and DTLS — while discarding the heavy baggage of old code and backward compatibility requirements.

We have written a new white paper that recapitulates the drawbacks of TLS and discusses ingredients for a possible replacement.

The paper emphasizes the benefits of redesigning transport layer security for the military, because the military in particular should be very much interested in better transport layer security protocols. The military should be interested in better performance over satellite and radio links, for obvious reasons. It should be interested in increased security, because so much is at stake in the security of military networks. And I would argue that it should also be interested in increased privacy, because what is viewed as privacy on the Internet may be viewed as resistance to traffic analysis in military networks.