Может ли файл быть злонамеренно изменен таким образом, чтобы сохранить исходный хэш SHA-1?

33

Согласно этой статье и многим другим, SHA-1 не является безопасным.

В моем случае меня не беспокоят пароли или цифровые сертификаты. Я обеспокоен целостностью файлов.

Разумно ли возможно, чтобы файл (например, образ ISO или исполняемый файл) был злонамеренно изменен таким образом, чтобы:

  • Поддерживает хэш исходного файла SHA-1 и
  • Поддерживает общее содержимое файла и его работу (но, конечно, теперь включает вредоносный контент, которого изначально там не было)

На мой взгляд, изменение файла таким образом, что это приводит к коллизии SHA-1, сделает файл совершенно бесполезным. ISO был бы полностью поврежден, или исполняемый файл был бы настолько зашифрован, что даже не был бы исполняемым файлом.

Но, как я понимаю, это может быть неправильно. До сих пор я ничего не нашел в поиске Google в отношении постоянной пригодности SHA-1 для проверки файлов. Есть идеи?

misha256
источник
7
Ответ «это зависит». Если ISO-образ содержит множество файлов JPEG или фильмов - вместе с целевым исполняемым файлом, то это возможно. Вы можете довольно сильно изменять файлы JPEG, не изменяя их размер или внешний вид. В конечном итоге, чем больше файл, тем больше вам придется поиграть и тем выше вероятность неразрушающего столкновения.
Пол
7
@cpast точно, многие сайты перечисляют хэши SHA-1, чтобы вы могли подтвердить свою загрузку. Размышляя об этом, кажется гораздо более вероятным, что хакер скомпрометирует веб-сайт, изменив контент и опубликованный хэш. Тогда ты действительно облажался.
misha256
1
Кстати, мой вопрос касается SHA-1 именно потому, что он довольно распространен, особенно при загрузке с Microsoft / MSDN. Конечно, некоторые веб-сайты публикуют хэши MD5, другие SHA256 и т. Д.
misha256
2
Вопрос в том, почему вы хотите использовать хеш, который имеет какие-либо известные уязвимости, когда есть альтернативы, которые столь же быстры, просты в использовании и широко доступны, но их нет (например, SHA-256) ? Кроме того, есть причина, по которой криптографы объявляют хеш-код небезопасным после обнаружения только одной уязвимости: история показала, что когда одна из них обнаруживается, другие быстро следуют. Знаменитая цитата Брюса Шнайера: «Атаки всегда становятся лучше, они никогда не становятся хуже»
BlueRaja - Дэнни Пфлугхофт
3
@ misha256 Эти хэши sha1 предназначены для проверки повреждения загрузки, а не для обеспечения безопасности. Если вам нужна безопасность, используйте файлы с подписью gpg
Daenyth

Ответы:

41

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

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

Дэвид Шварц
источник
Есть ли известная атака на SHA-1 для столкновений с данным файлом? У меня сложилось впечатление, что эта атака не была найдена ни для MD5, ни для SHA-1 (есть только атака со столкновением, а не атака вторым прообразом)
cpast
@cpast Вредоносная программа Flame использовала коллизию MD5, по-видимому, от Microsoft и взломала Windows Update. У них могла быть куча сертификатов Microsoft на выбор, но они не просто пытались найти какие-либо 2 файла с тем же MD5.
Арон Фостер
2
@ Арон Нет, это не был пример столкновения с данным файлом. Благодаря Flame у Microsoft был сервер лицензирования, который подписывал сертификаты X.509 в соответствии с запросом на подпись сертификата, что означает, что злоумышленник контролирует то, что подписывается в некоторых пределах. Там не было никакого существующего свидетельства, с которым они нашли столкновение; Microsoft подписала CSR от клиентов как часть активации, которая позволяет использовать коллизионную атаку (которая не является второстепенной атакой).
Сегодня,
2
@OlivierDulac Нет, это действительно никогда не было сделано. Нет известных столкновений SHA-1. Ориентировочная стоимость - это всего лишь приблизительная оценка. Дело не в том, что кто-то это сделал, а в том, сколько мы думаем, это стоит, а в том, что никто этого не сделал, но мы думаем, что это сколько будет стоить.
Сегодня,
4
@cpast Мы не знаем наверняка, было ли это сделано или нет, но атака в 3 миллиона долларов составляет менее 0,03% от годового бюджета АНБ (на самом деле атака должна быть дешевле, учитывая, что у них уже есть оборудование и нет). нужно арендовать). Разумно сделать вывод, что, поскольку у них есть средства и мотивация для этого, они, вероятно, уже это сделали. Помни Пламя .
Bain
26

