Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
Bodo Moeller wrote: Actually there are three choices: Pad-then-encrypt-then-MAC Pad-then-MAC-then-encrypt MAC-then-pad-then-encrypt It's true that pad-then-encrypt-then-MAC appears to be the safest approach in general, but pad-then-MAC-then-encrypt would also have avoided these attacks. By Pad-t-MAC-t-encrypt, do you mean a scheme where the MAC is also encrypted, or is left aside (the encrypt and authenticate method). There are problems with the latter as well, see appendix C of the paper from Krawczyk... If it's the first, then I guess that what you mean by Pad-t-MAC-t-encrypt is that you first pad the message (and IV and whatever other context) such that when you append the MAC (e.g 160 bits with SHA1-MAC) to the ciphertext the resulting size is a multiple of the block cipher size. So when you decrypt, you don't check the padding, but then after verifying the MAC you would take out the padding (and I guess verify it...). You can't play with the padding, because the MAC will fail. But if you are using CBC-DES as a MAC, you need to make sure that the MAC is verified first, not check the padding first, if not you *might* fall in to a similar trap (I'm not certain a vulnerability would exist in that context, but it sounds plausible). [...] The attack demonstrated by Vaudenay et al. users a less subtle timing difference (the difference between a MAC on about 256 SHA-1 input blocks and no MAC at all), but switching to Pad-then-MAC-then-encrypt should be considered for TLS 1.1. Pad-t-MAC-t-encrypt sounds like an interesting avenue, but why would you propose that for TLS 1.1 instead of just proposing the safe Pad-t-Encrypt-t-MAC? If there is going to be a change, might as well go with something that is provably secure, or is there some reason (compatibility or something) to prefer Pad-t-MAC-t-Encrypt that I do not see here? --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
On Tue, Feb 25, 2003 at 10:41:51AM -0500, Anton Stiglic wrote: Bodo Moeller wrote: Actually there are three choices: Pad-then-encrypt-then-MAC Pad-then-MAC-then-encrypt MAC-then-pad-then-encrypt It's true that pad-then-encrypt-then-MAC appears to be the safest approach in general, but pad-then-MAC-then-encrypt would also have avoided these attacks. By Pad-t-MAC-t-encrypt, do you mean a scheme where the MAC is also encrypted, or is left aside (the encrypt and authenticate method). The former. If it's the first, then [...]if you are using CBC-DES as a MAC, you need to make sure that the MAC is verified first, not check the padding first, if not you *might* fall in to a similar trap (I'm not certain a vulnerability would exist in that context, but it sounds plausible). Yes, I meant that implementations should proceed like this for pad-then-MAC-then-encrypt. For such a scheme it is the more natural way anyway to first decrypt, then verify the MAC, then look at the padding. (In the case of MAC-then-pad-then-encrypt, on the other hand, you can't verify the MAC before having handled the padding.) [...] switching to Pad-then-MAC-then-encrypt should be considered for TLS 1.1. Pad-t-MAC-t-encrypt sounds like an interesting avenue, but why would you propose that for TLS 1.1 instead of just proposing the safe Pad-t-Encrypt-t-MAC? If there is going to be a change, might as well go with something that is provably secure, or is there some reason (compatibility or something) to prefer Pad-t-MAC-t-Encrypt that I do not see here? For CBC (with explicit IVs, which we don't yet have in SSL 3.0 and TLS 1.0) and for stream ciphers, both variants achieve probable security. The reason to prefer pad-then-MAC-then-encrypt is just compatibility -- more specifically, ease of implementation (having an improved protocol is much more useful if it makes it into many actual products). -- Bodo Möller [EMAIL PROTECTED] 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 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
An extremely trivial observation, but may be useful to some: The attack assumes that multiple SSL or TLS connections involve a common fixed plaintext block, such as a password. There's been a discussion about how this affects POP over SSL on a private list. My suggestion was: -- Snip -- - Don't retry a connection repeatedly if it fails the first time (I guess you don't do that anyway, but some programs like Outlook try automated repeated connects). - Add random whitespace to the initial messages so the password isn't always at a fixed location (that is, sprinkle extra spaces and tabs and whatnot around in the lines you send up to and including the password). -- Snip -- This changes the padding on each message containing the password, making the attack rather more difficult, and has the advantage that you don't need to convince the party running the server to update their software. Depending on how much stuff you can send per message, you can vary it by quite a bit. In the POP case the PASS xxx would be a single message so you don't have quite that much leeway, but it looks like you can add enough whitespace to make the padding random. Someone else on the list posted a followup to say he'd tried it on two servers and they had no trouble with the whitespace. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
SMB writes: I'm struck by the similarity of this attack to Matt Blaze's master key paper. In each case, you're guessing at one position at a time, and using the response of the security system as an oracle. What's crucial in both cases is the one-at-a-time aspect -- that's what makes the attack linear instead of exponential. There's nothing new under the sun; both attacks are more similar than not to the classic Tenex page-alignment character-at-a-time password guessing attack. Speaking of which, does anyone have a good PRIMARY reference to that I've been trying to track one down for the print version of my lock paper, and all I can find is either secondary references (like countless OS textbooks and random computer security papers) or papers that you'd think would have the attack but turn out no to (like the recent Multics retrospective paper). Where did the Tenex attack first appear? -matt - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
Steven M. Bellovin [EMAIL PROTECTED] writes: I'm struck by the similarity of this attack to Matt Blaze's master key paper. In each case, you're guessing at one position at a time, and using the response of the security system as an oracle. What's crucial in both cases is the one-at-a-time aspect -- that's what makes the attack linear instead of exponential. Indeed. And of course, both attacks resemble the old password guessing attack on character by character passwords where you time how long password verification takes. (The details are pretty hazy but ISTR that you arranged for the password to cross a page boundary to increase the time discrimination). -Ekr -- [Eric Rescorla [EMAIL PROTECTED] http://www.rtfm.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
If I'm not mistaken, the OpenSSL spec says that you should MAC the (compressed) message, and then encrypt the message and the MAC. This composition is not generically secure, on the other hand you can prove some nice things about the composition encrypt-then- MAC assuming certain conditions, see for example David Wagner's post on sci.crypt for a discussion about that: http://groups.google.ca/groups?q=sci.crypt+encrypt+then+authenticate+Wagner; hl=enlr=ie=UTF-8oe=UTF-8selm=aj77jo%241ko%241%40agate.berkeley.edurnum= 1 (using CBC-DES with a random IV and then HMAC, with a KDF that derives independent keys for the encryption and the MACing (the KDF in SSL looks like it can do this) would satisfy these conditions.) I now always recommend encrypt-then-MAC. If SSL required encrypt-then-MAC, a programmer would more naturally start by verifying the MAC, then decrypt the message, so Vaudenay's attack would be caught first by the MAC verification and the implementation would probably return an error after the MAC verification and not leak the information needed to discover the plaintext. So even though the attack is not directly the result of the SSL protocol spec, a spec which would favor encrypt-then-MAC would be better in my point of view and the security holes relating to this SSLattack in implementations might have much less of a chance of existing. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
The idea is also similar to timing attacks against very, very badly-implemented password checking schemes; e.g. where a reply by some verifying server to a correct guess on the first n characters of a password takes slightly longer than a reply to a correct guess on only the initial n-1 characters (because an error is returned as soon as the first character is encountered). In these cases, the attack is also linear since one character at a time can be guessed, and the timing of the response provides an indication of whether or not the guess is correct. I believe we've also seen this type of paradigm in many cryptanalytic instances wherein a guess for just a portion of a secret key can be verified, thereby reducing the time for a brute-force search since one first guesses this portion, and gets it right, before trying to guess the remainder of the key material. Regards, Zully ~ Zulfikar Ramzan IP Dynamics, Inc. http://www.ipdynamics.com Unfettered, Simple VPNs -Original Message- From: Steven M. Bellovin [mailto:[EMAIL PROTECTED] Sent: Friday, February 21, 2003 6:17 AM To: EKR Cc: [EMAIL PROTECTED] Subject: Re: [Bodo Moeller [EMAIL PROTECTED]] OpenSSL Security Advisory: Timing- based attacks on SSL/TLS with CBC encryption I'm struck by the similarity of this attack to Matt Blaze's master key paper. In each case, you're guessing at one position at a time, and using the response of the security system as an oracle. What's crucial in both cases is the one-at-a-time aspect -- that's what makes the attack linear instead of exponential. --Steve Bellovin, http://www.research.att.com/~smb (me) http://www.wilyhacker.com (2nd edition of Firewalls book) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
I'm struck by the similarity of this attack to Matt Blaze's master key paper. In each case, you're guessing at one position at a time, and using the response of the security system as an oracle. What's crucial in both cases is the one-at-a-time aspect -- that's what makes the attack linear instead of exponential. --Steve Bellovin, http://www.research.att.com/~smb (me) http://www.wilyhacker.com (2nd edition of Firewalls book) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Bodo Moeller bodo@openssl.org] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption
Here's a fairly detailed description of how the attack works. You can also find a writeup by the authors at: http://lasecwww.epfl.ch/memo_ssl.shtml EXECUTIVE SUMMARY This is a potentially serious attack for automated systems that rely on passwords. Effectively, it potentially allows the attacker to recover an encrypted password. It doesn't appear to be serious for non-automated situations. OVERVIEW Imagine you have some protocol that uses passwords and the password always falls in the same place in the message stream. (IMAP, for instance). What happens is that the attacker observes a connection using that password. He then deliberately introduces a bogus message into the encrypted traffic and observes the server's behavior. This allows him to determine whether a single byte of the plaintext is a certain (chosen) value. By iterating over the various bytes in the plaintext he can then determine the entire plaintext. HOW THE ATTACK WORKS Basically, the attack exploits CBC padding. Recall that the standard CBC padding is to pad with the length of the pad. So, if you have an 8 byte block cipher and the data is 5 bytes long you'd have XX XX XX XX XX 03 03 03. This technique allows you to remove the pad by examining the final byte and then removing that many bytes. [0] Typically you also check that all the pad values are correct. Say the attacker intercepts a pair of consecutive blocks A and B, which are: A = AA AA AA AA AA AA AA a B = BB BB BB BB BB BB BB b And the plaintext of B corresponds to P = PP PP PP PP PP PP PP p The attacker wants to attack B and guesses that p == y. He transmits a new message A' || B where A' = AA AA AA AA AA AA AA (a XOR y) When the server decrypts B, the final byte will be (p xor y). If the attacker has guessed correctly then there will appear to be a zero length pad and MAC verification proceeds. Since the packet has been damaged, the MAC check fails. If the attacker has guessed wrong then the last byte will be nonzero and the padding check will fail. Many TLS implementations generated different errors for these two cases. This allows the attacker to discover which type of error has occurred and thus verify his guess. Unfortunately, since this generates an error, the attacker can only guess once. The attack described above was discovered a year or two ago and implementations were quickly modified to generate the same error for both cases. This attack introduces two new features: (1) The authors observed that if you were moving passwords over TLS then the password would generally appear in the same place in each protocol exchange. This lets you iterate the attack over multiple character guesses and eventually over multiple positions. (2) Even if the same error message generated the MAC check takes time. You can therefore use timing analysis to determine what kind of error occurred. This has the downside that there's some noise but if you take enough samples you can factor that out. PRACTICALITY Let's estimate how long this will take. Most passwords are 7-bit ASCII, so naively we need to try all 128 values for each character. On average we'll get a hit halfway through our search so we expect have to try about 64 values for each character position. If we assume an 8 character password this means we'll need about 8*64==512 trials. Now, you could be smarter about what characters are probable and reduce these numbers somewhat but this is the right order of magnitude. Now, things are complicated a bit by the fact that each trial creates an error on both client and server. This has two implications. First, it creates a really obvious signature. Second, it requires that the client create a lot of SSL connections for the attacker to work with. This is only likely if the client is automated. REQUIRED CONDITIONS So, under what conditions can this attack be successful? (1) The protocol must have the same data appearing in a predictable place in the protocol stream. In practice, this limits its usefulness to recovering passwords. However, this condition pretty common for things like HTTP, IMAP, POP, etc. (2) The SSL implementations must negotiate a block cipher. Many SSL implementations choose RC4 by default and RC4 is not vulnerable to this attack. (3) The attacker needs to be able to hijack or intercept TCP connections. There are tools to do this that require varying degrees of sophistication and access to use. (4) The client must be willing to initiate a lot of connections even if it's getting SSL errors. As a consequence it almost certainly needs to be an automated client. (5) The attacker and the server must have a reasonably good network connection between them. The noisier the network, the more trials you need to distinguish the two outcomes. OUTCOME OF A SUCCESSFUL ATTACK A successful attacker will be able to recover the plaintext of whatever connection he's attacking. In
