Как недавно обнаруженное столкновение sha1 влияет на git?

Ответ 1

Изменить, конец декабря 2017 года: Git версия 2.16 постепенно приобретает внутренние интерфейсы, позволяя использовать разные хэши. Еще предстоит пройти долгий путь.

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

Я загрузил оба этих файла, shattered-1.pdf и shattered-2.pdf, и поместил их в новый пустой репозиторий:

macbook$ shasum shattered-*
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf
macbook$ cmp shattered-*
shattered-1.pdf shattered-2.pdf differ: char 193, line 8
macbook$ git init
Initialized empty Git repository in .../tmp/.git/
macbook$ git add shattered-1.pdf 
macbook$ git add shattered-2.pdf 
macbook$ git status
On branch master

Initial commit

Changes to be committed:
  (use "git rm --cached <file>..." to unstage)

    new file:   shattered-1.pdf
    new file:   shattered-2.pdf

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

macbook$ git ls-files --stage
100644 ba9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0 0   shattered-1.pdf
100644 b621eeccd5c7edac9b7dcba35a8d5afd075e24f2 0   shattered-2.pdf

Это две контрольные суммы SHA-1 для файлов, хранящихся в Git: один - ba9aa..., а другой - b621e.... Также нет 38762c.... Но, почему?

Ответ заключается в том, что Git хранит файлы, а не как они сами, а скорее как строковый литерал blob, пробел, размер файла с десятичной точкой и байт ASCII NUL, а затем данные файла. Оба файла имеют одинаковый размер:

macbook$ ls -l shattered-?.pdf
...  422435 Feb 24 00:55 shattered-1.pdf
...  422435 Feb 24 00:55 shattered-2.pdf

поэтому оба имеют префикс с литеральным текстом blob 422435\0 (где \0 представляет один байт, октальные escape-последовательности a la C или Python в строках).

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

Причина, по которой это должно стать неудивительным, состоит в том, что если результат окончательной контрольной суммы не был бы чрезвычайно чувствителен к позиции, а также к значению каждого входного бита, было бы легко произвести столкновения по требованию, взяв известный входной файл и просто переставляя некоторые из его бит. Эти два входных файла дают ту же сумму, несмотря на наличие другого байта в char 193, line 8, но этот результат был достигнут, по мнению исследователей, путем опробования более 9 квинтиллионов (короткий масштаб). Чтобы получить этот результат, они поставили тщательно выбранные блоки необработанных данных в контролируемое положение, что повлияло бы на суммы, пока они не найдут пары входов, которые привели к столкновению.

Добавив заголовок blob, Git переместил позицию, уничтожив вычисление 110-GPU-годов в одном более или менее случайном отрыве.

Теперь, зная, что Git сделает это, они могут повторить свои вычисления 110-GPU-лет с входами, которые начинаются с blob 422435\0 (при условии, что их жертвенные блоки не будут сильно задвигаться, а фактические количество требуемых вычислительных вычислений, вероятно, будет меняться, так как процесс немного stochastic). Затем они придумали два разных файла, которые могли бы удалить заголовок blob. Эти два файла теперь будут иметь разные контрольные суммы SHA-1 друг от друга, но когда git add -ed, обе будут иметь одну и ту же контрольную сумму SHA-1.

В этом конкретном случае первый добавленный файл будет "выиграть" слот. (Предположим, что он называется shattered-3.pdf.) Достаточно хорошо Git - я совсем не уверен, что текущий Git - это хорошо; см. ответ на эксперимент Ruben на Как Git обрабатывать столкновение SHA-1 на блобе? - заметили бы, что git add shattered-4.pdf, пытаясь добавить второй файл, столкнулся с первым, но отличным shattered-3.pdf, и предупредил бы вас и завершил бы шаг git add. В любом случае вы не сможете добавить оба этих файла в один репозиторий.

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

Ответ 2

Возможно, ответ Линуса может пролить свет:

IIRC кто-то работал над параметризацией git допущений SHA1   поэтому хранилище может в конечном итоге использовать более безопасный хеш. Как далеко   что получилось? Есть еще много "40" констант в git.git HEAD.

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

Так как теперь мы имеем столкновений в действительных файлах PDF, столкновений в действительном git  возможно, могут быть созданы объекты commit и tree.

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

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

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

Иными словами, я сомневаюсь, что небо падает на git в качестве источника инструмент управления. Мы хотим перейти на другой хэш? Да. Это "игра окончена" для SHA1, как люди хотят сказать? Наверное, нет.

Я не видел деталей атаки, но я уверен, что

(a) тот факт, что мы имеем отдельную кодировку размера, делает ее сложнее сделать на git объектах в первую очередь

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

Линус

Источник: https://marc.info/?l=git&m=148787047422954