SHABAL — алгоритм криптографического хеширования . Является одним из участников конкурса SHA-3 , который проводится Национальным институтом стандартов и технологий , объявление окончательных результатов и победителя запланировано на 2012 год . Был представлен на конкурс исследовательским проектом «Сапфир» (Saphir: Security and Analysis of Hash Primitives), спонсором которого является Французское исследовательское агентство (ANR), а главной организацией — France Telecom .

Авторы алгоритма: Эммануэль Брессон, Анна Кантеоут, Беноит Шевалье-Мамес, Кристоф Клавьер, Томас Фухр, Алина Гоуджет, Томас Икарт, Жен-Франсуа Мисарски, Мария Ная-Пласенкия, Паскаль Пайлер, Томас Порнини, Жан-Рене Рейнхард, Селина Тьюлльет, Марион Видеау.

Алгоритм, по утверждению авторов, назван в честь «Себастьяна Шабала, французского игрока регби, известного агрессивным стилем игры, а также бородой и длинными волосами, за которые ему дали кличку „Пещерный человек“ (Caveman)» .

Алгоритм

По утверждению разработчиков, SHABAL является одним из самых быстрых кандидатов конкурса SHA-3 .

SHABAL может принимать на вход битовые последовательности любой длины, однако криптографическая стойкость для сообщений с длиной более, чем ${\displaystyle 2^{73}}$ бит, не гарантируется.

Принцип работы

SHABAL называется SHABAL-512 , SHABAL-384, SHABAL-256, SHABAL-224, SHABAL-192 в зависимости от длины получаемого хэша ${\displaystyle l_{h}}$ , соответственно равного 512, 384, 256, 224, 192 бит.

После того как на вход алгоритма приходит битовая последовательность, она разбивается на блоки по 512 бит вне зависимости от используемой вариации SHABAL (SHABAL-512, SHABAL-384 и т. д.). Отметим, что размер блока кратен 32. К последнему блоку, если его битовая длина не равна 512 битам, приписывается одна битовая единица и необходимое число нулей для достижения заданного размера блока.

При вычислении хеш-функции используется буфер, поделенный на три части ${\displaystyle (A,B,C)\in {\mathcal {f}}0,1{\mathcal {g}}^{l_{a}}\times {\mathcal {f}}0,1{\mathcal {g}}^{l_{b}}\times {\mathcal {f}}0,1{\mathcal {g}}^{l_{c}}}$ , где ${\displaystyle l_{a}}$ и ${\displaystyle l_{b}}$ и ${\displaystyle l_{c}}$ — это длины буферов ${\displaystyle A}$ , ${\displaystyle B}$ и ${\displaystyle C}$ соответственно. Также используется вспомогательный буфер W размером в 64 бита, который является счетчиком номера блока. Длины буферов ${\displaystyle l_{b}}$ и ${\displaystyle l_{c}}$ равны ${\displaystyle l_{m}}$ , где ${\displaystyle l_{m}}$ — это длина блока на которые разбивается поданное на вход сообщение.

SHABAL обладает двумя настраиваемыми параметрами ${\displaystyle r\geqslant 2}$ и ${\displaystyle p\geqslant 2}$ . Длина буфера ${\displaystyle A}$ определяется через ${\displaystyle r}$ , а именно ${\displaystyle l_{a}=32r}$ . Параметр ${\displaystyle p}$ — количество раундов в преобразовании ${\displaystyle P}$ , чем больше это значение, тем гарантируется большая безопасность. Заявленный на конкурс алгоритм SHABAL строго определяет ${\displaystyle (p,r)=(3,12)}$

SHABAL — итеративный алгоритм. Количество повторений равно количеству блоков исходной битовой последовательности плюс две итерации на добавляемые в начало сообщения блоки (подробнее об этих двух блоках написано в описании работы алгоритма по шагам), плюс ещё три финальные итерации. На каждой итерации происходит преобразование ${\displaystyle P_{M,C}(A,B)\rightarrow (A,C)}$ . При каждом повторении кроме трех финальных число, хранимое в ${\displaystyle W}$ , увеличивается на 1, то есть как уже упоминалось ${\displaystyle W}$ — это счетчик.

Действие алгоритма по шагам

Отметим, что операции суммирования и вычитания далее производятся в пределах слов (то есть 4-байтовых блоков) и без переноса.

Инициализация

В ${\displaystyle (A,B,C)}$ заносятся нули. В начало основного сообщения ${\displaystyle M}$ добавляются два блока, в каждый 4-байтовый фрагмент которых записываются фиксированные числа варьирующиеся от ${\displaystyle l_{h}}$ до ${\displaystyle l_{h}+31}$ , где ${\displaystyle l_{h}}$ — это длина выхода хеш-функции ${\displaystyle l_{h}\in {\mathcal {f}}192,224,256,384,512{\mathcal {g}}}$ . Если более подробно, то в два добавленных блока, которые мы назовем ${\displaystyle M_{-1}}$ и ${\displaystyle M_{0}}$ (каждый размером по ${\displaystyle l_{m}}$ =512 бит), записываются следующие слова (32-битные блоки): ${\displaystyle M_{-1}[0]=l_{h}}$ , ${\displaystyle M_{-1}[15]=l_{h}+15}$ , ${\displaystyle M_{0}[0]=l_{h}+16}$ , ${\displaystyle M_{0}[15]=l_{h}+31}$ . Промежуточные слова ${\displaystyle M_{-1}}$ и ${\displaystyle M_{0}}$ заполняются по аналогии.

Числу в ${\displaystyle W}$ присваивается значение −1, таким образом после обработки добавленных в начало блоков, первому блоку входного сообщения будет соответствовать ${\displaystyle W}$ , равная 1.

Разбиение на блоки

Входная битовая последовательность разбивается на блоки по 512 бит, если длина сообщения не кратна указанной длине, то к последней части добавляется одна битовая единица и нужное для достижения заданного размера количество нулей.

Обычные итерации

Для всех w ( ${\displaystyle w=2^{32}*W[1]+W[0];W[0]}$ и ${\displaystyle W[1]}$ -32 битные части W) от −1 до k (где k количество блоков изначального сообщения) сделать следующее:

• сложить B и M по словам, результат заносим в B

${\displaystyle B\leftarrow B+M_{w}}$

• применить XOR на счетчике и A

${\displaystyle A[0]\leftarrow A[0]\oplus W[0],A[1]\leftarrow A[1]\oplus W[1]}$

• сделать преобразование P

${\displaystyle (A,B)\leftarrow P_{M_{w},C}(A,B)}$

• вычесть из C M по словам

${\displaystyle C\leftarrow C-M_{w}}$

• поменять местами B и С

${\displaystyle (B,C)\leftarrow (C,B)}$

Заключительные итерации

После выполнения обычных итераций нужно выполнить еще три финальных итерациях. Они отличаются от обычных тем, что за блок ${\displaystyle M}$ принимается последний блок сообщения ${\displaystyle M_{k}}$ , значение счетчика фиксируется и равняется k общему числу блоков.

Результат

Выходные слова(32 битные блоки) от ${\displaystyle C[16-l_{h}/32]}$ до ${\displaystyle C[15]}$ являются результатом. ${\displaystyle A}$ и ${\displaystyle B}$ игнорируются.

Примечание

Стоит отметить, что рассчитывать преобразования от двух первых добавленных блоков каждый раз при использовании SHABAL совершенно необязательно. С таким же успехом, значения ${\displaystyle (A,B,C)}$ от этих двух блоков можно рассчитать один раз и потом использовать их как IV(initial vector).

Список IV для разных версий SHABAL

SHABAL-192:

A :

FD749ED4 B798E530 33904B6F 46BDA85E 076934B4 454B4058 77F74527 FB4CF465

62931DA9 E778C8DB 22B3998E AC15CFB9

B :

58BCBAC4 EC47A08E AEE933B2 DFCBC824 A7944804 BF65BDB0 5A9D4502 59979AF7

C5CEA54E 4B6B8150 16E71909 7D632319 930573A0 F34C63D1 CAF914B4 FDD6612C

C :

61550878 89EF2B75 A1660C46 7EF3855B 7297B58C 1BC67793 7FB1C723 B66FC640

1A48B71C F0976D17 088CE80A A454EDF3 1C096BF4 AC76224B 5215781C CD5D2669

SHABAL-224:

A :

A5201467 A9B8D94A D4CED997 68379D7B A7FC73BA F1A2546B 606782BF E0BCFD0F

2F25374E 069A149F 5E2DFF25 FAECF061

B :

EC9905D8 F21850CF C0A746C8 21DAD498 35156EEB 088C97F2 26303E40 8A2D4FB5

FEEE44B6 8A1E9573 7B81111A CBC139F0 A3513861 1D2C362E 918C580E B58E1B9C

C :

E4B573A1 4C1A0880 1E907C51 04807EFD 3AD8CDE5 16B21302 02512C53 2204CB18

99405F2D E5B648A1 70AB1D43 A10C25C2 16F1AC05 38BBEB56 9B01DC60 B1096D83

SHABAL-256:

A :

52F84552 E54B7999 2D8EE3EC B9645191 E0078B86 BB7C44C9 D2B5C1CA B0D2EB8C

14CE5A45 22AF50DC EFFDBC6B EB21B74A

B :

B555C6EE 3E710596 A72A652F 9301515F DA28C1FA 696FD868 9CB6BF72 0AFE4002

A6E03615 5138C1D4 BE216306 B38B8890 3EA8B96B 3299ACE4 30924DD4 55CB34A5

C :

B405F031 C4233EBA B3733979 C0DD9D55 C51C28AE A327B8E1 56C56167 ED614433

88B59D60 60E2CEBA 758B4B8B 83E82A7F BC968828 E6E00BF7 BA839E55 9B491C60

SHABAL-384:

A :

C8FCA331 E55C504E 003EBF26 BB6B8D83 7B0448C1 41B82789 0A7C9601 8D659CFF

B6E2673E CA54C77B 1460FD7E 3FCB8F2D

B :

527291FC 2A16455F 78E627E5 944F169F 1CA6F016 A854EA25 8DB98ABE F2C62641

30117DCB CF5C4309 93711A25 F9F671B8 B01D2116 333F4B89 B285D165 86829B36

C :

F764B11A 76172146 CEF6934D C6D28399 FE095F61 5E6018B4 5048ECF5 51353261

6E6E36DC 63130DAD A9C69BD6 1E90EA0C 7C35073B 28D95E6D AA340E0D CB3DEE70

SHABAL-512:

A :

20728DFD 46C0BD53 E782B699 55304632 71B4EF90 0EA9E82C DBB930F1 FAD06B8B

BE0CAE40 8BD14410 76D2ADAC 28ACAB7F

B :

C1099CB7 07B385F3 E7442C26 CC8AD640 EB6F56C7 1EA81AA9 73B9D314 1DE85D08

48910A5A 893B22DB C5A0DF44 BBC4324E 72D2F240 75941D99 6D8BDE82 A1A7502B

C :

D9BF68D1 58BAD750 56028CB2 8134F359 B5D469D8 941A8CC2 418B2A6E 04052780

7F07D787 5194358F 3C60D665 BE97D79A 950C3434 AED9A06D 2537DC8D 7CDB5969

Описание преобразования ${\displaystyle P}$

Входные данные: M,A,B,C

Выход: A,B

( ${\displaystyle x\lll a}$ обозначает вращение бит ${\displaystyle x}$ на ${\displaystyle a}$ позиций влево)

Преобразование представлено для наглядности в псевдокоде:

For i from 0 to 15, do:

${\displaystyle B[i]\leftarrow B[i]\lll 17}$

Next i;

For j from 0 to p-1, do:

• For i from 0 to 15, do:

${\displaystyle A[i+16j{\bmod {r}}]\leftarrow U(A[i+16j{\bmod {r}}]\oplus V(A[i-1+16j{\bmod {r}}]\lll 15)\oplus C[8-i{\bmod {1}}6])}$

${\displaystyle \oplus B[i+o_{1}{\bmod {1}}6]}$

${\displaystyle \oplus (B[i+o_{2}{\bmod {1}}6]\cap {\overline {B[i+o_{3}{\bmod {1}}6]}})}$

${\displaystyle \oplus M[i]}$

где ${\displaystyle (o_{1},o_{2},o_{3})=(13,9,6)}$

${\displaystyle B[i]\leftarrow (B[i]\lll 1)\oplus {\overline {A[i+16j{\bmod {r}}]}}}$

• Next i;

Next j;

For j from 0 to 35, do:

${\displaystyle A[j{\bmod {r}}]\leftarrow A[j{\bmod {r}}]+C[j+3{\bmod {1}}6]}$

Next j;

Где функции U и V определяются следующим образом:

${\displaystyle U(x)=3\times x\mod 2^{32}}$

${\displaystyle V(x)=5\times x\mod 2^{32}}$

Примеры результатов

Исходное сообщение в байтах

M1 :

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Результат и конечное состояние

SHABAL-192

A :

A38C0C63 17C2CAE8 3248572C 1C89CAD5 176ED597 B242B8AD 73298C22 7ADF1817

00D909DA 61AD8518 90266914 9DC1F617

B :

260A3D42 E9E62340 385A3EBF 2978F492 A1DE4E1A AEDBB855 49DB44CD D0B179F3

7D7FAAE0 87798FA8 9F7F5E35 4A9F52FE A0F35652 65A6D26E 320A1851 EFF9A7CD

C :

F91EEE5E 99DCC78C 82F72599 8CACD775 09544255 ED275CF3 0166F95E 2C375AFA

