Choice of Algorithms in the W3C Crypto API

Graham Steel
June 3, 2014

Cryptography is a small but important part of security, and choosing the right cryptographic algorithm is a small but important part of deploying cryptography. As part of some recent work I've been reviewing the cryptographic algorithms slated for inclusion in the W3C Crypto API, currently in last call. Fortunately, there are already a number of papers surveying the state of the art in cryptoanalysis of deployed algorithms, including the ENISA annual report on algorithms and key lengths (taking over form the old ECRYPT survey). There is also Rogaway's comprehensive block cipher mode survey from 2011. Unfortunately, some methods proposed by the W3C TC don't appear in either document, but tracking down the state of the art results for these was an interesting task. For the TL/DR, here's a table summarizing the findings:

1   Summary Table

The marks for legacy and future applications are the same as in the 2013 ENISA report [20], except for those algorithms (PBKDF2 and AES-KW) which are not covered by the report where the marks represent my interpretation of the available literature. Scroll below the table for the full details.  

Algorithm/mode Ok legacy Ok future note
RSAES-PKCS1-v1_5 × × See text
RSA-OAEP
RSASSA-PKCS1-v1_5 × No security proof
RSAS-PSS
ECDSA × Weak provable security results
ECDH
AES-CBC NB not CCA secure
AES-CFB NB not CCA secure
AES-CTR NB not CCA secure
AES-GCMtd> /td>
AES-CMAC
AES-CFB NB not CCA secure
AES-KW × No public security proof
HMAC
DH
SHA-1 × See text
SHA-256
SHA-384
SHA-512
CONCAT
HKDF-CTR
PBKDF2 × Known weaknesses (see text)

1.2    RSAES-PKCS1-v1_5

This encryption scheme has been known to be vulnerable to a chosen ciphertext attack (CCA) since 1998 [5]. The attack has recently been improved to require a median of less than 15 000 chosen ciphertexts on the standard oracle  [1]. Instances of the attack in widely-deployed real-world systems continue to be found [8].

Since version 2.0 (September 1998), the RSA PKCS#1 standard contains the text: “RSAES- PKCS1-v1_5 is included only for compatibility with existing applications, and is not recommended for new applications.” [19].

TLS up to version 1.2. supports RSAES-PKCS1-v1_5, but using specific countermeasures that 1) substitute a message with a random value in the event of a padding error and 2) require the client to display knowledge of the plaintext before proceeding with the protocol. These countermeasures are not trivially transposable to other applications. Finally, note also that as of version 1.3, RSAES-PKCS1-v1_5 will be dropped from the TLS standard.

UPDATE

As of 16th June 2014 RSA PKCS#1v1.5 Encryption has been removed from the W3C Crypto API spec.

1.3    RSA-OAEP

Has a security proof of preservation of indistinguishability under chosen ciphertext attacks (IND-CCA, the standard desirable notion of security for an encryption scheme)  [7]. Indeed, the proof has been formalised in the Coq proof assistant [2]. These proofs assume that a well-known implementation pitfall leading to an efficient attack  [13] is avoided.

1.4    RSASSA-PKCS1-v1_5

There are no publicly known attacks on this scheme. However, there are also no security proofs and no advantages compared to other RSA-based schemes such as PSS (below)  [20].

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

Has a security proof due to Bellare and Rogaway [4] in the random oracle model.

1.6    ECDSA

ECDSA schemes have some provable security results but only in weak models  [20]. Further it may be possible to maliciously choose an elliptic curve for ECDSA despite the standard validation scheme [22].

1.7    ECDH

ECDH has provable security results [6]. Like other plain DH modes it offers no authenticity, this must be taken care of separately.

1.8    AES-CBC, AES-CFB, AES-CTR

There are known cryptanalytic attacks on AES that are not currently believed to pose a practical threat [10]. The following results assume that AES is a secure block cipher.

AES-CBC mode is not CCA secure. It is secure against chosen plaintext attacks (CPA-secure) if the IV is random, but not if the IV is a nonce [18].

It does not tolerate a padding oracle [21] - indeed, in practice, padding oracle attacks are common [15, 14, 16] and the padding mode suggested in the current draft [9] is exactly that which gives rise to most of these attacks.

AES-CFB is not CCA secure. It is CPA-secure if the IV is random, but not if the IV is a nonce [18].

AES-CTR is not CCA secure. It is CPA-secure but not CCA-secure [18].

For a summary of the properties of these modes and the dangers of using ciphers with only CPA-security, the following excerpt from Rogaway’s review [18] is apposite:

“I am unable to think of any cryptographic design problem where, absent major legacy considerations, any of CBC, CFB, or OFB would represent the mode of choice.    
I regard CTR as easily the “best” choice among the set of the confidentiality modes (meaning the set of schemes aiming only for message privacy, as classically understood). It has unsurpassed performance characteristics and provable-security guarantees that are     at least as good as any of the “basic four” modes with respect to classical notions of privacy. The simplicity, efficiency, and obvious correctness of CTR make it a mandatory member in any modern portfolio of SemCPA-secure schemes.    
The  only  substantial  criticisms  of  CTR  center  on  its  ease  of  misuse.  First,  it  is imperative that the counter-values that are enciphered are never reused. What is more, these values are “exposed” to the user of CTR, offering ample opportunity to disregard the instructions. Second, the mode offers absolutely no authenticity, nonmalleability, or chosen-ciphertext-attack (CCA) security. Users of a symmetric scheme who implicitly     assume such properties of their confidentiality-providing mode are, with CTR, almost certain to get caught in their error.”

