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 |

RSA-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-GCM | ✓ | ✓ | |

AES-CMAC | ✓ | ✓ | |

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 2^{62} operations [23] (since SHA-1 has a fixed 160 bit output, the theoretical lower bound is 2^{80}). A talk by Marc Stevens outlines a procedure requiring 2^{60} 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 2^{146.2} steps on 44 round SHA-1and 2^{150.6} steps on 48 round [11] (full SHA-1 has 80 rounds).

Finally, some authors consider even the theoretical lower bound on collision attacks (2^{80}) 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.