23-09-2023
Атака на основе подобранного ключа (англ. Chosen-key attack ) — один из способов криптоаналитического вскрытия. Использующий этот тип атаки криптоаналитик может наблюдать за работой алгоритма шифрования, в котором используются несколько ключей. Криптоаналитик изначально ничего не знает о точном значении ключей, зато ему известно некоторое математическое отношение, связывающее между собой ключи.
При выборе криптосистем стараются выбирать систему, способную противостоять всевозможным неожиданным атакам. У таких мер предосторожности есть как минимум 3 причины:
В ранее существующей атаке на основе текста аналитик мог заставить пользователя шифровать или расшифровывать большое количество сообщений по выбору аналитика. В новом типе атаки аналитик может так же указывать один или более битов ключа, которые будут меняться в каждом шифровании[2].
Таким образом, если пользователь использует секретный ключ и открытую криптосистему , то в любой момент криптоаналитик может выбрать сообщение и вектор , также известный как key-flip, и выполнить шифрование или расшифрование . Основным применением атаки на основе подобранного ключа является верификация систем, но при определенных обстоятельствах эта атака может быть применена на практике. Если шифр потока данных используется для передачи сессионного ключа от пользователя к пользователю и криптоаналитик получит контроль над линией передачи, то он сможет изменить любые биты ключа и получит измененный ключ вместо . Когда начнет передачу с неверным ключом, получит искаженное сообщение и начнет процедуру восстановления. В то же время криптоаналитик получит зашифрованный ключом текст. (Хорошая криптозащита может отражать такие атаки, используя новые независимые сессионные ключи или добавляя нелинейных битов ошибок детектирования в сессионный ключ всякий раз, когда процедура восстановления необходима. Однако, история показывает, что хорошая криптозащита не всегда следует этому и желательно иметь систему, которая не падает под такой атакой)[2].
Продемонстрируем возможности нового типа атаки на основе криптосистемы, которая показала себя крайне устойчивой против атаки на основе подобранного текста, однако атака на основе подобранного ключа её мгновенно взламывает[2].
Пусть — секретный блочный шифр с размером ключа бит. Определим новый блочный шифр .
Если основной шифр имеет качественную n-битную защиту, то взлом шифра при помощи атаки на основе анализа текста требует расширенного поиска по ключевому пространству бит. Грубо говоря, если аналитик не обладает базовыми знаниями о , то он может получить нужную информацию, если только он шифрует или расшифровывает ключами или [2].
Хотя шифр сложен для взламывания атакой на основе анализа текста, он очень легко поддается взлому атакой на основе подобранного текста. Аналитик нуждается в двух шифрах: и для некоторого подходящего сообщения . Если первый бит равен нулю,
В остальных случаях,
Таким образом аналитик сразу получает все кроме первого бита , и может завершить операцию, так как ему известен открытый текст[3].
Пример выше был искусственно уязвим к атаке на основе подобранного ключа. В этой части покажем атаку, которая не зависит от конкретной слабости в функции шифровании. Оно основано на атаке MITM. Оно позволяет сократить время работу расширенного поиска в зависимости от числа key-flip[3].
Теорема. Пусть — блочный шифр с n-битным ключом. Предположим, что криптоаналитик может выполнить инверсий и имеет слов памяти. Тогда он сможет взломать в дополнительных шага[3].
Доказательство:
Аналитик заменяет последние бит в ключе всеми возможными способами. Например, он зашифровывает значения
где секретный ключ пользователя и любое подходящее сообщение. Он создает хэш-таблицу из значений [3].
Затем он совершает шифрований, меняя первые бит ключа и обнуляя последние бит:
После всех вычислений, каждое значение проверяется на соответствие в хэш-таблице[3].
Если изначальный ключ взламывается через , где состоит из последних бит, тогда запись будет соответствовать результату через шифрований во второй стадии. Когда же соответствие будет найдено, будет кандидатом в ключи. Возможно несколько ложных тревог, если несколько ключей подходят к сообщению , но, как в атаке на основе анализа текста, один или два дополнительных блока известного открытого текста почти наверняка исключают их, это незначительно повлияет на время работы[3].
Вывод: Используя неограниченное количество атак на основе подобранного ключа, любой блочный шифр с n-битным ключом может быть взломан, используя не более вычислений в памяти[3].
Доказательство: Выберем .
Замечание: Если много примеров должно быть решено и большое количество памяти доступно, будет намного эффективнее поменять 2 стадии местами в доказательстве теоремы. Предрасчет и сохранение шифрований в памяти. Для каждой проблемы, совершаем инверсий, и проверяем на соответствие таблицу. Таким образом, каждая дополнительная проблема требует только шагов[3].
Атака на основе подобранного ключа.