Что бы на самом деле произошло, если бы я столкнулся с хешем при использовании git?

Например, мне удается зафиксировать два файла с одной и той же контрольной суммой sha1, заметит ли это git или испортит один из файлов?

Можно ли улучшить git, чтобы жить с этим, или мне придется перейти на новый алгоритм хеширования?

(Пожалуйста, не отклоняйте этот вопрос, обсуждая, насколько это маловероятно - спасибо)

Сбор атомов на 10 лун

Хеш SHA-1 представляет собой строку из шестнадцатеричных символов ... это 4 бита на символ, умноженное на 40 ... 160 бит. Теперь мы знаем, что 10 бит - это приблизительно 1000 (1024, если быть точным), что означает, что существует 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 различных хэшей SHA-1 ... 10 ⁴⁸ .

Что это эквивалент? Ну, Луна состоит из 10 ⁴⁷ атомов. Так что, если у нас есть 10 Лун ... и вы случайно выберете один атом на одной из этих лун ... и затем снова выберете случайный атом на них ... тогда вероятность того, что вы выберете один и тот же атом дважды , вероятность того, что два данных git коммита будут иметь одинаковый хэш SHA-1.

Развивая это, мы можем задать вопрос ...

Сколько коммитов вам нужно в репозитории, прежде чем начинать беспокоиться о коллизиях?

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

В Википедии есть таблица вероятности столкновений с Парадоксом Дня Рождения . Нет записи для хеша из 40 символов. Но интерполяция записей для 32 и 48 символов приводит нас к диапазону 5 * 10 ²² git коммитов с вероятностью столкновения 0,1%. Это пятьдесят тысяч миллиардов миллиардов различных коммитов , или пятьдесят Зетта коммитов , прежде чем вы достигнете даже 0,1% вероятности вашего столкновения.

Сумма байтов только хэшей для этих коммитов будет больше данных, чем все данные, сгенерированные на Земле за год, то есть вам нужно будет производить код быстрее, чем YouTube транслирует видео. Удачи с этим. : D

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

«Но когда столкновение действительно произойдет, то , что происходит на самом деле?»

Хорошо, предположим, что невероятное действительно случается, или предположим, что кому-то удалось приспособить преднамеренное столкновение SHA-1 . Что происходит потом?

В этом случае есть отличный ответ, когда кто-то экспериментировал с этим . Я процитирую из этого ответа:

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

Как может показаться, некоторые случаи не очень хороши. Особенно случаи № 2 и № 3 портят ваш репозиторий. Тем не менее, кажется, что ошибка остается в этом хранилище, и атака / причудливая невероятность не распространяется на другие хранилища.

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

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

Смотрите пост Линуса Торвальдса в теме «Начинаешь думать о ша-256?» в списке рассылки git .

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

Здесь есть принципиальное недопонимание теории информации. Если вы сократите большой объем информации до меньшего объема путем отбрасывания некоторого количества (т. Е. Хэша), будет возможность столкновения, непосредственно связанного с длиной данных. Чем короче данные, тем МЕНЬШЕ это будет. Теперь, подавляющее большинство столкновений будет бредовым, что сделает их намного более вероятными (вы никогда не отметите тарабарщину ... даже двоичное изображение несколько структурировано). В конце концов, шансы невелики. Чтобы ответить на ваш вопрос, да, git будет обрабатывать их как одинаковые, изменение алгоритма хеширования не поможет, потребуется некоторая «вторая проверка», но в конечном итоге вам потребуется столько же данных «дополнительной проверки» поскольку длина данных должна быть на 100% уверена ... имейте в виду, что вы будете 99,99999 .... до действительно длинного числа цифр .... конечно с простой проверкой, как вы описываете. SHA-x - это криптографически надежные хэши, что означает, что обычно нетрудно преднамеренно создать два исходных набора данных, которые ОЧЕНЬ ПОДОБНЫ друг другу и имеют одинаковый хэш. Один бит изменений в данных должен создать более одного (желательно как можно большего) битов изменения в хеш-выводе, что также означает, что очень трудно (но не совсем невозможно) вернуться из хеша к полному набору коллизии, и, таким образом, вытащить исходное сообщение из этого набора коллизий - все, кроме нескольких, будут бессмысленными, а из тех, которых нет, еще есть огромное количество, которое нужно просеять, если длина сообщения будет какой-либо значительной длины. Недостатком крипто-хеша является то, что они медленно вычисляются ... в общем.

