Всем привет! Сейчас как обычно будет много текста и мало картинок.
Многие люди, интересующиеся вопросами безопасности и устойчивостью GSM ко взлому - читали про работы Карстена Нола (инструмент "Kraken"). Данное программное обеспечение используется для расшифровки шифра А5.1 , используемого в телефонии стандарта 2G по сей день.
Обычный уровень знаний про это ПО выглядит примерно так - "Качаем кракен, покупаем 2тб диск, на него записываем таблицы. Подключаем моторолу за 5$ и ломаем жсм. Profit" . Те немногие люди, которые дошли до запуска ПО, и даже модифицировали его (в интернете есть проекты под windows и т.д.) - совершенно не понимают, с чем имеют дело - и обычно задают вопросы из серии - а если 4090 воткнуть, быстрее будет считать - или нет? И это абсолютно нормально, учитывая что публикаций по данной теме очень мало, а на русском языке - вовсе нет.
Сегодня в статье я расскажу подробнее, как же эти таблицы устроены.
Некоторая используемая терминология - возможно, будет не понятной. Поэтому, найдя незнакомое слово -спросите у chatGPT, напишите ниже - постараюсь объяснить.
Для чего все это нужно
Исследователи вопросов информационной безопасности - записывают из эфира шифрованный трафик (обмена данными) телефона с базовой станцией. Из этого трафика получаем гамму - тот набор бит, при помощи которого пакет был зашифрован.
Зная гамму - не составит труда найти ключ сеанса связи, при помощи которого можно расшифровать переговор, SMS или совершить еще какие-либоприбыльные противоправные действия.
Первый этап поиска Кс - необходимо найти внутреннее состояние регистров алгоритма шифрования а5.1. Это можно сделать разными методами, один из них - поиск по большой таблице, в которой присутствуют все варианты "ключей".
Предварительно созданные таблицы состояний генератора А5/1
Существует возможность создать такую таблицу, в которой будет будет сопоставлено состояние регистров шифра A5/1 с некоторым входным значением гаммы.
В механизме шифрования А5.1 есть 3 регистра: длиной 19 бит, 22 бит, 23 бит. Таким образом суммарная длина в 64 бита полностью описывает состояние всех трех регистров, для соответствующей гаммы. Выглядит это примерно так:
Записываем таблицу в следующем виде. Internal state - 64 битный регистр состояния алгоритма А5.1 Keystream - гамма:
Как только мы получаем гамму - выполнив XOR между plaintext и ciphertext (эти данные перехватывают из эфира при помощи моторолы), становится возможным найти такое же значение в таблице и посмотреть соответствующее ему значение 64 битного регистра, описывающего состояние А5.1 в данный момент. Таблицу можно предварительно отсортировать по значениям гаммы и использовать очень эффективный механизм логарифмического поиска.
Все классно - но такая таблица будет очень большой.
2^64 состояний * 8 байт на каждое состояние (т.к. оно 64битное) = 128 Экзабайт.
Эффективное количество используемых бит ключа - только 61 бит. Так как количество вариантов ключа очень большое, могут встречаться варианты что одну и ту же гамму можно получить при помощи разных ключей. Но тем не менее значение все равно очень большое и не существует возможности генерации и хранения столь затратной по занимаемому на диске пространству, таблицы.
Сжатие таблиц
Попробуем сжать "сырую" таблицу состояний при помощи создания цепочек. Мы берем некоторое начальное состояние 64 битного регистра и используем его в качестве входных данных для алгоритма А5.1. Результат работы а5.1 - не сохраняем, и снова подаем на вход шифратора а5.1. Этот цикл повторяем до тех пор, пока не достигнем некоторого особенного результата, называемого особенной точкой ( DP ). Давайте будем считать что DP это такое значение регистра, в которым 12 младших бит - равны нулю.
Таким образом получается средняя длина цепочки в 2^12 = 4096 бит, то есть эффект сжатия составит примерно 1:4096.
Как только, в результате записи радиообмена - мы получаем некоторое значение гаммы, пригодное для взлома - можем использовать ее в качестве входного значения для генератора цепочки, и выполнять алгоритм до тех пор пока не достигнем особенную точку DP. После чего выполним обратный поиск этой точки в таблице. Так мы находим "ветвь" таблицы, в которой находится данное состояние - после чего приступаем к расчету цепочки, но уже "в прямом" направлении. Как только результат работы генератора цепочки совпал с первоначальной гаммой - мы нашли 64 бит состояния генератора А5.1 - а значит можем восстановить ключ сессии Кс!
Таким образом, сжимая таблицу - мы уменьшаем объем используемой дисковой памяти, но ухудшаем время поиска по сортированной таблице с log(N) до log(N)+chainlength. Эта атака называется TMTO (time-memory tradeoff).
Фактически, мы размениваем дисковую память - на вычислительную мощность устройства, выполняющего расчет цепочек.
Основная нагрузка на вычислительное устройство - циклический расчет функции A5/1 и функции редукции (про нее далее). В самом худшем варианте, для каждой цепочки - функцию А5/1 приходится выполнять 32768 раз (2^12 = 4096 комбинаций, умножить 8 цветов). А таких цепочек хорошо бы считать хотя бы тысяч 5 за секунду, а лучше 10...15тыс.
Пересечения цепочек
К сожалению, учитывая большое количество вариантов состояния шифра - некоторые цепочки могут объединяться в одну. Разные входные значения могут создавать в итоге одинаковую особенную точку DP. Таким образом от одной особенной точки может расходиться несколько "ветвей", что может давать разные варианты начального состояния алгоритма а5.1 при его обратном восстановлении из "особенной точки". Это является основной проблемой при попытке увеличения сжатия таблицы. Чем больше мы сжимаем таблицу - тем больше ветвей формируется от каждой DP, и тем больше нужно тратить времени на попытки восстановления Кс (и его проверку).
Пересечения цепочек могут быть уменьшены при разделении длинных цепочек на группы, называемые цветами. Поэтому таблицы называются "радужными таблицами". Мы дополним генератор цепочек функцией редукции. То есть раньше алгоритм выглядел так:
То теперь станет таким:
Самый простой вариант раскрашивания таблицы в радугу - выполнение следующей операции - "функция редукции (некоторая константа) _XOR (исключающее ИЛИ)__гамма". Разным цветам назначены различные константы. Таким образом, получается что части цепочек XORены с разными константами. Если пересечение произошло в разных цветовых группах, оно будет устранено из-за другой XOR константы в следующем цикле.
Функция, вычисляющая константу "цвета" - называется функцией редукции (RF, Reduction Function). В этой статье про нее информации не будет, т.к. описание RF заслуживает отдельного материала.
Процент охвата возможных вариантов 64 бит регистра, таблицами
У радужных таблиц есть существенный недостаток - они не могут покрывать все 100% вариантов состояний а5.1. Но в GSM - в каждом из фреймов есть 4 пакета длиной 114 бит каждый. Как пример, если мы пытаемся взломать последовательность длиной 64 бита, мы имеем 51 образец на пакет или 204 образца на фрейм.
51 - потому что длина пакета 114 бит. Длина одного образца гаммы = 64 бит. Соответственно, можно применить скользящее окно, что даст нам 114-64 бит +1 = 51 вариант гаммы из каждого пакета.
Для достижения 50% вероятности расшифровки фрейма и извлечения из него ключа сессии Кс, таблица должна охватывать около 0.5% от всех вариантов ключа. К тому же , как правило - в gsm коммуникации есть возможность извлекать за один сеанс аутентификации - больше образцов, чем содержит один фрейм.
Таким образом, объем таблиц можно уменьшить, что и было сделано командой Карстена Нола:
Получается что если мы создадим гипотетическую таблицу объемом в 10тб - это - дает почти 100% гарантию извлечения Кс из одного фрейма т.к. охват пространства возможных состояний шифроалгоритма а5/1, становится равен 2%.
Во времена когда Карстен Нол показал свою презентацию про устойчивость алгоритма А5/1 - дисковое пространство было дорогим, медленным (ssd еще не существовало). Поэтому для презентации, в целях демонстрации самой концепции возможности "взлома" GSM - они ограничились 2Тб таблиц. На самом деле, для практических задач - эти таблицы плохо пригодны.
Работа Карстена Нола состоит из 40 таблиц. Давайте подсчитаем, сколько займет времени поиск по ним!
Поиск значения одной 114 битной последовательности по 40 таблицам, требует 51*8*40 = 16320 операций чтения.
Где
51 - количество вариантов 64 бит регистра в 114 бит последовательности
8 - количество цветов
40 - количество таблиц
Например, массив из 10 жестких дисков для этого требует 16.3 секунды (примерно 100 IOPS/на диск). Т.е. 100*10 = 1000iops, 16320/1000 = 16.3с.
Либо если у Вас только один HDD - 163 секунды, почти целых 3 минуты! Медленные были времена! Но даже тогда, исследователи предположили, что имея 100 000 долларов, можно купить достаточное количество USB-флеш накопителей, чтобы "взламывать" код в реальном времени. На самом деле, эффективнее эти деньги потратить по другому, и про это - ниже.
Пример современного времени. Используем 2 SSD диска Kingston Fury Renegade по 1Тб каждый. Каждый из дисков имеет измеренную скорость в 535000 IOPS. Производитель заявляет 1млн IOPS, не верьте ему. Для измерения фактической производительности с длительными цепочками запросов, пришлось писать специальный бенчмарк.
2 диска дадут 535000*2 = 1070000 IOPS. Округлим до 1000000 операций в секунду.
Тогда 16320/1000000 = 0,016с на поиск всех вариантов одного 114 бит пакета. Запомните это число!
Массив таблиц можно разбивать на более мелкие накопители. Для этого можно использовать устройства Espada PCI-E - 4x M.2 NVMe PCIe4NVME.
Например, вариант для 8 дисков: 8 х 500000 IOPS = 4000000 IOPS, 0,0045 c на каждые 114 бит, то есть - скорость 240 Кс в секунду.
Первые 2 были похожи тем, что применяли 64 бита, сгенерированные алгоритмом A5/1 в качестве входа для следующего цикла, расчитывающего определенный цвет. В варианте 3 - алгоритм А5/1 выполняется на дополнительные 100 тактов вперед и следующие 64 бита используются.
Первый формат записи был назван dp15k32 - размер особенных точек 15 нулевых бит, и 32 цвета. Позже, исследователи обнаружили, что форматы фреймов LAPDm с известным текстом не сильно отличаются, и изменили формат таблиц на dp15k8 - цветов стало меньше, всего 8. Благодаря наличию большего количества образцов гамм, можно было бы выполнить больше поисков, а таблицы должны были бы охватывать меньше всего ключевого пространства и занимать меньше места.
Так как у исследователей стояла цель ограничить размер таблиц объемом 2Тб, они нацелились на уменьшение времени поиска и ускорение генерации таблиц. Эта цель была достигнута уменьшением количества цветов.
В итоге, когда был обнаружен факт, что после 100 циклов работы алгоритма A5/1 ключевое пространство генератора А5/1 становится равным всего 16% от суммарного, исследователи изменили формат таблиц на dp12k8e100 - длина характерной точки 12 бит, 8 цветов и 100 "пустых" циклов А5/1. Ключевое пространство которое охватывают данные таблицы стало в 8 раз меньше (как результат перехода формата с dp15 на dp12), что примерно соответствует тому что имеет смысл охватывать всего 16% ключевого пространства.
Учитывая что каждый дополнительный цвет требует 164/64 = в 2.5 раза больше циклов для расчета, время генерации и поиска по таблицам сократилов в 3.2 раза (8/2,5 = 3,2), по сравнению с форматорм dp15k8.
Внимательному читателю оставлю простенькое "домашнее задание" для проверки знаний. Напишите ниже, откуда взялось число 164?
Текущий формат таблиц, используемый в Кракене - dp12k8e100 . Но, это не означает что нельзя применять dp15k8, dp15k32 - все эти таблицы были созданы исследователями в свое время, при желании их можно найти в интернете и добавить в основной массив к 12k8e100, получив почти целых 6тб таблиц, тем самым увеличив вероятность взлома.
Теперь про оптимизацию.
Если Вы не можете позволить себе быстрый вычислитель, способный просчитывать тысячи цепочек в секунду - Вы можете просто уменьшить сжатие таблиц! SSDшки быстрые, 0,016с время взлома на обычном NVME. Увеличьте массив в 10 раз (20тб таблиц)- время поиска станет 0.16с , а вычислительная нагрузка на устройство расчета цепочек - соразмерно упадет тоже в 10 раз.
Атака TMTO удобна тем, что можно ловить баланс между вычислительной мощностью и дисковым пространством.
Имеете слабые вычислители (cpu, видеокарты) - так поставьте же 50шт SSDшек, это дешевле чем GPU ферма аналогичной производительности.
Есть быстрый вычислитель? Прочитали статью про FPGA? Поздравляю, Вам вообще не нужны таблицы. Вы можете в реальном времени генерировать цепочки, экономя при этом место (физическое, в корпусе), которое занимают диски. Эта технология тоже имеет недостатки, но про это - в следующий раз.
Многие люди, интересующиеся вопросами безопасности и устойчивостью GSM ко взлому - читали про работы Карстена Нола (инструмент "Kraken"). Данное программное обеспечение используется для расшифровки шифра А5.1 , используемого в телефонии стандарта 2G по сей день.
Обычный уровень знаний про это ПО выглядит примерно так - "Качаем кракен, покупаем 2тб диск, на него записываем таблицы. Подключаем моторолу за 5$ и ломаем жсм. Profit" . Те немногие люди, которые дошли до запуска ПО, и даже модифицировали его (в интернете есть проекты под windows и т.д.) - совершенно не понимают, с чем имеют дело - и обычно задают вопросы из серии - а если 4090 воткнуть, быстрее будет считать - или нет? И это абсолютно нормально, учитывая что публикаций по данной теме очень мало, а на русском языке - вовсе нет.
Сегодня в статье я расскажу подробнее, как же эти таблицы устроены.
Некоторая используемая терминология - возможно, будет не понятной. Поэтому, найдя незнакомое слово -
Для чего все это нужно
Исследователи вопросов информационной безопасности - записывают из эфира шифрованный трафик (обмена данными) телефона с базовой станцией. Из этого трафика получаем гамму - тот набор бит, при помощи которого пакет был зашифрован.
Зная гамму - не составит труда найти ключ сеанса связи, при помощи которого можно расшифровать переговор, SMS или совершить еще какие-либо
Первый этап поиска Кс - необходимо найти внутреннее состояние регистров алгоритма шифрования а5.1. Это можно сделать разными методами, один из них - поиск по большой таблице, в которой присутствуют все варианты "ключей".
Предварительно созданные таблицы состояний генератора А5/1
Существует возможность создать такую таблицу, в которой будет будет сопоставлено состояние регистров шифра A5/1 с некоторым входным значением гаммы.
В механизме шифрования А5.1 есть 3 регистра: длиной 19 бит, 22 бит, 23 бит. Таким образом суммарная длина в 64 бита полностью описывает состояние всех трех регистров, для соответствующей гаммы. Выглядит это примерно так:
Код:
Internal state Keystream
0x0000000000000000 0xabcdef12345678
0x0000000000000001 0x54632221afed03
0x0000000000000002 0x456dcd562b980e
...
0xffffffffffffffff 0x002accd4dc51dfКак только мы получаем гамму - выполнив XOR между plaintext и ciphertext (эти данные перехватывают из эфира при помощи моторолы), становится возможным найти такое же значение в таблице и посмотреть соответствующее ему значение 64 битного регистра, описывающего состояние А5.1 в данный момент. Таблицу можно предварительно отсортировать по значениям гаммы и использовать очень эффективный механизм логарифмического поиска.
Все классно - но такая таблица будет очень большой.
2^64 состояний * 8 байт на каждое состояние (т.к. оно 64битное) = 128 Экзабайт.
Эффективное количество используемых бит ключа - только 61 бит. Так как количество вариантов ключа очень большое, могут встречаться варианты что одну и ту же гамму можно получить при помощи разных ключей. Но тем не менее значение все равно очень большое и не существует возможности генерации и хранения столь затратной по занимаемому на диске пространству, таблицы.
Сжатие таблиц
Попробуем сжать "сырую" таблицу состояний при помощи создания цепочек. Мы берем некоторое начальное состояние 64 битного регистра и используем его в качестве входных данных для алгоритма А5.1. Результат работы а5.1 - не сохраняем, и снова подаем на вход шифратора а5.1. Этот цикл повторяем до тех пор, пока не достигнем некоторого особенного результата, называемого особенной точкой ( DP ). Давайте будем считать что DP это такое значение регистра, в которым 12 младших бит - равны нулю.
Таким образом получается средняя длина цепочки в 2^12 = 4096 бит, то есть эффект сжатия составит примерно 1:4096.
Как только, в результате записи радиообмена - мы получаем некоторое значение гаммы, пригодное для взлома - можем использовать ее в качестве входного значения для генератора цепочки, и выполнять алгоритм до тех пор пока не достигнем особенную точку DP. После чего выполним обратный поиск этой точки в таблице. Так мы находим "ветвь" таблицы, в которой находится данное состояние - после чего приступаем к расчету цепочки, но уже "в прямом" направлении. Как только результат работы генератора цепочки совпал с первоначальной гаммой - мы нашли 64 бит состояния генератора А5.1 - а значит можем восстановить ключ сессии Кс!
Таким образом, сжимая таблицу - мы уменьшаем объем используемой дисковой памяти, но ухудшаем время поиска по сортированной таблице с log(N) до log(N)+chainlength. Эта атака называется TMTO (time-memory tradeoff).
Фактически, мы размениваем дисковую память - на вычислительную мощность устройства, выполняющего расчет цепочек.
Основная нагрузка на вычислительное устройство - циклический расчет функции A5/1 и функции редукции (про нее далее). В самом худшем варианте, для каждой цепочки - функцию А5/1 приходится выполнять 32768 раз (2^12 = 4096 комбинаций, умножить 8 цветов). А таких цепочек хорошо бы считать хотя бы тысяч 5 за секунду, а лучше 10...15тыс.
Пересечения цепочек
К сожалению, учитывая большое количество вариантов состояния шифра - некоторые цепочки могут объединяться в одну. Разные входные значения могут создавать в итоге одинаковую особенную точку DP. Таким образом от одной особенной точки может расходиться несколько "ветвей", что может давать разные варианты начального состояния алгоритма а5.1 при его обратном восстановлении из "особенной точки". Это является основной проблемой при попытке увеличения сжатия таблицы. Чем больше мы сжимаем таблицу - тем больше ветвей формируется от каждой DP, и тем больше нужно тратить времени на попытки восстановления Кс (и его проверку).
Пересечения цепочек могут быть уменьшены при разделении длинных цепочек на группы, называемые цветами. Поэтому таблицы называются "радужными таблицами". Мы дополним генератор цепочек функцией редукции. То есть раньше алгоритм выглядел так:
Код:
function a5_i (input)
input = some value of 64 bit reg;
while(1){
gamma = a5_i(input)
check if gamma is DP
if there is DP, return
input = gamma
}То теперь станет таким:
Код:
function a5_i (input)
input = some value of 64 bit reg;
while(1){
input = input XOR color (reduction function)
gamma = a5_i(input)
check if gamma is DP
if there is DP:
color = color + n
if color > max _color
return
input = gamma
}Самый простой вариант раскрашивания таблицы в радугу - выполнение следующей операции - "функция редукции (некоторая константа) _XOR (исключающее ИЛИ)__гамма". Разным цветам назначены различные константы. Таким образом, получается что части цепочек XORены с разными константами. Если пересечение произошло в разных цветовых группах, оно будет устранено из-за другой XOR константы в следующем цикле.
Функция, вычисляющая константу "цвета" - называется функцией редукции (RF, Reduction Function). В этой статье про нее информации не будет, т.к. описание RF заслуживает отдельного материала.
Процент охвата возможных вариантов 64 бит регистра, таблицами
У радужных таблиц есть существенный недостаток - они не могут покрывать все 100% вариантов состояний а5.1. Но в GSM - в каждом из фреймов есть 4 пакета длиной 114 бит каждый. Как пример, если мы пытаемся взломать последовательность длиной 64 бита, мы имеем 51 образец на пакет или 204 образца на фрейм.
51 - потому что длина пакета 114 бит. Длина одного образца гаммы = 64 бит. Соответственно, можно применить скользящее окно, что даст нам 114-64 бит +1 = 51 вариант гаммы из каждого пакета.
Для достижения 50% вероятности расшифровки фрейма и извлечения из него ключа сессии Кс, таблица должна охватывать около 0.5% от всех вариантов ключа. К тому же , как правило - в gsm коммуникации есть возможность извлекать за один сеанс аутентификации - больше образцов, чем содержит один фрейм.
Таким образом, объем таблиц можно уменьшить, что и было сделано командой Карстена Нола:
Код:
Исходная таблица: 128 EiB, 148 EB
Уменьшили длину ключа на 3 бита (т.к. по факту ключ 61 битный, а не 64): 18 EB
Добавили цепочки длиной 4096 бит (DP с 12 нулевыми битами): 4.5 PB
Ограничили количество цветов 8: 563 TB
Ограничили охват до 0.5%: 2.8 TBПолучается что если мы создадим гипотетическую таблицу объемом в 10тб - это - дает почти 100% гарантию извлечения Кс из одного фрейма т.к. охват пространства возможных состояний шифроалгоритма а5/1, становится равен 2%.
Во времена когда Карстен Нол показал свою презентацию про устойчивость алгоритма А5/1 - дисковое пространство было дорогим, медленным (ssd еще не существовало). Поэтому для презентации, в целях демонстрации самой концепции возможности "взлома" GSM - они ограничились 2Тб таблиц. На самом деле, для практических задач - эти таблицы плохо пригодны.
Скорость чтения из таблиц
Скорость поиска значения в массиве таблиц ограничена количеством IOPS Вашего дискового массива. IOPS - это среднее число операций произвольного чтения с накопителя, в секунду .Работа Карстена Нола состоит из 40 таблиц. Давайте подсчитаем, сколько займет времени поиск по ним!
Поиск значения одной 114 битной последовательности по 40 таблицам, требует 51*8*40 = 16320 операций чтения.
Где
51 - количество вариантов 64 бит регистра в 114 бит последовательности
8 - количество цветов
40 - количество таблиц
Например, массив из 10 жестких дисков для этого требует 16.3 секунды (примерно 100 IOPS/на диск). Т.е. 100*10 = 1000iops, 16320/1000 = 16.3с.
Либо если у Вас только один HDD - 163 секунды, почти целых 3 минуты! Медленные были времена! Но даже тогда, исследователи предположили, что имея 100 000 долларов, можно купить достаточное количество USB-флеш накопителей, чтобы "взламывать" код в реальном времени. На самом деле, эффективнее эти деньги потратить по другому, и про это - ниже.
Пример современного времени. Используем 2 SSD диска Kingston Fury Renegade по 1Тб каждый. Каждый из дисков имеет измеренную скорость в 535000 IOPS. Производитель заявляет 1млн IOPS, не верьте ему. Для измерения фактической производительности с длительными цепочками запросов, пришлось писать специальный бенчмарк.
2 диска дадут 535000*2 = 1070000 IOPS. Округлим до 1000000 операций в секунду.
Тогда 16320/1000000 = 0,016с на поиск всех вариантов одного 114 бит пакета. Запомните это число!
Массив таблиц можно разбивать на более мелкие накопители. Для этого можно использовать устройства Espada PCI-E - 4x M.2 NVMe PCIe4NVME.
Например, вариант для 8 дисков: 8 х 500000 IOPS = 4000000 IOPS, 0,0045 c на каждые 114 бит, то есть - скорость 240 Кс в секунду.
Формат хранения таблиц
Известно, что исследователи в рамках проекта A5/1 TMTO (Карстен Нол и его коллеги), главным образом использовали 3 различных формата радужных таблиц.Первые 2 были похожи тем, что применяли 64 бита, сгенерированные алгоритмом A5/1 в качестве входа для следующего цикла, расчитывающего определенный цвет. В варианте 3 - алгоритм А5/1 выполняется на дополнительные 100 тактов вперед и следующие 64 бита используются.
Первый формат записи был назван dp15k32 - размер особенных точек 15 нулевых бит, и 32 цвета. Позже, исследователи обнаружили, что форматы фреймов LAPDm с известным текстом не сильно отличаются, и изменили формат таблиц на dp15k8 - цветов стало меньше, всего 8. Благодаря наличию большего количества образцов гамм, можно было бы выполнить больше поисков, а таблицы должны были бы охватывать меньше всего ключевого пространства и занимать меньше места.
Так как у исследователей стояла цель ограничить размер таблиц объемом 2Тб, они нацелились на уменьшение времени поиска и ускорение генерации таблиц. Эта цель была достигнута уменьшением количества цветов.
В итоге, когда был обнаружен факт, что после 100 циклов работы алгоритма A5/1 ключевое пространство генератора А5/1 становится равным всего 16% от суммарного, исследователи изменили формат таблиц на dp12k8e100 - длина характерной точки 12 бит, 8 цветов и 100 "пустых" циклов А5/1. Ключевое пространство которое охватывают данные таблицы стало в 8 раз меньше (как результат перехода формата с dp15 на dp12), что примерно соответствует тому что имеет смысл охватывать всего 16% ключевого пространства.
Учитывая что каждый дополнительный цвет требует 164/64 = в 2.5 раза больше циклов для расчета, время генерации и поиска по таблицам сократилов в 3.2 раза (8/2,5 = 3,2), по сравнению с форматорм dp15k8.
Внимательному читателю оставлю простенькое "домашнее задание" для проверки знаний. Напишите ниже, откуда взялось число 164?
Текущий формат таблиц, используемый в Кракене - dp12k8e100 . Но, это не означает что нельзя применять dp15k8, dp15k32 - все эти таблицы были созданы исследователями в свое время, при желании их можно найти в интернете и добавить в основной массив к 12k8e100, получив почти целых 6тб таблиц, тем самым увеличив вероятность взлома.
Теперь про оптимизацию.
Если Вы не можете позволить себе быстрый вычислитель, способный просчитывать тысячи цепочек в секунду - Вы можете просто уменьшить сжатие таблиц! SSDшки быстрые, 0,016с время взлома на обычном NVME. Увеличьте массив в 10 раз (20тб таблиц)- время поиска станет 0.16с , а вычислительная нагрузка на устройство расчета цепочек - соразмерно упадет тоже в 10 раз.
Атака TMTO удобна тем, что можно ловить баланс между вычислительной мощностью и дисковым пространством.
Имеете слабые вычислители (cpu, видеокарты) - так поставьте же 50шт SSDшек, это дешевле чем GPU ферма аналогичной производительности.
Есть быстрый вычислитель? Прочитали статью про FPGA? Поздравляю, Вам вообще не нужны таблицы. Вы можете в реальном времени генерировать цепочки, экономя при этом место (физическое, в корпусе), которое занимают диски. Эта технология тоже имеет недостатки, но про это - в следующий раз.
Последнее редактирование:
