*Sigh*

Thomas Ptacek | April 23rd, 2005 | Filed Under: Uncategorized

From sci.crypt. My edits are brutal and unfair.

DJB: “This paper reports successful extraction of a complete AES key from a network server on another computer.”

TSD: you need a bitchslap back to reality… Take my low bandwidth relatively high latency SSH session…

more below…

TSD: Couldn’t you just insert noise in the process to lower the bias?

DJB: Adding noise doesn’t lower the bias. The attacker sees through the noise by averaging over a larger number of packets.

Rubin: How about using the CPU cycle counter to add enough delay to make the total time constant.

DJB: Slowing the average case down to the worst case is a terrible penalty… The AES process can be interrupted, so making the total time constant isn’t sufficient to stop timing leaks.

Scheffer: A session of ping -s shows at least 1 ms rms deviation on all servers I tried… This is months at 1000 packets/second, even assuming you can arrange for 10 billion known plaintexts.

DJB: When I send pings several miles from UIC to the University of Chicago, the ping program claims a deviation of 0.51 ms, but the bottom half of the times have a deviation of only 0.01 ms—-just 6000 CPU cycles on a typical 600MHz server.

Warnock: HAH! You’re probably not going through more than a couple of routers.

DJB: Well, yes, as an attacker I think I can get myself within several miles of a typical Internet target. If the AES marketing slogan is AES. Speedy. Standard. Safe for several months of continuous use if everyone within six router hops is trustworthy. then I think it’s time to review our notion of cryptographic security.

Schryver: Attackers that are less than halfway accross the country are in fact more worrisome. They are far more likely to use other kinds of cryptoanalysis including key loggers, rubber hoses, bribery, and extortion.

Schryver: Isn’t it a good practice in general to limit the number of encryptions used for any key?

DJB: I must have missed the NIST memo saying “WARNING: ALWAYS SWITCH AES KEYS AFTER B BLOCKS.” What’s the number B, Vernon? How many blocks should an implementor allow under one AES key before switching keys?

TSD: WTF? Are you incapable of seeing the distinction between DESIGN and IMPLEMENTATION? … You’re not the first to come up with side channel attacks. So take your 15 mins of fame and sit the f!@# down.

TSD: It’s possible to use AES in a way that is immune to your attack…

DJB: Cryptography would be much easier if there weren’t any speed constraints… But many other applications do have speed constraints… the software you have in mind doesn’t exist.

TSD: Two major flaws with your attack (in case you’re wondering why reaction is minimal). 1. It requires a large amount of chosen plaintext. 2. Very timing sensitive.

DJB: No. It requires a large amount of known plaintext where the AES inputs are fairly random: e.g., known plaintext in CBC mode.

TSD: Last time I saw your attack you cycled through different values for a given byte position to see which took the longest…

DJB: Nope. The attack used random packets. You should read the description of the attack, or simply read the code in Appendix B.

DJB: Let me emphasize at this point that any serious attacker will construct packets that knock selected server AES table entries out of L2 cache, increasing the signal to hundreds of cycles. Large target servers (and their surrounding operating systems) are actually easier to attack in this way than a tiny sample server.

But I didn’t want to bother constructing those packets. I wanted to see whether AES could survive an embarrassingly simple attack. (Answer: No.)

Schryver: …if it were so easy to detect 0.1 microsecond signals, then NTP would routinely deliver at 0.1 microsecond.

Schryver: How often will they [queuing delays] happen if your target is 7 hops away (implied by 5 routers) and each of the 14 networks in the round trip are 30% loaded? What are the odds that a probes and its result will escape being delayed on any of those 14 hops? It looks like about 0.7% to me. It would be “stunningly ignorant” to naively increase your 2M probes by a factor of 14,000.

DJB: Packets come in waves and bursts and spikes, forcing almost all hops to have far more capacity than they usually need.

Schryver: If it is so easy to detect 0.1 microsecond signals… why is it so much fun to try to make NTP discipline clocks to within microseconds?

DJB: An NTP client is trying to produce an accurate measurement… from a relatively small number of packets. This has no relevance to the problem of producing an accurate measurement of a small time interval from many packets.

