How to Wrap it up - A Formally Verified Proposal for the use of Authenticated Wrapping in PKCS#11

Alexander Dax, Robert Künnemann, Sven Tangermann, Michael Backes

Introduction

PKCS#11 is the industry standard for Hardware Security Modules (HSMs), cryptographic tokens, and smart cards. Designed to keep cryptographic keys in a secure vault separate from the application, it ideally ensures that keys never appear in the clear. However, PKCS#11 has long been vulnerable to "logical attacks"—exploits that use flawed API calls to leak secret keys. This paper proposes a new, formally verified configuration that leverages Authenticated Encryption with Associated Data (AEAD) to secure key wrapping, providing a more functional and robust defense than previous proposals.

The Challenge of Key Wrapping

The primary security concern in HSMs is key wrapping: the process of encrypting a key so it can be exported or migrated. Historically, attackers have tricked HSMs into unwrapping keys with incorrect attributes, such as converting a non-exportable key into one that can be decrypted. While version 2.40 of the standard introduced AEAD to mitigate this, the implementation allowed users to set their own Initialization Vectors (IVs). This opened the door to "two-time pad" attacks, where IV reuse reveals the underlying key material.

A Formally Verified Policy

The authors propose a new policy based on three core pillars to eliminate these vulnerabilities:

  1. Key Hierarchy: Keys are assigned numerical levels. A key can only wrap or unwrap keys of a strictly lower level, preventing circular dependencies and "Trojan key" attacks.
  2. Handle Integrity: The key's identifier (handle) is unique and authenticated alongside the key material during wrapping.
  3. Binding Attributes: By using the "Associated Data" (AD) component of AEAD, the policy binds metadata—like levels and handles—to the ciphertext. If an attacker attempts to modify a key's permissions during transit, the authentication check fails.
Table 1: Proposed PKCS#11 function policy and security rules.

Securing Initialization Vectors

To address the IV reuse problem, especially on low-cost devices lacking a reliable Random Number Generator (RNG), the authors propose a deterministic IV construction. This method uses a unique device ID and a monotonic counter to ensure every IV is globally unique. This approach allows even simple tokens to participate in a secure global key-management system without the risks associated with manual IV selection.

Figure 1: Deterministic IV construction using monotonic counters to prevent IV reuse.

Verification and Impact

The proposed policy was verified using the Tamarin Prover, a tool for symbolic functional verification. The authors also extended the deduction soundness framework to provide a mathematical bridge, ensuring their symbolic proofs hold against real-world computational attackers.

Key results include:

  • Increased Functionality: Unlike previous "secure" configurations that often disabled key movement entirely, this policy allows for complex key management while maintaining safety.
  • Automated Proofs: Security properties (secrecy, integrity, and IV uniqueness) were verified in minutes on a standard laptop.
  • Theoretical Contribution: The paper provides the first formal proof for the deduction soundness of deterministic authenticated encryption.

Conclusion

By mandating internal IV generation and binding metadata through AEAD, this proposal transforms the IV problem from a mathematical risk into a manageable policy. While implementing this requires disabling some legacy PKCS#11 functions, it offers a provably secure path forward for the next generation of hardware security standards.

Summary updated

Abstract

Being the most widely used and comprehensive standard for hardware security modules, cryptographic tokens and smart cards, PKCS#11 has been the subject of academic study for years. PKCS#11 provides a key store that is separate from the application, so that, ideally, an application never sees a key in the clear. Again and again, researchers have pointed out the need for an import/export mechanism that ensures the integrity of the permissions associated to a key. With version 2.40, for the first time, the standard included authenticated deterministic encryption schemes. The interface to this operation is insecure, however, so that an application can get the key in the clear, subverting the purpose of using a hardware security module. This work proposes a formal model for the secure use of authenticated deterministic encryption in PKCS#11, including concrete API changes to allow for secure policies to be implemented. Owing to the authenticated encryption mechanism, the policy we propose provides more functionality than any policy proposed so far and can be implemented without access to a random number generator. Our results cover modes of operation that rely on unique initialisation vectors (IVs), like GCM or CCM, but also modes that generate synthetic IVs. We furthermore provide a proof for the deduction soundness of our modelling of deterministic encryption in Böhl et.al.'s composable deduction soundness framework.
BibTeX
@inproceedings{dax2019how,
  author = {Alexander Dax and Robert Künnemann and Sven Tangermann and Michael Backes},
  title = {{How to Wrap it up - A Formally Verified Proposal for the use of Authenticated Wrapping in PKCS\#11}},
  booktitle = {CSF},
  year = {2019},
  url = {https://openreview.net/forum?id=07su2aBXz3},
}
Figure