20-CS-5156 |
Security Vulnerability Assessment |
Spring 2017 |
---|---|---|

Lab 5 |

**Determine Keybits from Timing Data**

BackgroundSome cryptographic schemes have mathematical properties which make them difficult to attack mathematically. However, some of these are vulnerable to other methods of attack, such as timimg attacks, that were largely unknown when the schemes were first embraced. A case in point are algorithms which rely on modular exponentiation, like this:
is a string of bits representing,
say, a message, m is a private key, and
d is a publicly known modulus. An
eavedropper intercepting n could use a fast
algorithm for finding the modular log of S
to find the private key but no such algorithm is known if the keysize is a
couple of thousand bits long, hence the claim of security.
S
Unfortunately, the algorithm for computing : S function iterates modpow times, one time for each bit of private key
w (the size exp of key w is
computed on line exp). When an iteration is
on a key bit that has value 1, line 04 is
computed. Otherwise, line 07 is computed.
Clearly, on a computer for which an iteration on a 1 key bit always takes the
same amount of time and likewise for a 0 key bit, the 1 key bit iterations will
always take longer than the 0 key bit iterations because line 09 will always take more time than line 07. This would allow an attacker to determine the
key bits easily by running a spy process that measures the time of each
iteration of 09. However, such a
computer is not likely to be used by a victim that uses modpow. But, an attacker can use statistics from a
number of input samples to get most of the key bits: more correct key bits
will be acquired as the number of samples increases. Here's how.
modpow
The attacker collects some large number of input samples,
,
m_{2},
....
The attacker measures and records the time of each of
m_{p}
iterations on each w input for
both key bit 0 and key bit 1. That's a total of
m_{i}*w*p measurements.
These will be referenced below as
2
where iterTime_{i,k,b} refers to sample
i,
m_{i} refers to a key bit,
and k refers to the value of the
key bit. Note that the times for the same iteration on the same key bit value
will differ from input to input due to non-deterministic changes in execution by
the operating system and other threads running on the same machine. For
example, for key bit 0 and 5 inputs the following might be recorded (in
nanoseconds):b for key value 0: Observe that, over all inputs, sometimes the measured time is less for a 0 value of key bit and sometimes it is more. The attacker also has the victim exponentiate samples and modulus d. This is easily possible if, for example, the key
is used to sign plaintext messages. The attacker's spy thread watches the
victim's code as it iterates and creates a table of times from victim start to
victim's n iteration, for
k^{th} from 0 to k. There are a number of ways a spy thread can know
when the victim thread is running a particular operation and therefore is at a
particular point in the loop, particularly if both threads share some hardware
resources such as a multiplier. Let this table be indexed as w-1.
Consider the two differences:
spyTime_{i,k}
(2)
abs(iterTime_{i,0,1}-spyTime_{i,0})
If the 0
random samples
p with mean
X_{i}. Let
μ be (1) or (2).
The smallest resulting variance of the two cases will likely determine
the 0X_{i}^{th} key bit if the sample size is large enough, hence we
call this a guess. Once the first key bit is guessed the attacker can
guess the second key bit in the same way using times associated with the
first two iterations (the attacker has this information for the spy
thread and can get it from the
table that was constructed from experiments). Assuming the random values
are independent (probably reasonable) the variance of the second key bit
difference is only affected by the correctness of the second guessed key bit
and again the lowest variance fingers the likely key bit value.
This process may be repeated to guess the remaining key bits with high
likelihood that the key bits have been found.
iterTime
tables.
The number of input samples these tables are built for is given by the user
as will be shown below. The spyTime_{i,k}
tables are built from a fixed key of 32 bits. Access to these tables is
through the following functions:
spyTime
The file lab5.c shows how to use lab5aux.o. Compile this file and link it to lab5aux.o with the following:
run it like this, for example:
which produces tables for 30 input samples and prints those tables.
Your assignment is to modify Upload both the code and your guess of the key (binary, decimal, or hex). |