Сегодня я наткнулся на интересную и забавную историю. Скорее всего это давний баг в Linux, который пророс в очень многие места. Вы скорее всего слышали о CRC-32 алгоритме, ну а если нет, то это такой алгоритм чексумм, достаточно распространенный и много где используется, в том же втором уровне сетевого стека для коррекции бит.
В процессорах x86-64, есть набор инструкций pclmulqdq, которые считают умножения в полях Галуа и так как CRC-32 много использует примерно таких операций, векторизованная версия много где использует такие инструкции. У Intel есть даже целый гайд как вычислять CRC-32 с помощью SIMD и получать небывалые скорости вычисления хэша.
И в одной из математических констант в этом гайде, а именно k6' написана такая формула
На маленьких инпутах это никак не воспроизводилось, но этот баг проник в приличное количество мест, например, в Chromium и стандартную библиотеку Golang.
Можно ли это эксплуатировать как инцидент безопасности, пока математически непонятно, но факт однозначно забавный. А если и можно, нас ждут увлекательные времена 🙂. Узнал я это из библиотеки wuffs (Wrangling Untrusted File Formats Safely).
В процессорах x86-64, есть набор инструкций pclmulqdq, которые считают умножения в полях Галуа и так как CRC-32 много использует примерно таких операций, векторизованная версия много где использует такие инструкции. У Intel есть даже целый гайд как вычислять CRC-32 с помощью SIMD и получать небывалые скорости вычисления хэша.
И в одной из математических констант в этом гайде, а именно k6' написана такая формула
k6’ = (x^32 mod P(x) << 32)’ << 1 = 0x1db710640В целом не надо задумываться о том, что она делает, это просто вспомагательная история. Из забавного, что на следующей строке
(⌊x^64/P(x)⌋)’ = 0x1F7011641Что заканчивается на 641. Когда как предыдущая строка заканчивается на 640. И так, видимо, получилось, что автор, который вносил этот алгоритм в ядро, перепутал случайно и написал k6' равной 0x1DB710641 (отличается на 1 от k6' из гайда Intel). В целом это было с самого первого коммита этого алгоритма.
На маленьких инпутах это никак не воспроизводилось, но этот баг проник в приличное количество мест, например, в Chromium и стандартную библиотеку Golang.
Можно ли это эксплуатировать как инцидент безопасности, пока математически непонятно, но факт однозначно забавный. А если и можно, нас ждут увлекательные времена 🙂. Узнал я это из библиотеки wuffs (Wrangling Untrusted File Formats Safely).