CTF/gits2012teaser/2-ALsRevenge

From Fixme.ch
Jump to: navigation, search

#2 AL's Revenge

Question

Use your team GUID and generate a serial. (File)
Hint: File

Solution

  • file 49dd327824d5afe9cdf931ea4b13719f.bin says xz compressed file -> xzcat > f
  • file f says LLVM bitcode -> llvm-dis > f.s (only works with LLVM 2.8, not with 3.0)
  • analyze disassembly, extract C representation:
int
VerifySerial(uint64_t name, uint64_t serial)
{
	uint64_t a = 0x8000000000000000LL;
        uint64_t b = 0xa348fccd93aea5a7LL;
	uint64_t result = 0;
 
	/* high order bit set? */
	if (name & a)
		a ^= b;
 
	if (serial & a)
		serial ^= b;
 
	while (serial != 0) {
		if (serial & 1)
			result ^= name;
 
		serial >>= 1;
		name <<= 1;
 
		if (name & a)
			name ^= b;
	}H
 
	return (result == 1);
}
  • it looks like a multiplication over a galois field, with the irreducible polynomial 0x1a348fccd93aea5a7 (note leading bit not in C), but it actually isn't, because the high bit gets checked after the shift, not before.
  • lacking math knowledge and math package fu, decided to treat the problem as a linear equation system:
  • The shifting and xoring produces a set of integers, call them name_i. If the serial bit s_i is set, name_i gets added to the result. So you can roughly say r = N * s, with r being the result vector, s the serial vector and N the names matrix.
  • lacking math package fu, implement a gaussian elimination manually:
class Numeric
  def bits64
    sprintf("%064b", self).each_char.map{|c| c == "0" ? 0 : 1}
  end
end
 
def names(name)
  p = 0xa348fccd93aea5a7
 
  if (name >> 63) & 1 == 1
    name ^= p
  end
 
  ([name] + 63.times.map do |i|
    name <<= 1
    if (name >> 63) & 1 == 1
      name ^= p
    end
    name
  end).map(&:bits64)
end
 
class Array
  def pivot
    res = []
    self[0].size.times.map do |i|
      self.size.times.map do |j|
        self[j][i]
      end
    end
  end
 
  def bitary_to_int
    self.join.to_i(2)
  end
end
 
class Eq < Array
  attr_accessor :res
 
  def initialize(ary, res)
    self.replace(ary)
    @res = res
  end
 
  def lead_zero
    self.take_while{|e| e == 0}
  end
 
  def first_pos
    self.index(1)
  end
 
  def subtract(o)
    Eq.new(self.zip(o).map{|aa, bb| aa ^ bb}, @res ^ o.res)
  end
end
 
class EqSys < Array
  def initialize(ary, res=nil)
    if !(Eq === ary[0]) && !ary.empty?
      ary = ary.zip(res).map{|a, r| Eq.new(a, r)}
    end
    self.replace(ary)
  end
 
  def sort_by_zeros
    self.sort do |a, b|
      a.lead_zero <=> b.lead_zero
    end
  end
 
  def subtract_eq(eq)
    pos = eq.first_pos
    return self if not pos
    EqSys.new(self.map{|e| e[pos] == 1 ? e.subtract(eq) : e})
  end
 
  def elim
    front = EqSys.new([])
    cur = nil
    rest = self.sort_by_zeros
    while not rest.empty?
      front << cur if cur
      cur = rest.shift
 
      front = front.subtract_eq(cur)
      rest = rest.subtract_eq(cur)
      rest = rest.sort_by_zeros
    end
    front << cur
 
    front
  end
 
  def to_s
    self.map{|e| e.map(&:to_s).join + " = #{e.res}"}.join("\n")
  end
end
 
require 'pp'
if __FILE__ == $0
  ns = names(0x6638623261336134)
 
  pv = ns.pivot
  es = EqSys.new(pv, 1.bits64)
 
  puts es.to_s
  puts
 
  r = es.elim
  puts r.to_s
 
  res = r.map{|e| e.res}.reverse
  puts res.bitary_to_int.to_s(16)
 
  s0 = r.pivot.last.reverse
  puts s0.bitary_to_int.to_s(16)
  puts (res.bitary_to_int^s0.bitary_to_int).to_s(16)
end