Как бы Git справился с коллизией SHA-1 в большом двоичном объекте?

https://stackoverflow.com/questions/9392365

29-10-2019
|

Вопрос

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

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

Решение

Я провел эксперимент, чтобы точно выяснить, как 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);
 }

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

Если большой двоичный объект уже существует с тем же хэшем, вы вообще не получите никаких предупреждений.Кажется, все в порядке, но когда вы нажимаете, кто-то клонирует или вы возвращаетесь, вы теряете последнюю версию (в соответствии с тем, что описано выше).
Если древовидный объект уже существует, и вы создаете большой двоичный объект с тем же хэшем:Все будет казаться нормальным, пока вы либо не попытаетесь нажать, либо кто-то не клонирует ваш репозиторий.Тогда вы увидите, что репо повреждено.
Если объект фиксации уже существует, и вы создаете большой двоичный объект с тем же хэшем:то же, что и №2 - коррумпированный
Если большой двоичный объект уже существует, и вы создаете объект фиксации с тем же хэшем, при обновлении "ref" произойдет сбой.
Если большой двоичный объект уже существует, и вы создаете древовидный объект с тем же хэшем.Это приведет к сбою при создании коммита.
Если объект дерева уже существует, и вы создаете объект фиксации с тем же хэшем, он завершится ошибкой при обновлении "ref".
Если древовидный объект уже существует, и вы создаете древовидный объект с тем же хэшем, все будет выглядеть нормально.Но когда вы фиксируете, все хранилище будет ссылаться не на то дерево.
Если объект фиксации уже существует, и вы создаете объект фиксации с тем же хэшем, все будет выглядеть нормально.Но когда вы совершаете коммит, коммит никогда не будет создан, а указатель HEAD будет перемещен на старый коммит.
Если объект фиксации уже существует, и вы создаете древовидный объект с тем же хэшем, при создании фиксации произойдет сбой.

Для # 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 в порядке, так как он остановится с ошибкой.Я полагаю, было бы лучше, если бы он завершался с ошибкой, по крайней мере, во всех случаях.

Другие советы

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

Тот старый (2006) ответ от Линуса возможно, это все еще актуально:

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

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

Однако "более раннее переопределение" - это как раз то, что вам нужно с точки зрения безопасности:помните, что модель 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 префикс, с проектом гитбрут от Брэд Фитцпатрик (bradfitz).

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

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

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

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

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

a/ по-прежнему требует более 9 223 372 036 854 775 808 вычислений SHA1.Для этого потребовалась вычислительная мощность, эквивалентная 6500 годам вычислений на одном процессоре и 110 годам вычислений на одном графическом процессоре.
б/ подделал бы один файл (с тем же SHA1), но с дополнительным ограничением на его содержимое и размер привел бы к идентичному SHA1 (одного столкновения с содержимым недостаточно):видишь"Как вычисляется git-хэш?"):a blob SHA1 вычисляется на основе содержимого и размер.

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

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

Смотрите больше в моем отдельный ответ ниже.

Согласно Pro git :

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

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

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

(1) Во-первых - небо не падает. Существует большая разница между использованием криптографического хеша для таких вещей, как подпись безопасности, и использование одного для генерации «идентификатора контента» для адресной системы содержимого, как Git.
(2) Во-вторых, характер этой конкретной атаки SHA1 означает, что на самом деле довольно легко смягчить, и уже было два набора патчей, размещенных для этого смягчения последствий.
(3) и, наконец, на самом деле есть достаточно простой переход для некоторых других хэш, которые не нарушит мир - или даже старые репозитории Git.
Что касается того перехода, см. В разделе q1 2018 git 2.16 Добавление структуры, представляющей хеш-алгоритм. Реализация этого перехода началась.
Запуск Git 2.19 (Q3 2018) , git выбрал sha-256, как newhash и в процессе интеграции его в код (значение SHA1 все еще по умолчанию (Q2 2019, Git 2.21), но SHA2 будет преемником)

Оригинальный ответ (25 февраля) Но:
.
Это позволяет верить BLOB, однако SHA-1 дерева все равно меняется, поскольку размер кованого блоба не может быть таким же, как оригинальный: см. « Как рассчитывается Git Hash? "; a Blob Sha1 рассчитывается на основе содержимого и размера .

У него есть есть Некоторый вопрос для git-svn Hote . Или, скорее С самой SVN , как Видимый здесь .
Как я уже упоминал в моем оригинальном ответе , стоимость такой попытки по-прежнему запрещено сейчас (6500 годов процессоров. И 100 GPU лет) см. Также Valerie Anita Aurora in " Срок службы криптографических хэш-функций ".
как прокомментировал ранее, это не О безопасности или доверие, но целостность данных (de-deplication и обнаружение ошибок), которые можно легко обнаружить на git fsck , как упомянуты Linus Torvalds Отказ git fsck предупредил бы по сообщениям фиксации с непрозрачным дам

Ta скрыто после генеракодицетагкода (хотя NUL не всегда присутствует в мошеннической файле ).
Не все поворачиваются на NUL , но Github делает: любой толчок будет прерваться в случае неработающего объекта или сломанной ссылки. Хотя ... есть Причина этого не активируется по умолчанию .

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

linus добавляет :

Весь точка из SCM состоит в том, что это не одноразовое событие, Но о непрерывной истории. Что также принципиально означает, что Успешная атака должна работать со временем, а не обнаруживаться.
Если вы можете обмануть SCM один раз, вставьте свой код, и он получает Обнаружено на следующей неделе, вы на самом деле не делали ничего полезного. Только ты сгорел себя.
Джои Гесс пытается эти PDF в Git Refo и он нашел :
, который включает в себя два файла с одинаковым 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
.

При добавлении идентичных данных этих столбчатых файлов генерирует Другие столкновения, приготовление данных не делает.
Так что the Основной вектор атаки (коврича за коммит) будет

.
генерирует постоянный объект Commit;
Используйте весь объект Commit + Nul в качестве выбранного префикса, а также
Используйте атаку идентично-префикса столкновения для генерации столкновения хороших / плохих объектов.
... и это бесполезно, потому что хорошие и плохие коммиты объекты все еще указывают на то же дерево!
plus, вы уже можете и обнаружить атаки криптаналитических столкновений против SHA-1 в каждом файле с <сильный > Генеракодицетагкод
Добавление аналогичного чека в самом git будет иметь некоторые расчеты . / P >.
на смене хэши, Linux Comments :

Размер хэша и выбор хеш-алгоритма являются независимыми вопросами.
Что вы, вероятно, сделаете, это переключиться на 256-битное хеш, используйте это внутренне и в родной базе данных GIT, а затем по умолчанию только Показать хеш как 40-символьная шестигранная строка (вид, как мы уже сокращаются вещи во многих ситуациях).

Таким образом, инструменты вокруг Git даже не видят изменения, если не передано в Некоторые специальные «Генеракодицетагкод» аргумент (или «Генеракодицетагкод» или что-то еще - по умолчанию, который мы сокращаем до 40).
Все еще,

eferrer "> план перехода (от SHA1 к другой хэш-функции) все еще будет сложным , но активно изучается.
Кампания с генератором кодового кода - это в процессе :

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

<цитата>

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

Защита:

<цитата>

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

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

См. " transfer.fsck " от Марк Стивенс

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

Думаю, криптографы обрадуются.

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

<цитата>

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow