Секурное программирование

Вопрос понятен. Но ты не мог бы рассказать, при чем тут криптохеши? Как они спасут от наршителя, который подкладывает плохие данные?

Криптохэши -- это первое что в голову пришло.

Я почему задумался -- меня младший брат спросил как хэш-таблицу делать:)

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

Но таким образом мы сразу теряем скорость и можем стать неконкурентными по сравнению с алгоритмами by-design дающими гарантированную сложность.

То есть мы приходим к выводу что в надежной ОС, надежных сервисах не место хэш-таблицам и прочим алгоритмам хорошим "в среднем". Ну, может и место но в каких-то очень продуманных местах. Это перекликается и с тем что им также не место в рил-тайм ОС. Может кому-то это всегда было очевидно, до меня только сейчас дошло..

> Либо сразу использовать криптохэш как часть вычисления хэш-функции.

то есть злоумышленник встает перед проблемой поиска коллизий в криптохэше, мы его озадачили:)

имхо, конечно, но можно просто ввести рэндомный параметр в алгоритм хэширования. и считать его просто один раз при запуске проги, а регулярно менять, делая rehashing таблиц. более того, можно попробовать периодически проверять равномерность распределения последних, и если она подозрительно невысокая, делать rehashing немедленно =)

IMHO в секурных прогах BY DEFINITION нельзя полагаться на алгоритмы с НЕ гарантированной сложностью. Т.е., если программа получит DoS на worst case, то она не секурная. Точка. Это и называется в просторечии "дырка".

Конечно, отсюда НЕ следует, что в секурных программах нельзя использовать алгоритмы "в среднем", типа хэшей.

Простейшее решение состоит в контроле time complexity и динамическом переключении на строгий time complexity алгоритм в подозрительных случаях. И давать отлуп по истечении таймаута независимо от NP-сложности строгого алгоритма (если только не известно заранее его полиномиальное ограничение).

Впрочем, даже хэши можно сделать псевдополиномиальными.

А какая тут вообще может быть теория, кроме "комплексити"? BTW, одна из глав "первоисточника" Garey называется Performance Guarantees and Behavior "In Practice".

> IMHO в секурных прогах BY DEFINITION нельзя полагаться на алгоритмы с НЕ гарантированной сложностью. Т.е., если программа получит DoS на worst case, то она не секурная. Точка.

Даже если этот самый worst case в общем случае нельзя определить?

Может это похоже на отсебятину, но как насчет такого:

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

2int19h :

> Даже если этот самый worst case в общем случае нельзя определить?

Да.

Это и есть дырка! Хакер нащупал worst case (случайно, может быть) и залез.

Motl (*) (01.03.2005 14:30:08):

Да ну, проще сразу длинные коллизии б-деревом разрешать (логарифм -- хорошая функция!).

Вообще, в моей практике всегда (при необходимости учета длинных коллизий) находилась более оптимальная стратегия, чем просто линейный поиск.

> Это и есть дырка! Хакер нащупал worst case (случайно, может быть) и залез.

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