Хеш-функция облегчённой криптографии
— криптостойкая
хеш-функция
, используемая в «легковесной»
криптографии
. В настоящее время актуальность таких хеш-функций резко возросла благодаря возможности использовать их во многих сферах деятельности (от
RFID
до
Интернета вещей
) и на стыке дисциплин (
Блокчейн
и
IoT
)
. В виду специфики использования данных хеш-функций, на них накладываются дополнительные требования
. Большинство современных хеш-функций в качестве своей основы используют структуру
Меркла — Дамгора
и
функцию губки
.
Содержание
Концепция облегчённой криптографии
Облегчённая криптография — раздел криптографии, в котором рассматриваются алгоритмы для устройств, не обладающих достаточными ресурсами для реализации существующих
шифров
,
хеш-функций
,
электронных подписей
и т. д.
«Легковесная» криптография приобрела исключительную актуальность в настоящее время в связи распространением парадигмы
умного дома
, где множество приборов небольшого размера, с ограниченной вычислительной мощностью, лимитированным объёмом памяти и малым энергопотреблением коммуницируют между собой, обмениваясь конфиденциальной информацией жильца, для выполнения своих задач
. Также особый интерес представляют алгоритмы для
RFID
меток
. Для того, чтобы злоумышленики не воспользовались приватной информацией пользователя, требуется специальная разработка и оптимизация алгоритмов способных работать при ограниченных ресурсах и обеспечивать должный уровень безопасности
.
Хеш-функции
Применение
Для того, чтобы адресату убедиться в том, что ему было прислано сообщение от настоящего адресанта, оно отправляется вместе с электронной подписью. На практике подписывают не сообщение, а его хеш-сумму, это позволяет значительно уменьшить вычислительные ресурсы на создание подписи (так как обычно хеш-сумма на порядки меньше ключа) и повысить криптостойкость (злоумышленник не сможет узнать исходные данные только из хеша)
. Хеш-функции используются в технологии
блокчейн
для того, чтобы определить блок, который добавится в общую цепь. Например: для добавления нового блока в платформу
Bitcoin
требуется найти хеш-сумму
SHA-256
меньше, чем определённое целевое число. В следующий созданный блок будет записан хеш предыдущего
. Более того, хеш-функции, в частности хеш-функции облегчённой криптографии могут применяться на стыке дисциплин. Например: они применяются в блокчейне LSB, который предназначен для использования в интернете вещей
.
Также хеш-суммы используются при проверке паролей. Если бы операционные системы хранили пароли в файлах, то взломщики с помощью несанкционированного доступа смогли бы получить к ним доступ, извлечение хеша, в свою очередь, им ничего не даст
.
Требования
Основные требования к хеш-функциям облегчённой криптографии такие же, как и к обычным криптографическим хеш-функциям
:
Стойкость к восстановлению первого прообраза
— при наличии хеш-суммы
невозможность вычислить
Стойкость к восстановлению вторых прообразов
— при наличии
невозможность найти
, такое что
Стойкость к коллизиям
— невозможность найти
и
, такие что
Принимая в расчёт возможности вычислительных устройств, на которых будут производиться алгоритмы, а также задачи, которые требуется выполнить, к основным требованиям добавляются специальные:
(
англ.
) — эффективна для атак на хеш-функций и шифров, которые используют
LFSR
(
англ.
) — разработана для хеш-функций, использующих блочные и потоковые шифры
(
англ.
) — действенны для хеш-функций с блочными шифрами
Атака методом бумеранга
— усовершенствованная дифференциальная атака, которая успешно применяется к хеш-функциям
. Так, например, для нахождения коллизий
SHA-0
с помощью этой атаки потребовался всего лишь один час на обычном
ПК
Мультиколлизионная атака Жу
— направлена на хеш-функции, использующие в качестве своей основы
функцию губки
, которая распространена среди функций облегчённой криптографии
Допустим, нам дан вектор инициализации
:
(фиксированный и открытый), функция сжатия
отображающая
в
и сообщение
, где
блок из
битов, если
не кратно
, то последний блок мы дополняем 1 и нулями
. Например: если
,
то на вход мы подаём
блока:
,
где единица добавляется для избежания коллизий. Теперь можно определить хеш-функцию
:
Усовершенствованный алгоритм
Для усиления защиты от атак, основанных на расширении входного сообщения, можно добавить новый блок, в котором будет записана длина сообщения
. В данном случае это будет:
Также есть оптимизация, которая позволяет экономить ресурсы памяти (что важно для задач облегчённой криптографии): если в последнем блоке достаточно места для записи длины сообщения, то она будет там и записана:
Функция губки широко используется в криптографии, с помощью неё создаются алгоритмы
ГПСЧ
,
потоковых
и
блочных
шифров, а также хеш-функций
.
Основная идея
Губку размера
можно разделить на 2 части: битовую скорость
и мощность
. При инициализации внутреннее состояние губки обнуляется; сообщение
дополняется нулями, чтобы его размер был кратен
.
Далее следуют
стадии:
Абсорбция
Первые
бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
Внутреннее состояние обрабатывается функцией перестановки
Выжимание
Считываются первые
бит внутреннего состояния губки
Внутреннее состояние обрабатывается функцией перестановки
П-губка и Т-губка
П(ерестановочная)-губка и Т(рансформационная)-губка — губки, использующие соответственно случайную перестановку и ГПСЧ для обновления своего внутреннего состояния. В статье, в которой были введены функции губки, было показано, что губки с мощностью
, битовой скоростью
и вектором размера
, принимающие на вход сообщения длиной
, таковы, что для различных атак в среднем требуется следующее количество обращений к функциям обновлении(приведены степени двойки)
:
Губка
Первый прообраз
Второй прообраз
Коллизия
Нахождение цикла
T-губка
П-губка
JH-губка
JH-губку называют так, потому что она похожа на структуру хеш-функции
JH
.
У неё стадия абсорбции состоит из трёх частей:
Первые
бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
Внутреннее состояние обрабатывается функцией перестановки
Последние
бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
Примеры хеш-функций в облегчённой криптографии
GLUON
GLUON — это хеш-функция, использующая T-губку, основанную на программно-ориентированных потоковых шифрах X-FCSR-v2 и F-FCSR-H-v3
: внутреннее состояние губки дополняется и загружается в
FCSR
, который синхронизируется за фиксированное количество времени. Затем некоторые ячейки FCSR складываются по модулю 2 для формирования первого слова следующего внутреннего состояния, FCSR синхронизируется, эти же слова складываются по модулю 2 для формирования второго слова следующего внутреннего состояния и т. д.
Функция обладает высокой криптографической стойкостью. Например: атака нахождения прообраза в общем случае имеет сложность
, где
— размер матрицы
(которая определяет
FCSR
), а
-
размер слова, подаваемого на FCSR.
Особенность реализации GLUON состоит в том, что данные в FCSR записываются не последовательно, а параллельно, что значительно повышает скорость исполнения. Также был оптимизирован adder (элемент, осуществляющий сложение), который используется в FCSR, следующим образом:
, где
(здесь
используется в качестве обозначения
логического И
)
.
Функция обновления GLUON-64 является многозначной, и её поведение сильно отличается от поведения
ГПСЧ
.
QUARK
QUARK — это хеш-функция, использующая П-губку с аппаратно-ориентированной перестановкой. Была реализована под влиянием облегчённых блочных шифров KTANTAN
и KATAN
и аппаратно-ориентированного потокового шифра Grain
. Наименьшая версия (хеш-сумма длиной 136 бит) называется U-QUARK, средняя (176 бит) D-QUARK и самая длинная (256 бит) S-QUARK.
Функция обновления отображает вектор
в
, загружая каждую половину в отдельный
(
англ.
) длины
, а затем повторяет это
раза. NFSR связаны друг с другом и с небольшим LFSR длины
. Функции
,
и
являются булевыми функциями, выбранными из-за их нелинейности и алгебраической сложности.
и
одинаковы для всех версий и заимствованы из Grain-v1, а
определяется отдельным случаем.
Специфика реализации QUARK состоит в том, что в ней отсутствуют промежуточные значения функции губки, которые требуют дополнительных элементов для их запоминания. Другими словами, после перестановки значений состояния значения не записываются в следующее состояние, а сразу подаются на функцию перестановки, причём первые
бит делают
XOR
с сообщением
.
Обладает высокой криптостойкостью. Данные по резистентности к различным атакам приведены ниже
:
Сложность успешной атаки для нахождения:
Коллизии
Первого прообраза
Второго прообраза
У данной хеш-функции есть реализация в открытом
, написанная на языке
C
.
SipHash-2-4
SipHash имеет структуру ARX, которая была создана под влиянием
BLAKE
и
Skein
. Он собой предоставляет семейство отображений
, и предназначен для использования в качестве
MAC
или в хеш-таблицах. Он имеет структуру, аналогичную JH, как SPN-Hash, и использует заполнение, учитывающее также длину сообщения. Однако, оно заключается просто в добавлении байта с длиной сообщения по модулю 256. SipHash не претендует на устойчивость к коллизиям и, очевидно, не из-за небольшого размера хеш-суммы.
Отличительная черта SipHash состоит в том, что сообщения «
ксорятся
», не как в обычной функции губки, а по особому алгоритму:
Первое сообщение ксорится с последней четвертью губки
Губка обрабатывается двумя функциями перестановки
Первое сообщение снова ксорится, но уже с первой четвертью губки, в то время, как второе сообщение с последней
Губка обрабатывается двумя функциями перестановки
Второе сообщение ксорится с первой четвертью губки, а третья четверть ксорится с 0xFF
Несмотря на то, что в основе SipHash лежит ARX, не является уязвимой для
.
PHOTON представляет собой P-губку, основанную на AES-подобной
перестановке. Для наименьшего параметра безопасности (PHOTON-80/20/16) битовая скорость во время абсорбции равна 20 и равна 16 во время выжимания. Перестановка состоит из 12 итераций (для каждого параметра безопасности) ниже описанной последовательности преобразований, выполненных на квадрате
ячеек из 4 бит (8 бит для самой большой версии). Конвейер PHOTON состоит из 4 этапов:
Дополнительные константы (AddConstants)
— дополнительные константы выбираются так, чтобы быть разными на каждой итерации, и чтобы отсутствовала симметрия между столбцами, как в AES подобных архитектурах (без этого слоя входное сообщение с равными столбцами будет сохранять это качество спустя любое количество итераций). Дополнительные константы могут быть сгенерированы регистром сдвига с линейной обратной связью. Для высокой производительности задействован только первый столбец внутреннего состояния. После того, как константы были сгенерированы, они складываются по модулю 2 с каждой ячейкой.
Замена ячеек (SubCells)
— S-блок применяется на каждой ячейке. Если ячейка имеет длину 4 бита, то используется PRESENT Sbox SBOXPRE, если 8 бит — AES Sbox SBOXAES.
Сдвиг строк (ShiftRows)
— идентичен AES.
MixColumnsSerial
— ячейки рассматриваются как элементы поля Галуа
(или
для наибольшего параметра безопасности), и каждый столбец умножается на матрицу
, специально созданной для эффективной реализации в аппаратном обеспечении
.
Данные по криптостойкости:
Сложность успешной атаки для нахождения:
Коллизии
Первого прообраза
Второго прообраза
Способ перестановки, используемый для обновления губки, близок к LED
шифру, который был разработан позже создателями PHOTON.
SPONGENT
SPONGENT можно рассматривать как П-губку, где перестановка является модифицированной версией блочного шифра PRESENT.
Число итераций PRESENT-подобной перестановки варьируется от 45 для SPONGENT-88 до 140 для SPONGENT-256. Каждая итерация состоит из:
Складывания по модулю 2 содержимого LFSR, синхронизированного на каждой итерации (может рассматриваться, как константа на итерации)
Применение к слою S-блока
S-блок
4×4, удовлетворяющий тем же критериям, что и PRESENT S-блок
Переставляя биты способом, подобным в PRESENT
Насколько известно, нет никакой атаки на SPONGENT, за исключением линейных распознавателей для версий с уменьшенным количеством итераций
.
Основной интерес SPN-Hash заключается в её доказуемой защите от дифференциальных коллизионных атак. Это JH-губка, использующая, как следует из её названия, перестановку, основанную на
SPN
. Структура SPN основана на структуре AES
: сначала S-блоки 8×8 применяются к каждому байту внутреннего состояния. Используемый S-блок в точности совпадает с использующимся в AES. Затем применяется более сложный перемешивающий слой; Сильной стороной этого хеширования являются хорошая диффузия и легковесность. Наконец, константы на каждой итерации записываются во внутренне состояние (строгой дизъюнкцией), аналогичной LED и PHOTON. Эти операции повторяются 10 раз для всех параметров безопасности.
Используемый отступ такой же, как в усиленном Меркле-Дамгоре: длина сообщения добавляется к последнему блоку
.
DM-PRESENT
DM-PRESENT — это просто схема Меркла-Дамгора, где функцией сжатия является блочный шифр PRESENT в режиме Дэвиса-Мейера. DM-PRESENT-80 основан на PRESENT-80, а DM-PRESENT-128 — на PRESENT-128. Данная хеш-функция уязвима для коллизий и не является стойкой к восстановлению вторых прообразов, такие хеш-функции будут полезны только в приложениях, которым требуется стойкость к восстановлению первого прообраза и 64-битная защита
.
ARMADILLO
ARMADILLO — это
многоцелевой
примитив, предназначенный для использования в качестве FIL-MAC (приложение I), для хеширования и цифровых подписей (приложение II), а также для PRNG и PRF (приложение III). Он был взломан Найей-Пласенсией и Пейрином
. Они нашли способ быстро обнаруживать коллизии, когда он используется в качестве хеш-функции (несколько секунд на обычном ПК)
.
↑
Kerry A McKay, Larry Bassham, Meltem Sonmez Turan, Nicky Mouha.
. — Gaithersburg, MD: National Institute of Standards and Technology, 2017-03.
Megha Agrawal, Jianying Zhou, Donghoon Chang.
// Security and Privacy Trends in the Industrial Internet of Things. — Cham: Springer International Publishing, 2019. —
С. 71–94
. —
ISBN 978-3-030-12329-1
, 978-3-030-12330-7
.
↑
Susha Surendran, Amira Nassef, Babak D. Beheshti.
// 2018 IEEE Long Island Systems, Applications and Technology Conference (LISAT). — IEEE, 2018-05. —
ISBN 978-1-5386-5029-5
. —
doi
:
.
Damith C. Ranasinghe.
// Networked RFID Systems and Lightweight Cryptography. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. —
С. 311–346
. —
ISBN 978-3-540-71640-2
, 978-3-540-71641-9
.
F. Lefebvre, J. Czyz, B. Macq.
// Proceedings 2003 International Conference on Image Processing (Cat. No.03CH37429). — IEEE. —
ISBN 0-7803-7750-8
. —
doi
:
.
Guy Zyskind, Oz Nathan, Alex 'Sandy' Pentland.
// 2015 IEEE Security and Privacy Workshops. — IEEE, 2015-05. —
ISBN 978-1-4799-9933-0
. —
doi
:
.
Ali Dorri, Salil S. Kanhere, Raja Jurdak, Praveen Gauravaram.
// Journal of Parallel and Distributed Computing. — 2019-12. —
Т. 134
. —
С. 180–197
. —
ISSN
. —
doi
:
.
Mohammad Peyravian, Nevenko Zunic.
// Computers & Security. — 2000-07. —
Т. 19
,
вып. 5
. —
С. 466–469
. —
ISSN
. —
doi
:
.
Kerry A McKay, Larry Bassham, Meltem Sonmez Turan, Nicky Mouha.
. — Gaithersburg, MD: National Institute of Standards and Technology, 2017-03.
Gilles Brassard, Peter HØyer, Alain Tapp.
// LATIN'98: Theoretical Informatics. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. —
С. 163–169
. —
ISBN 978-3-540-64275-6
, 978-3-540-69715-2
.
Lathrop, Joel.
.
Joan Daemen.
[
Cipher and Hash Function Design
Strategies based on linear and differential
cryptanalysis]. — 1995. — 267 с.
Bart Preneel, René Govaerts, Joos Vandewalle.
// Advances in Cryptology — CRYPTO’ 93. — Berlin, Heidelberg: Springer Berlin Heidelberg. —
С. 368–378
. —
ISBN 978-3-540-57766-9
.
Antoine Joux, Thomas Peyrin.
// Advances in Cryptology - CRYPTO 2007. — Berlin, Heidelberg: Springer Berlin Heidelberg. —
С. 244–263
. —
ISBN 978-3-540-74142-8
.
Stéphane Manuel, Thomas Peyrin.
// Fast Software Encryption. — Berlin, Heidelberg: Springer Berlin Heidelberg. —
С. 16–35
. —
ISBN 978-3-540-71038-7
, 978-3-540-71039-4
.
↑
Jean-Sébastien Coron, Yevgeniy Dodis, Cécile Malinaud, Prashant Puniya.
// Advances in Cryptology – CRYPTO 2005. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. —
С. 430–448
. —
ISBN 978-3-540-28114-6
, 978-3-540-31870-5
.
Narayana D. Kashyap.
. — San Jose State University Library.
Mohammad A. AlAhmad, Imad Fakhri Alshaikhli, Mridul Nandi.
// Proceedings of the 6th International Conference on Security of Information and Networks - SIN '13. — New York, New York, USA: ACM Press, 2013. —
ISBN 978-1-4503-2498-4
. —
doi
:
.
Krystian Matusiewicz, María Naya-Plasencia, Ivica Nikolić, Yu Sasaki, Martin Schläffer.
// Advances in Cryptology – ASIACRYPT 2009. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. —
С. 106–125
. —
ISBN 978-3-642-10365-0
, 978-3-642-10366-7
.
Dmitry Khovratovich, Ivica Nikolić.
// Fast Software Encryption. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. —
С. 333–346
. —
ISBN 978-3-642-13857-7
, 978-3-642-13858-4
.
↑
R.O. Gilbert.
. — Office of Scientific and Technical Information (OSTI), 1973-05-01.
↑
Bertoni, Guido, Joan Daemen, Michaël Peeters and Gilles Van Assche. «Sponge Functions.» (2007).
от 16 июня 2022 на
Wayback Machine
Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche.
// Cryptographic Hardware and Embedded Systems, CHES 2010. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. —
С. 33–47
. —
ISBN 978-3-642-15030-2
, 978-3-642-15031-9
.
Hongjun Wu.
(англ.)
// Institute for Infocomm Research, Singapore. — 2011. — 1 January. —
P. 54
.
16 июня 2021 года.
Franc̨ois Arnault, Thierry Berger, Cédric Lauradoux, Marine Minier, Benjamin Pousse.
// Selected Areas in Cryptography. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. —
С. 433–448
. —
ISBN 9783642054433
, 9783642054457
.
Thierry P. Berger, Joffrey D’Hayer, Kevin Marquet, Marine Minier, Gaël Thomas.
// Progress in Cryptology - AFRICACRYPT 2012. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. —
С. 306–323
. —
ISBN 978-3-642-31409-4
, 978-3-642-31410-0
.
↑
Christophe De Cannière, Orr Dunkelman, Miroslav Knežević.
// Lecture Notes in Computer Science. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. —
С. 272–288
. —
ISBN 9783642041372
, 9783642041389
.
Martin Hell, Thomas Johansson, Alexander Maximov, Willi Meier.
// 2006 IEEE International Symposium on Information Theory. — IEEE, 2006-07. —
ISBN 142440505X
, 1424405041
. —
doi
:
.
↑
Jean-Philippe Aumasson, Luca Henzen, Willi Meier, María Naya-Plasencia.
// Journal of Cryptology. — 2012-05-10. —
Т. 26
,
вып. 2
. —
С. 313–339
. —
ISSN
. —
doi
:
.
Jean-Philippe Aumasson, Daniel J. Bernstein.
// Lecture Notes in Computer Science. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. —
С. 489–508
. —
ISBN 978-3-642-34930-0
, 978-3-642-34931-7
.
↑
Joan Daemen, Vincent Rijmen.
// Encyclopedia of Cryptography and Security. — Springer US. —
С. 520–524
. —
ISBN 9780387234731
.
Jian Guo, Thomas Peyrin, Axel Poschmann.
// Advances in Cryptology – CRYPTO 2011. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. —
С. 222–239
. —
ISBN 9783642227912
, 9783642227929
.
Jian Guo, Thomas Peyrin, Axel Poschmann, Matt Robshaw.
// Cryptographic Hardware and Embedded Systems – CHES 2011. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. —
С. 326–341
. —
ISBN 9783642239502
, 9783642239519
.
Andrey Bogdanov, Miroslav Knežević, Gregor Leander, Deniz Toz, Kerem Varıcı.
// Cryptographic Hardware and Embedded Systems – CHES 2011. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. —
С. 312–325
. —
ISBN 978-3-642-23950-2
, 978-3-642-23951-9
.
Mohamed Ahmed Abdelraheem.
// Lecture Notes in Computer Science. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. —
С. 368–382
. —
ISBN 9783642376818
, 9783642376825
.
Jiali Choy, Huihui Yap, Khoongming Khoo, Jian Guo, Thomas Peyrin.
// Progress in Cryptology - AFRICACRYPT 2012. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. —
С. 270–286
. —
ISBN 978-3-642-31409-4
, 978-3-642-31410-0
.
// Archives of Civil and Mechanical Engineering. — 2008-01. —
Т. 8
,
вып. 2
. —
С. 181–183
. —
ISSN
. —
doi
:
.
María Naya-Plasencia, Thomas Peyrin.
// Fast Software Encryption. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. —
С. 146–162
. —
ISBN 9783642340468
, 9783642340475
.
Stéphane Badel, Nilay Dağtekin, Jorge Nakahara, Khaled Ouafi, Nicolas Reffé.
// Cryptographic Hardware and Embedded Systems, CHES 2010. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. —
С. 398–412
. —
ISBN 9783642150302
, 9783642150319
.