Сторонние каналы: когда время и кэш выдают секрет

Криптография анализирует алгоритмы в модели, где противник видит только входы и выходы. Реальный процессор добавляет к этому время, потребление энергии, электромагнитное излучение и состояние кэша. Сторонний канал — это любая такая утечка, и история показывает, что её достаточно, чтобы извлечь ключ, не ломая ни один шифр.

Тема идёт от простого к сложному. Сначала время: сравнение тегов с ранним выходом и атака Кохера на модульное возведение в степень. Потом кэш: Flush+Reload и Prime+Probe, на которых ломали AES и восстанавливали ключи RSA. Затем энергопотребление: DPA и корреляционный анализ. Завершается защитой: константное время, маскирование, ослепление и то, почему эти меры обязательны даже в «чистом» коде.

Время как канал

Ранний выход

Функция сравнения тегов часто пишется так: пройти по байтам и вернуть False на первом несовпадении. Это быстро и естественно — и утекает: время работы зависит от того, сколько байт совпало. Противник подбирает байт за байтом, измеряя время ответа; для 16-байтного тега это в сотни раз меньше работы, чем полный перебор ¹.

Защита — сравнение без раннего выхода: пройти все байты, накопить различие в переменной и проверить его в конце. Длина тоже должна обрабатываться отдельно, чтобы не создавать второй канал.

Атака на возведение в степень

Кохер показал, что реализация m^d mod n с ветвлением по битам d утекает: умножение выполняется только для единичных бит, и время зависит от ключа. Атака восстанавливает d по замерам. Защита — алгоритм с постоянным числом операций (Монтгомери, «always multiply») и ослепление: m' = m·r^e, результат делится на r, и время перестаёт коррелировать с m ¹.

Схема на рисунке 1.

Удалённые атаки

Брумли и Боне показали, что атака по времени работает по сети, несмотря на шум: статистика по many запросам выделяет сигнал ³. Это изменило отношение к «локальным» утечкам: если сервер считает что-то секретное, время ответа — публичный канал. Lucky13 показал, что такой канал находится и в MAC-обработке TLS ⁸.

Кэш как канал

Flush+Reload и Prime+Probe

Кэш общий между процессами и ядрами. Flush+Reload использует разделяемую память: противник сбрасывает строку кэша, ждёт, пока жертва обратится к ней, и по времени доступа узнаёт, было ли обращение. Prime+Probe не требует разделяемой памяти: противник заполняет кэш своими строками и смотрит, какие вытеснены ⁴.

На этом ломали AES: таблицы подстановок индексируются байтами ключа, и обращение к конкретной строке кэша выдаёт байт. Первые работы — Бернстайн и независимо Гуллаш с соавторами ⁵⁶.

Spectre и Meltdown

Спекулятивное исполнение добавляет новый класс: процессор выполняет инструкции, которые не должны были выполниться, и оставляет следы в кэше. Spectre и Meltdown показали, что границы процессов и ядра не спасают от утечки через микроархитектурное состояние ⁷. Для криптографии это означает: константное время на уровне языка недостаточно, если компилятор или процессор вносит ветвления.

Схема на рисунке 2.

Энергопотребление и DPA

Идея

Каждая операция потребляет энергию, и потребление зависит от данных: вес Хэмминга, переключения битов. Дифференциальный анализ энергопотребления (DPA) собирает много трасс и коррелирует их с гипотезами о ключе. Для AES достаточно гипотезы о выходе S-бокса: SBOX(p ⊕ k); верный байт даёт максимальную корреляцию ².

Почему это работает

Шум велик, но он случаен, а сигнал систематичен. При тысячах трасс корреляция верной гипотезы статистически значимо превышает корреляцию неверных. Атака не требует знания реализации: достаточно модели потребления.

Защита

Маскирование: значение x заменяется на x ⊕ m, и все операции ведутся над долями; потребление перестаёт коррелировать с x. Скрытие: случайные задержки и дополнительная работа, чтобы выровнять трассы. Комбинирование даёт практическую стойкость, но не абсолютную: атаки высшего порядка и профилирование продолжают работать.

Как писать константный код

Правила

Не ветвиться по секрету. Не индексировать массивы секретом. Не использовать секрет в условиях выхода из цикла. Не полагаться на то, что компилятор «сам оптимизирует». Сравнивать теги целиком и накапливать различие. Использовать библиотечные функции, спроектированные для этого (например, hmac.compare_digest), а не самописные.

Проверка

Автотесты не ловят утечки по времени. Помогают анализ на уровне машинного кода, инструменты вроде dudect (статистическая проверка константности), ревью и осторожность с оптимизациями. В Python и Java константность принципиально ограничена: виртуальная машина и сборщик мусора вносят шум, поэтому критические операции выносят в нативные библиотеки.

Итоги темы

