Криптография побочных эффектов

Благодаря Ричарду Сноудену все больше людей теперь знают, что такое АНБ и чем оно занимается. Исходя из внутренних презентаций, которые были раскрыты, очевидно, что АНБ тратит немало усилий не только на коллекционирование трафика и внедрение “правильных” программ в сети интернет-провайдеров и софтверных гигантов, но и на анализ криптоалгоритмов. В открытый доступ попал 178-страничный документ с бюджетом национальной безопасности на 2013 год. Из него следует, что на проект Consolidated Cryptologic Program было потрачено 11 млрд. долларов. Что же можно сделать за такие деньги? Уж точно потратить с пользой. Например, на строительство гигантского вычислительного центра в штате Юта за 2 млрд. долларов, прямо в логове мормонов. Центр cодержит 2300 м2 площади под серверы, имеет собственную электростанцию в 65 Мегаватт и 60 тыс. тонн холодильного оборудования, чтобы все это охлаждать. В 2012 году из официальных уст было весьма завуалированно заявлено, что АНБ недавно достигла прорывных успехов в криптоанализе и взломе сложных систем. Уж не для этого ли им понадобился новый дата-центр? Гуру криптографии Брюс Шнайер прокомментировал эти заявления и высказал мнение, что АНБ вряд ли сможет в ближайшее время взломать какой-нибудь современный стойкий шифр, например AES. И далее сделал предположение, что АНБ направит свои усилия не на “честный” взлом алгоритмов, а на нахождение уязвимостей в самой реализации этих алгоритмов. Брюс выделил несколько областей, где можно достичь успеха:

• атака на процедуру генерации ключа, где эксплуатируются халтурные датчики случайных чисел
• атака на слабое звено в передачи данных (например, канал защищен хорошо, а сетевой коммутатор — плохо)
• атака на шифры со слабыми ключами, которые еще осталось кое-где по недосмотру системных администраторов (хороший кандидат – RSA с 1024-битным ключом)
• атака на побочные эффекты

Попробуем разобраться, что такое атаки на побочные эффекты.

Анализу защищенности различных криптосистем посвящено великое множество трудов и исследований. При этом “криптосистема” здесь рассматривается весьма широко – это может быть и некий протокол шифрования, и аппаратное устройство, и целая программно-аппаратная система с серверами, абонентами, и т. д. В первую очередь анализируется способность системы противостоять определенного рода атакам: имеется взломщик (в литературе по криптографии ему принято давать имя Ева или Мэллори), которому доступен определенный набор знаний и средств. Он их и использует для взлома системы: пытается вычислить ключ, прочитать шифрованные сообщения, осуществить подмену данных или цифровых подписей. Если потенциальный злоумышленник не может получить доступ к секретной информации данной системы, используя правдоподобные компьютерные мощности на протяжении разумного времени, то система считается стойкой. Хорошим тоном в криптографии считается не изобретение собственного алгоритма, а использование именно стойких и проверенных временем методов, так как они тщательно изучены, а их стойкость обычно подкреплена математикой. Возникает вопрос: если в своем устройстве я использую алгоритм, основанный, к примеру, на некой доказанной теореме, могу ли я быть спокоен (по крайней мере, до момента изобретения квантовых компьютеров)? Оказывается, нет.

Традиционные модели анализа защищенности рассматривают “подопытный” объект как некий черный ящик, производящий определенную операцию, например шифрование: на вход подается открытый текст, на выходе появляется шифрованный. Пусть также внутри этого ящика хранится ключ (как вариант, он может задаваться извне, быть постоянным, или генериться для каждой сессии – не важно). Главное, что ключ внешнему миру никак не доступен, а Ева довольствуется стандартным арсеналом взломщика: перехват данных на входе и на выходе, возможность подачи на вход произвольных данных в большом количестве, точное знание самого алгоритма и его параметров, и пр.

Взаимодействуя с внешним миром путем излучения, потребления электроэнергии, а также любых других регистрируемых проявлений, электронные устройства или компьютерные программы на этих устройствах могут дать злоумышленнику много полезной информации. Эти проявления называют побочными эффектами, иногда сторонними эффектами, а в англ. литературе есть устоявшийся термин – Side Channel. Для хакера эти сведения могут быть “на вес золота”, так как способны избавить его от неприятной перспективы полного перебора. По аналогии со вскрытием дверного замка: зачем вору-домушнику долго подбирать отмычки, если достаточно открутить болты, на которых крепится дверь?

