3,585 bytes added,
15:36, 8 January 2012 == #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>