Francois: Created page with "== #2 AL's Revenge == === Question === Use your team GUID and generate a serial. (File)
Hint: [[Media:17b82879c583eeae763ecfa..."

2012-01-08T15:36:36Z

Created page with "== #2 AL's Revenge == === Question === Use your team GUID and generate a serial. (File)<br> Hint: [[Media:17b82879c583eeae763ecfa..."

New page

== #2 AL's Revenge ==

=== Question ===

Use your team GUID and generate a serial. ([[Media:49dd327824d5afe9cdf931ea4b13719f.bin|File]])<br>
Hint: [[Media:17b82879c583eeae763ecfa9a135e431.cpp|File]]

=== Solution ===

* file [[Media:49dd327824d5afe9cdf931ea4b13719f.bin|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:

<syntaxhighlight lang="c">
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);
}
</syntaxhighlight>

* 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:

<syntaxhighlight lang="ruby">
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
</syntaxhighlight>

CTF/gits2012teaser/2-ALsRevenge - Revision history

Francois: Created page with "== #2 AL's Revenge == === Question === Use your team GUID and generate a serial. (File) Hint: [[Media:17b82879c583eeae763ecfa..."

Francois: Created page with "== #2 AL's Revenge == === Question === Use your team GUID and generate a serial. (File)
Hint: [[Media:17b82879c583eeae763ecfa..."