AES timing attacks

On sci.crypt we're having a discussion about side-channel timing
attacks on the encryption algorithm, AES.  I'm missing a little theory
and could use some help.

The basic idea of the attack is to send in a TCP/IP message to a
server over an AES channel and time the resulting turnaround time,
which will vary depending on how the message relates to the
cryptographic key.  The timing variance is extremely small, about two
to three orders of magnitude below the the raw turn around time
itself.

How many messages would need to be sent before the variance begins to
be discernable, with say 50% accuracy?

Thanks, karl m

Mok-Kong Shen wrote:
> karl malbrain wrote:
>
> > On sci.crypt we're having a discussion about side-channel timing
> > attacks on the encryption algorithm, AES.  I'm missing a little
theory
> > and could use some help.
> >
> > The basic idea of the attack is to send in a TCP/IP message to a
> > server over an AES channel and time the resulting turnaround time,
> > which will vary depending on how the message relates to the
> > cryptographic key.  The timing variance is extremely small, about
two
> > to three orders of magnitude below the the raw turn around time
> > itself.
> >
> > How many messages would need to be sent before the variance begins
to
> > be discernable, with say 50% accuracy?
>
> A very dumb question: Do I understand correctly that you send
> stuff from your computer to a remote server? If yes, aren't
> there arbitrarily large transmission delays possible which
> are barely under one's control? Thanks.

Yes there are.  I'm assuming a near-perfect configuration where the
server is accessible over a local area network subject to random delays
that I estimate are two to three orders of magnitude larger in size
than the signal in question.  karl m

karl malbrain wrote:

> On sci.crypt we're having a discussion about side-channel timing
> attacks on the encryption algorithm, AES.  I'm missing a little theory
> and could use some help.
> 
> The basic idea of the attack is to send in a TCP/IP message to a
> server over an AES channel and time the resulting turnaround time,
> which will vary depending on how the message relates to the
> cryptographic key.  The timing variance is extremely small, about two
> to three orders of magnitude below the the raw turn around time
> itself.
> 
> How many messages would need to be sent before the variance begins to
> be discernable, with say 50% accuracy?

A very dumb question: Do I understand correctly that you send
stuff from your computer to a remote server? If yes, aren't
there arbitrarily large transmission delays possible which
are barely under one's control? Thanks.

M. K. Shen

karl malbrain wrote:

> On sci.crypt we're having a discussion about side-channel timing
> attacks on the encryption algorithm, AES.  I'm missing a little theory
> and could use some help.
> 
> The basic idea of the attack is to send in a TCP/IP message to a
> server over an AES channel and time the resulting turnaround time,
> which will vary depending on how the message relates to the
> cryptographic key.  The timing variance is extremely small, about two
> to three orders of magnitude below the the raw turn around time
> itself.
> 
> How many messages would need to be sent before the variance begins to
> be discernable, with say 50% accuracy?
> 
> Thanks, karl m

I haven't had my coffee yet this morning so this'll wander a bit:

By "variance" you probably mean "difference" -- "variance" is a specific 
statistical term meaning the square of a random variable's standard 
deviation.  It sounds like the difference in the mean of the turn-around 
times that is due to the message's relation to the key is deterministic. 
  If this is so it should _not_ be called a "variance".

In terms of a detection/estimation problem you have a signal that you 
want to analyze (the turn-around time) that consists of at least three 
components: the one you're interested in is the relatively small 
difference in turn-around time as a function of the message content, 
then there's the average network-based turn around time, and finally 
there's the random variation in network-based turn around time, which 
you want to mask out (and any random variation _does_ have a variance, 
which is important to us).

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.  In order to collect enough data to find your 
deterministic difference you need to send enough messages to bring the 
standard deviation of the random variation of the turn-around time down 
around the value of the deterministic difference (I'm not going ot 
calculate it precisely).

One of the classic results of statistics is that the variance of the 
average of a set of samples of a random process is equal to the variance 
of one sample divided by the number of samples in the set.  So you need 
to get two averages, one for each of two test messages, and you need to 
bring the standard deviations of these down to around the actual 
difference in mean between the random processes.  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 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.

-- 

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

