11 октября 2012 г.

Алгоритм SHA-1 на ассемблере.

Начнем с небольшой теории из педевикии:
(Нудным и гнусявым голосом) Алгоритм был создан в 1995 году прошлого века, насколько я понимаю в замену алгоритма MD5. По внутренней структуре алгоритм очень похоже на MD5, но имеет на мой взгляд более простую реализацию и вроде как более защищен от возникновения коллизий. Хотя в 2005 году математики из Китая придумали как провести полноценную атаку на SHA-1 причем менее чем за 2 в 69 степени операций. Что лучше, чем так называемая атака Дней рождения. За подробностями рекомендую обратиться в гугл, может в будующем я реализую алгоритм атаки Дней рождения, но сейчас поговорим как реализовать SHA-1 на ассемблере.
Понадобился мне SHA-1 для одного моего креатива, об котором я позже напишу.
Итак, простыми словами базовый алгоритм:



1. Если сообщение меньше чем 440 бит(55байт) то его необходимо дополнить до 512бит следующим образом. Добавляем в следующий за сообщением бит единицу, заполняем нулями оставшеся место до 448бита,  в последние 64 бит записываем размер сообщения которые является 64битным числом в битах.
Пример(представление в HEX(16ном) формате):
Кодируем - Bearchik

00403242  42 65 61 72 63 68 69 6B  Bearchik - само сообщение
0040324A  80 00 00 00 00 00 00 00  Ђ....... - добавляем в последний бит 1
00403252  00 00 00 00 00 00 00 00  ........ - заполняем нулями
0040325A  00 00 00 00 00 00 00 00  ........ - заполняем нулями
00403262  00 00 00 00 00 00 00 00  ........ - заполняем нулями
0040326A  00 00 00 00 00 00 00 00  ........ - заполняем нулями
00403272  00 00 00 00 00 00 00 00  ........ - заполняем нулями
0040327A  00 00 00 00 00 00 00 40  .......@ - 64 битное число, 8 символов х 8 бит
Итого: 512бит или 64байт

2. Теперь нам необходимо инвертировать эту запись, дабы привести к нормальному виду.
Получается следующее:

00403242  72 61 65 42 6B 69 68 63  raeBkihc
0040324A  00 00 00 80 00 00 00 00  ...Ђ....
00403252  00 00 00 00 00 00 00 00  ........
0040325A  00 00 00 00 00 00 00 00  ........
00403262  00 00 00 00 00 00 00 00  ........
0040326A  00 00 00 00 00 00 00 00  ........
00403272  00 00 00 00 00 00 00 00  ........
0040327A  00 00 00 00 40 00 00 00  ....@...

3. Так как SHA-1 можно представить в виде некого процессора, инициализируем 5 регистров размером в 32 бита.

H0 = 67452301h
H1 = 0EFCDAB89h
H2 = 98BADCFEh
H3 = 10325476h
H4 = 0C3D2E1F0h


4. Так как у нас 80 итераций для вычисления 32х битных данных, а данных в текущий момент всего 512бит(64байт) то необходимо дополнить сообщение до 2560бит(320байт). Делается это так:
Получившееся сообщение в пунтке 2 оставляем как есть, а сразу после него вычисляем остаток до 320бит по следующей формуле:
Определим W[0] - как указатель на начало сообщения  которое получили в пунтке 2, тогда указатель на дополненные данные выглядит как W[16], если обозначим W[t]то формула выглядит так:
W[t] = W[t-3] XOR W[t-8] XOR W[t-14] XOR W[t-16] цикличный сдвиг в лево на 1

5. Необходимо создать 4 функции(а на самом деле 3) которые будут делать некие алгоритмические действия с регистрами и добавить 4 константы:
F1(B,C,D) = (B AND C) OR ((NOT b) AND d) 
F2(B,C,D) = B XOR C XOR D
F3(B,C,D) = (B XOR C) OR (B AND D) OR (C AND D)
F4(B,C,D) = B XOR C XOR D
Константы:

K1 = 5A827999h
K2 = dd 6ED9EBA1h
K3 = 8F1BBCDCh
K4 = 0CA62C1D6h

6. Переместить 5 реальных регистров во временные, так как реальные регистры нам еще понадобятся:
A = H0
B = H1
C = H2
D = H3
E = H4

7. Необходимо замутить основной цикл кодирования, выглядит он в псевдокоде так:
for i from 0 to 80 {
     if i <= 19 {
        temp = (А сдвиг в лево на 5бит) + F1(B, C,D) + E + K1 + W[i]
     }

     if 20 <= i <= 39 {
        temp = (А сдвиг в лево на 5бит) + F2(B, C,D) + E + K1 + W[i]
     }

     if 40 <= i <= 59 {
        temp = (А сдвиг в лево на 5бит) + F3(B, C,D) + E + K1 + W[i]
     }

     if 60 <= i <= 79 {
        temp = (А сдвиг в лево на 5бит) + F4(B, C,D) + E + K1 + W[i]
     }
    E = D
    D = C
    C = B сдвиг в право на 2бита
    B = A
    A = temp



}

