R0 CREW

Volga CTF: Reverse 400

За прошедшие дни интереса мое предложение не вызвало (семпл скачан всего 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.

И следовательно код основной функции должен все это генерировать.

Причесанный код обработчика представлен ниже.

 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).

 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

Запустив теперь нашего зверька можно получить сколь угодно длинный лог.

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 в стек помещается ноль.

.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). На основании адресов из лога и значений относительных смещений адреса возврата из исключения можем расставить все адреса точек исключений и метки адресов возврата из обработчика.

 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 

Теперь можно проследить логику работы приложения и даже, вынеся все сравнения значений регистров из обработчика прерывания в основной код получить нечто представленное ниже.

    .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.

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-schastlivyx’’-biletov/

Мой код на Python реализующий подсчет количества «счастливых билетов» на базе производящих функций представлен ниже.

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

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-ричных цифр, посчитал задачу в лоб.

 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 (относительно долго). Результат расчета на базе производящих функций аналогичный.

# exclude 0
print '%x'%(_CC(256,4)-1) # aaaaff

Теперь пришло время посчитать расчетное значение флага.

# correct flag for Volga2014Quals:Reverse400 - [C256(10,1275)-1]
# exclude 0
print 'FLAG: %x'%(_CC(256,10)-1) # [B]6e300fbb83dbe3[/B]ffff

Теперь можно вернуться к опубликованному райтапу одного из двоих решивших https://zku.github.io/CTF/ctf/reversing/2014/03/31/volgactf-quals-2014-reversing-400.html

Что касается реверса, то вопросов нет, с математикой не понятно, но результат 6e300fbb83dbfe3900 организаторами признан верным.

ПЫСЫ: Если взять мой код и причесанный код из верного райтапа (с добавлением параметра длинны числа) и посчитать для чисел разной длины

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.