bmw/analyze_f0.rb

   1 # analyze_f0.rb
   2 =begin
   3     This file is part of the ARM-Crypto-Lib.
   4     Copyright (C) 2006-2010  Daniel Otte (daniel.otte@rub.de)
   5
   6     This program is free software: you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation, either version 3 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 =end
  19 =begin
  20   q[ 0] = (+ h[ 5] - h[ 7] + h[10] + h[13] + h[14]);
  21   q[ 3] = (+ h[ 8] - h[10] + h[13] + h[ 0] - h[ 1]);
  22   q[ 6] = (- h[11] + h[13] - h[ 0] - h[ 3] + h[ 4]);
  23   q[ 9] = (+ h[14] + h[ 0] - h[ 3] + h[ 6] - h[ 7]);
  24   q[12] = (+ h[ 1] + h[ 3] - h[ 6] - h[ 9] + h[10]);
  25   q[15] = (- h[ 4] - h[ 6] - h[ 9] + h[12] + h[13]);
  26   q[ 2] = (+ h[ 7] + h[ 9] - h[12] + h[15] + h[ 0]);
  27   q[ 5] = (+ h[10] - h[12] + h[15] - h[ 2] + h[ 3]);
  28   q[ 8] = (+ h[13] - h[15] + h[ 2] - h[ 5] - h[ 6]);
  29   q[11] = (- h[ 0] - h[ 2] - h[ 5] + h[ 8] + h[ 9]);
  30   q[14] = (+ h[ 3] - h[ 5] + h[ 8] - h[11] - h[12]);
  31   q[ 1] = (+ h[ 6] - h[ 8] + h[11] + h[14] - h[15]);
  32   q[ 4] = (+ h[ 9] - h[11] - h[14] + h[ 1] + h[ 2]);
  33   q[ 7] = (- h[12] - h[14] + h[ 1] - h[ 4] - h[ 5]);
  34   q[10] = (+ h[15] - h[ 1] - h[ 4] - h[ 7] + h[ 8]);
  35   q[13] = (+ h[ 2] + h[ 4] + h[ 7] + h[10] + h[11]);
  36 =end
  37 f0_def =
  38 [
  39   [  '+5',  '-7', '+10', '+13', '+14'],
  40   [  '+8', '-10', '+13',  '+0',  '-1'],
  41   [ '-11', '+13',  '-0',  '-3',  '+4'],
  42   [ '+14',  '+0',  '-3',  '+6',  '-7'],
  43   [  '+1',  '+3',  '-6',  '-9', '+10'],
  44   [  '-4',  '-6',  '-9', '+12', '+13'],
  45   [  '+7',  '+9', '-12', '+15',  '+0'],
  46   [ '+10', '-12', '+15',  '-2',  '+3'],
  47   [ '+13', '-15',  '+2',  '-5',  '-6'],
  48   [  '-0',  '-2',  '-5',  '+8',  '+9'],
  49   [  '+3',  '-5',  '+8', '-11', '-12'],
  50   [  '+6',  '-8', '+11', '+14', '-15'],
  51   [  '+9', '-11', '-14',  '+1',  '+2'],
  52   [ '-12', '-14',  '+1',  '-4',  '-5'],
  53   [ '+15',  '-1',  '-4',  '-7',  '+8'],
  54   [  '+2',  '+4',  '+7', '+10', '+11']
  55 ]
  56
  57 $stat=Hash.new
  58 $stat_location=Hash.new
  59
  60 def set_stat(s1,s2,i)
  61   if s2.to_i.abs<s1.to_i.abs
  62     t = s1
  63     s1 = s2
  64     s2 = t
  65   end
  66   idx = nil
  67   idx = 0 if s1[0].chr=='+' && s2[0].chr=='+'
  68   idx = 1 if s1[0].chr=='+' && s2[0].chr=='-'
  69   idx = 2 if s1[0].chr=='-' && s2[0].chr=='+'
  70   idx = 3 if s1[0].chr=='-' && s2[0].chr=='-'
  71   puts "ERROR in idx" if idx==nil
  72   if $stat[(s1[1..-1]+','+s2[1..-1])]==nil
  73     $stat[(s1[1..-1]+','+s2[1..-1])] = [0,0,0,0]
  74     $stat_location[(s1[1..-1]+','+s2[1..-1])] = i.to_s()
  75   else
  76     $stat_location[(s1[1..-1]+','+s2[1..-1])] += ','+i.to_s()
  77   end
  78   $stat[(s1[1..-1]+','+s2[1..-1])][idx]+= 1
  79 end
  80
  81 def collision(x,y)
  82   r=0
  83   va = x[0].split(',')
  84   vb = y[0].split(',')
  85   va.each do |p|
  86     r=1 if vb.find_index(p)
  87   end
  88   return false if r==0
  89   va = x[2].split(',')
  90   vb = y[2].split(',')
  91   va.each do |p|
  92     r=2 if vb.find_index(p)
  93   end
  94   return false if r==1
  95   return true
  96 end
  97
  98 def reg_empty(map, reg, from, to)
  99   (from..to).each do |x|
 100     return false if(map[x][reg])
 101   end
 102   return true
 103 end
 104
 105 def reg_set(map, reg, from, to, value)
 106    (from..to).each do |x|
 107     map[x][reg] = value
 108   end
 109
 110 end
 111
 112 def print_reg_map(map, regs, length, indent=0)
 113   (regs-1).downto(0) do |r|
 114     print ' '*indent+'r'+r.to_s
 115     print ' '*(2+(2-r.to_s.length))
 116     print ':'
 117     (0..(length-1)).each do |x|
 118       if map[x][r]==nil
 119         print ' '
 120       else
 121         print map[x][r]
 122       end
 123     end
 124     print "\n"
 125   end
 126 end
 127
 128 def reg_map(steps, length)
 129   max_reg=0
 130   map = Array.new(length)
 131   (0..(length-1)).each {|x| map[x]=Array.new}
 132   steps.each do |step|
 133     reg=0
 134     a = step[2].split(',').collect { |x| x.to_i}
 135     a.sort!
 136     from = a[0]
 137     to = a[-1]
 138     while(reg_empty(map,reg,from,to)==false)
 139       reg += 1
 140     end
 141     reg_set(map, reg, from, to, step[3])
 142     max_reg=reg if reg>max_reg
 143   end
 144   return max_reg, map
 145 end
 146
 147 def word_to_steps(word, list)
 148   steps=Array.new
 149   idx=0
 150   while(word!=0)
 151     if(word&1==1)
 152       steps << list[idx]
 153     end
 154     word >>= 1
 155     idx += 1
 156   end
 157   return steps
 158 end
 159
 160 def print_collision_map(collisions, length)
 161   print '  '
 162   (0..(length-1)).each {|x| print ('A'[0]+x).chr+' '}
 163   (0..(length-1)).each do |y|
 164     print "\n"+('A'[0]+y).chr+' '
 165     (0..(length-1)).each do |x|
 166       if(collisions.find_index(('A'[0]+x).chr+('A'[0]+y).chr)) or
 167         (collisions.find_index(('A'[0]+y).chr+('A'[0]+x).chr))
 168         print('x ')
 169       else
 170         print('  ')
 171       end
 172     end
 173   end
 174   print("\n")
 175 end
 176
 177 def check_collision(word, lut)
 178   (0..(lut.length-1)).each do |i|
 179     if word&(1<<i)!=0
 180       return true if word&lut[i]!=0
 181     end
 182   end
 183   return false
 184 end
 185
 186 $bitcount_lut = Array.new(65536)
 187
 188 def bits_set_simple(x)
 189   r = 0
 190   while(x!=0)
 191     r+=1 if(x&1==1)
 192     x >>=1
 193   end
 194   return r
 195 end
 196
 197 def init_bitcount_lut
 198   (0..(2**8-1)).each {|x| $bitcount_lut[x] = bits_set_simple(x)}
 199   ((2**8)..(2**16-1)).each {|x| $bitcount_lut[x] = bits_set(x, 8)}
 200 end
 201
 202 def bits_set(x, length=16)
 203   r=0
 204   while(x!=0)
 205     r += $bitcount_lut[x&(2**length-1)]
 206     x >>= length
 207   end
 208   return r
 209 end
 210
 211 def decode_word(word)
 212   idx='A'
 213   r = ''
 214   while(word!=0)
 215     if(word&1==1)
 216       r += idx
 217     end
 218     word >>= 1
 219     idx = (idx[0]+1).chr
 220   end
 221   return r
 222 end
 223
 224 def generate_c_code(fout, func, optimizations=[], reg_map=[])
 225   out_interval = 3
 226   out_modulus = 16
 227   out_idx = 0
 228   opt_table = Array.new
 229   optimizations.each do |opt|
 230     opt_steps = opt[2].split(',')
 231     opt_steps.collect! {|x| x.to_i}
 232     opt_steps.each do |step|
 233       reg_a = opt[0].split(',')[0]
 234       reg_b = opt[0].split(',')[1]
 235       sign_a = '+' if func[step].find_index('+'+reg_a)
 236       sign_a = '-' if func[step].find_index('-'+reg_a)
 237       sign_b = '+' if func[step].find_index('+'+reg_b)
 238       sign_b = '-' if func[step].find_index('-'+reg_b)
 239       set = false
 240       free = false
 241       if step==opt_steps[0]
 242         sign_out='+'
 243         set=true
 244       else
 245         i=0
 246         while opt_table[opt_steps[0]][i][4]!=reg_a || opt_table[opt_steps[0]][i][5]!=reg_b
 247           i+=1
 248         end
 249         if(sign_a==opt_table[opt_steps[0]][i][0])
 250           sign_out='+'
 251         else
 252           sign_out='-'
 253         end
 254       end
 255       free = true if step==opt_steps[-1]
 256       reg_number = reg_map[step].find_index(opt[3])
 257       reg_name = sprintf("tr%d", reg_number)
 258       opt_table[step] = Array.new if opt_table[step]==nil
 259       opt_table[step] << [sign_a, sign_b, sign_out, reg_name, reg_a, reg_b, set, free]
 260     end
 261   end
 262   puts 'DBG: '+opt_table.inspect
 263   (0..(func.length-1)).each do |i|
 264     fout.printf("q[%2d] = ", out_idx)
 265     out_idx = (out_idx+out_interval)%out_modulus
 266     func[i].each do |j|
 267       skip = 0
 268       if opt_table[i]
 269         opt_table[i].each do |opt|
 270           skip = 1 if opt[4]==j[1..-1] or opt[5]==j[1..-1]
 271         end
 272       end
 273       fout.printf("%st[%2d] ", j[0].chr, j[1..-1].to_i) if skip==0
 274     end
 275     if opt_table[i]
 276       opt_table[i].each do |opt|
 277         fout.print(opt[2]+'('+opt[3])
 278         if opt[6]
 279           fout.printf('=%st[%2d]%st[%2d]',opt[0],opt[4].to_i,opt[1],opt[5].to_i)
 280         end
 281         fout.print(') ')
 282       end
 283     end
 284     fout.print(";\n")
 285   end
 286 end
 287
 288 (0..15).each do |i|
 289   (0..3). each do |j|
 290     ((j+1)..4).each do |k|
 291       set_stat(f0_def[i][j], f0_def[i][k], i)
 292     end
 293   end
 294 end
 295
 296
 297
 298 dublets = Array.new
 299
 300 $stat.each_pair do |key,value|
 301   if value[0]+value[3]>1 || value[1]+value[2]>1
 302 #    puts key+": \t"+value.inspect+": \t"+$stat_location[key]
 303   dublets << [key, value, $stat_location[key]]
 304   end
 305 end
 306
 307 dublets.sort! do |x,y|
 308   t = x[2].split(',')
 309   p = t[1].to_i - t[0].to_i
 310   t = y[2].split(',')
 311   q = t[1].to_i - t[0].to_i
 312   if (p!=q)
 313     (p-q)
 314   else
 315     (x[2].split(',')[0].to_i-y[2].split(',')[0].to_i)
 316   end
 317 end
 318
 319 idx='A'
 320 dublets.each {|e| e << idx; idx=(idx[0]+1).chr}
 321
 322 puts "useful combinations:"
 323 dublets.each {|e| puts e[3]+': '+e[0]+' '*(5-e[0].length)+" \t"+e[1].inspect+" \t" +e[2]}
 324
 325 collisions = Array.new
 326 puts "searching for collisions: "
 327 (0..(dublets.length-2)).each do |i|
 328   ((i+1)..(dublets.length-1)).each do |j|
 329     if collision(dublets[i], dublets[j])
 330       print '*'
 331       collisions << dublets[i][3]+dublets[j][3]
 332     else
 333       print '.'
 334     end
 335   end
 336 end
 337 puts ''
 338 #puts "collisions: "
 339 #puts collisions.join(',')
 340 #puts "collision-map: "
 341 #print_collision_map(collisions, dublets.length)
 342
 343 collision_lut = Array.new(dublets.length, 0)
 344 (0..(dublets.length-1)).each do |x|
 345   (0..(dublets.length-1)).each do |y|
 346     if collisions.find_index(('A'[0]+x).chr+('A'[0]+y).chr) or
 347        collisions.find_index(('A'[0]+y).chr+('A'[0]+x).chr)
 348       collision_lut[x] |= 1<<y
 349     end
 350   end
 351 end
 352
 353
 354 puts "initializing bitcount table..."
 355 init_bitcount_lut
 356
 357 puts "collision free combinations:"
 358 max = 0
 359 combinations = Array.new
 360 percent = 0
 361 percent_step =(2**dublets.length-1)/10000.0
 362 next_step = (2**dublets.length-1)
 363 puts ''
 364 (2**dublets.length-1).downto(0) do |x|
 365   if(x<=next_step)
 366     print "\x1b[s "+sprintf("%5.2f%%", percent/100.0)+"\x1b[u"
 367     percent += 1
 368     next_step -= percent_step
 369   end
 370   if check_collision(x, collision_lut) == false
 371     if bits_set(x)>= max
 372       combinations = Array.new if bits_set(x)>max
 373       combinations << x
 374       max = bits_set(x)
 375     end
 376   end
 377 end
 378
 379 combinations.each do |c|
 380   regs, reg_map = reg_map(word_to_steps(c, dublets), f0_def.length)
 381   puts bits_set(c).to_s+': '+decode_word(c)+' ( '+(regs+1).to_s+' registers)'
 382   print_reg_map(reg_map, regs+1, f0_def.length, 4)
 383 end
 384 steps = word_to_steps(combinations[-1], dublets)
 385 regs, reg_map = reg_map(steps, f0_def.length)
 386 generate_c_code(STDOUT, f0_def,steps, reg_map)