WikiSort.ru - Не сортированное

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

Эта атака представляет собой особый тип общей криптоаналитической атаки компромисса времени и памяти.

История

«Компромиссные» атаки на симметричные криптосистемы начались в 1980 году, когда Хеллман предложил метод компромисса времени и памяти^[1].

В 1980 году Хеллман представил метод компромиссной атаки времени и памяти (TMTO) на блочные шифры. В более общем виде её можно рассматривать как одностороннюю функцию-инвертор. Оригинальная работа Хеллмана рассматривалась как инвертирующая односторонняя функция f в одной точке^[1].

Бэббидж и Голич показали, что в контексте потоковых шифров несколько точек могут быть использованы другой компромиссной атакой, опираясь на парадокс дня рождения. Однако компромиссные атаки, основанные на парадоксе дня рождения также имеют проблемы: им не хватает гибкости из-за сильной связи сложности памяти со сложностью данных, что обычно приводит к нереалистичным данным или требованиям к памяти^[2][3].

Позднее Бирюков и Шамир показали, что некоторые данные могут быть объединены с компромиссом Хеллмана, что приводит к гибкой формуле компромисса времени / памяти / данных^[4].

Механика атаки

Эта атака является особым типом общей криптоаналитической атаки компромисса времени / памяти. Общая атака компромисса между временем и памятью состоит из двух основных фаз:

1. Предварительная обработка: На этом этапе злоумышленник исследует структуру криптосистемы и может записывать свои результаты в большие таблицы. Это может занять много времени.
2. Реальное время: На этом этапе криптоаналитику предоставляются реальные данные, полученные из определённого неизвестного ключа. Он или она пытается использовать предварительно вычисленную таблицу из фазы предварительной обработки, чтобы найти конкретный в как можно меньше времени.

Любая атака компромисса времени/памяти/данных имеет следующие параметры:

• ${\displaystyle N}$  — размер пространства поиска
• ${\displaystyle P}$  — время, необходимое для фазы предварительной обработки
• ${\displaystyle T}$  — время, необходимое для фазы реального времени
• ${\displaystyle M}$  — объём памяти, доступной злоумышленнику
• ${\displaystyle D}$  — объём данных в реальном времени, доступных злоумышленнику

В этом разделе не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 19 декабря 2018 года.

Хеллмановская компромиссная атака на блочные шифры

Для блочных шифров ${\displaystyle N}$  — это общее количество возможных ключей. Также, предполагается, что число возможных открытых текстов и шифротекстов равно ${\displaystyle N}$ . Также предположим что данные это единственный зашифрованный блок определённого аналога открытого текста.

Если рассмотреть маппинг ключа ${\displaystyle x}$ на зашифрованный текст ${\displaystyle y}$ как функцию случайной перестановки ${\displaystyle f}$ над точечным пространством ${\displaystyle N}$ , и если эта функция ${\displaystyle f}$ обратима; необходимо найти обратное этой функции ${\displaystyle {f}^{-1}(y)=x}$ . Метод Хеллмана, чтобы инвертировать эту функцию заключается в следующем^[1]:

• На этапе предварительной обработки: Покроем пространство точек ${\displaystyle N}$ прямоугольной матрицей ${\displaystyle m\times t}$ , которая создается путем итерации функции ${\displaystyle f}$ в ${\displaystyle m}$ случайных начальных точках в пространстве ${\displaystyle N}$ , и происходит это ${\displaystyle t}$ раз. Начальные точки — самый левый столбец в матрице, а конечные точки — самый правый столбец. Затем сохраняются пары начальной и конечной точек в порядке возрастания значений конечных точек.

  

Теперь только одна матрица не сможет покрыть все пространство ${\displaystyle N}$ . Но если добавить больше строк в матрицу, мы получим огромную матрицу, которая будет содержать восстановленные точки более одного раза.

Таким образом, находится критическое значение ${\displaystyle m}$ , при котором матрица содержит ровно ${\displaystyle m}$ разных точек.

Рассмотрим первые ${\displaystyle m}$ путей от начальных точек до конечных точек, которые не пересекаются с точками ${\displaystyle mt}$ , так что следующий путь, который имеет хотя бы одну общую точку с одним из этих предыдущих путей и включает в себя ровно ${\displaystyle t}$ точек.

