За прошедшие дни интереса мое предложение не вызвало (семпл скачан всего 3 раза).
А зря задачка не тривиальная. Из двоих решивших, один все таки написал райтап, на что я не очень надеялся, но об этом позже.
Теперь типа моего райтапа.
Задачка как было сказано выше представляет собой исполняемый файл под Виндовс размером всего 6656 байт и состоит фактически из двух подпрограмм: основной – 213 байт (addr 401140) и обработчика VEH – 310 байт (addr 401000). Смотреть в общем не на что в век монстрообразных программ.
Не смотря на свой небольшой объем VEH обработчик фильтрует 6 типов исключений:- 0x80000003 - EXCEPTION_BREAKPOINT;
- 0x80000004 - EXCEPTION_SINGLE_STEP;
- 0xC0000005 - EXCEPTION_ACCESS_VIOLATION;
- 0xC000001D - EXCEPTION_ILLEGAL_INSTRUCTION;
- 0xC0000094 - EXCEPTION_INT_DIVIDE_BY_ZERO;
- 0xC0000096 - EXCEPTION_PRIVILEGED_INSTRUCTION.
И следовательно код основной функции должен все это генерировать.
Причесанный код обработчика представлен ниже.
Code:
ExceptionFilter proc near
ptr_ExceptionInfo= dword ptr 8
push ebp
mov ebp, esp
mov edx, [ebp+ptr_ExceptionInfo]
mov ecx, [edx]
mov ecx, [ecx+_EXCEPTION_POINTERS.ExceptionRecord]
mov eax, [edx+EXCEPTION_RECORD.ExceptionFlags]
cmp ecx, EXCEPTION_ILLEGAL_INSTRUCTION
ja short above_80000005
jz short ILLEGAL_INSTRUCTION
cmp ecx, EXCEPTION_BREAKPOINT
jz short BREAK_POINT
cmp ecx, EXCEPTION_SINGLE_STEP
jz short SINGLE_STEP
cmp ecx, EXCEPTION_ACCESS_VIOLATION
jnz EXIT
mov [eax+_CONTEXT._Eip], offset AFTER_FILTER
or eax, -1
pop ebp
retn 4
SINGLE_STEP:
mov edx, [eax+_CONTEXT._Esi]
cmp byte ptr [edx], 0
jz short SS_skip_14
add [eax+_CONTEXT._Eip], 18h ; 0x18+0x14=0x2C
SS_skip_14:
add [eax+_CONTEXT._Eip], 14h
mov SKIP_OFFSET, 0
or eax, -1
pop ebp
retn 4
BREAK_POINT:
add [eax+_CONTEXT._Eip], -1Eh
or eax, -1
pop ebp
retn 4
ILLEGAL_INSTRUCTION:
add [eax+_CONTEXT._Eip], -4Ah
or eax, -1
pop ebp
retn 4
above_80000005:
cmp ecx, EXCEPTION_INT_DIVIDE_BY_ZERO
jz short DIVIDE_ZERO
cmp ecx, EXCEPTION_PRIVILEGED_INSTRUCTION
jnz EXIT
mov ecx, eax
push esi
mov esi, [ecx+_CONTEXT._Edx]
cmp esi, [ecx+_CONTEXT._Esi]
pop esi
jz short PI_skipback_2A_xor
mov edx, ecx
mov ecx, [edx+_CONTEXT._Edx]
cmp ecx, [edx+_CONTEXT._Ebx]
jz short PI_skipback_2A_xor
mov edx, SKIP_OFFSET ; 0x00 or 0x25
add edx, -8
add [eax+_CONTEXT._Eip], edx ; -0x08 or 0x25-0x08=0x1D
mov SKIP_OFFSET, 0
or eax, -1
pop ebp
retn 4
PI_skipback_2A_xor:
add [eax+_CONTEXT._Eip], -2Ah
mov ecx, [eax+_CONTEXT._Eip]
xor dword ptr [ecx], 0B090F2DAh
mov eax, [eax+_CONTEXT._Eip]
xor dword ptr [eax+4], 25EF7A16h
mov SKIP_OFFSET, 25h
or eax, -1
pop ebp
retn 4
DIVIDE_ZERO:
mov edx, eax
mov ecx, [edx+_CONTEXT._Esi]
cmp ecx, [edx+_CONTEXT._Edx]
jnz short DZ_skipback_0C
add [eax+_CONTEXT._Eip], 4Dh ; 0x4D-0x0C=0x41
DZ_skipback_0C:
add [eax+_CONTEXT._Eip], -0Ch
EXIT:
or eax, -1
pop ebp
retn 4
ExceptionFilter endp
Фильтр в основном содержит ветвления для кода основного потока на основании анализа значений регистров, а также модификацию (xor) восьми байт кода.
Отладчики по известным причинам с таким кодом работают неохотно, поэтому остается полюбить себе моск статическим анализом, пытаясь учесть для каких команд какой адрес передается в обработчик исключения, или помочь себе, добавив в код логгер исключений.
Моск нам еще пригодится, поэтому изберем второй путь. Для размещения такого прицепа вполне подойдет конец секции. Нас будет интересовать кроме адреса исключения, код исключения и значения регистров из основного потока на основании значений которых в фильтре происходят ветвления (EBX, EDX, ESI).
Code:
ExceptionFilter proc near
ptr_ExceptionInfo= dword ptr 8
push ebp
mov ebp, esp
mov edx, [ebp+ptr_ExceptionInfo]
mov ecx, [edx]
mov ecx, [ecx+_EXCEPTION_POINTERS.ExceptionRecord]
mov eax, [edx+EXCEPTION_RECORD.ExceptionFlags]
jmp Logger
db 0C0h
BackToFilter:
ja short above_80000005
...........................................
; =========== 00401A04
Logger:
60 pusha
51 push ecx
8B 88 A0 00 00 00 mov ecx, [eax+_CONTEXT._Esi]
51 push ecx
8B 88 A4 00 00 00 mov ecx, [eax+_CONTEXT._Ebx]
51 push ecx
8B 88 A8 00 00 00 mov ecx, [eax+_CONTEXT._Edx]
51 push ecx
8B 88 B8 00 00 00 mov ecx, [eax+_CONTEXT._Eip]
51 push ecx
FF 35 3D 1A 40 00 push ds:ptrFormat
FF 15 A8 20 40 00 call ds:printf
83 C4 18 add esp, 18h
61 popa
81 F9 1D 00 00 C0 cmp ecx, EXCEPTION_ILLEGAL_INSTRUCTION
E9 D6 F5 FF FF jmp BackToFilter
ptrFormat dd offset Format
Format db 'addr = 0x%08X; edx = 0x%08X ebx = 0x%08X esi = 0x%08X exc = 0x%08X',0Ah,0
Запустив теперь нашего зверька можно получить сколь угодно длинный лог.
Code:
I will give you the flag, but it can be time-consuming...
THE FLAG IS:
addr = 0x00000000; edx = 0x7C90E514 ebx = 0x00000000 esi = 0x003428B8 exc = 0xC0000005
addr = 0x004011B9; edx = 0x00000000 ebx = 0x003428BD esi = 0x003428B8 exc = 0x80000004
addr = 0x004011D6; edx = 0x003428C2 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC000001D
addr = 0x00401198; edx = 0x003428C1 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x00401198; edx = 0x003428C0 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x00401198; edx = 0x003428BF ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x00401198; edx = 0x003428BE ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x00401198; edx = 0x003428BD ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x00401198; edx = 0x003428BC ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x00401198; edx = 0x003428BB ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x00401198; edx = 0x003428BA ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x00401198; edx = 0x003428B9 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x00401198; edx = 0x003428B8 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000094
addr = 0x004011E3; edx = 0x003428BC ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011E3; edx = 0x003428BB ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011E3; edx = 0x003428BA ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011E3; edx = 0x003428B9 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011E3; edx = 0x003428B8 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011BE; edx = 0x003428C2 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011E3; edx = 0x003428C1 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011E3; edx = 0x003428C0 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011E3; edx = 0x003428BF ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011E3; edx = 0x003428BE ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
addr = 0x004011E3; edx = 0x003428BD ebx = 0x003428BD esi = 0x003428B8 exc = 0xC0000096
……………………………………………. Зацикливание …………………………………….
addr = 0x004011B9; edx = 0x003428BD ebx = 0x003428BD esi = 0x003428B8 exc = 0x80000004
addr = 0x004011D6; edx = 0x003428C2 ebx = 0x003428BD esi = 0x003428B8 exc = 0xC000001D
В нем первые две строки вывод самой программы, а дальше выхлоп нашей добавки. В нем отсутствует информация об исключении EXCEPTION_BREAKPOINT, т.к. оно произойдет очень не скоро, и все же придется единожды сломать моск.
Имея лог можно взглянуть на основной код, начиная с первого исключения EXCEPTION_ACCESS_VIOLATION. Оно будет сгенерировано за счет того, что в качестве адреса возврата из функции SetUnhandledExceptionFilter в стек помещается ноль.
Code:
.text:00401180 68 00 10 40 00 push offset ExceptionFilter
.text:00401185 52 push edx ; return address 0x00000000
.text:00401186 FF 25 00 20 40 00 jmp ds:SetUnhandledExceptionFilter
Это единственный раз, когда точка возврата из обработчика присутствует в виде абсолютного адреса (AFTER_FILTER). На основании адресов из лога и значений относительных смещений адреса возврата из исключения можем расставить все адреса точек исключений и метки адресов возврата из обработчика.
Code:
II_skipback4A_DZ_skipback0C:
dec edx
xor ecx, ecx
cmp al, 0
jz short NO_CARRY
adc [edx], al
setz al
; 0x00401198 - address raise EXCEPTION_INT_DIVIDE_BY_ZERO
NO_CARRY:
div ecx
AFTER_FILTER:
mov ebx, 5
mov eax, ebx
lea ebx, [esi+ebx]
mov edx, 2
imul edx
lea edi, [esi+eax]
BP_skipback1E:
pushf
or dword ptr [esp], 100h ; set trace flag
popf
xor ecx, ecx
; modified code after XOR
;.text:004011B9 51 push ecx
;.text:004011BA 33 C9 xor ecx, ecx
;.text:004011BC 8B D7 mov edx, edi
; 0x004011BE - address #2 raise EXCEPTION_PRIVILEGED_INSTRUCTION
;.text:004011BE 0F 01 16 lgdt fword ptr [esi]
; 0x004011B9 - address raise EXCEPTION_SINGLE_STEP
PI_skipback2A:
mov eax, ecx
pop ecx
cmp eax, ecx
jnz short BP_skipback1E
xor eax, eax
inc dword ptr [ebp-0Ch]
adc [ebp-8], eax
adc [ebp-4], eax
nop
; 0x004011CC - address raise EXCEPTION_BREAKPOINT
int 3
SS_skip14:
mov edx, edi
xor eax, eax
inc byte ptr [edx]
setz al
; 0x004011D6 - address EXCEPTION_ILLEGAL_INSTRUCTION
db 0Fh, 3Fh, 07h
DZ_skip41:
mov edx, ebx
movzx eax, byte ptr [edx]
add ecx, eax
dec edx
cmp edx, esi
; 0x004011E3 - address #1 raise EXCEPTION_PRIVILEGED_INSTRUCTION
invd
SS_skip2C:
push esi
call ds:free
lea eax, [ebp-0Ch]
mov edx, 4
push dword ptr [eax]
add eax, edx
push dword ptr [eax]
add eax, edx
push dword ptr [eax]
push Format
call ds:printf
call ds:getchar
add esp, 20h
pop ebp
retn
Теперь можно проследить логику работы приложения и даже, вынеся все сравнения значений регистров из обработчика прерывания в основной код получить нечто представленное ниже.
Code:
.486 ; create 32 bit code
.model flat, stdcall ; 32 bit memory model
option casemap :none ; case sensitive
include \masm32\include\windows.inc ; always first
include \masm32\macros\macros.asm ; MASM support macros
; -----------------------------------------------------------------
; include files that have MASM format prototypes for function calls
; -----------------------------------------------------------------
include \masm32\include\masm32.inc
include \masm32\include\user32.inc
include \masm32\include\kernel32.inc
include \masm32\include\msvcrt.inc
; ------------------------------------------------
; Library files that have definitions for function
; exports and tested reliable prebuilt code.
; ------------------------------------------------
includelib \masm32\lib\masm32.lib
includelib \masm32\lib\user32.lib
includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\msvcrt.lib
.data
buffer db 11 dup(0)
flag dd 3 dup(0)
Caption dd 'Congratz!',0
Format db 'FLAG: %x%x%x',0Ah,0
BoxText db 100 dup(0)
.code
start:
; buffer end_flag, 10 bytes number with 2 parts (HIGH5,LOW5)
mov esi, offset buffer
mov ebx, 5
mov eax, ebx
lea ebx, [esi+ebx]
mov edx, 2
imul edx
lea edi, [esi+eax]
MAINLOOP:
xor ecx, ecx
; check end flag
cmp byte ptr [esi], 0
jnz short _EXIT
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; increment NUMBER value with carry
mov edx, edi
xor eax, eax
inc byte ptr [edx]
setz al
LOOP_CARRY:
dec edx
xor ecx, ecx
cmp al, 0
jz short NO_CARRY
adc [edx], al
setz al
NO_CARRY:
; div ecx
cmp esi,edx
jnz LOOP_CARRY
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; calc sum of hex digits in 1st part NUMBER
; ecx already 0
mov edx, ebx
LOOP_CALC1:
movzx eax, byte ptr [edx]
add ecx, eax
dec edx
cmp edx,esi
jz END_CALC1
cmp edx,ebx
jnz LOOP_CALC1
END_CALC1:
push ecx
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; calc sum of hex digits in 2nd part NUMBER
xor ecx, ecx
mov edx, edi
LOOP_CALC2:
movzx eax, byte ptr [edx]
add ecx, eax
dec edx
cmp edx,esi
jz END_CALC2
cmp edx,ebx
jnz LOOP_CALC2
END_CALC2:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; compare sum's as lucky ticket
mov eax, ecx
pop ecx
cmp eax, ecx
jnz short MAINLOOP
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; increment counter of lucky tickets
xor eax, eax
inc [flag]
adc [flag+4], eax
adc [flag+8], eax
jmp MAINLOOP
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; print value
_EXIT:
mov eax, offset flag
mov edx, 4
push dword ptr [eax]
add eax, edx
push dword ptr [eax]
add eax, edx
push dword ptr [eax]
push offset Format
push offset BoxText
call crt_sprintf
sub esp,20
invoke MessageBox, NULL, addr BoxText, addr Caption, MB_OK
exit
end start
Чтобы вообще не напрягаться, вчитываясь в ассемблерный листинг, логику работы можно представить следующим кодом на Python.
Code:
i = 0
flag = 0
while 1:
i += 1
if i & 0x100000000000000000000:
break
x0 = (i&0xFF000000000000000000)>>72
x1 = (i&0x00FF0000000000000000)>>64
x2 = (i&0x0000FF00000000000000)>>56
x3 = (i&0x000000FF000000000000)>>48
x4 = (i&0x00000000FF0000000000)>>40
x5 = (i&0x0000000000FF00000000)>>32
x6 = (i&0x000000000000FF000000)>>24
x7 = (i&0x00000000000000FF0000)>>16
x8 = (i&0x0000000000000000FF00)>>8
x9 = (i&0x000000000000000000FF)
if x0+x1+x2+x3+x4 == x5+x6+x7+x8+x9:
flag += 1
print '%x'%i, '%x'%flag
print '%x'%flag
Т.е. берется одинадцатибайтовое число и производится его инкремент, до того пока старший байт равен нулю. В ходе этого на каждой итерации сравниваются суммы старших и младших пяти байт. И если они равны, то значение в итоге являющееся флагом увеличивается на единицу. Таким образом, нам нужно посчитать количество таких равных сумм в диапазоне от 1 до 0хFFFFFFFFFFFFFFFFFFFF (80 бит).
Замечание 1: Диапазон именно с 1, т.к. инкремент идет в начале цикла и комбинация 0 = 0 не учитывается.
Замечание 2: Понятно что пока в старших пяти байтах не появятся единичные биты ни о каком равенстве сумм не может быть и речи, т.е можно начинать с числа i = 0x0000000000FFFFFFFFFF, но это никак не спасает отца русской революции и особу приближенную к императору.
На этом реверс заканчивается и начинается суровая математика.
Опознаем алгоритм (это оказалось самым трудным). Оказалось, что это старая комбинаторная задачка про «счастливый билет», ведь именно так и определяется «счастливость» - сумма трех цифр в обеих частях шестизначного билета должны совпадать. Только номер не шестизначный, а десятизначный и система счисления не десятичная, а 256-ричная. Но математика на то и математика, что ей эти отличия не важны и она перемалывает числа любой длины в любых системах счисления.
Теория решения этой задачи есть и на базе метода динамического программирования и на базе производящих функций и даже на базе интегрирования.
Несколько линков по теме:
[1] http://www.genfunc.ru/theory/lucky/
[2] http://ega-math.narod.ru/Quant/Tickets.htm
[3] http://hijos.ru/2011/11/02/chislo-sc...’-biletov/
Мой код на Python реализующий подсчет количества «счастливых билетов» на базе производящих функций представлен ниже.
Code:
import math
def factorial(n):
fac = 1
i = 0
while i < n:
i += 1
fac = fac * i
return fac
def C(k,n):
return factorial(n)/factorial(n-k)/factorial(k)
def CC(m,n,N):
if n > N/m:
lim = N/m
else:
lim = n
sum = C(n-1,n+N-1)
for k in range(1,lim+1):
sum += math.pow(-1,k)*C(k,n)*C(n-1,n+N-k*m-1)
return int(sum)
def _CC(mn,l):
return CC(mn,l,l/2*(mn-1))
Код протестирован на всех найденных примерах [2] (понятно, что для десятичной системы счисления):- для двузначных номеров C = 10,
- для четырехзначных C = 670,
- для шестизначных C = 55 252,
- для восьмизначных C = 4 816 030.
# test Lucky Ticket
Code:
print '%d'%(_CC(10,2)) # 10
print '%d'%(_CC(10,4)) # 670
print '%d'%(_CC(10,6)) # 55252
print '%d'%(_CC(10,8)) # 4816030
Первый параметр основание системы счисления, второй число цифр номера.
Внимательный читатель спросит, а вдруг ошибка кроется в учете системы счисления. Я тоже задался таким же вопросом, поэтому, укоротив число с десяти до четырех 256-ричных цифр, посчитал задачу в лоб.
Code:
i = 0x0000FFFF
flag = 0
while 1:
i += 1
if i & 0x100000000:
break
x0 = (i&0xFF000000)>>24
x1 = (i&0x00FF0000)>>16
x2 = (i&0x0000FF00)>>8
x3 = (i&0x000000FF)
if x0+x1 == x2+x3:
flag += 1
#print '%x'%i, '%x'%flag
print '%x'%flag
Получил количество 0xAAAAFF (относительно долго). Результат расчета на базе производящих функций аналогичный.
Code:
# exclude 0
print '%x'%(_CC(256,4)-1) # aaaaff
Теперь пришло время посчитать расчетное значение флага.
Code:
# correct flag for Volga2014Quals:Reverse400 - [C256(10,1275)-1]
# exclude 0
print 'FLAG: %x'%(_CC(256,10)-1) # 6e300fbb83dbe3ffff
Теперь можно вернуться к опубликованному райтапу одного из двоих решивших https://zku.github.io/CTF/ctf/revers...rsing-400.html
Что касается реверса, то вопросов нет, с математикой не понятно, но результат 6e300fbb83dbfe3900 организаторами признан верным.
ПЫСЫ: Если взять мой код и причесанный код из верного райтапа (с добавлением параметра длинны числа) и посчитать для чисел разной длины
Code:
import math
def factorial(n):
fac = 1
i = 0
while i < n:
i += 1
fac = fac * i
return fac
def C(k,n):
return factorial(n)/factorial(n-k)/factorial(k)
def CC(m,n,N):
if n > N/m:
lim = N/m
else:
lim = n
sum = C(n-1,n+N-1)
for k in range(1,lim+1):
sum += math.pow(-1,k)*C(k,n)*C(n-1,n+N-k*m-1)
return int(sum)
def _CC(mn,l):
return CC(mn,l,l/2*(mn-1))
def compute_flag_slightly_faster(n):
digitsumsPrev = [1] * 256
for i in xrange(2, n + 1):
numQs = 255 * i + 1
digitsumsNow = [0] * numQs
for q in xrange(0, numQs):
for p in xrange(0, 256):
if 0 <= q - p < numQs - 255:
digitsumsNow[q] += digitsumsPrev[q - p]
digitsumsPrev = digitsumsNow
#print '%x'%sum(map(lambda x: x * x, digitsumsPrev))
assert sum(digitsumsNow) == 256**i
return sum(map(lambda x: x * x, digitsumsPrev))
print '%x'%(_CC(256,4))
print '%x' % compute_flag_slightly_faster(2)
print '%x'%(_CC(256,6))
print '%x' % compute_flag_slightly_faster(3)
print '%x'%(_CC(256,8))
print '%x' % compute_flag_slightly_faster(4)
print '%x'%(_CC(256,10))
print '%x' % compute_flag_slightly_faster(5)
то получим
aaab00
aaab00
8ccd0ccd00
8ccd0ccd00
7ab7e45e6db700
7ab7e45e6db700
6e300fbb83dbe40000
6e300fbb83dbfe3900
т.е. на длинах 4,6,8 знаков результаты совпадают, а для длины 10 разнятся =(. И где собака порылась? Все равно если их алго и считает правильно, а не мое, то не учтено обстоятельство изложенное в замечании 1, т.е. флаг должен быть на единицу меньше. За сим тему разбора закрываю.
Ждем вас на NDH2K14 CTF Qualifications.
Volga CTF: Reverse 400
Reply With Quote
Thanks