Это теоретически возможно, но это еще не сделано.

То, что вы ищете, называется «коллизия хешей»: два файла с одинаковым хешем. Криптографические хеш-коды, такие как SHA-1, обычно предназначены для того, чтобы сделать это трудным. Поскольку SHA-1 является 160-битным кодом, в среднем потребуется 2 ^ 159 попыток перебора, чтобы найти дубликат. Если найден алгоритм, который надежно работает лучше, чем алгоритм против криптографического хэша, хеш считается «сломанным».

MD-5 - пример очень сломанного хэша. Он должен был иметь прочность 128 бит, что требовало в среднем 2 ^ 127 попыток. Как и в случае злоупотребления известными уязвимостями, фактическое количество необходимых попыток может быть всего 2 ^ 47. Это намного меньше, чем 2 ^ 127. Фактически, это было сделано менее чем за один день на современном вычислительном кластере.

Я привожу этот пример, потому что это наиболее близко к тому, как вы собираетесь использовать SHA-1. Тем не менее, это не самый распространенный подход криптоанализа для проверки того, что хэши не сломаны. Они обычно допускают конфликт между двумя файлами, выбранными злоумышленником, вместо того, чтобы вы выбирали один файл, а злоумышленник пытается сопоставить его. Преимущество такого рода атак состоит в том, что их легче сравнивать. Если я нахожу, что «тяжело» взломать ваш файл, значит ли это, что другой файл такой же сильный? Эта атака, при которой злоумышленник выбирает оба файла, гарантирует, что мы поймаем худшее из худшего.

Этот тип атаки позволяет использовать интересный трюк, известный как « атака на день рождения». ». Короче говоря, использование атаки на день рождения вдвое снижает эффективность алгоритма, поэтому SHA-1 требует в среднем 2 ^ 80 попыток, а MD5 - в среднем 2 ^ 64. Это половина из 160 и 128 соответственно.

SHA-1 имеет известные атаки, которые уменьшают свою силу с 2 ^ 80 до 2 ^ 69. Это не будет иметь большого значения для вас. 2 ^ 69 попыток это долго .

Однако из истории мы обнаружили, что алгоритмы хеширования не нарушаются самопроизвольно, а скорее нарушаются со временем. Никто не взломает алгоритм, подобный MD-5, взяв его с 2 ^ 64 до 2 ^ 47 за ночь. Это происходит со временем, так как многие люди публикуют статьи о математике, которую они используют против нее. Обычно можно наблюдать, как сложность атак медленно снижается с самого начала алгоритма (где лучшая атака обычно - атака на день рождения).

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

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

