Теоретически могут ли две разные строки иметь одинаковый хэш и почему

Обновлено: 03.07.2024

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

Хотите перейти к делу?
Вот как реализовать множество распространенных хеш-функций с помощью hashlib в Python.

Недавно на работе я работал над задачей анализа текстовых данных. Для контекста клиент вел неструктурированный и необработанный учет около 3 миллионов контактов, включая клиентов, потенциальных клиентов, контакты и т. д. Что еще хуже, они добавляли в этот список около 5000+ записей в день. Хотя они находятся в процессе инвестирования в решение для управления мастер-данными, оно не будет реализовано в течение некоторого времени и мало что сделает для устранения 20-летнего отставания от зашумленных данных, что имеет решающее значение для непрерывной работы бизнеса.

Хорошо, это не первое мое родео. Посмотрим правде в глаза: беспорядочные данные повсюду в бизнесе. Большинство людей, работающих инженерами данных, аналитиками, учеными и машинными обучающимися, вероятно, знакомы с этой проблемой, и, к счастью, в нашем распоряжении есть целый арсенал инструментов. В том числе: обработка текста и стандартизация очистка, регулярное выражение; кластеризация «пост о кластеризации»; а также методы машинного обучения: разрешение сущностей, связывание записей и дедупликация. Мне нужно написать пост об этих duke, dedupe, zentity.

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

Так что же такое хэш-функция?

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

Для чего они используются?

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

Например, при выполнении запроса к базе данных для строки «Apple Computer» может использоваться хэш для создания хэш-таблицы, которая может использоваться для быстрого указания записей, содержащих подстроку «A» или « Apple» или «Компьютер». Булевы операции дешевы в вычислительном отношении, поэтому хеш-таблицы значительно сокращают пространство поиска до подмножества записей-кандидатов. Отсутствие необходимости оценивать каждую запись в базе данных. Хэш-таблица — это просто таблица логических значений (True или False) для определения того, содержит ли строка подстроку или нет, или, скорее, хэш строки или подстроки.

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

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

Как и выше, мы будем использовать хеш-функцию sha-1.

Хэш-значения sha-1 имеют длину 160 двоичных битов.
Хэш-значения обычно записываются в виде 40-значной шестнадцатеричной строки.
Один шестнадцатеричный символ может представлять только 16 различных значений от 0 до 9 и от A до F. Например. шестнадцатеричные цифры «0F» представляют два набора из 4 двоичных битов «0000 1111».
Поэтому существует всего $16^ = 2^$ sha-1 хеш-значений. Или

“один квиндециллион, четыреста шестьдесят один кваттюордециллион, пятьсот один тредециллион, шестьсот тридцать семь дудециллион, триста тридцать ундециллион, девятьсот два дециллиона, девятьсот восемнадцать нониллионов, двести три октиллиона, шесть сто восемьдесят четыре септиллиона восемьсот тридцать два секстиллиона семьсот шестнадцать квинтиллионов двести восемьдесят три квадриллиона девятнадцать триллионов шестьсот пятьдесят пять миллиардов девятьсот тридцать два миллиона пятьсот сорок две тысячи девять сто семьдесят шесть”руб

Это много! Неужели мы никогда не найдем дубликат? Мы бы? Подробнее об этом через минуту, поэтому давайте также обернем хэш в функцию, которая позволит нам нарезать хэш до заданной длины.

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

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

12 ответов 12

Для набора даже миллиардов активов вероятность случайных столкновений пренебрежимо мала — вам не о чем беспокоиться. Учитывая парадокс дня рождения, для набора из 2^64 (или 18 446 744 073 709 551 616) активов вероятность одного столкновения MD5 в этом наборе составляет 50 %. При таком масштабе вы, вероятно, превзойдете Google по объему хранилища.

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

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

Если это окажется проблемой, я предлагаю рассмотреть серию хеш-функций SHA-2 (SHA-256, SHA-384 и SHA-512). Недостатком является то, что он немного медленнее и выдает более длинный хэш.

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

