SHACAL 2

SHACAL — симметричный блочный криптоалгоритм. Он был разработан в 2000 году, его авторами являются Хелен Хандшух и Дэвид Наккаш из компании Gemplus. Впервые два варианта этого алгоритма — SHACAL-1(2000 г.) и SHACAL-2(2001 г.) были представлены на конкурсе NESSIE, последний в свою очередь попал в число 17 финалистов.

Основой SHACAL является алгоритм хеширования SHA (Secure Hash Algorithm), и в этом его основное отличие от прочих криптоалгоритмов. SHACAL-1 и SHACAL-2 используют хеш-функции SHA-1 и SHA-256 соответственно.

Хеш-алгоритм SHA-256

Данный алгоритм впервые был опубликован в 2001 г., его разработкой занималось Агентство национальной безопасности (АНБ) США. На данный момент SHA-256 используется в блокчейне, например Биткойн использует этот алгоритм в качестве сетевого алгоритма Proof of Work для майнинга криптовалюты. Размер выходного хеша SHA-256: 256 бит, при промежуточном размере хеша в 256 бит. Входные данные разбиваются на блоки по 512 бит, максимально возможный размер сообщения составляет $2^{64}-1$ бит. Размер слова — 32 бита, таким образом данный алгоритм рассчитан на 32-битную архитектуру, и все операции вычисляются в поле $F_{2^{32}}$(по модулю $2^{32}$). Число раундов, в отличие от всех прочих реализаций алгоритма SHA — 64 (в прочих версиях используется 80 раундов).

Необходимые в дальнейшем обозначения:

• $+$ : Сложение по модулю $2^{32}$ 32-битных слов
• $ROT_{i}(W)$ : Циклический сдвиг 32-битного слова W влево на i бит
• $\bigoplus$ : Побитовое исключающее ИЛИ
• $\And$ : Побитовое И
• $|$ : Побитовое ИЛИ

При хеширования сообщения выполняются следующие действия:

1. Сообщение дополняется таким образом, чтобы длина была кратна размеру функции сжатия (разбивается на блоки по 512 бит)
2. Инициализируем переменные $h_{0}$ — $h_{7}$, каждая по 32 бита, следующим образом (первые 32 бита дробных частей квадратных корней первых 8 простых чисел 2..19):
   • $h_{0}$ = 0x6a09e667
   • $h_{1}$ = 0xbb67ae85
   • $h_{2}$ = 0x3c6ef372
   • $h_{3}$ = 0xa54ff53a
   • $h_{4}$ = 0x510e527f
   • $h_{5}$ = 0x9b05688c
   • $h_{6}$ = 0x1f83d9ab
   • $h_{7}$ = 0x5be0cd19
3. Инициализируем массив констант округления (первые 32 бита дробных частей кубических корней первых 64 простых чисел 2..311):
   • k[0..63] = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2]
4. Для каждого блока сообщения по 512 бит:
   • Начинаем с исходного сообщения длиной L бит
   • Добавляем один бит «1»
   • Добавляем K «0» битов, где K — минимальное число >= 0 такое, что (L + 1 + K + 64) кратно 512
   • Добавляем L, как 64-битное целое число с обратным порядком байтов, в результате чего общая длина постобработки будет кратна 512 битам
   • Таким образом, чтобы биты в сообщении были: <исходное сообщение длины L> 1 <K нулей> <L как 64-битное целое> (количество битов будет кратно 512)
5. Создаем из сообщения массив с 64 элементами w[0..63] из 32-битных слов (начальные значения в w[0..63] не имеют значения, поэтому многие реализации их обнуляют)
6. Копируем фрагмент в первые 16 слов w[0..15] полученного массива
7. Расширяем первые 16 слов до оставшихся 48 слов w[16..63] следующим образом:
   • for i from 16 to 63
     • $s_{0}=ROT_{7}(w[i-15])\bigoplus ROT_{18}(w[i-15])\bigoplus ROT_{3}(w[i-15])$
     • $s_{1}=ROT_{17}(w[i-2])\bigoplus ROT_{19}(w[i-2])\bigoplus ROT_{10}(w[i-2])$
     • $w[i]=w[i-16]+s_{0}+w[i-7]+s_{1}$