Корт Аммон - Восстановить Монику
источник
8
Что касается абзаца с днем ​​рождения, 2 ^ 80 - это квадратный корень из 2 ^ 160, а не половина его (что будет 2 ^ 159).
Эндрю Мортон
Вопрос о второстепенных атаках, но ваш ответ о столкновениях. Прообразные атаки против SHA-1 & mdash; и даже MD5 & ndash; абсурдно нецелесообразно. (Существует атака с прообразом 2 ^ 123 против MD5, но с SHA-1 вы застряли с грубой силой 2 ^ 160.)
Мэтт Нордхофф,
«Поскольку SHA-1 является 160-битным кодом, в среднем требуется 2 ^ 159 попыток перебора». Но код 2 ^ 2 требует 2 ^ 2 догадок. Я не понимаю, почему ты -1. «Короче говоря,« ... »уменьшает мощность алгоритма вдвое, поэтому SHA-1 требует 2 ^ 80» ... «MD5 требует 2 ^ 64» ... «Это половина из 160 и 128 соответственно». Здесь вы должны иметь -1'ed. Биты увеличивают силу экспоненциально, поэтому вдвое сила 160-битного хэша будет рассматриваться как 159-битный, а не 80-битный. Каждый бит удваивает вызов атаки грубой силы.
TOOGAM
@TOOGAM: он сказал «в среднем»; в нескольких испытаниях только 50% ключевого пространства нужно искать в среднем, чтобы преуспеть в атаке грубой силой. Что касается сокращения вдвое, то комментарий Эндрю Мортона выше объясняет это; это должен быть квадратный корень, а не половина сложности.
Рейд
@ AndrewMorton хорошая мысль, мне не совсем понятна формулировка. Я нахожу, что литература часто переключается между числом состояний и логарифмом числа состояний по основанию-2. Моя формулировка относится к уменьшению числа битов вдвое, потому что люди склонны говорить о «силе» в количестве бит. Я так привык переключаться назад и вперед, что делал это неосознанно. Я отредактирую, чтобы убрать путаницу.
Корт Аммон - Восстановить Монику
8

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

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

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


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


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

cpast
источник
5

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

SHA-1 сломан, поскольку атака столкновением может быть осуществлена ​​в 2 52 операциях согласно статье в Википедии, в которой не приводится цитата для этого числа (лучшая атака, о которой я знаю, которая на самом деле заслуживает доверия, - это атака Марка Стивенса , что занимает 2 60 операций). Но давайте предположим пессимистический случай 2 52 .

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

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

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

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

Вы можете реально ожидать получить что-нибудь от 10 до 50 GFLOPS из одного ватта. Предполагая, что происходит какое-то чудо и процессоры получают в несколько тысяч раз больше энергии за ночь, можно предположить, что 1 SHA ≈ 1 FLOP (довольно оптимистично!). Это будет означать, что для выполнения 2 104 вычислений хэша в течение 10 лет вам потребуется электростанция мощностью 10 12 Вт. Чтобы запустить атаку в течение 1 года, вам нужна электростанция мощностью 10 13 Вт. Это примерно в 50 раз больше, чем все атомные электростанции США, Франции и Японии могут производить вместе, только для создания единого хэша.

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

Damon
источник
«... гораздо более простые способы достижения того же самого ...» Как показано на xkcd.com/538
Ральф Дж
2

Общая точка статьи refered в вопросе: SHA1 является устаревшим и должно быть прекращено , пока еще есть время , чтобы сделать это плавно. В некоторых областях время истекает, так как Google и Microsoft соблюдают крайние сроки.

Практическое правило для устаревшей технологии:

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

Краткая цитата из сообщения в блоге 2012 года Брюса Шнайера: «Дело в том, что мы в сообществе должны начать миграцию с SHA-1 и на SHA-2 / SHA-3 сейчас».

jmn
источник
2

Для части вашего вопроса, касающейся хэширования SHA-1, это было решено несколькими ответами.

Однако большая часть этого зависит от типа файла, с которым мы работаем:

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