См. ответ Рубенса для рабочего примера, который вызовет коллизию между двумя разными исполняемыми файлами за считанные часы. :)

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

В частности, обратите внимание, что коды MD5 имеют фиксированную длину, поэтому возможное количество кодов MD5 ограничено. Однако количество строк (любой длины) определенно не ограничено, поэтому логически следует, что должны быть коллизии.

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

См. этот и этот вопросы для примеров.

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

Да, конечно: хеши MD5 имеют конечную длину, но существует бесконечное число возможных строк символов, которые можно хешировать MD5.

Да, две разные строки могут генерировать один и тот же хэш-код MD5.

Вот простой тест, использующий очень похожее двоичное сообщение в шестнадцатеричной строке:

Они генерируют разные суммы SHA-1, но одинаковое хеш-значение MD5. Во-вторых, строки очень похожи, поэтому между ними сложно найти разницу.

Разницу можно найти с помощью следующей команды:

Вышеприведенный пример коллизии взят у Марка Стивенса: Столкновение одного блока для MD5, 2012 г.; он объясняет свой метод с исходным кодом (альтернативная ссылка на статью).

Другая сумма SHA-1, тот же хэш MD5.

Разница в одном байте:

Пример выше адаптирован из книги Тао Се и Дэнгуо Фэна: Создание коллизий MD5 с использованием всего одного блока сообщения, 2010 г.

Да, это возможно. Это называется коллизией хэшей.

При этом такие алгоритмы, как MD5, предназначены для минимизации вероятности коллизии.

Запись в Википедии о MD5 объясняет некоторые уязвимости в MD5, о которых вам следует знать.

Просто чтобы быть более информативным. С математической точки зрения хеш-функции не являются инъективными.
Это означает, что между начальным набором и результирующим набором существует не отношение 1 к 1 (а одностороннее).

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

Да, это так! Столкновение будет возможно (хотя риск очень мал). Если нет, у вас будет довольно эффективный метод сжатия!

EDIT: Как говорит Конрад Рудольф: потенциально неограниченный набор входных данных, преобразованный в конечный набор выходных данных (32 шестнадцатеричных символа), приведет к бесконечному количеству коллизий.

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

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

На самом деле, если злоумышленник может создавать коллизии с помощью одного алгоритма хеширования, он может использовать это, чтобы получить коллизии и для второго алгоритма. Это недавно обсуждалось по моему вопросу на crypto.stackexchange.

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

Я понимаю, что это устарело, но решил поделиться своим решением. Существует 2^128 возможных комбинаций хэшей. Таким образом, вероятность парадокса дня рождения равна 2^64. Хотя приведенное ниже решение не устранит возможность коллизий, оно, безусловно, значительно снизит риск.

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

Итак, мой псевдокод для этого:

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

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

Для меня, я думаю, что возможность столкновения достаточно редка, поэтому я буду считать это не "верным", но настолько маловероятным, что это соответствует необходимости.

Теперь количество возможных комбинаций значительно увеличивается. Хотя вы могли бы потратить много времени на то, сколько комбинаций это может вам дать, я скажу, что теоретически вы получите ЗНАЧИТЕЛЬНО больше, чем указанное выше число

Скорее всего, на сто цифр или около того. Теоретический максимум, который это может дать, будет

Возможное количество результирующих строк:

Похоже, что понимание теории не помогает, когда речь идет о теории на практике, и нужно знать, что означают только 2 числа 1 и 0, это означает 1111111111, поэтому 100 означает 10-кратное число.

Чтобы использовать все хэши, вам нужна одна файловая система или система с одним днем рождения, каждый человек в мире должен иметь 18446744073709551616/8000000000=2305843009,21 файлов для каждого человека, а если его размер 1 МБ, то это 2305843009 МБ или 2305843 ГБ или 2305. ТБ или 153722 диска Google бесплатно 15 ГБ на человека.

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

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

