Issues of Security with the Oswald-AignerExponentiation Algorithm
Colin D Walter
Comodo Research Lab, Bradford, UK
www.comodogroup.com

Overview
Side Channel Leakage
History
The Oswald-Aigner Exponentiation Algorithm
Recovering Secret Key Bits
Counter-measures
Conclusion

2/16

Side Channel Leakage
Gates use of power is state and data dependent.
Wire transmission of power is data dependent.
— So current & EMR are data dependent.
— For example, noticeable differences between loading data andcommencing a long integer computation.

Conditional Statements are data driven.
— So execution time may be data dependent— For example, a conditional modular subtraction may have only
one arm. So the value of the condition may be deducible.

Conclusion: secret key information may leak.
3/16

History
NSA – no such activity? – Tempest shielding.
Kocher et al (1996-7): Timing & Power side channel papers.
Walter & Thompson (2001): Theory for practical attack on RSA.
Oswald, Aigner, Smart, Liardet (2001): Randomised Algorithms.
Walter (2002): Liardet-Smart – use unblinded keys only once.
Okeya & Sakurai (2002): Oswald-Aigner, special case.
Here (2004): Oswald-Aigner, extended general case.

4/16

The Oswald-Aigner Algorithm
rb = 1
P=P+Q

The Expn Algorithm
contains randomisation
to obscure the relationshipbetween data andside channel leakage.

Q=2Q

11

rb = 1
P=P+Q

P=P-Q

0
1

Q=2Q

rb = 0

Q=2Q

Q=2Q

0

Finite Automaton
to compute P = kQ

rb = 0

1

Q=2Q

10

P=P+Q

Q=2Q

Q=2Q

P=P+Q

2

rb = 0P=P-Q

01

rb = 1Q=2Q

rb = random bit
secret key k: read R to L.

1P=P+Q

P=P+Q

rb = 1Q=2Q

Q=2Q

1
1

Q=2Q

03

rb = 0
P=P-Q
Q=2Q

5/16

Main Assumptions
Suppose:
1. Doubles & Adds can be distinguished using power/EMR/time.
2. Adds & Subtracts are indistinguishable.
3. The secret k is re-used many times (≥10, say) without blinding.
4. The random bits rb are chosen independently
with fixed probability which depends on the current stateof the automaton.
5. k has uniformly distributed, independently chosen bits, ...

6/16

Recovering Secret Key Bits (1)Each point multiplication generates a word over {D,A}
where the number of Ds is the number of bits in k.
– e.g. 11001 yields AD D D AD AD under r-to-l binary expn algm
Here other choices are also possible.

The ith “D” is generated by the ith bit of k, so we can align traces.
Patterns AD, D and DA are possible for a bit.
Between two Ds: DD, DAD and DAAD are possible.
The relative frequencies determine the bit of k.

7/16

Recovering Secret Key Bits (2)Example Strings

Key 11001, Ds aligned:10011

A D

DD A D A DA DDD A D A D AA DD

D A DD A

A DDD A DD A

A D A DD A D A D

A D A DD A D A D A

A D A DD A DD A

A D A DD A DD A←bit order reversed←binary exp case

8/16

Recovering Secret Key Bits (3)1. For each bit pattern, compute frequency of each {A,D} pattern.
2. Deduce the possible bit patterns, ranked by likelihood.
3. Remove inconsistencies where associated bit strings overlap.

Observation: it is easier to recognise bits from longer patterns.

9/16

Recovering Secret Key Bits (4)If p(rb=1) = ½ in each state, then the prob of each state is:0: ⅜ 1: ¼
2: ¼ 3: ⅛
So the prob of each D-to-D sub-string is:
DD

15/32

DAD

16/32

DAAD

1/32

10/16

Recovering Secret Key Bits (5)Example. 2 bits is enough with ~10 traces. For bit pair ki+1ki :DAAD in some trace means it is 11,
DAD or DAAD in some trace means it is not 00,
no DAD or DAAD means 00 (probably),
no DD or DAAD means 10 (probably),
both DD and DAD means it is x1,
both DD and DAD but no DAAD means 01 (probably).
Apply this to example on slide 8.
(Above bit order as in key, but reversed in trace table.)

11/16

Deduction Errors
Using 10 traces to deduce the most likely bit pair and assumingp(rb) = ½, only 1 in 166 bits is incorrect.
It is computationally feasible to search for, and recover, kwith standard ECC key length.
Precisely, k is recovered from O(log log k) tracesand O( (log k)2 ) decryptions
Bits are recovered from local data, not sequentially L-to-R orR-to-L, so less re-computation when errors are made.
Clearly, therefore, this algorithm should not be used where theinitial assumptions hold.

12/16

Counter-Measures
Can the parameters be changed to improve security?
No! Whatever the chosen probability of rb = 1 in a given state,similar deductions can be made.
Solutions:
1. Add fresh, random blinding for each use of k.
2. “Add and always double”, so every DD, DAD and DAAD isdisguised as DAAD (very expensive).
3. “Balanced” code which is the same for A and D.

13/16

Dangers
Longer {A,D}-patterns are more exclusive: the under-lying{0,1}-pattern may have uniquely determined substrings.
Fewer traces but more computation are required with thisapproach.
Experimentally, O(4√k) keys match a pattern given by k.
In fact, about 20 patterns for a 16-bit section of a key,and hence 2016 ≈ 269 decryption checks for a 256-bit key.
This is just computationally feasible.
So a single use of the key with this algorithm may be unsafe(making key blinding insufficient as a counter-measure).

14/16

Alternative Randomised Algorithms
Besides the previous counter-measures, there are moresecure randomised algorithms:

1. MIST: Walter (RSA 2001)
2. Overlapping Windows: Itoh et al (CHES 2002)

15/16

Conclusions
The original randomised algorithm of Oswald & Aigner
can only be used securely for a few times with the same key
unless other counter-measures are employed (although it isundoubtedly more secure than “square and multiply”.)
No parameter choice improves the situation.
Standard counter-measures improve the security.
The analysis is applicable to other randomised algorithms
where at each point the unprocessed part of the key is fixed.
It is clearer how to construct safer randomised algorithms.
There are also suitable alternative algorithms.
16/16