8 ms·

CREAM: the SSL attack you’ve probably never heard of

90 points by bascule 12y ago

feld 12y ago
So what hearing is: - AES is vulnerable to timing attacks by design unless the implementation is very careful. But even then no promise it is safe because of CPU hardware nuances between models and architectures. - Use AES-GCM if you must use AES. - AES-GCM(?) is accelerated by the Intel AES extension and provides a constant-time implementation, but you have to trust Intel's hardware isn't backdoored. - Don't use AES for network communications if you can avoid it. Is this correct?
- bascule 12y ago
  AES-NI can be used to accelerate AES on Intel CPUs. CLMUL instructions (namely PCLMULQDQ) can be used to accelerate GCM. You need to use both in conjunction for a fast, constant-time AES implementation. However, the conclusion to draw is more general: any data dependent timings in any cipher implementation can be catastrophic.
  - iacr262y2y2y 12y ago
    1 https://www.iacr.org/search/?q=AES+Cipher+Keys https://www.iacr.org/search/?q=AES+Cipher+Keys 2 prediction: 3 side-channel attack + boomerang attack 10 round >> AES-128 Broken 4 gap = goal(10 round) - present (7 round) = future (3 round) 5 gap/time = estimate at 1 year 6 software goal = http://hashcat.net/oclhashcat/ http://hashcat.net/oclhashcat/ 7 prediction method: 8 curl, elinks, word cluster, topic summaries 9 : 10 AES Cipher Keys Suitable for Eﬃcient Side-Channel 11 Vulnerability Evaluation 12 Takaaki Mizuki, Yu-ichi Hayashi Tohoku University 13 Abstract 14 This paper investigates pairs of AES-128 cipher keys and 15 plaintexts which result in being “quiet” in the ﬁnal round, 16 i.e., whose 128-bit State holds the same bit pattern 17 before and after Round 10. 18 HOLDS THE SAME BIT PATTERN BEFORE AND AFTER ROUND 10. 19 ...Because such quiet and noisy plaintexts make extreme actions 20 in the ﬁnal round of the AES encryption, these AES-128 cipher keys 21 are quite useful for AES hardware designers to eﬃciently 22 evaluate the vulnerabilities of their products, 23 for instance, the performance of their side-channel attack 24 countermeasures. 25 Table 8: The Estimated SNR at various distances from the FPGA. 26 9 Conclusion 27 recent research has been adopting the idea that suitable plaintexts, 28 say those with rather small (but non-zero) Hamming distances 29 in the ﬁnal round, are chosen for eﬃcient side-channel attack evaluation. 30 there has not been any study that uses quiet plaintexts 31 (i.e., those with exactly-zero-Hamming distance) yet. 32 New Related-Key Boomerang Attacks on AES 33 Michael Gorski and Stefan Lucks, Bauhaus-University Weimar, Germany 34 Abstract. In this paper we present two new attacks on round reduced 35 versions of the AES. We present the first application of the related-key 36 boomerang attack on 7 and 9 rounds of AES-192. The 7-round attack 37 requires only 218 chosen plaintexts and ciphertexts and needs 38 267.5 encryptions. We extend our attack to nine rounds of AES-192. 39 This leaves to a data complexity of 267 chosen plaintexts and ciphertexts 40 using about 2143.33 encryptions to break 9 rounds of AES-192. 41 Conclusion 42 The AES remains still unbroken but we have shown that up to 43 7 rounds practical attacks are available yet. 44 7 ROUNDS PRACTICAL ATTACKS ARE AVAILABLE
