What’s a PKCS-11 attack and how do you prevent it?

By June 30, 2016Blog

SPYRUS Hardware Security Modules Are Not Vulnerable To CVE-2015-5464

SPYRUS is not susceptible to the vulnerabilities described here. Our products only support FIPS-approved KDFs, which use hashing and always use the entire secret, not parts of the secret as described in the vulnerability.

PKCS #11 and HSM Vulnerabilities

The Hardware Security Module (HSM) continues to be a natural choice in combining a physically fortified storage and management locus for digital signature and encryption keys and a wide selection of cryptographic operations in which these sensitive key assets play a vital security role. They provide a secure environment for key generation, storage and destruction, as well as similar services for other important crypto-variables. Their dedicated processors offload host PCs and servers that would otherwise devote bandwidth to these functions under potentially weaker protection.

Linked to these benefits is the vital role of security standards to which these devices are built. Special-purpose standards like FIPS 140-2 and more generic security evaluation standards like the Common Criteria provide assurance that the HSM devices are designed and tested to meet high government and international standards. The PKCS #11 standard is one of the more focused technical standards that specify detailed requirements for standard public-key cryptographic functions and their platform-independent programming interfaces.  In addition to HSMs, a large number of crypto-libraries, software disk encryption systems and OS-pluggable cryptographic systems also adhere to this standard or subsets thereof.

The focus of this note will be on a family of the serious vulnerabilities of HSM implementations of PKCS #11.  While the PKCS #11 has a twenty-year history of use and development in the cryptographic world, it has been found that some far-reaching yet simple attacks are possible in HSM implementations that fully implement it yet facilitate unauthorized disclosure of secret symmetric and private ECC keys.

SafeNet Vulnerabilities

The attack under discussion concerns a SafeNet HSM key-extraction vulnerability discovered by Random Oracle and designated as CVE-2015-5464. To fully understand this attack, some in-depth knowledge of PKCS #11 is useful, but for brevity we will only briefly discuss the sources of the vulnerability. The source blog describes two brute force key guessing attacks that use one or more functional calls (called “mechanisms”) from PKCS-11:

CKM_EXTRACT_KEY_FROM_KEY, a mechanism which provides the capability

of creating one secret key from the bits of another secret key;  And,

CKM_XOR_BASE_AND_DATA, a mechanism

which provides the capability of deriving a secret key by performing a bit XORing of a key pointed to by a base key handle and some data.

As is clear from the above descriptions, these mechanisms are intended to allow the user to construct a new key from previously generated key material. We turn now to their exploitation.

Vulnerability 1

Given: a secret or private key whose value is unknown and cannot be exported by the HSM.

This attack uses CKM_EXTRACT_KEY_FROM_KEY to extract a small sub-key from a secret / private key. It then iterates this process to reconstruct the whole key. This attack works on keys for symmetric algorithms, ECC keys (e.g. ECDSA key), but not RSA, DSA or DH keys. For the latter algorithms, the private key is not a “scalar” from a finite field so the attack does not work.

The Attack: The subkey is taken from a specified offset in the secret/private key and a specified key length (e.g. 2 bytes) then a known plaintext is hashed with HMAC (from a PKCS-11 implementation or other HSM implementation) using the extracted subkey. The initial choice of HMAC subkey would be the 2 most significant bytes of the secret/private key.

The example given in the text is to extract a 2-byte subkey using this mechanism, then hash a known plaintext using the small subkey with HMAC.  Since the subkey is so short, it can take one of only 65,536 different values.  This makes for a very small search space for the brute force attack. Each of the 65,536 values is run through an HMAC of the known plaintext and the result compared with the original HMAC using the “secret” subkey.  When a match is found, the two byte segment of the key is known.  The attack then selects the “next” subkey from the secret/private key using CKM_EXTRACT_KEY_FROM_KEY and gradually reconstructs the whole secret/private key by iterating this process and moving the window of the attack by 2 bytes each time.

Vulnerability 2

This attack uses the second PKCS-11 mechanism CKM_XOR_BASE_AND_DATA in much the same way as the first attack uses HMAC.  The blog describes how the Safenet implementation features actually help the attacker.  When the size of the user chosen data is less than that of the secret key, the output of this mechanism is truncated to the size of the data.  This allows a one-byte attack on each byte of the secret key. The attacker can derive a new HMAC key by XORing successively longer sequences of zero bytes. Only the last segment of the new key uses a brute-force attack.

Solution

SPYRUS HSM and secure token technologies do not implement the PKCS #11 mechanisms described above and do not permit manipulation of previously generated key material to compose new keys.  SPYRUS products use FIPS 140-2 certified Key Derivation Function (KDF) calls to generate keys from random inputs generated from validated digitized random bit generator (DRBG) functions (not previously generated or used key material).  These KDF services are tested and validated to SP 800-56a and SP 800-108 requirements by an accredited laboratory. The KDF mechanisms are FIPS-approved, use FIPS-approved and certified hashing functions, and even if applied to previously generated key material would not permit the above attacks to take place.  The use of strong cryptographic one-way functions in KDF algorithms render it computationally impossible from any practical viewpoint to reconstruct any input to the key generation process.