Сводка по безопасности хеш-функции - Hash function security summary

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

Цветовой ключ таблицы

  Атака не продемонстрирована успешно - атака ломает только сокращенную версию хэша или требует больше работы, чем заявленный уровень безопасности хэша

  Атака продемонстрирована теоретически - атака прерывается во всех раундах и имеет меньшую сложность, чем требование безопасности

  Атака продемонстрирована на практике

Общие хеш-функции

Сопротивление столкновению

Основная статья: Атака столкновения

Хеш-функция	Требование обеспечения	Лучшая атака	Дата публикации	Комментарий
MD5	2^64	2^18 время	2013-03-25	Эта атака занимает секунды на обычном ПК. Двухблочные коллизии в 2^18, моноблочные коллизии в 2^41.[1]
SHA-1	2^80	2^61.2	2020-01-08	Статья Гаэтана Леурента и Томаса Пейрина[2]
SHA256	2^128	31 из 64 туров (2^65.5)	2013-05-28	Двухблочная коллизия.[3]
SHA512	2^256	24 из 80 туров (2^32.5)	2008-11-25	Бумага.[4]
SHA-3	До 2^512	6 из 24 туров (2^50)	2017	Бумага.[5]
BLAKE2s	2^128	2.5 из 10 раундов (2^112)	2009-05-26	Бумага.[6]
BLAKE2b	2^256	2.5 из 12 туров (2^224)	2009-05-26	Бумага.[6]

Выбранная префиксная атака столкновения

Хеш-функция	Требование обеспечения	Лучшая атака	Дата публикации	Комментарий
MD5	2^64	2^39	2009-06-16	На обычном ПК эта атака занимает несколько часов.[7]
SHA-1	2^80	2^63.4	2020-01-08	Статья Гаэтана Леурента и Томаса Пейрина[2]
SHA256	2^128
SHA512	2^256
SHA-3	До 2^512
BLAKE2s	2^128
BLAKE2b	2^256

Сопротивление прообразу

Основная статья: Атака на прообраз

Хеш-функция	Требование обеспечения	Лучшая атака	Дата публикации	Комментарий
MD5	2^128	2^123.4	2009-04-27	Бумага.[8]
SHA-1	2^160	45 из 80 раундов	2008-08-17	Бумага.[9]
SHA256	2^256	43 из 64 туров (2^254.9 время, 2^6 объем памяти)	2009-12-10	Бумага.[10]
SHA512	2^512	46 из 80 патронов (2^511.5 время, 2^6 объем памяти)	2008-11-25	Бумага,[11] обновленная версия.[10]
SHA-3	До 2^512
BLAKE2s	2^256	2.5 из 10 раундов (2^241)	2009-05-26	Бумага.[6]
BLAKE2b	2^256	2.5 из 12 туров (2^481)	2009-05-26	Бумага.[6]

Увеличение длины

Основная статья: Атака удлинения длины

• Уязвимы: MD5, SHA1, SHA256, SHA512
• Не уязвимы: SHA384, SHA-3, BLAKE2

Менее распространенные хэш-функции

Сопротивление столкновению

Хеш-функция	Требование обеспечения	Лучшая атака	Дата публикации	Комментарий
ГОСТ	2^128	2^105	2008-08-18	Бумага.[12]
HAVAL -128	2^64	2^7	2004-08-17	Столкновения первоначально сообщались в 2004 году,[13] за которым последовала статья о криптоанализе в 2005 году.[14]
MD2	2^64	2^63.3 время, 2^52 объем памяти	2009	Немного менее затратно с точки зрения вычислений, чем атака в день рождения,[15] но с практической точки зрения требования к памяти делают его более дорогим.
MD4	2^64	3 операции	2007-03-22	Обнаружение столкновений почти так же быстро, как и их проверка.[16]
ПАНАМА	2^128	2^6	2007-04-04	Бумага,[17] улучшение более ранней теоретической атаки 2001 года.[18]
RIPEMD (оригинал)	2^64	2^18 время	2004-08-17	Столкновения первоначально сообщались в 2004 году,[13] за которым последовала статья о криптоанализе в 2005 году.[19]
RadioGatún	До 2^608[20]	2^704	2008-12-04	Для размера слова ш между 1-64 битами хэш обеспечивает требование безопасности 29.5ш. Атака может найти столкновение за 211ш время.[21]
РИПЭМД-160	2^80	48 из 80 патронов (2^51 время)	2006	Бумага.[22]
SHA-0	2^80	2^33.6 время	2008-02-11	Двухблочные коллизии с использованием атака бумерангом. На среднем ПК атака длится примерно 1 час.[23]
Стрибог	2^256	9,5 раунда из 12 (2^176 время, 2^128 объем памяти)	2013-09-10	Отскок атаки.[24]
Водоворот	2^256	4.5 из 10 патронов (2^120 время)	2009-02-24	Отскок атаки.[25]