Эти два набора точек ${\displaystyle mt}$ и ${\displaystyle t}$ не пересекаются (исходя из парадокса дня рождения), если мы убедимся, что ${\displaystyle t\cdot mt\leq N}$ . Мы достигаем этого, применяя правило остановки матрицы: ${\displaystyle m{t}^{2}=N}$ .

Тем не менее, матрица ${\displaystyle m\times t}$ с ${\displaystyle m{t}^{2}=N}$ покрывает часть ${\displaystyle mt/N=1/t}$ всего пространства.

Чтобы сгенерировать ${\displaystyle t}$ для покрытия всего пространства, мы используем определённый вариант ${\displaystyle f}$ : ${\displaystyle {f}_{i}(x)={h}_{i}(f(x))}$ и ${\displaystyle {h}_{i}}$ , что выполняется простыми манипуляциями, такими как переупорядочение битов ${\displaystyle f(x)}$ ^[1]. И исходя из этого, общее время предварительной обработки составляет ${\displaystyle P\approx N}$ .

Также ${\displaystyle M=mt}$ , так как нам нужно хранить только пары начальных и конечных точек, и у нас есть матрицы ${\displaystyle t}$ , каждая из пар ${\displaystyle m}$ .

• В режиме реального времени Общее вычисление, необходимое для нахождения ${\displaystyle f^{-1}(y)}$ , равно ${\displaystyle T=t^{2}}$ , потому что нам нужно сделать ${\displaystyle t}$ попыток инверсии, так как оно может быть покрыто на одну матрицу, и каждая попытка занимает ${\displaystyle t}$ оценки некоторого ${\displaystyle f_{i}}$ . Оптимальная кривая компромисса получается с помощью правила остановки матрицы ${\displaystyle m{t}^{2}=N}$ , и мы получаем ${\displaystyle T{M^{2}}={N^{2}},P=N,D=1}$ , и выбор ${\displaystyle T}$ и ${\displaystyle M}$ зависит от стоимости каждого ресурса.

Согласно Хеллману, если блочный шифр обладает таким свойством, что маппинг его ключа на зашифрованный текст является функцией случайной перестановки ${\displaystyle f}$ над точечным пространством ${\displaystyle N}$ , и если эта ${\displaystyle f}$ является обратимой, компромиссные соотношения становятся намного лучше: ${\displaystyle TM=N}$ ^[1].

Атаки Бэббэйджа и Голича на потоковые шифры

Для потоковых шифров ${\displaystyle N}$ определяется числом внутренних состояний генератора битов — вероятно, отличается от количества ключей.

${\displaystyle D}$  — это число первых псевдослучайных битов, генерируемых генератором.

Наконец, цель злоумышленника состоит в том, чтобы найти одно из фактических внутренних состояний генератора битов, чтобы иметь возможность запустить генератор с этого момента для генерации остальной части ключа. Связывается каждое из возможных внутренних состояний ${\displaystyle N}$ генератора битов с соответствующей строкой, состоящей из первых битов ${\displaystyle log(N)}$ , полученных при запуске генератора из этого состояния с помощью отображения ${\displaystyle f(x)=y}$ из состояний ${\displaystyle x}$ к префиксам ${\displaystyle y}$ ^[2].

Это отображение считается случайной функцией в общем пространстве точек ${\displaystyle N}$ . Чтобы инвертировать эту функцию, злоумышленник выполняет следующее^[2]:

1. На этапе предварительной обработки выбераются ${\displaystyle M}$ случайных состояний ${\displaystyle {x}_{i}}$ и вычисляются их соответствующие выходные префиксы ${\displaystyle {y}_{i}}$
2. Сохраняются пары ${\displaystyle ({x}_{i},{y}_{i})}$ в порядке возрастания ${\displaystyle {y}_{i}}$ в большой таблице.
3. На этапе реального времени есть ${\displaystyle D+log(N)-1}$ сгенерированных битов. Рассчитываются из них все ${\displaystyle D}$ возможных комбинаций ${\displaystyle {y}_{1},{y}_{2},...,{y}_{D},}$ последовательных битов с длиной ${\displaystyle log(N)}$ .
4. Находится каждый ${\displaystyle {y}_{i}}$ в сгенерированной таблице, который занимает время журнала.
5. Если есть попадание, этот ${\displaystyle {y}_{i}}$ соответствует внутреннему состоянию ${\displaystyle {x}_{i}}$ генератора битов, из которого можно перезапустить генератор, чтобы получить остаток ключа.
6. Парадоксом дня рождения гарантируется, что два подмножества пространства с точками ${\displaystyle N}$ имеют пересечение, если произведение их размеров больше, чем ${\displaystyle N}$ .

