Welcome to the resource topic for 2012/587
Title:
Symbolic computation in block cipher with application to PRESENT
Authors: Changyong Peng, Chuangying zhu, Yuefei Zhu, Fei Kang
Abstract:In this paper,we give an example of how symbolic computation are used to analyze the block cipher PRESENT,an ultra-lightweight block cipher proposed by Bogdanov et al. at CHES’07.The block size is 64 bits and the key size can be 80 bit or 128 bit.Using Mathematica 7.0,this paper obtains the unexpanded polynomial expressions of the output of round 1-6 of PRESENT-80(80- bit key variant).The time complexity of getting these expressions is 4 minutes on a PC with a 2.6GHz CPU and 8G RAM.Then we expand the expressions of the output of round 1-2 and the LSB(least significant bit) of the output of round 3 and obtain the ANFs(Algebraic Normal Form) of these 129(=264+1) expressions. The time complexity of getting these ANFs is 22 minutes.It it known that the time complexity of the classical method of computing the ANF of an n-ary Boolean function from its truth table is O(n2^n),with total time complexity of obtaining these 129 ANFs O(1291442^144) = O(2^158)(each of the 129 ANFs can be viewed as a 144-ary Boolean function,where 144=64+80,the sum of the block size and the key size).As an application,we give a side channel attack on PRESENT-80 under the single bit leakage model proposed by Dinur and Shamir.If the LSB bit of the output of the 3rd round can be obtained without error,then with 200 known plaintexts,we can set up an equation system in terms of the master key bits and can recover 43 bits key by the Gr¨obner Basis method.Compared with the previous side channel attack on PRESENT,such as Yang et al. in CANS 2009,Abdul-Latip et al. in ASIACCS 2011 and Zhao et al. in 2011,each of which needs at least 2^13 chosen plaintexts,the data complexity of our attack is the best.
ePrint: https://eprint.iacr.org/2012/587
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .