Приветствую, Хабр! В нескольких предыдущих статьях я рассматривал режимы шифрования для блочных шифров, постепенно сдвигаясь в сторону режимов, превращающих блочные шифры в потоковые. В новой статье в фокусе будет чисто потоковый шифр - RC4. Я расскажу о самом шифре, а также об атаке FMS и применении её для решения задачи Oh SNAP с платформы Cryptohack.

Шифр RC4

RC4 - потоковый шифр, разработанный Роном Ривестом в 1987 году, реализация которого была скрыта коммерческой тайной до 1994 года, после чего она утекла в сеть. К началу 2000х годов он стал одним из самых популярных шифров, используемых в программном обеспечении. Такая популярность была во многом обусловлена его очень простой структурой, большой гибкостью и достаточно большой безопасностью - секретное состояние в ~1700 бит при ключе в 8 байт.

Шифр состоит из двух частей: процедура инициализации (KSA) и процедура генерации гаммы (PRGA). Процедура инициализации запускается единожды для подготовки шифра к работе. Она создаёт для шифра внутреннее состояние размером в 256 байт и перемешивает это состояние в соответствии с используемым ключом шифрования.

В общем случае шифр RC4 поддерживает различные размеры "слова" и внутренне состояние также может иметь различные размеры. В данной статье я не буду рассматривать настолько обобщённые реализации, размер слова в нашей задаче составляет байт, соответственное состояние получается размером 256, его и будем рассматривать.
За более общим описанием шифра и соответствующей атаки рекомендую ознакомиться с литературой из списка в конце статьи.

def ksa(key: bytes):
  S = [i for i in range(256)]
  
  j = 0
  for i in range(256):
    j = (j + S[i] + key[i % len(key)]) % 256
    S[i], S[j] = S[j], S[i]

Далее для получения байта гаммы ключа используется процедура PRGA

def prga():
  i = 0
  j = 0
  while True:
    i = (i + 1) % 256
    j = j + S[i]
    S[i], S[j] = S[j], S[i]
    yield S[(S[i] + S[j]) % 256]

Уязвимость в KSA

В 2001 году Скотт Флюрер, Итсик Мантин и Ади Шамир опубликовали статью под названием "Weakness in the Key Scheduling Algorithm of RC4". Из заголовка сразу понятно что их статья рассматривает первую часть шифра - процедуру KSA. Я не буду подробно рассматривать статью, опишу лишь её основные моменты и саму идею атаки.

Для начала авторы конструируют ослабленную версию процедуры KSA и строго показывают, что определённые шаблоны ключа, проходя через эту ослабленную процедуру, создают так же вполне определённые шаблоны в секретном состоянии шифра и соответсвенно это влияет на шифротекст. Другими словами, если используемый ключ шифрования удовлетворяет некоторым условиям, то и секретное состояние после ослабленной процедуры KSA также будет удовлетворять определённым условиям.

Далее они вносят поправку для неослабленной процедуры KSA и показывают, что те же определённые шаблоны распределения бит в ключе будут проникать в секретное состояние, однако теперь с некоторой вероятностью. И вероятность эта вполне существенная ( $\geq 2/5$ ).

В последующих секциях статьи описаны возможности применения данной особенности для атаки на шифрование RC4. В частности описываются возможности атаки с применением известного инициализирующего вектора в случаях когда вектор приписывается к ключу в начале или в конце. Именно атаку на известный инициализирующий вектор мы будем использовать для решения задачи и именно эта атака получила название FMS (Fluhrer-Mantin-Shamir) и обрела популярность, потому что она использовалась для взлома шифрования WiFi сетей использующих защиту WEP.

Атака FMS

Теперь чуть подробнее пройдёмся по механике самой атаки. Суть её в следующем:

