**Symbolic computation in block cipher with application to PRESENT**

*Changyong Peng and Chuangying zhu and Yuefei Zhu and 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 CHES07.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(=2*64+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(n*2^n),with total time complexity of obtaining these 129
ANFs O(129*144*2^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.

**Category / Keywords: **secret-key cryptography / PRESENT, symbolic computation, Gršobner Basis, side channel attack, block cipher

**Date: **received 16 Oct 2012

**Contact author: **pengchangyong at tom com

**Available format(s): **PDF | BibTeX Citation

**Version: **20121016:164123 (All versions of this report)

**Short URL: **ia.cr/2012/587

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]