Хеш-функция облегчённой криптографии: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м →‎Примечания: исправление
→‎GLUON: источники
Строка 104: Строка 104:


=== GLUON ===
=== GLUON ===
GLUON<ref>{{Статья|автор=Thierry P. Berger, Joffrey D’Hayer, Kevin Marquet, Marine Minier, Gaël Thomas|год=2012|isbn=9783642314094, 9783642314100|страницы=306–323|заглавие=The GLUON Family: A Lightweight Hash Function Family Based on FCSRs|ссылка=http://dx.doi.org/10.1007/978-3-642-31410-0_19|место=Berlin, Heidelberg|издательство=Springer Berlin Heidelberg|издание=Progress in Cryptology - AFRICACRYPT 2012}}</ref>- это хеш-функция, использующая T-губку, основанную на программно-ориентированных потоковых шифрах X-FCSR-v2 и F-FCSR-H-v3: внутреннее состояние губки дополняется и загружается в [[Регистр сдвига с обратной связью по переносу|FCSR]], который синхронизируется за фиксированное количество времени. Затем некоторые ячейки FCSR складываются по модулю 2 для формирования первого слова следующего внутреннего состояния, FCSR синхронизируется, эти же слова складываются по модулю 2 для формирования второго слова следующего внутреннего состояния и т. д.
GLUON<ref>{{Статья|автор=Thierry P. Berger, Joffrey D’Hayer, Kevin Marquet, Marine Minier, Gaël Thomas|год=2012|isbn=9783642314094, 9783642314100|страницы=306–323|заглавие=The GLUON Family: A Lightweight Hash Function Family Based on FCSRs|ссылка=http://dx.doi.org/10.1007/978-3-642-31410-0_19|место=Berlin, Heidelberg|издательство=Springer Berlin Heidelberg|издание=Progress in Cryptology - AFRICACRYPT 2012}}</ref>- это хеш-функция, использующая T-губку, основанную на программно-ориентированных потоковых шифрах X-FCSR-v2 и F-FCSR-H-v3<ref>{{Статья|автор=Franc̨ois Arnault, Thierry Berger, Cédric Lauradoux, Marine Minier, Benjamin Pousse|год=2009|isbn=9783642054433, 9783642054457|страницы=433–448|заглавие=A New Approach for FCSRs|ссылка=http://dx.doi.org/10.1007/978-3-642-05445-7_27|место=Berlin, Heidelberg|издательство=Springer Berlin Heidelberg|издание=Selected Areas in Cryptography}}</ref>: внутреннее состояние губки дополняется и загружается в [[Регистр сдвига с обратной связью по переносу|FCSR]], который синхронизируется за фиксированное количество времени. Затем некоторые ячейки FCSR складываются по модулю 2 для формирования первого слова следующего внутреннего состояния, FCSR синхронизируется, эти же слова складываются по модулю 2 для формирования второго слова следующего внутреннего состояния и т. д.


Функция обновления GLUON-64 является многозначной, и ее поведение сильно отличается от поведения [[Генератор псевдослучайных чисел|ГПСЧ]].
Функция обновления GLUON-64 является многозначной, и ее поведение сильно отличается от поведения [[Генератор псевдослучайных чисел|ГПСЧ]].

Версия от 18:07, 15 ноября 2019

Хеш-функция облегченной криптографии - хеш-функция, являющаяся криптостойкой и удовлетворяющая основным критериям применения в «легковесной» криптографии. Keccak[1] - победитель конкурса SHA-3 от NIST при оптимизации аппаратной реализации для технологии 0,09 мкм имеет не менее 15 200 GE (Gate Equivalent). Наименее затратный алгоритм - это 9 200 GE у Grøstl[2]; Это слишком много, скажем, для меток RFID. Вот почему были предложены «легкие» хеш-функции.

Концепция облегченной криптографии

Облегчённая криптография – раздел криптографии, в котором рассматриваются алгоритмы для устройств не обладающих достаточными ресурсами для реализации существующих шифров, хеш-функций, электронных подписей и т.д. Например: многим гаджетам может не хватать оперативной памяти, или время выполнения операций значительно превышает приемлемый уровень. «Легковесная» криптография приобрела исключительную актуальность в настоящее время в связи распространением парадигмы умного дома, где множество приборов небольшого размера, с ограниченной вычислительной мощностью, лимитированным объемом памяти и малым энергопотреблением коммуницируют между собой, обмениваясь конфедициальной информацией жильца, для выполнения своих задач. Для того, чтобы злоумышленики не воспользовались приватной информацией пользователя, требуется специальная разработка и оптимизация алгоритмов способных работать при ограниченных ресурсах и обеспечивать должный уровень безопасности.

Хеш-функции

Применение

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

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

Требования

Основные требования к хеш-функциям облегченной криптографии такие же, как и к обычным функциям свертки:

  • Стойкость к восстановлению первого прообраза - при наличии хеш-суммы H(m) невозможность вычислить m
  • Стойкость к восстановлению вторых прообразов - при наличии m невозможность найти n, такое что H(n) = H(m)
  • Стойкость к коллизиям - невозможность найти m и n, такие что H(n) = H(m)

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

  • Малое потребление энергии
  • Небольшой размер внутреннего состояния
  • Нежадное потребление памяти

Виды хеширований

Все применяемые на данный момент алгоритмы хеширования в облегченной криптографии можно разделить на 2 класса:

Меркл — Дамгор

Основная идея

Допустим, нам дан вектор инициализации IV {0, 1}n (фиксированный и открытый), функция сжатия h отображающая {0,1}n×{0,1}k в {0,1}n и сообщение m = (m0, m1, ..., mL-1), где mi блок из k битов, если m не кратно k, то последний блок мы дополняем 1 и нулями. Например: если

m = 123456789,

то на вход мы подаем 2 блока:

12345678 91000000,

где единица добавляется для избежания коллизий. Теперь можно определить хеш-функцию H:

  • c0 = IV
  • ci+1 = h(ci, mi)
  • H(m) = d = cL

Усовершенствованный алгоритм

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

12345678 91000000 00000009

Также есть оптимизация, которая позволяет экономить ресурсы памяти (что важно для задач облегченной криптографии): если в последнем блоке достаточно места для записи длины сообщения, то она будет там и записана:

12345678 91000009

Функция губки

Функция губки[3] широко используется в криптографии, с помощью неё создаются алгоритмы ГПСЧ, потоковых и блочных шифров, а также хеш-функций.

Основная идея

Губку размера b можно разделить на 2 части: битовую скорость r и мощность c. При инициализации внутреннее состояние губки обнуляется; сообщение m дополняется нулями, чтобы его размер был кратен r.

Далее следуют 2 стадии:

  1. Абсорбция
    • Первые r бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
    • Внутреннее состояние обрабатывается функцией перестановки
  1. Выжимание
    • Считываются первые r бит внутреннего состояния губки
    • Внутреннее состояние обрабатывается функцией перестановки

П-губка и Т-губка

П(ерестановочная)-губка и Т(рансформационная)-губка - губки, использующие соответственно случайную перестановку и ГПСЧ для обновления своего внутреннего состояния. В статье, в которой были введены функции губки, было показано, что губки с мощностью c, битовой скоростью r и вектором размера n, принимающие на вход сообщения длиной m < 2c/2, таковы, что для различных атак в среднем требуется следующее количество обращений к функциям обновлении(приведены степени двойки):

Губка Первый прообраз Второй прообраз Коллизия Нахождение цикла
T-губка min(n, c+r) min(n, c-log2(m)) min(n, c)/2 (c+r)/2
П-губка c-1 min(n, c/2) min(n, c)/2 c+r

JH-губка

JH-губку[4] называют так, потому что она похожа на структуру хеш-функции JH.

У неё стадия абсорбции состоит из трех частей:

  1. Первые r бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
  2. Внутреннее состояние обрабатывается функцией перестановки
  3. Последние r бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения

Примеры хеширований облегченной криптографии

GLUON

GLUON[5]- это хеш-функция, использующая T-губку, основанную на программно-ориентированных потоковых шифрах X-FCSR-v2 и F-FCSR-H-v3[6]: внутреннее состояние губки дополняется и загружается в FCSR, который синхронизируется за фиксированное количество времени. Затем некоторые ячейки FCSR складываются по модулю 2 для формирования первого слова следующего внутреннего состояния, FCSR синхронизируется, эти же слова складываются по модулю 2 для формирования второго слова следующего внутреннего состояния и т. д.

Функция обновления GLUON-64 является многозначной, и ее поведение сильно отличается от поведения ГПСЧ.

QUARK

QUARK[7] - это хеш-функция, использующая П-губку с аппаратно-ориентированной перестановкой. Была реализована под влиянием облегченных блочных шифров KTANTAN[8] и KATAN[9] и аппаратно-ориентированного потокового шифра Grain[10]. Наименьшая версия (хеш-сумма длиной 136 бит) называется U-QUARK, средняя (176 бит) D-QUARK и самая длинная (256 бит) S-QUARK.

Функция обновления отображает вектор {0,1}b в {0,1}b, загружая каждую половину в отдельный NSFR длины b/2, а затем повторяет это 4*b раза. NSFR связаны друг с другом и с небольшим LFSR длины log(4b), см. Рисунок сбоку. Функции f, g и h являются булевыми функциями, выбранными из-за их нелинейности и алгебраической сложности. f и g одинаковы для всех версий и заимствованы из Grain-v1, а h определяется отдельным случаем.

SipHash-2-4

SipHash[11] имеет структуру ARX, которая была создана под влиянием BLAKE и Skein. Он собой предоставляет семейство отображений {0,1}*→{0,1}64, и предназначено для использования в качестве MAC или в хеш-таблицах. Он имеет структуру, аналогичную JH, как SPN-Hash, и использует заполнение, учитывающее также длину сообщения. Однако, оно заключается просто в добавлении байта с длиной сообщения по модулю 256. SipHash не претендует на устойчивость к коллизиям и, очевидно, не из-за небольшого размера хеш-суммы.

PHOTON

PHOTON[12] представляет собой P-губку, основанную на AES-подобной[13] перестановке. Для наименьшего параметра безопасности (PHOTON-80/20/16) битовая скорость во время абсорбции равна 20 и равна 16 во время выжимания. Перестановка состоит из 12 итераций (для каждого параметра безопасности) ниже описанной последовательности преобразований, выполненных на квадрате d×d ячеек из 4 бит (8 бит для самой большой версии). Конвейер PHOTON состоит из 4 этапов:

  1. Дополнительные константы (AddConstants) - дополнительные константы выбираются так, чтобы быть разными на каждой итерации, и чтобы отсутствовала симметрия между столбцами, как в AES подобных архитектурах (без этого слоя входное сообщение с равными столбцами будет сохранять это качество спустя любое количество итераций). Дополнительные константы могут быть сгенерированы регистром сдвига с линейной обратной связью. Для высокой производительности задействован только первый столбец внутреннего состояния. После того, как константы были сгенерированы, они складываются по модулю 2 с каждой ячейкой.
  2. Замена ячеек (SubCells) - S-блок применяется на каждой ячейке. Если ячейка имеет длину 4 бита, то используется PRESENT Sbox SBOXPRE, если 8 бит - AES Sbox SBOXAES.
  3. Сдвиг строк (ShiftRows) - идентичен AES.
  4. MixColumnsSerial - ячейки рассматриваются как элементы поля GF(24) (или GF(28) для наибольшего параметра безопасности), и каждый столбец умножается на матрицу MDS, специально созданной для эффективной реализации в аппаратном обеспечении.

Способ перестановки, используемый для обновления губки, близок к LED[14] шифру, который был разработан позже создателями PHOTON.

SPONGENT

SPONGENT[15] можно рассматривать как П-губку, где перестановка является модифицированной версией блочного шифра PRESENT.

Число итераций PRESENT-подобной перестановки варьируется от 45 для SPONGENT-88 до 140 для SPONGENT-256. Каждая итерация состоит из:

  1. Складывания по модулю 2 содержимого LFSR, синхронизированного на каждой итерации (может рассматриваться, как константа на итерации)
  2. Применение к слою S-блока S-блок $4\times4$, удовлетворяющий тем же критериям, что и PRESENT S-box
  3. Переставляя биты способом, подобным в PRESENT

Насколько известно, нет никакой атаки на SPONGENT, за исключением линейных распознавателей для версий с уменьшенным количеством итераций.[16]

SPN-Hash

Основной интерес этой хеш-функции заключается в ее доказуемой защите от дифференциальных коллизионных атак. Это JH-губка, использующая, как следует из ее названия, перестановку, основанную на SPN. Структура SPN основана на структуре AES[17]: сначала S-блоки 8×8 применяются к каждому байту внутреннего состояния. Используемый S-блок в точности совпадает с использующимся в AES. Затем применяется более сложный перемешивающий слой; Сильной стороной этого хеширования являются хорошая диффузия и легковесность. Наконец, константы на каждой итерации записываются во внутренне состояние (строгой дизъюнкцией), аналогичной LED и PHOTON. Эти операции повторяются 10 раз для всех параметров безопасности.

Используемый отступ такой же, как в усиленном Меркле-Дамгоре: длина сообщения добавляется к последнему блоку.

DM-PRESENT

DM-PRESENT[18] - это просто схема Меркла-Дамгора, где функцией сжатия является блочный шифр PRESENT в режиме Дэвиса-Мейера. DM-PRESENT-80 основан на PRESENT-80, а DM-PRESENT-128 - на PRESENT-128. Данная хеш-функция уязвима к коллизиям и не является стойкой к восстановлению вторых прообразов, такие хеш-функции будут полезны только в приложениях, которым требуется стойкость к восстановлению первого прообраза и 64-битная защита.

ARMADILLO

ARMADILLO[19] - это многоцелевой примитив, предназначенный для использования в качестве FIL-MAC (приложение I), для хеширования и цифровых подписей (приложение II), а также для PRNG и PRF (приложение III). Он был взломан Найей-Пласенсией и Пейрином[20]. Они нашли способ быстро обнаруживать коллизии, когда он используется в качестве хеш-функции (несколько секунд на обычном ПК).

См. также


Литература

  1. ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche. The Making of KECCAK // Cryptologia. — 2014-01-02. — Т. 38, вып. 1. — С. 26–60. — ISSN 1558-1586 0161-1194, 1558-1586. — doi:10.1080/01611194.2013.856818.
  2. ↑ Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl // Fast Software Encryption. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. — С. 260–276. — ISBN 9783642033162, 9783642033179.
  3. ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche. Sponge-Based Pseudo-Random Number Generators // Cryptographic Hardware and Embedded Systems, CHES 2010. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. — С. 33–47. — ISBN 9783642150302, 9783642150319.
  4. ↑ EM submission PDF. dx.doi.org. Дата обращения: 15 ноября 2019.
  5. ↑ Thierry P. Berger, Joffrey D’Hayer, Kevin Marquet, Marine Minier, Gaël Thomas. The GLUON Family: A Lightweight Hash Function Family Based on FCSRs // Progress in Cryptology - AFRICACRYPT 2012. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. — С. 306–323. — ISBN 9783642314094, 9783642314100.
  6. ↑ Franc̨ois Arnault, Thierry Berger, Cédric Lauradoux, Marine Minier, Benjamin Pousse. A New Approach for FCSRs // Selected Areas in Cryptography. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. — С. 433–448. — ISBN 9783642054433, 9783642054457.
  7. ↑ Jean-Philippe Aumasson, Luca Henzen, Willi Meier, María Naya-Plasencia. Quark: A Lightweight Hash // Journal of Cryptology. — 2012-05-10. — Т. 26, вып. 2. — С. 313–339. — ISSN 1432-1378 0933-2790, 1432-1378. — doi:10.1007/s00145-012-9125-6.
  8. ↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. KATAN and KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers // Lecture Notes in Computer Science. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. — С. 272–288. — ISBN 9783642041372, 9783642041389.
  9. ↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. KATAN and KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers // Lecture Notes in Computer Science. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. — С. 272–288. — ISBN 9783642041372, 9783642041389.
  10. ↑ Martin Hell, Thomas Johansson, Alexander Maximov, Willi Meier. A Stream Cipher Proposal: Grain-128 // 2006 IEEE International Symposium on Information Theory. — IEEE, 2006-07. — ISBN 142440505X, 1424405041. — doi:10.1109/isit.2006.261549.
  11. ↑ Jean-Philippe Aumasson, Daniel J. Bernstein. SipHash: A Fast Short-Input PRF // Lecture Notes in Computer Science. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. — С. 489–508. — ISBN 9783642349300, 9783642349317.
  12. ↑ Jian Guo, Thomas Peyrin, Axel Poschmann. The PHOTON Family of Lightweight Hash Functions // Advances in Cryptology – CRYPTO 2011. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. — С. 222–239. — ISBN 9783642227912, 9783642227929.
  13. ↑ Joan Daemen, Vincent Rijmen. Rijndael/AES // Encyclopedia of Cryptography and Security. — Springer US. — С. 520–524. — ISBN 9780387234731.
  14. ↑ Jian Guo, Thomas Peyrin, Axel Poschmann, Matt Robshaw. The LED Block Cipher // Cryptographic Hardware and Embedded Systems – CHES 2011. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. — С. 326–341. — ISBN 9783642239502, 9783642239519.
  15. ↑ Andrey Bogdanov, Miroslav Knežević, Gregor Leander, Deniz Toz, Kerem Varıcı. spongent: A Lightweight Hash Function // Cryptographic Hardware and Embedded Systems – CHES 2011. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. — С. 312–325. — ISBN 9783642239502, 9783642239519.
  16. ↑ Mohamed Ahmed Abdelraheem. Estimating the Probabilities of Low-Weight Differential and Linear Approximations on PRESENT-Like Ciphers // Lecture Notes in Computer Science. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. — С. 368–382. — ISBN 9783642376818, 9783642376825.
  17. ↑ Joan Daemen, Vincent Rijmen. Rijndael/AES // Encyclopedia of Cryptography and Security. — Springer US. — С. 520–524. — ISBN 9780387234731.
  18. ↑ Information about PhD thesis at the Civil Engineering Faculty and the Mechanical Engineering Faculty of Wroclaw University of Technology // Archives of Civil and Mechanical Engineering. — 2008-01. — Т. 8, вып. 2. — С. 181–183. — ISSN 1644-9665. — doi:10.1016/s1644-9665(12)60205-2.
  19. ↑ Stéphane Badel, Nilay Dağtekin, Jorge Nakahara, Khaled Ouafi, Nicolas Reffé. ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware // Cryptographic Hardware and Embedded Systems, CHES 2010. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. — С. 398–412. — ISBN 9783642150302, 9783642150319.
  20. ↑ María Naya-Plasencia, Thomas Peyrin. Practical Cryptanalysis of ARMADILLO2 // Fast Software Encryption. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. — С. 146–162. — ISBN 9783642340468, 9783642340475.
Источник — https://ru.wikipedia.org/w/index.php?title=Хеш-функция_облегчённой_криптографии&oldid=103347620