8. Инициализировать рабочие переменные текущим значением хеша:
   • $a=h_{0}$
   • $b=h_{1}$
   • $c=h_{2}$
   • $d=h_{3}$
   • $e=h_{4}$
   • $f=h_{5}$
   • $g=h_{6}$
   • $h=h_{7}$
9. Проходим по основному циклу функции сжатия:
   • for i from 0 to 63
     • $s_{1}=ROT_{6}(e)\bigoplus ROT_{11}(e)\bigoplus ROT_{25}(e)$
     • $ch=(e\And f)\bigoplus ({\overline {e}}\And g)$, где ${\overline {e}}$ — отрицание e, в введенных нами обозначениях можем выразить как: ${\overline {e}}=e\bigoplus 0{\text{x}}ffffffff$
     • $temp_{1}=h+s_{1}+ch+k[i]+w[i]$
     • $s_{0}=ROT_{2}(a)\bigoplus ROT_{13}(a)\bigoplus ROT_{22}(a)$
     • $maj=(a\And b)\bigoplus (a\And c)\bigoplus (b\And c)$
     • $temp_{2}=s_{0}+maj$
     • $h=g$
     • $g=f$
     • $f=e$
     • $e=d+temp_{1}$
     • $d=c$
     • $c=b$
     • $b=a$
     • $a=temp_{1}+temp_{2}$
10. Добавляем сжатый фрагмент к текущему значению хеша:
    • $h_{0}=h_{0}+a$
    • $h_{1}=h_{1}+b$
    • $h_{2}=h_{2}+c$
    • $h_{3}=h_{3}+d$
    • $h_{4}=h_{4}+e$
    • $h_{5}=h_{5}+f$
    • $h_{6}=h_{6}+g$
    • $h_{7}=h_{7}+h$
11. Получаем выходное значение хеша (с прямым порядком байтов):
    • digest = [ $h_{0}$ || $h_{1}$ || $h_{2}$ || $h_{3}$ || $h_{4}$ || $h_{5}$ || $h_{6}$ || $h_{7}$ ]

SHACAL-2, и алгоритм использования SHA-256 в режиме шифрования

Хеш-функция SHA никогда не предназначалась для использования в шифровании, однако она может быть использована в этих целях. Так как каждый из 64 шагов её алгоритма является обратимым, если вставить секретный ключ в переменные сообщения и открытый текст в качестве начального значения, то мы, игнорируя последний шаг со сложением с начальным состоянием, получим обратимую функцию сжатия. Именно этот режим шифрования SHA и применяется в серии алгоритмов SHACAL.

Таким образом, SHACAL-2 — это блочный шифр, определённый для битового секретного ключа длиной 512 бит. Более короткие ключи также могут быть использованы путем дополнения ключа нулями до битовой строки длиной 512. Однако SHACAL-2 не предназначен для использования с ключами короче 128 бит.

Криптостойкость алгоритма SHACAL-2

Две самые известные атаки на системы, подобные SHA в режиме шифрования:

• линейный криптоанализ
• дифференциальный криптоанализ

Существует длинный список вариантов двух атак, предложенных в литературе, но основные принципы примерно одинаковы. Также были предложены много других атак на схемы шифрования, но они менее общие, чем два вышеупомянутых, и не относятся к схемам шифрования вообще. Далее рассматриваются только два представленных выше вида атак. Эти атаки применимы к SHACAL-2 в режиме шифрования, но, как видно далее, атаки, основанные на данных подходах совершенно непрактичны, если вообще возможны.

Линейный криптоанализ алгоритма SHACAL-2

Линейный криптоанализ — вид атаки на симметричные шифры, суть которого заключается в восстановлении секретного ключа шифрования, по известным открытому тексту и соответствующему ему шифртексту.

Рассмотрим алгоритм Мацуи: изначально для каждого раунда шифра находится линейная аппроксимация с наибольшей вероятностью смещения. Полученные выражения объединяются в общую для всех раундов линейную аппроксимацию, вероятность смещения которой позволяет найти лемма о набегании знаков:

