Как Git справится со столкновением SHA-1 на BLOB-объекте?

Question

Этого, вероятно, еще никогда не случалось в реальном мире, и, возможно, никогда не произойдет, но давайте рассмотрим это: скажем, у вас есть git-репозиторий, сделайте коммит и получите очень-очень не повезло: один из BLOB-объектов заканчивается тем жеSHA-1 как еще один, который уже есть в вашем хранилище.Вопрос в том, как Git справится с этим?Просто потерпеть неудачу?Найдите способ связать два больших объекта и проверить, какой из них необходим в зависимости от контекста?

Больше головоломка, чем реальная проблема, но я нашел проблему интересной.

Answer 1

Я провел эксперимент, чтобы выяснить, как именно Git будет вести себя в этом случае. Это с версией 2.7.9 ~ rc0 + next.20151210 (версия Debian). Я просто уменьшил размер хеша с 160-битного до 4-битного, применив следующий diff и перестроив git:

--- git-2.7.0~rc0+next.20151210.orig/block-sha1/sha1.c
+++ git-2.7.0~rc0+next.20151210/block-sha1/sha1.c
@@ -246,6 +246,8 @@ void blk_SHA1_Final(unsigned char hashou
    blk_SHA1_Update(ctx, padlen, 8);

    /* Output hash */
-   for (i = 0; i < 5; i++)
-       put_be32(hashout + i * 4, ctx->H[i]);
+   for (i = 0; i < 1; i++)
+       put_be32(hashout + i * 4, (ctx->H[i] & 0xf000000));
+   for (i = 1; i < 5; i++)
+       put_be32(hashout + i * 4, 0);
 }

Потом я сделал несколько коммитов и заметил следующее.

1. Если BLOB-объект уже существует с таким же хешем, вы вообще не получите никаких предупреждений. Кажется, все в порядке, но когда вы нажимаете, кто-то клонирует, или вы возвращаетесь, вы потеряете последнюю версию (в соответствии с тем, что объяснялось выше).
2. Если объект дерева уже существует, и вы создаете BLOB-объект с таким же хешем: все будет казаться нормальным, пока вы не попробуете протолкнуть или кто-то клонирует ваш репозиторий. Тогда вы увидите, что репо повреждено.
3. Если объект фиксации уже существует, и вы создаете большой двоичный объект с таким же хешем: то же самое, что и # 2 - поврежден
4. Если большой двоичный объект уже существует, и вы делаете объект фиксации с тем же хешем, он не будет работать при обновлении «ref».
5. Если большой двоичный объект уже существует и вы создаете объект дерева с таким же хешем. Не удастся создать коммит.
6. Если объект дерева уже существует, и вы делаете объект фиксации с тем же хешем, он не выполнится при обновлении «ref».
7. Если объект дерева уже существует, и вы создаете объект дерева с таким же хешем, все будет хорошо. Но когда вы фиксируете, все хранилище будет ссылаться на неправильное дерево.
8. Если объект фиксации уже существует, и вы делаете объект фиксации с тем же хешем, все будет хорошо. Но когда вы делаете коммит, коммит никогда не будет создан, а указатель HEAD будет перемещен в старый коммит.
9. Если объект фиксации уже существует, и вы создаете древовидный объект с таким же хешем, то при создании фиксации произойдет сбой.

Для # 2 вы обычно получаете такую ​​ошибку, когда запускаете «git push»:

error: object 0400000000000000000000000000000000000000 is a tree, not a blob
fatal: bad blob object
error: failed to push some refs to origin

или

error: unable to read sha1 file of file.txt (0400000000000000000000000000000000000000)

если вы удалите файл и затем запустите "git checkout file.txt".

Для № 4 и № 6 вы обычно получаете сообщение об ошибке:

error: Trying to write non-commit object
f000000000000000000000000000000000000000 to branch refs/heads/master
fatal: cannot update HEAD ref

при запуске "git commit". В этом случае вы можете просто снова набрать «git commit», так как это создаст новый хеш (из-за измененной метки времени)

Для № 5 и № 9 вы обычно получаете сообщение об ошибке, подобное этому:

fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object

при запуске "git commit"

Если кто-то попытается клонировать ваш поврежденный репозиторий, он обычно увидит что-то вроде:

git clone (one repo with collided blob,
d000000000000000000000000000000000000000 is commit,
f000000000000000000000000000000000000000 is tree)