Итак, что же все это значит для Git? Немного. Хэши выполняются настолько редко (относительно всего остального), что их вычислительные потери в целом незначительны для операций. Вероятность столкновения с парой коллизий настолько мала, что это нереальный шанс произойти и не быть обнаруженным немедленно (т. Е. Ваш код, скорее всего, внезапно прекратит сборку), позволяя пользователю решить проблему (создать резервную копию ревизии, и внесите изменения снова, и вы почти наверняка получите другой хэш из-за изменения времени, которое также передает хэш в git). Скорее всего, это будет реальной проблемой для вас, если вы храните произвольные двоичные файлы в git, что на самом деле не является той моделью, которая используется в них. Если вы хотите сделать это ... вам лучше использовать традиционную базу данных.

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

Можно ли улучшить git, чтобы жить с этим, или мне придется перейти на новый алгоритм хеширования?

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

Хорошее исследование можно найти в разделе « Как Git справится со столкновением SHA-1 на BLOB-объекте? ».

Поскольку теперь возможна коллизия SHA1 (как я упоминаю в этом ответе с помощью shattered.io ), знайте, что Git 2.13 (второй квартал 2017 года) улучшит / ослабит текущую ситуацию с помощью варианта реализации SHA-1 «обнаружение попытки создать коллизии». Марк Стивенс (CWI) и Дэн Шумов (Microsoft) .

Смотрите коммит f5f5e7f , коммит 8325e43 , коммит c0c2006 , коммит 45a574e , коммит 28dc98e (16 марта 2017 г.) Джеффом Кингом ( peff) .
^{(Слиты Junio C Hamano - gitster- в фиксации 48b3693 , 24 марта 2017)}

Makefile: сделать DC_SHA1по умолчанию

По умолчанию мы использовали реализацию SHA1 из библиотеки OpenSSL.
Поскольку мы пытаемся быть осторожными против атак коллизий после недавнего «разрушенного» объявления, переключите стандартное значение, чтобы побудить людей использовать вместо этого реализацию DC_SHA1.
Те, кто хочет использовать реализацию из OpenSSL, могут явно запросить ее OPENSSL_SHA1=YesPleaseпри запуске " make".

На самом деле у нас нет столкновения Git-объекта, поэтому лучшее, что мы можем сделать, - это запустить один из разбитых PDF-файлов через test-sha1. Это должно вызвать проверку столкновения и умереть.

Можно ли улучшить Git, чтобы жить с этим, или мне придется перейти на новый алгоритм хеширования?

Обновление в декабре 2017 года с Git 2.16 (Q1 2018): эта работа по поддержке альтернативного SHA уже ведется: см. « Почему Git не использует более современный SHA? ».

Вы сможете использовать другой алгоритм хэширования: SHA1 больше не единственный для Git.

Git 2.18 (Q2 2018) документирует этот процесс.

См. Коммит 5988eb6 , коммит 45fa195 (26 марта 2018 г.) Ævar Arnfjörð Bjarmason ( avar) .
^{(Объединено с Junio ​​C Hamano - gitster- в фиксации d877975 , 11 апреля 2018)}

doc hash-function-transition: уточнить, что означает SHAttered

Попытайтесь уточнить, что атака SHAttered означает на практике для Git.
В предыдущей версии текста не упоминалось о том, что в Git уже есть смягчение для этой конкретной атаки, которая, как утверждают исследователи SHAttered, будет обнаруживать криптоаналитические атаки на столкновения.

Возможно, я неправильно понял некоторые нюансы, но насколько я знаю, этот новый текст точно суммирует текущую ситуацию с SHA-1 в git. Т.е. git на самом деле больше не использует SHA-1, он использует Hardened-SHA-1 (просто так получаются одинаковые выходы 99.99999999999 ...% времени).

