Криптографические хеш-функции: свойства и применение

Введение

Хеш-функция, пригодная для использования в криптографии

Криптографическая хеш-функция (CHF) — это хеш-алгоритм (отображение произвольной двоичной строки в двоичную строку фиксированного размера в битах), обладающий специальными свойствами, необходимыми для криптографических приложений: вероятность получения конкретного битового результата (хеш-значения) для случайной входной строки ("сообщения") равна (как и для любой хорошей хеш-функции), поэтому хеш-значение можно использовать как репрезентацию сообщения; поиск входной строки, соответствующей заданному хеш-значению (прообраза), невозможен, при условии, что все входные строки равновероятны. Устойчивость к такому поиску количественно оценивается как криптографическая стойкость. Ожидается, что криптографический хеш с хеш-значением в битов будет иметь стойкость к поиску прообраза в битов, если пространство возможных входных значений значительно меньше, чем (практический пример можно найти в ); стойкость ко второму прообразу, при тех же ожиданиях, относится к аналогичной задаче – поиску второго сообщения, соответствующего заданному хеш-значению, когда одно сообщение уже известно; поиск любой пары различных сообщений, дающих одно и то же хеш-значение (коллизия), также невозможен. Ожидается, что криптографический хеш будет иметь стойкость к коллизиям в битов (меньшую из-за парадокса дней рождения). Криптографические хеш-функции имеют множество применений в области информационной безопасности, в частности, в цифровых подписях, кодах аутентификации сообщений (MAC) и других формах аутентификации. Они также могут использоваться как обычные хеш-функции для индексации данных в хеш-таблицах, для создания цифровых отпечатков, для обнаружения дубликатов данных или уникальной идентификации файлов, а также в качестве контрольных сумм для обнаружения случайной порчи данных. В контексте информационной безопасности криптографические хеш-значения иногда называют (цифровыми) отпечатками, контрольными суммами или просто хешами, хотя все эти термины относятся к более общим функциям с существенно различными свойствами и целями. Некриптографические хеш-функции используются в хеш-таблицах и для обнаружения случайных ошибок, и их конструкция часто не обеспечивает устойчивости к преднамеренным атакам. Например, атака типа "отказ в обслуживании" на хеш-таблицы возможна, если коллизии легко найти, как в случае с линейными циклическими функциями проверки избыточности (CRC).

A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with a fixed size of bits) that has special properties desirable for a cryptographic application:
the probability of a particular bit output result (hash value) for a random input string ("message") is (as for any good hash), so the hash value can be used as a representative of the message;
finding an input string that matches a given hash value (a pre image) is unfeasible, assuming all input strings are equally likely. The resistance to such search is quantified as security strength, a cryptographic hash with bits of hash value is expected to have a preimage resistance strength of bits, unless the space of possible input values is significantly smaller than (a practical example can be found in );
A second preimage resistance strength, with the same expectations, refers to a similar problem of finding a second message that matches the given hash value when one message is already known;
finding any pair of different messages that yield the same hash value (a collision) is also unfeasible, a cryptographic hash is expected to have a collision resistance strength of bits (lower due to the birthday paradox). Cryptographic hash functions have many information security applications, notably in digital signatures, message authentication codes (MACs), and other forms of authentication. They can also be used as ordinary hash functions, to index data in hash tables, for fingerprinting, to detect duplicate data or uniquely identify files, and as checksums to detect accidental data corruption. Indeed, in information security contexts, cryptographic hash values are sometimes called (digital) fingerprints, checksums, or just hash values, even though all these terms stand for more general functions with rather different properties and purposes. Non cryptographic hash functions are used in hash tables and to detect accidental errors, their construction frequently provides no resistance to a deliberate attack. For example, a denial of service attack on hash tables is possible if the collisions are easy to find, like in the case of linear cyclic redundancy check (CRC) functions.

Свойства

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