Истоки

Первое серьезное упоминание о “пользе” побочных эффектов можно найти в автобиографии одного британского агента Ми-5, Питера Райта, где описывается попытка взломать шифр роторной шифровальной машины, стоявшей в посольстве Египта в Лондоне в 60-е годы. Вычислительных мощностей в те времена им явно не хватало, и тогда автор предложил установить микрофон и записывать щелчки, издаваемые машиной, в то время как каждое утро ее приводил в порядок техник. Таким образом, удалось вычислить положение двух из трех колес, чтоб в итоге помогло вскрыть шифр.

Всесторонне побочные эффекты начали рассматриваться с 1995 года, после опубликования исследований Пола Кошера (Paul Kocher), в которых он доказал наличие статистической зависимости между значением секретного ключа и временем, затрачиваемым криптоустройством на вычисление операции возведения в степень. С тех пор стало ясно, что реализация криптографии на неком аппаратном устройстве выглядит уже не так “железобетонно”. Важное место в обеспечении безопасности различных систем занимают криптопроцессоры. Они оптимизированы для выполнения криптоопераций, исполняют свой изолированный код, никак не взаимодействующий с вражеской средой, а секретный ключ хранят в собственной памяти, которая часто имеет защиту – при обнаружении несанкционированного считывания ключевой материал уничтожается. С развитием анализа побочных эффектов криптопроцессоры уже не кажутся такими стойкими по крайней мере по двум причинам:

• они доступны (банковские карты с чипом, SIM-карты, DRM-чипы в планшетах и ноутбуках, токены – со всем этим мы сталкиваемся каждый день)
• развертывание атаки на побочные эффекты не требует каких-то гигантских вычислительных мощностей и сверхдорогого оборудования. Например, цифровой осциллограф с разрешением 100 МГц стоит в районе $2000

Классификация атак

Атаки на побочные эффекты в литературе обычно классифицируются по нескольким независимым критериям.

1. По факту вмешательства

• пассивная атака: атакующий никак не вмешивается в работу устройства и является лишь наблюдателем, собирающим информацию. При этом “подопытное” устройство работает ровно так, как будто бы атаки и не происходит
• активная атака: атакующий вмешивается в работу устройства путем воздействия как на внешние и внутренние интерфейсы, или, по крайней мере, он включает устройство и инициирует его работу

2. По степени вмешательства

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

3. По способу анализа данных

• простой анализ: проводят серию их небольшого числа измерений и анализируют каждое измерение отдельно – пытаются выявить взаимосвязь между исполняемыми инструкциями и “утекаемой” информацией. Отдельно означает, что не пытаются выявить корреляции между разными измерениями, равно как и того, как изменение исходных данных влияет на изменение наблюдаемых данных. Основная проблема этого метода – отделить действительные проявления секретной информации от бесполезного шума
• дифференциальный анализ: пытаются выявить взаимосвязь между исходными данными и наблюдаемыми данными. Это достигается путем проведения большого числа измерений и последующего статистического анализа результатов. Анализ помогает нивелировать влияние шума – позволяет “отделить мух от котлет”. При этом атакующий отталкивается от некой упрощенной модели интересующего его устройства:

Практика — атака по времени на RSA-шифрование

Опишем популярную и хорошо изученную в литературе атаку по времени на RSA-шифрование. Основа атаки – точное измерение времени, затрачиваемого на выполнение криптоопераций. Здесь предполагается, что хакер имеет в наличии само устройство, оборудование, необходимое для подачи данных на вход и отмеривания временных отметок, а также он достоверно знает, что в устройстве используется именно RSA.

Атаки по времени в принципе возможны благодаря тому, что атакуемое устройство тратит разное время на выполнение криптоопераций как в зависимости от данных на входе (будь то шифр или открытый текст), так и от ключа. Эта разница усиливается оптимизацией: процессор “стремится” оптимизировать по максимуму и, как следствие, какие-то операции могут выполняться заметно быстрее, чем мы предполагали теоретически.

Как известно, в основе алгоритма RSA (и Diffie-Hellman то же) лежит операция возведения в степень по модулю. Предлагаю использовать следующие обозначения:

m – открытый текст (от message)
c – шифр (от cipher)
{e, n} – открытый ключ (от encryption – берется при шифровании)
{d, n} – закрытый ключ (от decryption – берется при расшифровании)
w – разрядность ключа (от width)
d[i] – i-й бит ключа

Тогда процесс расшифрования будет выглядеть так:
m = c^d mod n
Здесь n общедоступно, так как является частью открытого ключа, а с можно заполучить, прослушивая канал с данными. Наша цель – найти d.

Существуют различные алгоритмы вычисления этой формулы, так как вычислять ее “в лоб” слишком затратно. Предположим, что на нашем криптоустройстве используется самый простой алгоритм быстрого возведения в степень, часто называемый двоичный алгоритмом экспонирования, либо, как в иностранных источниках, — square and multiply или exponentiation by squaring. Вот его псевдокод:

int squareAndMultiply(c, d, n) {
	R = array(0..w-1)
	S = array(0..w-1)
	s(0) = 1
	for (k = 0, k < w, k++) {
		if (d[k] == 1)
			R(k) = (s(k) * y) mod n
		else
			R(k) = s(k)
		s(k+1) = (R(k) ^ 2) mod n
	}
	return R(w–1)
}

Очевидно, что итерации для нулевых битов ключа будут занимать меньше времени, чем для единичных битов, так как первом случае процессор делает умножение, а во втором – только присваивание. Покажем, как можно вычислить весь ключ, измеряя время выполнения функции squareAndMultiply. Точных формул приводить не будет, опишем общий смысл.
Способ, предложенный Кошером, заключается в итеративном вычислении битов ключа: сначал бит 0, потом бит 1, и так далее, при этом каждая такая итерация обладает следующими свойствами:

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

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

1. общее время выполнения функции
2. время, затраченное системой на обработку уже известных битов ключа
3. время, приходящееся на операцию (s(k) * y) mod n в нашем алгоритме

Параметр 1 измерить проще всего, подавая на вход некий шифртекст, 2 и 3 – по сложнее, но тоже реально, если знать особенности физической реализации устройства или слегка его “препарировать”. Тогда время, затраченное на обработку всех неизвестных битов, следующих за исследуемым, будет равно:

• T = T1 – T2, если исследуемый бит = 0
• T = T1 – T2 – T3, если исследуемый бит = 1

Проведя множество измерений для данного исследуемого бита и накопив целый “ворох” значений T, можно вычислить вероятности того, что этот бит равен 1 и 0 соответственно, используя формулы условной вероятности.

Мы только что рассмотрели самый простой алгоритм возведения в степень, годный для атаки по времени. В современных криптосистемах он редко используется, а вместо него применяют более оптимальные способы. Обычно это алгоритм на основе китайской теоремы об остатках, алгоритм Монтгомери или алгоритм Карацубы. Но даже эти “продвинутые” алгоритмы, будучи примененными в чистом виде, подвержены временным атакам, что было доказано успешной атакой на OpenSSL-сервер.

Атака на OpenSSL-сервер

Изначально считалось, что удел временных атак – это исключительно аппаратные устройства: хакер берет, например, смарткарту, обвешивает ее датчиками и приборами, а затем извлекает секретные ключи. Но как показали Дэвид Брумли и Дэн Бони из Стендфордского Университета, временной атаке подвластно и программное обеспечение, в частности – Web-сервер, принимающий SSL-соединение с использованием “стоковой” библиотеки OpenSSL версии 0.9.7. И это несмотря на то, что типичный сервер выполняет множество параллельных процессов, а канал доступа к серверу вносит и свою лепту. Тем не менее, было сделано три успешных варианта атаки:

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

Протокол SSL/TLS описан в деталях в RFC 6101 (SSL v3.0), 2246 (TLS v1.0), 4346 (TLS v1.1), 5246 (TLS v1.2) и 6176 (TLS v2.0), поэтому сконцентрируем внимание на той его части, которая является целью атаки. Итак, типичный handshake включает в себя такие этапы:

1. Клиент посылает сообщение ClientHello, в котором передает 28-байтовое случайное число и список поддерживаемых шифров
2. Сервер посылает сообщение ServerHello, аналогичное клиентскому
3. Сервер посылает сообщение Certificate со своим сертификатом
4. Клиент, получив серверный сертификат, извлекает из него открытый ключ сервера, шифрует им 48-байтовое случайное число, и передает его серверу в сообщении ClientKeyExchange
5. Сервер расшифровывает случайное число клиента своим закрытым ключом, после чего вычисляется обоюдный мастер-ключ

