AES timing attacks

Started by karl malbrain December 4, 2004
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