pb0.py
1 #!/usr/bin/env python 2 3 # r = set() 4 # p0 only outputs c d e f 5 #for k in range(16): 6 # for tmp in range(16): 7 # if (tmp&0xc != 0): continue 8 # k1 = (k + (tmp & 3)) % 0x100 # 1f6f 9 # k1 = (((((tmp << 6) | (tmp >> 2)) + k1) & 3) | 0xc) % 0x100 10 # r.add(k1) 11 # print(f"{k:2} {tmp:2} = {k1:2} | {k:x} {tmp:x} = {k1:x}") 12 13 # p1 only outputs 3 7 b f 14 #for k in range(16): 15 # for tmp in range(16): 16 # if (tmp&3!=0): continue 17 # k1 = ((k << 6) | (k >> 2)) & 0xff # 1fa2 .. 1fa6 18 # k1 += tmp & 3 # 1fb7, 1fbb 19 # tmp1 = (((tmp << 6) | (tmp >> 2)) + k1) & 3 20 # k1 = (((tmp1 >> 2 | (tmp1 << 2)) & 0xff) | 3) % 0x100 # 1fbd .. 1fc8 21 # print(f"{k:2} {tmp:2} = {k1:2} | {k:x} {tmp:x} = {k1:x}") 22 # r.add(k1) 23 24 # p2 only outputs 0 1 2 3 25 #for k in range(16): 26 # for tmp in range(16): 27 # if (tmp&0xc != 0xc): continue 28 # k1 = k & 3 # 1fe3 .. 1fe7 29 # k1 = (k1 + (tmp & 3)) % 0x100 # 1ff8, 1fbb 30 # k1 = ((((tmp << 6) | (tmp >> 2)) % 0x100) + k1) & 3 # 1ffe .. 2005 31 # print(f"{k:2} {tmp:2} = {k1:2} | {k:x} {tmp:x} = {k1:x}") 32 # r.add(k1) 33 34 # p3 only outputs 0 4 8 c 35 #for k in range(16): 36 # for tmp in range(16): 37 # if (tmp&0x3 != 3): continue 38 # k1 = (k >> 2) & 3 # 202c 39 # k1 = (k1 + (tmp & 3)) % 0x100 # 203d, 2041 40 # tmp1 = ((((tmp << 6) | (tmp >> 2)) % 0x100) + k1) & 3 # 2043 .. 2048 41 # k1 = ((tmp1 << 2) | (tmp1 >> 6)) % 0x100 # 204a .. 204c 42 # print(f"{k:2} {tmp:2} = {k1:2} | {k:x} {tmp:x} = {k1:x}") 43 # r.add(k1) 44 45 #print(r) 46 47 # combine all inputs into a 10-bitvector tmp1|tmp|k and map it to it's output 48 kstats = {k:0 for k in range(16)} 49 sbox = [0]*1024 50 for i in range(4): 51 if(i==0): 52 # p0 -> c d e f 53 for k in range(16): 54 for tmp in range(16): 55 if (tmp&0xc != 0): 56 k1 = (k-4)%0x10 57 print(f"{i:02b}{tmp:04b}{k:04b} {k1:x}") 58 kstats[k1]+=1 59 sbox[(i<<8)|(tmp<<4)|k]=k1 60 continue 61 k1 = (k + (tmp & 3)) % 0x100 # 1f6f 62 k1 = (((((tmp << 6) | (tmp >> 2)) + k1) & 3) | 0xc) % 0x100 63 print(f"{i:02b}{tmp:04b}{k:04b} {k1:x}") 64 sbox[(i<<8)|(tmp<<4)|k]=k1 65 kstats[k1]+=1 66 67 elif(i==1): 68 # p1 -> 3 7 b f 69 for k in range(16): 70 for tmp in range(16): 71 if (tmp&3!=0): 72 k1 = (k-1)%0x10 73 print(f"{i:02b}{tmp:04b}{k:04b} {k1:x}") 74 kstats[k1]+=1 75 sbox[(i<<8)|(tmp<<4)|k]=k1 76 continue 77 k1 = ((k << 6) | (k >> 2)) & 0xff # 1fa2 .. 1fa6 78 k1 += tmp & 3 # 1fb7, 1fbb 79 tmp1 = (((tmp << 6) | (tmp >> 2)) + k1) & 3 80 k1 = (((tmp1 >> 2 | (tmp1 << 2)) & 0xff) | 3) % 0x100 # 1fbd .. 1fc8 81 print(f"{i:02b}{tmp:04b}{k:04b} {k1:x}") 82 sbox[(i<<8)|(tmp<<4)|k]=k1 83 kstats[k1]+=1 84 85 elif(i==2): 86 # p2 -> 0 1 2 3 87 for k in range(16): 88 for tmp in range(16): 89 if (tmp&0xc != 0xc): 90 k1 = (k+4)%0x10 91 print(f"{i:02b}{tmp:04b}{k:04b} {k1:x}") 92 kstats[k1]+=1 93 sbox[(i<<8)|(tmp<<4)|k]=k1 94 continue 95 k1 = k & 3 # 1fe3 .. 1fe7 96 k1 = (k1 + (tmp & 3)) % 0x100 # 1ff8, 1fbb 97 k1 = ((((tmp << 6) | (tmp >> 2)) % 0x100) + k1) & 3 # 1ffe .. 2005 98 print(f"{i:02b}{tmp:04b}{k:04b} {k1:x}") 99 sbox[(i<<8)|(tmp<<4)|k]=k1 100 kstats[k1]+=1 101 102 else: 103 # p3 -> 0 4 8 c 104 for k in range(16): 105 for tmp in range(16): 106 if (tmp&0x3 != 3): 107 k1 = (k+1)%0x10 108 print(f"{i:02b}{tmp:04b}{k:04b} {k1:x}") 109 kstats[k1]+=1 110 sbox[(i<<8)|(tmp<<4)|k]=k1 111 continue 112 k1 = (k >> 2) & 3 # 202c 113 k1 = (k1 + (tmp & 3)) % 0x100 # 203d, 2041 114 tmp1 = ((((tmp << 6) | (tmp >> 2)) % 0x100) + k1) & 3 # 2043 .. 2048 115 k1 = ((tmp1 << 2) | (tmp1 >> 6)) % 0x100 # 204a .. 204c 116 print(f"{i:02b}{tmp:04b}{k:04b} {k1:x}") 117 sbox[(i<<8)|(tmp<<4)|k]=k1 118 kstats[k1]+=1 119 120 print("distribution of output nibbles") 121 for i in range(16): 122 print(f"{i:04b}: {kstats[i]}") 123 print("values where the top or bottom 2 bits have the same value are more often generated,\n" 124 "with 0011/1100/1111/0000 being most commonly generated\n") 125 126 b0stats = {i:0 for i in range(4)} 127 b1stats = {i:0 for i in range(4)} 128 for i in range(16): 129 for j, b in enumerate(f"{i:04b}"): 130 if b=='1': b1stats[j]+=kstats[i] 131 else: b0stats[j]+=kstats[i] 132 133 print("bitwise distribution of outputs") 134 for i in range(4): 135 print(f"{i} 1:{b1stats[i]} 0:{b0stats[i]}") 136 137 def boxperm(i, k, tmp): 138 if(i==0): 139 if (tmp&0xc != 0): 140 return (k-4)%0x10 141 k += (tmp & 3) # 1f6f 142 return (((((tmp << 6) | (tmp >> 2)) + k) & 3) % 0x100) | 0xc 143 elif(i==1): 144 if (tmp&3!=0): 145 return (k-1)%0x10 146 k1 = ((k << 6) | (k >> 2)) & 0xff # 1fa2 .. 1fa6 147 k1 += tmp & 3 # 1fb7, 1fbb 148 tmp1 = (((tmp << 6) | (tmp >> 2)) + k1) & 3 149 return (((tmp1 >> 2 | (tmp1 << 2)) & 0xff) | 3) % 0x100 # 1fbd .. 1fc8 150 elif(i==2): 151 if (tmp&0xc != 0xc): 152 return (k+4)%0x10 153 k1 = k & 3 # 1fe3 .. 1fe7 154 k1 = (k1 + (tmp & 3)) % 0x100 # 1ff8, 1fbb 155 return ((((tmp << 6) | (tmp >> 2)) % 0x100) + k1) & 3 # 1ffe .. 2005 156 else: 157 if (tmp&0x3 != 3): 158 return (k+1)%0x10 159 k1 = (k >> 2) & 3 # 202c 160 k1 = (k1 + (tmp & 3)) % 0x100 # 203d, 2041 161 tmp1 = ((((tmp << 6) | (tmp >> 2)) % 0x100) + k1) & 3 # 2043 .. 2048 162 return ((tmp1 << 2) | (tmp1 >> 6)) % 0x100 # 204a .. 204c 163 164 # verify that sbox is indeed equal to boxperm 165 for i in range(4): 166 for k in range(16): 167 for tmp in range(16): 168 assert boxperm(i,k,tmp) == sbox[(i<<8)|(tmp<<4)|k] 169 170 def moebius(f,n): 171 blocksize=1 172 for step in range(1,n+1): 173 source=0 174 while(source < (1<<n)): 175 target = source + blocksize 176 for i in range(blocksize): 177 f[target+i]^=f[source+i] 178 source+=2*blocksize 179 blocksize*=2 180 181 def get_anfs(): 182 res = {} 183 184 fs=[[0]*1024,[0]*1024,[0]*1024,[0]*1024] 185 ms=[[0]*1024,[0]*1024,[0]*1024,[0]*1024] 186 187 for bit in range(4): 188 #print("bit", bit) 189 ones=0 190 for i in range(1024): 191 b = (sbox[i] >> bit) & 1 192 fs[bit][i]=b 193 ms[bit][i]=b 194 ones+=b 195 #print(''.join(f"{b}" for b in fs[bit]), ones) 196 moebius(ms[bit],10) 197 #print(''.join(f"{b}" for b in ms[bit]), ms[bit].count(1)) 198 #print() 199 200 # these have odd number of 1 constant terms in their polinomial 201 odd_const_terms = [2,3] 202 for j, (f, m) in enumerate(zip(fs,ms)): 203 f_ = ' ^ '.join(c for c in ['&'.join(f"x{i}" for i, x in enumerate(reversed(f'{a:010b}')) if x =='1') for a in range(1024) if m[a]==1] if c) 204 # these have odd number of 1 constant terms in their polinomial 205 if j in odd_const_terms: 206 f_ = '1 ^ ' + f_ 207 print(j, f_) 208 evaled =''.join(str(eval(f_, {f"x{i}":int(x) for i, x in enumerate(reversed(f'{a:010b}'))})) for a in range(1024)) 209 print('joined', ''.join(f"{b}" for b in f)) 210 print('evaled', evaled) 211 assert evaled==''.join(f"{b}" for b in f) 212 213 f_ = [] 214 for j, (f, m) in enumerate(zip(fs,ms)): 215 f_.append(' ^ '.join('('+c+')' for c in ['&'.join(f"x[{i}]" for i, x in enumerate(reversed(f'{a:010b}')) if x =='1') for a in range(1024) if m[a]==1] if c)) 216 if j in odd_const_terms: 217 f_[-1] = '1 ^ ' + f_[-1] 218 #print((p,nib), ', '.join(reversed(f_))) 219 return ', '.join(reversed(f_)) 220 221 anfs = get_anfs() 222 print(anfs)