ISO 9797-1: поросячья латынь / Хабр

Увы, у меня нет профильного математического образования (я вообще гуманитарий), потому любой стандарт по криптографии для меня ничто иное, как поросячья латынь. А после детального изучения приходит горькое осознание, что это я лезу в калашный ряд со свиным рылом... И вот прилетела задача, решить которую промптом не получится (я пробовал, честно), а потому надо лезть в ~~калашный ряд~~ ISO9797-1 и смотреть, что там такое делается. Результаты изучения решил расписать здесь, т.к. может кому-то будет полезно, а может кто-то из crypto-лордов укажет на недочеты/ошибки.

Исходники.

Я вечно плутаю между методами выравнивания входных данных - все эти padding'и-шмадинги с их 0x00 и 0x80. Какой из них просто нули, а какой предваряется 0x80? А надо ли вставлять этот 0x80 если данные выровнены? Почему байтов 24, а в блоке L указано 0xC0? Но этого мало: к этой сумятице добавляются методы генерации MAC которых целых пять штук и могут работать со всеми вариантами дополнения. В этой статье постараемся разобраться с:

общей архитектурой алгоритмов выработки MAC;
методами выравнивания;
методами расчета контрольной суммы №№ 1-4.

Итак, начнем!

Общая архитектура

Все описываемые алгоритмы выработки MAC имеют следующий шаблон:

и состоят из семи шагов:

Деривация ключа (key derivation);
Дополнение (padding);
Разбиение (splitting);
Итеративное поблочное шифрование (iterative block ciphering) e;
Финальная итерация (final iteration) F;
Выходное преобразование (output transformation) g;
Усечение (truncation) trunc;

В контексте данной статьи под блочным шифрованием e подразумевается DES, который ожидает данные длиною, кратной размеру его входного блока (8 байт). Например, если мы подаем 24 байта, то они будут поделены на D1, D2 и D3 по 8 байт каждый. Первый блок XOR’ится с нулевым вектором инициализации (8 нулей) и шифруется ключом K. Для второго в качестве вектора инициализации используется результат предыдущего шага, затем шифрование. Смыть, повторить. Описанное есть ни что иное как режим CBC в блочном шифровании и эта подсказка упростит нам жизнь на этапе имплементации.

Step 2: padding

В стандарте определены четыре метода:

padding method 1

Добавить ноль и более байт со значением "0x00" справа. Предполагается, что если длина входных данных кратна размеру блока, то нули вообще не добавляются.

padding method 2

Добавить байт 0x80 справа и дополнить нулями до кратности размеру блока. Здесь байт 0x80 добавляется всегда, даже если входные данные итак были выровнены:

Пример 1:

было: [0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07]
стало: [0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,0x80]

Пример 2:

было: [0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08]
стало: [0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08
0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]

padding method 3

Добавить ноль и более байт справа и 8-байтовый блок слева, в котором записано количество (внимание) бит в исходном сообщении:

Пример 1:

исходное сообщение:
[0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07]
количество бит: 7 x 8 = 56 (0x38)
Добивка справа:
[0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x00]
Блок слева:
[0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x38
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x00]

Пример 2:
исходное сообщение:
[0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08]
количество бит : 8 x 8 = 64 (0x40)
Добивка справа (отсутствует):
[0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08]
Блок слева:
[0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08]

padding method 4

Аналогичен методу 2 с той лишь разницей, что если данные итак выровнены, то метод не применяется вообще.

Так’с, с выравниванием, вроде, разобрались. "Разбиение (step 3)" и "итеративное шифрование (step 4)" описал под "Общей архитектурой", переходим к следующим шагам.

Step 5: final iteration

Финальная итерация выполняется над последним блоком входных данных D_q, а ее результатом становится блок H_q. Всего предусмотрено три варианта:

H_q = e_K1(D_q XOR H_q-1) - шифруем тем же ключом, что использовался на итерации;
H_q = e_K2(D_q XOR H_q-1) - используется другой ключ;
H_q = e_K1(D_q XOR H_q-1 XOR K2) - применяется маскирующий ключ. Так же есть исключение: если применяется padding method 4 и входная строка не кратна блоку, то применяется маскирующий ключ K₃: H_q = e_K1(D_q XOR H_q-1 XOR K3)

Step 6: output transformation

Результат предыдущего шага (H_q) передаем в функцию преобразования (на первой иллюстрации отмечена как коричневый блок g) , результатом которой будет блок G. Предлагаются три варианта:

G = H_q - т.е. никаких дополнительных действий не требуется.
G = e_K2(H_q) - последний блок дополнительно шифруем ключом K2.
G = e_K1(d_K2(H_q)) - применяем операцию расшифровывания на ключе K2, а затем шифруем на ключе K1.

