Кратко и по делу — угроза + контрмеры + оценка влияния на производительность.
1) Суть уязвимостей (на примере RSA)
- Операция: $s=m^d\mathrm{mod}n$. При реализации часто используют алгоритм "square-and-multiply" (бинарное возведение в степень). Если на шаге для бита $d_i$ выполняется дополнительное умножение только при $d_i=1$, то время и потребляемая мощность зависят от битов ключа → утечки.
- Тайминговая атака: измеряют общее время (или время ответов) и восстанавливают биты экспоненты по зависимостям времени от ветвлений/длительности операций.
- SPA (Simple Power Analysis): по одной трассе мощности видны паттерны «square» vs «multiply» — читаются биты.
- DPA (Differential Power Analysis): по множеству трасс статистически кореллируют предположения о промежуточных значениях (например, Hamming weight промежуточных регистров) с измерениями и извлекают ключ.
- Особая уязвимость CRT-оптимизации: вычисляют $s_p=m^{d_p}\mathrm{mod}p$, $s_q=m^{d_q}\mathrm{mod}q$ и комбинируют: $s=s_q+q\cdot ((s_p-s_q)\cdot q^{-1}\mathrm{mod}p)$. CRT даёт ускорение, но облегчает атаки (меньшие регистры, легче анализировать), и плохо защищён против фолт-атак (одна повреждённая подвычисление может раскрыть фактор).
2) Контрмеры и механизм их работы
- Константное время (algorithmic constant-time):
- Montgomery ladder или "always do both" — на каждом бите выполнять и квадрат, и умножение (или структуру, делающую одинаковое число операций и одинаковые ветвления). Ладдер держит два накопителя и делает фиксированную последовательность операций.
- Убирают условные ветвления и непредсказуемые памяти-индексы (таблицы превращают в постоянные чтения/dummy-операции).
- Блайндинг (маскирование):
- Message blinding: выбрать случайное $r$, вычислить $m^{\prime }=m\cdot r^e\mathrm{mod}n$, вычислить $s^{\prime }=(m^{\prime }{)}^d$ и вернуть $s=s^{\prime }\cdot r^{-1}\mathrm{mod}n$. Это ломает корреляцию промежуточных значений и наблюдаемых сигналов.
- Exponent blinding: взять случайное $k$ и использовать $d^{\prime }=d+k\varphi (n)$ (результат тот же, но последовательность битов экспоненты рандомизируется).
- CRT-специфический blinding: блайндить $m$ отдельно по модулю $p,q$ или рандомизировать промежуточные значения.
- Верификация результатов (fault mitigation): после генерации подписи/расшифровки проверять $s^e\mathrm{mod}n\stackrel{?}{=}m$. При несоответствии — отклонять или вычислять безопасным (медленным) способом. Это защищает от фолтовых атак (Bellcore).
- Защиты на уровне HW и физики: шум, питание с постоянной мощностью, dual-rail логика, фильтры — дорого и аппаратно-зависимы.
- Против DPA: маскирование промежуточных значений (разбиение операции на маскируемые части), рандомизация регистров, добавление шума — требует тщательной реализации.
3) Влияние на производительность (приблизительно)
- Базовый приватный exponentiation (без CRT) для экспоненты длиной $t$ бит требует порядка $\sim t$ квадр./умножений (в зависимости от метода). Montgomery ladder выполняет примерно $2t$ мультипликаций (фиксированно) → примерно $\times 2$ по времени относительно оптимального square-and-multiply при средней Hamming weight.
- CRT: стандартно даёт ускорение примерно $\sim 3÷4\times$ по сравнению с полным модулем (т.к. вычисления делятся на два модуля вдвое меньшей длины). Отказ от CRT (чтобы избежать CRT-специфичных атак) замедлит ≈ $\times 3÷4$.
- Message blinding: добавляет одну дешёвую экспоненту с публичным $e$ (обычно мал, например $e=65537$), одну инверсию и несколько умножений — общая накладная $\sim 10\%-30\%$ в зависимости от реализации (обычно мала).
- Exponent blinding: увеличивает размер экспоненты немного (зависит от величины $k$), обычно небольшая накладная, сравнимая с $\sim 10\%-20\%$.
- Верификация результата (вычисление $s^e\mathrm{mod}n$ с малым $e$): очень дешёвая для подписей (прибавляет $\sim 5\%-15\%$).
- Маскирование/комплексное DPA-устойчивое программное обеспечение: накладные расходы могут быть значительны и варьируются от $\sim 20\%$ до $\times 2$ и более, в зависимости от уровня защиты (полное маскирование и отсутствие утечек — дорого).
- Комбинации: типичная практическая схема — использовать CRT + message blinding + проверку результата + constant-time критических функций (но не обязательно полную лестницу на всем пути). Это даёт хорошее сочетание безопасности и производительности: реальная накладная обычно $\sim 10\%-40\%$ по сравнению с небезопасной, быстрым CRT-референсом; если дополнительно применять полный constant-time ladder на всем пути, то можно получить ≈$\times 1.8÷2$ замедление.
4) Практические рекомендации (кратко)
- Всегда использовать blinding для приватных операций (сообщение или экспонента).
- Для CRT: оставить CRT (ради скорости), но обязательно делать проверку результата и блайндинг под $p,q$ либо восстановление безопасным способом при обнаружении несоответствия.
- Реализовать критичные ядра (модульное умножение/редукция) в constant-time, избегать таблиц с секретными индексами; для оконных методов применять «scatter/gather» без секретных ветвлений.
- Для высокозащищённых устройств рассмотреть аппаратные countermeasures (constant-power, noise, dual-rail) и протоколы маскирования.
Короткая сводка: основные атаки — SPA/DPA и тайминги через различия операций (например, square-and-multiply). Эффективные контрмеры — message/exponent blinding, constant-time алгоритмы (Montgomery ladder или фиксированные окна с dummy-операциями), проверка результата; их комбинирование даёт надёжную защиту с типичной накладной в районе $\sim 10\%-40\%$. Полное исключение утечек (особенно от DPA) требует более серьёзных мер и может увеличить время работы заметно ($\times 2$ и более).