Как Git справится со столкновением SHA-1 на BLOB-объекте?
Вероятно, этого еще никогда не случалось в реальном мире, и, возможно, никогда не случится, но давайте рассмотрим это: скажем, у вас есть git-репозиторий, сделайте коммит, и вам очень очень не повезло: один из BLOB-объектов заканчивается тем же SHA-1 как другой, который уже находится в вашем хранилище. Вопрос в том, как Git справится с этим? Просто потерпеть неудачу? Найдите способ связать два блоба и проверить, какой из них нужен согласно контексту?
Больше дразнилка, чем реальная проблема, но я нашел проблему интересной.
6 ответов
Я провел эксперимент, чтобы выяснить, как именно 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);
}
Затем я сделал несколько коммитов и заметил следующее.
- Если BLOB-объект с таким же хешем уже существует, вы не получите никаких предупреждений. Кажется, все в порядке, но когда вы нажимаете, кто-то клонирует, или вы возвращаетесь, вы потеряете последнюю версию (в соответствии с тем, что описано выше).
- Если объект дерева уже существует, и вы создаете BLOB-объект с таким же хешем: все будет казаться нормальным, пока вы не попробуете подтолкнуть или кто-то клонирует ваш репозиторий. Тогда вы увидите, что репо повреждено.
- Если объект фиксации уже существует, и вы создаете BLOB-объект с таким же хешем: такой же, как #2 - поврежден
- Если BLOB-объект уже существует, и вы создаете объект коммита с таким же хешем, он не будет работать при обновлении "ref".
- Если BLOB-объект уже существует, и вы создаете объект дерева с таким же хешем. Это не удастся при создании коммита.
- Если объект дерева уже существует, и вы делаете объект фиксации с тем же хешем, то произойдет сбой при обновлении "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 генерирует группу обеспечения доступности баз данных, которая не полностью упорядочена, поэтому в то время как разные хранилища согласятся с тем, что "раньше" в случае прямого происхождения, если объект проходил через отдельные и не связанные напрямую ветви, два разных хранилища, очевидно, могли получить два объекта в разном порядке.
Тем не менее, "с более ранней точки зрения" это то, что вам нужно с точки зрения безопасности: помните, что модель git заключается в том, что вы должны в первую очередь доверять только своему собственному репозиторию.
Так что, если вы делаете "git pullmsgstr "новые входящие объекты по определению менее надежны, чем объекты, которые у вас уже есть, и поэтому было бы неправильно разрешать новому объекту заменять старый.Итак, у вас есть два случая столкновения:
непреднамеренный вид, когда вам как-то очень-очень не повезло, и два файла в конечном итоге имеют один и тот же SHA1.
На этом этапе, что происходит, когда вы фиксируете этот файл (или делаете "git-update-index"чтобы переместить его в индекс, но еще не зафиксировал), SHA1 нового содержимого будет вычислен, но, поскольку он соответствует старому объекту, новый объект не будет создан, и фиксация или индекс завершится указывая на старый объект.
Вы не заметите сразу (так как индекс будет соответствовать старому объекту SHA1, а это значит, что-то вроде "git diffбудет использовать извлеченную копию), но если вы когда-нибудь сделаете разность на уровне дерева (или вы клонируете или извлекаете, или форсируете извлечение), вы внезапно заметите, что этот файл изменился на нечто совершенно отличное от того, что ты ожидал
Таким образом, вы, как правило, заметили такое столкновение довольно быстро.
В связанных новостях вопрос состоит в том, что делать с непреднамеренным столкновением.
Прежде всего, позвольте мне напомнить людям, что непреднамеренное столкновение действительно невероятно маловероятно, поэтому мы, скорее всего, никогда не увидим его за всю историю вселенной.
Но если это произойдет, это не конец света: вам, скорее всего, придется просто изменить файл, который слегка столкнулся, и просто принудительно создать новый коммит с измененным содержимым (добавьте комментарий со словами "/* This line added to avoid collision */"), а затем обучите мерзавца магии SHA1, которая, как было показано, опасна.
Таким образом, в течение пары миллионов лет, возможно, нам придется добавить одно или два "отравленных" значения SHA1 в git. Это очень маловероятно, чтобы быть проблемой обслуживания;)Нападение нападающего, потому что кто-то сломал (или перебор) SHA1.
Это, безусловно, намного более вероятно, чем непреднамеренный, но по определению это всегда "удаленный" репозиторий. Если бы у злоумышленника был доступ к локальному хранилищу, у него были бы намного более простые способы испортить вас.
Таким образом, в этом случае столкновение не является проблемой: вы получите "плохой" репозиторий, отличный от того, который предполагал злоумышленник, но поскольку вы никогда не будете использовать его сталкивающийся объект, он буквально не отличается от злоумышленник просто не обнаружил столкновение, а просто использует объект, который у вас уже был (т.е. он на 100% эквивалентен "тривиальному" столкновению идентичного файла, генерирующего тот же SHA1).
Вопрос об использовании SHA-256 регулярно упоминается, но пока не решен.
Примечание (юмор): вы можете принудительно зафиксировать конкретный префикс SHA1 с помощью gitbrute проекта от Брэда Фицпатрика ( bradfitz )
gitbrute brute-форсирует пару временных меток "автор + коммиттер", так что результирующий git commit имеет желаемый префикс.
Пример: https://github.com/bradfitz/deadbeef
Daniel Dinnyes указывает в комментариях на http://git-scm.com/book/en/v2/Git-Tools-Revision-Selection, который включает в себя:
Существует более высокая вероятность того, что каждый член вашей команды программистов будет атакован и убит волками в несвязанных инцидентах в одну и ту же ночь.
Даже совсем недавно (февраль 2017 г.) shattered.io продемонстрировали возможность подделки столкновения SHA1:
(см. намного больше в моем отдельном ответе, включая пост Линуса Торвальдса в Google+)
- а / все еще требуется более 9 223 372 036 854 775 808 вычислений SHA1. Это заняло эквивалентную вычислительную мощность как 6500 лет вычислений с одним ЦП и 110 лет вычислений с одним ГП.
- b / подделал бы один файл (с тем же SHA1), но с дополнительным ограничением его содержимое и размер дали бы идентичный SHA1 (столкновение только с одним содержимым недостаточно): см. " Как вычисляется git-хеш? "): BLA- объект SHA1 вычисляется на основе содержимого и размера.
См. " Время жизни криптографических хеш-функций " от Валери Аниты Авроры для получения дополнительной информации.
На этой странице она отмечает:
Google потратил 6500 лет CPU и 110 лет GPU, чтобы убедить всех, что нам нужно прекратить использование 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 n, где вы можете создать два сталкивающихся PDF-файла: получить SHA- 1 цифровая подпись на первом файле PDF, которая также может использоваться как действительная подпись на втором файле PDF.
См. Также " У дверей смерти в течение многих лет широко используемая функция SHA1 теперь мертва ", и эта иллюстрация.
Обновление от 26 февраля: Линус подтвердил следующие пункты в посте Google+:
(1) Прежде всего - небо не падает. Существует большая разница между использованием криптографического хэша для таких вещей, как подпись безопасности, и его использованием для генерации "идентификатора контента" для системы с адресным контентом, такой как git.
(2) Во-вторых, природа этой конкретной атаки SHA1 означает, что на самом деле довольно легко противостоять, и уже было два набора патчей для этого смягчения.
(3) И, наконец, на самом деле существует довольно простой переход к другому хешу, который не сломает мир - или даже к старым git-репозиториям.
Относительно этого перехода см. Git 2.16 Q1 2018, в котором добавлена структура, представляющая алгоритм хеширования. Осуществление этого перехода началось.
Оригинальный ответ (25 февраля) Но:
- Это позволяет подделать большой двоичный объект, однако SHA-1 дерева все равно изменится, поскольку размер поддельного большого двоичного объекта может не совпадать с исходным: см. " Как рассчитывается git-хэш? "; BLA- объект SHA1 вычисляется на основе содержимого и размера.
Это имеет некоторые проблемы дляgit-svnхотя Вернее с самим svn, как видно здесь. - Как я уже упоминал в своем первоначальном ответе, стоимость такой попытки пока непомерно высока (6500 процессорных лет и 100 графических лет). См. Также Валери Анита Аврора в разделе " Время жизни криптографических хеш-функций ".
- Как отмечалось ранее, речь идет не о безопасности или доверии, а о целостности данных (устранение дублирования и обнаружение ошибок), которые могут быть легко обнаружены
git fsckкак уже упоминалось Линусом Торвальдсом сегодня.git fsckбудет предупреждать о коммит-сообщении с непрозрачными данными, скрытыми послеNUL(хотяNULне всегда присутствует в мошенническом файле).
Не все включаютсяtransfer.fsck, но GitHub делает: любой толчок будет прерван в случае некорректного объекта или неработающей ссылки. Хотя... есть причина, по которой она не активирована по умолчанию. - PDF-файл может содержать произвольные двоичные данные, которые вы можете изменить, чтобы создать конфликтующий SHA-1, а не поддельный исходный код.
Актуальная проблема при создании двух Git-репозиториев с одинаковым хешем коммитов и разным содержимым. И даже тогда атака остается запутанной. - Линус добавляет:
Весь смысл SCM в том, что речь идет не о разовом событии, а о непрерывной истории. Это также в основном означает, что успешная атака должна работать со временем, а не быть обнаруживаемой.
Если вы можете одурачить SCM один раз, вставить свой код, и он будет обнаружен на следующей неделе, вы на самом деле не сделали ничего полезного. Вы только сожгли себя.
Джои Хесс пробует эти PDF в репозитории Git, и он обнаружил:
Это включает в себя два файла с одинаковым SHA и размером, которые получают разные BLOB-объекты благодаря тому, как 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, а затем по умолчанию покажите хеш в виде шестнадцатеричной строки из 40 символов (вроде того, как мы уже сокращаем вещи в много ситуаций).
Таким образом, инструменты вокруг git даже не видят изменений, если они не переданы каким-то особым--full-hash"аргумент (или"--abbrev=64"или что-то еще - по умолчанию мы сокращаем до 40).
Тем не менее, план перехода (от SHA1 к другой хэш-функции) все еще будет сложным, но активно изучается.
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-1:
В феврале 2005 года было объявлено о нападении Сяоюнь Вана, Ицюня Лизы Инь и Хунбо Ю. Атаки могут обнаружить столкновения в полной версии SHA-1, требующей менее 2^69 операций. (Поиск грубой силы потребует 2^80 операций.)
Существует несколько различных моделей атак для хэшей, таких как SHA-1, но обычно обсуждается поиск коллизий, включая инструмент Марка Стивенса " HashClash".
Как указали люди, вы можете вызвать хеш-коллизию с git, но это не приведет к перезаписи существующих объектов в другом хранилище. Я бы даже git push -f --no-thin не будет перезаписывать существующие объекты, но не уверен на 100%.
Тем не менее, если вы взломаете удаленный репозиторий, вы можете сделать свой ложный объект более старым, возможно, внедрив взломанный код в проект с открытым исходным кодом на github или подобном. Если вы были осторожны, возможно, вы могли бы представить взломанную версию, которую загружали новые пользователи.
Однако я подозреваю, что многие вещи, которые могут сделать разработчики проекта, могут либо разоблачить, либо случайно уничтожить ваш взломанный многомиллионный взлом. В частности, это много денег на ветер, если какой-нибудь разработчик, которого вы не взломали, когда-либо запускает вышеупомянутый git push --no-thin после изменения созданных файлов, иногда даже без --no-thin в зависимости.