Если в 2002 году средний размер файла составлял 3,22 МБ, то в 2005 году – 8,92 МБ, и мы можем предположить, что мы по-прежнему используем то же качество размера файла. так что даже в файловой системе Google никогда не будет так много файлов в одной системе, поскольку, если 15 ГБ бесплатного диска Google заполнены в среднем множеством маленьких файлов размером 3 МБ на каждые 8 миллиардов человек в мире, получится 40000000000000, что из всех хэшей MD5 0,0000021684% от всех возможных хэшей размеры файлов.

Говоря о несвязанных вещах, таких как день рождения 100 года рождения двух человек, мы будем сравнивать 2 дня или 0,02, а в 365 из 2 человек будем сравнивать 0,00547 % файлов MD5 2/18446744073709551616=0,00000000000000000000108420217 % всех файлов, если так много вообще будет существовать.

Это все равно, что спросить в мире Адама и Евы, совпадают ли у них дни рождения, когда в мире нет ни 365 человек, ни файлов файловой системы, ни вообще такого количества паролей.

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

Если полный лимит MD5 составляет 18 446 744 073 709 551 616, то у вас никогда не будет столько файлов во всем мире.

MD5 — это пример того, как все мировые строки подсчитываются в хэши, которые никогда не будут существовать так долго, так что это просто проблема короткого MD5, но будет ли у нас триллион строк огромной длины, имеющих действительно один и тот же хэш?

На самом деле это все равно, что сравнивать 365 младенцев в разные дни с 366 младенцами, чтобы выяснить, у кого день рождения совпадает.

Как вы видите, теоретически все ответы дают утвердительный ответ, но не подтверждаются примерами из реальной жизни. Если это пароль, то только очень длинная строка может совпадать с короткой.

Если это хеширование идентификации файла, используйте другое хеширование или их комбинацию.

Проблема дня рождения состоит в том, что слово "abcd" одного человека состоит из 4 букв, тогда как ДНК другого человека может быть такой же, только если это "abcdfijdfj".

Если вы читаете Википедию о проблеме дня рождения, это не только дата рождения, но и дата рождения, час, секунда, мс и многое другое похоже на проблему ДНК.

С гашишем у вас может быть одинаковая ДНК и день рождения с близнецами? Неа. Иногда даже с кем-то другим.

Парадокс дня рождения, безусловно, заключается в том, что математическая уловка с вероятностью дает возможность 365 вариантов или дней, а хэш - от скольких? Гораздо более. Поэтому, если у вас есть 2 разные совпадающие строки, это просто потому, что хэш MD5 слишком короткий для слишком большого количества файлов, поэтому используйте что-то более длинное, чем MD5.

Это не сравнение 50 младенцев за 365 дней, это сравнение 2 хэшей, если они одинаковы из строк разной длины, которые были хешированы, как abcd так же, как 25-буквенный abcdef. zdgdege и 150 букв sadiasdjsadijfsdf.sdaidjsad.dfijsdf.

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

Что касается сравнения размера файла, я не уверен, насколько велика вероятность, но она не 97% и даже не 0,0000001%.

Хорошо, давайте будем более конкретными.

Если его файл может возникнуть в огромной системе, поскольку файлы будут разными, но на практике это не должно быть проблемой, поскольку 5 квадриллионов или 5 000 000 000 000 000 файлов должны быть в одной системе для UUID и для MD5.

А если это пароль, то 10 лет пробовать каждую секунду, а можно было пробовать каждую миллисекунду, но тогда за 3 неверных подбора блокировка ip на 1минуту заставит гадать миллионы лет.

Когда я вижу что-то не так, я знаю, что это неправильно. Теория обещает против реальности.

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

Могут ли значения хешей быть одинаковыми?

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

Всегда ли хеши разные?

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

Возвращает ли хэш то же значение?

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

Какова ценность хеша?

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

Что изменяет хеш-значение?

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

Как найти исходное значение хеша?

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

Какой лучший алгоритм хеширования?

Нужен ли для MD5 ключ?

MD5 — это не шифрование, а хэш. Вы ищете симметричный алгоритм шифрования. Он использует один и тот же ключ для шифрования и дешифрования.