1.9    AES-GCM

GCM mode has a security proof - the security notion is AEAD (Authenticated Encryption with Associated Data), which (loosely speaking) means that the encryption part is CCA-secure and the message and associated data are unforgeable. There are some cryptanalytic results on certain instantiations of the scheme, those these are not currently thought to pose a practical threat [20].

Standardised by NIST, GCM is gaining traction in standards such as IPsec, MACSec, P1619.1, and TLS [18].

1.10    AES-CMAC

AES-CMAC has good security proofs (i.e. it has well studied proofs with reasonable bounds under standard assumptions) [18].

1.11    AES-KW

AES-KW has received various criticisms, for example being inconsistent in its notions of security (requiring IND-CCA from a deterministic mode), but though it has no public security proof, it has no known attacks either [17].

There are alternative standards with security proofs such as SIV mode (RFC 5297).

1.12    HMAC

HMAC has well-studied security proofs, even if the underlying hash function is not (weak) collision resistant [3].                                                                                                                                                                      

1.13    DH

The security of Diffie-Hellman key agreement maps closely to the difficulty of the Diffie-Hellman problem. More than 35 years after publication of the DH protocol and despite progress on the discrete log problem, there are no publicly known attacks. Like other plain DH modes it offers no authenticity, this must be taken care of separately.

1.14    SHA-1

A procedure is known to obtain SHA-1 collisions in less than 262 operations [23] (since SHA-1 has a fixed 160 bit output, the theoretical lower bound is 280). A talk by Marc Stevens outlines a procedure requiring 260 operations. Speculation about when practical collisions will be seen ranges from 2018-21.

UPDATE

The first full collision appeared in March 2017.

Preimage calculation attacks on reduced round SHA-1 currently require 2146.2 steps on 44 round SHA-1and 2150.6 steps on 48 round [11] (full SHA-1 has 80 rounds).

Finally, some authors consider even the theoretical lower bound on collision attacks (280) to be too low a security parameter for future applications [20].

1.15    SHA-256, SHA-384, SHA-512

There are collision and preimage attacks reported on reduced-round versions of the SHA-2 family, but currently no practical attacks [20].

1.16    HKDF-CTR, PBKDF2

Security models for password-based key derivation functions are still in a state of flux [24]. However, we note that HKDF has security proofs [12], while PBKDF2 has known weaknesses [25].                                                                                                                                                                      

1.17    CONCAT

CONCAT (which refers to the key derivation function defined in Section 5.8.1 of NIST SP 800-56A) does not appear to have any independent analysis, but is simple and receives approval in the ENISA report [20]

Conclusions

The W3C Crypto API proposes a mixed bag of modern and legacy crypto. There's plenty that could go wrong but also some reasonable building blocks. Choose wisely.

References

[1]   Romain Bardou, Riccardo Focardi, Yusuke Kawamoto, Lorenzo Simionato, Graham Steel,    and Joe-Kai-Tsay.  Efficient padding oracle attacks on cryptographic hardware.  In Advances    in Cryptology: Proceedings of CRYPTO ’12, volume 7417 of LNCS, pages 608–625. Springer,    2012.        

[2]   Gilles Barthe, Benjamin Grégoire, and Santiago Zanella-Béguelin.  Formal certification of    code-based cryptographic proofs. In 36th ACM SIGPLAN-SIGACT Symposium on Principles    of Programming Languages, POPL 2009, pages 90–101. ACM, 2009.    

[3]   Mihir Bellare.   New proofs for mac and hmac: Security without collision-resistance.   In    Cynthia Dwork, editor, CRYPTO, volume 4117 of Lecture Notes in Computer Science, pages    602–619. Springer, 2006.    

[4]   Mihir Bellare and Phillip Rogaway.  The exact security of digital signatures-how to sign    with rsa and rabin. In Proceedings of the 15th Annual International Conference on Theory and    Application of Cryptographic Techniques, EUROCRYPT’96, pages 399–416, Berlin, Heidelberg,    1996. Springer-Verlag.    

[5]   D. Bleichenbacher.    Chosen  ciphertext  attacks  against  protocols  based  on  the  RSA                                                                                                                                                                          encryption standard. In Advances in Cryptology: Proceedings of CRYPTO ’98, volume 1462 of    LNCS, pages 1–12, 1998.    

[6]   Dan Boneh and IgorE. Shparlinski.  On the unpredictability of bits of the elliptic curve    diffie-hellman scheme. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, volume    2139 of Lecture Notes in Computer Science, pages 201–212. Springer Berlin Heidelberg, 2001.    

[7]   Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern.  Rsa-oaep is    secure under the rsa assumption. J. Cryptol., 17(2):81–104, March 2004.    

