Security of CBC Ciphersuites in SSL/TLS: Problems and Countermeasures http://www.openssl.org/~bodo/tls-cbc.txt [Last updated: 2004-05-20] There are some problems with the CBC-based ciphersuites in SSL 3.0 and TLS 1.0 that can be exploited by active adversaries under specific circumstances: 1. If bad padding is treated differently from bad MACs when decrypting SSL/TLS records, the adversary may be able to launch Vaudenay's attack on padding; see the first e-mail message reproduced below [Date: Thu, 20 Sep 2001]. TLS 1.0 has different error codes for these two cases ('decryption_failed' and 'bad_record_mac'), which is a bad idea. While the adversary will not be able to read the error codes that are transmitted (these are encrypted), an error logfile will suffice to launch the attack if it reveals the type of error -- even if file permissions prevent the adversary from actually reading the file (the file length increase cause by the attack is likely to reveal which of the two errors occured). Countermeasure: Treat incorrect block cipher padding like a MAC verification error during record decryption (in particular, don't send the TLS 1.0 'decryption_failed' error code). OpenSSL contains this countermeasure since version 0.9.6c [21 December 2001]. A different approach to distinguish these two error cases and launch the attack is to examine the timing of error responses: if the MAC verification is skipped when bad padding has been found, the error will appear quicker in the case of incorrect block cipher padding than in the case of an incorrect MAC. This problem is described in LASEC Memo "Password Interception in a SSL/TLS Channel" by Brice Canvel, published 2003-02-20: http://lasecwww.epfl.ch/memo_ssl.shtml A countermeasure is to compute a MAC of the plaintext anyway, even if the usual padding removal step fails because of incorrect padding, to obtain (nearly) uniform timing. OpenSSL contains this countermeasure since versions 0.9.6i and 0.9.7a [19 February 2003]; see the OpenSSL Security Advisory at http://www.openssl.org/news/secadv_20030219.txt 2. The CBC IV for each record except the first is the previous records' last ciphertext block. Thus the encryption is not secure against adversaries who can adaptively choose plaintexts; see the second e-mail message reproduced below [Date: Fri, 8 Feb 2002]. Note that for most application protocols such attacks are not really feasible. A simple countermeasure is to prepend a record with an empty plaintext fragment before sending the actual payload. The CBC encrypted part of such a record will consist just of a MAC and padding. Then the IV used for live data will not be known in advance. This is a compatible countermeasure in that it is compliant with the SSL 3.0 and TLS 1.0 specifications. OpenSSL contains this countermeasure since version 0.9.6d [9 May 2002]. It turned out that some buggy SSL/TLS implementations (most notably MSIE) reject empty fragments, so the countermeasure can be switched off in version 0.9.6e [30 July 2002] by setting option SSL_OP_DONT_INSERT_EMPTY_FRAGMENTS or SSL_OP_ALL. 3. For SSL 3.0, it is not completely specified what CBC block cipher padding has to look like -- most bytes of the padding can have arbitrary values, and only the very last byte is relevant. TLS 1.0 requires all padding bytes to take the same value, but reportedly some TLS 1.0 implementations do not verify whether padding is intact on records that they have received and decrypted. In SSL/TLS, block cipher padding is not covered by the MAC, so an active adversary can try out certain modifications to records that are transmitted and derive supposedly cryptographically secured information by observing whether these modifications do or do not disturb the SSL/TLS connection. For details on such attacks, see the third e-mail message reproduced below [Date: Wed, 5 Nov 2003]. For TLS 1.0, this vulnerability applies only when implementations are used that do not verify block cipher padding. OpenSSL does verify block cipher padding and hence is not vulnerable. For SSL 3.0, the vulnerability is intrinsic to the protocol because the integrity of block cipher padding cannot be verified. (Note that SSL/TLS has protections against version rollback attacks: if both the client and the server in a connection support TLS 1.0, the adversary cannot easiliy force them to use SSL 3.0 instead to expose them to this vulnerability.) TLS 1.1 will change the specification of the CBC ciphersuites to avoid these security problems as far as they apply to TLS: it advises against using the 'decryption_failed' alert, and it introduces explicit random IVs for CBC encryption. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Errata: In the message "TLS insecurity (attack on CBC)", the paragraph TLS 1.0 employs a commonly used style of plaintext padding for CBC: Append p padding bytes all valued p where p is a positive integer chosen such that the resulting total length is a multiple of the block size in bytes. (Unlike many other protocols, TLS does not bound p above by the block size; any value up to 255 is permitted.) should be replaced by TLS 1.0 employs a variant of a commonly used style of plaintext padding for CBC: Append p padding bytes all valued p-1 where p is a positive integer chosen such that the resulting total length is a multiple of the block size in bytes. (Unlike many other protocols, TLS does not bound p above by the block size; any value up to 256 is permitted.) Accordingly, the following substituations should be made in the description of the attack against TLS 1.0: 0x01 should read 0x00 0x02 0x02 should read 0x01 0x01 0x03 0x03 0x03 should read 0x02 0x02 0x02 Date: Thu, 20 Sep 2001 21:37:59 +0200 From: Bodo Moeller To: "IETF Transport Layer Security WG" Cc: openssl-cvs@openssl.org, serge.vaudenay@epfl.ch Subject: TLS insecurity (attack on CBC) [To ietf-tls list, Cc: openssl-cvs and Serge Vaudenay.] The TLS 1.0 specification (RFC 2246) defines the following two alerts for failures during record decryption and MAC verification: bad_record_mac This alert is returned if a record is received with an incorrect MAC. This message is always fatal. decryption_failed A TLSCiphertext decrypted in an invalid way: either it wasn`t an even multiple of the block length or its padding values, when checked, weren`t correct. This message is always fatal. While these alerts are not directly visible to attackers, they may be written to logfiles, allowing an attacker to observe which type of error was caused by an active attack. (Note that in practice simply observing the length of the logfile may suffice to launch this kind of attack; it may not be necessary to read the actual contents.) For security reasons, they should be kept secret from any potential attacker, so it is dangerous and arguably pointless to use different types of alerts in the first place. Thus, TLS 1.0 implementations should always generate a 'bad_record_mac' alert if the padding value check failed. SSL 3.0 did not have a separate 'decryption_failed' alert anyway. Both for SSL 3.0 and TLS 1.0, implementations should make sure that the difference between these errors is not made visible in local logfiles. The TLS 1.0 'decryption_failed' alert is OK for the case that the length is not a multiple of the block length, as this is visible directly from the ciphertext. For other cases, it should be depreciated. Background: In his CRYPTO 2001 paper "The order of encryption and authentication for protecting communications (Or: how secure is SSL?)" [1], Hugo Krawczyk shows that, under certain general security assumptions for MACs and symmetric encryption schemes, "encrypt-then-authenticate" (EtA) has the desired security properties for building secure channels while "authenticate-then-encrypt" (AtE) in general is not secure. He then shows that in the special cases where the symmetric encryption scheme is a block cipher in CBC mode or an XOR-based stream ciphers, security proofs *are* in fact possible for AtE. These are the cases relevant for SSL and TLS. So he concludes that "[...] while we show the generic security of SSL to be broken, the current standard implementations of the protocol that use the above modes of encryption are safe." However, this is not true if an attacker can tell apart the two failure cases discussed above. [1] The full version of Hugo's paper is available at . The following idea to attack CBC with block padding is essentially what Serge Vaudenay presented at the CRYPTO 2001 Rump Session the evening before Hugo's talk, except that he used an iterated attack to decrypt a complete plaintext and noted that this is impossible to do for SSL because the connection is aborted and the symmetric key invalidated as soon as a decryption error occurs. (Actually he must have meant TLS 1.0 -- for SSL 3.0, the attack works differently anyway; see below.) While the full attack is indeed not possible for SSL and TLS, the partial attack already constitutes a valid attack. In the case of TLS 1.0, an active attacker who guesses the last byte of a block of plaintext sent earlier in the connection can verify that this guess is true, with reliability about 254/255. (For example, if the attacker assumes that the plaintext byte is uniformly distributed, he has probability 1/256 to get a random guess confirmed; but in the case of confirmation, with probability about 1/255, the confirmation was wrong.) Here's how it goes. CBC encryption looks like this (Pi, Ci are plaintext and ciphertext blocks, respectively; E is single block encryption; the number of plaintext blocks is 3 in this example, but in fact, of course, is variable): IV P1 P2 P3 | | | | | v v v | > XOR > XOR > XOR | / | / | / | | / v / v / v | / E / E / E |/ |/ |/ | v v v v IV C1 C2 C3 Decryption looks like this (I'll leave plaintext blocks and ciphertext blocks in place and just reverse some of the arrows and substitute block decryption, D, for encryption): P1 P2 P3 ^ ^ ^ | | | > XOR > XOR > XOR / ^ / ^ / ^ / | / | / | / D / D / D / ^/ ^/ ^ / | | | IV C1 C2 C3 TLS 1.0 employs a commonly used style of plaintext padding for CBC: Append p padding bytes all valued p where p is a positive integer chosen such that the resulting total length is a multiple of the block size in bytes. (Unlike many other protocols, TLS does not bound p above by the block size; any value up to 255 is permitted.) Assume that the attacker has observed two consecutive ciphertext blocks, C1 and C2, say, and wants to verify a guess for the last byte of P2. As P2 = C1 XOR D(C2), this means the attacker can make a corresponding guess for the last byte of D(C2). Now he makes up a fake ciphertext IV' || C'1 || C'2 || ... || C'n with arbitrary blocks in the beginning, the last two ciphertext blocks being C'n-1 = random bits || (guess XOR 0x01) (using the appropriate number of random bits to fill this block) and C'n = C2. The recipient will decrypt this as follows: P'n = C'n-1 XOR D(C2) If the guess for the last byte of D(C2) was correct, the last byte of P'n will be 0x01, which looks like legitimate padding. Thus this is not a 'decryption_failed' condition, so it will (with very high probability) lead to 'bad_record_mac'. If the guess was incorrect, we get a 'decryption_failed' unless by chance P'n ends in 0x02 0x02 or in 0x03 0x03 0x03 or similar seemingly valid padding. The conditional probability for this is slightly more than 1/255. SSL 3.0 does not specify what the padding should look like; but the final byte is always the number of padding bytes excluding this final byte itself, and must be smaller than the block size in bytes. If the block size is 8 bytes, this means that a 'decryption_failed' condition occurs if the last byte of P'n is not of the form 00000xxx. SSL 3.0 does not actually have a 'decryption_failed' alert, but if the attacker somehow can observe the type of error (e.g. by peeking at logfiles), the attacker will be able to verify a guess on five bits of the last byte of the target plaintext. A similar attack applies to TLS 1.0 if the recipient does not verify that all of the p padding bytes actually have value p (in this case we can expect to see a 'decryption_failed' error if the last byte of P'n is larger than the total number of plaintext bytes). -- Bodo Möller PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html * TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt * Tel. +49-6151-16-6628, Fax +49-6151-16-6036 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Date: Fri, 8 Feb 2002 23:48:07 +0100 (CET) From: moeller@cdc.informatik.tu-darmstadt.de (Bodo Moeller) To: ietf-ssh@netbsd.org, ietf-tls@lists.certicom.com Cc: Wei Dai , openssl-dev@openssl.org Subject: Re: an attack against SSH2 protocol Wei Dai : >> [Posted to sci.crypt and the IETF SSH working group mailing list.] >> >> Phil Rogaway observed that CBC mode is not secure against chosen- >> plaintext attack if the IV is known or can be predicted by the attacker >> before he choses his plaintext [1]. Similarly, CBC mode is not secure if >> the attacker can observe the last ciphertext block before choosing the >> next block of plaintext, because the last block of ciphertext >> essentially serves as the IV for the rest of the message. >> >> The attack itself is very simple. Remember that in CBC mode, each >> plaintext block is XOR'ed with the last ciphertext block and then >> encrypted to produce the next ciphertext block. Suppose the attacker >> suspects that plaintext block P_i might be x, and wants to test whether >> that's the case, he would choose the next plaintext block P_j to be x >> XOR C_(i-1) XOR C_(j-1). If his guess is correct, then C_j = Encrypt(P_j >> XOR C_(j-1)) = Encrypt(P_i XOR C_(i-1)) = C_i, and so he can confirm his >> guess by looking at whether C_j = C_i. >> >> The SSH2 protocol, when used with a block cipher in CBC mode, does allow >> the attacker to observe the last ciphertext block of a packet, which is >> then used as the (implicit) IV of the next packet. [...] >> [1] http://www.cs.ucdavis.edu/~rogaway/papers/draft-rogaway-ipsec-comments-00.txt > I have received some comments through private email. Apparently the exact > same weakness was known for IPSec and may also exist in TLS (I haven't > read enough of its RFC to be sure) [...] In TLS, the "IV for subsequent records is the last ciphertext block from the previous record" [RFC 2246], and plaintext blocks usually consist of raw application data followed by a MAC, so the attack applies. (Having the MAC at the *beginning* of each packet would avoid the attack.) In his CRYPTO 2001 paper "The Order of Encryption and Authentication for Protecting Communications (or: How Secure Is SSL?)", Hugo Krawczyk supposedly shows that SSL/TLS with CBC encryption is secure -- but he assumes a random IV for each encrypted block, which is not how the actual SSL protocol works. Another problem with CBC as used in SSL/TLS was pointed out by Serge Vaudenay, see . That one can easily be avoided by implementations. To avoid the new attack without changing the protocol definition, implementations would have to send an empty fragment before application data to ensure IV randomization. -- Bodo Möller PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html * TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt * Tel. +49-6151-16-6628, Fax +49-6151-16-6036 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Date: Wed, 5 Nov 2003 13:42:40 +0100 From: Bodo Moeller To: "IETF Transport Layer Security WG" Subject: [ietf-tls] Re: TLS 1.1 question and comments On Tue, Nov 04, 2003 at 07:42:20PM +0000, David Wagner wrote: > Peter Gutmann wrote: >> Section 6.2.3.2, the padding text is now explicit about checking the padding, >> which older versions weren't. [...] > Is it safe to skip checking the padding? I'm wondering about > the possibility of Vaudenay-style attacks. Does anyone know whether > this is ought to be a concern? There are (at least) two problems if padding is not checked: 1. Note that unlike SSL 3.0, TLS allows up to 256 bytes of padding, i.e. you can use more than the block size if desired. With standard padding for a cipher block size of 8 bytes, say, you hide only three bits of the plaintext length; with TLS padding, you can hide eight bits of the plaintext length. If padding is not checked, then the plaintext length is not properly hidden: if an adversary randomly modifies a ciphertext block in transit and this does not cause problems to the TLS connection, then it can be deduced that this bytes lies entirely within the padding. (Say the adversary modifies the last-but-one ciphertext block, but doesn't touch its last byte. During CBC decryption, this affects the final two plaintext blocks, but the byte indicating the padding length won't be changed. So if at least two blocks of padding have been used, the TLS connection will continue.) 2a. Now (for simplicity) assume that the sender does not bother to use more than one block of padding for each TLS record. Also assume that the block size is eight (16 can be handled similarly). And keep in mind that TLS padding is not quite the same as PKCS #5 padding: TLS subtracts one from the padding length, so it uses 02 02 02 where PKCS #5 padding would be 03 03 03 03. Let C1 and C2 be consecutive ciphertext blocks. In CBC mode, this means that a corresponding plaintext block is related to these blocks as follows: P2 = C1 XOR D(C2) Assume that P2 is part of the actual payload of some TLS record and that the adversary has a guess g on the final byte of P2. Now the adversary catches any TLS record R and makes some guess on the amount of padding. (Under the assumptions here, a random guess will be correct with probability 1/8.) Let's say it guesses that there are three bytes of padding. The adversary replaces said TLS record (in transit) by R || (C1 XOR C) || C2 (adjusting the length field in the TLS record header accordingly) where C is any block of the form xx .. xx (12 XOR g), xx denoting arbitrary bytes. If the guess g was correct, the recipient will interpret this as a TLS record with 19 (= 0x12 + 1) bytes of padding; and if the recipient does not check the padding, it will accept the record. Conversely, if the recipient accepts the modified TLS record, then with very high probability the actual final bytes of P2 conincides with g at least in its five most significant bits. (We cannot be sure about the other three bits of g unless we are sure about the amount of padding used be the original sender.) 2b. Even if senders never use more than one block of padding and recipients always check that no more than this amount of padding has been used (which would amount to losing interoperability with perfectly valid TLS implementations, though), the protocol is not secure if padding is not verified. Again assume that the block size is eight, and assume that the sender transmits a TLS record with eight bytes of padding. The final block P_n containing the padding should look like this: 07 07 07 07 07 07 07 07 The recipient recovers P_n by computing P_n = C_(n-1) XOR D(C_n) If the recipient does not check padding, it will accept anything of the form xx xx xx xx xx xx xx 07; this means that the adversary can replace C_n by any other ciphertext block C that it has encountered in this TLS stream before for which it guesses that C_(n-1) XOR D(C) will have 07 as its final byte. (By the CBC decryption rules, this guess corresponds to a certain possible guess on the final byte of each plaintext block.) The modified TLS record will be accepted if the guess was correct and the TLS record really did have eight bytes of padding. If the guess was not correct and the original TLS record had eight bytes of padding, then the modified TLS record with very high probability will not be accepted. If the guess was not correct and the TLS record had less than eight bytes of padding, then the modified TLS record will be accepted with some probability (1/256 in the worst case, namely for 7 bytes of padding; usually less). <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<