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]
massive data theft at MasterCard processor
MasterCard reported the exposure of up to 40,000,000 credit card numbers at CardSystems Solutions, a third-party processor of credit card data. CardSystems was infected with a script that targeted specific data. In other words, this wasn't the usual carelessness, this was enemy action, and of a sophisticated nature. See http://www.mastercardinternational.com/cgi-bin/newsroom.cgi?id=1038 for the official statement. Designing a system that deflects this sort of attack is challenging. The right answer is smart cards that can digitally sign transactions, but that would require rolling out new readers to all the merchants. That's doable, about once per decade -- and at least one credit card vendor (JP Morgan-Chase) is using the opportunity to push out RFID-based credit card readers instead. So the marketing department outranks the security department -- big surprise there --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
[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]
RSA signatures without padding
I came across an application which uses RSA signatures on plain MD5 hashes, without padding (the more significant bits are all zero). Even worse, the application doesn't check if the padding bits are actually zero during signature verification. The downside is that the encryption exponent is fairly large, compared to the modules (27 vs 1024 bits). A few hundred signed messages have been published so far. What do you think? Are attacks against this application feasible? (It should be corrected, of course, but it's not clear if a high-priority update is needed.) - 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: massive data theft at MasterCard processor
On Fri, 17 Jun 2005, Steven M. Bellovin wrote: Designing a system that deflects this sort of attack is challenging. The right answer is smart cards that can digitally sign transactions, but that would require rolling out new readers to all the merchants. I was amazed to hear of the UK's fast progress in rolling out their Chip-and-PIN system. I would not have guessed that they could get about 85% of cardholders to switch and 75% of retail equipment upgraded by the end of 2004, only 15 months after the beginning of the rollout. http://www.chipandpin.co.uk/reflib/super_barometer_2004.pdf Naturally, conditions are different in the United States, but it's still an impressive result. -- ?!ng - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RSA signatures without padding
There is an attack against this type of RSA signature scheme, although cannot remember just now if it requires that the verfication exponent be small (ie. e=3). The attack I am trying to recall is a chosen-message attack and its efficiency is related to the probability that a random 128-bit integer can be factorized over a small set of primes (ie. the prob that a uniformily selected 128-bit integer is B-smooth for a small integer B). Basically, you pick a message for which you'd like to forge a signature, find a variant of the message that hashes to a B-smooth 128-bit integer, and then you construct the forgery after solving a linear system modulo e (the linear system incorporates the signatures on the chosen messages). I can't think of a reference for this but I will post another message if I find it. -James On Mon, 20 Jun 2005, Florian Weimer wrote: I came across an application which uses RSA signatures on plain MD5 hashes, without padding (the more significant bits are all zero). Even worse, the application doesn't check if the padding bits are actually zero during signature verification. The downside is that the encryption exponent is fairly large, compared to the modules (27 vs 1024 bits). A few hundred signed messages have been published so far. What do you think? Are attacks against this application feasible? (It should be corrected, of course, but it's not clear if a high-priority update is needed.) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: massive data theft at MasterCard processor
Steven M. Bellovin wrote: Designing a system that deflects this sort of attack is challenging. The right answer is smart cards that can digitally sign transactions No, it isn't! A handwritten signature is far better, it gives post-facto evidence about who authorised the transaction - it is hard to fake a signature so well that later analysis can't detect the forgery, and few people would bother to do it that well anyway, while it is easy enough to enter a PIN with digital reproducibility. Also there are several attacks on Chip n' PIN as deployed here in the UK, starting with the fake reader attacks - for instance, a fake reader says you are authorising a payment for $6.99 while in fact the card and PIN are being used to authorise a transaction for $10,000 across the street. They get quite complex, there's the double-dip, where the $6.99 transaction is also made, and the delayed double dip, where a reader belonging to a crook makes the $10,000 transaction several days later (the crook has to skip town with the money in this attack - so far. Except of course he never existed in the first place, and maybe ...). Then there's probably a Bank-wide attack, where an expensive attack on one card can break all the cards used by one bank - ouch! because the Banks haven't actually issued cards that digitally sign the transaction (and it would make little difference to many of the fake reader attacks if they had), but just reuse one key or a key with an offset or XOR on the card to generate a keyed hash of the transaction for authorisation. There are some more classes of attacks too. It's a bit early to say about many of them, but it looks like there are a goodly number of going-to-be successful attacks. This might not matter that much except to the banks, but the liability for what appears to be a PIN-authorised transaction is being foisted off on the cardholder, who has litle recourse to proof that he didn't make the transaction when one of these attacks is made. I don't have any Chip n' PIN cards, and I don't want any either. I'm sticking with signatures. -- Peter Fairbrother - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RSA signatures without padding
On 6/20/05, James Muir [EMAIL PROTECTED] wrote: The attack I am trying to recall is a chosen-message attack and its efficiency is related to the probability that a random 128-bit integer can be factorized over a small set of primes (ie. the prob that a uniformily selected 128-bit integer is B-smooth for a small integer B). Basically, you pick a message for which you'd like to forge a signature, find a variant of the message that hashes to a B-smooth 128-bit integer, and then you construct the forgery after solving a linear system modulo e (the linear system incorporates the signatures on the chosen messages). I think you're referring to the Desmedt-Odlyzko selective forgery attack. See http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1014_Menezes.sigs.pdf -- Taral [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RSA signatures without padding
Taral wrote: On 6/20/05, James Muir [EMAIL PROTECTED] wrote: The attack I am trying to recall is a chosen-message attack and its efficiency is related to the probability that a random 128-bit integer can be factorized over a small set of primes (ie. the prob that a uniformily selected 128-bit integer is B-smooth for a small integer B). Basically, you pick a message for which you'd like to forge a signature, find a variant of the message that hashes to a B-smooth 128-bit integer, and then you construct the forgery after solving a linear system modulo e (the linear system incorporates the signatures on the chosen messages). I think you're referring to the Desmedt-Odlyzko selective forgery attack. See http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1014_Menezes.sigs.pdf Yes, that's it. Thanks for the URL. -James - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: massive data theft at MasterCard processor
Steven M. Bellovin wrote: MasterCard reported the exposure of up to 40,000,000 credit card numbers at CardSystems Solutions, a third-party processor of credit card data. CardSystems was infected with a script that targeted specific data. In other words, this wasn't the usual carelessness, this was enemy action, and of a sophisticated nature. See http://www.mastercardinternational.com/cgi-bin/newsroom.cgi?id=1038 for the official statement. Designing a system that deflects this sort of attack is challenging. The right answer is smart cards that can digitally sign transactions, but that would require rolling out new readers to all the merchants. That's doable, about once per decade -- and at least one credit card vendor (JP Morgan-Chase) is using the opportunity to push out RFID-based credit card readers instead. So the marketing department outranks the security department -- big surprise there reference to posting in a usenet n.g. in a thread that talked about putting encryption everywhere as a solution http://www.garlic.com/~lynn/2005k.html#55 Encryption Everywhere? http://www.garlic.com/~lynn/2005k.html#56 Encryption Everywhere? as referenced in the above ... x9.59 http://www.garlic.com/~lynn/index.html#x959 has countermeasure against the harvesting vulnerability (w/o requiring any encryption) which is so attractive to attackers because the return is so enormous for the amount of effort http://www.garlic.com/~lynn/subpubkey.html#harvest it is a countermeasure to fraudulent terminals. there was some effort in x9a10 working group (which was tasked with preserving the integrity of the financial infrastructure for *ALL* retail payments, regardless of kind, debit, credit, stored-value, etc ... and/or environment) with regard to trusted terminal modules somewhat akin to EU finread standard and existing POS security modules ... but with the addition that the terminal also digitally signed the same transaction. the consumer would digitally signed for authentication ... and the trusted terminal would also digitally co-sign authenticating the terminal used. the issue is there is still some vulnerability involving terminal overlays (analogous to what has been read about regarding ATM cash machine overlays ... although not for harvesting ... since x9.59 closed that hole ... but for transaction misrepresntation ... the payback isn't nearly as attractive as compared to harvesting tho). so one of the AADS chip strawman suggestions for x9.59 from the 90s http://www.garlic.com/~lynn/index.html#aads was the same protocol and transaction whether it was with the merchant terminals ... or with a consumer owned pda/cellphone device (any kind of wireless to the merchant device) ... where a paranoid consumer would always maintain physical control of their private display and keypad. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
