The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

Коллизии в сокращённых идентификаторах коммитов в ядре Linux

31.12.2024 10:48

Кейс Кук (Kees Cook), бывший главный системный администратор kernel.org и лидер Ubuntu Security Team, продемонстрировал возможность создания коммита, сокращённый идентификатор которого совпадает с коммитом, ранее добавленным в ядро Linux. Эксперимент проведён в качестве подтверждения целесообразности перехода на 16-символьные сокращённые идентификаторы коммитов в ядре Linux, ранее обсуждавшегося в списке рассылки разработчиков ядра, но не одобренного Линусом Торвальдсом.

Сокращённые идентификаторы коммитов формируются через оставление первых 12 символов от хэша SHA-1 (48 бит из 160 бит). Так как число объектов в ядре, идентифицируемых через хэш SHA-1, превысило 13 миллионов, возникновение коллизий при использовании 12-символьного префикса стало делом времени. В качестве примера показаны уже добавленные в ядро объекты, пересекающиеся по своим 11-символьным идентификаторам. Кроме того, упомянуто, что пересечение 12-символьных идентификаторов уже фиксировалось в октябре, но до отправки патча было выявлено утилитой checkpatch.

Сокращённые идентификаторы применяются при публикации коротких ссылок на коммиты, а также указываются при отправке изменений в теге "Fixes", в качестве ссылки на коммит, проблема в котором устранена в отправленном патче (например, "Fixes: e21d2170f366"). Возникновение коллизий, при которых несколько разных изменений оказываются связаны с одним сокращённым идентификатором, могут привести к нарушению работы инструментов для анализа и проверки изменений, учитывающих содержимое тегов "Fixes". Например, данные теги учитываются в обработчике check_fixes, применяемом в ветке linux-next, а также в скриптах анализа исправления уязвимостей и отслеживания жизненного цикла патчей.

Линус Торвальдс скептически отнёсся к предложению увеличить минимальный размер сокращённых идентификаторов, так как фактически число коммитов в репозитории заметно меньше, чем объектов (примерно 1/8). Скорее всего, если случайные пересечения и возникнут, то они будут между коммитом и объектом какого-то другого типа (например, блобом или веткой). По его мнению, сокращённые идентификаторы на то и сокращённые, чтобы быть наглядными, читаемыми и легко цитируемыми, и для увеличения их размера пока нет объективных предпосылок.

Один из разработчиков предложил добиться сокращения размера при увеличении числа значимых бит, используя новый формат на базе кодировки Base36 (символы 0-9a-z) вместо шестнадцатеричных цифр. По мнению Линуса подобное изменение создаст больше проблем, чем решит. Например, потребуется добавить поддержку нового формата в имеющиеся утилиты и ввести идентификатор формата для того, чтобы различать старый и новый формат.

Для демонстрации, что проблема с сокращёнными идентификаторами не является умозрительной и её решение не стоит откладывать, Кейс Кук сформировал изменение документации ядра, сокращённый идентификатор которого (1da177e4c3f4) совпал с идентификатором коммита по созданию ветки ядра 2.6.12-rc2. Коллизию удалось подобрать за 6 часов вычислений на системе с GPU NVIDIA GeForce RTX 3080.

