Transcript Mist Exponentiation Algorithm

MIST
A Randomized Exponentiation Algorithm
for Reducing Side Channel Leakage
Colin D. Walter
formerly: www.co.umist.ac.uk (Manchester, UK)
[email protected]
now: www.comodo.net (Bradford, UK)
[email protected]
Power Analysis Attacks
• With no counter-measures and the binary expn algm,
averaging power traces at the same instants during several
expns enables one to differentiate squares and multiplies
and hence deduce the exponent bits.
• Averaging power traces over individual digit-by-digit products
in a single expn enables one to differentiate multiplicands
in m-ary expn and hence deduce the exponent.
• Smartcards have limited scope for including expensive,
tamper-resistant, hardware measures.
• Good software counter-measures are required: new algorithms
as well as modifying arguments e.g. E to E+r(M).
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
2
Requirements for Exponentiation
• New algorithm, not new inputs, as single expn
may be attacked.
• Different pattern of Squares and Multiplies to
frustrate averaging.
• No re-use of multiplicands (same reason)
• No fully determined tie between Square or
Multiply and known process.
• Good time and space efficiency
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
3
History
• T. S. Messerges, E.A. Dabbish & R.H. Sloan
Power Analysis Attacks of Modular Exponentiation
in Smartcards CHES 99 , LNCS 1717
• E. Oswald & M. Aigner
Randomized Addition-Subtraction Chains as a
Countermeasure against Power Attacks
CHES 2001, LNCS 2162
• C. D. Walter Exponentiation using Division Chains
IEEE TC 47, 1998, pp 757–765
• C. D. Walter MIST: An efficient, randomized …
CT-RSA 2002, LNCS 2271, pp 53 – 66
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
4
Binary Expn Algorithm (r-to-l)
{ To compute: ResultM = ME }
StartM  M ;
ResultM  1 ;
While E > 0 do
Begin
If (E mod 2) = 1 then
ResultM  StartM×ResultM ;
StartM  StartM2 ;
E  E div 2 ;
End
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
5
m-ary Expn (Reversed)
{ To compute: ResultM = ME }
StartM  M ;
ResultM  1 ;
While E > 0 do
Begin
R  E mod m ;
If R  0 then
ResultM  StartMR × ResultM ;
StartM  StartMm ;
E  E div m ;
{ Invariant: ME.Init = StartME × ResultM }
End
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
6
The MIST Expn Algorithm
{ To compute: ResultM = ME }
StartM  M ;
ResultM  1 ;
While E > 0 do
Begin
Choose a random “divisor”D ;
R  E mod D ;
If R  0 then
ResultM  StartMR × ResultM ;
StartM  StartMD ;
E  E div D ;
{ Invariant: ME.Init = StartME × ResultM }
End
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
7
Addition Chains
The main computational part of the loop is:
If R  0 then
ResultM  StartMR × ResultM ;
StartM  StartMD
• To provide the required efficiency, a set of possible values for
D are chosen so that an efficient addition chain for D contains
R, e.g.
1+1=2, 2+1=3, 2+3=5 is an addition chain for D=5
suitable for when R = 0, 1, 2 or 3.
• Comparable to the m-ary method regarding time complexity
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
8
Example
Choose the set of divisors {2, 3, 5}. Consider E = 257
E
257
D, R
5, 2
StartM
1
StartM/TempM
1+1 = 2
ResultM
0+2 = 2
51
3, 0
5
17
2, 1
15
8
4
2
1
2, 0
2, 0
2, 0
*, 1
Cambridge 2002
30
60
120
240
1+2 = 3
3+2 = 5
5+5 = 10
10+5 = 15
15+2 = 17
15 + 15 = 30
30 + 30 = 60
60 + 60 = 120
120+120 = 240
240+17 = 257
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
9
Choice of Divisor Set
• Security: Divisors must be chosen so that sequences of
squares and multiplies do not reveal D.
• Efficiency:
– Divisors must be chosen so that raising to the power
D is (time) efficient enough.
– Space is required to store addition chains.
– As few registers as possible should be used for the
exponentiation.
• Solution: Take the set of divisors {2,3,5}.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
10
Addition Sub-Chains
• For each pair (D,R) we need an addition chain which
calculates StartMD and StartMR efficiently.
1+1 = 2
1+1 = 2 ; 1+2 = 3
1+1 = 2 ; 1+2 = 3 ; 2+3 = 5
1+1 = 2 ; 2+2 = 4 ; 1+4 = 5
for D = 2, any R
for D = 3, any R
for D = 5, any R  4
for D = 5, R = 4
• These are minimal, i.e. fewest possible multns.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
11
Addition Sub-Chains
• We need instructions which include the update of ResultM.
• Use 1 for location of StartM, 2 for TempM, 3 for ResultM:
(111)
(112, 133)
(112, 121)
(112, 133, 121)
(112, 233, 121)
(112, 121, 121)
(112, 133, 121, 121)
(112, 233, 121, 121)
(112, 121, 133, 121)
(112, 222, 233, 121)
Cambridge 2002
for (D,R) = (2,0)
for (D,R) = (2,1)
for (D,R) = (3,0)
for (D,R) = (3,1)
for (D,R) = (3,2)
for (D,R) = (5,0)
for (D,R) = (5,1)
for (D,R) = (5,2)
for (D,R) = (5,3)
for (D,R) = (5,4)
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
12
Addition Sub-Chains
• There is choice about these sub-chains which give rise to
additional random behaviour.
• These are chosen deliberately to increase strength against
some potential attacks which we look at later.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
13
Choice of Divisor
Example choice:
D0;
If Random(8) < 7 then
If (E mod 2) = 0 then D  2 else
If (E mod 5) = 0 then D  5 else
If (E mod 3) = 0 then D  3 ;
If D = 0 then
Begin
p  Random(8) ;
If p < 6 then D  2 else
If p < 7 then D  3 else
D5
End
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
14
Choice of Divisor
– Choosing D when E  0 mod D is efficient because it
avoids a multiplication by StartMR.
– Choosing such D deterministically is unsafe,
so they should not be chosen always.
– Some pairs (D,R) require fewer multiplications per than
others per bit of reduction in the size of E.
We should choose the more efficient ones more
frequently.
– The CT-RSA paper gives some details on ordering them.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
15
A Markov Process
• Divisors affect the frequencies of residues E mod 30
(30 = LCM of divisor set):
– Choice of divisors 3, 5 when E is odd multiple of 3 or 5
reduces frequency of even residues.
– With the exceptions of 14 and 25, odd & even residues
occur with probability > 1/30 and < 1/30 resp.
– After several iterations, 3, 9, 11, 21, 29 are all three times
more likely to occur than the least likely residue 16.
• We need to model this as a Markov process, looking
at the limit probabilities of each residue mod 30.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
16
Probability of each (D,R)
• The matrix of probabilities of each output residue
mod 30 for each input residue enables the limit
probability of each residue to be computed.
• Let pij = proby of input E  i mod 30
giving output E  j mod 30
Construct matrix P = ( pij )
Pn = ( pij(n) ) has pij(n) = proby of output j from input i.
For large n, pij(n) is independent of i and so gives limit
probability pj of E  j mod 30.
pij(n) approaches pj at about 1 bit per increment of n.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
17
Probability of each (D,R)
• This gives the probabilities:
pD = ipipD|i
for each divisor D
pD,R = iR mod 30 pipD|i for each pair (D,R)
For the divisor selection process above:
p2 = 0.629
p3 = 0.228
p5 = 0.142
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
18
Avage Addn Chain Properties
• The probabilities of addition sub-chain lengths are:
length 1 is p2,0
= 0.354
length 2 is p3,0 + p2,1
= 0.458
length 3 is p5,0 + p3,1 + p3,2
= 0.139
length 4 is p5,1 + p5,2 + p5,3 + p5,4 = 0.049
• So average divisor sub-chain has length 1.883 mults
• Av decrease in E is 2p23p35p5 = 2.500 per subchain
• So 0.757 log2E subchains & 1.425 log2E mults
• This is faster than the binary expn algorithm
and marginally slower than 4-ary expn
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
19
Choice of Divisor
Initial choice above:
D0;
If Random(8) < 7 then
If (E mod 2) = 0 then D  2 else
If (E mod 5) = 0 then D  5 else
If (E mod 3) = 0 then D  3 ;
If D = 0 then
Begin
p  Random(8) ;
If p < 6 then D  2 else
If p < 7 then D  3 else
D5
End
Avge: 1.4247×log2E multns
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
20
Choice of Divisor
A semi-deterministic choice:
D0;
{ Delete this line: If Random(8) < 7 then }
If (E mod 2) = 0 then D  2 else
If (E mod 5) = 0 then D  5 else
If (E mod 3) = 0 then D  3 ;
If D = 0 then
Begin
p  Random(8) ;
If p < 6 then D  2 else
If p < 7 then D  3 else
D5
End
Avge: 1.4197×log2E multns
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
21
Choice of Divisor
A cheaper choice:
D0;
If Random(4) < 3 then
If (E mod 2) = 0 then D  2 else
If (E mod 3) = 0 then D  3 ;
If D = 0 then
If Random(4) < 3 then D  2 else
D3
Avge: 1.4696×log2E multns
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
22
Space Requirements
• There are 3 long integer registers: StartM, TempM,
ResultM (cf 2 for binary expn, 3 for 4-ary expn.)
• E can be fully processed before each expn, using log210
bits per divisor for (D,R), i.e. about 2.5 log2E bits in all.
• If multn instructions are determined in advance,
5 bits are needed for each, so about 7n bits to store
(but these may be generated as required).
• The addition sub-chains for each pair (D,R)
must be stored in ROM:
under 256 bits for the table in the CT-RSA paper.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
23
Other Processing
Apart from the long integer multiplicative operations,
processing includes:
• Generation of random numbers: 5.26 bits per divisor, or
4n bits for exponents of n bits.
• Divisions of E by D: equivalent to a few long integer
multiplications overall (depending on CPU word size).
• Since the multiplier output is not always used as an input
to the next operation (e.g. when ResultM is updated),
data movement is slightly greater than for binary or
4-ary, but still insignificant overall.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
24
Efficiency Overview
• We have deduced that:
– MIST is comparable to 4-ary exponentiation in
terms of space and time use.
– There are many ways of implementing the
algorithm.
– Similar methods to those above will establish
their time and space efficiencies.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
25
Data Leakage
• MIST prevents the usual power trace averaging associated with
power analysis attacks, but:
• The sequence of Squares and Mults parses in too many ways to
enable pairs (D,R) to be recovered: (2,1) & (3,0) are the same.
• Making deterministic choices for D is poor practice:
they may provide a handle to distinguish between correct and
incorrect keys.
• Processing of E and choosing of divisors must be well hidden:
computing E div D may leak. It is much shorter than a long
integer multiplication, so should leak much less. Don’t do it
after processing the long integer mults of the previous divisor.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
26
S&M Chains
• Assume an attacker can distinguish Squares and Multiplies
from a single exponentiation (e.g. they may have different freqs
for conditional modular subns)
• A division chain is the list of pairs (D,R) used in an expn
scheme. It determines the addition chain to be used, and hence
the sequence of squares and multiplies which occur:
(2,0)
(3,1), (3,2), (5,0)
(5,4)
S
SMM
SSMM
(2,1), (3,0)
(5,1), (5,2), (5,3)
SM
SMMM
• Divisor sub-chain boundaries are deduced from occurrences of S
except for ambiguity between (5,4) and (2,0)(3,x) or (2,0)(5,0).
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
27
S&M Chains
• There is/are:
1 way to interpret
2 ways to interpret
3 ways to interpret
4 ways to interpret
4 ways to interpret
S
SM
SMM with no preceding S
SMM with preceding S
SMMM
• Using the known probabilities for each occurring:
THEOREM: The search space for exponents with
the same S&M sequence as E has size approx E3/5.
• For 4-ary, it is much easier to average traces,
easier to be certain of the S&M sequence,
and the search space is only E7/18 – which is smaller.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
28
Operand Re-Use
• From its location, address, power use in multn or Hamming
weight, it may be possible to identify re-use of operands.
Assume we know when operands are equal, but nothing more.
– since only squares have equal operands, this means the
S&M sequence can be recovered.
– for classical m-ary & sliding windows expn, there is a
different pre-computed multiplicand for each expt digit,
so the secret exponent can be reconstructed uniquely.
• MIST operand sharing leaves ambiguities:
– (2,1) and (3,0) have the same operand sharing pattern.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
29
Operand Re-Use
• THEOREM: With MIST, the search space for
exponents with the same operand sharing
sequence as E has size approx E1/3.
– this assumes opd sharing is determined fully accurately
from one exponentiation;
– it also assumes a free choice of divisors at each step;
– the search space for m-ary expn has size E0.
• It isn’t clear if recovery from errors is possible.
• Selecting exact divisors will vastly decrease the search.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
30
Deterministic Choices
Example:
SMMM S SM SM M
The last M comes from E=1 being reduced to E=0.
Previous SM is (2,1) or (3,0), from E = 2*1+1 or 3*1+0, so E=3.
In fact divisor 3 must be chosen, since only it divides exactly.
Previous SM is from E = 2*3+1=7 or 3*3+0=9.
No restriction applies here.
Previous S is from E = 2*7 = 14 or 2*9 = 18.
Here only divisor 2 is available and only 2 is applicable.
Initial SMMM is from (5,1), (5,2) or (5,3). Residue 2 will generate
even E, so divisors should be 2, not 5.
So initial E is:
5*14+1 = 71 or 5*14+3 = 73 or 5*18+1 = 91 or 5*18+3 = 93.
The last requires divisor 3 not 5, so initial E is 71, 73 or 91.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
31
Deterministic Choices
• The deterministic constraints cut the search space for E.
• By how much? Consecutive divisor choices are not
independent, so theory simplified this way is inadequate.
• When the divisor is chosen deterministically and these
constraints are taken into account:
THEOREM: The search space for exponents with
the same S&M sequence as E has size approx E1/4.
• It is still computationally infeasible to recover E.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
32
Deterministic Choices
• Knowledge of opd sharing cuts the search space further.
• By how much? Simulations were used to find out.
• When the divisor is chosen deterministically and these
constraints are taken into account:
THEOREM: The search space for exponents with the
same opd sharing sequence as E has size approx E0.115.
• It may now be computationally feasible to recover E:
768-bit exponents give search space of size 288,
1024-bit known RSA modulus with CRT has size only 259.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
33
Knowing the Modulus
• Knowledge of the public RSA modulus/exponent means
we know the top half of the private exponent up to a few
choices. Let E´ be this approximation to E.
• Assume there is no exponent blinding, and CRT not used.
• If E0 is the exponent created correctly from the final half
of the division chain, and  is the product of all the initial
divisors, then  = E div E0 = E´ div E0.
• This enables the correct E0 to be selected from only
E0.058 choices and completed to E in linear time.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
34
Difficulties?
• The above does reduce recovery of 1024-bit exponents
to a feasible computation, but it requires:
– correct identification of opd sharing
– no CRT and minimal exponent blinding
– small public exponent, etc.
• There is no known way to recover from any mistakes; only a
few can vastly increase the search space.
• There is no known way to combine results from other
exponentiations.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
35
Conclusion
• A novel expn algm suitable for RSA on smartcard.
• Random choices make some averaging for DPA
impossible.
• Time comparable to 4-ary expn.
• Space comparable to 4-ary expn.
• Areas of security concern have been narrowed.
• Deterministic divisor choices may be dangerous.
• MIST is much stronger against power analysis
than standard expn algms.
Cambridge 2002
Colin D. Walter, Comodo Research Lab, Bradford
Next Generation Digital Security Solutions
36