8. Ну вот, самое страшное позади, осталось только прибавить временные регистры к основным и SHA-1 хэш готов.
H0 += A
H1 += B
H2 += C
H3 += D
H4 += E

9. Выстраиваем их друг за другом и получаем хэш, для Bearchik он будет выглядеть так:
56 c1 d2 68 98 66 fd de f8 03 86 46 08 bd bf e4 95 6e d1 dd

А теперь самое интересное, кодъ на ассемблере.
Пункт 1, дополняем сообщение до 512бит:
nextsym:
    cmp        BYTE PTR [eax+ecx], 0 ; сравниваем равен ли байт нулю
    jz        endstr     ; если равен - строка закончилась
    inc        ecx ; увеличиваем ecx
    jmp        nextsym ; прыгаем на следующий символ
endstr:
    mov        lengh, cl ; сохраним в переменную длину сообщения
    lea        edi, mkey ; в edi поместим указатель на начало сообщения
    lea        esi, sername ; в esi поместим указатель на строчку
    rep     movsb ; копируем
    mov        BYTE PTR [edi], 80h ; добавляем битовую еденицу
    lea        eax, mkey ; в eax поместим указатель на начало сообщения
    add        eax, 3Eh ; прибавим к ниму 62 байта
    xor        ebx, ebx ; обнулим ebx
    mov        bl, lengh ; поместим в bl длину в байтах
    shl        ebx, 3h ; умножим на 8
    xchg    bl, bh ; поменяем местами регистры, так как у нас x86 процессор
    mov        WORD PTR [eax], bx ; поместим в конец сообщения длинну

lea        edi, mkey ; снова пишем в edi указатель на начало сообщения
    mov        ecx, 16 ; в нем 16 DWORD, так что в счетчик 16 итераций
revmsg:
    mov        eax,DWORD PTR [edi] ; копируем в eax содержимое под адресу в edi
    bswap    eax ; меняем все местами(работает только на 486 процах и выше)
    mov        DWORD PTR [edi], eax ; записываем обратно
    add        edi, 4h ; сдвигаем указатель на 4 байта
    loop    revmsg ; повторяем пока не закочится ecx

Пункт 2, так как у нас х86 процессор, нам нужно поменять местами все данные:
lea        edi, mkey ; снова пишем в edi указатель на начало сообщения
    mov        ecx, 16 ; в нем 16 DWORD, так что в счетчик 16 итераций
revmsg:
    mov        eax,DWORD PTR [edi] ; копируем в eax содержимое под адресу в edi
    bswap    eax ; меняем все местами(работает только на 486 процах и выше)
    mov        DWORD PTR [edi], eax ; записываем обратно
    add        edi, 4h ; сдвигаем указатель на 4 байта
    loop    revmsg ; повторяем пока не закочится ecx

Пункт 3, объявляем регистры, их нада объявлять в секции например .data
H0                dd 67452301h
H1                dd 0EFCDAB89h
H2                dd 98BADCFEh
H3                dd 10325476h
H4                dd 0C3D2E1F0h

Пункт 4, дополняем сообщение до 320байт(2560бит) по формуле:
(не забываем, после 2 пункта у нас в edi находиться указатель на 16ую позицию сообщения)
nextword:
    mov        ebx, DWORD PTR [edi-3*4h] ; копируем в ebx содержимое -3 позиции
    xor        ebx, DWORD PTR [edi-8*4h] ; ксорим с ebx содержимое -8 позиции
    xor        ebx, DWORD PTR [edi-0Eh*4h] ; ксорим с ebx содержимое -12 позиции
    xor        ebx, DWORD PTR [edi-10h*4h] ; ; ксорим с ebx содержимое -16 позиции
    rol        ebx, 1 ; получившееся сдвигаем в лево на 1 бит
    mov        DWORD PTR [edi], ebx ; записываем что получилось в текущую позицию сообщения
    add        edi, 4 ; сдвигаем указатель на 4 байта, тоесть на след позицию
    inc        ecx ; увеличиваем ecx
    .if        ecx < 80 ; пока ecx меньше 80
        jmp        nextword ; дополняем сообщение
    .endif

Пункт 5, создаем необходимые функции:
f1 proc bv:DWORD, cv:DWORD, dv:DWORD
    mov        ebx, bv ; помещаем в ebx содержимое B
    and        ebx, cv ; делаем B AND C
    mov        edx, bv ; помещаем в edx содержимое B
    not        edx ; делаем NOT B
    and     edx, dv ; делаем B AND D
    or        ebx, edx ; делаем or между двумя половинами
    ret
f1 endp

f2 proc bv:DWORD, cv:DWORD, dv:DWORD
    mov        ebx, bv ; помещаем в ebx содержимое B
    xor        ebx, cv ; делаем B XOR C
    xor        ebx, dv ; делаем XOR D с получившимся
    ret
f2 endp

f3 proc bv:DWORD, cv:DWORD, dv:DWORD
    mov        ebx, bv ; помещаем в ebx содержимое B
    and        ebx, cv ; делаем B AND C
    mov        edx, bv ; помещаем в edx содержимое B
    and        edx, dv ; делаем B AND D
    
    or        ebx, edx ; делаем or между двумя половинами
    
    mov        edx, cv ; помещаем в edx C
    and        edx, dv ; делаем C AND D
    
    or        ebx, edx ; делаем or между двумя половинами
    
    ret
