Криптографические хэш функции: Криптографическая хеш-функция — Википедия – Криптографическая хеш-функция

Содержание

Криптографическая хеш-функция

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

Правильная криптографическая хеш-функция заключает в себе следующие особо важные характеристики:

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

Цифровая подпись – информация, которая защищена секретным ключом и привязана к исходному тексту. Для проверки достоверности подписи используется открытый ключ, с помощью которого расшифровывается подписанный текст. В том случае, если раскрытые данные аналогичны исходному тексту, подпись считается верной.

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

  •         повышение криптостойкости;
  •         снижение сложности процесса;
  •         обеспечение совместимости.
Применение криптографических хеш-функций при аутентификации парольной фразы

Как правило, парольные фразы удаляются из внутренней памяти целевых объектов, сохраняя только хеш-значения. Хранить парольные фразы – небезопасно. В случае, если путем хакерской атаки удастся взломать файл, содержащий парольные фразы, появляется возможность беспрепятственно воспользоваться полученной информацией. Несанкционированный доступ к данным, содержащим лишь хеш-значения, не даёт возможности получить ценную информацию, так как исходный вид парольной фразы невозможно восстановить. Хеш-значения хранятся только для аутентификации пароля, имеющегося в базе данных той или иной криптовалютной системы.

Наиболее распространенные криптографические хеш-функции

На данный момент применяются следующие криптографические хеш-функции:

  • MD5 – один из самых распространённых алгоритмов, являющийся криптографической хеш-функцией, размер которой составляет 128 бит. В ближайшее время готовится обновление версии, так как она уже не соответствует высоким стандартам криптоустойчивости.
  • ГОСТ Р 34.11-94 – отечественная криптографическая хеш-функция, генерирующая дайджест длиной 256 бит.
  • ГОСТ Р 34.11-2012 – обновлённая версия, отличающаяся высокой стойкостью к попыткам взлома и стабильностью в работе. Объем выдаваемого хеша может быть как 512, так и 256 бит. Как правило, применяется в системе государственного документооборота, создавая электронные подписи.
  • SHA-1 – криптографическая хеш-функция, преобразующая информацию в строку, длина которой равняется 160 битам. Не обладает достаточным уровнем криптоустойчивости.
  • SHA-2 – криптографическая хеш-функция, созданная на основе алгоритмов SHA: 224; 256; 384; 512; 512/256; 512/224. Несмотря на высокую стойкость к взлому, данный алгоритм используется крайне редко. Причина – неудачный результат одного из криптоанализов, во время которого было выявлено критическое количество коллизий (повторений хеша). Разработчики намерены создать новую криптографическую хеш-функцию SHA-3, которая будет основана на алгоритме Keccak.
Уровень сложности

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

Будьте в курсе всех важных событий United Traders — подписывайтесь на наш телеграм-канал

о хеш-функциях, ключах и цифровых подписях / Bitfury Group corporate blog / Habr

Криптография — это сердце блокчейна, которое обеспечивает работу системы. Архитектура блокчейна предполагает, что доверие между участниками сети базируется на принципах математики и экономики, то есть является формализованным. Криптография также гарантирует безопасность, причем основанную на прозрачности и проверяемости всех операций, а не на традиционном для индустрии ограничении видимости системы (perimeter security).

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


/ изображение BTC Keychain CC

Хеш-функции


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

Хеш-функции имеются практически в любом языке программирования. Например, они используются для реализации хеш-таблиц и множеств (HashMap/HashSet в Java, dict и set в Python, Map, Set и объекты в JavaScript и так далее). Отдельная категория хеш-функций — криптографические хеш-функции. К ним предъявляются существенно более строгие требования, чем к функциям, обычно используемым в хеш-таблицах. Поэтому и применяются они в более «серьезных» случаях, например для хранения паролей. Криптографические хеш-функции вырабатываются и тщательно проверяются исследователями по всему миру.

Поэкспериментировать с хеш-функциями можно, написав простую программу на Python:

import hashlib
def hash_hex(message):
    return hashlib.sha256(message.encode()).hexdigest()

Функция hash_hex() рассчитывает представление хеша в шестнадцатеричной записи для строки. В приведенном примере используется функция SHA-256 — та же, что и в биткойне.

Хорошая хеш-функция обеспечивает защиту от коллизий (невозможно получить два одинаковых хеша при разных начальных данных) и обладает так называемым эффектом лавины, когда малейшее изменение входных данных значительно преобразует выходное значение. Эффект лавины в хеш-функции SHA-256 выглядит следующим образом:

>>> hash_hex('Blockchain')
'625da44e4eaf58d61cf048d168aa6f5e492dea166d8bb54ec06c30de07db57e1'
>>> hash_hex('blockchain')
'ef7797e13d3a75526946a3bcf00daec9fc9c9c4d51ddc7cc5df888f74dd434d1'
>>> hash_hex('Bl0ckchain')
'511429398e2213603f4e5dd3fff1f989447c52162b0e0a28fe049288359220fc'

Хеш-функции в блокчейнах гарантируют «необратимость» всей цепочки транзакций. Дело в том, что каждый новый блок транзакций ссылается на хеш предыдущего блока в реестре. Хеш самого блока зависит от всех транзакций в блоке, но вместо того, чтобы последовательно передавать транзакции хеш-функции, они собираются в одно хеш-значение при помощи двоичного дерева с хешами (дерево Меркла). Таким образом, хеши используются как замена указателям в обычных структурах данных: связанных списках и двоичных деревьях.

За счет использования хешей общее состояние блокчейна — все когда-либо выполненные транзакции и их последовательность — можно выразить одним-единственным числом: хешем самого нового блока. Поэтому свойство неизменности хеша одного блока гарантирует неизменность всего блокчейна.


Ниже приведена рекурсивная реализация дерева Меркла, используемая в биткойне, на языке Python (по ссылке вы найдете примеры работы). На вход функции подается список хешей транзакций. На каждом этапе вычисления последовательные пары хешей склеиваются при помощи хеш-функции; если хешей нечетное число, то последний дублируется. В результате остается единственный хеш, который и является конечным хеш-значением для всего списка.
import hashlib
    
def merkle_root(lst):
    # Биткойн использует для склеивания хешей два прогона SHA-256 и изменение 
    # порядка байтов. Зачем, не до конца понятно.
    sha256d = lambda x: hashlib.sha256(hashlib.sha256(x).digest()).digest()
    hash_pair = lambda x, y: sha256d(x[::-1] + y[::-1])[::-1]

    if len(lst) == 1: return lst[0]
    
    # Дублирование элементов в дереве приводит к интересной уязвимости -
    # получается, что различные списки транзакций могут иметь один и тот же хеш.
    # По этой причине в биткойне даже есть специальный комментарий,
    # предостерегающий разработчиков новых криптовалют:
    # https://github.com/bitcoin/bitcoin/blob/master/src/consensus/merkle.cpp#L9
    if len(lst) % 2 == 1:
        lst.append(lst[-1])
    return merkle_root([ hash_pair(x, y) 
        for x, y in zip(*[iter(lst)] * 2) ])

Хеш-деревья имеют много применений помимо блокчейнов. Они используются в файловых системах для проверки целостности файлов, распределенных БД для быстрой синхронизации копий и в управлении ключами для надежного журналирования выдачи сертификатов. Git использует обобщение хеш-деревьев — направленные ациклические графы на основе хешей. В блокчейне использование хеш-деревьев продиктовано соображениями производительности, так как они делают возможным существование «легких клиентов», которые обрабатывают лишь малую часть транзакций из блокчейна.

Цифровые подписи


Цифровые подписи в блокчейнах базируются на криптографии с открытым ключом. В ней используются два ключа. Первый — закрытый ключ — нужен для формирования цифровых подписей и хранится в секрете. Второй — открытый ключ — используется для проверки электронной подписи. Открытый ключ реально вычислить на основе закрытого ключа, а вот обратное преобразование требует невозможного на практике объема вычислений, сравнимого с брут-форсом.
Существует множество различных схем криптографии с открытым ключом. Две самые популярные из них — это схемы на основе разложения на множители (RSA) и схемы на основе эллиптических кривых. Последние более популярны в блокчейнах из-за меньшего размера ключей и подписей. Например, в биткойне используется стандарт эллиптической криптографии ECDSA вместе с эллиптической кривой secp256k1. В ней закрытый ключ имеет длину 32 байта, открытый — 33 байта, а подпись — около 70 байт.
Общая идея подписей с открытым ключом выглядит следующим образом. Предположим, что Алиса хочет перевести Бобу один биткойн. Для этого она формирует транзакцию, где записывает, откуда его следует брать (указание на предыдущую транзакцию, в которой Алиса получила биткойн от кого-то еще) и кому отправить (открытый ключ Боба). Алиса знает открытый ключ Боба из сторонних источников — Боб может послать его Алисе через мессенджер или даже опубликовать его на сайте.

Затем Алиса подписывает транзакцию, используя свой секретный ключ. Любой узел в биткойн-сети может проверить, что транзакция подписана определенным открытым ключом (аутентификация), с которым до выполнения транзакции был ассоциирован один биткойн (авторизация). Если эти условия выполнены, то переведенный биткойн начинает ассоциироваться с открытым ключом Боба.

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

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



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

P.P.S. Немного дополнительных источников:


Хеш-функция облегчённой криптографии — Википедия

Хеш-функция облегчённой криптографии — криптостойкая хеш-функция, используемая в «легковесной» криптографии[1][⇨]. В настоящее время актуальность таких хеш-функций резко возросла из-за возможности использовать их во многих сферах деятельности (от RFID до Интернета вещей) и на стыке дисциплин (Блокчейн и IoT)[⇨]. В виду специфики использования данных хеш-функций, на них накладываются дополнительные требования[⇨]. Большинство современных хеш-функций в качестве своей основы используют структуру Меркла — Дамгора[⇨] и функцию губки[⇨].

Облегчённая криптография — раздел криптографии, в котором рассматриваются алгоритмы для устройств, не обладающих достаточными ресурсами для реализации существующих шифров, хеш-функций, электронных подписей и т. д.[2] «Легковесная» криптография приобрела исключительную актуальность в настоящее время в связи распространением парадигмы умного дома, где множество приборов небольшого размера, с ограниченной вычислительной мощностью, лимитированным объёмом памяти и малым энергопотреблением коммуницируют между собой, обмениваясь конфиденциальной информацией жильца, для выполнения своих задач[3][4]. Также особый интерес представляют алгоритмы для RFID меток[5]. Для того, чтобы злоумышленики не воспользовались приватной информацией пользователя, требуется специальная разработка и оптимизация алгоритмов способных работать при ограниченных ресурсах и обеспечивать должный уровень безопасности[6].

Применение[править | править код]

Для того, чтобы адресату убедиться в том, что ему было прислано сообщение от настоящего адресанта, оно отправляется вместе с электронной подписью. На практике подписывают не сообщение, а его хеш-сумму, это позволяет значительно уменьшить вычислительные ресурсы на создание подписи (так как обычно хеш-сумма на порядки меньше ключа) и повысить криптостойкость (злоумышленник не сможет узнать исходные данные только из хеша)[7]. Хеш-функции используются в технологии блокчейн для того, чтобы определить блок, который добавится в общую цепь. Например: для добавления нового блока в платформу Bitcoin требуется найти хеш-сумму SHA-256 меньше, чем определённое целевое число. В следующий созданный блок будет записан хеш предыдущего[8]. Более того, хеш-функции, в частности хеш-функции облегчённой криптографии могут применяться на стыке дисциплин. Например: они применяются в блокчейне LSB, который предназначен для использования в интернете вещей[9].

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

Требования[править | править код]

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

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

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

Атаки на хеш-функции[править | править код]

  1. Атака «дней рождения» — используется для поиска коллизии второго рода, эксплуатирует парадокс дней рождения. Для успешной атаки число обращений к хеш-функции должно составлять примерно 2n2{\displaystyle 2^{\frac {n}{2}}}, а квантовым компьютерам 2n3{\displaystyle 2^{\frac {n}{3}}}[14]
  2. Кубическая атака (англ. Cube attack) — эффективна для атак на хеш-функций и шифров, которые используют LFSR[15]
  3. Линейная атака (англ. Linear cryptanalysis) — разработана для хеш-функций, использующих блочные и потоковые шифры[16]
  4. Дифференциальные атаки (англ. Differential cryptanalysis) — действенны для хеш-функций с блочными шифрами[17]
  5. Атака методом бумеранга — усовершенствованная дифференциальная атака, которая успешно применяется к хеш-функциям[18]. Так, например, для нахождения коллизий SHA-0 с помощью этой атаки потребовался всего лишь один час на обычном ПК[19]
  6. Атака удлинением сообщения — применяется для хеш-функций, основанных на структуре Меркла — Дамгора[20]. Суть атаки заключается в добавлении новых битов в конец сообщения. Среди уязвимых функций: MD5 и SHA-1[21][22]
  7. Мультиколлизионная атака Жу[23] — направлена на хеш-функции, использующие в качестве своей основы функцию губки, которая распространена среди функций облегчённой криптографии
  8. Rebound атака — предназначена для AES-подобных алгоритмов[24]
  9. Ротационная атака (англ. Rotational cryptanalysis) — создана для взлома хеш-функций, основанных на ARX (сравнение по модулю-битовый сдвиг-XOR)[25]

Меркл — Дамгор[править | править код]

Основная идея[править | править код]

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

m=123456789{\displaystyle m=123456789},

то на вход мы подаём 2{\displaystyle 2} блока:

1234567891000000{\displaystyle 12345678\quad 91000000},

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

  • c0=IV{\displaystyle c_{0}=IV}
  • ci+1=h(ci,mi){\displaystyle c_{i+1}=h(c_{i},m_{i})}
  • H(m)=d=cL{\displaystyle H(m)=d=c_{L}}
Усовершенствованный алгоритм[править | править код]

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

123456789100000000000009{\displaystyle 12345678\quad 91000000\quad 00000009}

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

1234567891000009{\displaystyle 12345678\quad 91000009}

Функция губки[править | править код]

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

Основная идея[править | править код]

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

Далее следуют 2{\displaystyle 2} стадии:

  1. Абсорбция
    • Первые r{\displaystyle r} бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
    • Внутреннее состояние обрабатывается функцией перестановки
  1. Выжимание
    • Считываются первые r{\displaystyle r} бит внутреннего состояния губки
    • Внутреннее состояние обрабатывается функцией перестановки[30][31]
П-губка и Т-губка[править | править код]

П(ерестановочная)-губка и Т(рансформационная)-губка — губки, использующие соответственно случайную перестановку и ГПСЧ для обновления своего внутреннего состояния. В статье, в которой были введены функции губки, было показано, что губки с мощностью c{\displaystyle c}, битовой скоростью r{\displaystyle r} и вектором размера n{\displaystyle n}, принимающие на вход сообщения длиной m<2c2{\displaystyle m<2^{\frac {c}{2}}}, таковы, что для различных атак в среднем требуется следующее количество обращений к функциям обновлении(приведены степени двойки)[32]:

Губка Первый прообраз Второй прообраз Коллизия Нахождение цикла
T-губка min(n,c+r){\displaystyle \min(n,c+r)} min(n,c−log2⁡(m)){\displaystyle \min(n,c-\log _{2}(m))} min(n,c)/2{\displaystyle \min(n,c)/2} (c+r)/2{\displaystyle (c+r)/2}
П-губка c−1{\displaystyle c-1} min(n,c/2){\displaystyle \min(n,c/2)} min(n,c)/2{\displaystyle \min(n,c)/2} c+r{\displaystyle c+r}
JH-губка[править | править код]

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

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

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

Примеры хеш-функций в облегчённой криптографии[править | править код]

GLUON[править | править код]

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

Функция обладает высокой криптографической стойкостью. Например: атака нахождения прообраза в общем случае имеет сложность 23ωr2{\displaystyle 2^{\frac {3\omega r}{2}}} , где ω×ω{\displaystyle \omega \times \omega } — размер матрицы T{\displaystyle T} (которая определяет FCSR), а r{\displaystyle r} - размер слова, подаваемого на FCSR.

Особенность реализации GLUON состоит в том, что данные в FCSR записываются не последовательно, а параллельно, что значительно повышает скорость исполнения. Также был оптимизирован adder (элемент, осуществляющий сложение), который используется в FCSR, следующим образом: s=(a⊕b)⊕c{\displaystyle s=(a\oplus b)\oplus c}, где c=(a.b)⊕(a⊕b).c{\displaystyle c=(a.b)\oplus (a\oplus b).c} (здесь .{\displaystyle .} используется в качестве обозначения логического И)[35].

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

QUARK[править | править код]

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

Функция обновления отображает вектор {0,1}b{\displaystyle \{0,1\}^{b}} в {0,1}b{\displaystyle \{0,1\}^{b}}, загружая каждую половину в отдельный NFSR (англ. Nonlinear-feedback shift register) длины b2{\displaystyle {\frac {b}{2}}}, а затем повторяет это 4b{\displaystyle 4b} раза. NFSR связаны друг с другом и с небольшим LFSR длины log⁡(4b){\displaystyle \log(4b)}. Функции f{\displaystyle f}, g{\displaystyle g} и h{\displaystyle h} являются булевыми функциями, выбранными из-за их нелинейности и алгебраической сложности. f{\displaystyle f} и g{\displaystyle g} одинаковы для всех версий и заимствованы из Grain-v1, а h{\displaystyle h} определяется отдельным случаем.

Специфика реализации QUARK состоит в том, что в ней отсутствуют промежуточные значения функции губки, которые требуют дополнительных элементов для их запоминания. Другими словами, после перестановки значений состояния значения не записываются в следующее состояние, а сразу подаются на функцию перестановки, причём первые r{\displaystyle r} бит делают XOR с сообщением[39].

Обладает высокой криптостойкостью. Данные по резистентности к различным атакам приведены ниже[40]:

Сложность успешной атаки для нахождения:
Коллизии Первого прообраза Второго прообраза
2c2{\displaystyle 2^{\frac {c}{2}}} 2c{\displaystyle 2^{c}} 2c2{\displaystyle 2^{\frac {c}{2}}}

У данной хеш-функции есть реализация в открытом доступе, написанная на языке C.

SipHash-2-4[править | править код]

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

Отличительная черта SipHash состоит в том, что сообщения «ксорятся», не как в обычной функции губки, а по особому алгоритму:

  • Первое сообщение ксорится с последней четвертью губки
  • Губка обрабатывается двумя функциями перестановки
  • Первое сообщение снова ксорится, но уже с первой четвертью губки, в то время, как второе сообщение с последней
  • Губка обрабатывается двумя функциями перестановки
  • Второе сообщение ксорится с первой четвертью губки, а третья четверть ксорится с 0xFF

Несмотря на то, что в основе SipHash лежит ARX, не является уязвимой к ротационной атаке[41].

Существуют материалы по применению SipHash на github в открытом доступе.

PHOTON[править | править код]

PHOTON представляет собой P-губку, основанную на AES-подобной[42] перестановке. Для наименьшего параметра безопасности (PHOTON-80/20/16) битовая скорость во время абсорбции равна 20 и равна 16 во время выжимания. Перестановка состоит из 12 итераций (для каждого параметра безопасности) ниже описанной последовательности преобразований, выполненных на квадрате d×d{\displaystyle d\times 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){\displaystyle {\displaystyle GF(2^{4})}} (или GF(28){\displaystyle GF(2^{8})} для наибольшего параметра безопасности), и каждый столбец умножается на матрицу MDS, специально созданной для эффективной реализации в аппаратном обеспечении[43].

Данные по криптостойкости:

Сложность успешной атаки для нахождения:
Коллизии Первого прообраза Второго прообраза
2n2{\displaystyle 2^{\frac {n}{2}}} 2n−r{\displaystyle 2^{n-r}} 2n2{\displaystyle 2^{\frac {n}{2}}}

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

SPONGENT[править | править код]

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

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

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

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

Код SPONGENT на ассемблере и Си есть в открытом доступе.

SPN-Hash[править | править код]

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

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

DM-PRESENT[править | править код]

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

ARMADILLO[править | править код]

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

  1. Poschmann, Axel York. Lightweight cryptography : cryptographic engineering for a pervasive world. — Europ. Univ.-Verl, 2009. — ISBN 978-3-89966-341-9, 3-89966-341-1.
  2. Kerry A McKay, Larry Bassham, Meltem Sonmez Turan, Nicky Mouha. Report on lightweight cryptography. — Gaithersburg, MD: National Institute of Standards and Technology, 2017-03.
  3. Megha Agrawal, Jianying Zhou, Donghoon Chang. A Survey on Lightweight Authenticated Encryption and Challenges for Securing Industrial IoT // 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.

Безопасность криптографических хеш-функций — Википедия

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

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

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

  • Сопротивление поиску первого прообраза: при наличии хеша h{\displaystyle h} должно быть трудно найти какое-либо сообщение m{\displaystyle m}, такое что h=hash(m){\displaystyle h=hash(m)}, Это свойство связано с понятием односторонней функции. Функции, у которых отсутствует это свойство, уязвимы для атак нахождения первого прообраза.
  • Сопротивление поиску второго прообраза: при наличии сообщения m1{\displaystyle m_{1}}, должно быть трудно найти другое сообщение m2{\displaystyle m_{2}} (не равное m1{\displaystyle m_{1}}) такое, что hash(m1)=hash(m2){\displaystyle hash(m_{1})=hash(m_{2})}. Это свойство иногда называют слабым сопротивлением поиску коллизий. Функции, у которых отсутствует это свойство, уязвимы для атак поиска второго прообраза.
  • Сопротивление поиску коллизий: должно быть трудно найти два разных сообщения m1{\displaystyle m_{1}} и m2{\displaystyle m_{2}}, таких что hash(m1)=hash(m2){\displaystyle hash(m_{1})=hash(m_{2})}. Такая пара называется (криптографической) хеш-коллизией. Это свойство иногда называют сильным сопротивлением поиску коллизий. Требуется хеш-значение, по крайней мере, вдвое длиннее, чем требуемое для сопротивления поиску первого прообраза, в противном случае столкновения могут быть обнаружены атакой "дней рождения".
  • Псевдослучайность: должно быть трудно отличить генератор псевдослучайных чисел на основе хеш-функции от генератора случайных чисел, например, он проходит обычные тесты на случайность.

Значение понятия "трудно"[править | править код]

Основной вопрос - значение понятия "трудно". Есть два подхода к ответу на этот вопрос. Во-первых, это интуитивно-практический подход: «трудно означает, почти наверняка недосягаемо для любого противника, которому должно быть позволено взломать систему до тех пор, пока безопасность системы считается важной».

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

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

Безопасность хеш-функции может обеспечиваться сложностью некоторой математической задачи при наличии доказательства, что атаки, направленные на нарушение требований к ней, настолько же сложны, насколько и решение этой задачи.[1]

Криптографическая хеш-функция является доказуемо защищённой от коллизий, если задача нахождения коллизий может быть средуцирована за полиномиальное время[en] от задачи P{\displaystyle P}, которая считается неразрешимой за полиномиальное время. Иначе говоря, если алгоритм A{\displaystyle A} позволял бы за полиномиальное время решить задачу нахождения коллизий при существовании редуцирующего алгоритма R{\displaystyle R}, работающего также за полиномиальное время, то последний позволил бы алгоритму A{\displaystyle A} решить задачу P{\displaystyle P} за полиномиальное время, что противоречит её сложности, а значит задача нахождения коллизий не легче задачи P{\displaystyle P}.