Подбор был выполнен с использованием инструментария lucky-commit - в текст целевого патча добавлялись случайные пробелы до тех пор, пока 12-символьный префикс SHA-1 не совпал с уже имевшимися в ядре префиксами коммитов. По мнению Кейса проблему представляют не столько случайные пересечения, сколько возможность манипуляции с сокращёнными идентификаторами во вредоносных целях, например, для обхода каких-то проверок.

  1. Главная ссылка к новости (https://fosstodon.org/@kees/11...)
  2. OpenNews: Предложен метод определения коллизий в SHA-1, пригодный для атаки на PGP
  3. OpenNews: Представлен более эффективный метод определения коллизий для SHA-1
  4. OpenNews: До конца года ожидается появление практических атак по подбору коллизий для SHA-1
  5. OpenNews: Опубликованы исходные тексты программы для поиска коллизий в MD5
Лицензия: CC BY 3.0
Короткая ссылка: https://opennet.ru/62495-sha
Ключевые слова: sha, kernel, collision, git
При перепечатке указание ссылки на opennet.ru обязательно


Обсуждение (51) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.1, Аноним (1), 12:08, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • –4 +/
    А как этим можно злоупотребить? Я пример понял но вот реальный обход нет. Да и Торвальдс и так все сам читает.
     
     
  • 2.47, Аноним (-), 18:30, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +2 +/
    > А как этим можно злоупотребить? Я пример понял но вот реальный обход нет.
    > Да и Торвальдс и так все сам читает.

    Это сложно ибо при этом патч должен осмыленно выглядеть и проч, не вызывая подозрений. Но те кто удумал сократить хеши до 48 бит - все же нарываются. Простите, но высокосекурный DES с 56 битов вынесли полным перебором еще во времена царя гороха. А некоторые до сих пор не доперли что так делать не надо.

     
     
  • 3.57, bonifatium (?), 19:54, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    короткий хэш - это просто обрезанный до n символов полный хэш (для человеков и ui). сами хэши остаются как были
     
     
  • 4.62, Аноним (62), 23:33, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +2 +/
    > короткий хэш - это просто обрезанный до n символов полный хэш
    > (для человеков и ui). сами хэши остаются как были

    Если удалось на...ть человека, показав ему короткий хэш такой же как заявлено - он его и втянет, нисколько не сомневаясь что все как надо. А то что там хвост не совпадал... кто ж его знал, если попросили - вот это?!

     

  • 1.10, Аноним (10), 13:17, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    > но до отправки патча было выявлено утилитой checkpatch.

    Выглядит как майнинг коллизий.

     
  • 1.11, Аноним (11), 13:19, 31/12/2024 Скрыто ботом-модератором [﹢﹢﹢] [ · · · ]     [к модератору]
  • –6 +/
     

     ....ответы скрыты (2)

  • 1.12, Илья (??), 13:19, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • –4 +/
    Есть люди, которые никогда не поймут отличие гуида от хеша, и которые на серьёзных щах будут утверждать что нужно просто использовать хорошую хеш функцию

    Это не лечится

     
     
  • 2.52, Аноним (52), 19:03, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Ненужно ударяться в преждевременную оптимизацию.
     
     
  • 3.72, Илья (??), 09:09, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +2 +/
    > Ненужно ударяться в преждевременную оптимизацию.

    Глупый, что-ли? Коллизии выстреливают года через два, это именно то место, которое нужно предварительно правильно делать

     

  • 1.15, lizard (??), 13:35, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +7 +/
    Пользуйтесь SVN: 1,2,... 100000 цифирьки увеличиваются и никогда никаких коллизий.
     
     
  • 2.17, Аноним (16), 13:40, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Проблема в подмене смысла этих цифр с буквами. Глупость - она такая: хоть алфавит смени, но не помогает.
     
  • 2.48, Аноним (-), 18:32, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > Пользуйтесь SVN: 1,2,... 100000 цифирьки увеличиваются и никогда никаких коллизий.

    Ога, сломал 1 сервак - и выгрузил всей толпе неведомые фекальи. А без сервака этот антик вообще неоперабелен, и уж точно такой подарок проверками по локальным репам замечен не будет.

     
  • 2.78, Dmitry (??), 21:49, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    Svn централизованная система и поэтому это в принципе возможно
     

  • 1.25, ijuij (?), 14:06, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • –2 +/
    Я уважаю Кейса Кука больше, чем Линуса, НО в этой ситуации я согласен с Линусом. 🤷‍♂️💬

     
     
  • 2.49, Аноним (-), 18:34, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    > Я уважаю Кейса Кука больше, чем Линуса, НО в этой ситуации я согласен с Линусом. 🤷‍♂️💬

    Да это не киса куку предложил хрень с base36, как по мне - так стоит просто оперировать полными хешами. По хорошему - перйдя на SHA256.

     

  • 1.28, Аноним (28), 14:54, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    К полному хешу можно еще unix-timestamp добавить для надежности.
     
     
  • 2.35, bonifatium (?), 16:11, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • –2 +/
    что бы что? проблема в коллизии первых 12 символов, а не в полном хэше
     
     
  • 3.67, Neon (??), 02:46, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    А на фига использовать только первые 12 символов ?! Какой умник это придумал ?
     
     
  • 4.74, Аноним (-), 09:21, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    Потому-что 12 символов это коротко.
     

  • 1.32, Аноним (32), 15:07, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • –3 +/
    Не понимаю местных комментаторов, которым коллизии непочем. Коллизии - это страшно, нужно предотвращать, удлинять. ShA-1 в целом тоже уже устаревшая хэш-функция, но понимаю, что на sha2 менять мб затруднительно
     
     
  • 2.38, Аноним (11), 16:36, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +3 +/
    Проснитесь уже, для индентификации коммита используется 160 битный хэш, и количе... большой текст свёрнут, показать
     
     
  • 3.50, Аноним (-), 18:38, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > Проснитесь уже, для индентификации коммита используется 160 битный хэш,
    > и количество коллизий там минимальное,

    Для SHA-1 все же известны криптографические атаки. Конечно на слом 160 битов - да еще с теми constraints - ресурсов надо многократно больше. Но совсем не столько сколько ожидалось. А вот SHA256... там, видите ли, генерация "нужного" хеша основа майнинга. Если б кто-то сумел в предсказуемые хеши, уже миллиардером был бы. Потому что pow сводится к подгону SHA256 до нужного числа нолей в начале. Если удалось - ЗБС, вы намайнили блок, профит ваш! Правда, есть перестроить сложность если вы будете блоки слишком бытсро фигачить - но не сразу - и к тому же профит все же уйдет от остальных майнеров к более успешному шустряку.

     
  • 3.59, Аноним (59), 20:18, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    > можно скипнуть коммит, и сделать его снова

    Можно поподробнее? С точки зрения использования гита из командной строки это как будет выглядеть?

     
     
  • 4.65, Аноним (11), 23:50, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Не благодарите:
    git add blblba
    git commit -S
    -- ошибка при создании коммита
    git commit -S

    Хэш формируется командой git commit или git merge.

     
     
  • 5.73, Аноним (-), 09:21, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    Короткие идентификаторы используются для быстрого поиска, а не для коммитов. Попробуй потоньше.
     
     
  • 6.77, Аноним (59), 20:36, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    Ненене, мой вопрос к анониму выше касался именно (гипотетической) ситуации с полным идентификатором коммита. Спасибо ему за ответ.
     
  • 5.76, Аноним (59), 20:34, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    Всё же поблагодарю. Спасибо за информацию!

    Никогда с таким не сталкивался на практике (по понятным причинам), и было интересно, как с таким бороться в случае чего.

     

  • 1.34, bonifatium (?), 16:08, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +4 +/
    правда в том, что наглядность и удобность 12- и 16-ти символьных short hash'ей одинаковая. Они одинаково длинные для запоминания и необходимости копирования, а для билд/чек скриптов это все без разницы.
     
     
  • 2.79, Аноним (79), 07:38, 02/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    Во-во. Мы вот в нашей компании сыздавна использовали полные id коммитов где только можно (в почте, JIRA и тп). Какая разница что копировать по двойному клику-то?
     

  • 1.36, Аноним (36), 16:22, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Сокращение строковых значений и их последующее восстановление и сравнение - это глупость. Адреса криптокошельков, номера расчетных счетов - тоже строковые значения.
     
     
  • 2.39, Аноним (-), 16:37, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Коллизии настролько редки, что решили оставить всё как есть а не усложнять.
     

  • 1.37, Аноним (37), 16:32, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    т.е. они просто берут первые 12 символов от хеша?
    Гениально!
    "Оставайтесь, у нас. Будете гениальным механиком планеты!" (с)

     
     
  • 2.40, Аноним (-), 16:38, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    А что туту такого. На то и короткие.
     
  • 2.42, Аноним (11), 16:40, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Да, потому что это не реальная ссылка, а лишь удобный метод сокращения вывода на экране! Он даже не является реальной ссылкой на какой-то коммит, а лишь являет более удобной подстрокой, для текстового поиска, отсюда мы можем иметь сколько угодно много таких одинаковых подстрок.
     
     
  • 3.58, Аноним (37), 20:10, 31/12/2024 Скрыто ботом-модератором     [к модератору]
  • +/
     
  • 3.75, Rus_Trololo (ok), 12:20, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    >Возникновение коллизий, при которых несколько разных изменений оказываются связаны с одним сокращённым идентификатором, могут привести к нарушению работы инструментов для анализа и проверки изменений, учитывающих содержимое тегов "Fixes".
     
  • 2.68, Neon (??), 02:47, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    Да, талантливые ребята. Прямо как те, кто заложили  год кодировал двумя символами. Заранее заложенная мина замедленного действия.
     

  • 1.43, Чуть более чем полностью анонимный аноним (?), 17:26, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • –1 +/
    "640 КБ на самом деле хватит всем"
     
     
  • 2.61, Аноним (-), 22:10, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Эта та самая, знаменитая цитата Билла Гейтса?
     
  • 2.69, Neon (??), 02:48, 01/01/2025 [^] [^^] [^^^] [ответить]  
  • +/
    Два символа для хранения года в данных. Гениальная экономия))). Чтобы потом пострадать
     

  • 1.46, Аноним (-), 18:28, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    > Сокращённые идентификаторы коммитов формируются через оставление
    > первых 12 символов от хэша SHA-1 (48 бит из 160 бит)

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

     
     
  • 2.53, Аноним (53), 19:07, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Это хэш коммитов ЯДРА. Нафига ты коммитишь каждые 2 символа?
     
     
  • 3.63, Аноним (-), 23:48, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    > Это хэш коммитов ЯДРА. Нафига ты коммитишь каждые 2 символа?

    Вон там гражданин показал - что задавшись целью можно подогнать такой же "на вид" (сокрашенный хеш) комит - с другим содержимым. А вот это уже не айс. Ибо открывает почву для злоупотреблений. Конечно там еще пуллы по иерархии и все же это читают - но лучше пусть двуногие И машины обеспечивают 2 контура проверок, чем чисто на одних глазах выезжать.

     

  • 1.51, Аноним (52), 19:01, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Если бы Линус не разгонял этих горе новаторов не было бы сейчас никакого ядра. Сначала они пропихнут длинную коммитов, а потом зонд.
     
     
  • 2.54, Аноним (53), 19:13, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Самое странное, зачем делать уязвимости в ядре, когда полно приложух работающих с привилегиями ядра, и за которыми особо не смотрят. Наверняка специально отвлекают внимание на ядро, чтобы и дальше никто не смотрел.
     
     
  • 3.64, Аноним (-), 23:49, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    > Самое странное, зачем делать уязвимости в ядре, когда полно приложух работающих с
    > привилегиями ядра

    Это как? Мне уже интересно, право. Примеры такой приложухи? :)

     

  • 1.56, Аноним (56), 19:36, 31/12/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    git уже давно умеет не только sha1, а вообще давно нужно перейти на sha3-512
     
     
  • 2.60, Аноним (60), 20:46, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Он на GitHub слать не умеет так. Да и GitHub принимать не умеет так.
     
     
  • 3.66, Аноним (-), 23:50, 31/12/2024 [^] [^^] [^^^] [ответить]  
  • +/
    > Он на GitHub слать не умеет так. Да и GitHub принимать не умеет так.

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

     

     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Партнёры:
    PostgresPro
    Inferno Solutions
    Hosting by Hoster.ru
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2025 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру