Gits2012teaser

What is the password? (File)
Hint: TeLaViv+ is a packet forensics challenge.

• 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