Аналогично определяется доказуемая защищённость от поиска первого и второго прообраза.

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

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

Недостатки доказательного подхода[править | править код]

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

  • Текущие доказуемо безопасные алгоритмы хеширования слишком вычислительно сложны для того, чтобы использоваться на практике. По сравнению с обычными хеш-функциями они достаточно медленные.
  • Создание доказуемо безопасных хеш-функций значительно более трудоёмко, чем классические подходы.
  • Само доказательство безопасности часто основывается на задаче, имеющей требуемую сложность в среднем или в худшем случае. Сложность в худшем случае чаще всего описывает патологические ситуации, а не типичные для этой задачи. Даже редукция к задаче со сложностью в среднем обеспечивает ограниченную защищённость, так как может быть найден алгоритм, который легко решает проблему для определённого подмножества данных задачи. Так, например, было показано, что для двух из трёх предложенных в оригинальной статье для функции Fast Syndrome-Based hash параметров существуют более оптимальные атаки, чем предложенные создателями для доказательства безопасности.[3]

SWIFFT является примером хеш-функции, которая несколько обходит описанную проблему безопасности. Может быть показано, что для любого алгоритма, который взламывает SWIFFT с вероятностью P{\displaystyle P} за время T{\displaystyle T} найдётся алгоритм, который решает определённую математическую задачу в худшем случае за время T′{\displaystyle T'} в зависимости от P{\displaystyle P} и T{\displaystyle T}.[4]

Примеры доказуемо безопасных хеш-функции[править | править код]

  • VSH - Very Smooth Hash function - доказуемо безопасная устойчивая к коллизиям функция, опирающаяся на сложность нахождения нетривиальных квадратных корней по модулю составного числа n (что является настолько же сложным, насколько разложение n на множители).
  • MuHASH
  • ECOH - Elliptic curve only hash - основанная на идее эллиптических кривых, задаче о сумме подмножеств и суммировании полиномов хеш-функция. Доказательство безопасности опиралось на предположение о NP-полноте лежащей в основе математической задачи, однако была найдена уязвимость для обобщённой атаки "дней рождения" Вагнера, связанной с поиском второго прообраза.
  • FSB - Fast Syndrome-Based hash function - может быть показано, что взломать FSB по меньшей мере настолько же трудно, насколько решить NP-полную задачу, известную как регулярное синдромное декодирование.
  • SWIFFT - SWIFFT основан на БПФ и доказуемо безопасен при довольно слабом предположении о сложности нахождения коротких векторов в циклической/идеальной решетке в худшем случае.
  • Chaum, van Heijst, Pfitzmann hash function - функция, в которой нахождение коллизий так же трудоёмко, как и при нахождении дискретного логарифма в конечной группе .
  • Knapsack-based hash functions - семейство хеш-функций, основанное на задаче о рюкзаке.
  1. Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. A Fast Provably Secure Cryptographic Hash Function. — 2003. — № 230. — С. 3-4.
  2. Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. A Fast Provably Secure Cryptographic Hash Function. — 2003. — № 230. — С. 3.
  3. Jean-Sebastien Coron, Antoine Joux. Cryptanalysis of a Provably Secure Cryptographic Hash Function. — 2004. — № 013. — С. 1,3.
  4. Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: A Modest Proposal for FFT Hashing (англ.) // Fast Software Encryption. — Springer, Berlin, Heidelberg, 2008-02-10. — P. 65. — ISBN 9783540710387, 9783540710394. — doi:10.1007/978-3-540-71039-4_4.

Криптографические хеш-функции Википедия

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

Принципы построения[ | ]

Итеративная последовательная схема[ | ]

В общем случае в основе построения хеш-функции лежит итеративная последовательная схема. Ядром алгоритма является сжимающая функция — преобразование k входных в n выходных бит, где n — разрядность хеш-функции, а k — произвольное число, большее n. При этом сжимающая функция должна удовлетворять всем условиям криптостойкости.

Входной поток разбивается на блоки по (k − n) бит. Алгоритм использует вре́менную переменную размером в n бит, в качестве начального значения которой берется некое общеизвестное число. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Значением хеш-функции являются выходные n бит последней итерации. Каждый бит выходного значения хеш-функции зависит от всего входного потока данных и начального значения. Таким образом достигается лавинный эффект.

При проектировании хеш-функций на основе итеративной схемы возникает проблема с размером входног

Хэш-алгоритмы / Habr

Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.

О себе

Студент кафедры информационной безопасности.
О хэшировании

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

Хэш-функцией называется всякая функция h:X -> Y, легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину. X — множество всех сообщений, Y — множество двоичных векторов фиксированной длины.

Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x1, x2) двух переменных, где x1, x2 и y — двоичные векторы длины m, n и n соответственно, причем n — длина свертки, а m — длина блока сообщения.
Для получения значения h(M) сообщение сначала разбивается на блоки длины m (при этом, если длина сообщения не кратна m то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M1, M2,.., MN применяют следующую последовательную процедуру вычисления свертки:

Ho = v,
Hi = f(Mi,Hi-1), i = 1,.., N,
h(M) = HN

Здесь v — некоторая константа, часто ее называют инициализирующим вектором. Она выбирается
из различных соображений и может представлять собой секретную константу или набор случайных данных (выборку даты и времени, например).
При таком подходе свойства хэш-функции полностью определяются свойствами одношаговой сжимающей функции.

Выделяют два важных вида криптографических хэш-функций — ключевые и бесключевые. Ключевые хэш-функции называют кодами аутентификации сообщений. Они дают возможность без дополнительных средств гарантировать как правильность источника данных, так и целостность данных в системах с доверяющими друг другу пользователями.
Бесключевые хэш-функции называются кодами обнаружения ошибок. Они дают возможность с помощью дополнительных средств (шифрования, например) гарантировать целостность данных. Эти хэш-функции могут применяться в системах как с доверяющими, так и не доверяющими друг другу пользователями.

О статистических свойствах и требованиях

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

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

Первое требование означает высокую сложность подбора сообщения с правильным значением свертки. Второе — высокую сложность подбора для заданного сообщения с известным значением свертки другого сообщения с правильным значением свертки.

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

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

Это была теоретическая часть, которая пригодится нам в дальнейшем…

О популярных хэш-алгоритмах

Алгоритмы CRC16/32 — контрольная сумма (не криптографическое преобразование).

Алгоритмы MD2/4/5/6. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
Алгоритм MD6 — очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.

Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 — собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.

Российский стандарт — ГОСТ 34.11-94.

В следующей статье

Обзор алгоритмов MD (MD4, MD5, MD6).

Литература

А. П. Алферов, Основы криптографии.

Брюс Шнайер, Прикладная криптография.

Криптографическая хэш-функция Википедия

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

Принципы построения[ | ]

Итеративная последовательная схема[ | ]

В общем случае в основе построения хеш-функции лежит итеративная последовательная схема. Ядром алгоритма является сжимающая функция — преобразование k входных в n выходных бит, где n — разрядность хеш-функции, а k — произвольное число, большее n. При этом сжимающая функция должна удовлетворять всем условиям криптостойкости.

Входной поток разбивается на блоки по (k − n) бит. Алгоритм использует вре́менную переменную размером в n бит, в качестве начального значения которой берется некое общеизвестное число. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Значением хеш-функции являются выходные n бит последней итерации. Каждый бит выходного значения хеш-функции зависит от всего входного потока данных и начального значения. Таким образом достигается лавинный эффект.

При проектировании хеш-функций на основе итеративной схемы возникает проблема с размером входног

Отправить ответ

avatar
  Подписаться  
Уведомление о