f3 endp

Пункт 6, копируем регистры во временные
xor        ecx, ecx
    mov        ebx, H0
    mov        aav, ebx
    mov        ebx, H1
    mov        bbv, ebx
    mov        ebx, H2
    mov        ccv, ebx
    mov        ebx, H3
    mov        ddv, ebx
    mov        ebx, H4
    mov        eev, ebx

Пункт 7, основной цикл кодирования:
mainloop:
    cmp        ecx, 14h ; t больше или равно 20?
    jge        nf2 ; если да, то прыгаем на на обработку 2

    invoke    f1, bbv, ccv, ddv ; вычисляем по 1 функции значение
    mov        eax, K1 ; копируем в eax ключевое значение K1
    mov        k, eax ; перемещаем во временную переменную K1
    jmp        ef ; прыгаем на последующую обработку
nf2:
    cmp        ecx, 28h ; t больше или равно 40?
    jge        nf3 ; если да, то прыгаем на на обработку 3
    invoke    f2, bbv, ccv, ddv ; вычисляем по 2 функции значение
    mov        eax, K2 ; копируем в eax ключевое значение K2
    mov        k, eax ; перемещаем во временную переменную K2
    jmp        ef ; прыгаем на последующую обработку
nf3:
    cmp        ecx, 3Ch ; t больше или равно 60?
    jge        nf4 ; если да, то прыгаем на на обработку 4
    invoke    f3, bbv, ccv, ddv ; вычисляем по 3 функции значение
    mov        eax, K3 ; копируем в eax ключевое значение K3
    mov        k, eax ; перемещаем во временную переменную K3
    jmp        ef ; прыгаем на последующую обработку
nf4:
    invoke    f2, bbv, ccv, ddv ; вычисляем по 2 функции значение
    mov        eax, K4 ; копируем в eax ключевое значение K4
    mov        k, eax ; перемещаем во временную переменную K4
ef:
    lea        edi, mkey ; копируем указатель на сообщение в edi
    xor        eax, eax ; обнулим eax
    mov        eax, aav ; в eax помещаем A
    rol        eax, 5 ; делаем цикличный сдвиг на 5 в лево
    add        eax, ebx ; прибавляем к вычисленному регистру в функциях
    add        eax, eev ; прибавляем E
    add        eax, k ; прибавляем константу K
    add        eax, DWORD PTR [edi+ecx*4] ; прибавляем то что в текущей позиции i
    mov        temp, eax ;  в темп помещаем что получилось
    
    mov        eax, ddv ; в eax помещаем D
    mov        eev, eax ; в E помещаем D
    
    mov        eax, ccv ; в eax помещаем С
    mov        ddv, eax ; в D помещаем С
    
    mov        eax, bbv ; в eax помещаем B
    ror        eax, 2   ; делаем цикличный сдвиг в право на 2
    mov        ccv, eax ; в С помещаем что получилось
    
    mov        eax, aav ; в eax помещаем A
    mov        bbv, eax ; в B помещаем A
    
    mov        eax, temp ; в eax помещаем temp
    mov        aav, eax ; в A помещаем temp

    inc        ecx ; увеличиваем ecx на 1
    .if        ecx == 80 ; если достигнули 80
        jmp        exitmainloop ; кодирование закончено - выходим
    .endif
    jmp        mainloop
exitmainloop:

Пункт 8, прибавляем к эталонным регистрам то что получилось в A,B,C,D,E:
mov        eax, H0 ; в eax H0
    add        eax, aav ; прибавляем A
    mov        H0, eax ; копируем обратно в H0
    
    mov        eax, H1 ; в eax H1
    add        eax, bbv ; прибавляем B
    mov        H1, eax ; копируем обратно в H1
    
    mov        eax, H2 ; в eax H2
    add        eax, ccv ; прибавляем C
    mov        H2, eax ; копируем обратно в H2
    
    mov        eax, H3 ; в eax H3
    add        eax, ddv ; прибавляем D
    mov        H3, eax ; копируем обратно в H3
    
    mov        eax, H4 ; в eax H4
    add        eax, eev ; прибавляем E
    mov        H4, eax ; копируем обратно в H4

Ну вот в принципе и все, в принципе не очень сложно.

2 комментария:

  1. Наткнулся на этот блог случайно. Хочу выразить большую благодарность его автору. Афтар писши есчо! Хотелось бы спросить, не будет ли разбора SHA-256 под асм?

    ОтветитьУдалить
  2. Да в принципе там все тоже самое что в SHA-1, вид только с боку, ну если время будет на следующей неделе напишу алгоритм, там в принципе ничего сложного. А дальше по плану у меня был SHA-3 он же Keccak, но там очень сильно заточенно под 64 разряда и меня под 32 бита лень пока одолевает написать алгоритм. Не люблю длинную математику, больно оно медленное. :)

    ОтветитьУдалить