AES timing attacks

Tim Wescott <tim@wescottnospamdesign.com> writes:
> [...]
> I suspect that N may be quite large, and the attack could easily be
> defeated by wrapping your cryptographic algorithm by a process that
> schedules the outgoing message so the reply always takes the same
> amount of time to be sent, no matter how long the actual cryptography
> took.

Damn, Tim! Why spoil a perfectly good theoretical discussion with
a practical suggestion like that?
-- 
%  Randy Yates                  % "Rollin' and riding and slippin' and
%% Fuquay-Varina, NC            %  sliding, it's magic."
%%% 919-577-9882                %  
%%%% <yates@ieee.org>           % 'Living' Thing', *A New World Record*, ELO
http://home.earthlink.net/~yatescr

Randy Yates wrote:

> Tim Wescott <tim@wescottnospamdesign.com> writes:
> 
>>[...]
>>I suspect that N may be quite large, and the attack could easily be
>>defeated by wrapping your cryptographic algorithm by a process that
>>schedules the outgoing message so the reply always takes the same
>>amount of time to be sent, no matter how long the actual cryptography
>>took.
> 
> 
> Damn, Tim! Why spoil a perfectly good theoretical discussion with
> a practical suggestion like that?

Oh gosh, I'm sorry.  I'll go put on my sackcloth shirt, and roll around 
in last week's burn pile, OK?

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Bob Cain wrote:
> Karl Malbrain wrote:
>
> > Those times are milliseconds.  The attack either adds or not a few
cpu
> > cycles to those times.  karl m
>
> Does he present a full attack with this method or only claim
> possible vulnerability because some information about the
> key is extracted?  If the latter, how signifigant is it?

Professor Bernstein has only linked his work to the work of Professor
Boneh, who presents an attack on RSA encryption used by SSL over a
network.  So far it is only a suggestion that the two attacks could be
linked.  The question in this thread is how many messages would be
theoretically required.  So far it's only 1,000.  karl m

Tim Wescott wrote:
> Randy Yates wrote:
>
> > Tim Wescott <tim@wescottnospamdesign.com> writes:
> >
> >>[...]
> >>I suspect that N may be quite large, and the attack could easily be
> >>defeated by wrapping your cryptographic algorithm by a process that
> >>schedules the outgoing message so the reply always takes the same
> >>amount of time to be sent, no matter how long the actual
cryptography
> >>took.
> >
> >
> > Damn, Tim! Why spoil a perfectly good theoretical discussion with
> > a practical suggestion like that?
>

The problem with the practical suggestion you make is that it would
slow down AES encryption time for 16 bytes from 500 cycles currently,
to the time for 192 DRAM accesses, which I've been hearing over on
comp.arch run 250 cycles each.  We're looking to avoid this factor of
100 slowdown on the Athlon and Pentium platforms.

Going back to your earlier answers -- someone suggested we might delay
the algorithm to 10% of the worst case time (the 192 DRAM accesses is
worst case) and get an exponential effect on the number of attack-trial
encryptions required over the channel?
Thanks again for your assistance. karl m

Tim Wescott wrote:
 > [...] This means that if the
 > variance in your network turn-around time is v, and if the difference
 > between message times is t_d, you need to collect somewhere on the order
 > of N = v / t_d^2 of each type of message if you want to discern a
 > difference.

I think you mean  N = (v / t_d)^2.


-- 
--Bryan

Bryan Olson wrote:

 >
 > Tim Wescott wrote:
 >  > [...] This means that if the
 >  > variance in your network turn-around time is v, and if the difference
 >  > between message times is t_d, you need to collect somewhere on the 
order
 >  > of N = v / t_d^2 of each type of message if you want to discern a
 >  > difference.
 >
 > I think you mean  N = (v / t_d)^2.

Oops, my mistake.  The variance is already in seconds^2.


-- 
--Bryan

Bryan Olson wrote:
> Bryan Olson wrote:
>
>  >
>  > Tim Wescott wrote:
>  >  > [...] This means that if the
>  >  > variance in your network turn-around time is v, and if the
difference
>  >  > between message times is t_d, you need to collect somewhere on
the
> order
>  >  > of N = v / t_d^2 of each type of message if you want to discern
a
>  >  > difference.
>  >
>  > I think you mean  N = (v / t_d)^2.
>
> Oops, my mistake.  The variance is already in seconds^2.

Over a wide area network the variance is likely 10^12.  With a message
length of 1K bits and a DS3 transfer rate of 45 mbs, that's 45K
encryptions/second which makes for 50+ years.
Do you know the optical circuit data rate?  karl m

Bryan Olson wrote:
> Bryan Olson wrote:
>
>  >
>  > Tim Wescott wrote:
>  >  > [...] This means that if the
>  >  > variance in your network turn-around time is v, and if the
difference
>  >  > between message times is t_d, you need to collect somewhere on
the
> order
>  >  > of N = v / t_d^2 of each type of message if you want to discern
a
>  >  > difference.
>  >
>  > I think you mean  N = (v / t_d)^2.
>
> Oops, my mistake.  The variance is already in seconds^2.

On a wide area network I estimate the variance is going to run 10^12.
With a DS3 connection of 45mbs that's about 50 years to gather enough
trial encryptions.

karl m

"Randy Yates" <yates@ieee.org> wrote in message
news:653hpr4e.fsf@ieee.org...
> Tim Wescott <tim@wescottnospamdesign.com> writes:
> > [...]
> > I suspect that N may be quite large, and the attack could easily be
> > defeated by wrapping your cryptographic algorithm by a process that
> > schedules the outgoing message so the reply always takes the same
> > amount of time to be sent, no matter how long the actual cryptography
> > took.
>
> Damn, Tim! Why spoil a perfectly good theoretical discussion with
> a practical suggestion like that?
> -- 


Hello Randy,

The RSA algo has a similar vunerability and the standard work around was to
make the encryption/decryption process a constant time one.

Clay

Karl Malbrain wrote:
 > Over a wide area network the variance is likely 10^12.

Standing by itself and with no unit, that's not meaningful.  Tim
had it right (sorry about my previous confusion):

     The key parameters in this case are the deterministic difference in
     turn-around time due to message content and the variance in turn-
     around time from the network.

We can compress this to a single parameter: the signal to noise ratio.
The signal is the expected time difference caused by the key/message
values, and the noise is the standard deviation in the network turn-
around time.  Both are in seconds, so the ratio is a unit-less constant.

In this case, working with noise/signal is a little more convenient
than signal/noise.  We expect the signal to become larger than the noise
when the number of messages exceeds the square of the single-message
noise/signal.

 > With a message
 > length of 1K bits and a DS3 transfer rate of 45 mbs, that's 45K
 > encryptions/second which makes for 50+ years.
 > Do you know the optical circuit data rate?  karl m

Those numbers don't really tell us anything.  If the standard deviation
in the time is 1000 times as large than the key-dependent effect, then
we expect to need on the order of a million messages.


-- 
--Bryan