Cloning into 'clonedversion'...
done.
error: unable to read sha1 file of s (d000000000000000000000000000000000000000)
error: unable to read sha1 file of tullebukk
(f000000000000000000000000000000000000000)
fatal: unable to checkout working tree
warning: Clone succeeded, but checkout failed.
You can inspect what was checked out with 'git status'
and retry the checkout with 'git checkout -f HEAD'

Что «беспокоит» меня, так это то, что в двух случаях (2,3) хранилище становится поврежденным без каких-либо предупреждений, а в 3 случаях (1,7,8) все выглядит нормально, но содержимое хранилища отличается от того, что Вы ожидаете, что это будет. У людей, клонирующих или тянущих, будет другое содержание, чем у вас. Случаи 4,5,6 и 9 в порядке, так как остановится с ошибкой. Я полагаю, что было бы лучше, если бы он завершился с ошибкой, по крайней мере, во всех случаях.

Answer 2

Оригинальный ответ (2012) (см. shattered.io 2017 столкновение SHA1 ниже)

Этот старый (2006) ответ Линуса все еще может быть актуальным:

Неа.Если он имеет тот же SHA1, это означает, что когда мы получим объект с другого конца, мы не перезапишем объект, который у нас уже есть.

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

Однако, с точки зрения безопасности, «более ранняя переопределение» очень важна: помните:модель git такова, что вы должны в первую очередь доверять только своему собственному репозиторию.
Так что если вы делаете «git pull», новые входящие объекты по определению менее надежны, чем объекты, которые у вас уже естьи как таковой было бы неправильно разрешать новому объекту заменять старый.

Таким образом, у вас есть два случая столкновения:

• непреднамеренныйвида , где вам как-то очень-очень не повезло, и два файла в итоге имеют одинаковый SHA1.
  При этомДело в том, что когда вы фиксируете этот файл (или делаете «git-update-index», чтобы переместить его в индекс, но еще не зафиксировали), будет вычислен SHA1 нового содержимого, но , поскольку он соответствуетстарый объект, новый объект не будет создан, и фиксация или индекс заканчивает указанием на старый объект .
  Вы не заметите сразу (так как индексбудет соответствовать старому объекту SHA1, а это означает, что что-то вроде "git diff" будет использовать извлеченную копию), но если вы когда-либо сделаете разность на уровне дерева (или вы сделаете клон или вытяните, или вынудите извлечение)) вы внезапно заметите, что этот файл изменился на что-то полностью отличное от того, что вы ожидали.
  Таким образом, вы, как правило, заметите этот тип столкновения довольно быстро.
  В связанных новостях вопросчто делать с непреднамеренным столкновением ..
  Прежде всего, позвольте мне напомнить людям, что непреднамеренное столкновение действительно очень действительно чертовски маловероятно, поэтому мы, скорее всего, ещеВы когда-нибудь увидите это в полной истории вселенной.
  Но , если это случится, это не конец света: вам, скорее всего, придется просто изменитьфайл, который слегка столкнулся, и просто форсируйте новый коммит с измененным содержимым (добавьте комментарий, говорящий "/* This line added to avoid collision */"), а затем обучите git магии SHA1, которая, как было показано, опасна.
  пару миллионов лет, возможно, нам придется добавить одно или два «отравленных» значения SHA1 в git.Маловероятно, что это будет проблема с обслуживанием;)

• Тип столкновения атакующего , потому что кто-то сломал (или грубо форсировал) SHA1.
  Этоочевидно, что много более вероятно, чем случайный тип, но по определению это всегда "удаленный" репозиторий.Если бы у злоумышленника был доступ к локальному хранилищу, у него были бы гораздо более простые способы испортить вас.
  Так что в этом случае столкновение совершенно не проблема : вы получите«плохой» репозиторий, который отличается от того, что планировал атакующий, но , поскольку вы никогда не будете использовать его сталкивающийся объект, он буквально ничем не отличается от атакующего, просто не обнаружив столкновения вообще , но только с использованием объекта, который у вас уже был (т.е. он на 100% эквивалентен «тривиальному» столкновению идентичного файла, генерирующего тот же SHA1).

Вопрос об использовании SHA-256 регулярно упоминается, но пока не рассматривается (2012).
Примечание: начиная с 2018 года и Git 2.19 , кодрефакторинг для использования SHA-256.

---

