Почему Git использует криптографическую хеш-функцию?

140

Почему Git использует SHA-1 , криптографическую хеш-функцию, вместо более быстрой некриптографической хеш-функции?

Связанный вопрос:

Вопрос о переполнении стека Почему Git использует SHA-1 в качестве номеров версий? спрашивает, почему Git использует SHA-1 вместо последовательных чисел для коммитов.

Праксеолитический
источник
Лично я считаю, что даже использование сломанного SHA-1 вместо SHA-2 было преждевременной оптимизацией.
CodesInChaos 01
7
@CodesInChaos: кроме того, включение какого-либо конкретного алгоритма в код было ужасным нарушением принципов DI. Должен быть где-то в файле конфигурации XML ;-)
Стив Джессоп
Обновление декабрь 2017 г. с Git 2.16 (1 квартал 2018 г.): усилия по поддержке альтернативного SHA продолжаются: см. « Почему Git не использует более современный SHA? ».
VonC
Нет хороших 160-битных и выше некриптографических хешей. Большинство из них являются высокооптимизированными 32-битными, 64-битными или 128-битными функциями. 128-битный - это нормально, но мне кажется, что 128-битный - это немного мало для такого большого проекта, как git. Если бы получился быстрый и качественный 224/256-битный хеш, он, вероятно, был бы идеальным.
bryc

Ответы:

198

TL; DR;


Вы можете проверить это у самого Линуса Торвальдса, когда он представил Git Google в 2007 году :
(выделено мной)

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

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

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

Так что есть несколько причин, чтобы полюбить и криптографическую сторону, но на самом деле речь идет о способности доверять своим данным.
Я гарантирую вам, что если вы поместите свои данные в git, вы можете доверять тому факту, что пять лет спустя, после того, как они будут преобразованы с вашего жесткого диска на DVD на любую новую технологию и вы скопировали их вместе, через пять лет вы сможете проверить данные, которые вы get back out - это те же самые данные, которые вы ввели. И это то, что вам действительно следует искать в системе управления исходным кодом .


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


Я упоминал в « Как git обработает коллизию SHA-1 на большом двоичном объекте? », Что вы можете спроектировать фиксацию с определенным префиксом SHA1 (все еще очень затратное мероприятие).
Но суть остается неизменной, как упоминает Эрик Синк в книге « Git: Cryptographic Hashes » ( Контроль версий на примерах (2011)) :

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

Труднее найти хороший некриптографический хэш с низким уровнем коллизий, если вы не рассматриваете такие исследования, как « Поиск современных некриптографических хешей с помощью генетического программирования ».

Вы также можете прочитать « Рассмотрите возможность использования некриптографического алгоритма хеширования для ускорения хеширования », в котором упоминается, например, « xxhash », чрезвычайно быстрый некриптографический алгоритм хеширования , работающий на скоростях, близких к пределам ОЗУ.


Обсуждения изменения хэша в Git не новы:

(Линус Торвальдс)

От кода Mozilla практически ничего не осталось , но я начал с него. Оглядываясь назад, я, вероятно, должен был начать с asm-кода PPC, который уже разумно блокировал - но это "20/20 ретроспективный взгляд".

К тому же, код Mozilla - это ужасная куча грязи, поэтому я был так убежден, что могу улучшить ситуацию. Так что это своего рода источник для него, даже если он больше касается мотивационной стороны, чем какой-либо фактический оставшийся код;)

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

(Линус Торвальдс)

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

(Джон Тэпселл - johnflux)

Инженерные затраты на обновление git с SHA-1 до нового алгоритма намного выше . Я не уверен, как это можно сделать хорошо.

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

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

Короче, переключиться на любой хэш непросто.


Обновление от февраля 2017 года: да, теоретически возможно вычислить конфликтующий SHA1: shattered.io

Как влияет на ЖКТ?

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

Но:

Эта атака потребовала более 9 223 372 036 854 775 808 вычислений SHA1. Для этого потребовалась вычислительная мощность, эквивалентная 6500 годам вычислений на одном процессоре и 110 годам вычислений на одном графическом процессоре.

Так что давайте пока не паникуем.
Подробнее см. « Как Git обработает столкновение SHA-1 с BLOB-объектом? ».

VonC
источник
8
Похоже, что недавний урожай высококачественных некриптографических хэш-функций, таких как xxhash, появился слишком поздно - сразу после git.
Praxeolitic
3
@Praxeolitic действительно. Обсуждалась замена SHA1 другим хешем, но для этого просто потребовалось бы довольно много работы, для чего-то, что на данный момент работает нормально.
VonC
«мы знаем, что хэш хорошо распределен, и нам не нужно беспокоиться о некоторых проблемах распространения» - почему это проблема для scm?
ехал 06
@roded частота столкновений достаточно низка, чтобы хорошо подходить для SCM, где данные обычно не случайны, а являются тестовыми файлами.
VonC
1
На самом деле существует причина безопасности для использования криптографического хеша. Когда автор (скажем, Линус) хочет сократить выпуск (например, Linux), люди хотят знать, что исходный код, который они загружают, соответствует тому, что автор намеревался включить в выпуск. Для этого последний хэш фиксации в выпуске помечается, и этот тег подписывается. Если бы цепочка хэшей фиксации, оканчивающаяся на теге, не была криптографически защищенной, то источник мог быть искажен чем-то другим, чем задумал автор.
Кристофер Кинг,