Устойчивость к прообразу (preimage resistance). Для заданного хеш-значения h должно быть сложно найти какое-либо сообщение m, такое что h = hash(m). Эта концепция связана с понятием односторонней функции. Функции, не обладающие этим свойством, уязвимы к атакам по прообразу. Устойчивость ко второму прообразу (second preimage resistance). Для заданного входного сообщения должно быть сложно найти другое входное сообщение, такое что hash(m') = hash(m). Это свойство иногда называют слабой устойчивостью к коллизиям. Функции, не обладающие этим свойством, уязвимы к атакам по второму прообразу. Устойчивость к коллизиям (collision resistance). Должно быть сложно найти два различных сообщения m1 и m2, такие что hash(m1) = hash(m2). Такая пара называется криптографической коллизией хеша. Это свойство иногда называют сильной устойчивостью к коллизиям. Для этого требуется хеш-значение, по крайней мере, вдвое большее, чем необходимо для устойчивости к прообразу; в противном случае коллизии могут быть найдены с помощью атаки «день рождения». Устойчивость к коллизиям подразумевает устойчивость ко второму прообразу, но не подразумевает устойчивость к прообразу. В теоретической криптографии всегда предпочтительнее более слабое предположение, но на практике хеш-функция, устойчивая только ко второму прообразу, считается небезопасной и поэтому не рекомендуется для реальных приложений. Неформально эти свойства означают, что злоумышленник не может заменить или изменить входные данные, не изменив их дайджест. Таким образом, если две строки имеют одинаковый дайджест, можно с уверенностью предположить, что они идентичны. Устойчивость ко второму прообразу предотвращает создание злоумышленником документа с тем же хешем, что и документ, который он не может контролировать. Устойчивость к коллизиям предотвращает создание злоумышленником двух различных документов с одинаковым хешем. Функция, удовлетворяющая этим критериям, все же может обладать нежелательными свойствами. В настоящее время популярные криптографические хеш-функции уязвимы к атакам на расширение длины: имея hash(m) и len(m), но не m, злоумышленник, выбрав подходящий суффикс, может вычислить hash(m || суффикс), где ∥ обозначает конкатенацию. Это свойство может быть использовано для взлома наивных схем аутентификации, основанных на хеш-функциях. Конструкция HMAC обходит эти проблемы. На практике устойчивости к коллизиям недостаточно для многих практических применений. Помимо устойчивости к коллизиям, должно быть невозможно для злоумышленника найти два сообщения с существенно похожими дайджестами или получить какую-либо полезную информацию о данных, имея только их дайджест. В частности, хеш-функция должна вести себя как можно больше как случайная функция (часто называемая случайным оракулом в доказательствах безопасности), оставаясь при этом детерминированной и эффективно вычислимой. Это исключает функции, такие как функция SWIFFT, которая может быть строго доказана как устойчивая к коллизиям при условии, что определенные задачи на идеальных решетках являются вычислительно сложными, но, будучи линейной функцией, не удовлетворяет этим дополнительным свойствам. Алгоритмы контрольных сумм, такие как CRC32 и другие проверки избыточности по модулю два, разработаны для удовлетворения гораздо более слабых требований и, как правило, не подходят в качестве криптографических хеш-функций. Например, CRC использовался для обеспечения целостности сообщений в стандарте шифрования WEP, но была легко обнаружена атака, которая использовала линейность контрольной суммы.

Pre image resistance Given a hash value h, it should be difficult to find any message m such that 1=h = hash(m). This concept is related to that of a one way function. Functions that lack this property are vulnerable to preimage attacks. Second pre image resistance Given an input , it should be difficult to find a different input such that This property is sometimes referred to as weak collision resistance. Functions that lack this property are vulnerable to second preimage attacks. Collision resistance It should be difficult to find two different messages and such that Such a pair is called a cryptographic hash collision. This property is sometimes referred to as strong collision resistance. It requires a hash value at least twice as long as that required for pre image resistance; otherwise collisions may be found by a birthday attack. Collision resistance implies second pre image resistance but does not imply pre image resistance. The weaker assumption is always preferred in theoretical cryptography, but in practice, a hash function which is only second pre image resistant is considered insecure and is therefore not recommended for real applications. Informally, these properties mean that a malicious adversary cannot replace or modify the input data without changing its digest. Thus, if two strings have the same digest, one can be very confident that they are identical. Second pre image resistance prevents an attacker from crafting a document with the same hash as a document the attacker cannot control. Collision resistance prevents an attacker from creating two distinct documents with the same hash. A function meeting these criteria may still have undesirable properties. Currently, popular cryptographic hash functions are vulnerable to length extension attacks: given hash(m) and len(m) but not m, by choosing a suitable an attacker can calculate , where ∥ denotes concatenation. This property can be used to break naive authentication schemes based on hash functions. The HMAC construction works around these problems. In practice, collision resistance is insufficient for many practical uses. In addition to collision resistance, it should be impossible for an adversary to find two messages with substantially similar digests; or to infer any useful information about the data, given only its digest. In particular, a hash function should behave as much as possible like a random function (often called a random oracle in proofs of security) while still being deterministic and efficiently computable. This rules out functions like the SWIFFT function, which can be rigorously proven to be collision resistant assuming that certain problems on ideal lattices are computationally difficult, but, as a linear function, does not satisfy these additional properties. Checksum algorithms, such as CRC32 and other cyclic redundancy checks, are designed to meet much weaker requirements and are generally unsuitable as cryptographic hash functions. For example, a CRC was used for message integrity in the WEP encryption standard, but an attack was readily discovered, which exploited the linearity of the checksum.

Степень сложности

В криптографической практике "трудно" обычно означает "почти наверняка недостижимо для любого злоумышленника, которому необходимо помешать взломать систему на протяжении всего времени, пока безопасность системы считается важной". Таким образом, значение этого термина в некоторой степени зависит от конкретной области применения, поскольку усилия, которые злоумышленник может приложить к решению задачи, обычно пропорциональны ожидаемой выгоде. Однако, поскольку требуемые вычислительные ресурсы обычно растут экспоненциально с длиной дайджеста, даже тысячекратное преимущество в вычислительной мощности можно нейтрализовать, добавив всего несколько десятков бит к длине дайджеста. Для сообщений, выбираемых из ограниченного набора, например, паролей или других коротких сообщений, может быть возможно восстановить хеш, перебрав все возможные сообщения из этого набора. Поскольку криптографические хеш-функции обычно разрабатываются для быстрого вычисления, были созданы специальные функции вывода ключа, требующие больших вычислительных ресурсов, что затрудняет проведение атак полным перебором. В некоторых теоретических анализах "трудно" имеет конкретное математическое определение, например, "неразрешимо за полиномиальное асимптотическое время". Такие интерпретации сложности важны при изучении криптографических хеш-функций с доказанной безопасностью, но обычно слабо связаны с практической безопасностью. Например, алгоритм с экспоненциальной сложностью иногда может оказаться достаточно быстрым для осуществления реальной атаки. И наоборот, алгоритм с полиномиальной сложностью (например, требующий n^(20) шагов для ключей длиной n) может быть слишком медленным для любого практического применения.

Иллюстрация

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

Проверка целостности сообщений и файлов

Важным применением безопасных хешей является проверка целостности сообщений. Сравнение дайджестов сообщений (хеш-дайджестов сообщения), вычисленных до и после передачи, позволяет определить, были ли внесены какие-либо изменения в сообщение или файл. Хеш-дайджесты MD5, SHA-1 или SHA-2 иногда публикуются на веб-сайтах или форумах, чтобы пользователи могли проверить целостность загруженных файлов, включая файлы, полученные через файлообменные сети, такие как зеркала. Эта практика формирует цепочку доверия, если хеши размещены на надежном сайте – как правило, на сайте-источнике – защищенном протоколом HTTPS. Использование криптографического хеша и цепочки доверия позволяет выявлять злонамеренные изменения в файле. Не криптографические коды обнаружения ошибок, такие как циклический избыточный код, предотвращают только случайные изменения файла, поскольку злоумышленник может намеренно создать данные, приводящие к совпадению значений кода.

Создание и проверка подписей

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

Проверка пароля

Проверка пароля обычно основана на криптографических хэшах. Хранение всех паролей пользователей в открытом виде может привести к серьезному нарушению безопасности в случае компрометации файла паролей. Один из способов снизить эту опасность — хранить только хеш-дайджест каждого пароля. Для аутентификации пользователя пароль, введенный пользователем, хешируется и сравнивается с сохраненным хешем. При использовании хеширования паролей требуется механизм сброса пароля, поскольку исходные пароли невозможно восстановить из сохраненного хеш-значения. Однако использование стандартных криптографических хеш-функций, таких как семейство SHA, больше не считается безопасным для хранения паролей из-за уязвимости к атакам длинными сообщениями, атакам генерации и подстановки, а также невозможности параллелизации вычислений. В результате современные хеш-функции строятся на основе конструкций с широкой шиной, имеющих больший внутренний размер состояния, варьирующийся от модификаций конструкции Меркла — Дамгорда. Ни одна из функций, участвовавших в конкурсе хеш-функций NIST, не использует классическую конструкцию Меркла — Дамгорда. Кроме того, усечение выходных данных более длинного хеша, например, используемого в SHA 512/256, также эффективно противодействует многим из этих атак.

Использование в создании других криптографических примитивов

Функции хэша могут использоваться для построения других криптографических примитивов. Для обеспечения криптографической безопасности этих примитивов необходимо тщательно следить за правильностью их реализации. Коды аутентификации сообщений (MAC) (также называемые хеш-функциями с ключом) часто строятся на основе хеш-функций. HMAC является одним из таких MAC. Подобно тому, как блочные шифры могут использоваться для построения хеш-функций, хеш-функции могут использоваться для построения блочных шифров. Конструкции Люби-Ракоффа, использующие хеш-функции, могут быть доказательно безопасными, если базовая хеш-функция безопасна. Кроме того, многие хеш-функции (включая SHA-1 и SHA-2) строятся с использованием специализированного блочного шифра в конструкции Дэвиса-Мейера или другой подобной конструкции. Этот шифр также может использоваться в обычном режиме работы, но без тех же гарантий безопасности, например, SHACAL, BEAR и LION. Генераторы псевдослучайных чисел (PRNG) могут быть построены с использованием хеш-функций. Это достигается путем объединения (секретного) случайного начального значения с счетчиком и последующим его хешированием. Некоторые хеш-функции, такие как Skein, Keccak и RadioGatún, выдают поток произвольной длины и могут использоваться как потоковые шифры, а потоковые шифры также могут быть построены на основе хеш-функций с фиксированной длиной. Часто это делается путем предварительного построения криптографически безопасного генератора псевдослучайных чисел, а затем использования его потока случайных байтов в качестве ключевого потока. SEAL – это потоковый шифр, использующий SHA-1 для генерации внутренних таблиц, которые затем применяются в генераторе ключевого потока, слабо связанном с алгоритмом хеширования. Не гарантируется, что SEAL будет столь же надежным (или слабым), как SHA-1. Аналогично, расширение ключа потоковых шифров HC-128 и HC-256 активно использует хеш-функцию SHA-256.

Соединение

Конкатенация результатов работы нескольких хеш-функций обеспечивает стойкость к коллизиям, не уступающую стойкости самого сильного алгоритма, входящего в состав конкатенированного результата. Например, в более ранних версиях Transport Layer Security (TLS) и Secure Sockets Layer (SSL) использовались конкатенированные суммы MD5 и SHA-1. Это гарантирует, что возможность нахождения коллизий в одной из хеш-функций не скомпрометирует данные, защищенные обеими хеш-функциями. Для хеш-функций, построенных по принципу Меркла — Дамгорда, конкатенированная функция столь же устойчива к коллизиям, как и её самый сильный компонент, но не более. Антуан Жукс заметил, что два найденных коллизии приводят к возможности найти n коллизий: если злоумышленнику удается найти два сообщения с одинаковым хешем MD5, то он сможет найти столько дополнительных сообщений с тем же хешем MD5, сколько захочет, без значительных усилий. Среди этих n сообщений с одинаковым хешем MD5, вероятно, найдется коллизия для SHA-1. Дополнительные вычислительные затраты, необходимые для нахождения коллизии SHA-1 (помимо экспоненциального поиска «дня рождения»), требуют лишь полиномиального времени.

Криптографические хэш-алгоритмы

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

MD5

MD5 был разработан Рональдом Ривестом в 1991 году для замены более ранней хеш-функции MD4 и был специфицирован в 1992 году как RFC 1321. Коллизии для MD5 могут быть вычислены за секунды, что делает алгоритм непригодным для большинства применений, где требуется криптографическая хеш-функция. MD5 генерирует дайджест размером 128 бит (16 байт).

SHA-1

SHA 1 был разработан в рамках проекта Capstone правительства США. Оригинальная спецификация алгоритма, теперь обычно называемая SHA 0, была опубликована в 1993 году под названием Secure Hash Standard, FIPS PUB 180, агентством государственных стандартов США NIST (Национальный институт стандартов и технологий). Она была отозвана АНБ вскоре после публикации и заменена пересмотренной версией, опубликованной в 1995 году в FIPS PUB 180-1 и обычно обозначаемой как SHA 1. Коллизии для полного алгоритма SHA 1 могут быть сгенерированы с использованием атаки shattered, и хеш-функцию следует считать скомпрометированной. SHA 1 генерирует хеш-дайджест длиной 160 бит (20 байт). В документации SHA 1 может упоминаться просто как "SHA", хотя это может привести к путанице с другими алгоритмами семейства Secure Hash, такими как SHA 0, SHA 2 и SHA 3.

RIPEMD-160

RIPEMD (RACE Integrity Primitives Evaluation Message Digest) — это семейство криптографических хеш-функций, разработанное в Лёвене, Бельгия, Хансом Доббертином, Антоном Босселерсом и Бартом Пренелем в исследовательской группе COSIC при Католическом университете Лёвена и впервые опубликованное в 1996 году. RIPEMD был разработан на основе принципов проектирования, использованных в MD4, и имеет производительность, сопоставимую с более популярным SHA-1. Однако RIPEMD-160 до сих пор не был взломан. Как следует из названия, RIPEMD-160 генерирует хеш-дайджест длиной 160 бит (20 байт).

Водопады

Whirlpool — криптографическая хеш-функция, разработанная Винсентом Рижменом и Пауло С. Л. М. Баррето, которые впервые описали её в 2000 году. Whirlpool основан на значительно модифицированной версии стандарта шифрования Advanced Encryption Standard (AES). Whirlpool генерирует хеш-дайджест размером 512 бит (64 байта).

SHA-2

SHA 2 (Secure Hash Algorithm 2) — это набор криптографических хеш-функций, разработанный Агентством национальной безопасности США (NSA), впервые опубликованный в 2001 году. Они построены с использованием структуры Меркла — Дамгарда, на основе односторонней функции сжатия, которая сама построена с использованием структуры Дэвиса — Майера из (секретного) специализированного блочного шифра. SHA 2 в основном состоит из двух хеш-алгоритмов: SHA 256 и SHA 512. SHA 224 является вариантом SHA 256 с различными начальными значениями и усеченным результатом. SHA 384, а также менее известные SHA 512/224 и SHA 512/256, — все это варианты SHA 512. SHA 512 обеспечивает более высокий уровень безопасности, чем SHA 256, и обычно работает быстрее, чем SHA 256 на 64-битных машинах, таких как AMD64. Размер выходных данных в битах определяется расширением в названии "SHA", таким образом, SHA 224 имеет выходной размер 224 бита (28 байт); SHA 256 — 32 байта; SHA 384 — 48 байт; и SHA 512 — 64 байта.

SHA-3

SHA 3 (Secure Hash Algorithm 3) был опубликован NIST 5 августа 2015 года. SHA 3 является частью более широкого семейства криптографических примитивов Keccak. Алгоритм Keccak разработан Гидо Бертони, Джоан Деймен, Майклом Питерсом и Жилем Ван Аше. Keccak основан на конструкции «губка», которую также можно использовать для создания других криптографических примитивов, таких как поточный шифр. SHA 3 обеспечивает те же размеры выходных данных, что и SHA 2: 224, 256, 384 и 512 бит. Настраиваемые размеры выходных данных также можно получить с помощью функций SHAKE 128 и SHAKE 256. В данном случае расширения 128 и 256 в названии указывают на степень защиты функции, а не на размер выходных данных в битах.

Блэк 2

BLAKE2, улучшенная версия BLAKE, была анонсирована 21 декабря 2012 года. Она была разработана Жаном Филиппом Аумассоном, Самуэлем Невесом, Зооко Уилкоксом О’Хирном и Кристианом Виннерлейном с целью замены широко используемых, но устаревших алгоритмов MD5 и SHA 1. При работе на 64-битных архитектурах x64 и ARM, BLAKE2b работает быстрее, чем SHA 3, SHA 2, SHA 1 и MD5. Хотя BLAKE и BLAKE2 не были стандартизированы, как SHA 3, BLAKE2 используется во многих протоколах, включая функцию хеширования паролей Argon2, благодаря высокой эффективности, которую он обеспечивает на современных процессорах. Поскольку BLAKE был кандидатом на SHA 3, BLAKE и BLAKE2 предлагают те же размеры выходных данных, что и SHA 3, включая настраиваемый размер выходных данных.

Блэк3

BLAKE3, улучшенная версия BLAKE2, была анонсирована 9 января 2020 года. Она была разработана Джеком О'Коннором, Жаном Филиппом Аумассоном, Сэмюэлем Невесом и Зооко Уилкоксом О'Харном. BLAKE3 – это единый алгоритм, в отличие от BLAKE и BLAKE2, которые представляют собой семейства алгоритмов с множеством вариантов. Компрессионная функция BLAKE3 тесно основана на функции BLAKE2s, при этом основное отличие заключается в уменьшении количества раундов с 10 до 7. Внутренне BLAKE3 представляет собой дерево Меркла и поддерживает более высокую степень параллелизма, чем BLAKE2.

Атаки на криптографические хэш-алгоритмы

Существует длинный список криптографических хеш-функций, но многие из них оказались уязвимыми и не должны использоваться. Например, NIST выбрал 51 хеш-функцию в качестве кандидатов для первого раунда конкурса хеш-функций SHA-3, из которых 10 были признаны скомпрометированными, а 16 продемонстрировали значительные слабости и поэтому не прошли в следующий раунд; дополнительную информацию можно найти в основной статье о конкурсах хеш-функций NIST. Даже если хеш-функция никогда не была взломана, успешная атака на ослабленный вариант может подорвать доверие экспертов. Например, в августе 2004 года были обнаружены коллизии в нескольких тогда популярных хеш-функциях, включая MD5. Эти недостатки поставили под вопрос безопасность более сильных алгоритмов, производных от слабых хеш-функций, в частности, SHA-1 (усиленная версия SHA-0), RIPEMD-128 и RIPEMD-160 (обе – усиленные версии RIPEMD). 12 августа 2004 года Жу, Каррибо, Лемуэль и Жальби объявили об обнаружении коллизии для полного алгоритма SHA-0. Жу и другие достигли этого, используя обобщение атаки Шабо и Жу. Они обнаружили, что сложность коллизии составляет 2^51 и потребовала около 80 000 процессорных часов на суперкомпьютере с 256 процессорами Itanium 2, что эквивалентно 13 дням непрерывной работы суперкомпьютера. В феврале 2005 года была опубликована информация об атаке на SHA-1, позволяющей найти коллизии примерно за 269 операций хеширования, вместо ожидаемых 280 для 160-битной хеш-функции. В августе 2005 года была сообщена еще одна атака на SHA-1, позволяющая найти коллизии за 263 операции. Были известны и другие теоретические слабости SHA-1: в феврале 2017 года Google объявила об обнаружении коллизии в SHA-1. Специалисты по безопасности рекомендуют, чтобы новые приложения избегали этих проблем, используя более поздние члены семейства SHA, такие как SHA-2, или применяя методы, такие как рандомизированное хеширование, которые не требуют устойчивости к коллизиям. Успешная практическая атака скомпрометировала MD5, используемый в сертификатах для защиты транспортного уровня в 2008 году. Многие криптографические хеши основаны на конструкции Меркла–Дамгорда. Все криптографические хеши, которые напрямую используют полный результат конструкции Меркла–Дамгорда, уязвимы для атак на расширение длины. Это делает MD5, SHA-1, RIPEMD-160, Whirlpool и хеш-алгоритмы SHA-256/SHA-512 уязвимыми для этой конкретной атаки. SHA-3, BLAKE2, BLAKE3 и усеченные варианты SHA-2 не уязвимы для этого типа атак.

There is a long list of cryptographic hash functions but many have been found to be vulnerable and should not be used. For instance, NIST selected 51 hash functions as candidates for round 1 of the SHA 3 hash competition, of which 10 were considered broken and 16 showed significant weaknesses and therefore did not make it to the next round; more information can be found on the main article about the NIST hash function competitions. Even if a hash function has never been broken, a successful attack against a weakened variant may undermine the experts' confidence. For instance, in August 2004 collisions were found in several then popular hash functions, including MD5. These weaknesses called into question the security of stronger algorithms derived from the weak hash functions – in particular, SHA 1 (a strengthened version of SHA 0), RIPEMD 128, and RIPEMD 160 (both strengthened versions of RIPEMD). On August 12, 2004, Joux, Carribault, Lemuel, and Jalby announced a collision for the full SHA 0 algorithm. Joux et al. accomplished this using a generalization of the Chabaud and Joux attack. They found that the collision had complexity 2^(51) and took about 80,000 CPU hours on a supercomputer with 256 Itanium 2 processors – equivalent to 13 days of full time use of the supercomputer. In February 2005, an attack on SHA 1 was reported that would find collision in about 269 hashing operations, rather than the 280 expected for a 160 bit hash function. In August 2005, another attack on SHA 1 was reported that would find collisions in 263 operations. Other theoretical weaknesses of SHA 1 have been known: and in February 2017 Google announced a collision in SHA 1. Security researchers recommend that new applications can avoid these problems by using later members of the SHA family, such as SHA 2, or using techniques such as randomized hashing that do not require collision resistance. A successful, practical attack broke MD5 used within certificates for Transport Layer Security in 2008. Many cryptographic hashes are based on the Merkle–Damgård construction. All cryptographic hashes that directly use the full output of a Merkle–Damgård construction are vulnerable to length extension attacks. This makes the MD5, SHA 1, RIPEMD 160, Whirlpool, and the SHA 256 / SHA 512 hash algorithms all vulnerable to this specific attack. SHA 3, BLAKE2, BLAKE3, and the truncated SHA 2 variants are not vulnerable to this type of attack.

Атаки на хэшированные пароли

Вместо хранения обычных паролей пользователей, системы контролируемого доступа часто хранят хеш пароля каждого пользователя в файле или базе данных. Когда кто-то запрашивает доступ, введенный им пароль хешируется и сравнивается с сохраненным значением. Если база данных будет похищена (что, к сожалению, происходит довольно часто), злоумышленник получит только хеш-значения, а не сами пароли. Однако злоумышленник все еще может восстановить пароли из хешей, поскольку большинство людей выбирают предсказуемые пароли. Списки распространенных паролей широко доступны, и многие пароли достаточно короткие, чтобы можно было перебрать все возможные комбинации, если вычисление хеша не занимает слишком много времени. Использование криптографической соли предотвращает некоторые атаки, например, создание файлов предварительно вычисленных хеш-значений, таких как радужные таблицы. Но благодаря высокопроизводительным графическим процессорам возможны поиски со скоростью до 100 миллиардов тестов в секунду, что делает возможными прямые атаки даже при использовании соли. Национальный институт стандартов и технологий США (NIST) рекомендует хранить пароли, используя специальные хеши, называемые функциями вывода ключа (KDF), разработанными для замедления атак методом перебора. К медленным хешам относятся pbkdf2, bcrypt, scrypt, argon2, Balloon и некоторые современные режимы Unix crypt. Для KDF, выполняющих несколько хешей для замедления вычислений, NIST рекомендует использовать количество итераций не менее 10 000.