Tags: math reversing keygen
Rating:
# Day 10 - ChristmaSSE KeyGen - rev, math
> I ran this program but it never finished... maybe my computer is too slow. Maybe yours is faster?
Download: [reverse_ctf.out](https://advent2019.s3.amazonaws.com/326c15f8884fcc13d18a60e2fb933b0e35060efa8a44214e06d589e4e235fe34)
Mirror: [reverse_ctf.out](./reverse_ctf.out)
Inizialmente non avevo letto che la challenge fosse math e quindi ho subito pensato ad un ottimizzazione del codice. Ho iniziato a riscriverlo in python cachando le varie operazioni. Ottendendo cosi le 3 operazioni fondamentali che vengono utilizzate all'interno del \<main\>:
```
@cached(cache={})
def pshufd(src,order):
line=bin(src)[2:].rjust(128,"0")
n=32
src=[line[i:i+n] for i in range(0, len(line), n)][::-1]
#print(src)
line=bin(order)[2:].rjust(8,"0")
n=2
order=[line[i:i+n] for i in range(0, len(line), n)]
#print(order)
res=""
for i in order:
val=int(i,2)
res+=src[val]
#print(int(res,2))
return int(res,2)
@cached(cache={})
def pmulld(val1,val2):
line=bin(val1)[2:]
line=line.rjust(128,"0")
n=32
val1=[line[i:i+n] for i in range(0, len(line), n)]
line=bin(val2)[2:].rjust(128,"0")
n=32
val2=[line[i:i+n] for i in range(0, len(line), n)]
#print(val1,val2)
res=""
for i,j in zip(val1,val2):
res+=str(int(i,2)*int(j,2)).rjust(32,"0")
return int(res,16)
@cached(cache={})
def paddd(val1,val2):
line=bin(val1)[2:]
line=line.rjust(128,"0")
n=32
val1=[line[i:i+n] for i in range(0, len(line), n)]
line=bin(val2)[2:].rjust(128,"0")
n=32
val2=[line[i:i+n] for i in range(0, len(line), n)]
#print(val1,val2)
res=""
for i,j in zip(val1,val2):
res+=str(int(i,2)+int(j,2)).rjust(32,"0")
return int(res,16)
```
Successivamente ho individuato che le funzioni venivano sempre chiamate con una sequenza ben precisa, quindi le ho rese delle funzioni:
```
@cached(cache={})
def m_fun(s1, s2, s3):
m = pmulld(s1, s2)
m = paddd(m, s3)
return m
@cached(cache={})
def fun(s1, s2, s3, s4):
m = m_fun(s1, s2, s3)
m = paddd(m, s4)
return m
```
Ho copiato i dati 80 byte di dati in reverse_data.
Ricostruendo il main:
```
def main():
start_time = time.time()
data = open('reverse_data', 'rb').read()
res = int.from_bytes(data[64:80], byteorder='little')
i0 = pshufd(res, 0x15)
i1 = pshufd(res, 0x45)
i2 = pshufd(res, 0x51)
i3 = pshufd(res, 0x54)
# i = [
# [0, 0, 0, 1],
# [0, 0, 1, 0],
# [0, 1, 0, 0],
# [1, 0, 0, 0]
# ]
counter = 0x112210f47de98115
rax = 0
d9 = int.from_bytes(data[:16], byteorder='little')
d10 = int.from_bytes(data[16:32], byteorder='little')
d13 = int.from_bytes(data[32:48], byteorder='little')
d15 = int.from_bytes(data[48:64], byteorder='little')
s00 = pshufd(d9, 0)
s01 = pshufd(d9, 0x55)
sss5= pshufd(d9, 0xaa)
s03 = pshufd(d9, 0xff)
s10 = pshufd(d10, 0)
s5 = pshufd(d10, 0x55)
s12 = pshufd(d10, 0xaa)
s13 = pshufd(d10, 0xff)
s20 = pshufd(d13, 0)
s21 = pshufd(d13, 0x55)
s22 = pshufd (d13, 0xaa)
s23 = pshufd(d13, 0xff)
s30 = pshufd(d15, 0)
s31 = pshufd(d15, 0x55)
s32 = pshufd(d15, 0xaa)
s33 = pshufd(d15, 0xff)
print(hex(s00 ), hex(s01), hex(sss5), hex(s03 ))
print(hex(s10 ), hex(s5 ), hex(s12), hex(s13 ))
print(hex(s20), hex(s21 ), hex(s22 ), hex(s23))
print(hex(s30), hex(s31 ), hex(s32 ), hex(s33))
#
# A1 = [[16,15,14,13],
# [12,11,10, 9],
# [8 , 7, 6, 5],
# [4 , 3, 2, 1]]
sres = int.from_bytes(data[72:76], byteorder='little')
while(rax != counter):
# prima colonna
m6 = pmulld(s00, i3)
m8 = pmulld(s10, i3)
m11 = pmulld(s20, i3)
m14 = pmulld(s30, i3)
#--------------------
m12 = m_fun(s01, i2, m6) #xmm12s * xmm2 * xmm6 = xmm12
m5 = pmulld(s11, i1) #xmm5s *xmm1 = xmm5
i3 = fun(s03, i0, m5, m12)
print(hex(i3))
exit(0)
mm5 = m_fun(s11, i2, m8)
m7 = m_fun(s21, i2, s20)
mm6 = pmulld(s12, i1) #64c
i2 = fun(s13, i0, mm6, mm5) #662
mmm5 = pmulld(s22, i1)
mmm6 = pmulld(s32, i1) #680
i1 = fun(s23, i0, mmm5, m7)
m4 = m_fun(s31, i2, m14)
i0 = fun(s33, i0, mmm6, m4)
#var ciclo interno
m4 = pshufd(sres, 0xaa)
m5 = pshufd(i0, 0)
edx = 0x3e8
#internalCycle() ignoring overflow internal cycle
rax += 1
if rax % 10000000 == 0: #print time to execute 10.000.000 cycles
print(time.time()-start_time) #150 seconds every 10.000.000 cycles... mmm... wrong way
```
Dopo aver perso qualche ora cercando di risolverlo nel modo sbagliato, ho realizzato che la challenge era MATH!!!
Ho analizzato come veniva modificata la matrice alla fine di ogni ciclo, ed era una semplice moltiplicazione:
```
A1 = [[16,15,14,13],
[12,11,10, 9],
[8 , 7, 6, 5],
[4 , 3, 2, 1]]
A2 = A*A = [[600 542 484 426]
[440 398 356 314]
[280 254 228 202]
[120 110 100 90]]
```
A questo punto ho cercato il numero di volte che doveva essere eseguito (fibonacci)
```
def calculate_exponentiation():
res = []
s = 1234567890123456789
i=0
while(s>0):
if 2**i > s:
res.append(i-1)
s -= 2**(i-1)
i=0
else:
i+=1
return res
```
Ho trovato che il ciclo interno serviva a gestire l'overflow:
```
def overflow(a):
sres = 0x96433d
for x in range(4):
for y in range(4):
while a[x][y] > sres:
a[x][y] %= sres
return a
```
Infine ho emulato la risoluzione della flag:
```
def emulation(tot):
BASE = 0x400000
STACK = 0x7ffcaf000000
FLAG = 0x00600000
mu = Uc(UC_ARCH_X86, UC_MODE_64)
mu.mem_map(BASE, 1024*4)
mu.mem_map(STACK, 1024*4)
mu.mem_map(FLAG, 1024*1024)
code = struct.pack ("69B", *[
0x66,0x0f,0x7f,0x1c,0x24,0x66,0x0f,0x7f,0x54,0x24,0x10,
0x66,0x0f,0x7f,0x4c,0x24,0x20,0x66,0x0f,0x7f,0x44,0x24,
0x30,0x31,0xc0,0x66,0x2e,0x0f,0x1f,0x84,0x00,0x00,0x00,
0x00,0x00,0x0f,0x1f,0x00,0x0f,0xb6,0x0c,0x44,0x30,0x88,
0x90,0x10,0x60,0x00,0x0f,0xb6,0x4c,0x44,0x01,0x30,0x88,
0x91,0x10,0x60,0x00,0x48,0x83,0xc0,0x02,0x48,0x83,0xf8,
0x20,0x75,0xe1])
flag = struct.pack ("40B", *[
0xfc,0x14,0xeb,0x09,0xbc,0xae,0xe7,0x47,0x4f,0xe3,0x7c,
0xc1,0x52,0xa5,0x02,0x8e,0x89,0x71,0xc8,0x8d,0x96,0x23,
0x01,0x6d,0x71,0x40,0x5a,0xea,0xfd,0x46,0x1d,0x23,0x00,
0x00,0x00,0x00,0x00,0x00,0x00,0x00])
mu.reg_write(UC_X86_REG_RSP, STACK)
mu.reg_write(UC_X86_REG_XMM0, (tot[0][0]<<96) + (tot[0][1]<<64) + (tot[0][2]<<32) + (tot[0][3]))
mu.reg_write(UC_X86_REG_XMM1, (tot[1][0]<<96) + (tot[1][1]<<64) + (tot[1][2]<<32) + (tot[1][3]))
mu.reg_write(UC_X86_REG_XMM2, (tot[2][0]<<96) + (tot[2][1]<<64) + (tot[2][2]<<32) + (tot[2][3]))
mu.reg_write(UC_X86_REG_XMM3, (tot[3][0]<<96) + (tot[3][1]<<64) + (tot[3][2]<<32) + (tot[3][3]))
mu.mem_write(FLAG+0x1090, flag)
mu.mem_write(BASE, code)
mu.emu_start(BASE, BASE + len(code), 2 * UC_SECOND_SCALE)
print(mu.mem_read(FLAG+0x1090, 0x20))
```
