Breaking AES-128 in realtime, no ciphertext required | Hacker News Reader

Breaking AES-128 in realtime, no ciphertext required

eprint.iacr.org

69 pointstimf19 comments

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.

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.

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).

Yup. My bad.

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).

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 efﬁcient 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.

'''

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?

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.

Side channel attacks can become pretty funny, e.g. listening to the sounds your computer makes.

In case anyone is wondering (via Wikipedia):

In 2004, Adi Shamir and Eran Tromer demonstrated that it may be possible to conduct timing attacks against a CPU performing cryptographic operations by analysis of variations in its humming noise (that is, its high-frequency humming noise, not the louder low-frequency humming of its cooling fan). http://people.csail.mit.edu/tromer/acoustic/

Some people take long-exposure photographs in a dark box. Yes, really.

Of course, electron microscopes and precisely-aimed laser pulses are more... geeky.

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.

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.

I review roughly 1 cryptosystem per quarter in my practice, have been doing so for several years, and I can't think of a single system that survived as far as "I'd have to mount a side channel attack to break this". If your biggest problem is timing leaks, you win.

The stuff that breaks most cryptosystems is much more basic than "side channels" and "key management". It's using ECB mode, encrypting without a MAC, inventing your own SHA1 MAC, leaking errors, colliding IVs or nonces, failure modes that collide session keys, not checking parameters; I could go on and on.

I'd hate for people to think that side channels is the thing they have to be on the lookout for. Writing their own crypto constructions is what they need to be on the lookout for.

Point noted. I don't review cryptosystems for a living.

I guess my point was that most of the cryptosystems /I've/ used over the years have seen significant vulnerabilities exposed in key management and side channel attacks. Insufficient entropy for key generation is another one. That said, I probably benefit from people like you weeding out the REALLY bad implementations.

I do agree that you're likely to see a lot of extraordinarily poorly designed cryptosystems if you regularly look at work product from people who are unfamiliar with attack methodologies in general.

I work in app security, and maybe 1% of the testers I know (I know a lot of testers) are familiar with crypto attack methodologies. It's still a dark art. I don't know where a company that wasn't "plugged in" would ever find expertise.

Having your app own3d is a pretty good way to learn how NOT to do crypto.

I wonder how many ways there are to NOT do crypto. To enumerate them sounds like it might be exhausting.

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

Reply on news.ycombinator.com