r""" PRESENT polynomial system generator and experiment code. This file is meant to be used with the Sage mathematics software available at: \url{http://www.sagemath.org}. It implements the cipher PRESENT and a polynomial system generator for this cipher. PRESENT is an ultra-lightweight block cipher proposed at CHES 2007 by A. Bogdanov, L.R. Knudsen , G. Leander , C. Paar, A. Poschmann, M.J.B. Robshaw, Y. Seurin, and C. Vikkelsoe which is available at: \url{http://www.crypto.rub.de/imperia/md/content/texte/publications/conferences/present_ches2007.pdf}. Also this file implements the attacks 'A', 'B' and 'C' described in the paper 'Algebraic Techniques in Differential Cryptanalysis' by Martin Albrecht and Carlos Cid. It is available at: \url{http://www.informatik.uni-bremen.de/~malb/papers/algebraic_techniques_in_differential_cryptanalysis.pdf}. AUTHOR: - Martin Albrecht (2008-04-17): release to public EXAMPLE: First load this file sage: attach "adc-present.py" Now, we construct PRESENT-80-4 sage: p = PRESENT(Nr=4) Run Attack-C with a one round differential sage: present_dc(p, r=1, timeout=15) 0 8.748 11.052 1 9.351 10.736 2 8.051 9.421 3 8.572 9.972 4 8.202 9.643 5 9.606 11.025 6 8.273 9.726 7 8.182 9.630 8 7.819 9.297 9 9.336 10.720 10 7.988 9.415 11 8.874 10.248 12 7.913 9.340 Interrupting Sage... candidate found (([K0054 + K0055, K0053 + K0055 + 1], [0, 1, 0, 0]), ([K0006 + K0007 + 1, K0005 + K0007 + 1], [0, 0, 0, 1])) The left-hand side contains the output of the algorithm, while the right-hand side contains the correct key bits to check the result. NOTE: Tested with Sage 2.11 and 3.0.alpha5 """ ############################################################################## # # Algebraic Techniques in Differential Cryptanalysis # # Copyright (C) 2008 Martin Albrecht # # Distributed under the terms of the GNU General Public License (GPL) # # This code is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU # General Public License for more details. # # The full text of the GPL is available at: # # http://www.gnu.org/licenses/ ############################################################################## from sage.rings.polynomial.multi_polynomial_ring import MPolynomialRing from sage.crypto.mq.mpolynomialsystemgenerator import MPolynomialSystemGenerator class PRESENT(MPolynomialSystemGenerator): def __init__(self, Ks=80, Nr=1, B=16, **kwds): """ PRESENT is an ultra-lightweight block cipher proposed at CHES 2007 by A. Bogdanov, L.R. Knudsen , G. Leander , C. Paar, A. Poschmann, M.J.B. Robshaw, Y. Seurin, and C. Vikkelsoe INPUT: B -- blocksize divided by 4 (default: 16) Nr -- number of rounds (default: 1) Ks -- keysize in (80,128) (default: 80) postfix -- (default: '') order -- term ordering for the polynomial ring (default: 'degrevlex') polybori -- use PolyBoRi as underlying implementation (default: True) EXAMPLES: sage: p = PRESENT(80,31) sage: P = [0 for _ in xrange(p.Bs)] sage: K = [0 for _ in xrange(p.Ks)] sage: C = p(P,K) sage: bitstringtohexstring(C) # official test vector '5579c138 7b228445' sage: P = [0 for _ in xrange(p.Bs)] sage: K = [1 for _ in xrange(p.Ks)] sage: C = p(P,K) sage: bitstringtohexstring(C) # official test vector 'e72c46c0 f5945049' sage: P = [1 for _ in xrange(p.Bs)] sage: K = [0 for _ in xrange(p.Ks)] sage: C = p(P,K) sage: bitstringtohexstring(C) # official test vector 'a112ffc7 2f68417b' sage: P = [1 for _ in xrange(p.Bs)] sage: K = [1 for _ in xrange(p.Ks)] sage: C = p(P,K) sage: bitstringtohexstring(C) # official test vector '3333dcd3 213210d2' REFERENCES: http://www.crypto.rub.de/imperia/md/content/texte/publications/conferences/present_ches2007.pdf """ if Ks not in (80,128): raise TypeError, "Number of key bits must be either 80 or 128." if Nr < 1: raise TypeError, "Number of rounds must be >= 1." self.Ks = Ks self.Nr = Nr self.B = B self.Bs = B*4 self._postfix = kwds.get("postfix","") self._order = kwds.get("order","degrevlex") self._polybori = kwds.get("polybori",True) self.s = 4 self._base = GF(2) self._sbox = mq.SBox([12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2], \ big_endian=True) def new_generator(self, **kwds): """ Return a new instance of the PRESENT polynomial system generator. INPUT: see constructor """ Nr = kwds.get("Nr",self.Nr) B = kwds.get("B",self.B) Ks = kwds.get("Ks",self.Ks) postfix = kwds.get("postfix",self._postfix) order = kwds.get("order", self._order) polybori = kwds.get("polybori",self._polybori) return PRESENT(Ks=Ks, Nr=Nr, B=B, postfix=postfix, order=order, polybori=polybori) def varformatstr(self, name): r""" Return format string for variable named \code{name}. """ l = str(max([len(str(self.Nr)), len(str(self.Bs -1))])) if not name.startswith("K"): name += self._postfix return name + "%0" + l + "d" + "%0" + l + "d" def varstrs(self, name, r): r""" Return variable string for variable named \code{name} and round \code{r}. """ s = self.varformatstr(name) if name == "K": if r == 0: return [s%(r,i) for i in range(self.Ks) ] if self.Ks == 80: return [s%(r,i) for i in range(self.s) ] else: return [s%(r,i) for i in range(2*self.s) ] else: return [s%(r,i) for i in range(self.Bs) ] def vars(self, name, r): r""" Return variables for variable named \code{name} and round \code{r}. """ gd = self.R.gens_dict() return [gd[e] for e in self.varstrs(name,r)] def block_order(self, n = 1): r""" Return a block oder for the ring of this PRESENT equation system generator. INPUT: n -- number of plaintext-ciphertext pairs """ if self.Ks == 80: ks = 4 else: ks = 8 T = TermOrder("degrevlex", ks + 2*n*self.Bs) for nr in range(2,self.Nr+1): T += TermOrder("degrevlex", ks + 2*n*self.Bs) T += TermOrder("degrevlex", self.Ks) return T def __repr__(self): return "PRESENT-%d-%d"%(self.Ks,self.Nr) def ring(self, order=None, n=1): """ Return a new ring for this PRESENT equation system generator. INPUT: n -- number of plaintext ciphertext pairs (default: 1) """ if order is None: order = self._order if order == "block": order = self.block_order(n) Nr = self.Nr Bs = self.Bs Ks = self.Ks s = self.s if Ks == 80: ks = s elif Ks == 128: ks = 2*s if n==1: var_names = [] for nr in reversed(range(1,self.Nr+1)): var_names += [self.varformatstr("K")%(nr,j) for j in xrange(ks)] var_names += [self.varformatstr("Y")%(nr,j) for j in xrange(Bs)] var_names += [self.varformatstr("X")%(nr,j) for j in xrange(Bs)] var_names += [self.varformatstr("K")%(0,j) for j in xrange(Ks)] elif n > 1: var_names = [] for nr in reversed(range(1,self.Nr+1)): var_names += [self.varformatstr("K")%(nr,j) for j in xrange(ks)] for sample in xrange(n): var_names += [self.varformatstr("Y%d"%sample)%(nr,j) for j in xrange(Bs)] var_names += [self.varformatstr("X%d"%sample)%(nr,j) for j in xrange(Bs)] var_names += [self.varformatstr("K")%(0,j) for j in xrange(Ks)] else: raise TypeError, "parameter n must be >= 1" if self._polybori: R = BooleanPolynomialRing(len(var_names), var_names, order= order) else: R = MPolynomialRing(self._base, len(var_names), var_names, order=order) if n == 1: self.R = R return R def random_element(self, Bs=None): """ Return a random list of elements in $GF(2)$ of length Bs INPUT: Bs -- length (default: self.Bs) """ if Bs is None: return [self._base.random_element() for _ in range(self.Bs)] else: return [self._base.random_element() for _ in range(Bs)] def __getattr__(self, attr): """ Some syntactical sugar. EXAMPLE: sage: p = PRESENT(Nr=1) sage: p.K0 # variables K0 sage: p.R # ring """ import re if attr == "R": self.R = self.ring() return self.R s = re.match("([XYK])([0-9]+)",attr) if s: v,n = s.groups() return self.vars(v,int(n)) raise AttributeError, "'%s' object has no attribute '%s'"%(type(self),attr) def polynomial_system(self, P=None, K=None, **kwds): """ Return a polynomial system for self and P,K INPUT: P -- plaintext (default: random) K -- key (default: random) **kwds -- ignored OUTPUT: MPolynomialSystem, dictionary of solutions """ if not P: P = self.random_element() if not K: K = self.random_element(self.Ks) Kval = list(K) Kvar = list(self.K0) C = self(P, Kval) R = self.R Zi = P rounds = [self.field_polynomials(self.vars("K",0))] for i in range(1,self.Nr+1): Xi = self.vars("X",i) Yi = self.vars("Y",i) # key schedule Ki, Kvar, key = self.key_schedule_polynomials(Kvar,i) key += self.field_polynomials(self.vars("K",i)) # key addition add = self.key_addition_polynomials(Xi, Zi, Ki) add += self.field_polynomials(Xi) # sbox sbox = self.sbox_polynomials(Xi, Yi) sbox += self.field_polynomials(Yi) # diffusion layer Zi = self.pLayer(Yi) rounds.append(mq.MPolynomialRoundSystem(R, sbox + add + key)) # key addition equations Ki,Kvar, key = self.key_schedule_polynomials(Kvar, self.Nr+1) add = self.key_addition_polynomials(C, Zi, Ki) rounds.append(mq.MPolynomialRoundSystem(R, add + key)) solution = dict(zip(self.K0,Kval)) F = mq.MPolynomialSystem(R, rounds) return F, solution def sbox_polynomials(self, X, Y): """ Return a list of polynomials describing the sbox/substitution layer for the input variables X and the output variables Y. INPUT: X -- list of input variables of length self.Bs Y -- list of output variables of length self.Bs """ s = self.s return sum([ self.single_sbox_polynomials(X[j:j+s], Y[j:j+s]) for j in range(0,self.Bs,s)],[]) def single_sbox_polynomials(self,x,y, poly_choice=2): """ Return a list of polynomials describing one sbox for the input variables x and output variables y. INPUT: x -- list of length 4 with add-able elements y -- list of length 4 with add-able elements poly_choice -- in (1,2,3), choice which representation to use (default: 2) """ x0,x1,x2,x3 = x y0,y1,y2,y3 = y if poly_choice == 0: l = [ y3 + x0 + x1*x2 + x1 + x3, y1 + y2*x1 + y2*x2 + y3*x2 + y3 + x0*x3 + x2 + x3 + 1, y1*x0 + y2*x0 + y2*x1 + y2 + y3*x0 + y3 + x1 + x2 + x3, y0 + y1 + y3*x2 + y3*x3 + y3 + x0 + x1*x3 + x2 + x3, y0 + y1*x0 + y2*y3 + y3*x2 + y3 + x0 + x1 + x2 + 1, y0*x2 + y0 + y1*y3 + y2*x1 + y3*x3 + y3 + x1 + x2 + 1, y0*x1 + y0 + y2*x2 + y3*x0 + y3*x3 + y3 + x0 + x3 + 1, y0*x1 + y0 + y1*x0 + y1*x1 + y2 + y3*x0 + y3*x1 + x0 + x3 + 1, y0*x1 + y0 + y1*x0 + y1*x1 + y1*x3 + y1 + y2*x0 + y2*x2 + y3 + x1 + x3, y0*x0 + y1*x0 + y1*x1 + y1 + y2*x0 + y2*x2 + y3*x0 + y3*x2 + x0 + x1 + x2 + 1, y0*x0 + y0 + y1 + y2*x0 + y2*x3 + y3*x0 + y3 + x0 + x2, y0*x0 + y0 + y1*x1 + y1*x2 + y1 + y2*x0 + x0 + x1 + x3, y0*x0 + y0*x3 + y1 + y2*x0 + y3*x0 + x0 + x1 + 1, y0*x0 + y0*x2 + y0 + y1*x0 + y1 + y3*x0 + x0 + x1 + x2 + x3, y0*y3 + y2*y3 + y2 + y3*x3 + y3 + x0*x1 + x0 + x2, y0*y3 + y1 + y2*y3 + y2*x3 + y3*x3 + y3 + x0 + x1 + 1, y0*y3 + y1*x3 + y2*x1 + y2*x2 + y2 + x0 + x1 + x3, y0*y3 + y1*x1 + y1 + y2*x2 + y3*x3 + y3 + x1 + x2 + 1, y0*y3 + y1*y3 + y1 + y2*x0 + y2*x1 + y3*x2 + x3 + 1, y0*y3 + y1*y2 + y2 + y3*x3 + x0 + x1 + x3, y0*y3 + y0 + y2*y3 + y3*x3 + x0*x2 + x1 + x2 + 1, y0*y3 + y0 + y2*y3 + y3*x2 + y3*x3 + x1 + x2*x3 + x2 + 1, y0*y3 + y0 + y1 + y2*y3 + y2 + y3*x1 + y3*x2 + y3 + x0, y0*y3 + y0 + y1*y3 + y1 + y2*y3 + y2 + y3*x0 + x0, y0*y3 + y0 + y1*y3 + y1*x2 + y1 + y2*x2 + y2 + y3 + x1 + x3, y0*y3 + y0*x3 + y0 + y1 + y2*y3 + y3*x3 + x0 + x2, y0*y3 + y0*x1 + y1*y3 + y1 + y2*y3 + y2*x2 + y2 + y3*x3 + y3 + x3 + 1, y0*y3 + y0*x0 + y2*x1 + y2 + y3*x2 + y3*x3 + x0 + x1 + x2 + x3, y0*y2 + y1 + y3 + x3 + 1, y0*y1 + y2*y3 + y3*x3 + y3 + x0 + x2 + x3 + 1 ] elif poly_choice == 1: l = [ y3 + x0 + x1*x2 + x1 + x3, y2 + x0*x1*x3 + x0*x1 + x0*x2*x3 + x0*x2 + x0 + x1*x2*x3 + x2, y1 + x0*x1*x3 + x0*x2*x3 + x0*x2 + x0*x3 + x0 + x1 + x2*x3 + 1, y0 + x0*x1*x3 + x0*x2*x3 + x0 + x1*x2*x3 + x1*x2 + x2 + x3 + 1 ] elif poly_choice == 2: l = [ y2*x3 + y3*x3 + x1*x3 + x2*x3 + x3, y0*x3 + y3*x3 + x1*x3 + x2*x3 + y0 + y3 + x1 + x2 + x3 + 1, x1*x2 + y3 + x0 + x1 + x3, x0*x2 + y3*x3 + x1*x3 + x2*x3 + y0 + y1 + y3 + x0 + x2 + x3, y3*x2 + y3*x3 + x1*x3 + y0 + y1 + y3 + x0 + x2 + x3, y0*x2 + y1*x2 + y1*x3 + y3*x3 + y1 + x0 + x1 + x2 + 1, x0*x1 + y3*x3 + x1*x3 + x2*x3 + y1 + y2 + x1 + x2 + x3 + 1, y3*x1 + y3*x3 + x2*x3 + y1 + y2 + y3 + x0 + x1 + x2 + 1, y2*x1 + y2*x2 + y3*x3 + x0*x3 + x1*x3 + y0 + x0 + 1, y1*x1 + y2*x2 + y1*x3 + x0*x3 + x1*x3 + y0 + y1 + y2 + y3 + x2 + x3, y0*x1 + y1*x2 + y1*x3 + x0*x3 + x2*x3 + y1 + y2 + y3 + x0 + x1 + 1, y3*x0 + y1*x2 + y2*x2 + y1*x3 + y3*x3 + x0*x3 + x2*x3 + y0 + y1 + y2 + x1 + x3, y2*x0 + y1*x2 + x0*x3 + y0 + y1 + y2 + x1 + x2 + x3, y1*x0 + y1*x3 + x0*x3 + x1*x3 + x2*x3 + y0 + y2 + y3 + x0 + x1 + x3 + 1, y0*x0 + y2*x2 + y1*x3 + x1*x3 + y0 + y1 + y3 + x0 + x3, y2*y3 + y1*x3 + y3*x3 + x0*x3 + x2*x3 + y0 + y1 + y2 + y3 + x0, y1*y3 + y1*x2 + y2*x2 + y1*x3 + y3*x3 + x0*x3 + x1*x3 + y1 + y3 + 1, y0*y3 + y1*x3 + y3*x3 + x0*x3 + x1*x3 + y0 + y2 + x1 + x3 + 1, y1*y2 + y1*x3 + x0*x3 + x1*x3 + y0 + x0 + 1, y0*y2 + y1 + y3 + x3 + 1, y0*y1 + y1*x3 + x0*x3 + x2*x3 + y0 + y1 + y2 + x2 + x3 + 1, y1*x2*x3 + y1*x2 + y3*x3 + x0*x3 + x1*x3 + x2*x3 + y3 + x0 + x1 + x2 ] else: raise TypeError, "poly_choice parameter not understood" return l def key_addition_polynomials(self, X, Z, K): """ Return key addition polynomials. X = Z + K INPUT: X -- output variables Z -- input state variables K -- key variables """ return [ self.R(X[j]) + self.R(Z[j]) + self.R(K[j]) for j in xrange(self.Bs)] def key_schedule_polynomials(self,K,i): """ Return a triple ($K_i$, $K$, $eqns$) with $K_i$ the round keys for round $i$, $K$ the updated key register of length self.Ks and $eqns$ a list of polynomials describing relationships between $K_i$ and $K_{i-1}$. INPUT: K -- key variable register i -- round counter """ Bs = self.Bs Ks = self.Ks s = self.s Ki = K[:Bs] K = K[61:Ks] + K[0:61] if i == self.Nr+1: # we don't need to update the register return Ki, K, [] # in the last step x = K[:s] y = self.vars("K",i)[:s] eqns = self.single_sbox_polynomials(x,y) K[:s] = y if Ks == 128: x = K[s:2*s] y = self.vars("K",i)[s:2*s] eqns = self.single_sbox_polynomials(x,y) K[s:2*s] = y rc = self.round_counter(i) if Ks == 80: K[Ks-1-19] += rc[0] K[Ks-1-18] += rc[1] K[Ks-1-17] += rc[2] K[Ks-1-16] += rc[3] K[Ks-1-15] += rc[4] else: # 128 K[Ks-1-66] += rc[0] K[Ks-1-65] += rc[1] K[Ks-1-64] += rc[2] K[Ks-1-63] += rc[3] K[Ks-1-62] += rc[4] return Ki, K, eqns def field_polynomials(self, X): """ Return list $x_i^2 + x_i$ for all $x_i$ in X. INPUT: X -- list """ if self._polybori: return [] else: return [x**2 + x for x in X] def sbox(self): """ Return SBox object. """ return self._sbox def __call__(self,P,K): """ Encrypt plaintext P with key K. INPUT: P -- plaintext K -- key """ Zi = [ self._base(e) for e in P ] for i in range(1,self.Nr+1): Ki,K = self.keySchedule(K, i) Xi = self.addRoundKey( Zi, Ki ) Yi = self.sBoxLayer( Xi ) Zi = self.pLayer(Yi) Ki,K = self.keySchedule(K, self.Nr+1) Xi = self.addRoundKey(Zi, Ki) return Xi def round_counter(self, i): """ INPUT: i -- integer """ rc = list(reversed(ZZ(i).digits())) if len(rc) < 5: rc = [0]*(5-len(rc)) + rc rc = map(self._base, rc[-5:]) return rc def keySchedule(self, K, i): """ INPUT: K -- key register of size self.Ks i -- round counter """ S = self.sbox() Bs = self.Bs Ki = [0]*Bs # extract key for j in xrange(Bs): Ki[j] = K[j] if self.Ks == 80: # update register K = K[61:80] + K[0:61] K[0:4] = S(K[0:4]) # add round counter rc = self.round_counter(i) K[80-1-19] += rc[0] K[80-1-18] += rc[1] K[80-1-17] += rc[2] K[80-1-16] += rc[3] K[80-1-15] += rc[4] return Ki, K elif self.Ks == 128: # update register K = K[61:128] + K[0:61] K[0:4] = S(K[0:4]) K[4:8] = S(K[4:8]) # add round constant rc = self.round_counter(i) K[128-1-66] += rc[0] K[128-1-65] += rc[1] K[128-1-64] += rc[2] K[128-1-63] += rc[3] K[128-1-62] += rc[4] return Ki, K def addRoundKey(self, X, Y): """ Return list of pairwise sums of elements in X and Y. INPUT: X -- list Y -- list """ return [ X[j] + Y[j] for j in range(self.Bs) ] def sBoxLayer(self, X): """ Apply S-boxes to X """ s = self.s sbox = self.sbox() return sum([ sbox(X[j:j+s]) for j in range(0,self.Bs,s) ],[]) def pLayer(self, Y): """ Return a list of length self.Bs with linear combinations of the elements in the list y (of length self.Bs) matching the permutation layer of PRESENT. INPUT: Y -- list of length self.Bs """ B = self.B s = self.s Z = [0]*B*s for i in xrange(B): for j in xrange(s): Z[B*j + i] = Y[s*i + j] return Z def pLayer_inverted(self, Z): """ """ B = self.B s = self.s Y = [0]*B*s for i in xrange(B): for j in xrange(s): Y[s*i + j] = Z[B*j + i] return Y def pLayer_as_permutation(self): """ """ return Permutation( p.pLayer(range(1,65)) ) def bitstringtohexstring(l): """ Return a hex string in PRESENT style for l a list of bits. INPUT: l -- a list with bit entries of length divisible by 4 """ r = [] for i in xrange(0,len(l),4): z = list(reversed(map(int, l[i:i+4]))) r.append(hex(ZZ(z,2))) r = sum([r[i:i+8]+[" "] for i in xrange(0,len(r),8) ],[]) return "".join(r)[:-1] ######################################################### # # Attack Code # ######################################################### def differential(self, **kwds): """ Return a bitstring for a given differential in Wang's notation EXAMPLE: sage: differential(p, x0=1) """ D = map(GF(2),[0,0,0,0]*self.B) S = self.sbox() for idx, diff in kwds.iteritems(): idx = self.B-1 - int(idx[1:]) #x1 => 1 diff = S.to_bits(diff) for i in xrange(4): D[idx*4+i] = diff[i] return D def get_differences(S, diff): r""" Return (i1,d1,i2,d2) for the S-Box S and the difference diff if diff has the non zero value d1 at index i1 and difference d2 at index i2. """ i1 = 0 d1 = 0 i2 = 0 d2 = 0 for i in reversed(range(0,len(diff),4)): d = S.from_bits( diff[i:i+4] ) if d!=0: i1,d1 = 16-1-i/4,d break for i in range(i-4,0,-4): d = S.from_bits( diff[i:i+4] ) if d!=0: i2,d2 = 16-1-i/4,d break return i1,d1,i2,d2 def check_differential(self, D): """ INPUT: p -- PRESENT instance D -- difference iterator EXAMPLE: sage: p = PRESENT(Nr=31) sage: check_differential(p, Wang6DiffIter(p)) 1 4 2 8 3 12 4 16 5 22 6 26 7 30 8 34 9 40 10 44 11 48 12 52 13 58 14 62 """ r = 1 p = 1 S = self.sbox() M = S.difference_distribution_matrix() it = iter(D) while True: if r == 15: break idiff = it.next() if r!=1 and idiff != self.pLayer(odiff): errstr = str(get_differences(S,idiff)) + " " + str(get_differences(S,self.pLayer(odiff))) raise ValueError, errstr ii1,id1,ii2,id2 = get_differences(S, idiff) odiff = it.next() oi1,od1,oi2,od2 = get_differences(S, odiff) p *= M[id1,od1]/16 * M[id2,od2]/16 print r, len(p.denominator().digits())-1 r += 1 def present_dc(self, **kwds): """ INPUT: timeout -- time in seconds to wait for a contradition (default: 200) r -- number of rounds to approximate (default: 1) K -- key to use (default: random) kwds -- passed on to polynomial system generator alg -- one from ('polybori', 'singular', 'magma') (default: 'polybori') characteristic -- use specific characteristic rather than differential (default: False) """ self = copy(self) timeout = kwds.get("timeout", 200) r = kwds.get("r", 1) K = kwds.get("K", self.random_element(self.Ks)) alg = kwds.get("alg","polybori") characteristic = kwds.get("characteristic", False) kwds["K"] = K R = self.ring(n=2) diff_iter = Wang6DiffIter counter = -1 while True: counter += 1 wt = walltime() # request new plaintexts P0 = self.random_element() it = diff_iter(self) DP = it.next() P1 = map(GF(2), [P0[i] + DP[i] for i in xrange(len(P0))]) l = [] # generate polynomial systems gen = self.new_generator(postfix=str(0)) gen.R = R F,s = gen.polynomial_system(P=P0, **kwds) for i in xrange(F.nrounds()): if characteristic or i > r: l.append(F.round(i)) gen = self.new_generator(postfix=str(1)) gen.R = R F,s = gen.polynomial_system(P=P1, **kwds) for i in xrange(F.nrounds()): if characteristic or i > r: l.append(F.round(i)) # test filter function if False and (self.Nr,r) in [(4,2),(8,6),(12,10),(16,14)]: C0 = gen(P0, K) C1 = gen(P1, K) DC = [C0[i] + C1[i] % 2 for i in xrange(len(C0))] if filter_wang(self, DC): pass else: print counter, "Fail" continue it = diff_iter(self) gd = R.gens_dict() for i in xrange(r): DX = it.next() X0 = self.varformatstr("X0") X1 = self.varformatstr("X1") if characteristic: l.append([gd[X0%(i+1,b)] + gd[X1%(i+1,b)] + DX[b] for b in range(self.Bs)]) DY = it.next() if i == 0: D1 = DY Y0 = self.varformatstr("Y0") Y1 = self.varformatstr("Y1") if characteristic or i == r-1: l.append([gd[Y0%(i+1,b)] + gd[Y1%(i+1,b)] + DY[b] for b in range(self.Bs)]) F = mq.MPolynomialSystem(R,l) try: if alg == "magma": F = F._magma_() alarm(timeout) # arm alarm gt = magma.cputime() gb = F.GroebnerBasis() gt = magma.cputime(gt) alarm(0) # disable alarm again gb = [R(str(e)) for e in gb] elif alg == "singular": singular.option("redTail") singular.option("redThrough") singular.option("redSB") F = F._singular_() alarm(timeout) # arm alarm gt = singular.cputime() gb = F.groebner() gt = singular.cputime(gt) alarm(0) # disable alarm again gb = [R(e) for e in gb] elif alg == "polybori": if not isinstance(R,BooleanPolynomialRing): print "here" R = BooleanPolynomialRing(R.ngens(),R.variable_names(),R.term_order()) vd = dict(zip(R.variable_names(),R.gens())) I = sage0(R.ideal(sage_eval(str(F.gens()),vd))) else: I = sage0(F.ideal()) alarm(timeout) # arm alarm gt = sage0.cputime() gb = I.groebner_basis(faugere=True)._sage_() gt = sage0.cputime(gt) alarm(0) # disable alarm again sage0._start() # mem hole otherwise gb = [eval(str(e),gd) for e in gb] print "% 3d %.3f %.3f"%(counter, float(gt), float(walltime(wt))) if gb != [1]: return gb except (TypeError, KeyboardInterrupt): print "candidate found" break # defining equations for the S-boxes S0 = lambda x0,x1,x2,x3: x0*x1*x3 + x0*x2*x3 + x0 + x1*x2*x3 + x1*x2 + x2 + x3 + 1 S1 = lambda x0,x1,x2,x3: x0*x1*x3 + x0*x2*x3 + x0*x2 + x0*x3 + x0 + x1 + x2*x3 + 1 S2 = lambda x0,x1,x2,x3: x0*x1*x3 + x0*x1 + x0*x2*x3 + x0*x2 + x0 + x1*x2*x3 + x2 S3 = lambda x0,x1,x2,x3: x0 + x1*x2 + x1 + x3 s = self.s ### first key batch offset = (self.B-1 - it._offset[0])*s # Wang is big endian k0,k1,k2,k3 = self.K0[offset:offset+s] d0,d1,d2,d3 = D1[offset:offset+s] p0,p1,p2,p3 = P0[offset:offset+s] q0,q1,q2,q3 = P1[offset:offset+s] Fbar0 = [ d0 + S0(p0+k0, p1+k1, p2+k2, p3+k3) + S0(q0+k0, q1+k1, q2+k2, q3+k3), d1 + S1(p0+k0, p1+k1, p2+k2, p3+k3) + S1(q0+k0, q1+k1, q2+k2, q3+k3), d2 + S2(p0+k0, p1+k1, p2+k2, p3+k3) + S2(q0+k0, q1+k1, q2+k2, q3+k3), d3 + S3(p0+k0, p1+k1, p2+k2, p3+k3) + S3(q0+k0, q1+k1, q2+k2, q3+k3)] K0 = K[offset:offset+s] ### second key batch offset = (self.B-1- it._offset[1] )*s # Wang is big endian k0,k1,k2,k3 = self.K0[offset:offset+s] d0,d1,d2,d3 = D1[offset:offset+s] p0,p1,p2,p3 = P0[offset:offset+s] q0,q1,q2,q3 = P1[offset:offset+s] Fbar1 = [ d0 + S0(p0+k0, p1+k1, p2+k2, p3+k3) + S0(q0+k0, q1+k1, q2+k2, q3+k3), d1 + S1(p0+k0, p1+k1, p2+k2, p3+k3) + S1(q0+k0, q1+k1, q2+k2, q3+k3), d2 + S2(p0+k0, p1+k1, p2+k2, p3+k3) + S2(q0+k0, q1+k1, q2+k2, q3+k3), d3 + S3(p0+k0, p1+k1, p2+k2, p3+k3) + S3(q0+k0, q1+k1, q2+k2, q3+k3)] K1 = K[offset:offset+s] return (self.R.ideal(Fbar0).groebner_basis(), K0), (self.R.ideal(Fbar1).groebner_basis(), K1) class DiffIter: def __init__(self, p ): """ Abstract class for difference characteristic iterator. INPUT: p -- PRESENT instance """ self._p = p self._d = [] self._it = 0 def __iter__(self): return self def next(self): if self._it < len(self._d): it = self._it self._it += 1 else: it = 0 self._it = 1 return self._d[it] class PRESENTDiffIter(DiffIter): def __init__(self, p): """ Difference characteristic as provided in the original PRESENT paper. """ DiffIter.__init__(self, p) self._offset = [0,3] self._d = [differential(p,x0=4,x3=4), differential(p,x0=5,x3=5), differential(p,x0=9,x8=9), differential(p,x0=4,x8=4), differential(p,x8=1,x10=1), differential(p,x8=9,x10=9), differential(p,x2=5,x14=5), differential(p,x2=1,x14=1)] class Wang6DiffIter(DiffIter): def __init__(self, p): """ Difference characteristic as provided in Wang's ePrint paper and via private communication. """ DiffIter.__init__(self, p) self._offset = [2,14] self._d = [differential(p, x2=7, x14=7), # R1 differential(p, x2=1, x14=1), differential(p, x0=4, x3=4), # R2 differential(p, x0=5, x3=5), differential(p, x0=9, x8=9), # R3 differential(p, x0=4, x8=4), differential(p, x8=1, x10=1), # R4 differential(p, x8=9, x10=9), differential(p, x2=5, x14=5), # R5 differential(p, x2=1, x14=1), differential(p, x0=4, x3=4), # R6 differential(p, x0=5, x3=5), differential(p, x0=9, x8=9), # R7 differential(p, x0=4, x8=4), differential(p, x8=1, x10=1), # R8 differential(p, x8=9, x10=9), differential(p, x2=5, x14=5), # R9 differential(p, x2=1, x14=1), differential(p, x0=4, x3=4), # R10 differential(p, x0=5, x3=5), differential(p, x0=9, x8=9), # R11 differential(p, x0=4, x8=4), differential(p, x8=1, x10=1), # R12 differential(p, x8=9, x10=9), differential(p, x2=5, x14=5), # R13 differential(p, x2=1, x14=1), differential(p, x0=4, x3=4), # R14 differential(p, x0=5, x3=5), differential(p, x0=9, x8=9), # we don't have enough data for this guy differential(p, x0=4, x8=4), differential(p, x8=1, x10=1), ] def __len__(self): return len(self._d) def filter_wang(self, D): """ INPUT: self -- PRESENT polynomial system generator D -- list of length 64 """ S = self.sbox() s = self.s nonzeros = map(lambda x: x*s, [15-4, 15-6, 15-8, 15-10, 15-12, 15-14]) # strip last permutation layer D = self.pLayer_inverted(D) for i in range(0,64,4): v = S.from_bits( D[i:i+4] ) if i in nonzeros: if v not in [3,7,9,13,0]: return False if i not in nonzeros: if v != 0: return False return True