- geofft 12y ago
  I think worrying about a backdoor is mis-aiming paranoia. If the hardware were backdoored, it could do malicious things to you whether or not you call PCLMULQDQ. What you should be worried about is something much more common: you have to trust that Intel's hardware is correctly implemented. Intel does a fantastic job at an extremely hard problem, but they still make the occasional mistake: http://www.anandtech.com/show/8376/intel-disables-tsx-instructions-erratum-found-in-haswell-haswelleep-broadwelly http://www.anandtech.com/show/8376/intel-disables-tsx-instru... The AES-NI and CLMUL instructions promise two things: first, that they'll do the math correctly, and second, that they'll do it in constant time with respect to secret data. I don't think anything else nontrivial in the architecture makes that second promise. (On a minor technical point: AES itself is constant-time if you have AES-NI, which is moderately more common than CLMUL. It's just that, cryptographically, almost all new users of AES today should be using AES-GCM, and that involves a not-easily-constant-time operation separate from the AES block cipher itself.)
- zimmerfrei 12y ago
  >> - Use AES-GCM if you must use AES Without CLMUL instructions, GCM is either very slow or potentially sensitive to cache-based side-channel attacks (regardless of AES being the underlying cipher). The EAX mode of operation is more secure - though not very popular for some reasons and not part of any TLS cipher suite.
  - stouset 12y ago
    EAX is protected by patents.
    - zimmerfrei 12y ago
      Could you provide a reference?
  - tptacek 12y ago
    Given Rogaway's recent patent grants, OCB would be a more straightforward improvement over GCM.
    - tedunangst 12y ago
      Does anything use OCB? It seems GCM "won". The patents may have killed it. Even "free for open source" can be troublesome if you're worried about putting free software into an appliance and getting trapped. Easier to avoid patented algos entirely.
      - AlyssaRowan 12y ago
        Rogaway's patent grants are now very liberal: they cover all open source and everything non-military. It passed through CFRG, too, and is documented in an RFC: https://tools.ietf.org/html/rfc7253 https://tools.ietf.org/html/rfc7253 But yes, definitely the fact that there were patent grants hurt it a lot in adoption before; even when (as in WiFi) it was one of the contenders, CCM is more common. A few things do use it: off the top of my head, I think Mumble does, although I think that's an earlier variant (OCB2, perhaps, rather than OCB3 as documented in the RFC?). I'm also looking forward to the results of the CAESAR authenticated-encryption competition - http://competitions.cr.yp.to/caesar.html http://competitions.cr.yp.to/caesar.html - there's a lot of competition, and quite a few entries fell and have been withdrawn. The current version of OCB is among the current list of contenders, among several other interesting candidates.
tptacek 12y ago
For this attack to get a stupid name, it needs to actually attack SSL/TLS. But Bernstein got it to work only in a lab setting, with a target pessimized to expose the vulnerability. That target, of course, did not use SSL/TLS. Pedantry Points += 10
- brianpgordon 12y ago
  I think security researchers are getting a bit caught up with the glam and the glory of huge blockbuster bugs. Cash rules everything around me CREAM, get the money Dollar, dollar bill y'all
- bascule 12y ago
  Normally I'd agree the way an attack makes the leap from an academic paper to a cute name is a real-world PoC||GTFO, but c'mon, is this not the perfect name?
sdevlin 12y ago
This attack is conceptually simple, and the linked paper (http://cr.yp.to/antiforgery/cachetiming-20050414.pdf http://cr.yp.to/antiforgery/cachetiming-20050414.pdf) is very approachable for the layman. I recommend giving it a read. Here's the basic idea: 1. The first thing the AES encrypt function does is XOR user input against the secret key. 2. The result of this operation is used to index into a lookup table (the S-box). 3. The timing characteristics of step 2 will vary based on the contents of the cache. By measuring the timings for a large number of random inputs and correlating them by index, (e.g. sort all messages into buckets based on the value of the first byte), we can recover the corresponding byte of the secret key. Though it's not clear a priori what the timing characteristics should look like for a particular key byte, we can easily measure this on a machine we control that matches the description of the target platform.
- tptacek 12y ago
  Unsurprisingly excellent description. How much control do we have over the cache lines populated by AES in a TLS scenario? We can't fully randomize the AES inputs, because they have to correspond to the TLS protocol.
  - sdevlin 12y ago
    I think it would be tough to attack TLS with this. A couple important stumbling blocks off the top of my head: We need to pull off the attack in the context of a single TLS session, because new AES keys are generated for each one. This means we can't choose any inputs to the AES function. If we try to manipulate or forge a message, the MAC will fail and then the jig is up. This might not be a big deal, since the AES ciphertexts will seem random anyway. There will be a large amount of overhead in each request compared to Bernstein's original experiment. This will likely introduce a large amount of per-request jitter. With enough requests we can iron this out, but again: one session. So there may be an upper limit on the number of samples we can realistically take. We may have a tough time comparing like to like. Certainly we can request the same static resource each time if we control malicious JavaScript, but there may be confounding factors. This might not be a big deal, since I think this just amounts to more jitter.
- 12y ago
ZoFreX 12y ago
I'm really wary of the "don't invent your own crypto" mantra, so I want to venture an idea I had here, rather than writing any code for it: I understand the problems with adding a random delay to try to add "noise" to the measurements, but what if the delay was non-random? Specifically, what if the delay was calculated to make the whole operation always take constant time? Example: User input comes in on thread A. Thread A sends the request to thread B and delays for time t. Thread B does the encryption and sets the result. Thread A resumes and returns the result. If we pick 't' such that it is always larger than the amount of time it takes to do the operation, any timing differences observed by the attacker won't be correlated with the timing of the cryptographic operations. I think. (NB: it could be something other than threads, such as "microservice B" instead of "thread B", that particular detail isn't important)
- tedunangst 12y ago
  People like their crypto to run faster than "maximally pessimized".
  - kaoD 12y ago
    But they also like their crypto secure :P
- sdevlin 12y ago
  A better strategy (and an area of research for Dan Bernstein, author of the referenced paper) is to design crypto that doesn't leak this kind of side-channel information. See, for example, his Salsa20 family of stream ciphers.
  - ZoFreX 12y ago
    I know that is a better strategy, but it's also a much much harder strategy :) Even a well designed cipher could end up leaking info in practice due to compiler quirks or implementation mistakes.
- bascule 12y ago
  > I understand the problems with adding a random delay to try to add "noise" to the measurements Actually, this isn't problematic at all... it's called random blinding: https://en.wikipedia.org/wiki/Blinding_(cryptography) https://en.wikipedia.org/wiki/Blinding_(cryptography) It's a commonly used method used to implement things like RSA in constant time.
secabeen 12y ago
Many SSL attacks seem to require thousands or millions of interactive sessions or inputs. Is there a reason we aren't modifying our Internet-facing servers to drop connections and discard ephemeral keys when a particular IP or set of IPs performs actions that are outside the norm?
- TheLoneWolfling 12y ago
  Because then you end up blocking entire countries by accident.
- snowwrestler 12y ago
  Well I think the crypto nerds would like to design crypto systems that are inherently (i.e. mathematically) resistant to such attacks. But in general, I think you are right. I am astounded at how few networked applications perform rate limiting. Wordpress, for example, does not ship with any rate limiting on the login form. Brute force? Go ahead, give it a shot. By comparison, Drupal 7 out of the box limits any IP to a small number of quick login attempts before blocking that IP temporarily. If your application is intended for human interaction, it just makes sense to limit things to human speed. Maybe it's harder than I think it is, or maybe people just don't think of it.
  - e12e 12y ago
    It's a tradeoff (like so much in security): limit an IP to N number of quick login attempts, and it's easy for your students to DOS the Drupal-powered school portal (assuming the school is behind a NAT, at least). Often you want more security, and less convenience ... but it's not as easy as "most secure all the time!".
justcommenting 12y ago
from the blog post: > Fortunately, Intel solved this problem… for the hyperspecific case of AES. Newer Intel CPUs (and also other vendors including ARM) now provide a fast, constant-time implementation of AES in hardware. Others have pointed to particular aspects of Intel hardware that they don't believe are 'backdoored', for some definition of backdoored. One point some of these comments appear to be missing is that using things like AES-NI typically also means using things like RDRAND. Whether you think there's any relationship between Intel's Bull Mountain and NSA'S BULLRUN is up to you, but at the end of the day, the only way any of us can know for sure whether RDRAND uses DUAL_EC_DRBG is to: 1) decide to take Intel at their word about RDRAND using only CTR_DRBG, or 2) undertake some difficult and probably-expensive hardware forensics to find out
- pbsd 12y ago
  DUAL_EC_DRBG would have been the dumbest possible way to backdoor RDRAND. It would also imply that Intel is somehow able to slip in circuitry able to do two 256-bit elliptic curve scalar multiplications in under 300 cycles, and pretend it is AES circuitry which would normally be orders of magnitude smaller and faster.
Blackthorn 12y ago
CREAM? We Wu-Tang now?

90 points by bascule 12y ago

feld 12y ago

So what hearing is: - AES is vulnerable to timing attacks by design unless the implementation is very careful. But even then no promise it is safe because of CPU hardware nuances between models and architectures. - Use AES-GCM if you must use AES. - AES-GCM(?) is accelerated by the Intel AES extension and provides a constant-time implementation, but you have to trust Intel's hardware isn't backdoored. - Don't use AES for network communications if you can avoid it. Is this correct?

bascule 12y ago
AES-NI can be used to accelerate AES on Intel CPUs. CLMUL instructions (namely PCLMULQDQ) can be used to accelerate GCM. You need to use both in conjunction for a fast, constant-time AES implementation. However, the conclusion to draw is more general: any data dependent timings in any cipher implementation can be catastrophic.
- iacr262y2y2y 12y ago
  1 https://www.iacr.org/search/?q=AES+Cipher+Keys https://www.iacr.org/search/?q=AES+Cipher+Keys 2 prediction: 3 side-channel attack + boomerang attack 10 round >> AES-128 Broken 4 gap = goal(10 round) - present (7 round) = future (3 round) 5 gap/time = estimate at 1 year 6 software goal = http://hashcat.net/oclhashcat/ http://hashcat.net/oclhashcat/ 7 prediction method: 8 curl, elinks, word cluster, topic summaries 9 : 10 AES Cipher Keys Suitable for Eﬃcient Side-Channel 11 Vulnerability Evaluation 12 Takaaki Mizuki, Yu-ichi Hayashi Tohoku University 13 Abstract 14 This paper investigates pairs of AES-128 cipher keys and 15 plaintexts which result in being “quiet” in the ﬁnal round, 16 i.e., whose 128-bit State holds the same bit pattern 17 before and after Round 10. 18 HOLDS THE SAME BIT PATTERN BEFORE AND AFTER ROUND 10. 19 ...Because such quiet and noisy plaintexts make extreme actions 20 in the ﬁnal round of the AES encryption, these AES-128 cipher keys 21 are quite useful for AES hardware designers to eﬃciently 22 evaluate the vulnerabilities of their products, 23 for instance, the performance of their side-channel attack 24 countermeasures. 25 Table 8: The Estimated SNR at various distances from the FPGA. 26 9 Conclusion 27 recent research has been adopting the idea that suitable plaintexts, 28 say those with rather small (but non-zero) Hamming distances 29 in the ﬁnal round, are chosen for eﬃcient side-channel attack evaluation. 30 there has not been any study that uses quiet plaintexts 31 (i.e., those with exactly-zero-Hamming distance) yet. 32 New Related-Key Boomerang Attacks on AES 33 Michael Gorski and Stefan Lucks, Bauhaus-University Weimar, Germany 34 Abstract. In this paper we present two new attacks on round reduced 35 versions of the AES. We present the first application of the related-key 36 boomerang attack on 7 and 9 rounds of AES-192. The 7-round attack 37 requires only 218 chosen plaintexts and ciphertexts and needs 38 267.5 encryptions. We extend our attack to nine rounds of AES-192. 39 This leaves to a data complexity of 267 chosen plaintexts and ciphertexts 40 using about 2143.33 encryptions to break 9 rounds of AES-192. 41 Conclusion 42 The AES remains still unbroken but we have shown that up to 43 7 rounds practical attacks are available yet. 44 7 ROUNDS PRACTICAL ATTACKS ARE AVAILABLE