49AAFBE0 4D9C01C6 CB6E700F CE4DCF97 D2BBBF00 0C5364FB B40C8732 0D733948

H :

CB6E700F CE4DCF97 D2BBBF00 0C5364FB B40C8732 0D733948

SHABAL-224

A :

08FC66FC CE392D14 42C29F35 5649D86A DCD65214 9A423F72 99D2F688 5073E130

1E1F9B61 A28A416E 9C9572AB C3A9B2BC

B :

33D58779 1AD91014 D67F57EC FDADD8EC 75AB31C5 C50ECE4D B7C2CD52 3B8500C5

FCCD0F17 F7EED488 FF906EED DB95D041 965CBF04 B0E05609 1B26DB06 843B9DE7

C :

BE6AC9DC 86AFB8BB 300C6C1B 237F0C8C 6DEF5EEF 599CA070 540040F7 EEA985E4

4A5B8375 14A6DD99 E8D207F9 F7187681 326F6930 8BCAAE00 25F4855F 3120BA43

H :

14A6DD99 E8D207F9 F7187681 326F6930 8BCAAE00 25F4855F 3120BA43

SHABAL-256

A :

3DBA182A D0D6787E DAD8F4C9 CC065328 A36A08C7 902C794E 43E5A220 E2F378F1

1E35B4C3 EF6B834E 8E442A11 6922E895

B :

66DF96F1 E4D309BD 6377D5E2 48F253E3 F8E9B974 0773C11C 8B2B886F 9D7AC002

343612B3 80C441F4 F676FCAD 3D6A453A 6CBEC284 2B3DE748 57EE16DB 80DBFF08

C :

57E837B3 3B2C6ACA E0358DC2 2BD758E9 30F7A2ED DF3516C7 253CB0E0 1A1A98FC

C0088FDA 9ABA672A 79D0BD56 07AE488E 095E2114 06855B3B 1877A349 A2543F99

H :

C0088FDA 9ABA672A 79D0BD56 07AE488E 095E2114 06855B3B 1877A349 A2543F99

SHABAL-384

A :

37661E10 1BEDBBD5 B022D077 CB1781BD 23DCFA84 AF4946EC 9C681ADD 8C48B88C

6BC4D0CB 1F4A95CD 0F2C5CD4 D1BC38C6

B :

CA3AFDBC 298219E1 5E0BF2B8 8F151F6D 648A1FC9 C1F29FEE CD9F4978 F81C514A

44EB858B D33B06CF 929CBC10 60672CBB 20B3CCCA EB12DED0 5CCD8C97 240C8D1C

C :

D4163C6A 49313E63 0D1ACCBE 7AD73B3E 3312DE9D DA850D91 03785C3A C611B112

5D1BCAFC 033755D2 3B8EE05E 15251E4E 636A724F F0A8E584 4AABEAAF 122FC0C4

H :

3312DE9D DA850D91 03785C3A C611B112 5D1BCAFC 033755D2 3B8EE05E 15251E4E

636A724F F0A8E584 4AABEAAF 122FC0C4

SHABAL-512

A :

1FD517B4 18EE0662 002DA3F7 3C864C42 00BDBC17 D3A91349 84B98D58 DB0A255C

EA84933C 78858700 4E1BD28E 22E17C53

B :

D90A51B3 625DBAFC A04AE0F1 15BBA584 3D510ABB 8DF79E61 BBC7D290 442F3794

A65F93BA 7FCB1E48 60830747 B3922082 93AC0A65 FFB4D084 7900BFF4 8548658A

C :

C6168015 0A3F1FC8 688DD952 8E9E2FED 23EF9578 BCE2A7CB A5D80961 E6C9E632

9701A5A6 F037B89F 20C6C44E DC7931E7 2BB5AB82 B3ADCD32 9CE25056 22305E98

H :

C6168015 0A3F1FC8 688DD952 8E9E2FED 23EF9578 BCE2A7CB A5D80961 E6C9E632

9701A5A6 F037B89F 20C6C44E DC7931E7 2BB5AB82 B3ADCD32 9CE25056 22305E98

Криптоанализ

SHABAL является чем-то средним между схемой Меркле-Дамгаарда и впитывающей функцией (sponge function). Для стойкости этих схем необходима криптостойкость преобразования ${\displaystyle P}$ . И создатели SHABAL стремились к этой цели. К сожалению ${\displaystyle P}$ оказалось нестойким, но криптоаналитики пришли к выводу, что безопасность SHABAL от этого не пострадала. Данный факт вызывает отдельный интерес и сейчас изучается.

Примечания

Ссылки