Почему MD5 односторонний?

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

Безопасен ли MD5?

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

Является ли хеш односторонней функцией?

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

Какой длины хэш SHA256?

Что вы интерпретируете из одностороннего свойства в хеш-функции?

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

На практике мы взломали SHA-1.

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

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

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

Защита от атак

Вот два файла PDF с разным содержимым, но с одинаковым дайджестом SHA-1.

Тестер файлов

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

Разве SHA-1 не устарел?

Сегодня многие приложения по-прежнему полагаются на SHA-1, несмотря на то, что теоретические атаки известны с 2005 года, а NIST официально объявил SHA-1 устаревшим в 2011 году. Мы надеемся, что наша практическая атака на SHA-1 повысит осведомленность и убедит промышленности быстро перейти на более безопасные альтернативы, такие как SHA-256.

Как я могу защитить себя?

Вы можете использовать наш файловый тестер выше, чтобы проверить свои файлы. Если вы используете Chrome, вы будете автоматически защищены от небезопасных сертификатов TLS/SSL, и Firefox ~~запланировал эту функцию на начало 2017 года~~, быстро отреагировал на это объявление и объявил SHA-1 устаревшим с 24 февраля. 2017.
Файлы, отправленные через Gmail или сохраненные на Google Диске, уже автоматически тестируются на предмет этой атаки.

Какие типы систем затронуты?

Любое приложение, использующее SHA-1 для цифровых подписей, целостности файлов или идентификации файлов, потенциально уязвимо. К ним относятся:

Подписи цифровых сертификатов
Отправлять подписи PGP/GPG по электронной почте
Подписи поставщиков программного обеспечения
Обновления программного обеспечения
Контрольные суммы ISO
Системы резервного копирования
Системы дедупликации
ГИТ
.

Подвержены ли риску сертификаты TLS/SSL?

Любой центр сертификации, соблюдающий правила CA/Browser Forum, больше не может выдавать сертификаты SHA-1. Кроме того, требуется, чтобы центры сертификации вставляли не менее 64 бит случайности в поле серийного номера. При правильной реализации это помогает предотвратить практическое использование.

Покажет ли мой браузер предупреждение?

Начиная с версии 56, выпущенной в январе 2017 года, Chrome будет считать небезопасным любой веб-сайт, защищенный сертификатом SHA-1. Firefox ~~эта функция запланирована на начало 2017 года~~ SHA-1 объявлен устаревшим с 24 февраля 2017 года.

Влияет ли это на ЖКТ?

GIT сильно зависит от SHA-1 для идентификации и проверки целостности всех файловых объектов и коммитов. По сути, можно создать два репозитория GIT с одним и тем же хешем фиксации головы и разным содержимым, скажем, с безопасным исходным кодом и с бэкдором. Злоумышленник потенциально может выборочно обслуживать любой репозиторий для целевых пользователей. Это потребует от злоумышленников вычисления собственной коллизии.

Влияет ли SVN?

SVN был исправлен против атаки: версии 1.9.6 и выше невосприимчивы к ней, а также отладочная версия 1.8.18.

Предыдущая версия '>подвержена атаке. Серверы Subversion используют SHA-1 для дедупликации, и репозитории повреждаются, когда два конфликтующих файла фиксируются в репозитории. Это было обнаружено в репозитории WebKit Subversion и независимо подтверждено нами. Мы заметили, что в некоторых случаях из-за повреждения блокируются дальнейшие фиксации.

Как исправить/обновить систему?

Рассмотрите возможность использования более безопасных альтернатив, таких как SHA-256 или SHA-3.

Как обнаружить эту атаку?

Вы можете использовать указанный выше онлайн-инструмент, чтобы отправить файлы и проверить их на наличие криптоаналитической атаки на коллизии SHA-1. Код, лежащий в основе этого, был разработан Марком Стивенсом (CWI) и Дэном Шумоу (Microsoft) и общедоступен на GitHub.