geofft 12y ago
I think worrying about a backdoor is mis-aiming paranoia. If the hardware were backdoored, it could do malicious things to you whether or not you call PCLMULQDQ. What you should be worried about is something much more common: you have to trust that Intel's hardware is correctly implemented. Intel does a fantastic job at an extremely hard problem, but they still make the occasional mistake: http://www.anandtech.com/show/8376/intel-disables-tsx-instructions-erratum-found-in-haswell-haswelleep-broadwelly http://www.anandtech.com/show/8376/intel-disables-tsx-instru... The AES-NI and CLMUL instructions promise two things: first, that they'll do the math correctly, and second, that they'll do it in constant time with respect to secret data. I don't think anything else nontrivial in the architecture makes that second promise. (On a minor technical point: AES itself is constant-time if you have AES-NI, which is moderately more common than CLMUL. It's just that, cryptographically, almost all new users of AES today should be using AES-GCM, and that involves a not-easily-constant-time operation separate from the AES block cipher itself.)
zimmerfrei 12y ago
>> - Use AES-GCM if you must use AES Without CLMUL instructions, GCM is either very slow or potentially sensitive to cache-based side-channel attacks (regardless of AES being the underlying cipher). The EAX mode of operation is more secure - though not very popular for some reasons and not part of any TLS cipher suite.
- stouset 12y ago
  EAX is protected by patents.
  - zimmerfrei 12y ago
    Could you provide a reference?
- tptacek 12y ago
  Given Rogaway's recent patent grants, OCB would be a more straightforward improvement over GCM.
  - tedunangst 12y ago
    Does anything use OCB? It seems GCM "won". The patents may have killed it. Even "free for open source" can be troublesome if you're worried about putting free software into an appliance and getting trapped. Easier to avoid patented algos entirely.
    - AlyssaRowan 12y ago
      Rogaway's patent grants are now very liberal: they cover all open source and everything non-military. It passed through CFRG, too, and is documented in an RFC: https://tools.ietf.org/html/rfc7253 https://tools.ietf.org/html/rfc7253 But yes, definitely the fact that there were patent grants hurt it a lot in adoption before; even when (as in WiFi) it was one of the contenders, CCM is more common. A few things do use it: off the top of my head, I think Mumble does, although I think that's an earlier variant (OCB2, perhaps, rather than OCB3 as documented in the RFC?). I'm also looking forward to the results of the CAESAR authenticated-encryption competition - http://competitions.cr.yp.to/caesar.html http://competitions.cr.yp.to/caesar.html - there's a lot of competition, and quite a few entries fell and have been withdrawn. The current version of OCB is among the current list of contenders, among several other interesting candidates.

tptacek 12y ago

For this attack to get a stupid name, it needs to actually attack SSL/TLS. But Bernstein got it to work only in a lab setting, with a target pessimized to expose the vulnerability. That target, of course, did not use SSL/TLS. Pedantry Points += 10

brianpgordon 12y ago
I think security researchers are getting a bit caught up with the glam and the glory of huge blockbuster bugs. Cash rules everything around me CREAM, get the money Dollar, dollar bill y'all
bascule 12y ago
Normally I'd agree the way an attack makes the leap from an academic paper to a cute name is a real-world PoC||GTFO, but c'mon, is this not the perfect name?

sdevlin 12y ago

This attack is conceptually simple, and the linked paper (http://cr.yp.to/antiforgery/cachetiming-20050414.pdf http://cr.yp.to/antiforgery/cachetiming-20050414.pdf) is very approachable for the layman. I recommend giving it a read. Here's the basic idea: 1. The first thing the AES encrypt function does is XOR user input against the secret key. 2. The result of this operation is used to index into a lookup table (the S-box). 3. The timing characteristics of step 2 will vary based on the contents of the cache. By measuring the timings for a large number of random inputs and correlating them by index, (e.g. sort all messages into buckets based on the value of the first byte), we can recover the corresponding byte of the secret key. Though it's not clear a priori what the timing characteristics should look like for a particular key byte, we can easily measure this on a machine we control that matches the description of the target platform.

tptacek 12y ago
Unsurprisingly excellent description. How much control do we have over the cache lines populated by AES in a TLS scenario? We can't fully randomize the AES inputs, because they have to correspond to the TLS protocol.
- sdevlin 12y ago
  I think it would be tough to attack TLS with this. A couple important stumbling blocks off the top of my head: We need to pull off the attack in the context of a single TLS session, because new AES keys are generated for each one. This means we can't choose any inputs to the AES function. If we try to manipulate or forge a message, the MAC will fail and then the jig is up. This might not be a big deal, since the AES ciphertexts will seem random anyway. There will be a large amount of overhead in each request compared to Bernstein's original experiment. This will likely introduce a large amount of per-request jitter. With enough requests we can iron this out, but again: one session. So there may be an upper limit on the number of samples we can realistically take. We may have a tough time comparing like to like. Certainly we can request the same static resource each time if we control malicious JavaScript, but there may be confounding factors. This might not be a big deal, since I think this just amounts to more jitter.
12y ago

ZoFreX 12y ago

I'm really wary of the "don't invent your own crypto" mantra, so I want to venture an idea I had here, rather than writing any code for it: I understand the problems with adding a random delay to try to add "noise" to the measurements, but what if the delay was non-random? Specifically, what if the delay was calculated to make the whole operation always take constant time? Example: User input comes in on thread A. Thread A sends the request to thread B and delays for time t. Thread B does the encryption and sets the result. Thread A resumes and returns the result. If we pick 't' such that it is always larger than the amount of time it takes to do the operation, any timing differences observed by the attacker won't be correlated with the timing of the cryptographic operations. I think. (NB: it could be something other than threads, such as "microservice B" instead of "thread B", that particular detail isn't important)

tedunangst 12y ago
People like their crypto to run faster than "maximally pessimized".
- kaoD 12y ago
  But they also like their crypto secure :P
sdevlin 12y ago
A better strategy (and an area of research for Dan Bernstein, author of the referenced paper) is to design crypto that doesn't leak this kind of side-channel information. See, for example, his Salsa20 family of stream ciphers.
- ZoFreX 12y ago
  I know that is a better strategy, but it's also a much much harder strategy :) Even a well designed cipher could end up leaking info in practice due to compiler quirks or implementation mistakes.
bascule 12y ago
> I understand the problems with adding a random delay to try to add "noise" to the measurements Actually, this isn't problematic at all... it's called random blinding: https://en.wikipedia.org/wiki/Blinding_(cryptography) https://en.wikipedia.org/wiki/Blinding_(cryptography) It's a commonly used method used to implement things like RSA in constant time.

secabeen 12y ago

Many SSL attacks seem to require thousands or millions of interactive sessions or inputs. Is there a reason we aren't modifying our Internet-facing servers to drop connections and discard ephemeral keys when a particular IP or set of IPs performs actions that are outside the norm?

TheLoneWolfling 12y ago
Because then you end up blocking entire countries by accident.
snowwrestler 12y ago
Well I think the crypto nerds would like to design crypto systems that are inherently (i.e. mathematically) resistant to such attacks. But in general, I think you are right. I am astounded at how few networked applications perform rate limiting. Wordpress, for example, does not ship with any rate limiting on the login form. Brute force? Go ahead, give it a shot. By comparison, Drupal 7 out of the box limits any IP to a small number of quick login attempts before blocking that IP temporarily. If your application is intended for human interaction, it just makes sense to limit things to human speed. Maybe it's harder than I think it is, or maybe people just don't think of it.
- e12e 12y ago
  It's a tradeoff (like so much in security): limit an IP to N number of quick login attempts, and it's easy for your students to DOS the Drupal-powered school portal (assuming the school is behind a NAT, at least). Often you want more security, and less convenience ... but it's not as easy as "most secure all the time!".

justcommenting 12y ago

from the blog post: > Fortunately, Intel solved this problem… for the hyperspecific case of AES. Newer Intel CPUs (and also other vendors including ARM) now provide a fast, constant-time implementation of AES in hardware. Others have pointed to particular aspects of Intel hardware that they don't believe are 'backdoored', for some definition of backdoored. One point some of these comments appear to be missing is that using things like AES-NI typically also means using things like RDRAND. Whether you think there's any relationship between Intel's Bull Mountain and NSA'S BULLRUN is up to you, but at the end of the day, the only way any of us can know for sure whether RDRAND uses DUAL_EC_DRBG is to: 1) decide to take Intel at their word about RDRAND using only CTR_DRBG, or 2) undertake some difficult and probably-expensive hardware forensics to find out

pbsd 12y ago
DUAL_EC_DRBG would have been the dumbest possible way to backdoor RDRAND. It would also imply that Intel is somehow able to slip in circuitry able to do two 256-bit elliptic curve scalar multiplications in under 300 cycles, and pretend it is AES circuitry which would normally be orders of magnitude smaller and faster.

Blackthorn 12y ago

CREAM? We Wu-Tang now?