Таким образом, предыдущий текст был неверным, утверждая, что:

[...] В результате [SHAttered] SHA-1 больше не может считаться криптографически безопасным [...]

Это не тот случай. У нас есть меры против SHAttered, однако мы считаем целесообразным переходить к работе в случае появления NewHashбудущих уязвимостей в SHA-1 или Hardened-SHA-1.

Итак, новая документация теперь гласит:

Git v2.13.0 и более поздние версии впоследствии по умолчанию перешли к усиленной реализации SHA-1, которая не уязвима для атаки SHAttered.

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

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

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

Примечание: тот же самый документ (Q3 2018, Git 2.19) явно ссылается на «новый хеш» как SHA-256 : см. « Почему Git не использует более современный SHA? ».

Google теперь утверждает, что столкновение SHA-1 возможно при определенных предварительных условиях: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

Поскольку git использует SHA-1 для проверки целостности файла, это означает, что целостность файла в git нарушена.

IMO, git определенно должен использовать лучший алгоритм хеширования, поскольку теперь возможна преднамеренная коллизия.

Столкновение хешей настолько маловероятно, что это просто сногсшибательно! Ученые всего мира очень стараются достичь его, но пока не справились. Однако для некоторых алгоритмов, таких как MD5, это удалось.

Каковы шансы?

SHA-256 имеет 2 ^ 256 возможных хэшей. Это около 10 ^ 78 . Или, чтобы быть более наглядным, вероятность столкновения составляет около

1: 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

Шанс выиграть в лотерею составляет около 1: 14 млн . Вероятность столкновения с SHA-256 подобна выигрышу в лотерею 11 дней подряд !

Математическое объяснение: 14 000 000 ^ 11 ~ 2 ^ 256

Кроме того, во Вселенной насчитывается около 10 ^ 80 атомов. Это всего в 100 раз больше, чем комбинаций SHA-256.

Успешное столкновение MD5

Даже для MD5 шансы малы. Хотя математикам удалось создать столкновение:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 8 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 b 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 a 80d1e c69821bcb6a88393 96f965 2 b6ff72a70

имеет тот же MD5, что и

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 0 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 f 1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 3 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 2 80d1e c69821bcb6a88393 96f965 a b6ff72a70

Это не означает, что MD5 теперь менее безопасен, поскольку его алгоритм взломан. Вы можете специально создавать коллизии MD5, но вероятность случайного коллизии MD5 по-прежнему составляет 2 ^ 128, что все еще много.

Вывод

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

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

Недавно я нашел сообщение от 2013-04-29 в дискуссионной группе BSD на

http://openbsd-archive.7691.n7.nabble.com/Why-does-OpenBSD-use-CVS-td226952.html

где постер утверждает:

Однажды я столкнулся с хеш-коллизией, используя git rebase.

К сожалению, он не предоставляет никаких доказательств своего утверждения. Но, возможно, вы хотели бы попытаться связаться с ним и спросить его об этом предполагаемом инциденте.

Но на более общем уровне из-за атаки на день рождения вероятность столкновения хеша SHA-1 равна 1 в пау (2, 80).

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

Однако это относится только к тем версиям, которые фактически остаются в истории версий.

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

Но если столкновение происходит во время перебазирования или ответвления фильтра, оно все равно может иметь неблагоприятные последствия.

Другой способ - оценить общее количество хэшированных объектов в git-репозиториях и посмотреть, насколько они далеки от pow (2, 80).

Допустим, у нас около 8 миллиардов человек, и все они будут работать с git и держать свои версии в 100 репозиториях на человека. Предположим далее, что средний репозиторий имеет 100 коммитов и 10 файлов, и только один из этих файлов изменяется на коммит.

Для каждой ревизии у нас есть по крайней мере хэш для объекта дерева и самого объекта фиксации. Вместе с измененным файлом у нас есть 3 хеша на ревизию и, таким образом, 300 хешей на репозиторий.

Для 100 хранилищ из 8 миллиардов человек это дает пау (2, 47), который еще далек от пау (2, 80).

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