Re: AES cache timing attack

2005-06-20 Thread D. J. Bernstein
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

2005-06-20 Thread Steven M. Bellovin
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

2005-06-20 Thread Perry E. Metzger

[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

2005-06-20 Thread Stephan Neuhaus

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

2005-06-20 Thread Peter Gutmann
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

2005-06-20 Thread Florian Weimer
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

2005-06-20 Thread Victor Duchovni
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

2005-06-20 Thread Ka-Ping Yee
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

2005-06-20 Thread James Muir
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

2005-06-20 Thread Peter Fairbrother
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

2005-06-20 Thread Taral
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

2005-06-20 Thread James Muir

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

2005-06-20 Thread Anne Lynn Wheeler
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]