Отметим, что в п. 4 блок форматируется в соответствии со стандартом PKCS#1 (тип 2):

[ 0x00 ] [ 0x02 ] [ строка-заполнитель (padding) ] [ данные ]

, после чего шифруется.

Итерация атаки заключается в посылке серверу пробных данных в качестве шифрованного блока. После расшифровки сервер естественно обнаруживает, что данные не отформатированны согласно PKCS#1. Моментальное прерывание handshake на данном этапе открывало бы уязвимость (атаку на которую показал Данэль Блейхенбахер из Bell Laboratories), поэтому современные реализации SSL/TLS “делают вид”, что ошибки нет, и продолжают handshake. В результате клиент и сервер вычислят различный мастер-ключ, что всплывет при следующих сообщениях — так или иначе, клиент получит сообщение Alert и соединение будет прервано, но это нас уже мало интересует. Главное, что делается замер времени с момента отправки ClientKeyExchange и до получения ответа от сервера. Тут вспомним, что N = p·q является RSA-модулем, а секретная и открытая экспонента связаны соотношением d·e = 1 mod (p-1)(q-1). Так вот, проведя серию измерений, можно бит за битом восстановить q, а следовательно и найти закрытый ключ. Откуда же такие чудеса? Для точного доказательства пришлось бы привести целый ворох математических формул, что выходит за рамки этой статьи, а вместо этого я опишу общие принципы, которые лежат в основе анализа. Их два.

Для начала отметим, что OpenSSL для экспонирования по модулю использует бинарый алгоритм, описанный ранее, но с рядом оптимизаций. Во-первых, применив Китайскую Теорему об Остатках, задача m = c^d mod N разбивается на две подзадачи m1 = c1^d1 mod p и m2 = c2^d2 mod q, после чего из двух чисел m1 и m2 по специальной формуле получается m. Во-вторых, умножение по модулю, используемое в алгоритме, оптимизируется методом Монтгомери. Суть метод в том, чтобы уйти от вычисления по исходному модулю и вычислять по модулю, равному степени 2, что намного быстрее для процессора. Вначале оба множителя конвертируются в специальную форму Монтгомери, затем делается быстрое умножение, после чего результат переводится в обычную форму. Все бы ничего, да в 2000 г. немецкий профессор Вернер Шиндлер обнаружил, что чем более g близко к числу, кратному q, тем больше времени занимает весь алгоритм. Вот и первый принцип: измеряя время метода Монтгомери, можно делать вывод о том, насколько g близко к q, 2q, 3q и т.д.

Идем дальше. Само простое умножение (без взятия по модулю) реализовано в OpenSSL двумя способами: обычным и методом Карацубы. Сложность обычного метода оценивается в O(n·m), где m и n – размеры множетилей. Советский ученый А. А. Карацуба впервые изобрел метод быстрого умножения со сложностью O(n^1,58). Именно его и использует OpenSSL в том случае, когда множители одинакового размера. Отсюда следует второй принцип: если g чуток меньше числа, кратного q, то будет использован быстрый метод, а если чуток больше, то будет затрачено большее время.

Авторам этой атаки на OpenSSL удалось продемонстрировать, что для нахождения 1024-битного ключа хватило около миллиона запросов, что заняло примерно 2 часа. Но не спешите паниковать. Начиная с версии 0.9.7b, OpenSSL содержит защиту от временных атак. Защита заключается в бесполезном вычислении x = r^e · с · mod N до самой операции дешифрования, где r – случайное число, e – секретная экспонента, c – шифрованный текст. Эта операция вносит случайную задержку и не позволяет информации о ключе “просочиться” в побочные эффекты. Цена защиты – от 2% до 10% потери производительности.

Атаки на энергопотребление

Перейдем к другому классу атак на побочные эффекты – атаки на энергопотребление. Эти атаки реально применить только к аппаратным криптографическим модулям, и чем более изолированную и узкую функцию выполняет модуль, тем успешнее атака. Очевидно, что разные инструкции, выполняемые процессором, потребляют разное количество энергии, которая в итоге определяется количеством переключений транзисторов. (Из курса физики мы все знаем, что МОП-транзисторы потребляют ток в момент переключения, а в покое их ток пренебрежимо мал, чего не скажешь об ТТЛ-транзисторах). Следовательно, инструкции или группы инструкций можно идентифицировать на графике потребления. Но тот же Кошер показал, что проанализировав графики потребления смарткарт, можно извлечь секретный ключ.

