International Association
for Cryptologic Research

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(=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.