Сопротивление прообразу

Хеш-функция	Требование обеспечения	Лучшая атака	Дата публикации	Комментарий
ГОСТ	2^256	2^192	2008-08-18	Бумага.[12]
MD2	2^128	2^73 время, 2^73 объем памяти	2008	Бумага.[26]
MD4	2^128	2^102 время, 2^33 объем памяти	2008-02-10	Бумага.[27]
RIPEMD (оригинал)	2^128	35 из 48 раундов	2011	Бумага.[28]
РИПЭМД-128	2^128	35 из 64 раундов
РИПЭМД-160	2^160	31 из 80 туров
Стрибог	2^512	2^266 время, 2^259 данные	2014-08-29	В статье представлены две атаки второго прообраза с требованиями к переменным данным.[29]
Тигр	2^192	2^188.8 время, 2^8 объем памяти	2010-12-06	Бумага.[30]

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

Основная статья: Взлом пароля

Описанные здесь хэши предназначены для быстрых вычислений и имеют примерно одинаковую скорость.^[31] Поскольку большинство пользователей обычно выбирают короткие пароли сформированные предсказуемым образом, пароли часто можно восстановить из их хешированного значения, если используется быстрый хеш. Поиски порядка 100 миллиардов тестов в секунду возможны с помощью high-end графические процессоры.^[32][33] Специальные хэши называются ключевые производные функции были созданы для замедления поиска методом грубой силы. К ним относятся pbkdf2, bcrypt, зашифровать, аргон2, и воздушный шар.

Смотрите также

• Сравнение криптографических хеш-функций
• Криптографическая хеш-функция
• Атака столкновения
• Атака на прообраз
• Атака удлинения длины
• Сводка по безопасности шифрования

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

