Leakage-Resilient Primitives using Re-keying · 03-27-2014 1 / 24 Leakage-Resilient Encryption Scheme Leakage-Resilient PRNG with Input Conclusion Side-Channel Attacks Countermeasures

03-27-2014 1 / 24

Leakage-Resilient Encryption SchemeLeakage-Resilient PRNG with Input

Conclusion

Side-Channel AttacksCountermeasures

Leakage-Resilient Primitives using Re-keyingJournées Codage et Cryptographie 2014

Sonia Belaïd1,2

École Normale Supérieure, 45 rue d’Ulm 75005 Paris

Thales Communications & Security

[email protected]

Sonia Belaïd Leakage-Resilient Primitives using Re-keying

03-27-2014 2 / 24


Conclusion


Side-Channel Attacks

I physical leakage

• timing

• power consumption

• temperature

• . . .

I statistical treatment

I key recovery


03-27-2014 3 / 24


Conclusion


Countermeasures against Side-Channel Attacks

Masking

sensitive values randomized:

x replaced by (xm,m0, . . . ,md−1)

x = xm ?m0 ? · · · ?md−1

Drawbacks of Masking

8 higher-order attacks8 performances

Re-keying


03-27-2014 3 / 24


Conclusion


Countermeasures against Side-Channel Attacks

Masking

sensitive values randomized:

x replaced by (xm,m0, . . . ,md−1)

x = xm ?m0 ? · · · ?md−1

Drawbacks of Masking

8 higher-order attacks8 performances

Re-keying


03-27-2014 4 / 24


Conclusion


Goal

Goal:I build leakage-resilient primitivesI practical for use in constrained devices

Leakage-Resilient Cryptography Model- only computation leaks- bounded amount of leakage per

invocation- unlimited number of invocations

Practical constraints:- limited code size- limited storage- reasonable

execution time


03-27-2014 5 / 24


Conclusion


Outline

1 Leakage-Resilient Encryption Scheme

2 Leakage-Resilient PRNG with Input

3 Conclusion


03-27-2014 6 / 24


Conclusion

ContextLeakage-Resilient ConstructionsPractical Analysis

Outline



3 Conclusion


03-27-2014 7 / 24


Conclusion


Encryption Scheme

encryption schemeplaintext

secret key

ciphertext

Goal: efficient and leakage-resilient encryption scheme

Related Work: Kocher’s patent 1999 but- multiple use of the same key- no security proof

Contribution: Leakage-Resilient Symmetric Encryption via Re-keyingMichel Abdalla, Sonia Belaïd, Pierre-Alain FouqueCHES 2013: 471-488


03-27-2014 7 / 24


Conclusion


Encryption Scheme

encryption schemeplaintext

secret key

ciphertext

Goal: efficient and leakage-resilient encryption scheme

Related Work: Kocher’s patent 1999 but- multiple use of the same key- no security proof

Contribution: Leakage-Resilient Symmetric Encryption via Re-keyingMichel Abdalla, Sonia Belaïd, Pierre-Alain FouqueCHES 2013: 471-488


03-27-2014 8 / 24


Conclusion


Contributions

Scheme 1 LR encryption scheme using a LR PRFScheme 2 Instantiation of Scheme 1 with the [FPS12] LR PRFScheme 3 more efficient and still LR encryption scheme with a

tweaked (not LR and not PRF) function


03-27-2014 9 / 24


Conclusion


Schemes 1 and 2

• Re-keying PrimitiveI leakage-resilient PRF

• Block CipherI as a PRFI not leakage-resilient

- instantiated with the [FPS12] LR PRFFaust, Pietrzak, Schipper: Practical Leakage-Resilient Symmetric Cryptography. CHES 2012


03-27-2014 9 / 24


Conclusion


Schemes 1 and 2





03-27-2014 9 / 24


Conclusion


Schemes 1 and 2





03-27-2014 9 / 24


Conclusion


Schemes 1 and 2





03-27-2014 9 / 24


Conclusion


Schemes 1 and 2





03-27-2014 9 / 24


Conclusion


Schemes 1 and 2





03-27-2014 10 / 24


Conclusion


Scheme 3: More Efficient LR Encryption Scheme

LR Encryption Scheme from

4 re-keying function(not LR, not PRF)

4 block cipher

with

4 short-cuts between keys

4 uniformly random values:- one triplet per level [FPS12],- PRG with public seed [YS13]

but

8 additional constraint on themessage


03-27-2014 11 / 24


Conclusion


Security Aspects

I block cipher with random inputs→ plaintext added to the output

I same primitive for the block cipher and the weak PRFs

I secret keys used at most three times :

→ avoid the recomputation of previous keys


03-27-2014 12 / 24


Conclusion


Instantiation

weakPRF


03-27-2014 12 / 24


Conclusion


Instantiation

weakPRF

blockcipher


03-27-2014 12 / 24


Conclusion


Instantiation

weakPRF

blockcipher PRG


03-27-2014 12 / 24


Conclusion


Instantiation

weakPRF

blockcipher PRG

unmaskedAES


03-27-2014 13 / 24


Conclusion

ContextPRNG with Input from CCS 2013Leakage-Resilient Generic ConstructionInstantiation

Outline



3 Conclusion


03-27-2014 14 / 24


Conclusion


Pseudo-Random Generators

Goal: efficient and leakage-resilient PRNG

Related Works: PRNG- robust with input: Dodis et al. CCS’13- leakage-resilient: Yu et al. CCS’10

Contribution: Leakage-Resilient PRNG with InputMichel Abdalla, Sonia Belaïd, David Pointcheval, Sylvain Ruhault,Damien Vergnaud


03-27-2014 14 / 24


Conclusion


Pseudo-Random Generators

Goal: efficient and leakage-resilient PRNG

Related Works: PRNG- robust with input: Dodis et al. CCS’13- leakage-resilient: Yu et al. CCS’10

Contribution: Leakage-Resilient PRNG with InputMichel Abdalla, Sonia Belaïd, David Pointcheval, Sylvain Ruhault,Damien Vergnaud


03-27-2014 15 / 24


Conclusion


PRNG with Input from CCS 2013

I setup() outputs seed = (X ,X ′);

I S = refresh(S, I;X ) = S · X + I;

I (S,R) = next(S;X ′) = G([X ′S]m1 ).

G : {0,1}m → {0,1}n+` is a secure PRG (K ← [X ′S]m1 ).


03-27-2014 16 / 24


Conclusion


Security Properties

Attacker A Capabilities

I ask for outputs (S,R)

I compromise the inputs II compromise the internal state S

RobustnessIf enough entropy is provided, A cannotdistinguish (S,R) from a uniformly randomstring with a significant advantage.


03-27-2014 16 / 24


Conclusion


Security Properties

Attacker A CapabilitiesI ask for outputs (S,R)




03-27-2014 16 / 24


Conclusion


Security Properties


I compromise the inputs I

I compromise the internal state S



03-27-2014 16 / 24


Conclusion


Security Properties





03-27-2014 16 / 24


Conclusion


Security Properties





03-27-2014 17 / 24


Conclusion


New Security Properties

Attacker AL CapabilitiesI ask for outputs (S,R)


I collect the leakage: λ bits of information onthe manipulated data at each invocation

Robustness with Leakage

If enough entropy is provided, AL cannotdistinguish (S,R) from a uniformly randomstring with a significant advantage.


03-27-2014 17 / 24


Conclusion









03-27-2014 17 / 24


Conclusion









03-27-2014 18 / 24


Conclusion


Limitations in Presence of Leakage: Generator G

I setup() outputs seed = (X ,X ′);


I (S,R) = next(S;X ′) = G([X ′S]m1 ).

→ Diffential Power Analysis of G


03-27-2014 19 / 24


Conclusion


New Generic Construction

I setup() outputs seed = (X ,X ′,X ′′);


I (S,R) = next(S;X ′,X ′′) = G([X ′S]m1 ,X′′).

New security property for PRG G

G is a leakage-resilient and secure PRG.


03-27-2014 20 / 24


Conclusion


Leakage-Resilient Instantiation

F

p0

F′

C

F

p1publ

icva

riabl

es

F′

C + 1

K0

T0

K0

T1

X ′′ X ′′

. . .

. . .

F

pn+`−2

F′

C + n + `− 2

F

pn+`−1

F′

C + n + `− 1

Kκ−1

Tn+`−2

Kκ−1

Tn+`−1

X ′′ X ′′

(K0|| . . . ||Kκ−1||C)← [X ′S]m1

m is (κ+ 1) times larger than in CCS’13


03-27-2014 21 / 24


Conclusion


Practical Analysis

CCS’13 (2−40 security):I internal state S: 489 bitsI threshold: γ∗ = 449I AES: 5 calls with 1 secret

key

Our Construction (2−40 security):I internal state S: 1408 bitsI threshold: γ∗ = 1370I AES: 12 calls with 6 secret

keys (2 calls per secret key)

I Efficiency: about five times slower than CCS 13I Security: higher security levels can be achieved with a tweaked

instantiation


03-27-2014 22 / 24


Conclusion

Outline



3 Conclusion


03-27-2014 23 / 24


Conclusion

Conclusion

Summary? leakage-resilient and efficient symmetric encryption? leakage-resilient and efficient PRNG with input

Further Work? more efficient leakage-resilient primitives? leakage-resilience evaluation of different modes of operation


03-27-2014 24 / 24


Conclusion

Thank you


Documents

Leakage-Resilient Primitives using Re-keying · 03-27-2014 1 / 24 Leakage-Resilient Encryption Scheme Leakage-Resilient PRNG with Input Conclusion Side-Channel Attacks Countermeasures