MAC algorithm 1

Параметры алгоритма:

final iteration 1: последовательная и финальная трансформации используют один ключ
output transformation 1: никаких дополнительных действий над выходным значением H_q
key: K1
padding methods No 1 (нули), 2 (0x80 + нули), 3 (счетчик битов + 0x80 + нули):

def iso9797_1_mac_1(input_list:list[int], padding_method:int) -> list[int]:
    print("\nISO 9797-1 MAC 1")

    key1   = hex_to_bytes('0123456789ABCDEF')
    data   = list(input_list)

    data   = __padding(data, padding_method)

    des_K1 = DES.new(bytes(key1), DES.MODE_CBC, (b'\x00' * 8))
    Hq     = des_K1.encrypt(bytes(data))
    mac    = list(Hq)[-8:]

    return mac

Как говорилось ранее, шаг №4 "iterative block ciphering" - это режим CBC, поэтому на строке №9 создаем объект DES в соответствующем режиме с ключом K1 и нулевым вектором инициализации и шифруем данные. Последний блок шифротекста и есть MAC. Кстати, ключи (и проверочные значения, о них в конце) я взял из самого стандарта редакции 2011 года.

Функция дополнения одна на всех:

def __padding(data:list[int], padding_method:int) -> list[int]:

    padding = 0

    if padding_method == 0x01:
        print("padding method 1")
        data_len = len(data)
        padding  = (8 - (data_len % 8)) % 8
        data    += [0] * padding
    elif padding_method == 0x02:
        print("padding method 2")
        data.append(0x80)
        data_len = len(data)
        padding  = (8 - (data_len % 8)) % 8
        data    += [0] * padding
    elif padding_method == 0x03:
        print("padding method 3")
        data_len = len(data)
        padding  = (8 - (data_len % 8)) % 8
        data    += [0] * padding
        # This method counts the number of bits, not bytes
        data_len = data_len * 8
        data_len = list(data_len.to_bytes(8, "big"))
        data = data_len + data
    else:
        raise ValueError(F"Unsupported padding method {padding_method:02X}")

    return data

Да, поддержка "method 4" пока не добавлена (и на солнце есть пятна).

MAC algorithm 2

Как видно на иллюстрации, отличие состоит в дополнительном шаге по шифрованию вторым ключом непосредственно перед срезанием MAC'а.

Параметры алгоритма:

final iteration 1: финальная трансформация использует ключ K2
output transformation 2: дополнительно шифруем H_qключом K2
key: K1, K2
padding methods No 1 (нули), 2 (0x80 + нули), 3 (счетчик битов + 0x80 + нули):

def iso9797_1_mac_2(input_list:list[int], padding_method:int) -> list[int]:
    print("\nISO 9797-1 MAC 2")

    key1   = hex_to_bytes('0123456789ABCDEF')
    key2   = hex_to_bytes('F1D3B597795B3D1F')
    data   = list(input_list)

    data   = __padding(data, padding_method)

    des_K1 = DES.new(bytes(key1), DES.MODE_CBC, (b'\x00' * 8))
    Hq     = des_K1.encrypt(bytes(data))

    des_K2 = DES.new(bytes(key2), DES.MODE_CBC, (b'\x00' * 8))
    g      = des_K2.encrypt(Hq[-8:])
    mac    = list(g)

    return mac

Соответственно, в коде мы берем последние 8 байт H_q и еще раз прогоняем их через DES (но уже с другим ключом).

MAC algorithm 3

Широко известен в узких кругах как Retail MAC

Этот метод - дальнейшее усиление защиты путем усложнения финальной трансформации.

Параметры:

final iteration 1: финальная трансформация использует ключ K2
output transformation 3: дополнительно расшифровываем H_qключом K2, затем шифруем ключом K1.
key: K1, K2, производные от мастер-ключа
padding methods No 1 (нули), 2 (0x80 + нули), 3 (счетчик битов + 0x80 + нули);

По своей сути этот метод генерирует MAC посредством комбинации DES и 3DES. Что мы и сделаем в коде:

def iso9797_1_mac_3(input_list:list[int], padding_method:int) -> list[int]:
    print("\nISO 9797-1 MAC 3")

    key1   = hex_to_bytes('0123456789ABCDEF')
    key2   = hex_to_bytes('FEDCBA9876543210')
    data   = list(input_list)

    data   = __padding(data, padding_method)

    des_K1 = DES.new(bytes(key1), DES.MODE_CBC, (b'\x00' * 8))
    Hq     = des_K1.encrypt(bytes(data[0:-8]))

    des_K2 = DES3.new(bytes(key1 + key2), DES.MODE_CBC, bytes(Hq[-8:]))
    g      = des_K2.encrypt(bytes(data[-8:]))
    mac    = list(g)
    
    return mac

