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]
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 #include #include #include 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]
US DoJ wants ISPs to be forced to log their customers activities
Quoting: The U.S. Department of Justice is quietly shopping around the explosive idea of requiring Internet service providers to retain records of their customers' online activities. http://news.com.com/Your+ISP+as+Net+watchdog/2100-1028_3-5748649.html -- Perry E. Metzger[EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Crypto 2005 papers on SHA-0 and SHA-1 collisions
Wang et al. published their Crypto 2005 papers on SHA-0 and SHA-1 collisions. Maybe you find it interesting http://www.infosec.sdu.edu.cn/people/wangxiaoyun.htm Vlastimil Klima -- Nechte si zasilat do mailu denni prehled nejzajimavejsich clanku z portalu VOLNY. http://web.volny.cz/mailinfo/ - 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: de-identification
"Steven M. Bellovin" writes: | > | >Ladies and Gentlemen, | > | >I'd like to come up to speed on the state of the | >art in de-identification (~=anonymization) of data | >especially monitoring data (firewall/hids logs, say). | >A little googling suggests that this is an academic | >subspeciality as well as a word with many interpretations. | >If someone here can point me at the mother lode of | >insight, I would be most grateful. | > | | What's your threat model? It's proved to be a very hard problem to | solve, since there are all sorts of other channels -- application data, | timing data (the remote fingerprinting paper mentioned this one), etc. Steve, et al., My threat model is how can I have a convincing technical solution that, in turn, gets your average corporate general counsel to permit sharing various kinds of logs with similar firms. The Patriot Act (2001,Bush), PDD 63 (1998,Clinton), and various other intervening bits of legislation say that threat and vulnerability information shared between like private sector firms is (1) exempt from Anti-Trust (even where security is a competitive feature) and (2) exempt from FOIA (even where such sharing is under government aegis). Nevertheless no corporate general counsel will permit such sharing. From where a GC sits, the risk is clear, near-term and direct to the firm while any benefit is diffuse and distant, and no GC believes any laws' words until the courts, as unacknowledged legislators, get a whack at it and that being so no GC wants to be the test case. Ipso facto, I (we) need a way to ensure that log data can be shared between firms in ways that do not identify the source firm so that, in turn, I can stand up and say that the risk as seen from the GC's point of view has been technically put to bed. I don't imagine for a minute that even that argument will be trivial, but a technical solution is necessary even if insufficient. My real aim is, of course, the characterization of macro-scale risk to critical infrastructure. In the hypothesis-generation stage of such an effort I need to take field observations that could easily go any of three ways: (1) All the players see the same scans, the same automated attacks, the same over-pressure; (2) All the players see entirely different scans, entirely different automated attacks, entirely different over-pressures; or (3) One of the players stands apart from the others and whereas the corpus of that industrial sector sees the same scans, the same automated attacks, the same over-pressure there is one player whose experience is different. This is information that no firm can get on its own, so uniqueness of value is a given and amongst rational players unarguable. What I need is to break the logjam over being the first to share. The only alternative is to take the biased samples that are available inside managed security providers and confidential consulting firms and pool that data, thus anonymizing it, within a single corporate shell. This is second best and tends to have little motive power of its own, though I/we proved it can be done[1] as has Qualys[2], inter alia. Clear enough? --dan [1] http://www.atstake.com/research/reports/acrobat/atstake_app_reloaded.pdf [2] http://www.qualys.com/company/newsroom/newsreleases/usa/pr.php/2004-07-28 - 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]