татко Крокодил

Малко за гледаните лекции от 28c3 – ще бъдат в няколко post-а по ред причини.

Ще започна с една лекция, която описа в общи линии нов проблем в повечето web-facing езици/framework-ове в хеш реализациите, за който даже написах малко код.

Къде е проблемът – повечето такива езици (в случая – perl, php, python, java, ruby, asp.net) използват hash-ове (познати още като асоциативни масиви), за да подадат към програмиста параметрите, които са дошли от HTTP request-а (най-вече от POST-а). Почти всички го реализират, използвайки стандартни hash таблици с 32 или 64битов hash (не-криптографски, т.е. даже и CRC32 би свършил работа, повечето ползват нещо, писано от DJB, например DJBX33A).
По принцип insert-а на нов елемент в такава таблица е с ниска/константна сложност, но ако вмъкваме само елементи, които дават същия hash, сложността става максималната възможна, т.е. O(n) и съответно вмъкването на n елемента ще е от порядъка на O(n^2).
Накратко, ако подадем (например) през POST параметри, които се хешират към същата стойност, времето, което ще отнеме на езика/framwork-а да обработи заявката (преди да стигне до вашето приложение) ще е бая, като тестовете при мен показаха нещо от порядъка на 1 минута за заявка с 62000 параметъра и голяма около 400kb. В лекцията (има и запис, mirror-нат при мен) има повече подробности и тестове.

Реших да видя доколко мен ме лови тоя проблем. Като за начало трябваше да си напиша генератор на тия стрингове (ВНИМАНИЕ: грозен гаден код на C), което се оказа сравнително лесно – измъкнах от source на php от Zend/zend_hash.h тяхната функция, поразгледах кода и се оказа, че от hash функцията се взимат първите X бита, като X е в общи линии log2(N) (където N е броя елементи в стуктурата). Съответно ако ми трябват по-малко от 65536 collide-ващи стринга ми е достатъчно да търся колизии само в първите 16 бита. Моята некадърна програмка на машина със 192GB памет (трябваха и около 120GB) се справи за около 5 минути.
(пускам кода като пример, който може да го разбере би могъл да си го напише и сам сравнително лесно).

Имам да се поровя още малко, но в някои случаи debian-ската default-на конфигурация реже тия атаки (понеже не позволява повече от 1000 променливи в какъвто и да е request, което па от своя страна чупи малко (малоумен) софтуер), в някои не и повечето php-та, които човек може да намери по net-а ги лови тоя проблем. Реализирането на DoS-а за да направи реален проблем изисква прилично количество паралелни връзки и определено не е толкова опасно, колкото беше проблемът с Range request-ите от август, но пак не е приятно. Също така може да се атакува и през други места, например ако трябва да се сглоби json request или какъвто и да е hash, чиито ключове зависят от данни, подадени от потребителя.

Решението е да се random-изира hash-а на всяка заявка, за което си написах една тестова програмка, която да пробва в/у такива подбрани string-ове hash, който освен всичко XOR-ва всеки 8-байтов блок от входа с един random seed. Мисля ако скоро не изкарат някакво хубаво решение да си patch-на директно php-то, но още не съм имал време да намеря подходящия entry point, в който да вкарам инициализацията на seed-а, така че хем да е различен за всеки request, хем да не счупи нещо по много лош начин (ако някой е бърникал по кода на php и знае къде, много моля да пише).

Та, добри хора, прочетете оригиналното advisory и се patch-вайте, ако правите нещо свързано с web най-вероятно проблемът ви засяга.

Tags: 28c3, работа

This entry was posted on Thursday, December 29th, 2011 at 22:12 and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.