Бабушка, смотри, я сделал двач! Войти !bnw Сегодня Клубы
огрёб хэш-коллизию
#VMBUDS / @hirthwork / 2531 день назад

Расскажи.
#VMBUDS/JSR / @komar / 2531 день назад
@komar Сервер А говорит: «Отправил на сервер Б такие-то данные для такого-то пользователя» Сервер Б говорит: «Принял данные для этого пользователя» Сервер Б говорит: «Записал данные для этого пользователя» Сервер А говорит: «Сходил на стораж и отправил ещё данных серверу Б для того же пользователя» Сервер Б говорит: «Принял данные для этого пользователя» Вот здесь бы серверу Б сказать, что он записал данные, но тут тишина, если по айдишнику пользователя грепать. На сервера идёт постоянная нихуёвая нагрузка. А оказалось, что на стораже случилась хэш-коллизия кэша и данные он достал относящиеся к другому пользователю совсем
#VMBUDS/UMO / @hirthwork --> #VMBUDS/JSR / 2531 день назад
@hirthwork Это не интересно. Как сама хеш-коллозия-то получилась? Что за данные брали и как хеш делали?
#VMBUDS/QXZ / @komar --> #VMBUDS/UMO / 2531 день назад
@komar Просто у меня до этого ситуация «хеши сошлись» была только в случае, когда гит путался, куда были пермещены какие одинаковые файлы. Довольно-таки пиздец, но ясно. А тут что?
#VMBUDS/17J / @komar --> #VMBUDS/QXZ / 2531 день назад
@komar несколько дней назад один из серверов пошёл на стораж и попросил данные. nginx посчитал 128битный хэш он запроса и тела POSTа, увидел, что в кэше ничего нет по этому хэшу, поэтому дёрнул медленный бэкэнд, чтобы он нагенерил данных, и схоронил их в кэш по данному хэшу. Вот теперь для совсем другого запроса, с другим URI и другим телом хэш от запроса совпал с тем что лежал там до этого, поэтому nginx решил что это правильные данные и отдал их
#VMBUDS/8E2 / @hirthwork --> #VMBUDS/QXZ / 2531 день назад
@hirthwork и такие коллизии на тысяче серверов у нас происходят каждый день
#VMBUDS/ZYK / @hirthwork --> #VMBUDS/8E2 / 2531 день назад
@hirthwork хуёво, чо, чини
#VMBUDS/0EK / @mugiseyebrows --> #VMBUDS/ZYK / 2531 день назад
@mugiseyebrows да вот уже скурил всю страницу документации
#VMBUDS/7GY / @hirthwork --> #VMBUDS/0EK / 2531 день назад
@hirthwork > 128 бит (340282366920938463463374607431768211456 вариантов) > совершенно разные корректные данные (не из шума) > каждый день Хули ты мне пиздишь? Чини свое говно.
#VMBUDS/E9N / @komar --> #VMBUDS/8E2 / 2531 день назад
@komar у нас реально большой rps
#VMBUDS/1JW / @hirthwork --> #VMBUDS/E9N / 2531 день назад
@hirthwork Не пизди.
#VMBUDS/6YV / @komar --> #VMBUDS/1JW / 2531 день назад
@hirthwork Покажи мне URI и тело, по которому брался хеш, и хеш-функцию тоже. Я бы на твоем месте не стал бы верить в то, что звезды на небе сошлись, а проверил бы, что из вашего говна написано через жопу.
#VMBUDS/NPK / @komar --> #VMBUDS/7GY / 2531 день назад
@komar не покажу. потому что тело POSTа я сам не смогу достать (а то бы не ебался целый вечер). А URI там реально разный. В файле кэша KEY лежит c URI
#VMBUDS/L97 / @hirthwork --> #VMBUDS/NPK / 2531 день назад
@hirthwork KEY — это хеш? Ну охуеть. Тогда давай сделаем вот что. Поднимаем аналогичную конфигурацию. Ебем ее рандомным говном. Получаем коллозию. Схороняем ее. Отправляем багрепорт с просьбой заменить эту хуевую хеш-функцию.
#VMBUDS/AM5 / @komar --> #VMBUDS/L97 / 2531 день назад
@komar двачую тута либо веришь в бога, либо в математику (теорию вероятности)
#VMBUDS/PIY / @mugiseyebrows --> #VMBUDS/NPK / 2531 день назад
@komar вначале файла лежит `static u_char ngx_http_file_cache_key[] = { LF, 'K', 'E', 'Y', ':', ' ' };` — далее идёт URI запроса. а судя по коду «хуёвая хэш-функция» — это md5
#VMBUDS/7EA / @hirthwork --> #VMBUDS/NPK / 2531 день назад
@mugiseyebrows ну давай, заебень мне при помощи формулы Стирлинга вероятность того из трёх миллиардов вычислений md5 ни разу не случится коллизия
#VMBUDS/QX6 / @hirthwork --> #VMBUDS/PIY / 2531 день назад
Желание загадал?
#VMBUDS/3SS / @je / 2531 день назад
@komar This.
#VMBUDS/QV7 / @je --> #VMBUDS/E9N / 2531 день назад
@hirthwork >2017 >md5
#VMBUDS/R3R / @anonymous --> #VMBUDS/QX6 / 2531 день назад
@mugiseyebrows Бля, а вот тут-то я, возможно, (тоже) долбоеб. http://ru.wikipedia.org/wiki/Атака_«дней_рождения» Надо посчитать получше.
#VMBUDS/P9U / @komar --> #VMBUDS/PIY / 2531 день назад
@komar я тоже прочитал про эт хуйню когда коллизию отгрёб
#VMBUDS/FV1 / @hirthwork --> #VMBUDS/P9U / 2531 день назад
@je это оно и было — увидеть хэш-коллизию md5. эт куда прикольнее чем на сиськи пялиться
#VMBUDS/XR5 / @hirthwork --> #VMBUDS/3SS / 2531 день назад

@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.

#VMBUDS/KMD / @fix --> #VMBUDS/QX6 / 2531 день назад
ОП, внеси в студию размер кеша в элементах. Или хотя бы прикинь примерно.
#VMBUDS/2Z3 / @komar / 2531 день назад

@komar > в среднем после перебора 1{,}25 \cdot \sqrt{N} различных входных значений будет найдена искомая коллизия.
Если N=2^128, то это будет 2.305843009213694e19

#VMBUDS/U0T / @fix --> #VMBUDS/P9U / 2531 день назад
Короч, по платону раскидаю. Хеш функции придумывают учёные математики решая две проблемы: 1 необратимость, 2 без коллизий. Функция не удовлетворяющая этим условиям не попадёт в "продакшн". Количество вариантов результатов хеширования примерно (на порядок-два-три-пять) равно длинне хеша, иначе можно было было бы в конце хеширования его сократить каким-нибудь побитовым сложением двух половинок хеша без потери информации. Даже если хакиры-математики находят коллизии, они скорее всего связаны с определенным набором данных, который интуичится из алгоритма хеш функции и случайно его невероятно получить. Сто пудов в реализации хеш функции ошибка.
#VMBUDS/IYW / @mugiseyebrows / 2531 день назад
@komar шесть гигов при среднем размере в 5-10 кб. и так на тысяче серверов
#VMBUDS/NQ2 / @hirthwork --> #VMBUDS/2Z3 / 2531 день назад
@hirthwork Что «на тысяче серверов»? Поиск идет по тысяче серверов одновременно, или по одному? Или коллозии ловятся каждый день, но только на одном из тысячи серверов?
#VMBUDS/TWQ / @komar --> #VMBUDS/NQ2 / 2531 день назад
@komar сервер куда идти определяется по айдишнику документа. вчера было коллизия на одном сервере. в субботу — на двух других
#VMBUDS/7Z2 / @hirthwork --> #VMBUDS/TWQ / 2531 день назад
а ведь мне эти же охуительные истории завтра админам стораджа рассказывать
#VMBUDS/RBV / @hirthwork / 2531 день назад
@hirthwork кинь ссылку на бнвач, чтобы не пересказывать
#VMBUDS/7WV / @anonymous --> #VMBUDS/RBV / 2531 день назад
@anonymous удобно
#VMBUDS/9BT / @komar --> #VMBUDS/7WV / 2531 день назад
@komar Че-то я посчитал и вероятность КРАЙНЕ МАЛА. Скорее всего хуевый с меня математик просто. Заодно поебался в хаскельные тайпклассы, больше не хочу.
#VMBUDS/EQP / @komar --> #VMBUDS/P9U / 2531 день назад
@anonymous «Хуевость» md5 в этом случае не играет роли. То, что нашли способы быстро (без перебора) искать коллизии, никак не поможет случайно возникающим коллизиям здесь. Разве что по другую сторону сидит злой сотруднек яндыха, который в курсе, как расчитывается хеш, подбирает типа «безобидные» данные и кормит ими вебсервер.
#VMBUDS/1IB / @komar --> #VMBUDS/R3R / 2531 день назад
@komar палю: больше битность -- меньше коллизий
#VMBUDS/3D5 / @anonymous --> #VMBUDS/1IB / 2531 день назад
@anonymous Это да.
#VMBUDS/A6Y / @komar --> #VMBUDS/3D5 / 2531 день назад
ipv6 ready BnW для ведрофона BnW на Реформале Викивач Котятки

Цоперайт © 2010-2016 @stiletto.