Он основан на концепции встречного криптоанализа и способен обнаруживать известные и неизвестные криптоаналитические коллизии SHA-1 по одному файлу из конфликтующей пары файлов.

Насколько это широко распространено?

Насколько нам известно, наш пример коллизии создан впервые.

Использовалось ли это в реальных условиях?

Насколько нам известно, нет.

Уязвим ли Hardened SHA-1?

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

Кто способен организовать эту атаку?

Эта атака потребовала более 9 223 372 036 854 775 808 вычислений SHA1. Это потребовало вычислительной мощности, эквивалентной 6500 летам вычислений на одном процессоре и 110 летам вычислений на одном GPU.

Как эта атака отличается от атаки грубой силы?

Атака SHAttered на 100 000 быстрее, чем атака грубой силы, основанная на парадоксе дня рождения. Атака методом грубой силы потребует 12 000 000 лет работы графического процессора, поэтому она нецелесообразна.

Как вы использовали формат PDF для этой атаки?

Кто является командой, стоящей за этим исследованием?

Этот результат является результатом долгосрочного сотрудничества между группой криптологии Centrum Wiskunde & Informatica (CWI) — национального научно-исследовательского института математики и компьютерных наук в Нидерландах – и Google Research Security, Privacy and Anti-Authority. Группа. Два года назад Марк Стивенс и Эли Бурштейн, руководитель исследовательской группы Google по борьбе со злоупотреблениями, начали совместную работу по практической реализации криптоаналитических атак Марка против SHA-1, используя опыт и инфраструктуру Google. С тех пор многие исследователи CWI и сотрудники Google помогли сделать этот проект возможным, в том числе Пьер Карпман, который работал над криптоанализом и реализацией прототипа графического процессора, и Анж Альбертини из Google, разработавший атаку PDF, Ярик Марков, который позаботился о распределенном коде графического процессора, Алекс Пети-Бьянко внедрил детектор столкновений для защиты пользователей Google, Лука Инверницци, создавший онлайн-средство проверки файлов, и Клеман Блез, следивший за надежностью вычислений.

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

Перегрузки

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

Возвращает хэш-код для этой строки, используя указанные правила.

Возвращает хэш-код для указанного диапазона символов, доступного только для чтения.

Возвращает хэш-код для этой строки.

GetHashCode(ReadOnlySpan, StringComparison)

Параметры

Диапазон символов, доступный только для чтения.

Одно из значений перечисления, указывающее правила, используемые при сравнении.

Возврат

32-битный целочисленный хеш-код со знаком.

Относится к

ПолучитьHashCode(StringComparison)

Возвращает хэш-код для этой строки, используя указанные правила.

Параметры

Одно из значений перечисления, указывающее правила, используемые при сравнении.

Возврат

32-битный целочисленный хэш-код со знаком.

Относится к

ПолучитьHashCode(ReadOnlySpan)

Возвращает хэш-код для указанного диапазона символов, доступного только для чтения.

Параметры

Диапазон символов, доступный только для чтения.

Возврат

32-битный целочисленный хеш-код со знаком.

Относится к

ПолучитьHashCode()

Возвращает хэш-код для этой строки.

Возврат

32-битный целочисленный хэш-код со знаком.

Примеры

В следующем примере демонстрируется метод GetHashCode с использованием различных входных строк.

Примечания

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

Если два строковых объекта равны, метод GetHashCode возвращает идентичные значения. Однако для каждого уникального строкового значения не существует уникального значения хеш-кода. Разные строки могут возвращать один и тот же хэш-код.

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

Наконец, не используйте хеш-код вместо значения, возвращаемого криптографической функцией хеширования, если вам нужен криптографически стойкий хэш. Для криптографических хэшей используйте класс, производный от класса System.Security.Cryptography.HashAlgorithm или System.Security.Cryptography.KeyedHashAlgorithm.

Для получения дополнительной информации о хэш-кодах см. Object.GetHashCode.

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

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

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

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

Для получения дополнительной информации об использовании хэш-кодов и метода GetHashCode см. Object.GetHashCode.

Примечания для звонящих

Читайте также: