Algorithm Choice in PKCS#11 (part 1) - RSA in v2.20

Graham Steel
June 12, 2014

Following my post on the security of the algorithms in the W3C Crypto API (our most viewed blog post by far), I thought I'd repeat the exercise for other cryptographic APIs. Here at Cryptosense we do a lot of work with PKCS#11, widely used in applications that use devices like HSMs and smartcards to provide cryptography. How do the algorithms in PKCS#11 measure up?

One problem with PKCS#11 is it hasn't been updated since 2004 (though this is about to change, we'll look at the proposed changes in a future post). The state of the art in cryptanalysis, however, has certainly advanced, to the extent that many of the cryptographic algorithms, or mechanisms proposed in PKCS#11 are now considered broken.There are a lot more mechanisms in PKCS#11 than in the W3C Crypto API, so we'll treat one section of the standard at a time, starting with RSA mechanisms. Below is the summary table

Algorithm/mode Ok legacy Ok future Note
RSAES-PKCS1-v1_5 × × See text
RSASSA-PKCS1-v1_5 × No security proof
RSA-OAEP
RSA-PSS
ISO/IEC 9796 DS1 × × Completely broken, see below
ISO/IEC 9796 DS2 Like RSA-PSS
ISO/IEC 9796 DS3 × See below
X.509 (Raw) RSA × × See text
ANSI X9.31 RSA × Almost identical to RSA PKCS#1v1.5

               

1.2    RSAES-PKCS1-v1_5

Denoted CKM_RSA_PKCS, when used with C_Encrypt, this encryption scheme has been known to be vulnerable to a chosen ciphertext attack (CCA) since 1998. For all the details, see this post, and for references to the cryptanalysis literature see here.

1.3    RSA-OAEP

Denoted CKM_RSA_PKCS_OAEP, used with C_Encrypt this scheme has a security proof of preservation of indistinguishability under chosen ciphertext attacks (IND-CCA, the standard desirable notion of security for an encryption scheme) - for references go here.

1.4    RSASSA-PKCS1-v1_5

When used with C_Sign the CKM_RSA_PKCS mechanism gives a scheme which has no publicly known attacks. However, there are also no security proofs and no advantages compared to other RSA-based schemes such as PSS (below).

An RSA Laboratories memo by Burt Kaliski, dated February 26 2003 states “’While the traditional and widely deployed PKCS #1 v1.5 signature scheme is still appropriate to use, RSA Laboratories encourages a gradual transition to RSA-PSS as new applications are developed.”

1.5    RSA-PSS

Mechanism CKM_RSA_PKCS_PSS has a security proof due to Bellare and Rogaway in the random oracle model.

X509 (Raw)

The CKM_RSA_X_509 mechanism just left-pads the input with zeros and then encrypts (or signs) it. There are various reasons why this is a very bad idea. Taking the case of encryption, one is that identical plaintexts encrypt to the same value. Another is that you might be open to a Chinese remainder theorem attack. Certainly you won't have any security proofs.

Presumably this method was included in PKCS#11 to permit custom padding schemes to be used. To put it mildly, rolling your own padding scheme is highly unlikely to result in a secure scheme.

ISO/IEC 9796

A signature scheme implemented by mechanism CKM_RSA_9796. The latest (3rd, 2010) version of ISO 9796-2 contains three digital signature schemes. The first one (DS1) was shown to be insecure by Coron et al at CRYPTO 2009. The second (DS2) closely resembles RSA-PSS and the third (DS3) vaguely resembles RSA-FDH. The 2013 ENISA report advises against the use of all but the second variant. The PKCS#11 implementation just pads whatever input it is given front and rear by the ISO-9796 padding blocks, so potentially one could use any of the encoding schemes.

What about hash functions

Nowadays to sign a message one first creates a digest. This is generally done with a hash function.PKCS#11 also contains signature mechanisms that calculate the digest, i.e. that take the whole message as input, calculate the digest using a particular inbuilt hash function, and then give the signature. For secure digital signatures the hash function has to be collision-free, otherwise attacks are possible. Collision based attacks have been seen "in the wild" in the Flame malware, which exploited a weakness in MD5. We'll cover the state of the art in cryptanalysis of the hash functions available in PKCS#11 in a future post.

Plug

Cryptosense offers a free whitepaper on PKCS#11 security. Get yours here.