Если IV состоит хотя бы из трёх байт и имеет вид , где - произвольный байт; и мы имеем возможность угадать или вычислить первый байт гаммы ключа (мы знаем первый байт открытого текста) , то с вероятностью около 5% можно вычислить правильный первый байт ключа по формуле $K_0 = keyStreamByte - 6 - X \pmod {256}$
После вычисления первого байта ключа, второй байт можно вычислить если IV имеет вид по формуле $K_1 = keyStreamByte - 10 - X - K_0 \pmod {256}$
Обобщённая форма IV: , где - количество уже вычисленных байт ключа.
Общая формула для байта ключа:, где - первый байт гаммы ключа, - значение индекса в KSA после итераций, - значение байта в состоянии шифра по индексу после итераций. KSA в данном случае вычисляется с использованием уже известных байт ключа. То есть в KSA мы передаём значение . Например, для поиска первого байта ключа мы вычисляем 3 итерации KSA используя только известный IV в качестве ключа. Для следующего байта проводим уже 4 итерации используя в качестве ключа конкатенацию IV и уже известного байта, и т. д.

Чтобы понять откуда всё это берётся разберём несколько итераций KSA при IV = (3, 255, X). Держите в уме, что IV добавляется в начало ключа, поэтому , и равны , и соответственно.

Состояние изначально выглядит так (сверху индекс, снизу значение)

Во время первой итерации , . Далее в меняются местами элементы с индексами и , соответственно получаем состояние

Вторая итерация: , $j = 3 + S[1] + K[1] = 3 + 1 + 255 = 3 \pmod {256}$

Третья итерация: ,

Наконец, четвёртая итерация: ,

А теперь давайте предположим, что KSA на этом остановилась. Если мы попытаемся сгенерировать один байт ключевой гаммы процедурой PRGA, то получим следующее

,
,
, меняются местами, но это не влияет на результат вычисления первого байта.
Первый байт ключевой гаммы будет равен

Получается, что первый байт ключевой гаммы связан с первым (неизвестным нам) байтом ключа формулой , и если мы знаем чему равен этот байт, то мы можем легко вычислить $K_3 = keyStreamByte - 6 - X \pmod {256}$ . То есть мы получили то же отношение, которое я привёл в начале секции. Формулу для следующего байта можно получить таким же образом, если заменить IV на .

Единственная проблема в том, что процедура KSA не останавливается после 4 итераций, а отрабатывает ещё 252 цикла. В любой из этих итераций индексы , и могут измениться и тогда формула не будет работать. Если предположить, что в любой итерации индекс принимает случайное значение, то вероятность того, что в этой итерации не изменится какой-то из индексов 0, 1 или 3 составляет $\frac{253}{256}$ . Соответственно вероятность того, что за никакой из индексов не изменится за 252 таких итерации составляет $(\frac{253}{256}) ^ {252} \approx 0.05$ . Отсюда вытекает вероятность успешно вычислить байт ключа в 5%.

Давайте обратим внимание на то, что мы имеем 5% вероятность получить правильный байт ключа, в 95% остальных случаев мы будем получать какое-то случайное значение. Эта вероятность распределена между 255 другими возможными неправильными байтами. Соответственно, вероятность получения какого-либо конкретного неправильного байта будет сильно ниже 5% ( $\approx 0.3$ %, если меня не подводят мои расчёты). Именно таким образом мы можем отделить правильные значения от неправильных - собрать как можно больше вариантов и найти тот, который появляется чаще остальных.

Решение задачи

Теперь перейдём к самой задаче. Нам дан следующий код

from Crypto.Cipher import ARC4


FLAG = ?


@chal.route('/oh_snap/send_cmd/<ciphertext>/<nonce>/')
def send_cmd(ciphertext, nonce):
    if not ciphertext:
        return {"error": "You must specify a ciphertext"}
    if not nonce:
        return {"error": "You must specify a nonce"}

    ciphertext = bytes.fromhex(ciphertext)
    nonce = bytes.fromhex(nonce)

    cipher = ARC4.new(nonce + FLAG.encode())
    cmd = cipher.decrypt(ciphertext)
    if cmd == b"ping":
        return {"msg": "Pong!"}
    else:
        return {"error": f"Unknown command: {cmd.hex()}"}

Нам дана возможность расшифровать (то же самое что зашифровать) произвольный текст с помощью RC4 (ARC4 то же самое что RC4). В качестве ключа для шифра используется присланный нами произвольный IV (nonce), к которому добавлен флаг. Если расшифрованный текст не равен ping, то сервер возвращает сообщение об ошибке с расшифрованным текстом.

Фактически нам дана идеальная среда для применения атаки FMS. Мы сами можем конструировать подходящие нам IV, а также нам не нужно угадывать первый байт ключевой гаммы, т.к. мы знаем и открытый и закрытый тексты, а значит можем его вычислить. Осталось только написать код, не будем же мы это делать вручную.

Код решения будет выглядеть так

import requests
import json
from time import sleep
import os
from ptCrypt.Attacks.Symmetric.RC4.FluhrerMantinShamirAttack import FluhrerMantinShamirAttack


baseAddress = "https://aes.cryptohack.org/oh_snap/send_cmd"

class Callback(FluhrerMantinShamirAttack.Callback):

    def __init__(self):
        self.text = os.urandom(16).hex()
        self.lastFoundByte = None
        self.sleepTime = 1

    def applyNonce(self, nonce):
        try:
            request = f"{baseAddress}/{self.text}/{nonce}"
            response = requests.get(request)
            
            firstByteCommand = json.loads(response.content)["error"].strip("Unknown command: ")[:2]
            keyStreamByte = int(firstByteCommand, 16) ^ int(self.text[:2], 16)

            return keyStreamByte
        except Exception as t:
            print(t)
            sleep(self.sleepTime)
            self.sleepTime = min(60, self.sleepTime * 2)
            return self.applyNonce(nonce)
        
    
    def shouldContinue(self):
        return self.lastFoundByte != b"}"

    def onKeyByteFound(self, keyByte):
        self.lastFoundByte = bytes([keyByte])
        print(f"Found byte: {chr(keyByte)}")
    
    def onFinished(key):
        print(f"Found key: {key}")


attack = FluhrerMantinShamirAttack(Callback(), b"")
attack.run()

Сама атака реализована внутри библиотеки ptCrypt начиная с версии 0.0.14.1. Класс FluhrerMantinShamirAttack сам генерирует IV нужной формы и вычисляет наиболее вероятные байты ключа, необходимо по сути только реализовать взаимодействие с сервером и пару методов для контроля хода атаки.

Чуть подробнее про код:

Класс Callback реализовывает интерфейс колбека FluhrerMantinShamirAttack.Callback для взаимодействия с классом атаки.
Метод applyNonce(self, nonce) получает IV нужного формата и отправляет на сервер для шифрования, затем из зашифрованного текста вычисляет первый байт гаммы ключа и возвращает в класс атаки для последующей обработки. Так как при многочисленных запросах на сервер может выстрелить ограничение на количество запросов, в методе предусмотрен рекурсивный ретрай с увеличением интервала отправки запросов.
Метод shouldContinue() проверяет не нашли ли мы полный флаг.
Методы onKeyByteFound() и onFinished() просто выводят найденный байт ключа и полный ключ соответственно.

Результаты работы программы:

Источники

"Weakness of the Key Scheduling Algorithm of RC4", Fluhrer, Mantin, Shamir
"Applied Cryptanalysis. Breaking Ciphers in the Real World", Mark Stamp, Richard M. Low, p. 103 - 110
"RC4 - Fluhrer, Mantin, Shamir attack", Kevin Liu
Fluhrer, Mantin and Shamir attack, Wikipedia
RC4, Wikipedia

Cryptohack. Решение Oh SNAP. Атака Флюрера-Мантина-Шамира (Fluhrer, Mantin, Shamir)