1. Тао Се; Фанбао Лю; Дэнго Фэн (25 марта 2013 г.). «Быстрая атака на столкновение с MD5».
2. Гаэтан Леурент; Томас Пейрин (2020-01-08). «SHA-1 - это беспорядок: конфликт первого выбранного префикса на SHA-1 и приложение к сети доверия PGP» (PDF).
3. Флориан Мендель; Томислав Над; Мартин Шлеффер (28 мая 2013 г.). Улучшение локальных коллизий: новые атаки на сокращенный SHA-256. Еврокрипт 2013.
4. Сомитра Кумар Санадхья; Палаш Саркар (25 ноября 2008 г.). Новые коллизионные атаки против 24-шагового SHA-2. Индокрипт 2008 г. Дои:10.1007/978-3-540-89754-5_8.
5. Л. Сонг, Г. Ляо и Дж. Го, Неполная линеаризация Sbox: приложения к атакам на коллизию на Keccak с сокращенным циклом, CRYPTO, 2017
6. LI Ji; Сюй Лянъюй (26.05.2009). "Атаки на BLAKE с уменьшенным раундом".
7. Марк Стивенс; Арьен Ленстра; Бенн де Вегер (16.06.2009). «Конфликты с выбранным префиксом для MD5 и приложений» (PDF).
8. Ю Сасаки; Казумаро Аоки (27 апреля 2009 г.). Поиск прообразов в полном MD5 быстрее, чем исчерпывающий поиск. Еврокрипт 2009. Дои:10.1007/978-3-642-01001-9_8.
9. Кристоф де Канньер; Кристиан Рехбергер (17 августа 2008 г.). Прообразы для сокращенных SHA-0 и SHA-1. Крипто 2008.
10. Казумаро Аоки; Цзянь Го; Кристиан Матусевич; Ю Сасаки; Лэй Ван (2009-12-10). Прообразы для SHA-2 с уменьшенным шагом. Asiacrypt 2009. Дои:10.1007/978-3-642-10366-7_34.
11. Ю Сасаки; Лэй Ван; Казумаро Аоки (25 ноября 2008 г.). "Атаки на прообраз на 41-шаговом SHA-256 и 46-шаговом SHA-512".
12. Флориан Мендель; Норберт Прамсталлер; Кристиан Рехбергер; Марчин Контактак; Януш Шмидт (18.08.2008). Криптоанализ хеш-функции ГОСТ. Крипто 2008.
13. Сяоюнь Ван; Дэнго Фэн; Сюэцзя Лай; Хунбо Ю (2004-08-17). «Коллизии для хеш-функций MD4, MD5, HAVAL-128 и RIPEMD».
14. Сяоюнь Ван; Дэнго Фэн; Сююань Юй (октябрь 2005 г.). «Атака на хеш-функцию HAVAL-128» (PDF). Наука в Китае. Серия F: Информационные науки. 48 (5): 545–556. CiteSeerX  10.1.1.506.9546. Дои:10.1360/122004-107. Архивировано из оригинал (PDF) на 2017-08-09. Получено 2014-10-23.
15. Ларс Р. Кнудсен; Джон Эрик Матиассен; Фредерик Мюллер; Сорен С. Томсен (январь 2010 г.). «Криптоанализ MD2». Журнал криптологии. 23 (1): 72–90. Дои:10.1007 / s00145-009-9054-1. S2CID  2443076.
16. Ю Сасаки; Юсуке Наито; Нобору Кунихиро; Казуо Охта (22 марта 2007 г.). «Улучшенные коллизионные атаки на MD4 и MD5». Сделки IEICE по основам электроники, связи и компьютерных наук. E90-A (1): 36–47. Bibcode:2007IEITF..90 ... 36S. Дои:10.1093 / ietfec / e90-a.1.36.
17. Джоан Дэемен; Жиль Ван Аше (4 апреля 2007 г.). Мгновенное создание столкновений для Панамы. FSE 2007.
18. Винсент Риджмен; Барт Ван Ромпей; Барт Пренил; Джоос Вандевалле (2001). Создание коллизий для PANAMA. FSE 2001.
19. Сяоюнь Ван; Сюэцзя Лай; Дэнго Фэн; Хуэй Чен; Сююань Юй (23.05.2005). Криптоанализ хеш-функций MD4 и RIPEMD. Еврокрипт 2005. Дои:10.1007/11426639_1.
20. RadioGatún - это семейство из 64 различных хеш-функций. Уровень безопасности и лучшая атака в таблице относятся к 64-битной версии. 32-разрядная версия RadioGatún имеет заявленный уровень безопасности 2.³⁰⁴ и лучшая заявленная атака занимает 2³⁵² работай.
21. Томас Фур; Томас Пейрин (2008-12-04). Криптоанализ RadioGatun. FSE 2009.
22. Флориан Мендель; Норберт Прамсталлер; Кристиан Рехбергер; Винсент Реймен (2006). О столкновительной стойкости РИПЭМД-160. ISC 2006.
23. Стефан Мануэль; Томас Пейрин (11 февраля 2008 г.). Коллизии на SHA-0 за один час. FSE 2008. Дои:10.1007/978-3-540-71039-4_2.
24. Цзун Юэ Ван; Хунбо Ю; Сяоюнь Ван (10.09.2013). «Криптоанализ хэш-функции ГОСТ Р». Письма об обработке информации. 114 (12): 655–662. Дои:10.1016 / j.ipl.2014.07.007.
25. Флориан Мендель; Кристиан Рехбергер; Мартин Шлеффер; Сорен С. Томсен (24 февраля 2009 г.). Rebound Attack: криптоанализ уменьшенного водоворота и Грёстля (PDF). FSE 2009.
26. Сорен С. Томсен (2008). «Улучшенная атака прообраза на MD2».
27. Гаэтан Леурент (10 февраля 2008 г.). MD4 не односторонний (PDF). FSE 2008.
28. Чиаки Охтахара; Ю Сасаки; Такеши Симояма (2011). Атаки на прообразы на RIPEMD-128 и RIPEMD-160 с уменьшенным шагом. ISC 2011. Дои:10.1007/978-3-642-21518-6_13.
29. Цзянь Го; Жереми Жан; Гаэтан Леурент; Томас Пейрин; Лэй Ван (2014-08-29). Новый взгляд на использование счетчика: атака второго прообраза на новую российскую стандартизованную хеш-функцию. SAC 2014.
30. Цзянь Го; Сан Линг; Кристиан Рехбергер; Хуасюн Ван (06.12.2010). Расширенные атаки на прообразы встречи-посередине: первые результаты на Full Tiger и улучшенные результаты на MD4 и SHA-2. Asiacrypt 2010. С. 12–17.
31. «Тестирование криптографических хэшей с помощью ECRYPT». Получено 23 ноября, 2020.
32. «Потрясающая производительность графического процессора». Improsec. 3 января 2020 г.
33. Гудин, Дэн (2012-12-10). «Кластер на 25 GPU взламывает каждый стандартный пароль Windows менее чем за 6 часов». Ars Technica. Получено 2020-11-23.

внешняя ссылка

• Обзор атак на Tiger, MD4 и SHA-2 за 2010 год: Цзянь Го; Сан Линг; Кристиан Рехбергер; Хуасюн Ван (06.12.2010). Расширенные атаки на прообразы встречи-посередине: первые результаты на Full Tiger и улучшенные результаты на MD4 и SHA-2. Asiacrypt 2010. стр. 3.