The OpenNET Project / Index page

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

DoS атака против файловой системы Btrfs

13.12.2012 20:25

Опубликована техника DoS-атаки на файловую систему Btrfs, манипулирующая коллизиями хэшей имён файлов. При создании примерно 500 файлов со случайными именами, их удаление происходит почти мгновенно. Но если выбрать имена файлов, вызывающих коллизии при их хэшировании, при удалении система начинает тратить чрезмерные ресурсы. Например, создав 500 файлов с именами, которые сводятся к 55 хэш-значениям crc32c (метод хэширования элементов в индексе содержимого директории Btrfs), их удаление заняло настолько много времени, что в ходе эксперимента пришлось принудительно завершить процесс после того как его выполнение заняло 220 минут.

При попытке создать файлы, имена которых соответствуют одному хэшу, таких файлов удалось создать не более 61, после чего процесс c ошибкой завершал своё выполнение. Подобную особенность злоумышленник может использовать для блокирования создания определённых имён файлов в общедоступных директориях. Патч с устранением указанных проблем планируется добавить в состав ядра Linux 3.8.

 
  1. Главная ссылка к новости (http://crypto.junod.info/2012/...)
  2. OpenNews: Автор md5crypt подчеркнул небезопасность данного алгоритма и призвал перейти на более стойкие методы хэширования паролей
  3. OpenNews: Универсальный способ DoS-атаки, затрагивающий PHP, Java, Ruby, Python и различные web-платформы
Лицензия: CC BY 3.0
Короткая ссылка: https://opennet.ru/35593-dos
Ключевые слова: dos, security, btrfs
При перепечатке указание ссылки на opennet.ru обязательно


Обсуждение (150) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.2, ryoken (?), 20:29, 13/12/2012 [ответить] [﹢﹢﹢] [ · · · ]  []     [к модератору]
  • +54 +/
    Готова к продакшену, да? Поздравлямс сусю.
     

     ....большая нить свёрнута, показать (54)

  • 1.3, linux must _RIP_ (?), 20:38, 13/12/2012 [ответить] [﹢﹢﹢] [ · · · ]  [] []     [к модератору]
  • +1 +/
    ОО.. и где местные аналитики которые кричали все хорошо?
     
     
  • 2.10, Аноним (-), 21:01, 13/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • +5 +/
    Ооо, btrfs-у выпала честь от более-менее оригинально мыслящего перца потыкать в него палочкой и обнаружить неординарные возможности.

    Заметьте, все остальные просто не попали под его внимание. Это не значит что там всенепременно нет проблем. Это значит что их пока никто палочкой не тыкал.

     
     
  • 3.37, all_glory_to_the_hypnotoad (ok), 22:03, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +3 +/
    атаки на хэши давно известны, их часто используют (вспоминаем, например, недавние атаки на питоны и некоторые веб сервера). Так что сам факт хэширования по crc32 кричит всякой школоте и просто скучающим людям - поимей меня!

    > Заметьте, все остальные просто не попали под его внимание. Это не значит что там всенепременно нет проблем.

    в остальных фс обычно используют менее тривиальное хэширование и деревья, саксес подобного DoSа будет ниже или  вообще невозможен.

     
     
  • 4.58, Аноним (-), 23:26, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • –1 +/
    Взаимоисключающие параграфы детектед Он, конечно, кричит, но в хеш-табли... большой текст свёрнут, показать
     
     
  • 5.104, linux must _RIP_ (?), 16:24, 14/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • –1 +/

    > Радуют меня такие индивиды - мешают в кучу все подряд. Указанное поведение
    > - проблема именно хэш-таблиц. При чем тут деревья вообще? Это иные
    > структуры с иными свойствами. Потенциально деревья кстати не лучше хэш-таблиц. Для
    > дерева O(log(N)) а для таблиц O(1). Вот только как оказалось, можно
    > спровоцировать ситуацию когда O(1) скорее станет похоже на O(N) :)

    для хэш таблиц никогда не бывает O(1), именно из-за колизий. Не позорьтесь.
    И вопрос был не о O(N), там явно что-то другое сыграло :-)

     
     
  • 6.117, Аноним (-), 17:59, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > для хэш таблиц никогда не бывает O(1), именно из-за колизий. Не позорьтесь.

    Вообще-то нормальным сценарием эксплуатации хэш-таблицы является случай когда коллизий нет или мало. Поэтому при нормальном юзеже получается именно O(1), за что их и любят, собственно. Если коллизий слишком много, значит дуболом который юзал хэш-таблицу выбрал слишком которкий хэш для используемого размера таблицы. Какгбэ это в общем случае считается FAIL-ом в использовании данной технологии :)

    > И вопрос был не о O(N), там явно что-то другое сыграло :-)

    В конкретно этом случае возмжно алгоритм вообще локапнулся где-то. Ибо 220 минут - как-то шибко уж дофига.

     
  • 5.134, nuclight (??), 19:49, 14/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • –2 +/
    Эксперт 294 уровня как всегда газифицировал лужу, побыв для части сведений кэпом, а в остальной облажавшись. Эти вещи на втором курсе дают, есличо. И распределение (равномерность) значений хэш-функции учат смотреть, так что "похожесть на O(N)" для не забивавших не "как оказалось", а давно известное понятие. И что такое контрольные суммы, и что CRC предназначена для поиска и исправления ошибок в канале связи (а не для хеширования), тоже учат.

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

     
     
  • 6.144, Аноним (-), 00:30, 16/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    Много апломба и мало по делу На втором курсе обычно учат тому что нужна какая-... большой текст свёрнут, показать
     
     
  • 7.160, arisu (ok), 21:59, 20/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > Ориентируясь на скорость в среднем, а не worst case (о чем
    > обычно честно предупреждают). CRC32, очевидно, является хэш-функцией, сжимая все множество
    > входных значений до 32 битов (или сколько там у кого).

    ага, а костыли — это такие ноги, только альтернативные и экономичные. но марафоны на костылях почему-то не бегают.

    вообще-то в *нормальном* учебном заведении когда говорят про хэш-таблицы, рассказывают и про uniform distribution, и про avalanche, и — в том числе — почему люди, использующие crc32 в качестве хэш-функции для хэш-таблиц — форменные идиоты.

    > Ниоткуда не следует что ее нельзя юзать как функцию хэш-таблицы.

    следует, причём напрямую: из изучения её свойств.

    не надо больше про хэши в этом контексте, ок? а то позоришься не хуже изи.

     
  • 2.11, SubGun (ok), 21:03, 13/12/2012 [^] [^^] [^^^] [ответить]  [] []     [к модератору]
  • +/
    Никто не говорил, что все идеально. Уверен, подобную "фишку" можно было бы со всеми существующими ФС сотворить, и не одна не была бы идеальной.
     
     
  • 3.15, Аноним (-), 21:06, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > со всеми существующими ФС сотворить,

    Насчет всех - это смотреть надо. Зависит от юзаемых алгоритмов.

    Потенциально же такая проблема с теми или иными последствиями может быть вообще везде где есть хэш-таблицы. Где-то это не проблема. А где-то может позволить кому-то что-то основателььно тормознуть.

     
  • 3.151, Аноним (-), 18:49, 16/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > со всеми существующими ФС сотворить,

    Для OpenBSD что-то похожее нашли. Там же в бложике в коментах немало интересного встречается.

     
  • 2.18, Аноним (-), 21:12, 13/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • +/
    > ОО.. и где местные аналитики которые кричали все хорошо?

    Это вы еще просто не видели перцев с IXBT которые совершенно случайно нашли видеофайл который можно нарезать на CD, но потом тотально не получается его оттуда прочитать. Хотя носитель при этом абсолютно исправен.

    Оказывается, после трансформации алгоритмами коррекции ошибок данные файла превратились в нечто, совпадающее с служебной сущностью (IIRC, синхрометкой). Ну а приводы налетев на такое западло совершенно не понимали как это читать дальше и отдавали ошибку чтения :)

     
     
  • 3.26, Аноним (-), 21:31, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    >> ОО.. и где местные аналитики которые кричали все хорошо?
    > Это вы еще просто не видели перцев с IXBT которые совершенно случайно
    > нашли видеофайл который можно нарезать на CD, но потом тотально не
    > получается его оттуда прочитать. Хотя носитель при этом абсолютно исправен.
    > Оказывается, после трансформации алгоритмами коррекции ошибок данные файла превратились
    > в нечто, совпадающее с служебной сущностью (IIRC, синхрометкой). Ну а приводы
    > налетев на такое западло совершенно не понимали как это читать дальше
    > и отдавали ошибку чтения :)

    а ссыли нет? интересно было бы самому нарезать...

     
     
  • 4.33, Аноним (-), 21:41, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +3 +/
    > а ссыли нет? интересно было бы самому нарезать...

    Вот ссыль на описалово. Вместе с объяснением феномена - http://www.ixbt.com/optical/magia-chisel.shtml

     

  • 1.5, Аноним (-), 20:44, 13/12/2012 [ответить] [﹢﹢﹢] [ · · · ]  []     [к модератору]
  • +2 +/
    местные аналитики забывают что подобная атака была и на питон и на пхп и на много еще чего находящегося в продакшене.
     
  • 1.8, Аноним (-), 20:54, 13/12/2012 [ответить] [﹢﹢﹢] [ · · · ]  []     [к модератору]
  • +/
    Это можно сделать не только на Btrfs, в том плане что поедание ресурсов возможно не только в данной ФС и не только в ФС
     
     
  • 2.14, Аноним (-), 21:04, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > Это можно сделать не только на Btrfs, в том плане что поедание
    > ресурсов возможно не только в данной ФС и не только в ФС

    Это можно сделать много где и это не самый ожидаемый вектор атаки для программистов.

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

     
  • 2.16, svn (??), 21:07, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +1 +/
    На качественных файловых системах, xfs(btree вместо hash), reiserfs(на этапе проектировки предусмотрена устойчивость к коллизиям) такого сделать не получится.
     
     
  • 3.20, Аноним (-), 21:14, 13/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • +1 +/
    > предусмотрена устойчивость к коллизиям)

    А нельзя ли пруф на то что они специально дизайнились с учетом этого фактора? А то проблема просто есть у целого класса алгоритмов - хэш функций. И задумались о аккуратном подгоне входных данных для их торможения относительно недавно. Явно позже чем указанные ФС проектировались. Что вызывает некие нехорошие подозрения на ваш счет.

     
     
  • 4.23, linux must _RIP_ (?), 21:23, 13/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • –1 +/
    какая-то у вас каша в голове.. скорость вычисления хэша - вещь константная. И то что колизии бывают - нормальный разработчик как бы в курсе.. (достаточно подумать 255 байт ужимают до 32 - тут уж не бывает без вариантов). Другой вопрос что при реализации кто-то заложился что таких колизий не много - но это уже проблемы реализации :-) Которую тут хвалили..
     
     
  • 5.28, Аноним (-), 21:31, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • –1 +/
    Просто намеренный гасеж коллизиями вообще-то не является штатным видом эксплуата... большой текст свёрнут, показать
     
     
  • 6.105, linux must _RIP_ (?), 16:33, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • –1 +/
    crc32 не является криптохэшем - видимо что бы это узнать нужны дикие познания ... большой текст свёрнут, показать
     
     
  • 7.119, Аноним (-), 18:24, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    Внезапно, хэш-таблицы сами по себе вообще не требуют в общем случае использовани... большой текст свёрнут, показать
     
  • 4.24, svn (??), 21:25, 13/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • +/
    reiserfs использует хеш функцию r5, для которой не известен алгоритм создания коллизий.
    И уж точно (даже если коллизия возникнет) это ограничится проблемой производительности, а не будет отказ в создании файла.
     
     
  • 5.34, Аноним (-), 21:43, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > И уж точно (даже если коллизия возникнет)

    В общем то коллизии находят даже для криптостойких функций иногда, а для хэш-таблиц нет требования криптостойкости в общем случае. Хотя как оказалось, такая поблажка может икаться совершенно неожиданным образом.

    > а не будет отказ в создании файла.

    Так в btrfs нет отказов при создания файла. Правда есть какое-то непотребное время удаления.

     
     
  • 6.41, svn (??), 22:23, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • –1 +/
    >Так в btrfs нет отказов при создания файла.

    По ссылке не ходил статью не читал? brtfs выдал ошибку на шестьдесят втором файле с коллизией.

     
     
  • 7.61, Аноним (-), 23:46, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    Не только читал, но и в курсе как хэш таблицы делают Понимаете ли, для хэш-табл... большой текст свёрнут, показать
     
     
  • 8.84, svn (??), 07:35, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • –1 +/
    Почитай ещё раз То что ты знаешь, не значит что авторы btrfs знают По факту, в... текст свёрнут, показать
     
  • 8.106, linux must _RIP_ (?), 16:37, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • –1 +/
    остальной бред скипнут В случае применения в FS - там все немного не так как вы... большой текст свёрнут, показать
     
     
  • 9.122, Аноним (-), 18:32, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    Во первых, простите, а что есть дописать в середину файла Технически я понима... большой текст свёрнут, показать
     
     
  • 10.137, linux must _RIP_ (?), 00:10, 15/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • –1 +/
    Мисье - вы уверены что к директориям примимо слово posix Если уверены - то мне ... текст свёрнут, показать
     
     
  • 11.145, Аноним (-), 00:36, 16/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    Пардон, вы сами про ФАЙЛЫ завели речь На самом деле я просто не понял ваш манев... текст свёрнут, показать
     
  • 3.22, linux must _RIP_ (?), 21:20, 13/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • +/
    у ext4 тоже специально предусмотрена обработка колизий в dx tree..
     
     
  • 4.29, Аноним (-), 21:34, 13/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • –1 +/
    > у ext4 тоже специально предусмотрена обработка колизий в dx tree..

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

     
     
  • 5.107, linux must _RIP_ (?), 16:38, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • –1 +/
    >> у ext4 тоже специально предусмотрена обработка колизий в dx tree..
    > Проблема не в том что обработки нет. А в том что если
    > коллизий будет много, алгоритм очень существенно провалится по скорости относительно "среднего
    > по больнице" поведения.

    see up. все не так просто.

     
     
  • 6.150, Аноним (-), 01:04, 16/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > see up. все не так просто.

    Да, оказывается не все так просто. В коментах к бложику продолжается изучение где еще можно так поприкалываться. Под внимание попала дефолтная ФС OpenBSD, которую как я понял успешно заDOSили :)

     

  • 1.30, Buy (ok), 21:35, 13/12/2012 [ответить] [﹢﹢﹢] [ · · · ]  [] []     [к модератору]
  • –1 +/
    Не понятно чего так носятся с этой btrfs, преимуществ никаких, сколько тестов уже было опубликовано, сколько раз сам ставил на корень и убеждался. В ЧЕМ, ПРИ КАКИХ УСЛОВИЯХ проявляется ее мифическая производительность???
     

     ....большая нить свёрнута, показать (46)

  • 1.72, Аноним (-), 00:41, 14/12/2012 [ответить] [﹢﹢﹢] [ · · · ]  [] []     [к модератору]
  • +/
    У бтрфс есть еще одно узкое место помимо производительности - пожирание места на диске за счет метаданных. на 10 гб данных требуется 1 гб метаданных, если правильно помню - 10% места коту под хвост в самом лучшем случае ;)
     
     
  • 2.73, filosofem (ok), 00:49, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > У бтрфс есть еще одно узкое место помимо производительности - пожирание места
    > на диске за счет метаданных. на 10 гб данных требуется 1
    > гб метаданных, если правильно помню - 10% места коту под хвост
    > в самом лучшем случае ;)

    Слегка ошибся. На 5ТБ данных 10ГБ метаданных. А вообще это зависит.

     
  • 2.128, Аноним (-), 18:53, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > на диске за счет метаданных. на 10 гб данных требуется 1 гб метаданных,

    Хотите прикол? Создавайте директории и в них файлы 0-го размера до упора. Однажды вы обнаружите что хотя на диске всего 0 байтов (т.к. все файлы нулевого размера), место тем не менее почему-то кончилось. Да-да, на 0 байтов полезных данных можно спровоцировать 100500Гб метаданных, сожравших вообще все место. Кстати, от типа файловой системы это вообще не зависит особо :)

     
  • 2.141, Аноним (-), 23:30, 15/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > У бтрфс есть еще одно узкое место помимо производительности - пожирание места
    > на диске за счет метаданных. на 10 гб данных требуется 1
    > гб метаданных, если правильно помню - 10% места коту под хвост
    > в самом лучшем случае ;)

    Внезапно, эта величина сильно зависит от среднего размера файлов. Потому что информация о том, что файл есть, и как он называется - это и есть метаданные.

     

  • 1.90, slowpoke (?), 09:14, 14/12/2012 [ответить] [﹢﹢﹢] [ · · · ]  [] []     [к модератору]
  • +1 +/
    crc32? ну они дали(((
     
     
  • 2.129, Аноним (-), 18:55, 14/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > crc32? ну они дали(((

    Для hash table это в принципе вполне себе функция. Просто оказалось что в конкретно этом случае можно хитро изогнуться. Но этот изгибон требует хакерского мышления а не програмерского. Так умеют не все.

     
     
  • 3.135, nuclight (??), 20:01, 14/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • –3 +/
    >> crc32? ну они дали(((
    > Для hash table это в принципе вполне себе функция. Просто оказалось что
    > в конкретно этом случае можно хитро изогнуться. Но этот изгибон требует
    > хакерского мышления а не програмерского. Так умеют не все.

    Покажи-ка еще хотя бы парочку известных применений, где CRC32 использовался бы именно в качестве _хэша_ для таблиц. То, что формально математически его можно отнести к хэшам, не означает, что таким идиотизмом надо заниматься на практике.

     
     
  • 4.148, Аноним (-), 00:48, 16/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +/
    > Покажи-ка еще хотя бы парочку известных применений, где CRC32 использовался бы именно
    > в качестве _хэша_ для таблиц.

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

     
  • 3.159, arisu (ok), 21:08, 20/12/2012 [^] [^^] [^^^] [ответить]  []     [к модератору]
  • +/
    > Для hash table это в принципе вполне себе функция.

    вот такие кулхацкеры и суют её в хэши, ага. сейчас я тебе скажу два словосочетания: «avalanche test» и «uniform distribution test». да, это надо вбивать в гугель вместе с буквами «crc32».

    я надеюсь, ты не пишешь ничего сложнее приветмиров. или хотя бы не показываешь публике. потому что с таким уровнем компетенции… в других областях она у тебя не лучше, инфа 146%

     

  • 1.158, arisu (ok), 21:04, 20/12/2012 [ответить] [﹢﹢﹢] [ · · · ]  []     [к модератору]
  • –1 +/
    хэш. crc32. на всякий случай отложил идею пощупать btrfs на 50 лет.
     
     
  • 2.162, Аноним (-), 01:58, 21/12/2012 [^] [^^] [^^^] [ответить]      [к модератору]
  • +2 +/
    > хэш. crc32. на всякий случай отложил идею пощупать btrfs на 50 лет.

    Лучше на 100. А то вдруг каким-то чудом доживешь еще? Как же тогда твой статус некрофила?

     

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



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

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