Ключевые атаки

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

Подходы

В своей основополагающей статье ^[1] Что касается атак с поиском ключей, Шамир и ван Сомерен предложили два разных подхода к поиску ключей: статистический или энтропийный поиск ключей и аналитический поиск ключей. Первый метод основан на обнаружении различий в статистических свойствах данных, составляющих криптографические ключи, а второй — на определении конкретных шаблонов байтов, которые обязательно должны существовать в материале целевого ключа, и на поиске этих шаблонов.

Статистический ключевой вывод

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

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

Аналитический ключевой вывод

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

Шамир и ван Сомерен ^[1] продемонстрировал один пример этого аналитического подхода к поиску частных ключей RSA , где открытый ключ известен и имеет небольшой открытый показатель. В системе RSA открытый ключ представляет собой пару. $(n,e)$ , где $n=p.q$ где p и q — два больших простых числа. Соответствующий закрытый ключ $(n,d)$ (или иногда $(p,q,d)$ или какой-либо его вариант), где $e.d\equiv 1{\pmod {\phi (n)}}$ , то есть e, умноженное на d, эквивалентно 1 по модулю $\phi (n)$ где φ представляет собой функцию Эйлера и размер мультипликативной группы по модулю n. В случае ключа RSA:

$\phi (n)=(p-1)(q-1)=n-p-q+1$

Нахождение значения $\phi (n)$ from n позволяет факторизовать n , и безопасность криптосистемы RSA зависит от сложности этого процесса. Таким образом, злоумышленник не может точно определить d , зная e и n . Однако атака может многое узнать о том, как выглядит d , учитывая, что p и q обычно выбираются одинаковой длины в битах и оба «близки» к квадратному корню из n . Таким образом, злоумышленник может приблизительно предположить:

$\phi (n)\approx \phi '(n)=n-2{\sqrt {n}}$

и обычно это приближение будет правильным в более значимой половине битов его двоичного представления. Связь e и d означает, что:

$d=(1+k.\phi (n))/e$

где точное значение k неизвестно, но $0<k<e.$ Используя этот факт и приближение $\phi '(n)$ злоумышленник может перечислить набор возможных значений верхней половины двоичного представления d для каждого возможного значения k . Эти двоичные шаблоны можно проверить на много порядков быстрее, чем выполнить расшифровку следа. Кроме того, в обычном случае $e=3$ можно показать, что $k=2,$ старшей половины битов d что позволяет точно определить и выполнить непосредственный поиск .

Приложение

Атаки с поиском ключей использовались в сочетании с атаками с холодной загрузкой для извлечения ключей из машин после их выключения. ^[2] Хенингер и Шахам показали, что ключи можно извлечь, даже если данные в памяти были повреждены из-за отключения питания. ^[3]

Статистический поиск ключей был использован Нико ван Сомереном для обнаружения ключей проверки подписи, используемых Microsoft для проверки подписей в надстройках MS-CAPI. Позже выяснилось, что один из этих ключей был назван NSAKEY , что вызвало некоторые споры. Microsoft ^[4]

Смягчения

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

Ссылки

^ Jump up to: ^а ^б Шамир, Ади; ван Сомерен, Нико (1 января 1998 г.). Игра в прятки с сохраненными ключами . Конспекты лекций по информатике. стр. 118–124. CiteSeerX 10.1.1.40.4467 .
^ Халдерман, Дж. Алекс; Шон, Сет Д.; Хенингер, Надя ; Кларксон, Уильям; Пол, Уильям; Кэл, Джозеф А.; Фельдман, Ариэль Дж.; Фельтен, Эдвард В. (1 января 2008 г.). «Меньше всего мы помним: атаки с холодной загрузкой на ключи шифрования» . На симпозиуме по безопасности USENIX .
^ Хенингер, Надя ; Шахам, Ховав (1 января 2009 г.). «Восстановление закрытых ключей rsa из случайных битов ключа». Труды Крипто 2009 . стр. 1–17. CiteSeerX 10.1.1.215.6281 .
^ «Информация Microsoft/АНБ» . 17 июня 2000 г. Архивировано из оригинала 17 июня 2000 г. Проверено 12 октября 2016 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )

[hideseek-1] Jump up to: ^а ^б Шамир, Ади; ван Сомерен, Нико (1 января 1998 г.). Игра в прятки с сохраненными ключами . Конспекты лекций по информатике. стр. 118–124. CiteSeerX 10.1.1.40.4467 .

[2] Халдерман, Дж. Алекс; Шон, Сет Д.; Хенингер, Надя ; Кларксон, Уильям; Пол, Уильям; Кэл, Джозеф А.; Фельдман, Ариэль Дж.; Фельтен, Эдвард В. (1 января 2008 г.). «Меньше всего мы помним: атаки с холодной загрузкой на ключи шифрования» . На симпозиуме по безопасности USENIX .

[3] Хенингер, Надя ; Шахам, Ховав (1 января 2009 г.). «Восстановление закрытых ключей rsa из случайных битов ключа». Труды Крипто 2009 . стр. 1–17. CiteSeerX 10.1.1.215.6281 .

[4] «Информация Microsoft/АНБ» . 17 июня 2000 г. Архивировано из оригинала 17 июня 2000 г. Проверено 12 октября 2016 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )

[1]

[2]

[3]

[4]