1. Вначале необходимо каким-либо образом выбрать некоторые биты ключа, открытого текста и шифртекста, чтобы выполнялось следующее уравнение (достаточно на большом наборе пар текстов и шифртекстов иметь вероятность выполнения уравнения отличную от ${1 \over 2}$):
   • $P_{1}\bigoplus P_{2}\bigoplus ...\bigoplus P_{a}\bigoplus C_{1}\bigoplus C_{2}\bigoplus ...\bigoplus C_{b}=K_{1}\bigoplus K_{2}\bigoplus ...\bigoplus K_{c}$ $(1)$ — называется линейной аппроксимацией, где P, C, K — текст, шифртекст и ключ соответственно, а нижние индексы обозначают номер бита в соответствующем блоке данных
2. После выполнения пункта 1 криптоаналитик, имея линейную аппроксимацию, зависящие от исследуемого алгоритма, может восстановить один бит ключа. Проблемы, с которыми сталкивается криптоаналитик, при работе с данным алгоритмом криптоанализа:
   • Как найти эффективное уравнение вида $(1)$
   • Как с помощью такого уравнения получить больше одного бита информации о ключе

Десятиступенчатая линейная аппроксимация, предложенная авторами алгоритма, действительна в течение 40 шагов полнораундового SHA-2. Поэтому оценка максимального смещения равняется $(2^{-6})^{4}*2^{3}=2^{-21}$. Это, конечно, всего лишь приближенная оценка. Среди многих благоприятных предположений для криптоаналитики выделяется утверждающее, что это десятиступенчатое линейное приближение может быть соединено само с собой. Расширение этого приближения в любом направлении, вероятно, даст сильное падение используемого смещения линейного приближения.

Для раунда 1 есть возможность приближенно оценить, что 20 шагов могут, с использованием линейной аппроксимации, дать смещение не более чем $(2^{-6})^{2}*2=2^{-11}$. Точно так же можно оценить, что для 20 шагов в раунде 3 может быть аппроксимирована со смещением не более $(2^{-5})^{2}*2=2^{-9}$. При наиболее благоприятных для криптоаналитика условиях, которые в реальности вряд ли могут быть удовлетворены, если SHA-2 используя линейную аппроксимацию, смещение будет не более чем $2^{-21}*2^{-11}*2^{-9}*2^{2}=2^{-39}$. Таким образом, ключевые условия, необходимые для получения наилучшего смещения для аппроксимации в раундах 1 и 3 выполняются исключительно редко и поэтому, игнорируя этот случай, можно заключить, что систематическая ошибка, скорее всего, окажется ниже $2^{-40}$.

С другой стороны, описанное приближение имеет нулевое смещение для многих ключей, поэтому аналитику пришлось бы использовать другие приближения, в этих случаях давая уменьшенное рабочее смещение.

Таким образом, для линейной криптоатаки на SHA-2 требуется не менее $2^{80}$ известных открытых текстов, что можно считать исключительно маловероятным.

Дифференциальный криптоанализ алгоритма SHACAL-2

Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров), основанный на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю $2^{32}$.

Идея состоит в том, что разница в открытых текстах позволяет злоумышленнику вероятностно определить разницу в промежуточных шифртекстах. Если можно определить разницу в зашифрованных текстах после нескольких последних раундов шифрования, тогда с высокой вероятностью часто можно произвести поиск для битов ключа, использованных в последнем раунде. Если удастся восстановить ключ, злоумышленник может расшифровать все зашифрованные тексты за один раунд и повторить атаку на шифр на один раунд короче, чем оригинал, который обычно проще, чем атака на полный шифр.

Основными инструментами дифференциального криптоанализа являются характеристика и дифференциал:

