Although not perfect OpenSSL remains the cryptographic toolkit of reference. It is very well supported, has a steady community and is available on almost all architectures and systems.

Below is a selected list of several well known cryptographic attacks performed against OpenSSL since 2001 and their associated countermeasures taken in responses. It is worth mentioning that some of these attacks were theoretical or with few concrete incidence, nevertheless the interest here is to study their countermeasures. Obviously most of these attacks were not limited to OpenSSL and also affected others populars cryptographic libraries. However as OpenSSL is one of the most used open source toolkit and because several of these attacks explicitly targeted OpenSSL to present and validate their results it seemed natural and convenient to introduce these attacks from OpenSSL's perspective.

Some of the following attacks are due to cryptanalytic advances in side-channels attacks: including cache based attacks and timing attacks. Another class of attacks resulted (at least in part) from SSL/TLS protocols flaws or lack of directives in way of handling errors. Weaknesses also affected the quality of generated random keys or parameters.

Timeline

• [2008] Predictable random number generator in the Debian's OpenSSL package, found by Luciano Bello.
  • advisory – summary – incriminated commit – description – description – tools – tools – tools
• [2007] A Vulnerability in RSA Implementations Due to Instruction Cache Analysis and Its Demonstration on OpenSSL by Acıiçmez and Schindler.
  • advisory – paper – changes
  • This attack works with an instruction cache analysis aiming at revealing the instruction flow of the Montgomery Modular Multiplication (MMM) algorithm. By default, MMM internally uses two different multiple precision algorithms: a squaring when the inputs are equals, a multiplication otherwise. There are both followed by a Montgomery reduction which may accomplish an additional input-dependent subtraction called Extra Reduction (ER) if the result need to be reduced. This extra conditional step was thought to be safe or at least protected by others mechanisms (see after). However, in their publication the authors show that a spy process can exploit this flaw by analyzing the instructions cache, looking for subtraction's code implemented by BN_usub() and identify ER steps occurrences performed during RSA decryption. Knowing these occurrences they study the probabilities of happening in either a squaring or a multiplication. Across several Montgomery exponentiations with the same secret exponent an attacker is able to guess the fixed sequence of squarings and multiplications operations and further easily deduce the secret exponent. This attack is resistant to mitigations implemented in responses to previous SPBA and data cache analysis MicroArchitectural attacks even when base blinding is provided. The OpenSSL team eventually made this extra reduction step branchless. Exponent blinding (add a random multiple of the group order to the exponent see this page for more details) could be an alternative for blocking this attack.
• [2007] Branch prediction vulnerabilities by Acıiçmez, Gueron and Seifert.
  • paper – changes
  • The authors conjecture that an SPBA (Simple Prediction Branch Analysis) could be performed with enough precision to precisely learn about program flow execution of some selected parts of relevant crypto algorithms. They state that SPBA (analysis that they do not provide though) could be accomplished on any modern microprocessor not only on SMT processors by exploiting how scheduler works. Under this assumption, they introduce an attack on the Binary Extended Euclidean Algorithm (BEEA) of OpenSSL used in modular inversion operations (Note that BEEA was not used in every cases depending on parameters bit-lengths). They demonstrate how to reconstruct input operands x, y from the result of modular inversion x.x^-1 ≡ 1 mod y from the former program flow analysis. Modular inversion is usually used in several public key cryptography operations and could lead to leak secret informations. Base blinding (useful for preventing pure timing attacks) is at best useless in these cases and at worst could be compromised widening the surface of attack to remote timing attacks. The proposed mitigations mechanisms mainly consist into avoiding conditional branching whenever it would provide useful information to the attacker (typically each time it depends on secret data or input data). They also propose a completely new resistant implementation of CRT-RSA called "Smooth CRT-RSA" which does not seem to have been integrated to OpenSSL though.
• [2006] RSA signature forgery by Bleichenbacher.
  • advisory – description – description – changes – changes
  • This attack forges valid signatures for RSA keys with small e=3 public exponent, with large 3072 bits modulus, when used with PKCS1-v1_5 signature encoding and eventually verified by an implementation too permissive on data format verification. A malicious signer is able to forge a signature for a valid hash value without any private key by appending some chosen garbage data to its PKCS1-v1_5 representation to assemble a value from which it is possible to take a root cube. A flawed verifier uses its public key, raises the signature to the cube, extracts the hash value from the PKCS1-v1_5 byte string without considering the presence of the useless trailing data, successfully checks this hash against its own computed value therefore leading to authenticate this signature. In order to defeat this forgery the verifier must ensure that there is no remaining right trailing data appended after the hash or any additional ASN.1 parameter. Note also that probabilistic RSASSA-PSS signature scheme does prevent this attack. This attack has been refined since its publication, for instance some improvements targeting shorter modulus have been independently published.
• [2005] Colin Percival's Hyper-Threading timing attack.
  • advisory – description – paper – description – related (independently) attack – changes
  • This side channel attack uses a spy process to spot cache eviction patterns leading to extraction of secret information. Part of the secret key bits are recovered by analyzing cache timings of the sliding windows exponention algorithm used by OpenSSL to compute modular exponentiation. The spy process exploits the fact that microprocesor's cache is shared between multiple threads of execution as on processors with hyperthreading enabled.
  • Let's see with an example what changes were implemented in response to this attack (extensive changes contributed by Matthew D Wood from Intel). A new modular exponentiation was implemented, it uses a fixed-window to precompute a small number of exponentiations. In the case of an RSA decryption operation involving a modulus N of 1024 bits, the Chinese Remainder Theorem is used to reduce the complexity of the computations by performing two separate exponentiations with each of the 512 bits prime factors as exponents. The fixed number of precomputations on a modern microprocessor (as e.g. on a Pentium 4 Northwood) with L1 data cache lines of 64 bytes and an exponent of 512 bits will be equal to 2⁵-1. Let's C_q = C mod q where q is a prime factor of N and C is the ciphertext. The goal is to precompute the first 31 exponents (C_q)^1..31 in order to reduce the complexity of computing (C_q)^d_q mod q where d_q = d mod (q - 1) and d is the RSA private exponent. Note that because the underlying algorithm used is the Montgomery exponentiation using Montgomery reductions all the precomputations need to be represented under Montgomery's representation. Recall that Montgomery reduction is noted Mont(x, y) = x.y.R^-1 mod q where R is a power of 2 greater than q, typically R = 2³² on 32 bits architectures. For a complete introduction to Montgomery reduction see this book section 14.3.2. Let p₀, …, p₃₁ be all the precomputations:

    p₀ = Mont(1, R²) = R².R^-1 mod q = R mod q
    p₁ = Mont(C_d, R²) = C_d.R².R^-1 mod q = C_d.R mod q
    p₂ = Mont(p₁, p₁) = p₁².R^-1 mod q
    p₃ = Mont(p₂, p₁) = p₂.p₁.R^-1 mod q
    …
    p₃₁ = Mont(p₃₀, p₁)
    

    These precomputations are inserted into a same array, the original straightforward way of doing that was to insert them sequentially like this: | p₀ | p₁ | p₂ | ... | p₃₁ |. This array would be represented in a similar shape in the L1 cache. Each element p_x of 512 bits for x ∈ [1,31] fits into a single cache line (otherwise with p_x > 512 it would have taken at least 2 consecutive cache lines to store a single element). Let line₀, …, line₃₁ be 32 consecutive L1 data cache lines:

    line₀: p₀
    line₁: p₁
    line₂: p₂
    …
    line₃₁: p₃₁
    

    This is this representation that was vulnerable to the attack introduced by Percival. By observing which cache line was evicted (a whole cache line is either loaded or evicted from cache at once) or not (through timings observations) it was possible to deduce which p_x was accessed by OpenSSL. Observing that a particular p_x is used in a multiplication means that the value x has successfully been matched against a subpart of q revealing 5 bits of secret q.
    The purpose of the clever countermeasure implemented by this patch was to break the sequential order of the p_xs and to interleave them instead by single byte chunks in an array. Which eventually leads to create cache lines representations of this form:

    line₀: p₀byte₀, p₁byte₀, …, p₃₁byte₀
    line₁: p₀byte₁, p₁byte₁, …, p₃₁byte₁
    …
    line₆₃: p₀byte₆₃, p₁byte₆₃, …, p₃₁byte₆₃
    

    In this case observing accessed cache lines' patterns reveals nothing. Note that a Pentium 4 Northwood has 128 L1 data cache lines thus in this case all precomputed exponentiations may fit together in the L1 cache at the same time.
• [2003] Klima-Pokorny-Rosa attack on RSA in SSL/TLS.
  • advisory – paper – extends this attack – changes – Client Key Exchange Message (TLS Protocol) – tool
  • Original Bleichenbacher's attack: adaptative chosen-ciphertext attack relying on specifics properties of RSAES-PKCS1-v1_5 encryption scheme (several bytes are knowns and constants) and submitting its decryption queries to a SSL decryption oracle (see its corresponding protocol state) in order to determine if these ciphertexts are PKCS1-v1_5 conforming or not. This information is obtained from timing measurements or from overly detailed error messages. It permits one attacker through a high number of chosen ciphertexts to narrow the space of possible plaintext candidates until only one remains. As countermeasures the author suggested to check ciphertext's integrity before decrypting it or using RSAES-OAEP encryption scheme. However, even without these protections (SSL/TLS does not provide them) this attack is not practical against a correctly implemented SSL server: returning an error when a message is not PKCS1-v1_5 encoded or otherwise further checking its protocol version number and premaster secret length (46+2 bytes) and returning the same error for wrong values. Therefore most of PKCS1-v1_5 conforming forged ciphertexts will be rejected by these additional tests with an overwhelming probability. Thus it will be impractical to distinguish between conforming and non-conforming ciphertexts, defeating this attack. See also this section and its associated note.
  • Klima-Pokorny-Rosa's attack: the authors improved the previous attack and succeeded in using OpenSSL's SSL server as a reliable oracle for guessing rightly padded ciphertexts. They observed that OpenSSL returned a distinct error message for messages with bad protocol version numbers. Furthermore, a ciphertext raising this error had necessarily been successfully decrypted priorly to this check meaning that its padding was correct. Therefore OpenSSL was vulnerable to a "bad version oracle" identifying PKCS1-v1_5 conforming messages whenever bad version number errors are returned.
  • To sum it all up: all checks must be correctly performed (padding, version, length), no distinguishable error message must be returned but instead computations must always go forward to the end of the handshake while taking care of not leaking timing informations. It is critical that an attacker could not use in any manner any information from the server to exploit it as an oracle and distinguish among all forged ciphertexts which are well formed plaintexts.
• [2003] Timing-based attacks on RSA keys by Boneh and Brumley.
  • advisory – ml – paper – description – changes – changes
  • This work directly extends the seminal work of Kocher on timing attacks (note that this work did not originally work on modular exponentiations using CRT). The authors developed a remote timing attack against OpenSSL which let them extract the SSL server's private key on decryption queries. The decryption uses the Chinese Remainder Theorem and a sliding-window modular exponentiation algorithm to perform exponentiations. They exploited two algorithmic data dependencies which create timing differences inside two different algorithms used during decryption through modular exponentiation C^d mod N on input ciphertext. First, the Montgomery reduction algorithm called on modular multiplication has a conditional extra reduction thus slowing computations when this step accomplished. Second, the choice of the multi-precision integer multiplication algorithm depends on the size of the operands. The multiplication is faster when operands have the same number of words and Karatsuba algorithm is used, than with a non-optimized algorithm. The attack works by guessing successive bits of one RSA's prime factor. The attack decrypts its own guesses, computes associated timings and try to isolate larges timing differences in order to reveal the next bit. Note that RSA encryption encoding RSAES-PKCS1-v1_5 has no effect on this attack. Base blinding such as described into Kocher's paper is an effective method for mitigating this attack. The OpenSSL team already had implemented RSA blinding but it wasn't enabled by default. Therefore the purpose of the applied patch was simply to turn blinding on for all RSA decryption operations by default.
• [2003] Timing-based attacks on SSL/TLS with CBC encryption by Canvel, Hiltgen, Vaudenay and Vuagnoux.
  • advisory – description – description – paper – slides – paper – changes
  • More readings on authenticated encryption see this and this article and AEAD algorithms especially EAX mode.
• [2001] Check the result of RSA-CRT to protect against computations errors, based on the work of Boneh, DeMillo and Lipton.
  • paper – description (section 5.2) – changes
  • This paper demonstrates the need for checking results or intermediate results against hardware or software faults (see also this article on induced hardware faults) and only returning valid results. The authors introduce an attack on RSA signatures finding one of the prime factors without factoring the modulus. The attacker only needs access to a signer oracle which on rare occasions returns wrong signatures due to arbitrary faults (for instance a fault can lead to a random bit flip). This attack works on RSA signatures based on the Chinese Remainder Theorem (CRT), one half (and one half only) of this computation must contain an error. The attacker only needs one erroneous signature along with the original message (improvement contributed by Lenstra) to perform his attack. At the difference of RSASSA-PKCS1-v1_5 signature encoding, RSASSA-PSS does prevent this attack. OpenSSL mitigates this attack by checking that S^e ≡ M mod N before returning any signature. If this verification fails with a bogus signature it recomputes and returns the modular exponentiation of M^d mod N without using CRT. Note that randomized encodings schemes may not prevent all attacks of this class. In fact, it appears that RSAES-OAEP offers only limited protection over a faulty processor whose multiplier would output at least one wrong result for a given couple of operands, see Bug Attacks by Biham and al. As a side note, fault attacks are even a bigger concern in embedded systems (such as smart cards) and verifying the result with the public exponent is often inefficient. Moreover, It has been established that Shamir's countermeasure (section 4) as well as all its variants were not resistant to all known attacks, thus secure alternatives are still currently investigated. Recently a new type of attack "second-order" attacks were introduced by Kim and Quisquater (in this article), while first-order attacks generally inject a fault during a computation in order to produce a wrong result, second-order attacks try to prevent its detection or the execution of its mitigation. See this paper by Dottax et Al. for more details on the current state on this subject.
• [2001] Attack against the pseudorandom generator of DSA by Bleichenbacher.
  • description – description (section 2.2) – ml – changes – changes
  • DSA standard initially specified to choose a random parameter k of 160 bits and reduce it modulo a prime q, where q ∈ [2¹⁵⁹, 2¹⁶⁰-1]. Daniel Bleichenbacher observed that the values in range [0, 2¹⁶⁰-q] had therefore twice the probability to be chosen than the others values. It is unlikely though it had a real incidence on the security of the private key. See the Debian OpenSSL PRNG bug for another example of attack on k when this parameter lacks of entropy.