• Время, кэш и энергия — реальные каналы утечки, а не теория.
• Ранний выход в сравнении тегов выдаёт секрет побайтово.
• Ветвление по битам ключа ломается атакой Кохера; ослепление помогает.
• Flush+Reload и Prime+Probe извлекают индексы таблиц; Spectre расширил класс.
• DPA восстанавливает ключ по корреляции трасс.
• Защита: константный код, маскирование, ослепление, библиотечные примитивы.

Литература

1. Kocher P. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. CRYPTO 1996. — исходная работа по атакам на время.
2. Kocher P., Jaffe J., Jun B. Differential Power Analysis. CRYPTO 1999. — DPA и корреляционный анализ.
3. Brumley D., Boneh D. Remote Timing Attacks are Practical. USENIX Security 2003. — атака по сети на RSA в OpenSSL.
4. Yarom Y., Falkner K. Flush+Reload: A High Resolution, Low Noise, L3 Cache Side-Channel Attack. USENIX Security 2014. — методика кэш-атаки.
5. Bernstein D. Cache-Timing Attacks on AES. 2005. — таблицы AES как источник утечки.
6. Gullasch D., Bangerter E., Krenn S. Cache Games — Bringing Access-Based Cache Attacks on AES to Practice. IEEE S&P 2011. — практическая реализация.
7. Kocher P. et al. Spectre Attacks: Exploiting Speculative Execution. IEEE S&P 2019. — спекулятивное исполнение как канал.
8. AlFardan N., Paterson K. Lucky Thirteen: Breaking the TLS and DTLS Record Protocols. IEEE S&P 2013. — тайминговая атака на MAC в реальном протоколе.

Дополнительные материалы к апокрифу 13

Вопросы для самопроверки

1. Чем сторонний канал отличается от криптоаналитической атаки?
2. Почему сравнение тегов с ранним выходом утекает?
3. Как время ответа выдаёт биты показателя степени?
4. Что делает ослепление и от чего защищает?
5. Как работает Flush+Reload?
6. Почему Prime+Probe не требует разделяемой памяти?
7. Что именно утекает из таблиц AES?
8. Как Spectre использует спекулятивное исполнение?
9. Что такое вес Хэмминга и почему он важен для DPA?
10. Сколько трасс нужно для восстановления ключа?
11. Как шум влияет на необходимое число трасс?
12. Чем маскирование отличается от скрытия?
13. Почему константный код нужно проверять инструментами?
14. Почему Lucky13 — атака на протокол, а не на примитив?
15. Что можно и чего нельзя гарантировать в Python?

Глоссарий темы

Шпаргалка

cp timing_template.py timing.py && python3 check_timing.py
python3 leaky_mac.py
python3 dpa_service.py

Что почитать и посмотреть

• Kocher 1996 — атака по времени.
• Kocher, Jaffe, Jun 1999 — DPA.
• Brumley, Boneh 2003 — удалённая атака на OpenSSL.
• Yarom, Falkner 2014 — Flush+Reload.
• Bernstein 2005 — кэш-атаки на AES.
• Kocher et al. 2019 — Spectre.
• AlFardan, Paterson 2013 — Lucky13.
• Документация hmac.compare_digest — https://docs.python.org/3/library/hmac.html#hmac.compare_digest.

Углубление: почему «просто добавь задержку» не работает

Скрытие (случайные задержки) снижает корреляцию, но не устраняет её: при достаточном числе измерений сигнал выделяется из шума. Маскирование устраняет сам сигнал: потребление перестаёт зависеть от секрета, потому что все промежуточные значения маскированы случайными долями. Именно поэтому маскирование считается сильнее скрытия, а на практике их комбинируют.

Аналогично с временем: sleep(random) не делает код константным; константным его делает отсутствие ветвлений и зависимых от данных обращений к памяти.

Углубление: почему Lucky13 — протокол, а не шифр

Lucky13 эксплуатирует разницу во времени вычисления MAC в TLS для CBC-режимов: время зависит от того, сколько байт дополнения пришлось обрабатывать. Это утечка уровня протокола, а не AES. Она показывает, что сторонний канал может жить в коде, который «просто проверяет дополнение», и что защита требует анализа всей цепочки обработки, а не только примитива.

Лабораторная работа 13. Секрет, который видно по времени

• Раздел курса: апокриф 13 «Сторонние каналы: время, кэш, энергопотребление»

Введение

В «Сейфе» проверка тега написана так, как пишут все: цикл по байтам и return False на первом несовпадении. Формально всё верно, криптография не ломается — а тег восстанавливается побайтово по времени ответа. Рядом лежит AES-реализация с таблицами подстановок, и обращение к ним по секретному индексу оставляет след в кэше. А на смарт-карте тот же ключ читается по энергопотреблению.

Работа показывает три канала. Сначала время: сравнение тегов с ранним выходом и восстановление секрета. Затем кэш: модель Flush+Reload, в которой сервис отдаёт след последнего сравнённого байта, и побайтовая атака. Затем энергопотребление: синтетические трассы AES и корреляционный анализ, восстанавливающий ключ. Завершается константным кодом и проверкой, что утечка устранена.

Части: сравнение, след кэша, DPA, защита, продвинутая.

Цель работы

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

После выполнения работы получится:

• писать сравнение без раннего выхода и объяснять, почему это обязательно;
• восстанавливать секрет по следу кэша побайтово;
• восстанавливать ключ AES по синтетическим трассам DPA;
• объяснять, чем маскирование отличается от скрытия;
• формулировать правила константного кода.

Теоретический минимум

Разделы «Время как канал», «Кэш как канал», «Энергопотребление и DPA», «Как писать константный код» апокрифа 13. Соотношения:

ранний выход: время ~ числу совпавших байт
DPA: корреляция(weight(SBOX(p ⊕ k)), trace)
маскирование: x → x ⊕ m, операции над долями
ослепление RSA: m' = m·r^e mod n, результат · r^(−1)

Перечень оснащения

Ubuntu 24.04, Python 3.10+. Права root не нужны. Архив lr-env.

mkdir -p ~/lab-apocrypha-13 && cd ~/lab-apocrypha-13
unzip ~/lr-env.zip
cp timing_template.py timing.py
python3 check_timing.py

Порядок выполнения работы

В журнале фиксируйте: число сравнений на атаку, число трасс до верного ключа, корреляцию верной и лучшей неверной гипотезы. Провал — с причиной: неверный признак верного байта, потерян последний байт, не та модель потребления.

Часть 1. Сравнение без раннего выхода

Задание

1. Реализуйте ct_compare(a, b): сравнить все байты, накопить различие, проверить длину отдельно.
2. Убедитесь, что при различии в первом байте выполняется столько же операций, сколько при различии в последнем.
3. Запустите python3 check_timing.py: проверки сравнения.
4. Сравните с hmac.compare_digest из стандартной библиотеки. Объясните, почему свою реализацию всё равно полезно понимать.
5. Ответьте: почему проверка длины — отдельный канал и как её делать безопасно.

Часть 2. След кэша

Задание

1. Изучите leaky_mac.py: verify с ранним выходом выставляет last_index — модель Flush+Reload.
2. Реализуйте recover_by_oracle(mac): для позиции i перебирайте байт; признак верного — след ушёл дальше i, а для последнего байта — True.
3. Запустите проверку: секрет должен совпасть, сравнений — не больше 4096.
4. Оцените, во сколько раз это быстрее полного перебора 16 байт.
5. Ответьте: почему в реальной атаке след кэша не отдаётся явно, а измеряется временем доступа.

Часть 3. DPA

Задание

1. Изучите dpa_service.py: трасса для байта — вес Хэмминга SBOX(p ⊕ k) плюс шум.
2. Реализуйте recover_dpa: для каждого байта и каждой гипотезы постройте ряд весов и посчитайте корреляцию с трассой.
3. Запустите проверку: ключ должен восстановиться на 2500 трассах.
4. Уменьшайте число трасс, пока ключ не начнёт ошибаться. Запишите порог.
5. Увеличьте шум и повторите. Объясните, как шум связан с числом трасс.
6. Ответьте: почему маскирование ломает именно эту корреляцию.

Часть 4. Защита

Задание

1. Замените leaky_mac.verify на константное сравнение и покажите, что recover_by_oracle перестаёт работать.
2. Реализуйте ослепление для модульного возведения в степень и покажите, что время перестаёт зависеть от входа.
3. Сформулируйте пять правил константного кода и найдите по одному нарушению в учебных примерах.
4. Объясните, почему в Python константность ограничена и что делают библиотеки.
5. Ответьте: чем маскирование отличается от скрытия и почему их применяют вместе.

Часть 5. Продвинутая: проверка константности

Задание

1. Реализуйте статистический тест: две группы входов, сравнение распределений времени, оценка значимости.
2. Прогоните тест на раннем выходе и на константном сравнении; зафиксируйте p-value.
3. Разберите Lucky13 как пример утечки в реальном протоколе: где именно время зависит от данных.
4. Сформулируйте, почему «локальная» утечка в библиотеке становится сетевой в протоколе.
5. Соберите чек-лист ревью кода на сторонние каналы.

Что должно получиться

Тест, различающий реализации, разбор реального инцидента и чек-лист.

Журнал работы

Фиксируйте: число сравнений, корреляцию, число трасс до ошибки, p-value. Провал — с причиной.

Контрольные вопросы

1. Что такое сторонний канал?
2. Почему ранний выход в сравнении опасен?
3. Как атака Кохера восстанавливает показатель степени?
4. Что даёт ослепление?
5. Как работает Flush+Reload?
6. Почему таблицы AES уязвимы к кэш-атакам?
7. Что такое Spectre и как он связан с кэшем?
8. Как DPA использует корреляцию?
9. Почему маскирование помогает против DPA?
10. Чем скрытие отличается от маскирования?
11. Почему константность в Python ограничена?
12. Как Lucky13 превращает утечку в атаку на протокол?