Этот результат атаки «дней рождения» дает условие ${\displaystyle DM=N}$ со временем атаки ${\displaystyle T=D}$ и временем предварительной обработки ${\displaystyle P=M}$ , которое является просто определённой точкой на кривой компромисса ${\displaystyle TM=N}$ ^[2].

Можно обобщить это соотношение, если проигнорировать некоторые из доступных данных в режиме реального времени и получится уменьшить ${\displaystyle T}$ с ${\displaystyle T=D}$ до ${\displaystyle 1}$ , и общая кривая компромисса в конечном итоге станет ${\displaystyle TM=N}$ с ${\displaystyle 1\leq T\leq D}$ и ${\displaystyle P=M}$ ^[2].

Атака компромисса между временем/памятью/данными, разработанная Шамиром и Бирюковым на потоковые шифры

Эта новая идея^[4], представленная в 2000 году, сочетает в себе оба метода: компромисс Хеллмана^[1] и атаки компромисса Бэббиджа и Голича^[3][2], чтобы получить новую кривую компромисса с улучшенными границами для криптоанализа потоковых шифров^[4].

Можно применить технику блочного шифра Хеллмана к потоковому шифру, используя ту же идею покрытия пространства точек ${\displaystyle N}$ через матрицы, полученные из нескольких вариантов ${\displaystyle f_{i}}$ функции ${\displaystyle f}$ , которая является отображением внутренних состояний на выходные префиксы^[4].

Эта компромиссная атака на потоковый шифр успешна, если какой-либо из заданных выходных префиксов ${\displaystyle D}$ найден в любой из матриц, покрывающих ${\displaystyle N}$ . Следовательно, можно сократить количество покрываемых точек матрицами от точек ${\displaystyle N}$ до ${\displaystyle N/D}$ . Это достигается путем уменьшения количества матриц с ${\displaystyle t}$ до ${\displaystyle t/D}$ при сохранении максимально возможного размера ${\displaystyle m}$ (но для этого требуется, чтобы ${\displaystyle t\geq D}$ имел по крайней мере одну таблицу)^[4].

Для этой новой атаки ${\displaystyle M=mt/D}$ , так как уменьшилось количество матриц до ${\displaystyle t/D}$ и то же самое — для времени предварительной обработки ${\displaystyle P=N/D}$ . В реальном времени для атаки требуется ${\displaystyle T=(t/D)\cdot t\cdot D=t^{2}}$ , что представляет собой произведение количества матриц, длины каждой итерации и количества доступных точек данных во время атаки^[4].

В конце концов, снова используется правило остановки матрицы для получения кривой компромисса ${\displaystyle TM^{2}D^{2}=t^{2}\cdot (m^{2}t^{2}/D^{2})\cdot D^{2}=m^{2}t^{4}=N^{2}}$ для ${\displaystyle D^{2}\leq T\leq N}$ (потому что ${\displaystyle t\geq D}$ )^[4].

Компромиссные атаки на потоковые шифры с низким сопротивлением выборки

Эту атаку изобрели Бирюков, Шамир, Вагнер^[5].

Идея опирается на следующую особенность различных потоковых шифров: генератор битов претерпевает лишь несколько изменений во внутреннем состоянии перед созданием следующего выходного бита. Следовательно, можно перечислить те состояния, которые генерируют ${\displaystyle k}$ нулевых битов для небольших значений ${\displaystyle k}$ при низких затратах^[5].

Но, когда большое количество выходных битов принимает конкретные значения, этот процесс перечисления становится очень дорогим и сложным. Теперь можно определить сопротивление выборки потокового шифра как ${\displaystyle R=2^{-k}}$ с максимальным значением ${\displaystyle k}$ , которое делает возможным такое перечисление^[5].

Пусть потоковый шифр имеет состояния ${\displaystyle N=2^{n}}$ , каждое из которых имеет полное имя ${\displaystyle n}$ битов и соответствующее имя выхода, которые являются первыми ${\displaystyle n}$ битами в выходной последовательности битов. Если этот потоковый шифр имеет сопротивление выборки ${\displaystyle R=2^{-k}}$ , то эффективное перечисление может использовать короткое имя из ${\displaystyle n-k}$ битов для определения определённых состояний генератора^[5].

Каждое состояние с коротким именем ${\displaystyle n-k}$ имеет соответствующее короткое имя вывода из ${\displaystyle n-k}$ битов, которое является выходной последовательностью состояния после удаления первых начальных битов ${\displaystyle k}$ . Теперь возможно определить новое отображение по уменьшенному пространству точек ${\displaystyle NR=2^{n-k}}$ , и это отображение эквивалентно исходному отображению^[5].

Если ${\displaystyle DR\geq 1}$ , данные в реальном времени, доступные злоумышленнику, гарантированно получится по крайней мере один выход из этих состояний. В противном случае, необходимо ослабить определение состояний, чтобы включить больше точек^[5].

Если заменить ${\displaystyle D}$ на ${\displaystyle DR}$ и ${\displaystyle N}$ на ${\displaystyle NR}$ в новой атаке на обмен времени / памяти / данных Шамира и Бирюкова, получится такая ​​же кривая компромисса ${\displaystyle TM^{2}D^{2}=N^{2}}$ , но с ${\displaystyle (DR)^{2}\leq T\leq NR}$ ^[5].

Это на самом деле улучшение, так как возможно было бы ослабить нижнюю границу ${\displaystyle T}$ , поскольку ${\displaystyle (DR)^{2}}$ может быть небольшим до ${\displaystyle 1}$ , что означает, что атака может быть выполнена быстрее^[5].

Ещё одно преимущество этого метода заключается в том, что сократилось количество дорогостоящих операций доступа к диску с ${\displaystyle t}$ до ${\displaystyle tR}$ , поскольку будет запрашиваться доступ только к специальным точкам ${\displaystyle DR}$ . И это также может значительно ускорить атаку из-за уменьшения количества дорогостоящих дисковых операций^[5].

Пример атаки на схему паролей в Unix-системах

Атаки, описанные в этой статье, не ограничиваются блочными или потоковыми шифрами, они применимы к другим односторонним конструкциям, например, к хеш-функциям^[6].

Компромисс времени / памяти / данных можно использовать для анализа паролей Unix, например, если злоумышленник получает доступ к хранилищу файлов хешей паролей крупной организации (D = 1000 хэшей паролей)^[6].

В самом деле, пространство компромисса состоит из 56 битов неизвестного ключа (то есть пароля) и 12 бит известной соли. Поскольку размер соли намного короче размера ключа, его эффект от усложнения компромисса не очень значителен^[6].

Предположим, что злоумышленник знает, что пароли выбираются из набора произвольных 8-символьных буквенно-цифровых паролей, включая заглавные буквы и два дополнительных символа как точка и запятая, которые в сумме могут быть закодированы в 48 бит. Таким образом, вместе с 12-битной солью состояние N = 260 бит^[6].

Например, параметры следующей атаки кажутся довольно практичными: время предварительной обработки выполняется один раз: P = N / D = 250 Unix хеш-вычисления, распараллеливаемые. Память M = 234 8-байтовых записей (12 + 48 бит), занимает один жесткий диск 128 ГБ. Таким образом, мы храним 234 стартовых указателей. Тогда время атаки равно T = 232 оценкам Unix-хеша — примерно час на быстром ПК или около 8 секунд на BEE2 FPGA^[7].

Атака будет восстанавливать один пароль из каждых 1000 новых хэшей паролей. Относительно длительный этап предварительной обработки может выполняться параллельно в сети ПК (на сотню ПК может уйти меньше месяца) или около 1,5 месяцев для одной BEE2 FPGA. Количество таблиц рассчитывается параллельно и может достигать t / D = 217/1000 = 27^[7].

Чтобы уменьшить количество запросов к жесткому диску, атака должна будет использовать отличительные точки с 16-битным префиксами. Это позволит сделать только 216 обращений к диску (что меньше 6 минут)^[7].

На самом деле ясно, что такой компромисс может проанализировать все пароли, набираемые на клавиатуре. Пространство N = 848 · 212 = 263. Предполагая снова D = 210, мы получаем время предварительного вычисления P = 253, M = 235 8-байтовых записей или один жесткий диск 256 ГБ, Т = 236 оценок хешей^[7].

Примечания