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

# AES timing attacks

Started by ●December 4, 2004

Reply by ●December 4, 20042004-12-04

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 littletheory> > 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, abouttwo> > to three orders of magnitude below the the raw turn around time > > itself. > > > > How many messages would need to be sent before the variance beginsto> > 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

Reply by ●December 4, 20042004-12-04

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

Reply by ●December 4, 20042004-12-04

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

Reply by ●December 4, 20042004-12-04

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 littletheory> > 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, abouttwo> > to three orders of magnitude below the the raw turn around time > > itself. > > > > How many messages would need to be sent before the variance beginsto> > 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 aspecific> statistical term meaning the square of a random variable's standard > deviation. It sounds like the difference in the mean of theturn-around> times that is due to the message's relation to the key isdeterministic. 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 leastthree> 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 avariance,> 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 inturn-around> time from the network. In order to collect enough data to find your > deterministic difference you need to send enough messages to bringthe> standard deviation of the random variation of the turn-around timedown> 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 thevariance> of one sample divided by the number of samples in the set. So youneed> to get two averages, one for each of two test messages, and you needto> bring the standard deviations of these down to around the actual > difference in mean between the random processes. This means that ifthe> 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 theorder> 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 sameamount> 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

Reply by ●December 4, 20042004-12-04

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

Reply by ●December 4, 20042004-12-04

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

Reply by ●December 4, 20042004-12-04

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 sameamount> > of time to be sent, no matter how long the actual cryptographytook.> > Even the possibly simpler-to-implement stratagem of holding theoutgoing> message for a pseudorandom interval can easily multiply N by2^plenty-1.> > Traffic seems to be fairly light right now. Here are the times oftwelve> pings to the same DNS: 210 202 202 202 196 202 218 202 190 186 202202.> 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

Reply by ●December 4, 20042004-12-04

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 sameamount> > of time to be sent, no matter how long the actual cryptographytook.> > Even the possibly simpler-to-implement stratagem of holding theoutgoing> message for a pseudorandom interval can easily multiply N by2^plenty-1.> > Traffic seems to be fairly light right now. Here are the times oftwelve> pings to the same DNS: 210 202 202 202 196 202 218 202 190 186 202202.> 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

Reply by ●December 4, 20042004-12-04

Karl Malbrain wrote:> Those times are milliseconds. The attack either adds or not a few cpu > cycles to those times. karl mDoes 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