4 ms·

Lucky Thirteen: Breaking the TLS and DTLS Record Protocols

77 points by agl 14y ago

agl 14y ago
Post on implementing the (rather complex) fix: http://www.imperialviolet.org/2013/02/04/luckythirteen.html http://www.imperialviolet.org/2013/02/04/luckythirteen.html
ajross 14y ago
Can anyone with expertise provide details? From the description, it's a timing attack based on the content of the stream. But my understanding (and presumably that of the protocol designers) was that TLS post-key-negotiation was mostly deterministic and not subject to this kind of thing. What am I missing?
- agl 14y ago
  The attacker lets the handshake complete normally and then intercepts the transmission of the encrypted record that contains the secret that they wish to decrypt. (Assuming that the parties negotiated a CBC ciphersuite.) The attacker can then alter the encrypted record and send it onwards to the server. Because the record has been altered, the server will reject it and close the connection. However, the amount of time that it takes to reject the record reveals something about the plaintext padding. If the client will repeatedly send the same plaintext secret (e.g. HTTP cookie) over many connections (e.g. a web browser repeatedly requesting a resource) then the attacker can learn a little from each connection and, after thousands of connections, start to decrypt the secret.
  - ajross 14y ago
    > However, the amount of time that it takes to reject the record reveals something about the plaintext padding. This is the part I don't get. Symmetric cyphers in CBC mode don't traditionally behave that way. You encrypt the block and get your answer. Is there a variable-length HMAC in there somewhere or something?
    - agl 14y ago
      TLS does CBC wrong: it authenticates the plaintext and then encrypts the plaintext and MAC. Since CBC mode needs to pad its input, this means that the padding is outside of the authentication. So, when decrypting, the padding has to be removed and then the MAC can be checked. But the number of blocks hashed in the MAC depends on the padding. So the attacker can setup the padding such that a valid padding means that it's removed and one less hash block is calculated. An invalid padding isn't removed and the MAC takes one more hash-block worth of time. Thus the attacker can tell whether a padding was valid and that's sufficient to completely break TLS.
      - Bootvis 14y ago
        How is it sufficient to know the padding to break TLS? I thought that if you know the padding, you only know the message length.
        caf 14y ago
        The attacker has an unknown plaintext byte P, and due to the way CBC mode works (together with the timing attack), is able to test if (P xor X) is a valid padding byte with X chosen by the attacker. Once the attacker finds an X that makes a valid padding byte, she can trivially determine P.
    - deleted 14y ago
      [deleted]
api 14y ago
If designing new crypto stuff, use a mode like GCM (Galois Counter Mode) or EAX. Avoid the old non-authenticated modes.
- agl 14y ago
  Both AES and GHASH have their own timing side-channel issues. If you need to encrypt something, I recommend NaCl: http://nacl.cr.yp.to/ http://nacl.cr.yp.to/
  - ctz 14y ago
    Are you saying that there is an equivalent attack for the AES-GCM TLS 1.2 ciphersuites? If so, paper please :)
    - JoachimSchipper 14y ago
      There have been cache-based timing attacks on AES; these are hard to stop completely. To the best of my knowledge, this is not a knock on GCM specifically; but I'd be happy to learn more.
  - moonboots 14y ago
    Besides the difficulties of patching openssl and nss, what are other technical and political challenges preventing the adoption of djb's crypto primivatives in tls?
    - JoachimSchipper 14y ago
      They have not been reviewed to anywhere near the extent that AES and co. have been. So few people use them, which makes them less attractive targets for cryptanalysis, and so on. Also, I'm under the impression that NaCl achieves impressive speeds, but at the cost of using implementations tuned to a specific CPU. This makes the amount of code that has to be reviewed considerably larger.
moxie 14y ago
@agl, it looks to me as if the timing differences they are measuring would be a complete wash in any realistic scenario? The original "good enough" timing fix (in response to Vaudenay) was based on the assumption that an attacker would not realistically be able to measure the small remaining timing differences. This paper has demonstrated that it is possible to measure the small remaining timing differences, but it seems as if that requires: 1) The server not to be doing anything else or processing any other TLS sessions. 2) The attacker to be in a hyper-controlled networking environment with extremely low latency to the server and zero interference. Do you see this attack ever being possible in a practical situation?
- agl 14y ago
  Against DTLS it appears to practical, both because the connection isn't destroyed and because the difference can be amplified by the researcher's Heartbeat trick from http://www.isg.rhul.ac.uk/~kp/dtls.pdf http://www.isg.rhul.ac.uk/~kp/dtls.pdf. Against TLS it's tougher. The paper is suggesting a difference of ~10000 cycles, which may be ~5us. So, yes, you need to have a good connection to the server to be able to measure that difference, but that's not unthinkable to me. I know that you could get such a connection to a Google server if you were willing to pay some money to get a machine hosted in the right place. But it also appears that it's fairly easy to get a process instantiated on the same EC2 host as a target application. Or maybe your server is running on a small ARM device and so the difference is much larger. Don't get me wrong - this is a trivial issue compared to, say, the Java vulnerabilities that we've seen recently. But it's huge compared to the level of security that plain TLS should be providing. Saying that it's secure as long as you don't allow the attacker to be close by, or you don't run it on a slow machine isn't good enough for me. But I admit that it's unlikely to anyone will ever actually perform this attack in anger. Although I would have said the same about MD5 collisions at the beginning of 2012 :)
  - moxie 14y ago
    Interesting. And beyond network position, do you think it's possible to measure these micro timing differences effectively against a server that experiences the type of load patterns Google's servers do? (And yeah, I have little faith in DTLS generally).
