(Нудным и гнусявым голосом) Алгоритм был создан в 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
Ну вот в принципе и все, в принципе не очень сложно.
Наткнулся на этот блог случайно. Хочу выразить большую благодарность его автору. Афтар писши есчо! Хотелось бы спросить, не будет ли разбора SHA-256 под асм?
ОтветитьУдалитьДа в принципе там все тоже самое что в SHA-1, вид только с боку, ну если время будет на следующей неделе напишу алгоритм, там в принципе ничего сложного. А дальше по плану у меня был SHA-3 он же Keccak, но там очень сильно заточенно под 64 разряда и меня под 32 бита лень пока одолевает написать алгоритм. Не люблю длинную математику, больно оно медленное. :)
ОтветитьУдалить