[8]   Tibor Jager, Sebastian Schinzel, and Juraj Somorovsky.   Bleichenbacher’s attack strikes    again:  Breaking  pkcs#1  v1.5  in  xml  encryption.   In  Sara  Foresti,  Moti  Yung,  and  Fabio    Martinelli,  editors,  Computer Security - ESORICS 2012,  volume  7459  of  Lecture Notes in    Computer Science, pages 752–769. Springer Berlin Heidelberg, 2012.    

[9]   Bert Kaliski.  PKCS #7: Cryptographic Message Syntax.  RSA Security Inc., v1.5, march    1998. https://www.ietf.org/rfc/rfc2315.txt.    

[10]   Alan   Kaminsky,   Michael   Kurdziel,   and   Stanislaw   Radziszowski.       An   overview    of   cryptanalysis   research   for   the   advanced   encryption   standard.       In   MILITARY    COMMUNICATIONS CONFERENCE, 2010 - MILCOM 2010, 2010.    

[11]   Simon Knellwolf and Dmitry Khovratovich.  New preimage attacks against reduced sha-1.    In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO, volume 7417 of Lecture Notes    in Computer Science, pages 367–383. Springer, 2012.    

[12]   Hugo Krawczyk.  Cryptographic extraction and key derivation: The hkdf scheme.  In Tal    Rabin, editor, CRYPTO, volume 6223 of Lecture Notes in Computer Science, pages 631–648.    Springer, 2010.    

[13]   James Manger. A chosen ciphertext attack on RSA optimal asymmetric encryption padding    (OAEP) as standardized in PKCS #1 v2.0.  In Joe Kilian, editor, Advances in Cryptology      CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 230–238. Springer    Berlin / Heidelberg, 2001.                                                                                                                                                                          

[14]   Chris J. Mitchell.  Error oracle attacks on CBC mode: Is there a future for CBC mode    encryption? In J. et al. Zhou, editor, ISC 2005, number 3650 in LNCS, pages 244–258, 2005.    

[15]   K.G. Paterson and A. Yau.   Padding oracle attacks on the ISO CBC mode encryption    standard. In T. Okamoto, editor, RSA ’04 Cryptography Track, number 2964 in LNCS, pages    305–323. Springer, 2004.    

[16]   Juliano Rizzo and Thai Duong. Practical padding oracle attacks. In Proceedings of the 4th    USENIX conference on Offensive technologies, WOOT’10, pages 1–8, Berkeley, CA, USA, 2010.    USENIX Association.    

[17]   P. Rogaway    and T. Shrimpton.  Deterministic authenticated-encryption: A provable-security treatment of    the key-wrap problem. In Advances in Cryptology (EUROCRYPT ’06), volume 4004 of LNCS,    pages 373–390, 2006. Full version https://eprint.iacr.org/2006/221.pdf.    

[18]   Philip Rogaway.  Evaluation of some blockcipher modes of operation.  Technical report,    University of California, Davis, February 2011.  Evaluation carried out for the Cryptography    Research and Evaluation Committees (CRYPTREC) for the Government of Japan.    

[19]   RSA Security Inc., v2.0. PKCS #1: RSA Cryptography Standard, September 1998.    

[20]   Nigel P. Smart, Vincent Rijmen, Bogdan Warinschi, and Gaven Watson.  Algorithms, key    sizes and parameters report: 2013 recommendations.  Technical report, October 2013.  ENISA    Report. Version 1.0.    

[21]   Serge Vaudenay.  Security flaws induced by CBC padding - applications to SSL, IPSEC,    WTLS  ...   In  Lars R.  Knudsen,  editor,  EUROCRYPT,  volume  2332  of  Lecture  Notes  in    Computer Science, pages 534–546. Springer, 2002.    

[22]   Serge Vaudenay.  The security of dsa and ecdsa.  In YvoG. Desmedt, editor, Public Key    Cryptography - PKC 2003, volume 2567 of Lecture Notes in Computer Science, pages 309–323.    Springer Berlin Heidelberg, 2002.                                                                                                                                                                          

[23]   Xiaoyun  Wang,  Yiqun Lisa  Yin,  and  Hongbo  Yu.   Finding  collisions  in  the  full  sha-1.    In  Proceedings  of  the  25th  Annual  International  Conference  on  Advances  in  Cryptology,    CRYPTO’05, pages 17–36, Berlin, Heidelberg, 2005. Springer-Verlag.    

[24]   Chuah Chai  Wen,  Ed Dawson,  Juan  Manuel González  Nieto,  and  Leonie  Simpson.   A    framework for security analysis of key derivation functions. In Mark Dermot Ryan, Ben Smyth,    and Guilin Wang, editors, ISPEC, volume 7232 of Lecture Notes in Computer Science, pages    199–216. Springer, 2012.    

[25]   Frances F. Yao and Yiqun Lisa Yin. Design and analysis of password-based key derivation    functions.  In Alfred Menezes, editor, CT-RSA, volume 3376 of Lecture Notes in Computer    Science, pages 245–261. Springer, 2005.