Что это означает, сильно зависит от того, что обнаруживает изменения:

  • Если это подписанный исполняемый файл, то нет (разумного) шанса: вам нужно каким-то образом получить два коллизии хеша: SHA-1 файла и внутреннюю подпись .exe.
  • Если это неподписанный исполняемый файл, .com, unsigned .dll или аналогичный, их ветки ресурсов могут быть добавлены способами, которые не изменят их работу, и, таким образом, вы можете (в конечном итоге) получить хеш-коллизию, которая не обнаруживается «обычным» операция.
  • Если это файл исходного кода или аналогичная структура (.cs, .c, .h, .cpp, .rb, .yml, .config, .xml, .pl, .bat, .ini), то добавление, изменение или удаление может быть ограничен допустимым синтаксисом комментария, так что изменение не будет заметно в большинстве случаев (его компиляция или запуск, а не открытие в текстовом редакторе).
  • Если это формат .iso или .zip или другой контейнер, это также маловероятно, так как большинство случайных изменений повредит контейнер. Это можно сделать: добавить фиктивную запись в файл или изменить содержимое в контейнере и перепроверить его, но вы добавляете уровень сложности и добавляете дополнительное время для проверки результата, а также ограниченные степени свободы в отношении как и какое содержимое может быть изменено.
  • Если это текстовый или подобный тексту формат, их можно изменить практически любым удобным для вас способом, оставаясь при этом «допустимым» файлом, хотя содержимое, вероятно, будет заметным.
  • Со многими форматами, такими как .rtf, .doc, .html, .xslx и другими форматами, поддерживающими разметку, они могут быть добавлены или изменены способами, которые не будут обнаруживаться синтаксическими анализаторами, кроме длины (или даже с ограниченной длиной) (меньше свободы) файлы могут быть изменены, чтобы (в конечном итоге) получить коллизию хеша, оставаясь при этом не только допустимым файлом, но и не заметно изменяемым любым способом, который был бы виден типичным приложениям, с которыми они будут использоваться.

Итак, что вам осталось, так это как получить столкновения в любой структуре, которая не разрушается и, возможно, в некоторой степени не обнаруживается:

  1. Внесите любые необходимые функциональные изменения (возможно, вставку вредоносного содержимого) и внесите дополнительные изменения, чтобы сохранить валидность конкретного формата файла.
  2. Добавьте раздел, который будет не функционировать (между блоками комментариев, в самом конце текстового файла с возвратом каретки 3k, изолировать текущий блок комментариев)
  3. Добавьте или выберите символ / кодовую точку / байт для модификации и попробуйте все возможные допустимые комбинации (например, не каждая комбинация байтов действительна для разных кодировок).
  4. Пересчитайте хэш, посмотрите, совпадает ли коллизия.
  5. если нет, переходите к 3.

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

2^160/1000/60/60/24/365.24 
= 4.63x10^37 years 
= 46,300,000,000,000,000,000,000,000,000,000,000,000 years 
= 46 undecillion years.

Но погодите, давайте попробуем 2^60и 2^52версию, и делать вид , что они позволяют изменить файл так , как нам нравится (они не делают) , и что они тоже, могут быть сделаны в 1мсе каждый попробовать:

2^52 yields 142,714 years 
/*humans might still be around to care, but not about these antiquated formats*/
2^60 yields 3.65x10^7 years = 36,500,000 years 
/*machines will probably have taken over anyway*/

Но, может, тебе повезет. На самом деле, на самом деле, чудеса «больше чудо, чем все, что люди называют» чудеса.

Ehryk
источник
0

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

Энтони Гесс
источник
1
Почти невозможно пока . При достаточной вычислительной мощности все возможно.
-6

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

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

кругозор
источник
7
-1 все в этом посте полностью выдумано. Атаки с удлинением по длине не «поддерживают один и тот же хэш» (хэш просто изменяется известным способом) . Кроме того, нет никакой причины, по которой вирус должен был бы удалить «менее используемый код» (как он вообще мог бы определить, что это такое?) . И при чем тут jpegs !?
BlueRaja - Дэнни Пфлугхофт
2
Это совершенно неправильно, я даже не могу начать предлагать исправления, не переписав весь ответ
Марк К Коуэн
2
-1 Не совсем так. aka "Даже не неправильно" (Вольфганг Паули)
Оливье Дюлак
1
Ну, мы могли бы начать с того, что если что-то вообще возможно, то, очевидно, это возможно в конкретном случае . Однако не всегда верно обратное: легко представить проблему, которая может быть решена для конкретного случая, но не в целом.
CVn