Advanced Cryptanalysis Side Channel Attacks CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Material based on Information Security by Mark Stamp (Chapter 6.6)
Ryszard Janicki
Side Channel Attacks 1/16
Side Channel Attacks
Sometimes possible to recover key without directly attacking the crypto algorithm
A side channel consists of “incidental information” Side channels can arise due to
The way that a computation is performed Media used, power consumed, emanations, etc.
Induced faults can also reveal information Side channel may reveal a cryptographic key
Ryszard Janicki
Side Channel Attacks 2/16
Types of Side Channels
Emanations security (EMSEC)
Electromagnetic field (EMF) from computer screen can allow
screen image to be reconstructed at a distance Smartcards have been attacked via EMF emanations
Differential power analysis (DPA)
Smartcard power usage depends on the computation
Differential fault analysis (DFA)
Key stored on smartcard in GSM system could be read using a flashbulb to induce faults
Timing analysis
Different computations take different time
RSA keys recovered over a network (openSSL)!
Ryszard Janicki
Side Channel Attacks 3/16
The Scenario
Alice’s public key: (N, e) Alice’s private key: d Trudy wants to find d
Trudy can send any message M to Alice and Alice will respond with Md mod N
That is, Alice signs M and sends result to Trudy
Trudy can precisely time Alice’s computation of Md mod N.
Ryszard Janicki
Side Channel Attacks 4/16
How to Compute Md mod N. Repeated Squaring
Modular exponentiation example
520 = 95367431640625 =⇒
520 mod 35 = 95367431640625 mod 35 = 25mod35
Straightforward computation is very slow as one has to compute 520 = 95367431640625 first in spite of the fact that the final answer is restricted to the range 0 to 34.
Repeated squaring works by building up the exponent one bit at a time.
At each step we double the current exponent and if the binary expansion has a 1 in the corresponding position, we also add one to the exponent.
How can we double (and add one) to an exponent?
Ryszard Janicki
Side Channel Attacks 5/16
Properties of Modular Arithmetic
Modular addition:
((a mod n) + (b mod n)) mod n = (a + b) mod n, for example,
(7 + 12) mod 6 = 19 mod 6 = 1 mod 6
and
(7 + 12) mod 6 = (1 + 0) mod 6 = 1 mod 6
Modular multiplication:
((a mod n)(b mod n)) mod n = ab mod n, (7 · 4) mod 6 = 28 mod 6 = 4 mod 6
and
(7 · 4) mod 6 = (1 · 4) mod 6 = 4 mod 6
Ryszard Janicki
Side Channel Attacks 6/16
Computing Md mod N with Repeated Squaring
Repeated squaring works by building up the exponent one bit at a time.
At each step we double the current exponent and if the binary expansion has a 1 in the corresponding position, we also add one to the exponent.
How can we double (and add one) to an exponent? Considerxy. Wehave(xy)2 =x2y andx·xy =xy+1.
Consequently, we can easily double or add one to any exponent.
From the basic properties of modular arithmetic, we know that we can reduce any intermediate results by the modulus, and thereby avoid extremely large numbers.
Ryszard Janicki
Side Channel Attacks 7/16
Wehave(xy)2=x2y andx·xy =xy+1.
Consider 520 = 95367431640625
First, note that the exponent 20 is, in binary, 10100
The exponent 10100 can be built up one bit at a time, beginning from the high-order bit, as
(0, 1, 10, 101, 1010, 10100) = (0, 1, 2, 5, 10, 20)
As a result, the exponent 20 can be constructed by a series of steps, where each step consists of doubling and, when the next bit in the binary expansion of 20 is a 1, adding one, that is
1=0·2+1 2=1·2 5=2·2+1 10 = 5 · 2 20 = 10·2
Ryszard Janicki
Side Channel Attacks 8/16
We have 20 = 10100,
(0, 1, 10, 101, 1010, 10100) = (0, 1, 2, 5, 10, 20) and 1 = 0 · 2 + 1, 2 = 1 · 2, 5 = 2 · 2 + 1
10 = 5 · 2, 20 = 10 · 2
Now to compute 520, repeated squaring proceeds as
51 mod35=(50)2·51 mod35=5mod35
52 mod35=(51)2 mod35=25mod35
55 mod35=(52)2·51 mod35=252·5=3125mod35=
10 mod 35
510 mod35=(55)2 mod35=102 mod35=
100 mod 35 = 30 mod 35
520 mod35=(510)2 mod35=302 mod35=
900 mod 35 = 25 mod 35
Note that a modular reduction occurs at each step.
Although there are many steps in the repeated squaring algorithm, each step is simple, efficient, and we never have to deal with a number that is greater than the cube of the modulus.
Ryszard Janicki
Side Channel Attacks 9/16
Repeated Squaring Algorithm
The algorithm discussed on previous slides can be described by the following pseudo-code:
Repeated Squaring
x=M
for j = 1 to n
x= mod(x2,N) if dj == 1 then
x= mod(xM,N) end if
next j return x
To make it even more efficient we may use the following mod function (standard builtin mod operation is denoted by “%”):
function mod(x, N) if x ≥ N
x = x%N end if
return x
Ryszard Janicki
Side Channel Attacks 10/16
Timing Attack on RSA
Consider Md mod N
We want to find private key d, where d = d0d1 …dn
Suppose repeated squaring is used used for Md mod N and suppose the following efficient mod function is used:
Efficient Mod Function
(standard builtin mod oper- ation is denoted by “%”)
function mod(x, N) if x ≥ N
x = x%N end if
return x
Repeated Squaring
x=M
for j = 1 to n
x= mod(x2,N) if dj == 1 then
x= mod(xM,N) end if
next j return x
Ryszard Janicki
Side Channel Attacks 11/16
The private key d = d0d1 …dn Ifdj =0then
x= mod(x2,N) Ifdj =1then
x= mod(x2,N) x= mod(x·M,N)
Computation time differs in each case!
Can attacker take advantage of this?
Consider Md mod N
Repeated Squaring
x=M
for j = 1 to n
x= mod(x2,N) ifdj ==1then
x= mod(xM,N) end if
next j return x
Efficient Mod Function
function mod(x, N) if x ≥ N
x = x%N end if
return x
Ryszard Janicki
Side Channel Attacks 12/16
Choose M1 with M12 < N Choose M2 with M2 < N < M13
Let x1 = M1 and x2 = M2 Considerj=1
x1 = mod (x12, N) does no “%” x1= mod(x1·M1,N)doesno“%” x2 = mod (x2, N) does no “%” x2= mod(x2·M2,N)does“%” only if d1 = 1
If d1 = 1 then j = 1 step takes longer forM2 thanforM1
But we have more than one round. . .
Consider Md mod N
Repeated Squaring
x = M
for j = 1 to n
x = mod (x2,N) ifdj ==1then
x= mod(xM,N) end if
next j return x
Efficient Mod Function
function mod(x,N) ifx≥N
x = x%N end if
return x
Ryszard Janicki
Side Channel Attacks 13/16
Timing Attack on RSA
An example of a chosen plaintext attack ChooseM1,M1,...,Mm−1 with
Mi3 < N for i = 0,1,...,m1
Let ti be time to compute Mid mod N, and let
t = (t0 + t1 + . . . + tm−1)/m ChooseM ̃1,M ̃1,...,M ̃m−1 with
M ̃i2 < N < M ̃i3 for i = 0, 1, . . . , m1
Let t ̃ be time to compute M ̃d mod N, and let
ii
t ̃=(t ̃ +t ̃ +...+t ̃ )/m 01 m−1
Ift ̃>t thend1 =1otherwised1 =0 Once d1is known, find d2 then d3 then . . .
Ryszard Janicki
Side Channel Attacks 14/16
Repeated Squaring Resistant to Timing Attack
It is less efficient but practically no time difference between dj =1anddj =0!
x=M
for j = 1 to n
y= mod(x2,N) z= mod(yM,N)
ifdj ==1thenx=zelsex=y
end if next j
return x
z = mod (yM,N) is never used in 50% of all calculations. But timing attack as described before, does not work!
Ryszard Janicki
Side Channel Attacks 15/16
Side Channel Attacks
If crypto is secure Trudy looks for shortcut What is good crypto?
More than mathematical analysis of algorithms
Many other issues (such as side channels) must be considered
Lesson: Attacker’s don’t play by the rules!
Ryszard Janicki
Side Channel Attacks 16/16