@komar Сервер А говорит: «Отправил на сервер Б такие-то данные для такого-то пользователя»
Сервер Б говорит: «Принял данные для этого пользователя»
Сервер Б говорит: «Записал данные для этого пользователя»
Сервер А говорит: «Сходил на стораж и отправил ещё данных серверу Б для того же пользователя»
Сервер Б говорит: «Принял данные для этого пользователя»
Вот здесь бы серверу Б сказать, что он записал данные, но тут тишина, если по айдишнику пользователя грепать. На сервера идёт постоянная нихуёвая нагрузка.
А оказалось, что на стораже случилась хэш-коллизия кэша и данные он достал относящиеся к другому пользователю совсем
@komar Просто у меня до этого ситуация «хеши сошлись» была только в случае, когда гит путался, куда были пермещены какие одинаковые файлы. Довольно-таки пиздец, но ясно. А тут что?
@komar несколько дней назад один из серверов пошёл на стораж и попросил данные. nginx посчитал 128битный хэш он запроса и тела POSTа, увидел, что в кэше ничего нет по этому хэшу, поэтому дёрнул медленный бэкэнд, чтобы он нагенерил данных, и схоронил их в кэш по данному хэшу. Вот теперь для совсем другого запроса, с другим URI и другим телом хэш от запроса совпал с тем что лежал там до этого, поэтому nginx решил что это правильные данные и отдал их
@hirthwork > 128 бит (340282366920938463463374607431768211456 вариантов)
> совершенно разные корректные данные (не из шума)
> каждый день
Хули ты мне пиздишь? Чини свое говно.
@hirthwork Покажи мне URI и тело, по которому брался хеш, и хеш-функцию тоже. Я бы на твоем месте не стал бы верить в то, что звезды на небе сошлись, а проверил бы, что из вашего говна написано через жопу.
@hirthwork KEY — это хеш? Ну охуеть.
Тогда давай сделаем вот что. Поднимаем аналогичную конфигурацию. Ебем ее рандомным говном. Получаем коллозию. Схороняем ее. Отправляем багрепорт с просьбой заменить эту хуевую хеш-функцию.
@komar вначале файла лежит `static u_char ngx_http_file_cache_key[] = { LF, 'K', 'E', 'Y', ':', ' ' };` — далее идёт URI запроса. а судя по коду «хуёвая хэш-функция» — это md5
@komar > в среднем после перебора 1{,}25 \cdot \sqrt{N} различных входных значений будет найдена искомая коллизия. Если N=2^128, то это будет 2.305843009213694e19
Короч, по платону раскидаю. Хеш функции придумывают учёные математики решая две проблемы: 1 необратимость, 2 без коллизий. Функция не удовлетворяющая этим условиям не попадёт в "продакшн". Количество вариантов результатов хеширования примерно (на порядок-два-три-пять) равно длинне хеша, иначе можно было было бы в конце хеширования его сократить каким-нибудь побитовым сложением двух половинок хеша без потери информации. Даже если хакиры-математики находят коллизии, они скорее всего связаны с определенным набором данных, который интуичится из алгоритма хеш функции и случайно его невероятно получить. Сто пудов в реализации хеш функции ошибка.
@hirthwork Что «на тысяче серверов»? Поиск идет по тысяче серверов одновременно, или по одному? Или коллозии ловятся каждый день, но только на одном из тысячи серверов?
@komar Че-то я посчитал и вероятность КРАЙНЕ МАЛА.
Скорее всего хуевый с меня математик просто.
Заодно поебался в хаскельные тайпклассы, больше не хочу.
@anonymous «Хуевость» md5 в этом случае не играет роли. То, что нашли способы быстро (без перебора) искать коллизии, никак не поможет случайно возникающим коллизиям здесь. Разве что по другую сторону сидит злой сотруднек яндыха, который в курсе, как расчитывается хеш, подбирает типа «безобидные» данные и кормит ими вебсервер.
@hirthwork Вероятность —
1 - \prod_{i = m-n+1}^{m} \frac{i}{m}, где m=2^128, n=3000000000. Я не знаю, как такое считать, поэтому посчитаю оценку сверху.1 - \prod_{i = m-n+1}^{m} \frac{m-n+1}{m} = 1 - (\frac{m-n+1}{m})^n \approx 2.644 \cdot 10^{-20}.Иными словами, не больше, чем 0.00000000000000000002644862288468526129777965095160344354079281.
@komar > в среднем после перебора
1{,}25 \cdot \sqrt{N}различных входных значений будет найдена искомая коллизия.Если N=2^128, то это будет 2.305843009213694e19