Но тут есть тонкости о которых стоит упомянуть. Перво-наперво в DES (строка №11) передается не вся входная строка, а лишь LEN - 8, так мы получаем H_q. Далее используем последние 8 байт H_q как вектор инициализации 3DES, который будет шифровать последний блок открытых данных.

MAC algorithm 4

Широко известен в узких кругах как MacDES

Как и MAC3 является разновидностью MAC2, только усиливает первую часть схемы (initial transformation). Кстати, в ISO 9797-1 от 2011 года термин "initial transformation" исчез, что может привести к путанице, т.к. многие стандарты твердят, что он там есть.

Параметры алгоритма:

final iteration 1: финальная трансформация использует ключ K2
output transformation 2: дополнительно шифруем H_qключом K2.
key: K1, K2, K3, при этом K3 извлекается из K2.
padding methods No 1 (нули), 2 (0x80 + нули), 3 (счетчик битов + 0x80 + нули);

Чтобы получить ключ K3, к нечетным (слева направо, 1й, 3й, 5й и т.д.) нибблам ключа K2 необходимо применить операцию дополнительного кода. Тогда "01" станет "FE", "02" - "DC" и т.д.

Связка «K1 и K3» используются для обработки первого блока входных данных по формуле

H₁ = e_K3(e_K1(D₁))

А связка «K1 и K2» используется на этапе выходной трансформации.

def iso9797_1_mac_4(input_list:list[int], padding_method:int) -> list[int]:
    print("\nISO 9797-1 MAC 4")

    key1 = hex_to_bytes('01234567 89ABCDEF')
    key2 = hex_to_bytes('FEDCBA98 76543210')
    # key3   = hex_to_bytes('0E2C4A68 86A4C2E0')
    key3 = [0] * 8

    for i, b in enumerate(key2):
        msn = (0x0F - ((b & 0xF0) >> 4)) << 4 # two'complement method
        lsn = (b & 0x0F)
        key3[i] = msn + lsn
    
    data   = list(input_list)

    data   = __padding(data, padding_method)

    des_K1 = DES.new(bytes(key1), DES.MODE_CBC, (b'\x00' * 8))
    e      = des_K1.encrypt(bytes(data[0:8]))

    des_K3 = DES.new(bytes(key3), DES.MODE_CBC, (b'\x00' * 8))
    h1     = des_K3.encrypt(e)

    des_K1 = DES.new(bytes(key1), DES.MODE_CBC, h1)
    Hq     = des_K1.encrypt(bytes(data[8:]))

    des_K2 = DES.new(bytes(key2), DES.MODE_CBC, (b'\x00' * 8))
    g      = des_K2.encrypt(Hq[-8:])
    mac    = list(g)

    return mac

Этот метод отличается мудреностью. Сначала необходимо вывести ключ K3 из ключа K2, затем первый блок входных данных (строка № 19) прогоняем через DES на ключе K1, чтобы получить e, которую в свою очередь передаем в DES на ключе K3 (строка № 22) и получаем H₁ (первый обработанный блок входных данных).

Далее, берем этот H₁ и передаем как вектор инициализации для второго и последующих входных блоков, которые мы опять-таки шифруем на ключе K₁ (строка №25). Здесь мы получаем H_q, последние 8 байт которого надо зашифровать на ключе K2, чтобы получить g, который и есть наш MAC. Фух.

Ну и напоследок, в репозитории можете найти исходники и описание для запуска тестов, взятых из стандарта. Примечательно, что тест MAC 2 с паддинг-методом 2 падает:
ожидается 1736AC1A 63 630EFB,
получаем 1736AC1A 61 630EFB

Всем пока!

ISO 9797-1: поросячья латынь

Общая архитектура

Step 2: padding

padding method 1

padding method 2

padding method 3

padding method 4

Step 5: final iteration

Step 6: output transformation

MAC algorithm 1

MAC algorithm 2

MAC algorithm 3

MAC algorithm 4

Разработчик сжёг токенов на $157 143, заплатив за них $400

У крупнейшей в РФ сети фитнес‑клубов DDX утечка данных: в сети появились фотографии и персональные данные клиентов

Разработка через «ИИ» отбирает у программистов состояние потока?

Куда подевался старый веб? Мы прошли по 657 607 ссылкам, чтобы разобраться

Публикации