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

TL;DR

This paper proposes a formally verified method for securely wrapping cryptographic keys using authenticated encryption within the widely-used PKCS#11 standard. It addresses a critical vulnerability in current PKCS#11 implementations that allows attackers to extract keys by exploiting weaknesses in how authenticated encryption is integrated, offering a robust solution that enhances security without sacrificing functionality.

What Problem Does This Paper Address?

The PKCS#11 standard is a cornerstone for securing cryptographic keys in hardware security modules (HSMs), smart cards, and software libraries. Its core promise is to keep sensitive keys separate from potentially vulnerable applications. However, a significant security flaw has been identified: the mechanism for exporting keys (key wrapping), which involves encrypting a key with another, often fails to authenticate the attributes and intended use of the key. This can lead to scenarios where an attacker can manipulate the process to extract keys in the clear, undermining the entire purpose of using a hardware security module. While newer versions of PKCS#11 have introduced authenticated encryption schemes, the interface for using them remains insecure, allowing for attacks like the "two-time pad attack" if not handled carefully. This paper tackles the challenge of designing and formally verifying a secure PKCS#11 configuration that leverages authenticated encryption to provide robust key wrapping and attribute integrity.

Methods

The authors propose a formal model for secure PKCS#11 key wrapping using authenticated encryption with associated data (AEAD). Their approach centers on three key innovations:

  • Key Hierarchy: A static hierarchy where keys can only wrap keys of a lower level, preventing circular dependencies and limiting the impact of compromised keys.
  • Globally Unique Counters: A mechanism to generate unique initialization vectors (IVs) for AEAD schemes, even on devices lacking a random number generator. This is achieved by combining a unique device identifier with a monotonically increasing counter.
  • Handle Authentication: Ensuring that cryptographic handles (references to keys) are authenticated, meaning a handle always refers to the same key regardless of the device or session.

They formally verify their proposed policy using the Tamarin prover, a tool for symbolic analysis of security protocols. This involves defining a symbolic model of cryptography and a deduction system to represent the adversary's capabilities. They also introduce a "deduction soundness" framework, which is a necessary condition for computational soundness, and extend it to AEAD schemes. This framework allows for the composition of security proofs for different cryptographic primitives.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Interface Matters: Simply supporting AEAD schemes in PKCS#11 isn't enough; the API design is crucial. The paper highlights how a flawed interface can negate the security benefits of advanced cryptographic primitives.
  • Authenticated Attributes are Key: The core problem in key wrapping is the lack of authentication for key attributes. By ensuring these attributes are authenticated during wrapping, the proposed policy prevents many existing attacks.
  • Global Uniqueness Without RNG: The paper offers a practical solution for generating unique IVs on low-cost devices that may lack a true random number generator, a significant hurdle for widespread secure AEAD adoption.
  • Formal Verification is Essential: The use of Tamarin and a formal deduction soundness framework demonstrates the rigor required to ensure the security of cryptographic protocols and APIs.

Key Results

The paper presents a formally verified secure PKCS#11 configuration that:

  • Prevents key extraction attacks by ensuring authenticated key wrapping.
  • Provides a mechanism for globally unique IV generation, even on devices without a random number generator.
  • Guarantees handle integrity, ensuring that handles consistently refer to the same key.
  • The formal verification process, conducted using Tamarin, demonstrates the soundness of the proposed policy for AES-GCM/CCM and SIV modes. The paper reports on the number of proof steps and verification times for various lemmas, indicating the feasibility of automated verification.

Limitations and Future Work

The authors acknowledge several limitations:

  • Static Key Hierarchy: The proposed static key hierarchy reduces flexibility in key management.
  • Application Modification: Existing applications need to be modified to leverage handle authentication, though a workaround using CKA_LABEL is discussed.
  • Deduction Soundness vs. Computational Soundness: While deduction soundness is a necessary condition, it doesn't guarantee computational soundness. The composability of computational soundness remains an open research question.
  • Dynamic Corruption: The formalization does not cover dynamic corruption of encryption keys, which could limit the potential damage from wrapping keys that leak.
  • Key Compromise: The model does not explicitly consider key compromise scenarios.

Future work suggested includes extending the formalization to cover dynamic corruption, investigating composable computational soundness, and exploring the resistance against key leakage. The authors also encourage the adoption of their proposed policy and the inclusion of device-internal nonce generation in future PKCS#11 standards.

Summary updated

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\textbackslash\{\}\#11}},
  booktitle = {CSF},
  year = {2019},
  url = {https://openreview.net/forum?id=07su2aBXz3},
}
Figure