1. Характеристика — это список предсказанных различий в шифртекстах после каждого раунда шифра, начиная с открытого текста и вероятностей, связанных с ними. Характеристики обычно строятся из сложения характеристик одного раунда. Затем берется вероятность характеристики, как произведение вероятностей всех участвующих характеристик одного раунда. Здесь предполагается, что задействованные характеристики одного раунда независимы, что чаще всего это не совсем так, но так же часто это хорошее приближение.
2. Дифференциал — это совокупность характеристик, имеющих одинаковые начальные и конечные значения. Таким образом, дифференциал s-го раунда обычно определяет только различия в открытых текстах и ​​в шифртекстах после s раундов. Для дифференциалов в промежуточных зашифрованных текстах допускается варьирование. Таким образом, вероятности дифференциала в целом выше, чем для соответствующей характеристики. Для того, чтобы обеспечить успешную атаку на основе дифференциального криптоанализа, существование хороших характеристик являются необходимостью, в то время как для доказательства устойчивости против атак, необходимо убедиться, что все дифференциалы имеют низкую вероятность. Обнаружение хороших дифференциалов оказалось очень трудным для большинства шифров и часто учитываются только характеристики.

Чаще всего в дифференциальном криптоанализе «различие» определяется как «исключающее или» от двух текстов, участвующих в паре. Также для SHACAL-2 это кажется лучшим и очевидным определением. Используя оценку наилучших характеристик для раундов 1, 2, 3 и 4, можно вычислить оценку наилучшей характеристики для всех 64 шагов SHACAL-2, а именно $2^{-26}*2^{-32}*2^{-26}*2^{-32}=2^{-116}$. Стоит ещё раз подчеркнуть, что полученная оценка достаточно условна. Во-первых, оценки для каждого раунда были приближенными, а во-вторых, нет гарантии, что высоковероятностные характеристики для каждого раунда по отдельности могут быть объединены со всем шифром. Поэтому можно сделать вывод, что дифференциальный криптоанализ SHACAL-2, скорее всего, потребует нереалистичного количество выбранных текстов, если это вообще возможно.

Заключение

В предыдущих разделах было показано, что линейная крипто-атака на SHA-2 потребует, по крайней мере, $2^{80}$ известных открытых текстов, и что дифференциальная атака потребует, по крайней мере, $2^{116}$ выбранных открытых текстов. Данные оценки были получены из рассмотрения конструируемых линейных приближений и дифференциальных характеристик. Вполне может быть, что есть и другие приближения и характеристики над SHACAL-2, которые не выявляются этим типом анализа. Их пришлось бы искать грубой силой. Так как нет известных коротких путей к такому поиску, эту возможность следует рассматривать как маловероятную и не заслуживающую практического рассмотрения.

В качестве метода построения аппроксимаций и характеристик был использован ad hoc, но на основе значительного практического опыта. Исходя из приведенных расчетов и оценок, в настоящее время утверждается, что линейная или дифференциальная крипто-атака с использованием менее $2^{80}$ известных блоков открытого текста, неосуществима.

На текущий момент никому не удалось взломать полнораундовый SHACAL-2 (64 раунда) с 512 битным ключом, следовательно, его можно считать безопасным.

См. также

• SHACAL
• Симметричные криптосистемы
• NESSIE
• SHA-1
• SHA-2
• Блокчейн
• Биткойн
• Криптографическая хеш-функция
• Раунд (криптография)
• Ключ (криптография)
• Шифротекст
• Открытый текст
• Криптоаналитик
• Линейный криптоанализ
• Дифференциальный криптоанализ

Литература

1. H. Handschuh, D. Naccache. SHACAL (2000)
2. Mario Lamberger and Florian Mendel (2011). «Higher order differential attack on small SHA-256»
3. Matsui, M. «First Experimental Cryptanalysis of a Data Protection Standard.» Advances in Cryptology — CRYPTO 1994
4. Heys H. M. A Tutorial on Linear and Differential Cryptanalysis
5. Biham E., Shamir A. Differential cryptoanalysis of the Data Encription Standart
6. Seokhie Hong; Jongsung Kim; Guil Kim; Jaechul Sung; Changhoon Lee; Sangjin Lee (December 2003). Impossible Differential Attack on 30-Round SHACAL-2
7. YongSup Shin; Jongsung Kim; Guil Kim; Seokhie Hong; Sangjin Lee (July 2004). Differential-Linear Type Attacks on Reduced Rounds of SHACAL-2
8. Christoph Dobraunig; Maria Eichlseder & Florian Mendel (2016). «Analysis of SHA-512/224 and SHA-512/256»