Dissertation > Excellent graduate degree dissertation topics show

Research of Linear Hull for Block Cipher

Author: DaiZhenLi
Tutor: WangXiaoYun；WangMeiQin
School: Shandong University
Course: Information Security
Keywords: the block cipher linear cryptanalysis linear hull dependency of linear paths the rate of weak keys
CLC: TN918.1
Type: Master's thesis
Year: 2010
Downloads: 43
Quote: 0
Read: Download Dissertation

Abstract

The block cipher is a basic symmetric cryptosystem, which is widely used in other cryptosystems. Linear cryptanalysis and differential cryptanalysis are usually used to attack the block cipher. Furthermore, resisting against linear cryptanalysis and differential cryptanalysis is important security requirements of modern block ciphers.Linear cryptanalysis is a powerful method of cryptanalysis introduced by Matsui in 1993. It is a known plaintext attack in which the attacker studies the linear approximations of parity bits of the plaintext, ciphertext and the subkey. The probability of linear approximation needs to be away from 1/2. Based on this idea, many kinds of variant linear cryptanalysis appeared one after the other, such as single linear cryptanalysis. linear cryptanalysis using multiple approximations with the same key mask, multiple linear approxima-tions crypt analysis and linear cryptanalysis based on linear hull. etc.Linear cryptanalysis using multiple approximations was introduced by Kaliski and Robshaw in 1994. For a given success rate, this method reduced the data complexity by using multiple approximations. But their technique is limited to cases where all approximations have the same mask key bits. Unfortunately, this approach imposes a very strong restriction on the approx-imations. The concept of linear hull was first announced by Xyberg in 1994. and a linear hull stands for the collection of all linear relations that have the same fixed input mask and output mask, but involves different sets of round subkeys according to different linear paths. The linear hull effect accounts for a clustering of linear paths, with the consequence that the final bias may become significantly higher than that of any individual paths. In 2009, how-ever. Murphy proved that there is no linear hull effect in linear cryptanalysis. In the same year, K. Ohkuma pointed that 32%of PRESENT keys are weak for linear cryptanalysis, and the linear bias can be much larger than the linear path value by the multi-path effect. That is to say, attacks based on weak keys exist. However, this conclusion is given under the assumption of independent linear paths. And actually, all the linear paths are dependent. So the current model is inaccurate.Well, how to build a linear cryptanalysis model based on linear hull with weak keys?The main purpose of this paper is to build a linear cryptanalysis model based on linear hull when the linear paths are dependent. And we do the following:1. Introduce the method to compute the final bias of linear hull under the dependent linear paths.2. Give a new method to compute the rate of weak keys for the given linear hull as the linear paths are dependent.3. For PRESENT, compute the rate of weak keys for 7-13 rounds linear hull by our method. Then we compare them with the result computed by Ohkuma’s model, and compare the result of practical test for 7-round PRESENT.For a linear hull, the dependency of linear paths means their equivalent key bits are dependent. Here we classify all the independent equivalent key bits, and deduce the method to compute the bias of linear hull and the rate of weak keys. The main idea is described as follows,1. We find all the independent equivalent keys. which are named as in-dependent key bits. The rest equivalent keys are called dependent key bits.2. We study the distribution of the independent subkey bits on the ex-pressions of the dependent subkey bits. For a given master key, every independent subkey bit has two possible values:0 or 1, and|Γ1|= 2R.a. For a possible value ofΓ1, suppose that the number of the independent subkey bits whose values are 0 is s (s≤R), and the number of the independent subkey bits whose values are 1 is R - s. We classify the independent subkey bits into two groups according to their values. b. Consider the values of the dependent subkey bits. If there are odd number of subkey bits among the s subkey bits in the expressions of the dependent key bit kj (R<j≤L), we have kj= 0.c. In order to get the general formula, we classify the dependent subkey bits according to the number of independent subkey bits, whose values are 0, in the expressions of them.3. Compute the bias of the linear hull for every possible value ofΓ1 Then we can calculate the rate of weak keys according to the definition of weak keys.In order to reduce the computation complexity, we try to compute the rate of weak keys by random test for the space of equivalent key bits. We compute the rate of weak keys for 7-13 round PRESENT. For example, there are 72 linear paths for a 7-round linear hull, and the number of independent keys is 45. The rate of weak keys computed by Ohkuma’s model is 28.88%, but the rate computed by our method is 28.13%. Then the reduced rate is (?)≈2.60%.There are 24255 linear paths for a 13-round linear hull, and the number of independent keys is 153. The rate of weak keys computed by Ohkuma’s model is 29.60%, the rate computed by our method is 25.15%. So the reduced rate is (?)≈15.03%. All the results are summarized in Tab.5.2.At present, our model can only be used to attack block cipher with few rounds. When the number of rounds becomes large, our cryptanalysis tech-nology is limited by the computation complexity.But we can also get the important conclusion by analyzing the block cipher with few rounds. The experimental results show that the dependency of linear paths reduces the rate of weak keys for the given linear hull. Moreover, the rate of weak key will be lower if the equivalent keys depend more on others. Ohkuma attacks 24-round PRESENT by using linear cryptanalysis based on weak keys. But our conclusion shows the rate of weak keys for 24-round PRESENT is far less than 32%.

Related Dissertations

CLC: > Industrial Technology > Radio electronics, telecommunications technology > Communicate > Confidentiality of communications and communications security > Theory
© 2012 www.DissertationTopic.Net Mobile