Таймерные атаки на RSA

Реализуя сетевой протокол аутентификации я столкнулся с проблемой защиты от атак на rsa по таймеру.
Как известно, от rsa ключа зависит время шифрования данных, и сещуствует возможность послав большое количество запросов и измерив время ответа, вычислать секретный ключ (известны даже успешные реализации таких атак).

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

 

озадачил

 

Стандартное время на аутентификацию вводи, а не случайные задержки.
То есть, запрос поступил, снял текущее время - аутентификацию завершил - снова получил текущее время. Если время меньше некоторого фиксированного значения, сделал типа Sleep на (Тфикс-(Тпослеаутентификации - Тдоаутентификации))
Также можно подстраивать Тфикс на случай если
Тфикс < (Тпослеаутентификации - Тдоаутентификации) - тогда
Тфикс = (Тпослеаутентификации - Тдоаутентификации).

 

Ну почему же неприемлемо ?
Атака производится оперируя миллисекундами, введи задержку c равномерным распределением в диапазоне [0.2 - 0.5] секунд - и атаку затруднишь и end-user ничего не почувствует.

Или сколько у тебя среднее время аутентификации ?

 

Среднее время шифрования на секретном ключе около 1мс, но увеличивать это время совершенно недопустимо, ввиду того, что это и так самая тормозная часть протокола. Задержка уже сделает работу сервера совершенно невозможной.
Допустим, у нас поступает в секунду 1000 запросов аутентификации, при этом уже все процессорное время уйдет на их обработку. Если же сюда добавить еще и вызов Sleep, то все сразу умрет...

 

С таким диапазоном сразу можно будет вобще забыть о всякой аутентификации. просто все рабочие потоки сервера будут большую часть времени висеть в sleep.

 

1. Задержку в 1 или 20 мс пользователь не различит.
2. С чего это ВСЁ и СРАЗУ умрет? Пока тред спит остальные фурычат. Ты просто отложишь время возрата результата. Как предлагалось или добавь случайное время или приведи все к одному.

 

Максимум можно создать 1200 потоков (но при этом уже немалая часть процессорного времени будет уходит только на их переключение). В случае же ввода задержки, они будут ждать ВСЕ, не останется потоков обрабатывающих запросы.

 

Да, кстати, забыл сказать, что в случае ввода задержки более 5мс (независимо от числа потоков), у меня просто переполниться очередь tcp соединений. Короче варианты с задержками не обсуждаются.
Я думаю, надо идти в направлении увеличения производительности работы с большими числами. Тогда естественные задержки прохождения пакетов покроют время аутентификации.

Вопрос: кто-нибудь производил тестирование различных библиотек для работы с большими числами на производительность?

 

правильно поставленный вопрос - 80% ответа. Ты неверно сформулировал проблему и упорно пытаешься ее решить. Тебе правильно посоветовали про задержки, а вот проблемы с tcp и потоками явно идут от неверного дизайна системы. Мое имхо - не в ту сторону роешь, если простая задержка валит твою систему, то ее надо переделать. Иначе обычный клиент с медленным диалапом свалит ее тожно также.

 

Я не просил советовать делать задержки, я про это написал еще в первом посте.
Если кто-то знает метод решения этой проблемы не связаный с задержками и падением производительности, то пусть скажет. А советовать ввести задержки любой горазд.

Дизайн системы заточен на полностью асинхронную обработку запросов в малом числе потоков. И нельзя допускать накопления более 15000 запросов в очереди, т.к. это сильно валит производительность. В идеале, число потоков должно быть в 2 раза больше числа процессоров в системе. Введение любой блокирующей операции потребует увеличения числа потоков, что повлечет расходы на их переключение.

Короче, еще раз повторяю. В этом топике обсуждаем фундаментальные методы решения этой проблемы, а не архитектуру обработки запросов примененную у меня. Из возможных фундаментальных путей я вижу следующие
1) Повышение производительности работы с большими числами. Задержки шифрования будут покрываться задержками пакетов.
2) Использование алгоритмов работы с большими числами, время выполнения которых не зависит от числа.

З.Ы. кстати, кто-нибудь исследовал зависимость времени шифрования от числа, при использовании Китайской теоремы остатков, для шифрования на секретном ключе?

 

А ты сделай аутентификацию на датаграммах - никаких переполнений тсп стека и не будет

Не нужно создавать поток для каждого соединения. сделай вертушку с каким-нибудь ручным алгоритмом диспетчеризации запросов

 

А вот нельзя, надо именно tcp.

Я сетевые приложения не первый день пишу. читай внимательно

Все запросы обрабатываются в двух/четырех потоках.

 

PE386

Исходя из этого я и подумал что ты делаешь по одному потоку на каждую аутентификацию. Если у тебя потоков по 2 на каждый процессор - никаких sleep не будет, а будет GetTickCount и что-то вроде VoidPopQueue()

Сделай для каждой аутентификации по 2 тсп соединения. одно запрос на аутентификацию. 2-е - получение результатов (инициируемое с клиента через n миллисекунд)

 

Опять же нельзя. Все должно оставаться в рамках спецификаций протокола http.

З.Ы. мы тут особенности реализации протоколов обсуждаем, или особенности rsa? Я бы хотел обсудить второе, а с протколом я и сам справлюсь.

 

PE386

А какая, собсвтенно, разница, в твоем случае, реализованы задержки на уровне математики rsa, или с помощью протокола аутентификации? В любом случае, задержки лишь возрастут (с rsa ты ничего не поделаешь) но в случае изменения математики шифрования у тебя даже возрастет нагрузка на процессор, по сравнению с протокольным решением.

ИМХО

 

А вообще имхо можно сделать NDIS Intermediate драйвер со случайными задержками пакетов +/- пару миллисекунд. Просто и эффективно. В DDK есть даже пример такого драйвера

 

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

Например, если изначально приведение x по модулю m в коде выглядит так:

if( something ) {
x = x - m;
}

то нужно добавить вторую ветку, подобную первой:

if( something ) {
x = x - m;
}
else {
temp = temp - m;
}

и т.д.

 

RElf
Вот первый дельный пост в этой теме! Неплохое решение, жаль правда несколько снижает производительность.

З.Ы. проблема уже решена написанием быстрой работы с большими числами на ассемблере (задержки шифрования менее 0.5 мс распознать удаленно нельзя). Но если у вас есть еще идеи, то тема остается открытой.

 

здесь