Вот график потребления для DES-шифрования одного блока: видна начальная перестановка, 16 раундов шифрования и конечная перестановка:

А вот подробный график 2-го и 3-го раунда:


Атаки на потребление принято классифицировать на простые и дифференциальные (сокращенно – SPA, Single Power Analysis, и DPA, Differential Power Analysis). Графики, наподобии приведенных выше, анализируются в SPA-атаках, где основная цель – сопоставить участки графика выполняемым инструкциям или функциям и каким-то образом определить значения, возникаемые в регистрах устройства. SPA-атака предполагает, что имеются подробные сведения о внутренней реализации устройства. DPA-атака, напротив, базируется на статистическом анализе результатов множества измерений. Например, классическая атака на DES смарткарты, описанная Кошером, выглядит так:

1. регистрируют энергопотребление нескольких последних раундов для 1000 DES-шифрований, причем для после каждого раунда регистрируется также и результат шифрования
2. график для каждого такого шифрования разбивают на 100000 равных отрезков, и каждому отрезку ставится в соответствие его энегропотребление
3. полученную матрицу 1000 x 100000 анализируют статистическими методами и находят ключ​, который был неизменен на протяжении всего периода измерений. (За точным алгоритмом читателю предлагается обратиться к первоисточнику, так как формат хабра-статьи не очень удобен для выкладки многоэтажных формул)

Противодействие

Мы рассмотрели несколько вариантов атак на побочные эффекты. Во всем мире поняли, что при проектировании криптосистем подобные атаки надо учитывать еще на этапе разработки. Здесь действуют по нескольким направлениям:

• Создание препятствий к считыванию побочной информации. Очень ограниченная мера, если только не предотвратить физический доступ к устройству. В остальных случаях взлом сводится обычно к удорожанию оборудования для сбора данных, и если его стоимость превысит ценность самого взлома, то тогда цель достигнута
• Внесение случайных помех в “утекаемые” сигналы. Это уже более эффективная мера, но и здесь есть свои подводные камни. Во-первых, получение случайных данных в компьютерной системе само по себе является проблемой: где их взять и в нужном количестве. Если помеха будет “не совсем” случайная, то закономерности можно вычислить и дальше отделить шум от полезного сигнала. Во-вторых, даже на “хороший” случайный шум хакер может найти редуцирующий алгоритм, и чем больше данных он насобирает, тем больше вероятность успеха
• Попытка сделать систему детерминированной. Например, чтобы все операции занимали одинаковое время — тогда атака по времение будет бесполезна. Этого тоже непросто достичь, так как на арену выходят оптимизации процессора и компилятора, наличие нескольких уровней кэш-памяти с разным временем доступа – все это играет на руку взломщику
• Проектирование криптоалгоритмов и протоколов, изначально стойких к утечкам по побочным каналам – это самое надежное противодействие. Например, применить такой алгоритм вычисление некой формулы, время выполнения которого не зависело бы ни от разрядности входных данных, ни от количества нулей или единиц в них, ни от каких-либо других свойств аргументов

Дизайну атак на побочные эффекты посвящено множество научных трудов. И не в коем случае не стоит думать, что этим атакам подвержены только старые криптоалогоритмы: RSA, DES, Diffie-Hellman. Уже есть доказательства “утечек” от AES, и от алгоритмов на эллиптических кривых. Охватить все это в рамках одной статьи нереально. Моя задача лишь заинтересовать читателей для углубления в эту увлекательную тему.

Для тех, кто хочет углубиться

• Introduction to Differential Power Analysis and Related Attacks. Paul Kocher, Joshua Jaffe, Benjamin Jun
• Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. Paul C. Kocher
• Remote Timing Attacks are Practical. David Brumley, Dan Boneh
• Timing Attacks on RSA. Mark van Cuijk
• Side channel cryptanalysis of product ciphers. John Kelsey, Bruce Schneier, David Wagner, Chris Hall
• DPA Attacks and S-Boxes. Emmanuel Prouff