Timing Cryptanalysis Attack

pck@netcom.com (Paul C. Kocher) writes:

 > I've just released details of an attack many of you will
 > find interesting since quite a few existing cryptography
 > products and systems are potentially at risk.  The general
 > idea of the attack is that secret keys can be found by
 > measuring the amount of time used to to process messages.

I just read this paper, and while it is somewhat interesting, I
don't think the walls of cryptography are in any danger of
crumbling.

People employing systems like PGP are already advised to use them
on private machines, with only one user, and untampered-with
binaries.  Under such circumstances, the collecting of statistics
necessary to employ a timing attack would be difficult at best,
and anyone doing a "black bag" job on the platform would be
better advised to use a direct attack like a passphrase-sniffer
as opposed to a complex statistical approach.

On Networked systems with many users, where one is advised not to
decrypt with or store ones private key, the situation is of
course different.  But again, another user with the ability to
monitor the timing of specific subroutines in ones cryptographic
software or feed that software enough chosen data to generate a
statistical profile of the key, would doubtless have an
opportunity to compromise the system in other ways.

In the particular case of RSA used to sign messages or transmit
session keys, the values being exponentiated are either highly
random or strongly hashed, and the opportunity of an opponent to
time numerical routines with data of his own choosing is
non-existant.

So while this is a very nice piece of work, and certainly of
theoretical interest, I don't think it will modify the way in
which people are advised to utilize cryptographic software, or
cause companies like Netscape of RSADSI to shed any tears.

                                   -Bourbaki 137

On Mon, 11 Dec 1995, Anonymous wrote:
> pck@netcom.com (Paul C. Kocher) writes:
> I just read this paper, and while it is somewhat interesting, I
> don't think the walls of cryptography are in any danger of
> crumbling.
...
> So while this is a very nice piece of work, and certainly of
> theoretical interest, I don't think it will modify the way in
> which people are advised to utilize cryptographic software, or
> cause companies like Netscape of RSADSI to shed any tears.

Read the SKIP spec (SKIP is Sun's IP level encryption protocol).  It uses
Diffle-Hellman certificates.  That means fixed secret DH keys being used
in routers.  It is hard to thing of a better target for this type of
attack.  I have not done a complete read of the SKIP specification (only a
quick scan) so I could be wrong about SKIP but DH certificates sound like
a very very bad idea.  The other source for attack would be any networked
service that is on a local network.  Single user machines are far better
targes than multi-user systems.  That Web server sitting idle not doing
much, repeatedly hit it with https requests and if you are on a local
network, you should be able to get very good timing information. 

I for one will probably add a flag for conditional compilation of my 
bignumber library so that it will take constant time.  This may be a %10 
slow down (using small windows exponentiation) which is trivial compared 
to the %30 speedup I will probably get when I implement a faster mod 
function :-).

eric
--
Eric Young                  | Signature removed since it was generating
AARNet: eay@mincom.oz.au    | more followups than the message contents :-)

Eric Young writes:
> Read the SKIP spec (SKIP is Sun's IP level encryption protocol).  It uses
> Diffle-Hellman certificates.

Photuris, which likely will be the standard way to do this sort of
thing on top of IPsec, also suffers from the problem, but I suspect
the next version of the draft (number 9) will have it fixed.

More interesting is the fact that a number of NSA vetted protocols
seem to have the flaw. Obviously, they either didn't know or didn't
say anything about it to the folks designing such stuff...

Perry

Eric Young wrote:
> 
> I for one will probably add a flag for conditional compilation of my
> bignumber library so that it will take constant time.  This may be a
> %10 slow down (using small windows exponentiation) which is trivial
> compared to the %30 speedup I will probably get when I implement a
> faster mod function :-).

Careful.  Even if you can make the number of executed instructions the
same, you still have to worry about timing differences due to branches
and the way the hardware multiplier handles different operands.

-- 
Sure we spend a lot of money, but that doesn't mean | Tom Weinstein
we *do* anything.  --  Washington DC motto          | tomw@netscape.com

