Как недавно обнаруженное столкновение SHA-1 влияет на Git?
Недавно группа исследователей создала два файла с одинаковым хешем SHA-1 ( https://shattered.it/).
Поскольку Git использует этот хэш для внутреннего хранения, насколько эта атака влияет на Git?
2 ответа
Редактирование, конец декабря 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, пробел, размер файла в десятичном формате и байт NSC ASCII, а затем данные файла. Оба файла имеют одинаковый размер:
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 представляет одиночный байт (восьмеричное восьмеричное значение C или Python в строках).
Возможно, это удивительно - или нет, если вы знаете что-нибудь о том, как рассчитывается SHA-1, - добавление одного и того же префикса к двум разным файлам, которые, тем не менее, ранее производили одну и ту же контрольную сумму, заставляет их теперь создавать разные контрольные суммы.
Причина, по которой это должно стать неудивительным, заключается в том, что если бы конечный результат контрольной суммы не был чрезвычайно чувствительным к позиции, а также к значению каждого входного бита, было бы легко создать коллизии по требованию, взяв известный входной файл и просто повторно -строить некоторые из его битов. Эти два входных файла дают одинаковую сумму, несмотря на то, что в char 193, line 8, но этот результат был достигнут, по словам исследователей, при попытке ввода более 9 квинтиллионов ( короткая шкала). Чтобы получить такой результат, они помещают в тщательно отобранные блоки необработанных данных в контролируемой ими позиции, которая будет влиять на суммы, пока не найдут пары входных данных, которые привели к коллизии.
Добавляя blob В заголовке Git сдвинул позицию, уничтожив 110-GPU-годы вычислений в одной более или менее случайной отрыжке.
Теперь, зная, что Git сделает это, они могли бы повторить свои вычисления на 110 GPU с вводами, которые начинаются с blob 422435\0 (при условии, что их жертвенные блоки не будут слишком сильно сдвигаться; и фактическое количество необходимых вычислений в годах на GPU, вероятно, будет варьироваться, поскольку процесс немного стохастический). Затем они придумают два разных файла, которые могут иметь blob заголовок сорван. Эти два файла теперь будут иметь разные контрольные суммы SHA-1 друг от друга, но когда git add -ed, оба будут производить одну и ту же контрольную сумму SHA-1.
В этом конкретном случае первый добавленный файл "выиграет" слот. (Давайте предположим, что он назван shattered-3.pdf.) Достаточно хороший Git - я совсем не уверен, что текущий Git такой хороший; см . основанный на эксперименте ответ Рубена на Как Git будет обрабатывать столкновение SHA-1 на BLOB-объекте? - заметил бы это git add shattered-4.pdf, пытаясь добавить второй файл, столкнулся с первым, но другим shattered-3.pdf и предупредит вас и провалит git add шаг. В любом случае вы не сможете добавить оба этих файла в один репозиторий.
Но сначала кто-то должен потратить гораздо больше времени и денег, чтобы вычислить новое столкновение хешей.
Возможно, ответ Линуса может пролить свет
IIRC кто-то работал над параметризацией предположений SHA1 для git, чтобы в конечном итоге хранилище могло использовать более безопасный хеш. Как далеко это зашло? В git.git HEAD все еще много "40" констант.
Я не думаю, что вы обязательно захотите изменить размер хэша. Вы можете использовать другой хеш и просто использовать те же 160 бит из него.
Поскольку теперь у нас есть коллизии в допустимых файлах PDF, коллизии в действительных git commit и tree объектах, вероятно, могут быть созданы.
Я еще не видел атаки, но git на самом деле не просто хэширует данные, а добавляет к ней поле типа / длины. Это обычно приводит к тому, что атаки со столкновением становятся намного сложнее, потому что вы либо должны сделать результирующий размер одинаковым, либо вы также должны иметь возможность редактировать поле размера в заголовке.
У pdf такой проблемы нет, у них есть фиксированный заголовок, и вы можете произвольно добавить тихие данные в середину, которые просто не отображаются.
Таким образом, pdf создает гораздо лучший вектор атаки именно потому, что они представляют собой довольно непрозрачный формат данных. В некоторых местах Git хранит непрозрачные данные (например, мы намеренно скрываем объекты в коммит-объектах, но по определению непрозрачные данные являются довольно вторичными.
Другими словами: я сомневаюсь, что в качестве инструмента управления исходным кодом небо падает на git. Мы хотим перейти на другой хеш? Да. Это "игра окончена" для SHA1, как люди хотят сказать? Возможно нет.
Я не видел детали атаки, но держу пари
(а) тот факт, что у нас есть отдельная кодировка размера, во-первых, значительно усложняет работу с объектами git.
(б) мы, вероятно, можем легко добавить некоторые дополнительные проверки работоспособности к непрозрачным данным, которые у нас есть, чтобы было намного сложнее скрывать случайные данные, от которых эти атаки почти всегда зависят.
Линус