Difference between revisions of "Gits2012teaser"

From Fixme.ch
Jump to: navigation, search
(#1 TelAviv)
 
(20 intermediate revisions by 3 users not shown)
Line 1: Line 1:
== #1 TelAviv ==
+
[[Category:CTF]]
 +
[[Image:gits-scores.png]]
  
What is the password? ([[Media:7139a4ea239dcac655f7c38ca6a77b61.bin|File]])<br>
+
= Ghost in the Shellcode 2012 Teasers writeups =
Hint: TeLaViv+ is a packet forensics challenge.
+
  
== #2 AL's Revenge ==
+
http://ghostintheshellcode.com/
  
* file 49dd327824d5afe9cdf931ea4b13719f.bin says xz compressed file -> xzcat > f
+
Thanks to the organizers for those pretty nice teasers!
* file f says LLVM bitcode -> llvm-dis > f.s (only works with LLVM 2.8, not with 3.0)
+
* analyze disassembly, extract C representation:
+
  
<pre>
+
The following writeups have been made by members of the FIXME team during between January 6th and January 8th.
int
+
VerifySerial(uint64_t name, uint64_t serial)
+
{
+
uint64_t a = 0x8000000000000000LL;
+
        uint64_t b = 0xa348fccd93aea5a7LL;
+
uint64_t result = 0;
+
  
/* high order bit set? */
+
* Challenge [[CTF/gits2012teaser/1-TelAviv|#1 TelAviv]] by [[User:Francois|Francois]]
if (name & a)
+
* Challenge [[CTF/gits2012teaser/2-ALsRevenge|#2 AL's Revenge]] by [[User:Corecode|Corecode]]
a ^= b;
+
* Challenge [[CTF/gits2012teaser/3-Hackquest|#3 Hackquest]] by [[User:Corecode|Corecode]]
 
+
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);
+
}
+
</pre>
+
 
+
* 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:
+
 
+
<pre>
+
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
+
</pre>
+
 
+
== #3 Hackquest ==
+

Latest revision as of 09:24, 22 October 2012

Gits-scores.png

Ghost in the Shellcode 2012 Teasers writeups

http://ghostintheshellcode.com/

Thanks to the organizers for those pretty nice teasers!

The following writeups have been made by members of the FIXME team during between January 6th and January 8th.