caf 14y ago
Isn't it about time that a new TLS version switches to Encrypt-then-MAC?

77 points by agl 14y ago

agl 14y ago

Post on implementing the (rather complex) fix: http://www.imperialviolet.org/2013/02/04/luckythirteen.html http://www.imperialviolet.org/2013/02/04/luckythirteen.html

ajross 14y ago

Can anyone with expertise provide details? From the description, it's a timing attack based on the content of the stream. But my understanding (and presumably that of the protocol designers) was that TLS post-key-negotiation was mostly deterministic and not subject to this kind of thing. What am I missing?

agl 14y ago
The attacker lets the handshake complete normally and then intercepts the transmission of the encrypted record that contains the secret that they wish to decrypt. (Assuming that the parties negotiated a CBC ciphersuite.) The attacker can then alter the encrypted record and send it onwards to the server. Because the record has been altered, the server will reject it and close the connection. However, the amount of time that it takes to reject the record reveals something about the plaintext padding. If the client will repeatedly send the same plaintext secret (e.g. HTTP cookie) over many connections (e.g. a web browser repeatedly requesting a resource) then the attacker can learn a little from each connection and, after thousands of connections, start to decrypt the secret.
- ajross 14y ago
  > However, the amount of time that it takes to reject the record reveals something about the plaintext padding. This is the part I don't get. Symmetric cyphers in CBC mode don't traditionally behave that way. You encrypt the block and get your answer. Is there a variable-length HMAC in there somewhere or something?
  - agl 14y ago
    TLS does CBC wrong: it authenticates the plaintext and then encrypts the plaintext and MAC. Since CBC mode needs to pad its input, this means that the padding is outside of the authentication. So, when decrypting, the padding has to be removed and then the MAC can be checked. But the number of blocks hashed in the MAC depends on the padding. So the attacker can setup the padding such that a valid padding means that it's removed and one less hash block is calculated. An invalid padding isn't removed and the MAC takes one more hash-block worth of time. Thus the attacker can tell whether a padding was valid and that's sufficient to completely break TLS.
    - Bootvis 14y ago
      How is it sufficient to know the padding to break TLS? I thought that if you know the padding, you only know the message length.
      - caf 14y ago
        The attacker has an unknown plaintext byte P, and due to the way CBC mode works (together with the timing attack), is able to test if (P xor X) is a valid padding byte with X chosen by the attacker. Once the attacker finds an X that makes a valid padding byte, she can trivially determine P.
  - deleted 14y ago
    [deleted]

api 14y ago

If designing new crypto stuff, use a mode like GCM (Galois Counter Mode) or EAX. Avoid the old non-authenticated modes.

agl 14y ago
Both AES and GHASH have their own timing side-channel issues. If you need to encrypt something, I recommend NaCl: http://nacl.cr.yp.to/ http://nacl.cr.yp.to/
- ctz 14y ago
  Are you saying that there is an equivalent attack for the AES-GCM TLS 1.2 ciphersuites? If so, paper please :)
  - JoachimSchipper 14y ago
    There have been cache-based timing attacks on AES; these are hard to stop completely. To the best of my knowledge, this is not a knock on GCM specifically; but I'd be happy to learn more.
- moonboots 14y ago
  Besides the difficulties of patching openssl and nss, what are other technical and political challenges preventing the adoption of djb's crypto primivatives in tls?
  - JoachimSchipper 14y ago
    They have not been reviewed to anywhere near the extent that AES and co. have been. So few people use them, which makes them less attractive targets for cryptanalysis, and so on. Also, I'm under the impression that NaCl achieves impressive speeds, but at the cost of using implementations tuned to a specific CPU. This makes the amount of code that has to be reviewed considerably larger.

moxie 14y ago

@agl, it looks to me as if the timing differences they are measuring would be a complete wash in any realistic scenario? The original "good enough" timing fix (in response to Vaudenay) was based on the assumption that an attacker would not realistically be able to measure the small remaining timing differences. This paper has demonstrated that it is possible to measure the small remaining timing differences, but it seems as if that requires: 1) The server not to be doing anything else or processing any other TLS sessions. 2) The attacker to be in a hyper-controlled networking environment with extremely low latency to the server and zero interference. Do you see this attack ever being possible in a practical situation?

agl 14y ago
Against DTLS it appears to practical, both because the connection isn't destroyed and because the difference can be amplified by the researcher's Heartbeat trick from http://www.isg.rhul.ac.uk/~kp/dtls.pdf http://www.isg.rhul.ac.uk/~kp/dtls.pdf. Against TLS it's tougher. The paper is suggesting a difference of ~10000 cycles, which may be ~5us. So, yes, you need to have a good connection to the server to be able to measure that difference, but that's not unthinkable to me. I know that you could get such a connection to a Google server if you were willing to pay some money to get a machine hosted in the right place. But it also appears that it's fairly easy to get a process instantiated on the same EC2 host as a target application. Or maybe your server is running on a small ARM device and so the difference is much larger. Don't get me wrong - this is a trivial issue compared to, say, the Java vulnerabilities that we've seen recently. But it's huge compared to the level of security that plain TLS should be providing. Saying that it's secure as long as you don't allow the attacker to be close by, or you don't run it on a slow machine isn't good enough for me. But I admit that it's unlikely to anyone will ever actually perform this attack in anger. Although I would have said the same about MD5 collisions at the beginning of 2012 :)
- moxie 14y ago
  Interesting. And beyond network position, do you think it's possible to measure these micro timing differences effectively against a server that experiences the type of load patterns Google's servers do? (And yeah, I have little faith in DTLS generally).

caf 14y ago

Isn't it about time that a new TLS version switches to Encrypt-then-MAC?