Schryver: Or if packet delays are so well behaved, why is VoIP, which needs merely 10s of milliseconds instead of micorseconds…

DJB: When VoIP users bump into the occasional half-second network overload, they’re justifiably annoyed. When an attacker bumps into the occasional half-second network overload, he simply waits and tries again.

Shalunov: In fact, with modern networks, the jitter of a whole backbone is smaller than the jitter of the PCI bus inside the computer.

Amling: IIRC, OCB applies a different secret mask to each ciphertext block before decrypting it. My understanding is that the timing attacker has to know the (unmasked) ciphertext to extract the key. If so, just using OCB would be protection.

DJB: But it obtains its first mask by encrypting the nonce! That first encryption is the obvious target of a timing attack.

The attacker doesn’t need to see the output of those encryptions. He just needs to see the timings.

TSD: The AES specification specifies only the algorithm not it’s implementation.

DJB: The AES designers and official evaluators

• considered timing attacks in detail,
• claimed that table lookup was “not vulnerable to timing attacks,”
• claimed that Rijndael gained a “major speed advantage over its competitors” for software protected against timing attacks,
• made the same comment in its summaries of the finalists, and
• made the same comment in its paragraph explaining the selection of Rijndael.

The problem is that, when they stated “Table lookup: not vulnerable to timing attacks,” they were simply wrong. Table lookup is vulnerable to timing attacks.

TSD: Dude, no one is denying the attack works.

DJB: My paper makes quite a few recommendations to CPU designers… Of course, another solution is to admit that there was a serious error in the AES design and evaluation process (“Table lookup: not vulnerable to timing attacks”), and to switch to a cipher that avoids this error.

Amling: Do any of the five AES finalists meet that criterion?

Wagner: Twofish doesn’t. Serpent might, in appropriate bitsliced mode, but it is noticeably slower than AES. MARS doesn’t. I’m not sure whether it will be possible to write a constant-time implementation of RC6

Schryver: You are ignoring my larger point that such a timing attack involves more than enough traffic to be a denial of service attack against almost all systems.

DJB: You are, first of all, wildly overestimating the amount of traffic needed by this embarrassingly simple timing attack… Furthermore, you are wildly underestimating the amount of traffic handled by today’s web servers… Furthermore, you are confusing traffic volume with traffic rate… Finally, you are fundamentally misunderstanding the nature of a timing attack. A timing attack doesn’t require the attacker to generate any packets. He simply has to see the packet timings.

Schryver: Isn’t it true that for every application of every encryption scheme, there exists such a B even without timing or power attacks. For example, shouldn’t B be related to the entropy in the key? Or the range of key values?

DJB: No. Modern ciphers, such as AES, are designed to remain secure (i.e., indistinguishable from a uniform random permutation) for any number of blocks.

Schryver: It seems reasonable to assume that he did not use more than 10 times too many packets.

DJB: Once again: The 200 million packets were massive overkill.

Schryver: If you don’t generate the packets, you will have trouble forcing lines out of L1 caches

DJB: As for going to extra effort to force lines out of cache, that would reduce the number of packets needed.

Schryver: …or picking the patterns to probe.

DJB: Normal CBC traffic already has a complete spread of input bytes. No “picking” is necessary.

Schryver: If you don’t generate the traffic, then you may need to rely on the accuracy and precision of the TCP timestamps supplied by the target of the attack.

DJB: The attacker watches the packets as they go by, and times them with his own highly accurate local clock.

Schryver: It seems intuitively clear that significantly more traffic would be required for a passive timing attack, but how much?

Schryver: …but claiming that AES is generally broken and useless and suggesting that the choice of AES was based on chicanery are not good ways to advance…

DJB: There was a blatant error in the AES design and evaluation process. (“Table lookup: not vulnerable to timing attacks.”) Nobody said that this error was deliberate. Perhaps you don’t understand what the word “chicanery” means.

Schryver: You gave the clear and presumably intentionally impression that chicanery was involved.

DJB: You’re a nutcase, Vernon.