Breaking AES-128 in realtime, no ciphertext required

[tptacek]

You have to be on the same machine as the software doing the encryption. It works in roughly the same way that Daniel Bernstein, Eran Tromer, Onur Aciiçmez, and Colin Percival's (independently discovered) attacks work; you run a tight loop measuring memory accesses for cache perturbation, and postprocess the measurements to guess key bits. It has nothing to do with AES - the - algorithm.

The paper is interesting (they used an artificial neural network to filter the measurements), but the results aren't ultra-surprising; I think everyone expects more side channels to be discovered on x86 hardware in the coming years, especially since much of the microarchitecture is undocumented. (Note: this paper targets a very old processor, which probably improved their results).

The biggest issue with this branch of side channel study --- an issue not mentioned in the paper --- is that "getting on the same machine as an encryption process" is much less hard than it sounds in 2010: many encryption processes run on VMs inside hosting providers, where the cost of situating an attacker on the same metal as the target might be as low as $20.

But, long story short: this isn't the crypto attack you should be most worried about. My understanding is that OpenSSL has pushed back on fixing much more straightforward timing channels than this. There are remote attacks that are still worth attention.

[caf]

This particular implementation of the timing attack uses the fact that OpenSSL is used as a shared library, so that the (read-only) lookup table is mapped to the same physical pages in every process using the library. That wouldn't be true in the "same-metal-different-VM" attack model (but it seems like it should be possible to extend the attack to that scenario).

[JoachimSchipper]

E.g. http://cseweb.ucsd.edu/~hovav/dist/cloudsec.pdf shows that the whole "crypto in the cloud" idea isn't so hot.

Still, the speed with which this attack runs is impressive.

[InclinedPlane]

When browsers have been updated to have "good and proper" high performance byte-code VMs fully integrated we can look forward to these sorts of attacks becoming possible through merely viewing a web page or component (say, an ad served by a 3rd party).

[timtadh]

from the conclusion it looks like the latest version of OpenSSL mitigates the attack:

'''

One concrete mitigation strategy has been realized in OpenSSL 1.0 [18]. There, only the substitution table S is stored, and then the required multiplications within GF (28) are computed by using the following relations, which can be realized in a highly efficient way using the PCMPGTB instruction:

                     +-                           -+
                     |       +-                    |
                     |       | ff (int8_t) x > 0   |
    2•x = (x << 1) ⊕ | 1b ∧ -+                     |
                     |       | 0  (int8_t) x ≤ 0   |
                     |       +-                    |
                     +-                           -+

        = (x << 1) ⊕ (1b ∧ PCMPGTB(x, 0))
    3•x = 2 • x ⊕ x

In this case, the required table contains 28 = 256 entries of 20 = 1 bytes each, and on standard x86-architectures with a cache-line size of 26 = 64 bytes we have that only l = 2 bits of each x∗ are leaked. Looking at Table 1 now shows that we have p3 = 1, i.e., every k∗ ∈ {0, 1}4·2 is a valid partial key-column candidate for every x∗ and y∗ . For this reason, our key search algorithm does not work anymore. Because of the large prevalence of AES another mitigation strategy is currently embarked by software vendors. Namely, they are increasingly often offering hardware support of AES in their chips, e.g., [25], rendering access-driven cache attacks impossible.

'''

[MikeCapone]

Anybody can explain to us non-cryptographers if:

1) This is legit?

2) This can work in the real-world and not just in some very specific lab conditions?

[mey]

The first sentence mentions this as a side channel attack, which is a legitimate attack method and applies to most algorithms, not just AES. Most crypto packages guard against this attack one way or another. This is one of the reasons you do not implement your own cryptography solution without understanding all the details, as any weakness can cause a complete compromise.

Further reading. http://en.wikipedia.org/wiki/Side_channel_attack

Also this article title is slightly mis-leading, but not entirely.

[Nrsolis]

Not only is it legit but it's a kind of attack that is very closely studied because theory != practice. MOST crypto systems fail because they implement a very solid algorithm/protocol in a very bad way.

My experience has been that cryptographic systems fail in two ways:

1. Side channel attacks. 2. Key management attacks.

There is a whole conference (called CHES) which talks about ways to build/verify crypto hardware that will withstand side channel attacks and prevent the loss of keying material stored in a hardware device. It's a hard problem to get right and a lot of very paranoid people work very hard to anticipate how bad they might be at building a working cryptographic system.

[js4all]

2) The attack is possible, but only on the machine which does the encryption. So the threat is real but relatively difficult to exploit.

Anyway, the findings are spectacular because most other attacks use time-memory trade-off brute-force methods.

[mateuszb]

I know David and have seen him demo the software in practice and it is almost instant and very surprising. He has been playing with caches for a long time now