Атака компромисса между временем/памятью/данными

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

История

"Компромиссные" атаки на симметричные криптосистемы начались в 1980 году, когда Хеллман предложил метод компромисса времени и памяти, В 1980 году Хеллман представил метод компромиссной атаки времени и памяти (TMTO) на блочные шифры. В более общем виде её можно рассматривать как одностороннюю функцию-инвертор. Оригинальная работа Хеллмана рассматривалась как инвертирующая односторонняя функция f в одной точке. Чтобы взломать блочные шифры с $N$возможными ключами времени $T$ и памяти $M$, связанными с кривой компромисса $T{M^{2}}={N^{2}}$, где $1\leq T\leq N$. Бэббидж и Голич показали, что в контексте потоковых шифров несколько точек могут быть использованы другой компромиссной атакой, опираясь на парадокс дня рождения. Однако компромиссные атаки, основанные на парадоксе дня рождения также имеют проблемы: им не хватает гибкости из-за сильной связи сложности памяти со сложностью данных, что обычно приводит к нереалистичным данным или требованиям к памяти. Позднее Бирюков и Шамир показали, что некоторые данные могут быть объединены с компромиссом Хеллмана, что приводит к гибкой формуле компромисса времени / памяти / данных.

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

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

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

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

$N$ размер пространства поиска

$P$ время, необходимое для фазы предварительной обработки

$T$ время, необходимое для фазы реального времени

$M$ объем памяти, доступной злоумышленнику

$D$ объем данных в реальном времени, доступных злоумышленнику

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

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

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

  

  Hellman's Matrix

Теперь только одна матрица не сможет покрыть все пространство $N$. Но если мы добавим больше строк в матрицу, мы получим огромную матрицу, которая будет содержать восстановленные точки более одного раза. Таким образом, мы находим критическое значение $m$, при котором матрица содержит ровно $m$ разных точек. Рассмотрим первые $m$путей от начальных точек до конечных точек, которые не пересекаются с точками $mt$, так что следующий путь, который имеет хотя бы одну общую точку с одним из этих предыдущих путей и включает в себя ровно $t$точек. Эти два набора точек $mt$ и $t$ не пересекаются (исходя из парадокса дня рождения), если мы убедимся, что $t\cdot mt\leq N$. Мы достигаем этого, применяя правило остановки матрицы: $m{t}^{2}=N$. Тем не менее, матрица $m\times t$ с $m{t}^{2}=N$ покрывает часть $mt/N=1/t$ всего пространства. Чтобы сгенерировать $t$ для покрытия всего пространства, мы используем определенный вариант $f$: ${f}_{i}(x)={h}_{i}(f(x))$и ${h}_{i}$, что является простыми манипуляциями, такими как переупорядочение битов $f(x)$ . И можно увидеть, что общее время предварительной обработки составляет $P\approx N$. Также $M=mt$, так как нам нужно хранить только пары начальных и конечных точек, и у нас есть матрицы $t$, каждая из пар $m$.

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

According to Hellman, if the block cipher at hand has the property that the mapping from its key to cipher text is a random permutation function $f$ over an $N$ point space, and if this $f$ is invertible, the tradeoff relationship becomes ways better: $TM=N$.

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

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

Для потоковых шифров $N$ определяется числом внутренних состояний генератора битов - вероятно, отличается от количества ключей. $D$ - это число первых псевдослучайных битов, генерируемых генератором. Наконец, цель злоумышленника состоит в том, чтобы найти одно из фактических внутренних состояний генератора битов, чтобы иметь возможность запустить генератор с этого момента для генерации остальной части ключа. Свяжите каждое из возможных внутренних состояний $N$ генератора битов с соответствующей строкой, состоящей из первых битов $log(N)$, полученных при запуске генератора из этого состояния с помощью отображения $f(x)=y$ из состояний $x$ к префиксам $y$. Это отображение считается случайной функцией в общем пространстве точек $N$. Чтобы инвертировать эту функцию, злоумышленник выполняет следующее:

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

Этот результат атаки «дней рождения» дает условие $DM=N$ со временем атаки $T=D$ и временем предварительной обработки $P=M$, которое является просто определенной точкой на кривой компромисса $TM=N$. Мы можем обобщить это соотношение, если проигнорируем некоторые из доступных данных в режиме реального времени и сможем уменьшить $T$ с $T=D$ до $1$, и общая кривая компромисса в конечном итоге станет $TM=N$с $1\leq T\leq D$ и $P=M$.

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

Эта новая идея, представленная в 2000 году, сочетает в себе оба метода: компромисс Хеллмана и атаки компромисса Бэббиджа и Голича, чтобы получить новую кривую компромисса с лучшими границами для криптоанализа потоковых шифров. Можно применить технику блочного шифра Хеллмана к потоковому шифру, используя ту же идею покрытия пространства точек $N$ через матрицы, полученные из нескольких вариантов $f_{i}$ функции $f$, которая является отображением внутренних состояний на выходные префиксы. Напомним, что эта компромиссная атака на потоковый шифр успешна, если какой-либо из заданных выходных префиксов $D$ найден в любой из матриц, покрывающих $N$. Следовательно, мы можем сократить количество покрываемых точек матрицами от точек $N$ до $N/D$. Это достигается путем уменьшения количества матриц с $t$ до $t/D$ при сохранении максимально возможного размера $m$ (но для этого требуется, чтобы $t\geq D$имел по крайней мере одну таблицу). Для этой новой атаки есть $M=mt/D$, потому что уменьшилось количество матриц до $t/D$и то же самое для времени предварительной обработки $P=N/D$. В реальном времени для атаки требуется $T=(t/D)\cdot t\cdot D=t^{2}$, что представляет собой произведение количества матриц, длины каждой итерации и количества доступных точек данных. во время атаки.

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

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

Эту атаку изобрели Бирюков, Шамир, Вагнер. Идея опирается на следующую особенность различных потоковых шифров: генератор битов претерпевает лишь несколько изменений во внутреннем состоянии перед созданием следующего выходного бита. Следовательно, мы можем перечислить те состояния, которые генерируют $k$ нулевых битов для небольших значений $k$ при низких затратах. Но когда большое количество выходных битов принимает конкретные значения, этот процесс перечисления становится очень дорогим и сложным. Теперь мы можем определить сопротивление выборки потокового шифра как $R=2^{-k}$с максимальным значением $k$, которое делает возможным такое перечисление.

Пусть потоковый шифр имеет состояния $N=2^{n}$, каждое из которых имеет полное имя $n$ битов и соответствующее имя выхода, которые являются первыми $n$ битами в выходной последовательности битов. Если этот потоковый шифр имеет сопротивление выборки $R=2^{-k}$, то эффективное перечисление может использовать короткое имя из $n-k$ битов для определения определённых состояний генератора. Каждое состояние с коротким именем $n-k$ имеет соответствующее короткое имя вывода из $n-k$ битов, которое является выходной последовательностью состояния после удаления первых начальных битов $k$. Теперь мы можем определить новое отображение по уменьшенному пространству точек $NR=2^{n-k}$, и это отображение эквивалентно исходному отображению. Если $DR\geq 1$, данные в реальном времени, доступные злоумышленнику, гарантированно получим по крайней мере один выход из этих состояний. В противном случае мы ослабим определение состояний, чтобы включить больше точек. Если мы заменим $D$ на$DR$ и $N$ на $NR$ в новой атаке на обмен времени / памяти / данных Шамира и Бирюкова, мы получим такую ​​же кривую компромисса $TM^{2}D^{2}=N^{2}$, но с $(DR)^{2}\leq T\leq NR$. Это на самом деле улучшение, так как мы могли бы ослабить нижнюю границу $T$, поскольку $(DR)^{2}$ может быть небольшим до $1$, что означает, что наша атака может быть выполнена быстрее. Еще одно преимущество этого метода заключается в том, что мы сократили количество дорогостоящих операций доступа к диску с $t$ до $tR$, поскольку мы будем получать доступ только к специальным точкам $DR$. И это также может значительно ускорить нашу атаку из-за уменьшения количества дорогостоящих дисковых операций.

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

Атаки, описанные в этой статье, не ограничиваются блочными или потоковыми шифрами, они применимы к другим односторонним конструкциям, например, к хеш-функциям. Время / память / обмен данными можно использовать для анализа паролей Unix, например, если злоумышленник получает доступ к хранилищу файлов хешей паролей крупной организации (D = 1000 хэшей паролей). В самом деле, пространство компромисса состоит из 56 битов неизвестного ключа (то есть пароля) и 12 бит известной соли. Поскольку размер соли намного короче размера ключа, его эффект от усложнения компромисса не очень значителен. Предположим, что злоумышленник знает, что пароли выбираются из набора произвольных 8-символьных буквенно-цифровых паролей, включая заглавные буквы и два дополнительных символа как точка и запятая, которые в сумме могут быть закодированы в 48 бит. Таким образом, вместе с 12-битной солью состояние N = 260 бит. Например, параметры следующей атаки кажутся довольно практичными: время предварительной обработки выполняется один раз: P = N / D = 250 Unix хеш-вычисления, распараллеливаемые. Память M = 234 8-байтовых записей (12 + 48 бит), занимает один жесткий диск 128 ГБ. Таким образом, мы храним 234 стартовых указателей. Тогда время атаки равно T = 232 оценкам Unix-хеша - примерно час на быстром ПК или около 8 секунд на BEE2 FPGA . Атака будет восстанавливать один пароль из каждых 1000 новых хэшей паролей. Это на два-три порядка быстрее результатов, описанных в статье. Относительно длительный этап предварительной обработки может выполняться параллельно в сети ПК (на сотню ПК может уйти меньше месяца) или около 1,5 месяцев для одной BEE2 FPGA. Количество таблиц рассчитывается параллельно и может достигать t / D = 217/1000 = 27. Чтобы уменьшить количество запросов к жесткому диску, атака должна будет использовать отличительные точки с 16-битным префиксы. Это позволит сделать только 216 обращений к диску (что меньше 6 минут). На самом деле ясно, что такой компромисс может проанализировать все пароли, набираемые на клавиатуре. Пространство N = 848 · 212 = 263. Предполагая снова D = 210, мы получаем время предварительного вычисления P = 253, M = 235 8-байтовых записей или один жесткий диск 256 ГБ, Т = 236 оценок хешей.