On Mon, 11 Dec 1995, Tom Weinstein wrote:
> Careful.  Even if you can make the number of executed instructions the
> same, you still have to worry about timing differences due to branches
> and the way the hardware multiplier handles different operands.

Granted.  For my particular library, there are no major 'if statements' I 
believe (I'll check) after you get out of the mod_exp function and into 
the mod and mul sub parts.  As for the multiplier, I just had a look at 
my old 386 book and yup, it does take an argument dependent time... I've 
been around pipelined RISC cpus too long...

eric 
--
Eric Young                  | Signature removed since it was generating
AARNet: eay@mincom.oz.au    | more followups than the message contents :-)

Tom Weinstein writes:
> > I for one will probably add a flag for conditional compilation of my
> > bignumber library so that it will take constant time.  This may be a
> > %10 slow down (using small windows exponentiation) which is trivial
> > compared to the %30 speedup I will probably get when I implement a
> > faster mod function :-).
> 
> Careful.  Even if you can make the number of executed instructions the
> same, you still have to worry about timing differences due to branches
> and the way the hardware multiplier handles different operands.

The trivial way to handle this is simply to check user time with the
right system calls and make sure it always comes out the same with an
apropriate number of sleeps.

Perry

>The trivial way to handle this is simply to check user time with the
>right system calls and make sure it always comes out the same with an
>apropriate number of sleeps.

Of course, this works against a remote adversary, but not against one
on the same machine who can look at actual CPU consumption (which doesn't
increase when the target is blocked).

-matt

Matt Blaze writes:

> Of course, this works against a remote adversary, but not against one
> on the same machine who can look at actual CPU consumption (which doesn't
> increase when the target is blocked).

Maybe this is a good reason to spinwait, rather than sleep, until
the timer expires.  It would be pretty subtle to distinguish that
from "real" computation.

Peter Monta

In message <199512120056.QAA16055@mage.qualcomm.com>, Peter Monta writes:
>> Of course, this works against a remote adversary, but not against one
>> on the same machine who can look at actual CPU consumption (which doesn't
>> increase when the target is blocked).
>
>Maybe this is a good reason to spinwait, rather than sleep, until
>the timer expires.  It would be pretty subtle to distinguish that
>from "real" computation.

Across a net it should be hard.  On the same CPU it may be easy.  Some
CPUs with hardware branch prediction keep track of how many branches were
correctly and incorrectly predected.  These registers are not allways
protected, and not allways "made virtual" by the OS.

If your spin wait is of the form:

LOAD #big_number, R1
L1:
DEC R1
BNE L1

(a.k.a "for(i = big_number; i--;) { }")

Then the "number of correctly predicted branches" will go up by approximatly
big_number...

(in all honesty the only CPU I am sure "allows" normal user programs to
see the performance registers is the AMD29xxx series, and that is only
if the OS sets the right bit in the register protection mask.  I know
the P6 has such performance registers, but don't know if they are protected,
and I think the P5 has them, but again I don't know if they are protected.
I think some of the Alpha's have them, but seem to remember them being
protected (and I use to think it was a dumb idea...))

Matt Blaze writes:
> >The trivial way to handle this is simply to check user time with the
> >right system calls and make sure it always comes out the same with an
> >apropriate number of sleeps.
> 
> Of course, this works against a remote adversary, but not against one
> on the same machine who can look at actual CPU consumption (which doesn't
> increase when the target is blocked).

True enough, but using busy loops could handle that. However, I must
admit to being far more interested in handling the remote case
efficiently, especially given concerns people have about using
Photuris like systems on heavily pounded servers.

Perry

Perry E. Metzger wrote:
> 
> The trivial way to handle this is simply to check user time with the
> right system calls and make sure it always comes out the same with an
> apropriate number of sleeps.

The problem with that approach is that if the system is heavily loaded,
it can take an arbitrarily large amount of user time.  Somewhat better
is to sleep for a random amount of time after you're done.  That will
smear out the time distribution making it harder to get a statistically
meaningful number of samples.  It also increases your latency, but
doesn't hurt throughput on a busy system.

-- 
Sure we spend a lot of money, but that doesn't mean | Tom Weinstein
we *do* anything.  --  Washington DC motto          | tomw@netscape.com

