Рейтинг:72

Насколько легко в 2022 году найти коллизию SHA1?

флаг us

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

Насколько легко это сделать прямо сейчас?

fgrieu avatar
флаг ng
Предыдущие вычислительные работы могут быть дешево расширены для поиска новых столкновений. Я предполагаю, что вопрос ограничивается получением коллизий независимо от предыдущей работы. Есть [эта] (https://eprint.iacr.org/2020/014.pdf) относительно недавняя статья, в которой указано 8 GPU-лет за столкновение с использованием GTX 1080 Ti, что бы это ни было.
Hormoz avatar
флаг us
1080 TI устарел, и в более новых поколениях производительность значительно улучшена, и у вас может работать сотня или даже тысяча таких графических процессоров.
kelalaka avatar
флаг in
Я голосую за то, чтобы закрыть этот вопрос, потому что речь идет скорее о производительности графических процессоров, а не о новых улучшениях криптографических атак.
Hormoz avatar
флаг us
Хотя это действительно имеет значение? Производительность графических процессоров влияет на криптографические атаки.
kelalaka avatar
флаг in
Вы просите их сравнить. Вам нужно спросить, какая на данный момент лучшая атака, которая может использовать множество различных GPU/CPU/ASIC для достижения своей цели.
kelalaka avatar
флаг in
$9 223 372 036 854 775 808 \приблизительно 2^{63}$, чтобы [Summit мог выполниться за один день, а совместные усилия биткойн-майнера — за одну секунду.](https://crypto.stackexchange.com/a/63537/18298 )
Blockchain Office avatar
флаг gw
как насчет квантовых атак на скорости для создания столкновения?
Рейтинг:115
флаг cn

по мнению некоторых Тесты Hashcat, текущий графический процессор Nvidia может вычислять хэши SHA-1 со скоростью:

  • NVIDIA GeForce RTX 3090 ~22,6×109 хэшей в секунду
  • NVIDIA GeForce RTX 3080 Ti ~21,7×109 хэшей в секунду

И видеокарты AMD, кажется, работают в том же диапазоне, что и этот эталон:

SHA-1 Скорость.№1.........: 20,6×109

Учитывая рекомендованную производителем розничную цену ~$649, AMD RX 6800 XT кажется нашим лучшим кандидатом для проведения подобной атаки. (Несмотря на нехватку чипов, безумно взвинчивающую цены...)

Далее, по данным 2017 г. разрушенный.это сайт и газета:

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

Но как упоминалось в комментарий fgrieu, в 2020 г., новая статья («SHA-1 — это руины») вышел, еще больше улучшив атаку SHAttered, в которой они оценили стоимость своей атаки до $~2^{61,6} = 3,5\умножить на 10^{18}$ Вычисления SHA-1 по сравнению с $2^{63}$ расчеты в SHAttered (см. Таблицу 4.)

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

$$\frac{2^{61,6}}{20,6×10^9} \приблизительно 169\times10^6$$

секунд с одним GPU, что составляет ~ 5,36 года. Но это относительно хорошо распараллеливается, поэтому вы можете просто добавить больше графических процессоров в смесь, и вы можете получить один за шесть месяцев с 10 графическими процессорами или за 2 месяца с 30 графическими процессорами ... И это при теоретической стоимости GPU ~ 19 470 долларов. , плюс ~ 2000 долларов на электроэнергию для работы 30 графических процессоров в течение 2 месяцев...

Вы также можете просто арендовать три экземпляра AWS p3.16xlarge. с хешрейтом ~135GH/s каждый по цене ~ 24,48 долл. США за экземпляр в час, всего 405 ГГц / с за 73,44 долл. США в час. Это займет у вас примерно 2397,12 часа (3 месяца) и обойдется вам примерно в 176 044 доллара.

Примечательно, что мы видим, что всего за 5 лет мы сократились с атаки, затратившей ~110 лет на GPU, до атаки, которая стоила бы примерно 8 лет на GPU в 2020 году (благодаря теоретическим усовершенствованиям и более новым графическим процессорам), и теперь всего до ~5,4 года на GPU в настоящее время. (благодаря новым и более быстрым графическим процессорам).

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

В частности, мы отмечаем, что коллизии выбранного префикса для SHA-1 могут быть сгенерированы менее чем за минуту с кластером ASIC, который стоит несколько десятков миллионов долларов. Такая возможность позволит злоумышленнику применить атаку SLOTH на соединения TLS или SSH с использованием SHA-1.

Наконец, если мы примем во внимание суперкомпьютеры и сеть Биткойн, этот вопрос уже освещен в этом превосходном ответе kelalaka от 2018 года., и дела обстоят не очень хорошо: сеть Биткойн может сделать это за 1 секунду, учитывая ее текущий хешрейт более 200 TH/s... Ага: одна секунда! Но технически это неверно, поскольку выделенное оборудование Биткойн на самом деле специализируется на вычислении хэшей SHA-256.
Более реалистично, это заняло бы меньше дня, чтобы сделать это на суперкомпьютере, таком как тот, который принадлежит Национальной лаборатории Ок-Риджа (ORNL) Министерства энергетики США под названием «Саммит".

флаг cn
Дополнительное примечание (без принадлежности), но такие услуги, как https://vast.ai, стоят от 3 до 5 долларов в час для 8x 3090, поэтому для этой цели используются примерно одинаковые скорости. Еще в восемь раз меньше стоимости (~ 25-35 тысяч долларов). Хотя мне нравится использовать Amazon в качестве примера цен на GPU для взлома паролей, фактические затраты могут быть намного ниже с другими сервисами, спотовыми инстансами и т. д.

Ответить или комментировать

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