Шабал - Shabal

Шабал это криптографическая хеш-функция представленный исследовательским проектом Saphir, финансируемым Францией, в Международный конкурс NIST по хеш-функциям.

Партнеры Saphir

Партнеры по исследованиям Saphir (за исключением LIENS) инициировали концепцию Shabal, а позже к ним присоединились партнеры исследовательского проекта Saphir2, которые активно участвовали в окончательном дизайне Shabal. Saphir (Безопасность и анализ хэш-примитивов) - это финансируемый ANR проект по хеш-функциям. Saphir начал свою деятельность в марте 2006 года и продлил ее на три года и объединил пять партнеров: Cryptolog International, DCSSI, France Telecom (лидер), Gemalto и LIENS. Партнеры Saphir2 представляют как промышленность, так и научные круги; Помимо партнеров Saphir, к проекту присоединились 4 новых партнера: EADS SN, INRIA, Sagem Sécurité и UVSQ.^[1]

История

Shabal был участником конкурса хеш-функций NIST, где прошел во второй раунд, но не прошел в финальный раунд. Шабал не был выбран в финал в основном из соображений безопасности. Хотя безопасность алгоритма полного хеширования не была нарушена, обнаружение свойств неслучайности с низкими временными сложностями вызвало опасения среди криптографов NIST по поводу возможности более мощных атак в будущем.^[2]

Название алгоритма было выбрано как дань уважения Себастьян Шабаль.^[1]

Описание

Shabal использует режим работы, который можно рассматривать как вариант конструкции хэша Меркла – Дамгарда с широким конвейером. Внутреннее состояние Shabal состоит из трех частей, обозначенных как A, B и C. Перестановка с ключом Shabal обновляет A и B с помощью регистров сдвига с нелинейной обратной связью, которые взаимодействуют друг с другом. Основной цикл перестановки использует модульное умножение на три и пять, модульное сложение, XOR, дополнение и операции AND.

Режим цепочки Shabal работает следующим образом: (A, B) ← PM, C

(A, B, C) ← (A, C - M, B),

(A ⊕ W, B + M),

где M - блок сообщения, а W - счетчик. После обработки всех блоков сообщения применяются три раунда завершения, в которых фиксируются значения блока сообщения и счетчика. Для Shabal определены два настраиваемых параметра (p, r), где p - количество циклов, выполняемых в рамках перестановки ключей, а r - размер A. Значение по умолчанию (p, r) равно (3, 12). Кроме того, p и r должны удовлетворять 16p ≡ 0 mod r. Одна и та же внутренняя функция используется для всех форматов вывода Shabal.^[2]

Выходные размеры Shabal

Размеры вывода Shabal в зависимости от длины дайджеста:

Шабал-192
Шабал-224
Шабал-256
Шабал-384
Шабал-512^[1]

Выходы Шабала

Пример хешей Shabal:

Шабал-192: CB6E700F CE4DCF97 D2BBBF00 0C5364FB B40C8732 0D733948
Шабал-224: 14A6DD99 E8D207F9 F7187681 326F6930 8BCAAE00 25F4855F 3120BA43
Шабал-256: C0088FDA 9ABA672A 79D0BD56 07AE488E 095E2114 06855B3B 1877A349 A2543F99
Шабал-384: 3312DE9D DA850D91 03785C3A C611B112 5D1BCAFC 033755D2 3B8EE05E 15251E4E 636A724F F0A8E584 4AABEAAF 122FC0C4
Шабал-512: C6168015 0A3F1FC8 688DD952 8E9E2FED 23EF9578 BCE2A7CB A5D80961 E6C9E632 9701A5A6 F037B89F 20C6C44E DC7931E7 2BB5AB82 B3ADCD32 9CE985E25056 2230^[1]

Безопасность

Для перестановки Шабала были предложены различные отличительные признаки. Используя кубические тестеры, свойство статистической неслучайности перестановки ключей Шабала было описано с временной сложностью 2³⁰⁰.^[3]
Вращающийся отличитель ключевой перестановки Шабала с использованием 2¹⁷¹ звонки были представлены. Различитель основан на наблюдении, что большинство операций в P сохраняют отношения вращения между входами. Однако атака не может быть распространена на алгоритм хеширования из-за несимметричного IV, добавления счетчика блоков и существования раундов завершения.^[4]^[5]
Был представлен еще один отличительный признак, основанный на наблюдении, что умножение на три сохраняет разницу в наиболее значимом бите с вероятностью один. Используя это наблюдение, авторы представили метод поиска полуэквивалентных ключей для ключевой перестановки. В рамках модели связанных ключей авторы также представили метод, который отличает P от случайной перестановки с помощью одного запроса. Метод можно обобщить на любой параметр безопасности. Авторы также представили метод поиска псевдоколлизий и псевдосекундных прообразов для варианта Shabal, в котором количество итераций в финализации составляет 24N (N ≥ 2) вместо 36. Однако эта атака не работает для оригинальный Шабал, так как при количестве итераций 36 исключить различия невозможно.^[6]
Для ключевой перестановки P были показаны некоторые свойства неслучайности, которые легко проверить. Авторы предложили простой метод нахождения неподвижных точек в P. Входные данные перестановки были выбраны так, чтобы на них не влияли циклы перестановки. Метод не зависит от количества слов в A и количества раундов; следовательно, метод работает при любом выборе настраиваемых параметров безопасности. Авторы также показали способ создания множества больших множественных коллизий, единственное отличие которых заключается в вводе ключа.^[2]
Различитель был представлен по некоторым из смещенных выходных битов с использованием дифференциального анализа с 2²³ сложность данных.^[7]
Атака псевдо-коллизией с низким весом (45 бит) на функцию сжатия Shabal с временной сложностью 2⁸⁴ был представлен. Атака прообраза с 2⁴⁹⁷ время и 2⁴⁰⁰ сложность памяти для Shabal 512 с использованием параметров безопасности (2, 12).^[8]
Ни один из отличительных признаков напрямую не угрожает заявленной безопасности хеш-алгоритма. Более того, разработчики модифицировали доказательство безопасности неразличимости своего режима цепочки, чтобы требовать более слабых предположений, чем идеальные шифры.^[2]

Реализации

Рекомендации

^ ^а ^б ^c ^d Брессон, Эммануэль; Клавир, Кристоф; Фур, Томас; Икарт, Томас; Мисарский, Жан-Франсуа; Ная-Пласенсиа, Мария; Рейнхард, Жан-Рене; Тюйе, Селин; Видео, Марион (2008-10-28). "Shabal, заявка на конкурс криптографических хеш-алгоритмов NIST" (PDF): 2–3, 20, 22, 32–35. Цитировать журнал требует | журнал = (помощь)
^ ^а ^б ^c ^d Межведомственный отчет NIST 7764 (февраль 2011 г.). «Отчет о состоянии второго раунда конкурса алгоритмов шифрования SHA-3» (PDF): 20–21. Цитировать журнал требует | журнал = (помощь)
^ Оумассон, Жан-Филипп. «О псевдослучайности ключевой перестановки Шабала» (PDF). Получено 14 ноября 2018. Цитировать журнал требует | журнал = (помощь)
^ Ван Аше, Жиль (24 марта 2010 г.). «Вращающийся отличительный признак ключевой перестановки Шабала и его влияние на доказательства безопасности» (PDF). Цитировать журнал требует | журнал = (помощь)
^ Aerts, Nieke (август 2011 г.). «Криптоанализ хэш-функций, в частности, претендентов на SHA-3, Шабала и Блейка» (PDF): 56–57. Цитировать журнал требует | журнал = (помощь)
^ Оумассон, Жан-Филипп; Машатан, Атефех; Мейер, Вилли. «Подробнее о перестановке Шабала» (PDF). Получено 14 ноября 2018. Цитировать журнал требует | журнал = (помощь)
^ Новотней, Питер (20 июля 2010 г.). «Отличитель перестановочной функции Шабала» (PDF). Цитировать журнал требует | журнал = (помощь)
^ Исобе, Таканори; Шираи, Тайдзо. «Атака псевдоколлизией с малым весом на Шабале и атака прообраза на уменьшенном Шабале-512» (PDF). Получено 14 ноября 2018. Цитировать журнал требует | журнал = (помощь)

[:1-1] а ^б ^c ^d Брессон, Эммануэль; Клавир, Кристоф; Фур, Томас; Икарт, Томас; Мисарский, Жан-Франсуа; Ная-Пласенсиа, Мария; Рейнхард, Жан-Рене; Тюйе, Селин; Видео, Марион (2008-10-28). "Shabal, заявка на конкурс криптографических хеш-алгоритмов NIST" (PDF): 2–3, 20, 22, 32–35. Цитировать журнал требует | журнал = (помощь)

[:0-2] а ^б ^c ^d Межведомственный отчет NIST 7764 (февраль 2011 г.). «Отчет о состоянии второго раунда конкурса алгоритмов шифрования SHA-3» (PDF): 20–21. Цитировать журнал требует | журнал = (помощь)

[3] Оумассон, Жан-Филипп. «О псевдослучайности ключевой перестановки Шабала» (PDF). Получено 14 ноября 2018. Цитировать журнал требует | журнал = (помощь)

[4] Ван Аше, Жиль (24 марта 2010 г.). «Вращающийся отличительный признак ключевой перестановки Шабала и его влияние на доказательства безопасности» (PDF). Цитировать журнал требует | журнал = (помощь)

[5] Aerts, Nieke (август 2011 г.). «Криптоанализ хэш-функций, в частности, претендентов на SHA-3, Шабала и Блейка» (PDF): 56–57. Цитировать журнал требует | журнал = (помощь)

[6] Оумассон, Жан-Филипп; Машатан, Атефех; Мейер, Вилли. «Подробнее о перестановке Шабала» (PDF). Получено 14 ноября 2018. Цитировать журнал требует | журнал = (помощь)

[7] Новотней, Питер (20 июля 2010 г.). «Отличитель перестановочной функции Шабала» (PDF). Цитировать журнал требует | журнал = (помощь)

[8] Исобе, Таканори; Шираи, Тайдзо. «Атака псевдоколлизией с малым весом на Шабале и атака прообраза на уменьшенном Шабале-512» (PDF). Получено 14 ноября 2018. Цитировать журнал требует | журнал = (помощь)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]