Tom Weinstein writes:
> Perry E. Metzger wrote:
> > The trivial way to handle this is simply to check user time with the
> > right system calls and make sure it always comes out the same with an
> > apropriate number of sleeps.
> 
> The problem with that approach is that if the system is heavily loaded,
> it can take an arbitrarily large amount of user time.

Totally untrue. The process can take an arbitrary amount of wall clock
time, not user time.

In the case of the heavily loaded machine, the problem is gone -- the
opponent can't precisely predict this. Provided you take the same
amount of process time no matter what, you are okay.

(To be technical, user time doesn't pass during sleeps, but that
doesn't matter -- the problem gets fixed anyway).

> Somewhat better is to sleep for a random amount of time after you're
> done.

I don't think so. First of all, you can still extract some
information. If you have been gone as long as the maximum computation
plus the maximum random fudge, you know that you had to have conducted
the maximum computation. This means that some bits are indeed
leaking. Your approach also has the disadvantage that it is hard to
produce good random numbers -- you are perhaps familiar with that problem?

Perry

Perry E. Metzger wrote:
> 
> Tom Weinstein writes:
>
> > The problem with that approach is that if the system is heavily
> > loaded, it can take an arbitrarily large amount of user time.
> 
> Totally untrue. The process can take an arbitrary amount of wall clock
> time, not user time.

Whoops.  You are absolutely correct.  Pardon my brain-damage.  I
was thinking wall clock time, as you indicated.

> > Somewhat better is to sleep for a random amount of time after you're
> > done.
> 
> I don't think so. First of all, you can still extract some
> information. If you have been gone as long as the maximum computation
> plus the maximum random fudge, you know that you had to have conducted
> the maximum computation. This means that some bits are indeed
> leaking. Your approach also has the disadvantage that it is hard to
> produce good random numbers -- you are perhaps familiar with that
> problem?

Yes, you are correct.  It's better than taking a fixed amount of wall
clock time, but definitely not better than a fixed amount of user
time.

As Paul mentions in his extended abstract, there is actually an easy way
to fix the problem without hurting either latency or throughput much. 
If you blind and and unblind around the modular exponentiation, it
appears impossible to perform this attack.  Because you don't know the
inputs to the exponentiation operation, you can't make any predictions
based on those inputs.

-- 
Sure we spend a lot of money, but that doesn't mean | Tom Weinstein
we *do* anything.  --  Washington DC motto          | tomw@netscape.com

> > I for one will probably add a flag for conditional compilation of my
> > bignumber library so that it will take constant time.  This may be a
> > %10 slow down (using small windows exponentiation) which is trivial
> > compared to the %30 speedup I will probably get when I implement a
> > faster mod function :-).
> 
> Careful.  Even if you can make the number of executed instructions the
> same, you still have to worry about timing differences due to branches
> and the way the hardware multiplier handles different operands.

No, he's saying to equalize wall-clock time---just pad out beyond the
largest possible execution time with a timer.  Surely with a sufficient
pad the timing-channel leak can be made negligible (though the author
seems to claim otherwise---I should read the explanation!).

Peter Monta