Tim Wescott wrote:
> karl malbrain wrote:
>
> > On sci.crypt we're having a discussion about side-channel timing
> > attacks on the encryption algorithm, AES.  I'm missing a little
theory
> > and could use some help.
> >
> > The basic idea of the attack is to send in a TCP/IP message to a
> > server over an AES channel and time the resulting turnaround time,
> > which will vary depending on how the message relates to the
> > cryptographic key.  The timing variance is extremely small, about
two
> > to three orders of magnitude below the the raw turn around time
> > itself.
> >
> > How many messages would need to be sent before the variance begins
to
> > be discernable, with say 50% accuracy?
> >
> > Thanks, karl m
>
> I haven't had my coffee yet this morning so this'll wander a bit:
>
> By "variance" you probably mean "difference" -- "variance" is a
specific
> statistical term meaning the square of a random variable's standard
> deviation.  It sounds like the difference in the mean of the
turn-around
> times that is due to the message's relation to the key is
deterministic.

Yes, that's correct.

>   If this is so it should _not_ be called a "variance".

Thank you.

> In terms of a detection/estimation problem you have a signal that you

> want to analyze (the turn-around time) that consists of at least
three
> components: the one you're interested in is the relatively small
> difference in turn-around time as a function of the message content,
> then there's the average network-based turn around time, and finally
> there's the random variation in network-based turn around time, which

> you want to mask out (and any random variation _does_ have a
variance,
> which is important to us).

OK.

> 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.  In order to collect enough data to find your
> deterministic difference you need to send enough messages to bring
the
> standard deviation of the random variation of the turn-around time
down
> around the value of the deterministic difference (I'm not going ot
> calculate it precisely).

I'm using data from a paper "Remote timing attacks are Practical" by
Professor Boneh at Stanford.  From figure 3 the timing difference due
to random network noise is about two to three orders of magnitude
larger than the deterministic difference.


> One of the classic results of statistics is that the variance of the
> average of a set of samples of a random process is equal to the
variance
> of one sample divided by the number of samples in the set.  So you
need
> to get two averages, one for each of two test messages, and you need
to
> bring the standard deviations of these down to around the actual
> difference in mean between the random processes.  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.

v = 1000, t_d = 1

> 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.

Unfortunately, N is actually quite small.  Your comment appears to
match the concensus.  Thanks, karl m

Tim Wescott wrote:

  ...

> I suspect that N may be quite large, 

Amen to that!

> 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.

Even the possibly simpler-to-implement stratagem of holding the outgoing
message for a pseudorandom interval can easily multiply N by 2^plenty-1.

Traffic seems to be fairly light right now. Here are the times of twelve
pings to the same DNS: 210 202 202 202 196 202 218 202 190 186 202 202.
It's interesting that seven of those twelve took the second-longest
time, but I don't know what to make of it.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:
> Tim Wescott wrote:
> 
>   ...
> 
> 
>>I suspect that N may be quite large, 
> 
> 
> Amen to that!
> 
> 
>>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.
> 
> 
> Even the possibly simpler-to-implement stratagem of holding the outgoing
> message for a pseudorandom interval can easily multiply N by 2^plenty-1.
> 
> Traffic seems to be fairly light right now. Here are the times of twelve
> pings to the same DNS: 210 202 202 202 196 202 218 202 190 186 202 202.
> It's interesting that seven of those twelve took the second-longest
> time, but I don't know what to make of it.
> 
> Jerry

Your experiment points to another problem: given non-Gaussian noise a 
linear process (such as averaging) is not necessarily the optimal estimator.

-- 

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

Jerry Avins wrote:
> Tim Wescott wrote:
>
>   ...
>
> > I suspect that N may be quite large,
>
> Amen to that!
>
> > 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.
>
> Even the possibly simpler-to-implement stratagem of holding the
outgoing
> message for a pseudorandom interval can easily multiply N by
2^plenty-1.
>
> Traffic seems to be fairly light right now. Here are the times of
twelve
> pings to the same DNS: 210 202 202 202 196 202 218 202 190 186 202
202.
> It's interesting that seven of those twelve took the second-longest
> time, but I don't know what to make of it.

Those times are milliseconds.  Professor Bernstein's timing attack uses
a few cpu cycles added to those times.  karl m

Jerry Avins wrote:
> Tim Wescott wrote:
>
>   ...
>
> > I suspect that N may be quite large,
>
> Amen to that!
>
> > 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.
>
> Even the possibly simpler-to-implement stratagem of holding the
outgoing
> message for a pseudorandom interval can easily multiply N by
2^plenty-1.
>
> Traffic seems to be fairly light right now. Here are the times of
twelve
> pings to the same DNS: 210 202 202 202 196 202 218 202 190 186 202
202.
> It's interesting that seven of those twelve took the second-longest
> time, but I don't know what to make of it.

Those times are milliseconds.  The attack either adds or not a few cpu
cycles to those times.  karl m

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?


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein