Реализация ENRUPT и RC4 на фасме -)

UbIvItS
Пока слабая, но попытка. Есть только 3 вида атак: статистические (linear, differential, X^2, slide, boomerang и т.д.), структурные (guess and determine) и алгебраические (linearization, SAT solvers и т.д.).

Luby & Rackoff показали как делать шифры на базе независимых (неотличимо разных) PRF, которые доказуемо не ломаются статистическими методами. К счастью, в их доказательстве PRF - это функции неотличимые от случайных "достаточно легко" или "в полиномиальное время". Они для примера привели O(n^3), хотя в более поздних работах это было расширено другими авторами до "местно-случайных" функций, неотличимых по какому-то небольшому количеству переменных, не сравнимому с размером ключа. Поэтому построив такие PRF, можно доказать что статистические методы работать не будут после нескольких итераций таких функций в определённой структуре типа Feistel Network.

При этом [обычно поточный] шифр может иметь уязвимую структуру, благодаря которой можно угадывать и решать/вычислять (или угадывать и ломать статистическими или алгебраическими методами), но от этого легче всего защититься и доказать бесполезность угадывания.

А вот с алгебраическими атаками сложно... Они совсем ещё не развиты и ещё долго будет трудно не то что доказать неломаемость любого заданного шифра, а хотя бы даже одним методом каким-то от них *доказуемо* защитить в общем случае. Так что тут уж извиняйте. Могу только один аргумент привести – всем алгебраическим атакам требуется разрозненная полиномиальная структура, а определение PRF само по себе требует случайной 50%-плотной структуры полиномов уже даже после 1/4 кругов в шифре. Так что скорее всего Luby-Rackoff шифры неуязвимы и к алгебраическим атакам в общем случае, но это пока не доказано, опереться дизайнеру не на что.

 

Побаловался чуть с реализацией.
Получилось обогнать unrolled C на (правка) 13%
Тоже на С.
Идея вот в чем:
Возьмем:

Код (Text):

1. #define enRUPTc(r,x,xw,key,kw) x[r%xw]^=_lrotr(2*x[(r-1)%xw]^x[(r+1)%xw]^key[r%kw]^r,8)*9^key[r%kw]

Видим что key[r%kw] берется два раза, причем первый раз он ксорится с номером шага.
Теперь делаем отдельную табличку, которая инициализируется один раз, что то типа:

Код (Text):

1. #define ktw 64
2. ...
3. for (int i = 0; i < ktw; ++i)
4.     kt[i] = key[i % kw] ^ i;

И переделываем алгоритм в:
#define enRUPTc(r,x,xw,key,kw) x[r%xw]^=_lrotr(2*x[(r-1)%xw]^x[(r+1)%xw] ^ kt[r % ktw]^(r & ~(ktw-1)) ,8)*9^key[r%kw]

Т.е. мы делаем xor с табличным значением, а (r & ~(ktw-1)) нужно для получения маски старших бит, если количество шагов больше ktw. Если шагов меньше ktw, то оптимизатор ее выкинет (ибо там 0).

Результат (мое - enRUPTfa):

Код (Text):

1. AES      116004.950735 kbps [4e5bfeae 880aebe9 73534999 86e318bb]
2. AESu     120916.872072 kbps [4e5bfeae 880aebe9 73534999 86e318bb]
3. enRUPT   62253.120594 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
4. enRUPTu  98762.125092 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
5. enRUPTfa  111569.183707 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
6. Speed compare:
7. 1.000 1.042 0.537 0.851 0.962
8. 0.959 1.000 0.515 0.817 0.923
9. 1.863 1.942 1.000 1.586 1.792
10. 1.175 1.224 0.630 1.000 1.130
11. 1.040 1.084 0.558 0.885 1.000

Есть еще вариант переписать шаг на асме, но у меня не получилось выиграть больше 0.5% от С варианта. Но на всякий случай привожу, вдруг кто чего придумает:

Код (Text):

1. #define ruptX(a)    ((a) % xw) * 4
2. #define ruptK(a)    ((a) % kw) * 4
3.  
4. #define enRUPTc(r,x,xw,key,kw) \
5. {\
6.     _asm    add eax, eax\
7.     _asm    xor eax, [esi][ruptX(r + 1)]\
8.     _asm    xor eax, [ecx][r * 4]\
9.     _asm    ror eax, 8\
10.     \
11.     _asm    lea eax, [eax * 8 + eax]\
12.     _asm    xor eax, [edi][ruptK(r)]\
13.     \
14.     _asm    xor eax, [esi][ruptX(r)]\
15.     _asm    mov [esi][ruptX(r)], eax\
16. }

И проинициализировать все перед развернутым циклом:

Код (Text):

1.     _asm
2.     {
3.         mov esi, [x]
4.         mov edi, [key]
5.         lea ecx, [kt]
6.  
7.         mov eax, [esi][ruptX(0)]
8.     }

Т.е.:
esi = смещение на x
edi = смещение на key
ecx = смещение на kt
eax содержит x[(r-1) % xw] и используется на каждом следующем шаге.
Кроме того, asm вариант не учитывает что количество шагов может быть больше ktw.

Я взял за основу прогу написанную неким akkort, сорцы которой лежат тут: http://81.30.182.45/aesenrupt.cpp

Кстати, я не согласен с тем, что в проге все циклы шифрования __forceinline'd - если они как функции дергаются (не inline), картина совсеем другая:

Код (Text):

1. AES      110104.780968 kbps [4e5bfeae 880aebe9 73534999 86e318bb]
2. AESu     86816.124191 kbps [4e5bfeae 880aebe9 73534999 86e318bb]
3. enRUPT   58431.749238 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
4. enRUPTu  84254.694288 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
5. enRUPTfa  110104.780968 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
6. Speed compare:
7. 1.000 0.788 0.531 0.765 1.000
8. 1.268 1.000 0.673 0.970 1.268
9. 1.884 1.486 1.000 1.442 1.884
10. 1.307 1.030 0.694 1.000 1.307
11. 1.000 0.788 0.531 0.765 1.000

Правда не понимаю чего AESu оказался медленнее AES..

Кроме того, проблема __forceinline - меняя порядок алгоритмов, меняется и скорость их исполнения (+-10%). Так что, imho, правильно без __forceinline замерять.

 

Ruptor

насколько я понимаю, в криптографии есть две энтропии: энтропия связки (ключ + сифер) и "текста" - выходной шифр обладает большей из двух энтропий. в общем мне не совсем ясно, что значит:

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

 

Отличная идея!

 

Joes
Для 4x4 можно вообще весь блок в регистрах держать:

Код (Text):

1. #define enRUPTa(a,b,c,r) \
2.     __asm { lea esi,[a*2] }\
3.     __asm { xor esi,c }\
4.     __asm { xor esi,[edi+r*8] }\
5.     __asm { ror esi,8 }\
6.     __asm { lea esi,[esi*8+esi] }\
7.     __asm { xor esi,[edi+r*8+4] }\
8.     __asm { xor b,esi }
9.  
10. {
11.     __asm { mov esi,[x] }
12.     __asm { mov edi,[kt] }
13.     __asm { mov eax,[esi   ] }
14.     __asm { mov ebx,[esi+ 4] }
15.     __asm { mov ecx,[esi+ 8] }
16.     __asm { mov edx,[esi+12] }
17.     enRUPTa(eax,ebx,ecx, 0); enRUPTa(ebx,ecx,edx, 1); enRUPTa(ecx,edx,eax, 2); enRUPTa(edx,eax,ebx, 3);
18.     enRUPTa(eax,ebx,ecx, 4); enRUPTa(ebx,ecx,edx, 5); enRUPTa(ecx,edx,eax, 6); enRUPTa(edx,eax,ebx, 7);
19.     enRUPTa(eax,ebx,ecx, 8); enRUPTa(ebx,ecx,edx, 9); enRUPTa(ecx,edx,eax,10); enRUPTa(edx,eax,ebx,11);
20.     enRUPTa(eax,ebx,ecx,12); enRUPTa(ebx,ecx,edx,13); enRUPTa(ecx,edx,eax,14); enRUPTa(edx,eax,ebx,15);
21.     enRUPTa(eax,ebx,ecx,16); enRUPTa(ebx,ecx,edx,17); enRUPTa(ecx,edx,eax,18); enRUPTa(edx,eax,ebx,19);
22.     enRUPTa(eax,ebx,ecx,20); enRUPTa(ebx,ecx,edx,21); enRUPTa(ecx,edx,eax,22); enRUPTa(edx,eax,ebx,23);
23.     enRUPTa(eax,ebx,ecx,24); enRUPTa(ebx,ecx,edx,25); enRUPTa(ecx,edx,eax,26); enRUPTa(edx,eax,ebx,27);
24.     enRUPTa(eax,ebx,ecx,28); enRUPTa(ebx,ecx,edx,29); enRUPTa(ecx,edx,eax,30); enRUPTa(edx,eax,ebx,31);
25.     enRUPTa(eax,ebx,ecx,32); enRUPTa(ebx,ecx,edx,33); enRUPTa(ecx,edx,eax,34); enRUPTa(edx,eax,ebx,35);
26.     enRUPTa(eax,ebx,ecx,36); enRUPTa(ebx,ecx,edx,37); enRUPTa(ecx,edx,eax,38); enRUPTa(edx,eax,ebx,39);
27.     enRUPTa(eax,ebx,ecx,40); enRUPTa(ebx,ecx,edx,41); enRUPTa(ecx,edx,eax,42); enRUPTa(edx,eax,ebx,43);
28.     enRUPTa(eax,ebx,ecx,44); enRUPTa(ebx,ecx,edx,45); enRUPTa(ecx,edx,eax,46); enRUPTa(edx,eax,ebx,47);
29.     __asm { mov esi,[x] }
30.     __asm { mov [esi   ],eax }
31.     __asm { mov [esi+ 4],ebx }
32.     __asm { mov [esi+ 8],ecx }
33.     __asm { mov [esi+12],edx }
34. }

Только проинициализировать kt чередуя {k[r%kw]+r,k[r%kw],...}.

Я не знаю на много ли это быстрее, не мерял ещё...

 

Я старался быструю общую реализацию сделать.
Сейчас поковыряю 128-x (ключ 128 бит).

 

Померял.

Чистый С на 50% медленнее, чем самый быстрый AES (24 такта на байт по сравнению с 16.25 AES), вышеуказанный ассемблер - 21 такт на байт, а вот эта функция:

#define enRUPTa(a,b,c,r) \
__asm { mov esi,c }\
__asm { xor esi,r+1 }\
__asm { lea ebp,[a*2] }\
__asm { xor esi,[edi+(r%4)*4] }\
__asm { xor b,[edi+(r%4)*4] }\
__asm { xor esi,ebp }\
__asm { ror esi,8 }\
__asm { lea esi,[esi*8+esi] }\
__asm { xor b,esi }

16.25 тактов на байт как и AES, если её заменить в вышеуказанном коде, только в edi должен быть указатель на сам ключ и ebp надо сохранять. Таблицу заранее считать получается медленнее.

 

Сейчас все свелось к написанию кода для известного размера ключа? Так?

 

Дык, чистый С работает для любых ключей, а у тебя - только для 128 битных.
Потому да, такой вариант будет быстрее.

Ничего, я тоже поковыряю оптимизированную 128-битную имплементацию

 

Joes
AES тоже работает только для 128-битовых ключей и 128-битовых блоков. Не надо же сравнивать яблоки с апельсинами... Мы даже key setup не считаем, а тоже ведь надо. Пакеты часто совсем маленькие бывают. Но для AES это будет не честно – он тогда совсем медленный окажется.

KeSqueer
Вообще-то так задача не стояла. Я даже не знаю как задача стоит. Они у всех разные. Кому-то надо гибкость, а кому-то и 128-битовых блоков и ключей хватает. Но раз начали сравнивать с AES-128 по скорости, то почему бы и не сравнить на сколько быстро его можно сделать для такого же размера? Я слышал что enRUPT-128-128-CTR в SSE в 2 раза быстрее, чем AES-128-CTR...

 

Ага, понял про 128 битность. В таком ключе - согласен, неправильно сравнивать общий алгоритм и специализированную версию.

Ruptor:
Твой последний асм вариант у меня, почему то, дает не правильные результаты (быстро, но не совпадает результат с reference implementation).

 

Так, получилось заоптимайзить еще. Теперь на асме. Вариант x-128 (128 данные):

Код (Text):

1. #define fastRUPTa2(r, x0, x1, x2) \
2. {\
3.     _asm    mov ebp, x2\
4.     _asm    lea eax, [x0 * 2]\
5.     \
6.     _asm    xor ebp, (r)\
7.     _asm    xor x1,  [esi][ruptK(r)]\
8.     \
9.     _asm    xor ebp, [esi][ruptK(r)]\
10.     _asm    xor eax, ebp\
11.     \
12.     _asm    ror eax, 8\
13.     _asm    lea eax, [eax*8 + eax]\
14.     _asm    xor x1, eax\
15. }
16.  
17. #define fastRUPTa2Round(r)\
18.     fastRUPTa2(r + 0, ecx, edx, ebx)\
19.     fastRUPTa2(r + 1, edx, ebx, edi)\
20.     fastRUPTa2(r + 2, ebx, edi, ecx)\
21.     fastRUPTa2(r + 3, edi, ecx, edx)
22.  
23. void INLINE FastRupta2(DWORD *x, DWORD *key)
24. {
25.     _asm
26.     {
27.         mov esi, [x]
28.         mov ecx, [esi][0x0]
29.         mov edx, [esi][0x4]
30.         mov ebx, [esi][0x8]
31.         mov edi, [esi][0xC]
32.         mov esi, [key]
33.         push ebp
34.     }
35.  
36.     fastRUPTa2Round(1 + 0 );
37.     fastRUPTa2Round(1 + 4 );
38.     fastRUPTa2Round(1 + 8 );
39.     fastRUPTa2Round(1 + 12);
40.     fastRUPTa2Round(1 + 16);
41.     fastRUPTa2Round(1 + 20);
42.     fastRUPTa2Round(1 + 24);
43.     fastRUPTa2Round(1 + 28);
44.     fastRUPTa2Round(1 + 32);
45.     fastRUPTa2Round(1 + 36);
46.     fastRUPTa2Round(1 + 40);
47.     fastRUPTa2Round(1 + 44);
48.  
49.     _asm
50.     {
51.         pop ebp
52.         mov esi, [x]
53.         mov [esi][0x0], ecx
54.         mov [esi][0x4], edx
55.         mov [esi][0x8], ebx
56.         mov [esi][0xC], edi
57.     }
58. }

Идея похожа на Ruptor'овскую, разве что код отдебажен и чуть изменен. ebp, к сожалению, меняется.

Результат (назвал enRUPT2):

Код (Text):

1. AES      114520.245734 kbps [4e5bfeae 880aebe9 73534999 86e318bb]
2. AESu     121025.904418 kbps [4e5bfeae 880aebe9 73534999 86e318bb]
3. enRUPT2   143241.972252 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
4. enRUPTu  98762.125092 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
5. enRUPTfa  111569.183707 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
6. Speed compare:
7. 1.000 1.057 1.251 0.862 0.974
8. 0.946 1.000 1.184 0.816 0.922
9. 0.799 0.845 1.000 0.689 0.779
10. 1.160 1.225 1.450 1.000 1.130
11. 1.026 1.085 1.284 0.885 1.000

enRUPTfa остался прежним - табличный unrolled C вариант.

 

Joes

Я честно говоря даже не рассчитывал AES по скорости обогнать никакими оптимизациями... А тут 20%.

/me почёсывая голову

Это Core 2 Duo? Какой у тебя компилятор?

 

Если кому интересно, переделал первоначальный вариант без div'ов. Вариант для ключей и текста любой длины

Код (Text):

1. Enrupt:
2.     virtual at esp
3.         .next   dd ?
4.         .maxlen dd ?
5.         rd      1+4
6.         .x      dd ?
7.         .xw     dd ?
8.         .k      dd ?
9.         .kw     dd ?
10.     end virtual
11.  
12.         push    ebp ebx esi edi
13.         push    ecx ecx
14.         mov     eax, [.xw]
15.         mov     ecx, [.kw]
16.         lea     eax, [ecx+eax*2]
17.         xor     edi, edi
18.         shl     eax, 2
19.         jz      .exit
20.         inc     edi
21.         mov     [.maxlen], eax
22.         xor     ebx, ebx
23.         mov     esi, [.x]
24.         xor     ecx, ecx
25.         xor     eax, eax
26.         cmp     [.kw], 2
27.         sbb     eax, -1
28.         mov     [.next], eax
29.  
30.     .xloop:
31.         inc     ecx
32.         cmp     ecx, [.kw]
33.         mov     edx, [.k]
34.         sbb     ebp, ebp
35.         and     ecx, ebp
36.         mov     edx, [edx+ecx*4]
37.         mov     eax, [esi+ebx*4]
38.         add     eax, eax
39.  
40.         mov     ebx, [.next]
41.         xor     eax, edx
42.         inc     ebx
43.         cmp     ebx, [.xw]
44.         sbb     ebp, ebp
45.         and     ebx, ebp
46.         xor     eax, [esi+ebx*4]
47.         xchg    [.next], ebx
48.  
49.         xor     eax, edi
50.         ror     eax, 8
51.         lea     eax, [eax*8+eax]
52.         xor     eax, edx
53.         xor     [esi+ebx*4], eax
54.  
55.         inc     edi
56.         cmp     edi, [.maxlen]
57.         jbe     .xloop
58.     .exit:
59.         pop     ecx ecx
60.         pop     edi esi ebx ebp
61.         retn    4*4

Если кому не лень, проверьте, плз на скорость, но прийдется переделать немного. Интересно на сколько отстает

 

Ruptor:
Да, Core 2 Duo.
Компилятор - MSVC 2005.

 

Joes
Тогда уж уменьшим обращение к памяти в 2 раза:

Код (Text):

1. mov ebp, [esi][ruptK(r)]
2. lea eax, [x0*2]
3. xor x1, ebp
4. xor ebp, r
5. xor ebp, x2
6. xor eax, ebp
7. ror eax, 8
8. lea eax, [eax*8+eax]
9. xor x1, eax

 

KeSqueer
Так получается медленнее. Это не лишнее обращение к памяти. Ячейка та-же, читается прямо из cache без задержек, зато спасает от pipe stall. Проверь.

Joes
Говорят с Intel Compiler AES немного быстрее получается и если память очень быстрая, то может и до 15.43 тактов на байт разогнаться – на 5% быстрее чем enRUPT, который от скорости памяти почти не зависит.

 

KeSqueer: Твой вариант еще быстрее. Там еще не только в чтении из памяти фишка, а в том как оно смогло распралелить код. Я еще попереставляю комманды, может получится чуть чуть еще выжать. Но, все равно, 1.5 раза от unrolled C это неплохо.
Я думаю тут еще от архитектуры процессора зависит. Вобщем, у меня на 5% быстрее от двойного чтения..

Код (Text):

1. AES      117631.663453 kbps [4e5bfeae 880aebe9 73534999 86e318bb]
2. AESu     122797.555352 kbps [4e5bfeae 880aebe9 73534999 86e318bb]
3. enRUPT2   150637.180696 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
4. enRUPTu  99864.380952 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
5. enRUPTfa  113073.064869 kbps [fcb74c06 ae5210d6 2f09b883 c700fd99]
6. Speed compare:
7. 1.000 1.044 1.281 0.849 0.961
8. 0.958 1.000 1.227 0.813 0.921
9. 0.781 0.815 1.000 0.663 0.751
10. 1.178 1.230 1.508 1.000 1.132
11. 1.040 1.086 1.332 0.883 1.000

Проверить на интеловом компиляторе не могу - у меня его нет... Но поищу.

 

Ruptor
Фигасе немного?
У меня почти в 2 раза разница получается для ICC 10.1 vs MSVC 7.1

ICC

VC7.1

 

Это на P4 805 (2680 MHz)
На данный момент под рукой нет другого.
Вечером дома могу проверить на C2D E4500 (2.2 Gz)