Improving impossible differential cryptanalysis

Please download to get full document.

View again

of 52
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Calendars

Published:

Views: 0 | Pages: 52

Extension: PDF | Download: 0

Share
Related documents
Description
Improving impossible differential cryptanalysis Christina Boura joint work with Virginie Lallemand, María Naya-Plasencia and Valentin Suder Séminaire CCA, June 12, / 39 Block ciphers E : {0,1} n
Transcript
Improving impossible differential cryptanalysis Christina Boura joint work with Virginie Lallemand, María Naya-Plasencia and Valentin Suder Séminaire CCA, June 12, / 39 Block ciphers E : {0,1} n {0,1} k {0,1} n (m,k) E(m,K) = c K m E c 2 / 39 Lightweight block ciphers Block ciphers designed for constrained environnements (RFID tags, sensor networks,...) A high number of proposals in the last few years (PRESENT, CLEFIA, LED, LBlock, Piccolo, TWINE, KLINE, Zorro, PRINTCipher, PRINCE, SIMON, SPECK,...) New ISO/IEC standards: PRESENT, CLEFIA. Need to identify the robust algorithms for future use. 3 / 39 Cryptanalysis of block ciphers In symmetric key cryptography security proofs are partial and insuffient. The only way to conclude that a block cipher is strong is to evaluate its security against different kind of attacks. Generic attack: exhaustive search of the key in O(2 k ). A block cipher is considered unbroken as far as no attack faster than exhaustive search exists. There is a multitude of attacks against block ciphers : differential, linear, algebraic, higher-order differential, integral, impossible differential,... 4 / 39 Differential cryptanalysis Introduced by Biham and Shamir in 90. Given an input difference between two plaintexts, some output differences occur more often than others. x D X x+d X E k E k D Y E k (x) E k (x+d X ) A differential is a pair (D X,D Y ). 5 / 39 Impossible differential cryptanalysis Introduced by Knudsen and Biham et al. in 99. Exploit differentials of probability 0. Why care about impossible differential attacks? Very powerful attacks (lead to the best cryptanalysis against many ciphers, e.g. some famous Feistel constructions) Were for a long time the most successful attacks against the AES. Not fully understood and exploited in an non-optimal way due to their high technicality. 6 / 39 First step: Find an impossible differential Well understood and easy part of the attack. Algorithms for finding impossible differentials on a given cipher exist. Find the impossible differential using the Miss-in-the-middle technique. p = 1 p = 0 p = 1 7 / 39 Miss in the Middle for AES AK SB SR MC AK AK AK Contradiction SB 1 SR 1 MC 1 AK SB 1 SR 1 MC 1 AK SB 1 SR 1 8 / 39 Extend the impossible differential Example : 6-round attack on AES Extend the impossible differential one round to both directions. Impossible Differential 1 round 4 rounds 1 round 9 / 39 Second step: Extend the impossible differential K0 Round 1 D in SB SR MC p = 2 16 D X 4-round Impossible Differential Round 6 D Y MC 1 p = 2 24 SB 1 SR 1 D out K6 Collect pairs verifying (D in,d out ). Guess 4 bytes of K 1 and 4 bytes of K 6. If for a value of K 1 and K 6 we get at the same time D X and D Y, then these (partial) keys can be discarded. Exhaustive search for the remaining candidate keys. 10 / 39 Our contributions The key recovery phase of impossible differential attacks is a very technical and not fully understood procedure. Errors are common. Many of the published attacks are sub-optimal. Our goal : Formalize the key recovery procedure. Provide complete complexity formulas. Introduce new techniques for improving the time or data complexity of such attacks. 11 / 39 The results presented next appear in the following two papers: Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and Simon, Christina Boura, María Naya-Plasencia and Valentin Suder. Presented at ASIACRYPT Improving Impossible Differential Cryptanalysis, Christina Boura, Virginie Lallemand, María Naya-Plasencia and Valentin Suder, submitted. 12 / 39 Notation D in Round 1 Round r in D X Round r in +1 Round r in +r D Y Round r in +r +1 Round r in +r +r out 2 cin 0 2 cout V : size in bits of a difference D V. c in,c out : number of bit conditions to be verified. k in,k out : number of involved subkey bits. k in k out : key entropy D out 13 / 39 Example K0 Round 1 D in SB SR MC p = 2 16 D X 4-round Impossible Differential Round 6 D Y MC 1 p = 2 24 SB 1 SR 1 D out K6 in = 32, out = 32 c in = 16,c out = 24 k in = 32,k out = / 39 The early abort technique Introduced by Lu et al. in 2008 for impossible differential cryptanalysis. K 0 D in S S S S P D X 15 / 39 The early abort technique D in K 0 S S S S P D X Classical approach: Guess all the required subkey bits, encrypt a pair and verify if the difference D X occurs. 15 / 39 The early abort technique D in K 0 S S S S D S P D X Early abort: Guess the subkey bits word by word and check if the partial difference occurs. If the partial difference doesn t occur, discard the pair. 15 / 39 Complexity Formulas Outline 1 Complexity Formulas 2 New techniques 3 Applications 16 / 39 Complexity Formulas How many pairs does an attack require? By taking N pairs satisfying (D in,d out ), the probability of not discarding a candidate key is P = (1 2 (c in+c out) ) N How many pairs N are needed for the attack? First approach: (1 2 (c in+c out) ) N 2 k in k out Better approach: (1 2 (c in+c out) ) N 1 2 Take N min = 2 c in+c out. Memory complexity : N 17 / 39 Complexity Formulas Finding N solutions for a given truncated differential Problem: Find N pairs verifying D in and D out For N = 1: Limited birthday technique [Gilbert, Peyrin FSE 2010] C 1 = max{ min { 2 n },2 n ( in+ out) }, { in, out} where n is the state size. 18 / 39 Complexity Formulas Limited Birthday Technique [Gilbert, Peyrin FSE 2010] n in E k out Find a pair of inputs (m,m ) such that m m D in and E k (m) E k (m ) D out 19 / 39 Complexity Formulas Limited Birthday Technique [Gilbert, Peyrin FSE 2010] n E k Extreme case: out = 0 and input unrestricted. Collision after 2 n/2 computations. 19 / 39 Complexity Formulas Limited Birthday Technique [Gilbert, Peyrin FSE 2010] n in E k out When the input space is restricted, the number of pairs that can be constructed is reduced. Consider the quantity (2 in + out ). If (2 in n out ) apply birthday paradox to collide on n out bits. Else, restart the birthday paradox 2 n 2 in out times. 19 / 39 Complexity Formulas Limited Birthday Technique [Gilbert, Peyrin FSE 2010] n in E k out { 2 n out if 2 C 1 = in n out, 2 n ( out+ in) otherwise. 19 / 39 Complexity Formulas Cost C N for finding N pairs verifying (D in,d out ) By considering C N = N C 1 we might be wasting some structures. Determine the number of inputs 2 x we need in order to construct N pairs. 1 N 2 in2 in 1 2 n out (D in is large enough). Thus 2 x 2 in and therefore N = 22x 1 2 n out. We need 2 x = N2 n out+1 inputs. 2 N 2 in2 in 1 2 n out (D in is not large enough). We need to add 2 y structures of size in such that N = 2 y 2 in2 in 1 2 n out. Therefore we need 2 x = 2 y+ in = N2 n in out+1 inputs. 20 / 39 Complexity Formulas Cost for finding N pairs { { C N = max min } } N2 n +1,N2 n in out+1. { in, out} Data complexity: C N Obviously, C N 2 n 21 / 39 Complexity Formulas Time complexity T comp = C N + Encrypt data. 22 / 39 Complexity Formulas Time complexity T comp = C N + ( N +2 k in k out N 2 c in out) C +c E Encrypt data. Early abort technique Check each key candidate step by step. Decrease the number of pairs in the list. 22 / 39 Complexity Formulas Time complexity T comp = ( C N + ( N +2 k in k out 2 c in out) C +c E +2 K P ) C E N Encrypt data. Early abort technique Check each key candidate step by step. Decrease the number of pairs in the list. The last term corresponds to 2 K P = 2 K k in k out P2 k in k out. Test by exhaustive search the remaining keys. 22 / 39 Complexity Formulas The role of the key schedule During the key-recovery phase, key bits of different subkeys are guessed. How to recover the master key from these guessed bits? This depends on the nature of the key-schedule. If the key-schedule is (almost) linear, directly translate the k in and k out guessed bits in the same number of bits of the master key. 23 / 39 Complexity Formulas Complex key schedules K 0 K 6 k in = 64 k out = 32 If the key-schedule is complex, it is not possible to directly translate the information guessed on the subkeys into the same amount of information on the master key. 24 / 39 Complexity Formulas What do we do then? K 0 K 6 k in = 64 k out = / 39 Complexity Formulas What do we do then? Key schedule K 0 K 6 k in = 64 k out = 32 Complete the missing bits to some of the subkeys. Compute through the key schedule. Verify if the result matches. 25 / 39 Complexity Formulas How is the time complexity affected? A new term has to be added to the time complexity formula. min(2 K k in,2 K kout ) P 2 k in+k out C KS, where C KS is the key schedule cost. 26 / 39 Complexity Formulas How is the time complexity affected? A new term has to be added to the time complexity formula. where C KS is the key schedule cost. min(2 K+k in,2 K+kout ) P C KS, In previous works, it was wrongly supposed that one guessed word of a subkey could directly be seen as one guessed word of the master key. 26 / 39 New techniques Outline 1 Complexity Formulas 2 New techniques 3 Applications 27 / 39 New techniques The state-test technique Goal: Eliminate some candidate keys without considering all the possibilities for the involved key bits. How? If a word of the state of size s depends on more than s key bits, guess this word instead. 28 / 39 New techniques Example on CLEFIA-128 ISO/IEC standard in lightweight crypto. Developed by SONY in Block size: 4 32 = 128 bits Key size: 128 bits Number of rounds: 18 P0 i 1 P1 i 1 P2 i 1 P3 i 1 RK 2i 2 RK 2i 1 F 0 F 1 P i 0 P i 1 P i 2 P i 3 29 / 39 New techniques The state-test technique in practice D in RK 0 RK 1 F 0 F 1 RK 2 RK 3 F 0 F 1 D X 30 / 39 New techniques The state-test technique in practice D in RK 0 RK 1 F 0 F 1 RK 2 RK 3 B F 0 F 1 D X 30 / 39 New techniques The state-test technique in practice D in cste RK0 RK1 F 0 F 1 RK2 RK3 B F 0 F 1 D X B = S 0 ( ) 30 / 39 New techniques The state-test technique in practice D in cste RK0 RK1 F 0 F 1 RK2 RK3 B F 0 F 1 D X B = S 0 ( ) with B = B k in k out = 122 bits k in k out = }{{} B bits 30 / 39 New techniques Remark regarding the state-test technique The state-test technique applies to both Feistel and SPN constructions. However, it seems to apply better to Feistel ciphers. In SPN ciphers the gain in the time complexity generally leads to an equivalent loss in data complexity, because a part of the active part of the plaintexts has to be fixed. We have implemented this technique on a toy-cipher (mini-clefia) and verified its efficiency in practice. 31 / 39 New techniques Multiple Impossible Differentials Formalize the idea of [Tsunoo et al. 08]. CLEFIA has 9-round impossible differentials ((0, 0, 0, A) (0, 0, 0, B)) and ((0,A,0,0) (0,B,0,0)) when A and B verify: A B (0,0,0,α) (0,0,β,0) (0,β,0,0) (β,0,0,0) (0,0,α,0) (0,0,0,β) (0,β,0,0) (β,0,0,0) (0,α,0,0) (0,0,0,β) (0,0,β,0) (β,0,0,0) (α,0,0,0) (0,0,0,β) (0,0,β,0) (0,β,0,0) C N = C N = log 2 (24) 32 / 39 New techniques Multiple differentials in impossible differential cryptanalysis More choices for the input/output patterns of a pair. Less data is needed to construct the pairs for the attack reduction in the data complexity Multiple inputs D in D X D Y one impossible differential Multiple outputs D out The log 2 of the data complexity is reduced by # input multiples + # output multiples. 33 / 39 New techniques Combine multiple impossible diff. with multiple diff. Use multiple differentials and multiple impossible differentials together to further reduce the amount of data. Din DX DY Dout / 39 Applications Outline 1 Complexity Formulas 2 New techniques 3 Applications 35 / 39 Applications Applications Feistel ciphers Best cryptanalysis on CLEFIA-128, Camellia and LBlock. Best impossible differential attacks on the SIMON family. SPN ciphers Best impossible differential attacks on AES-128, CRYPTON-128 and ARIA-128. Each application illustrates a different combination of the new techniques. 36 / 39 Applications Results on Feistel ciphers Algorithm Rounds Data Time Memory Tech. Ref. (CP) (Blocks) CLEFIA ID [MDS 11] ID Camellia ID [LLGWLCL 12] ID Camellia ID [LLGWLCL 12] ID Camellia ID [LLGWLCL 12] ID Camellia ID [LLGWLCL 12] ID LBlock ID [KDH 12] ZC [BM 14] ID 37 / 39 Applications Results on SPN ciphers Algorithm Rounds Data Time Memory Tech. Ref. (CP) (Blocks) ID [MDRM 10] AES MITM [DFJ 13] MITM [DFJ 13] ID ID Tr. Diff. [KHLSY 03] CRYPTON ID [MSD 10] ID Tr. Diff. [KHLSY 03] ID [LSZL 08] ID [WZD 07] ARIA ID [LS 08] ID LC [LGLLL 38 / 11] 39 Applications Conclusions The proposed techniques are general, however the level of applicability of each method is different on SPN and Feistel ciphers. Important to verify the new techniques by implementing them. Apply the same approach to other families of attacks, e.g. zero-correlation attacks. 39 / 39 Applications Conclusions The proposed techniques are general, however the level of applicability of each method is different on SPN and Feistel ciphers. Important to verify the new techniques by implementing them. Apply the same approach to other families of attacks, e.g. zero-correlation attacks. Thanks for your attention! 39 / 39
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x