Атака компромисса между временем/памятью/данными — тип криптографической атаки, при которой злоумышленник пытается достичь ситуации, аналогичной компромиссу времени и памяти, но с ещё одним параметром: объём данных, доступных злоумышленнику в режиме реального времени. Атакующий балансирует или уменьшает один или два из этих параметров в пользу другого или двух. Этот тип атаки очень сложен, и большинство шифров и схем шифрования не были разработаны, чтобы противостоять такому типу атак.
Эта атака представляет собой особый тип общей криптоаналитической атаки компромисса времени и памяти.
«Компромиссные» атаки на симметричные криптосистемы начались в 1980 году, когда Хеллман предложил метод компромисса времени и памяти[1].
В 1980 году Хеллман представил метод компромиссной атаки времени и памяти (TMTO) на блочные шифры. В более общем виде её можно рассматривать как одностороннюю функцию-инвертор. Оригинальная работа Хеллмана рассматривалась как инвертирующая односторонняя функция f в одной точке[1].
Бэббидж и Голич показали, что в контексте потоковых шифров несколько точек могут быть использованы другой компромиссной атакой, опираясь на парадокс дня рождения. Однако компромиссные атаки, основанные на парадоксе дня рождения также имеют проблемы: им не хватает гибкости из-за сильной связи сложности памяти со сложностью данных, что обычно приводит к нереалистичным данным или требованиям к памяти[2][3].
Позднее Бирюков и Шамир показали, что некоторые данные могут быть объединены с компромиссом Хеллмана, что приводит к гибкой формуле компромисса времени / памяти / данных[4].
Механика атаки
Эта атака является особым типом общей криптоаналитической атаки компромисса времени / памяти. Общая атака компромисса между временем и памятью состоит из двух основных фаз:
Предварительная обработка: На этом этапе злоумышленник исследует структуру криптосистемы и может записывать свои результаты в большие таблицы. Это может занять много времени.
Реальное время: На этом этапе криптоаналитику предоставляются реальные данные, полученные из определённого неизвестного ключа. Он или она пытается использовать предварительно вычисленную таблицу из фазы предварительной обработки, чтобы найти конкретный в как можно меньше времени.
Любая атака компромисса времени/памяти/данных имеет следующие параметры[5]:
<math>N</math> — размер пространства поиска
<math>P</math> — время, необходимое для фазы предварительной обработки
<math>T</math> — время, необходимое для фазы реального времени
<math>M</math> — объём памяти, доступной злоумышленнику
<math>D</math> — объём данных в реальном времени, доступных злоумышленнику
Для блочных шифров <math>N</math> — это общее количество возможных ключей. Также, предполагается, что число возможных открытых текстов и шифротекстов равно <math>N</math>. Также предположим что данные это единственный зашифрованный блок определённого аналога открытого текста.
Если рассмотреть маппинг ключа <math>x</math> на зашифрованный текст <math>y</math> как функцию случайной перестановки <math>f</math> над точечным пространством <math>N</math>, и если эта функция <math>f</math> обратима; необходимо найти обратное этой функции <math>{f}^{-1}(y)=x</math>. Метод Хеллмана, чтобы инвертировать эту функцию заключается в следующем[1]:
На этапе предварительной обработки: Покроем пространство точек <math>N</math> прямоугольной матрицей <math>m \times t</math>, которая создаётся путём итерации функции <math>f</math> в <math>m</math> случайных начальных точках в пространстве <math>N</math>, и происходит это <math>t</math> раз. Начальные точки — самый левый столбец в матрице, а конечные точки — самый правый столбец. Затем сохраняются пары начальной и конечной точек в порядке возрастания значений конечных точек.Hellman's MatrixHellman's Matrix
Теперь только одна матрица не сможет покрыть все пространство <math>N</math>. Но если добавить больше строк в матрицу, мы получим огромную матрицу, которая будет содержать восстановленные точки более одного раза.
Таким образом, находится критическое значение <math>m</math>, при котором матрица содержит ровно <math>m</math> разных точек.
Рассмотрим первые <math>m</math> путей от начальных точек до конечных точек, которые не пересекаются с точками <math>mt</math>, так что следующий путь, который имеет хотя бы одну общую точку с одним из этих предыдущих путей и включает в себя ровно <math>t</math> точек.
Эти два набора точек <math>mt</math> и <math>t</math> не пересекаются (исходя из парадокса дня рождения), если мы убедимся, что <math>t \sdot mt \leq N</math>. Мы достигаем этого, применяя правило остановки матрицы: <math>m{t}^2=N</math>.
Тем не менее, матрица <math>m \times t</math> с <math>m{t}^2=N</math> покрывает часть <math>mt/N=1/t</math> всего пространства.
Чтобы сгенерировать <math>t</math> для покрытия всего пространства, мы используем определённый вариант <math>f</math>: <math>{f}_{i}(x)={h}_{i}(f(x))</math> и <math>{h}_{i}</math>, что выполняется простыми манипуляциями, такими как переупорядочение битов <math>f(x)</math>[1]. И исходя из этого, общее время предварительной обработки составляет <math>P \approx N</math>.
Также <math>M=mt</math>, так как нам нужно хранить только пары начальных и конечных точек, и у нас есть матрицы <math>t</math>, каждая из пар <math>m</math>.
В режиме реального времени Общее вычисление, необходимое для нахождения <math>f^{-1}(y)</math>, равно <math>T=t^{2}</math>, потому что нам нужно сделать <math>t</math> попыток инверсии, так как оно может быть покрыто на одну матрицу, и каждая попытка занимает <math>t</math> оценки некоторого <math>f_{i}</math>. Оптимальная кривая компромисса получается с помощью правила остановки матрицы <math>m{t}^2=N</math>, и мы получаем <math>T{M^2}={N^2}, P=N, D=1</math>, и выбор <math>T</math> и <math>M</math> зависит от стоимости каждого ресурса.
Согласно Хеллману, если блочный шифр обладает таким свойством, что маппинг его ключа на зашифрованный текст является функцией случайной перестановки <math>f</math> над точечным пространством <math>N</math>, и если эта <math>f</math> является обратимой, компромиссные соотношения становятся намного лучше: <math>TM=N</math>[1].
Атаки Бэббиджа и Голича на потоковые шифры
Для потоковых шифров <math>N</math> определяется числом внутренних состояний генератора битов — вероятно, отличается от количества ключей.
<math>D</math> — это число первых псевдослучайных битов, генерируемых генератором.
Наконец, цель злоумышленника состоит в том, чтобы найти одно из фактических внутренних состояний генератора битов, чтобы иметь возможность запустить генератор с этого момента для генерации остальной части ключа. Связывается каждое из возможных внутренних состояний <math>N</math> генератора битов с соответствующей строкой, состоящей из первых битов <math>log(N)</math>, полученных при запуске генератора из этого состояния с помощью отображения <math>f(x)=y</math> из состояний <math>x</math> к префиксам <math>y</math>[2].
Это отображение считается случайной функцией в общем пространстве точек <math>N</math>. Чтобы инвертировать эту функцию, злоумышленник выполняет следующее[2]:
На этапе предварительной обработки выбираются <math>M</math> случайных состояний <math>{x}_i</math> и вычисляются их соответствующие выходные префиксы <math>{y}_i</math>
Сохраняются пары <math>({x}_i,{y}_i)</math> в порядке возрастания <math>{y}_i</math> в большой таблице.
На этапе реального времени есть <math>D+log(N)-1</math>сгенерированных битов. Рассчитываются из них все <math>D</math> возможных комбинаций <math>{y}_1,{y}_2,...,{y}_D,</math> последовательных битов с длиной <math>log(N)</math>.
Находится каждый <math>{y}_i</math> в сгенерированной таблице, который занимает время журнала.
Если есть попадание, этот <math>{y}_i</math> соответствует внутреннему состоянию <math>{x}_i</math> генератора битов, из которого можно перезапустить генератор, чтобы получить остаток ключа.
Парадоксом дня рождения гарантируется, что два подмножества пространства с точками <math>N</math> имеют пересечение, если произведение их размеров больше, чем <math>N</math>.
Этот результат атаки «дней рождения» даёт условие <math>DM=N</math> со временем атаки <math>T=D</math> и временем предварительной обработки <math>P=M</math>, которое является просто определённой точкой на кривой компромисса <math>TM=N</math>[2].
Можно обобщить это соотношение, если проигнорировать некоторые из доступных данных в режиме реального времени и получится уменьшить <math>T</math> с <math>T=D</math> до <math>1</math>, и общая кривая компромисса в конечном итоге станет <math>TM=N</math>с <math>1 \leq T \leq D</math> и <math>P=M</math>[2].
Эта новая идея[4], представленная в 2000 году, сочетает в себе оба метода: компромисс Хеллмана[1] и атаки компромисса Бэббиджа и Голича[2][3], чтобы получить новую кривую компромисса с улучшенными границами для криптоанализа потоковых шифров[4].
Можно применить технику блочного шифра Хеллмана к потоковому шифру, используя ту же идею покрытия пространства точек <math>N</math> через матрицы, полученные из нескольких вариантов <math>f_{i}</math> функции <math>f</math>, которая является отображением внутренних состояний на выходные префиксы[4].
Эта компромиссная атака на потоковый шифр успешна, если какой-либо из заданных выходных префиксов <math>D</math> найден в любой из матриц, покрывающих <math>N</math>. Следовательно, можно сократить количество покрываемых точек матрицами от точек <math>N</math> до <math>N/D</math>. Это достигается путём уменьшения количества матриц с <math>t</math> до <math>t/D</math> при сохранении максимально возможного размера <math>m</math> (но для этого требуется, чтобы <math>t \geq D</math>имел по крайней мере одну таблицу)[4].
Для этой новой атаки <math>M=mt/D</math>, так как уменьшилось количество матриц до <math>t/D</math>и то же самое — для времени предварительной обработки <math>P=N/D</math>. В реальном времени для атаки требуется <math>T=(t/D) \sdot t \sdot D=t^{2}</math>, что представляет собой произведение количества матриц, длины каждой итерации и количества доступных точек данных во время атаки[4].
В конце концов, снова используется правило остановки матрицы для получения кривой компромисса <math>TM^{2}D^{2}=t^{2}\sdot (m^{2}t^{2}/D^{2})\sdot D^{2}=m^{2}t^{4}=N^{2}</math> для <math>D^{2}\leq T\leq N</math> (потому что <math>t\geq D</math>)[4].
Компромиссные атаки на потоковые шифры с низким сопротивлением выборки
Идея опирается на следующую особенность различных потоковых шифров: генератор битов претерпевает лишь несколько изменений во внутреннем состоянии перед созданием следующего выходного бита. Следовательно, можно перечислить те состояния, которые генерируют <math>k</math> нулевых битов для небольших значений <math>k</math> при низких затратах[6].
Но, когда большое количество выходных битов принимает конкретные значения, этот процесс перечисления становится очень дорогим и сложным. Теперь можно определить сопротивление выборки потокового шифра как <math>R=2^{-k}</math>с максимальным значением <math>k</math>, которое делает возможным такое перечисление[6].
Пусть потоковый шифр имеет состояния <math>N=2^{n}</math>, каждое из которых имеет полное имя <math>n</math> битов и соответствующее имя выхода, которые являются первыми <math>n</math> битами в выходной последовательности битов. Если этот потоковый шифр имеет сопротивление выборки <math>R=2^{-k}</math>, то эффективное перечисление может использовать короткое имя из <math>n-k</math> битов для определения определённых состояний генератора[6].
Каждое состояние с коротким именем <math>n-k</math> имеет соответствующее короткое имя вывода из <math>n-k</math> битов, которое является выходной последовательностью состояния после удаления первых начальных битов <math>k</math>. Теперь возможно определить новое отображение по уменьшенному пространству точек <math>NR=2^{n-k}</math>, и это отображение эквивалентно исходному отображению[6].
Если <math>DR\geq 1</math>, данные в реальном времени, доступные злоумышленнику, гарантированно получится по крайней мере один выход из этих состояний. В противном случае, необходимо ослабить определение состояний, чтобы включить больше точек[6].
Если заменить <math>D</math> на <math>DR</math> и <math>N</math> на <math>NR</math> в новой атаке на обмен времени / памяти / данных Шамира и Бирюкова, получится такая же кривая компромисса <math>TM^{2}D^{2}=N^{2}</math>, но с <math>(DR)^{2}\leq T\leq NR</math>[6].
Это на самом деле улучшение, так как возможно было бы ослабить нижнюю границу <math>T</math>, поскольку <math>(DR)^{2}</math> может быть небольшим до <math>1</math>, что означает, что атака может быть выполнена быстрее[6].
Ещё одно преимущество этого метода заключается в том, что сократилось количество дорогостоящих операций доступа к диску с <math>t</math> до <math>tR</math>, поскольку будет запрашиваться доступ только к специальным точкам <math>DR</math>. И это также может значительно ускорить атаку из-за уменьшения количества дорогостоящих дисковых операций[6].
Атаки, описанные в этой статье, не ограничиваются блочными или потоковыми шифрами, они применимы к другим односторонним конструкциям, например, к хеш-функциям[7].
Компромисс времени / памяти / данных можно использовать для анализа паролей Unix, например, если злоумышленник получает доступ к хранилищу файлов хешей паролей крупной организации (D = 1000 хэшей паролей)[7].
В самом деле, пространство компромисса состоит из 56 битов неизвестного ключа (то есть пароля) и 12 бит известной соли. Поскольку размер соли намного короче размера ключа, его эффект от усложнения компромисса не очень значителен[7].
Предположим, что злоумышленник знает, что пароли выбираются из набора произвольных 8-символьных буквенно-цифровых паролей, включая заглавные буквы и два дополнительных символа как точка и запятая, которые в сумме могут быть закодированы в 48 бит. Таким образом, вместе с 12-битной солью состояние N = 260 бит[7].
Например, параметры следующей атаки кажутся довольно практичными: время предварительной обработки выполняется один раз: P = N / D = 250 Unix хеш-вычисления, распараллеливаемые. Память M = 234 8-байтовых записей (12 + 48 бит), занимает один жёсткий диск размером 128 ГБ. Таким образом, мы храним 234 стартовых указателей. Тогда время атаки равно T = 232 оценкам Unix-хеша — примерно час на быстром ПК или около 8 секунд на BEE2 FPGA[8].
Атака будет восстанавливать один пароль из каждых 1000 новых хэшей паролей. Относительно длительный этап предварительной обработки может выполняться параллельно в сети ПК (на сотню ПК может уйти меньше месяца) или около 1,5 месяцев для одной BEE2 FPGA. Количество таблиц рассчитывается параллельно и может достигать t / D = 217/1000 = 27[8].
Чтобы уменьшить количество запросов к жёсткому диску, атака должна будет использовать отличительные точки с 16-битным префиксами. Это позволит сделать только 216 обращений к диску (что меньше 6 минут)[8].
На самом деле ясно, что такой компромисс может проанализировать все пароли, набираемые на клавиатуре. Пространство N = 848 · 212 = 263. Предполагая снова D = 210, мы получаем время предварительного вычисления P = 253, M = 235 8-байтовых записей или один жёсткий диск размером 256 ГБ, Т = 236 оценок хешей[8].