Hey, don't go for constant time, that's too hard to get perfect.  Add a
*random* delay.  This particular crypto-flaw is pretty easy to fix. 
(See, I'm not *always* arguing the downside of cryptography!)

It is worth noting, however, the extent to which "secure" cryptographic
protocols keep needing to get fixed one last time....  -- Nathaniel
--------
Nathaniel Borenstein <nsb@fv.com>       | (Tense Hot Alien In Barn)
Chief Scientist, First Virtual Holdings | VIRTUAL YELLOW RIBBON:
FAQ & PGP key: nsb+faq@nsb.fv.com       | http://www.netresponse.com/zldf

> Nathaniel Borenstein <nsb@nsb.fv.com> writes:
> Hey, don't go for constant time, that's too hard to get perfect.  Add a
> *random* delay.  This particular crypto-flaw is pretty easy to fix. 
> (See, I'm not *always* arguing the downside of cryptography!)

Random delay may be harder to get perfect than constant time.  Note that
the actual time for the transaction is the minimum of all the transaction
times you measure, since you can't add a negative delay to them.  It's
presumably even easier if the random distribution is known.  Adding a
random delay means more transactions are required to find each new bit,
but information is still leaking.

> It is worth noting, however, the extent to which "secure" cryptographic
> protocols keep needing to get fixed one last time....  -- Nathaniel

Amen...

	Jim Gillogly
	Trewesday, 21 Foreyule S.R. 1995, 19:16

Jim Gillogly wrote:

| > Nathaniel Borenstein <nsb@nsb.fv.com> writes:
| > Hey, don't go for constant time, that's too hard to get perfect.  Add a
| > *random* delay.  This particular crypto-flaw is pretty easy to fix. 
| > (See, I'm not *always* arguing the downside of cryptography!)
| 
| Random delay may be harder to get perfect than constant time.  Note that
| the actual time for the transaction is the minimum of all the transaction
| times you measure, since you can't add a negative delay to them.  It's
| presumably even easier if the random distribution is known.  Adding a
| random delay means more transactions are required to find each new bit,
| but information is still leaking.

	Does the delay have to be random, or does the total time for a
transacation need to be unrelated to the bits in the secret key?
Assume that the time added is pseudo-random (and confidential).
Further, for any non-overlapping group of N transactions, the
distribution of the times fits some predetermined curve, say a bell
curve.

	We've added a non random number, but since those numbers end
up being a curve, it would be difficult to determine which transaction
got which time added to it.  This resembles the 'make them all a
constant time', but allows us to send out some in a shorter time than
the maximum (although most transactions should probably take longer
than the average.)

Adam

-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume

> Jim Gillogly wrote:
> 
> | > Nathaniel Borenstein <nsb@nsb.fv.com> writes:
> | > Hey, don't go for constant time, that's too hard to get perfect.  Add a
> | > *random* delay.  This particular crypto-flaw is pretty easy to fix. 
> | > (See, I'm not *always* arguing the downside of cryptography!)
> 
> 	Does the delay have to be random, or does the total time for a
> transacation need to be unrelated to the bits in the secret key?
> Assume that the time added is pseudo-random (and confidential).
> Further, for any non-overlapping group of N transactions, the
> distribution of the times fits some predetermined curve, say a bell
> curve.

Random time won't save you - it just increases the noise, thus reducing
the effective bandwidth of the covert channel.  To get the time, I only
need to do enough repetitions of the same computation to eliminate the
effect of the randomness and I have the same resulting information about
the key.

The only way to completely remove covert channels is by making the
measurable time completely independent of the actual time.

One way with the RSA might be to do the encryption with the key and the
inverse of the key (hence all 0s become 1s and 1s become 0s).

-> See: Info-Sec Heaven at URL http://all.net/
Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236

Nope, I'm wrong, as Fred and Simon point out.  The noise makes
finding the times more difficult by some small factor, nothing more.
I'll stop writing these things in the morning. :)

I wrote:

| 	Does the delay have to be random, or does the total time for a
| transacation need to be unrelated to the bits in the secret key?
| Assume that the time added is pseudo-random (and confidential).
| Further, for any non-overlapping group of N transactions, the
| distribution of the times fits some predetermined curve, say a bell
| curve.
| 
| 	We've added a non random number, but since those numbers end
| up being a curve, it would be difficult to determine which transaction
| got which time added to it.  This resembles the 'make them all a
| constant time', but allows us to send out some in a shorter time than
| the maximum (although most transactions should probably take longer
| than the average.)

Dr. Frederick B. Cohen wrote:
> 
> One way with the RSA might be to do the encryption with the key and
> the inverse of the key (hence all 0s become 1s and 1s become 0s).

Nope, this doesn't work.

-- 
Sure we spend a lot of money, but that doesn't mean | Tom Weinstein
we *do* anything.  --  Washington DC motto          | tomw@netscape.com

Anonymous wrote:
> So while this is a very nice piece of work, and certainly of
> theoretical interest, I don't think it will modify the way in
> which people are advised to utilize cryptographic software, or
> cause companies like Netscape of RSADSI to shed any tears.

  While an exploit of this attack against our software has not
been demonstrated, and there is some debate about whether it
will even work, we are taking it very seriously.  We've been
working with Paul to develop a fix, which we will implement
even if the attack is never proven effective against our software.

	--Jeff

PS - I think Paul was a bit surprised when Jim Barksdale pulled
out his wallet and handed him 10 crisp $100 bills.  :-)
-- 
Jeff Weinstein - Electronic Munitions Specialist
Netscape Communication Corporation
jsw@netscape.com - http://home.netscape.com/people/jsw
Any opinions expressed above are mine.

Jeff Weinstein wrote:

| PS - I think Paul was a bit surprised when Jim Barksdale pulled
| out his wallet and handed him 10 crisp $100 bills.  :-)

Great.  mention it where the IRS is sure to be listening.  :)


-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume

Adam Shostack wrote:
> 
> Jeff Weinstein wrote:
> 
> | PS - I think Paul was a bit surprised when Jim Barksdale pulled
> | out his wallet and handed him 10 crisp $100 bills.  :-)
> 
> Great.  mention it where the IRS is sure to be listening.  :)

  I know the spooks hang out here, but I didn't think the IRS
