Cryptanalysis Of Lightweight Block Cipher And Practical QKD With Decoy-State Method

Cryptography is the foundation of information security. On one hand, people take advantage of cryptography to ensure the security of the sensitive information. On the other hand, for different kinds of goals, people want to extract the secret information without the legal owner's authorization. Thus there are two basic research areas in cryptography, cryptographic design and cryptanalysis. The two research areas have a reciprocal impact, the progress in one sector promoting the progress in the other. With the progress of cryptanalysis, the leak of the cryptographic scheme has been found. Cryptographic scheme designer should propose new design technology. And new cryp-tographic design technology would be an inducement to improve the cryptanalyticsis technology.Our study includes two aspects, cryptanalysis and cryptographic design. In crypt-analysis, we analyze the security of two lightweight block ciphers. And we concentrate on practical quantum key distribution (QKD) on the decoy-state method in crypto-graphic design. The two aspects have been focused on by the researchers.1. Cryptanalysis of Lightweight Block CipherThe Lightweight block ciphers are also belong to block ciphers, particularly one with aggressive performance characteristics. When the internet of things was proposed in 1990, RFID tags and sencor network have been aggressively deployed in a variety of applications. People take more care of the security applications on them. Since the abil-ities of the devices in computing is restricted with limited resources, many lightweight block ciphers are designed. In order to pursue high performance, the security of the lightweight block ciphers must be affected. Our research goal is to analyze the security of the lightweight block ciphers.The block cipher use the same key for encryption and decryption. Essentially, the block cipher is a permutation with key, which translate fixed length plaintext into fixed length ciphertext. There are two main structures to construct block ciphers. One is Feistel Network. The early block cipher, Data Encryption Standard (DES), is based on the Feistel Network. DES has endured various attacks for over 20 years, even though its round function is very simple. DES served as a sort of baseline for cipher design through the 80s and 90s. Many of the techniques used in 20th center ciphers came from DES and many of the design principles came from analysis of DES. Since Feistel construction operates on half of the block length in each iteration, the size of code or intermediate required to implement it is nearly halved. It is suitable for the extremely constrained environments. Another structure is Substitution-Permutation Network (SPN). Advanced Encryption Standard (AES) is based on SPN with block size of 128 bits and key size of 128/192/256 bits. SPN can be proved secure for differential cryptanalysis and linear cryptanalysis.The design of many lightweight block ciphers is influenced by DES and AES, such as PRESENT and MIBS.A. Bogdanov etc. presented the lightweight block cipher PRESENT in CHES 2007, which is a hardware-optimized block cipher. Its hardware implement efficiency is very high. PRESENT is an example of a SPN and consists of 31 rounds. The block length is 64 bits and two key lengths of 80 and 128 bits are supported. MIBS is a new block cipher which is presented by M. Izadi etc. in CANS 2009. It is designed for hardware efficient security primitive for resource-constrained devices such as low-cost RFID tags. MIBS uses a Feistel Network and consists of 32 rounds, which round function is also SPN. It's block size is 64 bits and the key size can be 64 or 80 bits.Since the lightweight block cipher is designed to be used in extremely constrained environments, We should strike the right balance between security and performance. Obviously, the high performance of a algorithm will impact the security of it. Under the instruction of my supervisor Pro. Tao Zhan and Pro. Xiaoyun Wang, we analyze the security of the lightweight block cipher PRESENT and MBS.Our main contributions are as follows.●Side Channel Cube Attack on PRESENTWe combine side channel attack and cube attack to analyze PRESENT. By analyzing the relationship between the intermediate state in the first few rounds with the plaintext and key bits for PRESENT by cube test, we found some important nonrandomness which can be utilized by the side channel cube attack. We present how to recover 80-bit key of PRESENT even if only a bit in the special position of the third round is leaked. Especially, if the leaked bit is bit 1, bit 2 or bit 3 of the output bits in the third round, we can also recover 80-bit key with lower computing complexity compared to other leaked bits, and our attack requires 215 chosen plaintexts and 232 31-round PRESENT encryptions.For any cipher, each output bit can be regard as a polynomial of plaintext and key bits. Generally this polynomial is too complex to exploit key informa-tion. The cube attack exploits low-degree equations from the low-gegree multi-variate polynomial. We find the maxterm and corresponding maxterm equation based on PRESENT property, so we can identify the chosen message in the on-line phase of cube attack. The original cube attack utilizes random walk method to identify the maxterm.We present the important property of PRESENT as follows, which can be used to find the maxterm.-For Present, each output bit of the third round is related to the 64-bit plain-text variables and 80-bit key variables.-After the third round of PRESENT, the plaintext variables do not cancel each other.Since there is uncancel property in the first three rounds, the reduce poly-nomial can be utilized to deduce the maxterm and the corresponding maxterm equation. In other words, the output variables can be represented as a polyno-mial of the input variables and the subkey variables in iterative function. In order to apply the cube attack, we focus on the terms which contain only a key vari-able and all plaintext variables. For each round, we reserve these terms involving a key variable and the terms only involving public variables. Then in the next round we calculate the partial terms in the polynomial of the state bit which is related to the reserved terms only. Then we can control the size of the reduced polynomial. The maxterms can be deduced from the reduced polynomial.●Differential Cryptanalysis of Reduce-Round MIBSM. Izadi believed that MIBS-64 can supply adequate security for applica-tions, such as low-cost RFID tags. And it need low hardware resource. Accord-ing to the input and output difference of the S-box, we present the best 4 rounds differential characteristic with probability 2-12 which is better than the one, which M. Izadi present, with probability 2-15.Four 12-round differential characteristics have been found. We recover the key of reduce-round MIBS with them. The total 64-bit key can be recovered with 261.6 chosen message pairs and 216 byte counters. The success probability is 0.99.2. Practical QKD with Decoy-state MethodWhile the classical cryptography is widely used, the research of the quantum cryp-tography has become a hot subject these days. The security of QKD is guaranteed by principles of quantum mechanics. The QKD is proved unconditional security on the-ory. The QKD protocol don't need quantum computer or quantum memory but only need to produce, transmit and measure the quantum state to complete the task. But now the experimental conditions can not satisfy the theory requirements, the security of the QKD is seriously affected. Our goal is to design practical and security QKD protocol under exiting technologies.The first QKD protocol, named BB84, was proposed by C. Bennett and G. Brassard in 1984. Alice and Bob use different quantum states to carry the bit value 0 and 1. Alice randomly chooses a polarization and sends the phone to Bob one by one by quantum channel. Bob measures it in different type of basis randomly. Later, Bob announces his basis for each photon, and they discard those bits with basis mismatch. Then they randomly choose some remaining bits and publicly announce them for error test. They discard these test bits. If the error rate is too large, they abort the protocol; otherwise they continue to distill the final key with appropriate error correction and privacy amplification for the remaining bits.D. Mayers proved the secruity of a protocol based on BB84 in 1996, and so are applicable near-practical settings. However the proof is quite complex. In 1999, P. Shor and J. Preskill present a simpler proof by relating the security of BB84 to entanglement purification protocols. The final key is unconditionally secure, if it uses for one-time-pad.Although BB84 protocol have been proven to be unconditional security, this does not guarantee the security of QKD in practice, due to various types of imperfections in the practical setup. In practice, the source is often imperfect, which may produce multi-photon. The first decoy-state method is presented by Hwang[14], but not practical. Wang proposed the practical decoy-state method, which is useful in practice. Utilizing the decoy-state method can distill final key without perfect source.Under the instruction of my co-superviser Xiangbin Wang, who propose the decoy-state method with source error and statistic fluctuation, we propose a QKD pro-tocol based on decoy-state method with source error and statistic fluctuation. This result is the first QKD theory considered the source error and statistic fluctuation so far as we know.Our main contributions are presented below.●Decoy-state quantum key distribution with both source errors and statistical fluc-tuationsQuantum key distribution has now been extensively studied both theoreti-cally and experimentally. QKD have been proven unconditionally secure, var-ious types of imperfections in a practical setup make it unsecure in practical. Especially, QKD require perfect single-photon source. However, one uses an imperfect single-photon source with a lossy channel in practice, the security is undermined by the photon-number-splitting attack.Fortunately, the so-called ILM-GLLP proof has shown that if we know the upper bound of the fraction of multi-photon counts (or equivalently, the lower bound of single-photon counts) among all raw bits, we still have a way to distill the secure final key. Verifying such a bound is strongly nontrivial. The practical decoy-state method proposed by Xiangbin Wang is to find such tight bounds. Then the function below can be utilized to calculate the final key rate. where t1, t are the quantum bit error rate (QBER) for single-photon counts of the signal source and the QBER for all counts of the signal pulses from the signal source.Δ'1 is the lower bound of the fraction of counts due to single-photon pulses from the signal source.We present the formula to calculateΔ'1. This is the key formula to obtain the QKD final key rate. In practice, source error and classical statistical fluctu-ations can affect the security of the QKD. Very recently, a general theory for decoy-state QKD with source errors was presented. Our earlier work assumes zero error for vacuum source, while we assume errors in all sources. The results presented here only need the bound values of a few parameters in the states of different sources. In practice, one of the major causes of source error is intensity fluctuation. Therefore we often use the term intensity fluctuation for source er-rors. But our result is not limited to the intensity fluctuation only. In particular, in deriving the fraction of single-photon counts we do not use any unproven as-sumption and we do not need to worry about the internal fluctuation of Alice's device, since our method only needs the bound values of a few parameters in the source state. We do not need to presume any specific distribution for our states. In our study in this work, classical statistical fluctuation is considered by estimating the observed values from the asymptotic values with a fixed standard deviation. We shall start with a protocol with one-way quantum communication only. But as we point out at the end of this paper, our method obviously also applies to a Plug-and-Play protocol.