Примечание (юмор): вы можете принудительно зафиксировать коммит для определенного префикса SHA1 с проектом gitbrute из Брэд Фицпатрик (bradfitz) .

gitbrute brute-force пара меток времени автора + коммиттера, так что результирующий git commit имеет желаемый префикс.

Пример: https://github.com/bradfitz/deadbeef

---

Даниэль Динниес указывает в комментариях до 7.1 Git Tools- Выбор редакции , который включает:

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

---

Даже совсем недавно (февраль 2017 г.) shattered.io продемонстрировалВозможность подделки коллизии SHA1:
(подробности см. в моем отдельном ответе , включая пост Google+ Линуса Торвальдса)

• a /по-прежнему требуется более 9 223 372 036 854 775 808 расчетов SHA1.Это заняло эквивалентную вычислительную мощность как 6500 лет вычислений с одним ЦП и 110 лет вычислений с одним ГП.
• b / создаст один файл (с тем же SHA1), но с дополнительным ограничением его содержимое и size приведет к тому же SHA1 (столкновение содного содержимого недостаточно): см. " Как вычисляется git-хэш? "): BLA-объект SHA1 вычисляется на основе содержимого и размера .

См. " Время жизни криптографических хеш-функций " от Подробнее Валери Анита Аврора .
На этой странице она отмечает:

Google потратил 6500 лет CPU и 110 лет GPU, чтобы убедить всех, что нам нужно прекратить использование SHA-1 для критически важных приложений безопасности.
Кроме того, потому что это было круто

См. Больше в моем отдельном ответе ниже .

Answer 3

Согласно Pro Git :

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

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

Чуть дальше, эта же ссылка пытается проиллюстрировать вероятность такогоСтолкновение:

Вот пример, чтобы дать вам представление о том, что нужно сделать, чтобы получить столкновение SHA-1.Если бы все 6,5 миллиарда людей на Земле занимались программированием, и каждую секунду каждый из них создавал код, эквивалентный всей истории ядра Linux (1 миллион объектов Git), и помещал его в один огромный репозиторий Git, это заняло бы 5 лет, покаэтот репозиторий содержал достаточно объектов, чтобы иметь 50% вероятности столкновения одного объекта SHA-1.Существует более высокая вероятность того, что каждый член вашей команды программистов будет атакован и убит волками в несвязанных инцидентах в одну и ту же ночь.

Answer 4

Чтобы добавить к моему предыдущему ответу от 2012 года , теперь есть (февраль 2017 года, пять лет спустя) пример фактического столкновения SHA-1 с shattered.io , где вы можете создать два сталкивающихся PDF-файла: получить цифровую подпись SHA-1 в первом PDF-файле, которая также может использоваться как действительная подпись во втором PDF-файле.
См. Также " На пороге смерти в течение многих лет широко используемая функция SHA1 теперь мертва", и эта иллюстрация .

Обновление от 26 февраля: Линус подтвердил следующие пункты в посте Google+ :

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

(2) Во-вторых, природа этого конкретногоАтака SHA1 означает, что на самом деле довольно легко противодействовать, и уже было опубликовано два набора исправлений для этого смягчения.

(3) И, наконец, на самом деле есть достаточно простой переход к другому хэшу, который выиграл 't разрушить мир - или даже старые git-репозитории.

Что касается этого перехода, см. Q1 2018 Git 2.16 , в котором добавлена ​​структура, представляющая алгоритм хеширования.Реализация этого перехода началась.

Начиная с Git 2.19 (Q3 2018) , Git выбрал SHA-256 в качестве NewHash и находится в процессе интеграцииэто к коду (то есть SHA1 по-прежнему по умолчанию (Q2 2019, Git 2.21), но SHA2 будет преемником)

---

Оригинальный ответ (25 февраля) Но:

• Это позволяет подделывать большой двоичный объект, однако SHA-1 дерева все равно изменится, поскольку размер поддельного большого двоичного объекта может не совпадать с исходным: см. Как рассчитывается git-хэш? "; blob SHA1 вычисляется на основе содержимого и размера .
  У него есть некоторая проблема для git-svn, хотя .Или, скорее, с самой SVN , как видно здесь .
• Как я уже упоминал в моем первоначальном ответе , стоимость такой попытки все ещена данный момент запредельно (6500 процессорных лет и 100 графических лет). См. также Валери Анита Аврора в разделе " Время жизни криптографических хеш-функций ".
• Как уже отмечалось ранее, это не о безопасности или доверии, а о целостности данных (дедупликация и обнаружение ошибок), которые могут быть легко обнаружены с помощью git fsck, а упоминается Линусом Торвальдсом сегодня.git fsck будет предупреждать о коммит-сообщении с непрозрачными данными, скрытыми после NUL (хотя NUL не всегда присутствует в мошенническом файле ).
  Не все включают transfer.fsck, но GitHub делает: любой толчок будет прерван в случае уродливого объекта или неработающей ссылки.Хотя ... существует причина, по которой он не активирован по умолчанию .
• PDF-файл может содержать произвольные двоичные данные, которые можно изменить для создания конфликтующего SHA-1, в отличие отподдельный исходный код.
  Актуальная проблема при создании двух репозиториев Git с одинаковым хешем фиксированного заголовка и разным содержимым.И даже тогда атака остается запутанной .
• Линус добавляет :

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

Джои Хесс пробует эти PDF в репозиторий Git и он нашел :

Это включает в себя два файла с одинаковым SHA и размером, которые получаютразличные капли благодаря тому, как Git добавляет заголовок к содержание.

joey@darkstar:~/tmp/supercollider>sha1sum  bad.pdf good.pdf 
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  bad.pdf
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  good.pdf
joey@darkstar:~/tmp/supercollider>git ls-tree HEAD
100644 blob ca44e9913faf08d625346205e228e2265dd12b65    bad.pdf
100644 blob 5f90b67523865ad5b1391cb4a1c010d541c816c1    good.pdf

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

Таким образом, основной вектор атаки (подделка коммита) будет :

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

Кроме того, вы уже можете обнаруживать криптоаналитические атаки на SHA-1, присутствующие в каждом файле, с помощью cr-marcstevens/sha1collisiondetection

Добавление аналогичной проверки в самом Git потребует некоторых вычислительных затрат .

Об изменении хэша, Комментарии Linux :

Размер хэша и выбор алгоритма хеширования являются независимыми вопросами.
Что вы, вероятно, сделаете, это переключитесь на 256-битный хеш, используйте это внутренне и в собственной базе данных git, а затем только по умолчанию show хеш в виде шестнадцатеричной строки из 40 символов (вроде как мы уже сокращать вещи во многих ситуациях).
Таким образом, инструменты вокруг git даже не видят изменений, если не переданы в какой-то особый аргумент "--full-hash" (или "--abbrev=64" или что-то еще - по умолчанию мы сокращаемся до 40).

Тем не менее, план перехода (от SHA1 к другой хэш-функции) все еще будет сложным , но будет активно изучаться.
A convert-to-object_id кампания в процессе :

---

Обновление от 20 марта: GitHub подробно описывает возможную атаку и ее защиту :

Именам SHA-1 можно присвоить доверие через различные механизмы. Например, Git позволяет криптографически подписывать коммит или тэг. При этом подписывается только сам объект фиксации или тега, который, в свою очередь, указывает на другие объекты, содержащие фактические данные файла, используя их имена SHA-1. Столкновение в этих объектах может привести к подписи, которая кажется действительной, но которая указывает на данные, отличные от предполагаемых подписывающим лицом. В такой атаке подписывающий видит только одну половину столкновения, а жертва видит вторую половину.

Защита:

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

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

См. "sha1collisiondetection" Марк Стивенс

---

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

Answer 5

Я думаю, что криптографы праздновали бы.

Цитата из Статья в Википедии о SHA-1 :

В феврале 2005 г. атака Сяоюнь Вана, ИцюньЛиза Инь и Хунбо Ю было объявлено.Атаки могут обнаружить столкновения в полной версии SHA-1, требующей менее 2 ^ 69 операций.(Поиск грубой силы потребует 2 ^ 80 операций.)

Answer 6

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

"Начиная с 2012 года, наиболее эффективной атакой против SHA-1 считается быть тем Марком Стивенсом [34] с оценочной стоимостью $ 2,77 млн. сломайте одно значение хеша, арендуя мощность процессора у облачных серверов. "

Как указали люди, вы можете вызвать хеш-коллизию с git, но это не приведет к перезаписи существующих объектов в другом хранилище. Я думаю, что даже git push -f --no-thin не будет перезаписывать существующие объекты, но не уверен на 100%.

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

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