did.  Maybe the NSA just forwards them all net traffic that
includes the words cash, bills, etc.  :-)

  Since Paul mentioned it on his web page, and it was also
in a press release, I figured it was OK.

	--Jeff

-- 
Jeff Weinstein - Electronic Munitions Specialist
Netscape Communication Corporation
jsw@netscape.com - http://home.netscape.com/people/jsw
Any opinions expressed above are mine.

On Mon, 11 Dec 1995, Adam Shostack wrote:

> Jeff Weinstein wrote:
> 
> | PS - I think Paul was a bit surprised when Jim Barksdale pulled
> | out his wallet and handed him 10 crisp $100 bills.  :-)
> 
> Great.  mention it where the IRS is sure to be listening.  :)
> 

Why would the IRS listen?  Everyone knows the tax system is voluntary.
 
> -- 
> "It is seldom that liberty of any kind is lost all at once."
> 					               -Hume
> 
> 

---
My prefered and soon to be permanent e-mail address: unicorn@schloss.li
"In fact, had Bancroft not existed,       potestas scientiae in usu est
Franklin might have had to invent him."    in nihilum nil posse reverti
00B9289C28DC0E55  E16D5378B81E1C96 - Finger for Current Key Information

On Mon, 11 Dec 1995, Jeff Weinstein wrote:

> 
>   While an exploit of this attack against our software has not
> been demonstrated, and there is some debate about whether it
> will even work, we are taking it very seriously.  We've been
> working with Paul to develop a fix, which we will implement
> even if the attack is never proven effective against our software.
> 

My gut & scribble-on-the-back-of-a-napkin feeling about this class of 
attack is that it could be a problem for smartcards (almost certainly), 
and possibly for non-routed networks (possibly - napkin was too small  
:-), but is not going to viable on internetworks where routers are in 
use; if a packet enters a queue at any point in its path, then the 
transit time will be quantised by the time it drains the queue, which is 
basically controlled by the time it takes to drain previously queued 
packets; this will destroy any microsecond level correlations that may 
have been leaked. Ron is supposed to be doing a presentation at WWW IV 
later this week - hopefully he'll give his opinion on this.

Definitely a really neat hack, even if it isn't always practical.

Simon
p.s.

 Someone mentioned adding random timings instead of padding out to a 
constant time. This won't work (adding noise doesn't destroy a signal - 
just increases the effort needed to isolate it)

Anonymous writes:
> I just read this paper, and while it is somewhat interesting, I
> don't think the walls of cryptography are in any danger of
> crumbling.
> 
> People employing systems like PGP are already advised to use them
> on private machines, with only one user, and untampered-with
> binaries.

Timings like the ones listed are trivial to take in establishing
things like SSL sessions, or Photuris sessions. The danger is to
online protocols, not to PGP.

Any reason you felt you had to say this anonymously?

Perry