Re: AES cache timing attack
On Tue, Jun 21, 2005 at 10:38:42PM -0400, Perry E. Metzger wrote: Jerrold Leichter [EMAIL PROTECTED] writes: Usage in first of these may be subject to Bernstein's attack. It's much harder to see how one could attack a session key in a properly implemented system the same way. You would have to inject a message into the ongoing session. I gave an example yesterday. Perhaps you didn't see it. The new 802.11 wireless security protocols encrypt the on-air portion of communications, and are typically attached to ethernet bridges. Sorry I didn't respond to this earlier -- I was on vacation last week. It is simple to practice this attack against an 802.11 network that is behind a NAT or routing firewall, rather than just a simple Ethernet bridge. It's only moderately harder when the 802.11 network is separated from the public Internet by a proxy firewall. In fact, I can run it right here in my house: From the west-facing window of my apartment building, I can see over 50 different 802.11 networks as I scan the buildings across the street with a reasonably tight antenna. Many of those networks are connected to the public Internet by a cablemodem network to which I also have access. A small number of those networks use WPA with AES (I'm lucky I have so many networks to choose from; this isn't common on residentail networks -- yet). So, to obtain encryption timing data, I can: 1) Do two quick tcpdumps, imported them into SPSS, and look for the best-correlated wireless and wired activity times. This gives me a good guess as to which wireless network had which public address (it also, presumably, gives me en/deryption timing data, for known, even, but not chosen plaintext; but that's just gravy). 2) Look at the tcpdump for the wired segment again (or run a new one) to find some open TCP connections. These will pretty much all correspond to open TCP connections on the inside; routing firewalls and almost all NAT boxes will just pass packets sent from the outside straight through (a proxy firewall will require an application-layer attack) 3) Send duplicate ACKs (or wholly spurious ACKs) to the public address of the firewall in question and watch the wireless segment to see how long it takes to encrypt them. Oh, by the way, they're chosen plaintext... Thor - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
At 02:44 AM 6/20/2005, Peter Gutmann wrote: Stephan Neuhaus [EMAIL PROTECTED] writes: Concerning the practical use of AES, you may be right (even though it would be nice to have some advice on what one *should* do instead). Would switching to triple-AES (or double-AES) or something help? Yeah, it's ugly, and AES was supposed to let us get away from triple-DES, but maybe running one AES with the original key and the other session with the inverse of the key would interfere with timing attacks? - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Jerrold Leichter [EMAIL PROTECTED] writes: Usage in first of these may be subject to Bernstein's attack. It's much harder to see how one could attack a session key in a properly implemented system the same way. You would have to inject a message into the ongoing session. I gave an example yesterday. Perhaps you didn't see it. The new 802.11 wireless security protocols encrypt the on-air portion of communications, and are typically attached to ethernet bridges. If you want to, you can send any packet you like at an arbitrary box on the wireless segment from the main network, and have the wireless router act as a fine quality oracle for you for the AES key being used on air. It would be possible, though perhaps less convenient (since it would require tapping rather than just listening) to do something similar to a wide variety of VPN protocols. However, if the protocol authenticates its messages, you'll never get any response to an injected message. You don't need to in the above instances. You just need to be able to inject. People like to downplay the impact of attacks like this, but there are just too many scenarios one didn't think of in the security universe. Doubtless some other usage cases may get badly bitten by AES side channel attacks. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
| It's much harder to see how one could attack a session key in a properly | implemented system the same way. You would have to inject a message into | the ongoing session. However, if the protocol authenticates its messages, | you'll never get any response to an injected message. At best, you might | be able to observe some kind of reaction to the injected message. But | that's a channel that can be made very noisy, since it shouldn't occur | often. (BTW, if you use encrypt-then-authenticate, you're completely | immune to this attack, since the implementation won't ever decrypt the | injected message. Of course, there may be a timing attack against the | *authentication*!) | | I agree with your comments about the injection, but I | don't see why the attack doesn't work on the session | passively. Are you assuming that because it is a | session, it's in some way not plausible to match the | inbound packets with outbound packets? I would | have thought that was possible with things like keep | alives and so forth. The only drawback I can see is | that there might not be enough data (hence desire to | tickle things along with an injection). That's basically it. You need to pair up packets that have known (or at least recognizeable) plaintext - or, more accurately, input to the encryptor. (In CTR mode, what matters is the value of the counter, not the plaintext.) Unless the protocol required some externally-visible response to a keep-alive, it would provide you with no information - *nothing* would pair with the keep- alive packet. (Well, I suppose one can imagine an implementation that uses absolute time on its system to a very high degree of precision to determine when to send a keep-alive, and then posit an attacker who can get access to the system time. But given any reasonably typical keep-alive mechanism, this seems pretty unlikely.) A low-level ack to a received message might work. Any higher-level response - one that came from semantic processing of the actual data, not from the low-level bits - is likely to contain so much noise that pulling useful timing out will take more paired, guesssable packets than an attacker will ever see (yet another reason for periodic rekeying, of course). This does point out some interesting interactions. For example, a mode like CBC is harder to attack because you need to know more actual plaintext to determine the input to the encryptor. On the other hand, a mode like CTR may be particularly vulnerable since the input can be determined independently of the actual plaintext. Pre-whitening, even with a (secret) constant (for a particular connection) - something that generally seems pointless - would help. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Ian G [EMAIL PROTECTED] writes: Definitely. Maybe time for a BCP, not just for AES but for general block ciphers? What is a BCP? Best Coding Practices? Block Cipher Protocol? Best Current Practice, a special-case type of RFC. Based on recent experience with this style of collaborative document editing, I've set up a wiki at http://blockcipher.pbwiki.com/, blank username, password 'sbox', for anyone who wants to add their $0.02 about what to do/what not to do to protect block ciphers from side-channel attacks. If it works out, this could turn into a BCP. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Ian G [EMAIL PROTECTED] writes: On Tuesday 21 June 2005 13:45, Peter Gutmann wrote: Best Current Practice, a special-case type of RFC. Based on recent experience with this style of collaborative document editing, I've set up a wiki at http://blockcipher.pbwiki.com/, blank username, password 'sbox', for anyone who wants to add their $0.02 about what to do/what not to do to protect block ciphers from side-channel attacks. If it works out, this could turn into a BCP. That's what I like, action, not words! To celebrate this, I've stuck some words in there which others can act on ;-) Uhh, that wasn't really what I was after, that's pretty much textbook stuff, what I wanted was specifically advice on how to use block ciphers in a way that avoids possibilities for side-channel (and similar) attacks. I have some initial notes that can be summarised as Don't let yourself be used as an oracle that I was planning to add after I've fleshed them out a bit. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
| Uhh, that wasn't really what I was after, that's pretty much textbook stuff, | what I wanted was specifically advice on how to use block ciphers in a way | that avoids possibilities for side-channel (and similar) attacks. I have some | initial notes that can be summarised as Don't let yourself be used as an | oracle that I was planning to add after I've fleshed them out a bit. It strikes me that block ciphers in *communications*get used in two different contexts: - With a long-lived key. This is in protocols like Kerberos, where the long-lived key is used as part of a mechanism to produce a session key. In most more recent protocols, some combination of D-H or public key plays this role. - With a session key. Usage in first of these may be subject to Bernstein's attack. It's much harder to see how one could attack a session key in a properly implemented system the same way. You would have to inject a message into the ongoing session. However, if the protocol authenticates its messages, you'll never get any response to an injected message. At best, you might be able to observe some kind of reaction to the injected message. But that's a channel that can be made very noisy, since it shouldn't occur often. (BTW, if you use encrypt-then-authenticate, you're completely immune to this attack, since the implementation won't ever decrypt the injected message. Of course, there may be a timing attack against the *authentication*!) By their nature, the first class of uses don't usually require the ultimate in performance. Since they receive and respond to small messages involving the encryption of a small amount of data, the encryption portion of the what they do is rarely the major time cost. If this dicotomy holds up, it leads to a simple recommendation: Use a constant-time implementation in the first role; use the highest-performance implementation in the second role. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Ian Grigg [EMAIL PROTECTED] writes: Alternatively, if one is in the unfortunate position of being an oracle for a single block encryption then the packet could be augmented with a cleartext random block to be xor'd with the key each request. Moves you from being an encryption oracle to a related-key oracle, and makes the protocol non-idempotent. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
http://cr.yp.to/talks.html#2005.06.01 has slides that people might find useful as an overview of what's going on. In particular, there's a list of six obstacles to performing array lookups in constant time. People who mention just one of the obstacles are oversimplifying the problem. Hal Finney writes: The one extra piece of information it does return is the encryption of an all-zero packet. So there is a small element of chosen plaintext involved. Known plaintext, not chosen plaintext. I used timings to identify 105 key bits and then compared the remaining 2^23 keys against a known plaintext-ciphertext pair, namely the encrypted zero that you mention. One can carry out the final search with nothing more than known ciphertext: try decrypting the ciphertext with each key and see which result looks most plausible. It should even be possible to carry out a timing attack with nothing more than known ciphertext, by focusing on either the time variability in the last AES-encryption round or the time variability in the first AES-decryption round. Of course, most applications have some known plaintext, and some applications allow chosen plaintext, so even a chosen-plaintext attack is considered to be a fatal flaw in a cryptographic standard. The user isn't supposed to have to worry that someone who influences part of the plaintext will be able to read all the rest. ---D. J. Bernstein, Associate Professor, Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
[EMAIL PROTECTED] (Peter Gutmann) writes: [EMAIL PROTECTED] (Hal Finney) writes: Steven M. Bellovin writes: Dan Bernstein has a new cache timing attack on AES: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf This is a pretty alarming attack. It is? Recovering a key from a server custom-written to act as an oracle for the attacker? By this I don't even mean the timing-related stuff, but just one that just acts as a basic encryption oracle. Try doing that with TLS or SSH, you'll get exactly one unrelated packet back, which is the connection shutdown message. So while it's a nice attack, section 15 should really be simplified to: Don't do that, then. Sadly, it is very hard to avoid chosen plaintext attacks in the real world. Consider, for example, the various new wireless security protocols that have been proposed. For many of them, it should be simple to send chosen data from the internet to a machine on the wireless network. No established connection is needed -- you don't care if it rejects the packets, only that the router sends them -- and if you are in a position to listen in so you can exploit the stolen key, you are also in a position to capture as much ciphertext resulting from the chosen plaintext as you like. Adaptive attacks are quite straightforward in this scenario. This is only one of a number of instances in which it is fairly straightforward to inject data in the real world. Lots of VPN scenarios make it possible. I'd say we should probably be thinking of ways to make sure that AES implementations are safe from this kind of attack. Perry PS Credit where credit is due -- the wireless network example came from Thor Simon. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Peter Gutmann wrote: Stephan Neuhaus [EMAIL PROTECTED] writes: Concerning the practical use of AES, you may be right (even though it would be nice to have some advice on what one *should* do instead). Definitely. Maybe time for a BCP, not just for AES but for general block ciphers? I think so. I find it pretty alarming that in spite of all the review that AES got, [resistance to timing attacks] was not met, and in an exploitable fashion to boot. Well, it depends on what your design assumptions were. [...] In fact I'd say it's actually not possible to certify resistance to timing attacks across all possible CPUs, because it'll always be possible to find some oddball CPU for which an AES-critical instruction somewhere has some weird characteristic that helps in an attack. True, but what we have here is not some oddball CPU, but the fact that a natural AES implementation on one of the most popular CPUs in existence today has this problem. It's a problem because the algorithm (and by extension, any natural implementation of it) isn't supposed to be vulnerable to a timing attack. Lets say you want constant timing for at least the most common CPU family, x86. [...] So in the end you've got an algorithm design that happens to be resistant to timing attacks on the D0 stepping of a Northwood-core Intel P4. Anything else and all bets are off. This doesn't seem very useful to me. I don't know. That cache accesses are faster than memory accesses is not exactly new. I agree totally that we shouldn't insist on constant-time implementations across all possible architectures. This way madness lies. But the fact that it is apparently difficult to produce a fast constant-time implementation on the P4 is definitely a warning sign, especially when resistance to timing attacks was an explicit design criterion. How can we get fast constant-time implementations? (Or even just an implementation that is resistant to timing attacks, which isn't necessarily the same thing?) I don't know. But what you can't do is solicit a cipher that is supposed to be free of timing attacks and then, when one is found, say, well, don't do that then :-) I think this says more about the standardization and review process than about AES. I think the standardisation process went about as well as can be expected, given Newtonian physics-level assumptions about how CPUs work. Again, I don't know. That cache accesses are faster than memory accesses is very much inside the limits of Newtonian physics-level assumptions. If the standardizers had had a testable, implementable phrasing of their design requirements, this embarrassing mistake could have been avoided. Granted, I don't see at the moment how you could phrase this so that the word cache does not already appear somewhere, but I feel that this should have been possible. It's just good engineering practice. IIRC, the timing resistance was accepted on a theoretical argument (that table accesses take constant time); nobody actually tried it out before accepting it. If they had, they would have seen that the implementation was not constant-time. I think this is bad and I still think that the fault lies with the standardization process. Fun, Stephan begin:vcard fn:Stephan Neuhaus n:Neuhaus;Stephan org;quoted-printable:Universit=C3=A4t des Saarlandes;Department of Informatics adr;quoted-printable:;;Postfach 15 11 50;Saarbr=C3=BCcken;;66041;Germany email;internet:[EMAIL PROTECTED] title:Researcher tel;work:+49-681/302-64018 tel;fax:+49-681/302-64012 x-mozilla-html:FALSE url:http://www.st.cs.uni-sb.de/~neuhaus version:2.1 end:vcard
Re: AES cache timing attack
Stephan Neuhaus [EMAIL PROTECTED] writes: Concerning the practical use of AES, you may be right (even though it would be nice to have some advice on what one *should* do instead). Definitely. Maybe time for a BCP, not just for AES but for general block ciphers? But as far as I know, resistance to such attacks was one of the design goals for AES. I find it pretty alarming that in spite of all the review that AES got, this design goal was not met, and in an exploitable fashion to boot. Well, it depends on what your design assumptions were. I assume AES went with a basic Newtonian physics-level approximation of the world that's good enough for most cases without going into so much specialised detail that it becomes unworkable. In fact I'd say it's actually not possible to certify resistance to timing attacks across all possible CPUs, because it'll always be possible to find some oddball CPU for which an AES-critical instruction somewhere has some weird characteristic that helps in an attack. Lets say you want constant timing for at least the most common CPU family, x86. But that's way too broad, so you restrict it to Intel x86. That still covers far too many architectures to be useful, so you say Intel P4 x86. But there are multiple P4 cores that all perform differently, so you decide on the Northwood core. Now, which stepping of that core do you want to use? So in the end you've got an algorithm design that happens to be resistant to timing attacks on the D0 stepping of a Northwood-core Intel P4. Anything else and all bets are off. This doesn't seem very useful to me. I think this says more about the standardization and review process than about AES. I think the standardisation process went about as well as can be expected, given Newtonian physics-level assumptions about how CPUs work. Once you start getting into special relativity-level analysis, the model gets a bit more precise, but you also need a small book of explanatory notes for each situation, and it becomes impossible to ship any normal product if you require per-core-stepping tuning. So I'll stick by my comment that the only really practical way to address this is with Don't do that, then. Now, as you point out, we need a BCP on what not to do. I'd suggest not just a basic don't do this but also a do do this, along with a list of common solutions that get it right: SSL/TLS, SSH, IPsec, etc etc. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
On Mon, Jun 20, 2005 at 01:54:46AM -, D. J. Bernstein wrote: One can carry out the final search with nothing more than known ciphertext: try decrypting the ciphertext with each key and see which result looks most plausible. It should even be possible to carry out a timing attack with nothing more than known ciphertext, by focusing on either the time variability in the last AES-encryption round or the time variability in the first AES-decryption round. Dan, have you looked into or thought about the applicability of your attack to the Kerberos ticket granting service (measure error response time for authenticator + random ticket). The KDC needs to decrypt the ticket with the TGS key, recover the session key and principal name, then check the authenticator. Presumably the time to perform AES decryption will show the same key/data correlations. Quantizing the error response delay could solve this problem, though I for one don't know how to do that portably in a way that guarantees no leakage of timing information. -- /\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
[EMAIL PROTECTED] (Hal Finney) writes: Steven M. Bellovin writes: Dan Bernstein has a new cache timing attack on AES: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf This is a pretty alarming attack. It is? Recovering a key from a server custom-written to act as an oracle for the attacker? By this I don't even mean the timing-related stuff, but just one that just acts as a basic encryption oracle. Try doing that with TLS or SSH, you'll get exactly one unrelated packet back, which is the connection shutdown message. So while it's a nice attack, section 15 should really be simplified to: Don't do that, then. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
On Fri, Jun 17, 2005 at 11:57:29PM +1200, Peter Gutmann wrote: [EMAIL PROTECTED] (Hal Finney) writes: Steven M. Bellovin writes: Dan Bernstein has a new cache timing attack on AES: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf This is a pretty alarming attack. It is? Recovering a key from a server custom-written to act as an oracle for the attacker? By this I don't even mean the timing-related stuff, but just one that just acts as a basic encryption oracle. Try doing that with TLS or SSH, you'll get exactly one unrelated packet back, which is the connection shutdown message. So while it's a nice attack, section 15 should really be simplified to: Don't do that, then. Doesn't the Kerberos TGS, for example, somewhat resemble Dan's server? Yes, it does not report fine-grained time-stamps or do everything in mememory. Still, if one sends data that looks like authenticator + TGT, the TGS is going to decrypt the TGT with the ticket granting service key, getting nonsense and will report an error. The time taken to report the error will be data dependent, and Dan's attack may apply. This is speculative. Has anyone studied the applicability of Dan's attack to a Kerberos 5 KDC with an AES TGS key? -- /\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Peter Gutman writes:
[EMAIL PROTECTED] (Hal Finney) writes:
Steven M. Bellovin writes:
Dan Bernstein has a new cache timing attack on AES:
http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
This is a pretty alarming attack.
It is? Recovering a key from a server custom-written to act as an oracle for
the attacker? By this I don't even mean the timing-related stuff, but just
one that just acts as a basic encryption oracle.
Does it though? Take a look at the code at the end of Dan's paper,
server.c in Appendix A, which I have reproduced below. It does not appear
to act as an encryption oracle. It takes the input, which is *random*
(visible in Appendix C), encrypts it and returns the timing it took to
encrypt it. However, it does not return the encrypted result.
The one extra piece of information it does return is the encryption of
an all-zero packet. So there is a small element of chosen plaintext
involved.
But for all the rest, as far as I can see a passive eavesdropper on an
encrypted channel with a good timer could make it work.
Hal Finney
===
server.c:
#include sys/types.h
#include sys/socket.h
#include netinet/in.h
#include openssl/aes.h
unsigned int timestamp(void)
{
unsigned int bottom;
unsigned int top;
asm volatile(.byte 15;.byte 49 : =a(bottom),=d(top));
return bottom;
}
unsigned char key[16];
AES_KEY expanded;
unsigned char zero[16];
unsigned char scrambledzero[16];
void handle(char out[40],char in[],int len)
{
unsigned char workarea[len * 3];
int i;
for (i = 0;i 40;++i) out[i] = 0;
*(unsigned int *) (out + 32) = timestamp();
if (len 16) return;
for (i = 0;i 16;++i) out[i] = in[i];
for (i = 16;i len;++i) workarea[i] = in[i];
AES_encrypt(in,workarea,expanded);
/* a real server would now check AES-based authenticator, */
/* process legitimate packets, and generate useful output */
for (i = 0;i 16;++i) out[16 + i] = scrambledzero[i];
*(unsigned int *) (out + 36) = timestamp();
}
struct sockaddr_in server;
struct sockaddr_in client; socklen_t clientlen;
int s;
char in[1537];
int r;
char out[40];
main(int argc,char **argv)
{
if (read(0,key,sizeof key) sizeof key) return 111;
AES_set_encrypt_key(key,128,expanded);
AES_encrypt(zero,scrambledzero,expanded);
if (!argv[1]) return 100;
if (!inet_aton(argv[1],server.sin_addr)) return 100;
server.sin_family = AF_INET;
server.sin_port = htons(1);
s = socket(AF_INET,SOCK_DGRAM,0);
if (s == -1) return 111;
if (bind(s,(struct sockaddr *) server,sizeof server) == -1)
return 111;
for (;;) {
clientlen = sizeof client;
r = recvfrom(s,in,sizeof in,0
,(struct sockaddr *) client,clientlen);
if (r 16) continue;
if (r = sizeof in) continue;
handle(out,in,r);
sendto(s,out,40,0,(struct sockaddr *) client,clientlen);
}
}
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Hal Finney wrote: Steven M. Bellovin writes: Dan Bernstein has a new cache timing attack on AES: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf This is a pretty alarming attack. Bernstein was actually able to recover the AES key using a somewhat artificial server which reported its own timing to do an AES operation. In principle the same attack would be possible on a typical remote server, using a larger number of requests to average out timing variations. This is a very nice piece of work by Bernstein but I am not convinced about the practical significance of the attack. And I certainly don't see any reason to abandon some of the design approaches (e.g table lookup) as he has been suggesting just because they are exploitable in some situations. In many situations they are not exploitable at all and in those situations where they might cause problems it is up to system designers to decide whether or not they need to deploy countermeasures. He also had some critical things to say about the AES selection process, which apparently dropped the ball on this issue. Other ciphers got dinged for nonconstant execution time, but no one thought that cache misses would be that significant. Dan has more information at http://cr.yp.to/mac.html, including graphs showing the variability in timings for various implementations at http://cr.yp.to/mac/variability1.html and http://cr.yp.to/mac/variability2.html, and his own attempt at a (nearly) constant-time AES implementation as part of his poly1305-aes MAC function. It would be interesting to see how the speed of his AES implementation compares to that of other widely used versions like Brian Gladman's. How much speed penalty do you pay to get the constant speed? As Dan notes, you can easily make a slow AES that runs at constant speed, but a fast one is far more difficult. Nevertheless Bernstein has shown up one issue that I had not been conscious of and this is that on modern (Intel) x86 systems there is no longer a significant speed penalty for unaligned memory accesses to 32-bit words, a feature that allows AES to be implemented with very much less table space than is normally the case. There is almost no speed penalty in terms of best speed and the typical speed is likely to be a lot better in most practical situations because the load on the cache is greatly reduced. And the timing variability of this code is greatly reduced so its an all round win on the x86. The downside is that, although unaligned accesses on x86 are ok, on many other architectures these cause exceptions and this makes it tedious to build compressed table operation into portable C code. In fact it is so tedious that I am not going to offer this and have instead simply published x86 assembler code which I report on here: http://fp.gladman.plus.com/AES/index.htm For those who can live with x86 only, and with an assembler implementation, this code matches the maximum speed of my large table assembler version on the P3 and P4. Another issue that this raises is that of the crypto API since in those situations where the timing attack matters it is necessary to control the position of the expanded AES key on the stack and this requires that key expansion and encryption is done as one integrated API call, aka: encrypt(key[], in[], out[], no_of_blocks) I hope this helps but if not I will try and answer any other questions. Brian Gladman - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
AES cache timing attack
Dan Bernstein has a new cache timing attack on AES: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf (This was mentioned in Bruce Schneier's CRYPTO-GRAM newsletter.) Briefly, the attack relies on the fact that retrieving an S-box entry from the cache is much faster than retrieving it from main memory; this in turn leaks bits of keying material. One of his claims is that the attack is possible because of the characteristics of efficient software implementations of AES, and that NIST should have realized the problem -- there are ciphers that don't have this problem. He also makes some suggestions to CPU designers about steps they can take to let implementors avoid such traps. For years, it was a commonplace that one should not design one's own encryption algorithms. Some people have extended that advice to apply to cryptographic protocols. Dan Boneh now says he's warning people even against doing their own implementations. --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Steven M. Bellovin writes: Dan Bernstein has a new cache timing attack on AES: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf This is a pretty alarming attack. Bernstein was actually able to recover the AES key using a somewhat artificial server which reported its own timing to do an AES operation. In principle the same attack would be possible on a typical remote server, using a larger number of requests to average out timing variations. He also had some critical things to say about the AES selection process, which apparently dropped the ball on this issue. Other ciphers got dinged for nonconstant execution time, but no one thought that cache misses would be that significant. Dan has more information at http://cr.yp.to/mac.html, including graphs showing the variability in timings for various implementations at http://cr.yp.to/mac/variability1.html and http://cr.yp.to/mac/variability2.html, and his own attempt at a (nearly) constant-time AES implementation as part of his poly1305-aes MAC function. It would be interesting to see how the speed of his AES implementation compares to that of other widely used versions like Brian Gladman's. How much speed penalty do you pay to get the constant speed? As Dan notes, you can easily make a slow AES that runs at constant speed, but a fast one is far more difficult. I also wonder how it would compare to take something like Gladman's (supposing it is faster than Bernstein's), estimate its worst case running time, and then add a delay using a high-res timer from the operating system to make it always take the same time. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
