Ломаем модифицированный AES-256

Недавно в институте я столкнулся с любопытной криптографической задачей, которой хотел бы поделиться с Сообществом. Так как русскоязычных примеров решения таких учебных «головоломок» встречается немного, а сама задача рекомендована для начинающих свой путь специалистов (не обладающих глубокими знаниями предмета), я считаю, что такая статья может быть интересна юному криптоаналитику. Пожалуйте под кат.

Условие

Байтовая подстановка $inline$pi_8$inline$ шифра AES-256 определяется некоторой последовательностью операций в поле $inline$GF(2^8)$inline$, и также может быть задана массивом из 256 байт:

63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

Определим модифицированный вариант шифра – «AES-256-М», который будет отличаться от оригинального только подстановкой, а именно:

2b c4 4d a2 76 99 10 ff 56 b9 30 df 0b e4 6d 82
db 34 bd 52 86 69 e0 0f a6 49 c0 2f fb 14 9d 72
95 7a f3 1c c8 27 ae 41 e8 07 8e 61 b5 5a d3 3c
65 8a 03 ec 38 d7 5e b1 18 f7 7e 91 45 aa 23 cc
cb 24 ad 42 96 79 f0 1f b6 59 d0 3f eb 04 8d 62
3b d4 5d b2 66 89 00 ef 46 a9 20 cf 1b f4 7d 92
75 9a 13 fc 28 c7 4e a1 08 e7 6e 81 55 ba 33 dc
85 6a e3 0c d8 37 be 51 f8 17 9e 71 a5 4a c3 2c
6f 80 09 e6 32 dd 54 bb 12 fd 74 9b 4f a0 29 c6
9f 70 f9 16 c2 2d a4 4b e2 0d 84 6b bf 50 d9 36
d1 3e b7 58 8c 63 ea 05 ac 43 ca 25 f1 1e 97 78
21 ce 47 a8 7c 93 1a f5 5c b3 3a d5 01 ee 67 88
8f 60 e9 06 d2 3d b4 5b f2 1d 94 7b af 40 c9 26
7f 90 19 f6 22 cd 44 ab 02 ed 64 8b 5f b0 39 d6
31 de 57 b8 6c 83 0a e5 4c a3 2a c5 11 fe 77 98
c1 2e a7 48 9c 73 fa 15 bc 53 da 35 e1 0e 87 68

Задача. Имеется шифртекст длиной 5120 бит (40 блоков), который был получен шифрованием открытого текста шифром «AES-256-М» в режиме простой замены на неизвестном ключе. Известен первый блок открытого текста. Предложить осуществимый на практике способ вскрытия неизвестной части шифртекста.

Теоретическое введение

Рассмотрим общую структуру LSX-шифров, одним из представителей которых является AES Rijndael.

Структура LSX-шифра

В основе шифров LSX-архитектуры лежит итеративное применение раундовой функции к блоку a преобразуемого текста (длина блока a для большинства современных шифров – 128 бит).
Раундовая функция состоит из трех преобразований:
$inline$X$inline$ — сложение по модулю 2 входного блока с итерационным ключом $inline$K_i$inline$ ($inline$i=overline{1, r}$inline$, где $inline$r$inline$ – число раундов шифра);
$inline$S$inline$ — применение фиксированной подстановки $inline$pi_8$inline$ к каждому байту блока;
$inline$L$inline$ — линейное преобразование.

Схематично LSX-преобразование можно представить как

В каждом раунде LSX-шифра используется отдельный раундовый ключ $inline$K_i$inline$ некоторым образом формируемый из первичного ключа $inline$K$inline$. Битовая длина первичного ключа $inline$K$inline$ обычно равна длине итерационного ключа или превосходит её. Процедуры ключевой развертки итерационных ключей из первичного существенным образом отличаются у различных шифров.

Общая формула шифрующего преобразования $inline$Enc(K, a)$inline$ для LSX-шифра с числом раундов, равным $inline$r$inline$, может быть записана в следующем виде:

$$display$$b = Enc(K, a) = X[K_r]LSX[K_{r-1}]...LSX[K_2]LSX[K_1](a)$$display$$

Схематично общую структуру LSX-шифра можно представить как

Процесс расшифрования выполняется с помощью обратных преобразований:
$inline$X$inline$ — сложение по модулю 2 входного блока с итерационным ключом;
$inline$S^{-1}$inline$ — применение обратной к $inline$S$inline$ подстановки;
$inline$L^{-1}$inline$ — применение обратного $inline$L$inline$-преобразования ($inline$SS^{-1}=I$inline$ – единичная подстановка).
Формула для расшифрования $inline$Dec(K, b)$inline$ $inline$r$inline$-раундового LSX-шифра:

$$display$$a = Dec(K, b) = X[K_1]S^{-1}L^{-1}X[K_2]...S^{-1}L^{-1}X[K_r](b)$$display$$

Подстановки в LSX-шифрах

В шифрах LSX-архитектуры огромную роль играют подстановки – биективные отображения вида $inline$pi_n : V^n_2 rightarrow V^2_n$inline$, где $inline$V_2 = {0, 1}, V^n_2 = {0, 1}^n$inline$. Неудачно выбранная подстановка может привести к снижению стойкости всего шифра, а в худшем случае к применимой на практике атаке на шифр.

Не буду поэтапно разбирать сам алгоритм AES-256, на этом ресурсе это делали уже не один раз: например, можно почитать такие замечательные статьи как эта, вот эта, и конечно официальную документацию шифра.

Решение

Я постараюсь воспроизвести ход решения данной задачи с точки зрения малоопытного криптографа (самого себя), чтобы показать логику размышлений в случае, когда абсолютно не знаешь, за что взяться с начала.

Разведка

Очевидно, что ключевая особенность этой задачи – это уязвимая подстановка (S-box), поэтому мое исследование проблемы началось с построения таблицы дифференциальных характеристик. Несмотря на то, что классический дифференциальный метод является непрактичным по отношению к AES-like шифрам (число раундов слишком велико), некоторую полезную информацию о модифицированном S-box'е можно попытаться извлечь.

Итак, строим таблицу:

length = len(sboxm)

diff_table = [[0] * length for _ in range(length)]
for c in range(length):
	for d in range(length):
		diff_table[c ^ d][sboxm[c] ^ sboxm[d]] += 1

count_prob = 0
for c in range(1, length):
	for d in range(1, length):
		if diff_table[c][d] == length:
			count_prob += 1
		print('{} : {} -> {}'.format(diff_table[c][d], c, d))

return count_prob == length - 1

И не удивляемся результату: оказывается, таблица имеет вырожденный вид – в каждой ее строке есть запись с вероятностью 256/256 (остальные записи соответственно равны 0).

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

Из базового курса криптографии известно, что основная роль S-box'а в блочном шифре, заключается во внесении нелинейности в криптограмму (другими словами, в максимальном сокрытии статистической связи между открытым текстом и шифртекстом), и раз данный нам S-box является уязвимым местом AES-256-M, можно предположить, что он не выполняет свою целевую функцию. Значит, скорее всего, этот S-box является результатом применения какой-либо линейной функции к диапазону чисел $inline$overline{0, 255}$inline$.

Экспериментальным методом выясняем, что в роли генератора подстановки выступила простая аффинная функция вида $inline$f(x) = Mx oplus v$inline$, где

$inline$M = begin{pmatrix}0&1&1&1&0&0&0&1\1&1&0&1&1&1&1&1\0&1&1&1&1&0&1&1\0&0&1&1&1&1&0&0\0&0&1&0&1&1&0&1\1&0&1&0&1&1&1&1\0&0&1&0&0&0&1&1\0&0&0&0&1&1&0&1end{pmatrix}$inline$ — двоичная матрица размера 8x8,

$inline$v = begin{pmatrix}0&0&1&0&1&0&1&1end{pmatrix}$inline$ — двоичный 8-битный вектор-строка.

Таким образом, наше предположение оказалось верным: если представить байты подстановки в виде двоичных векторов, то модифицированная подстановка превращается в представленное выше аффинное преобразование с линейной зависимостью между входным и выходным набором бит.

Теперь даже можно написать небольшой скрипт для генерации таких подстановок.

import numpy as np
import random
import math
import sys

# ----------------------------------------------------------
# ---------------------- AFFINE SBOX -----------------------
# ----------------------------------------------------------

"""
Affine function: y(x) = M*x + v, where
                 M is 8x8 boolean matrix,
	             v is 8-bit constant vector column,
	             * is bitwise AND (&),
	             + is bitwise XOR (^).
"""

def affine_function(x, M, v):
	Mx = (np.dot(M, x) % 2).T
	y = Mx ^ v
	return y

def S(x, M, v, bin_length):
	raw_value = list(affine_function(to_bin(x, bin_length), M, v).flat)
	return int(''.join([ str(b) for b in raw_value ]), 2)

def generate_affine_sbox(length):
	bin_length = len(bin(length-1)[2:])

	np.random.seed()
	while True:
		M = np.random.randint(0, 2, size=(bin_length, bin_length))
		if np.linalg.det(M).astype(int) % 2:
			break

	v = np.random.randint(0, 2, size=(1, bin_length))

	sbox = [ S(i, M, v, bin_length) for i in range(length) ]
	if not any_duplicates(sbox) and is_sbox_degenerate(sbox):
		return (sbox, M, v)
	return (None, None, None)

# ----------------------------------------------------------
# ----------------------- UTILITIES ------------------------
# ----------------------------------------------------------

def to_bin(number, bin_length):
	return np.array([ [int(b)] for b in bin(number)[2:].zfill(bin_length) ])

def print_sbox(name, sbox, length):
	dim = math.sqrt(length)
	print('{} = {{'.format(name), end='')

	if dim.is_integer():
		print('nt', end='')
		for i in range(length):
			if not (i % dim) and i:
				print('nt', end='')
			print('{: >5}'.format(sbox[i]), end=', ')
		print('.n}')
	else:
		for item in sbox:
			print(item, end=', ')
		print('.}')

def any_duplicates(sbox):
	seen = set()
	for item in sbox:
		if item not in seen:
			seen.add(item)
		else:
			return True
	return False

def is_sbox_degenerate(sbox):
	length = len(sbox)

	diff_table = [[0] * length for _ in range(length)]
	for c in range(length):
		for d in range(length):
			diff_table[c ^ d][sbox[c] ^ sbox[d]] += 1

	count_prob = 0
	for c in range(1, length):
		for d in range(1, length):
			if diff_table[c][d] == length:
				count_prob += 1
			# print('{} : {} -> {}'.format(diff_table[c][d], c, d))

	return count_prob == length - 1

# ----------------------------------------------------------
# -------------------------- MAIN --------------------------
# ----------------------------------------------------------

if __name__ == '__main__':
	if len(sys.argv) != 2:
		print('usage: python3 {} <sbox_length>'.format(sys.argv[0]))
		sys.exit(1)

	try:
		length = int(sys.argv[1])
	except ValueError:
		print("Invalid input type")
		sys.exit(1)

	if length & (length-1) != 0 or length < 1:
		print("Sbox length must be a power of two and > 1")
		sys.exit(1)

	while True:
		sbox, M, v = generate_affine_sbox(length)
		if sbox:
			print('M = n{}n'.format(repr(M)))
			print('v = n{}n'.format(repr(v)))
			print_sbox('Affine Sbox', sbox, length)
			break

Подготовка к атаке

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

Найдем альтернативное бит-ориентированное представление всех линейных преобразований шифра AES Rijndael такое, чтобы было возможно «встроить» линейную теперь операцию применения подстановки к каждому байту блока в одну большую линейную трансформацию.

SubBytes

Операция SubBytes, как раз представляющая преобразование $inline$S$inline$ в LSX-шифре, теперь выглядит как $inline$a mapsto Ma oplus v$inline$, где $inline$a$inline$ — шифруемый блок, $inline$M$inline$ и $inline$v$inline$ описаны выше.

Следовательно, бит-ориентированное представление операции SubBytes пример вид:
$inline$A mapsto SB*A oplus V$inline$, где
$inline$A$inline$ — 128-битное представление блока $inline$a$inline$;

$inline$SB = begin{pmatrix}M&0&0&0\0&M&0&0\0&0&M&0\...&...&...&...\0&0&0&Mend{pmatrix}$inline$; $inline$V = begin{pmatrix}v\v\v\...\vend{pmatrix}$inline$.

ShiftRows

Обратимся к [1] для определения матрицы, отвечающей за операцию ShiftRows. Эта матрица имеет следующий вид:

$inline$SR = begin{pmatrix}I_{32x32}&0&0&0\0&R^2&0&0\0&0&R^3&0\0&0&0&R^4end{pmatrix},$inline$ где $inline$R = begin{pmatrix}0&I_{8x8}&0&0\0&0&I_{8x8}&0\0&0&0&I_{8x8}\I_{8x8}&0&0&0end{pmatrix}.$inline$

И преобразование ShiftRows принимает вид $inline$A mapsto SR*A$inline$.

MixColumns

$$display$$MDS = begin{pmatrix}02&03&01&01\01&02&03&01\01&01&02&03\03&01&01&02end{pmatrix}$$display$$

Здесь потрудней: необходимо оригинальную MDS-матрицу над полем $inline$GF(2^8)$inline$ привести к эквивалентной форме над $inline$GF(2)$inline$. Для этого обратимся к [2] и увидим, что элемент $inline$01$inline$ над $inline$GF(2^8)$inline$ преобразуется в матрицу единичную матрицу 8x8 над $inline$GF(2)$inline$, элемент $inline$02$inline$ принимает вид следующей матрицы над $inline$GF(2)$inline$

$$display$$C_2 = begin{pmatrix}0&1&0&0&0&0&0&0\0&0&1&0&0&0&0&0\0&0&0&1&0&0&0&0\1&0&0&0&1&0&0&0\1&0&0&0&0&1&0&0\0&0&0&0&0&0&1&0\1&0&0&0&0&0&0&1\1&0&0&0&0&0&0&0end{pmatrix},$$display$$

а элемент $inline$03$inline$ перейдет в $inline$C_3 = C_2 oplus C_1 = C_2 oplus I$inline$.

В результате для бит-ориентированного представления понадобится такая матрица (под спойлером).

И соответствующее преобразование примет вид $inline$A mapsto MC*A$inline$.

Атака

Анализ практически завершен, подготовим все необходимое для атаки.

Один раунд

Рассмотрим один раунд шифра AES-256-M.

В стандартном виде:

$$display$$a mapsto AddRoundKey(MixColumns(ShiftRows(SubBytes(a))))$$display$$

В матричном виде над $inline$GF(2)$inline$:

$$display$$A mapsto MC*SR*(SB*A oplus V) oplus K_i = MC*SR*SB*A oplus MC*SR*V oplus K_i,$$display$$

но так как $inline$MC*V = SR*V = V$inline$, то

$$display$$A mapsto MC*SR*SB*A oplus V oplus K_i = L*A oplus V oplus K_i,$$display$$

где $inline$L = MC*SR*SB$inline$ — матрица, представляющая весь линейный рассеивающий слой AES-256-M.

Несколько раундов

Рассмотрим 15 раундов (14 + раунд инициализации ключом) шифра AES-256-M в матричном виде:

$$display$$L(L(L( ... L(P_0 oplus K_0 ) oplus K_1 oplus V ) oplus K_2 oplus V ) oplus dots oplus K_{13} oplus V) oplus K_{14} oplus V) = C_0$$display$$

Раскроим скобки:

$$display$$L^{14}P_0 oplus L^{14}K_0 oplus L^{13}K_1 oplus L^{13}V oplus dots oplus LK_{13} oplus LV oplus K_{14} oplus V = C_0;$$display$$

$$display$$L^{14}P_0 oplus (L^{13} oplus L{12} oplus dots oplus L oplus I)V oplus mkey = C_0,$$display$$

где $inline$mkey = L^{14}K_0 oplus L^{13}K_1 oplus L^{12}K_2 oplus dots oplus LK_{13} oplus K_{14}$inline$ — условный «мастер-ключ», который можно использовать для дешифрования других блоков (т. к., шифрование проводится в режиме ECB):

$$display$$mkey = C_0 oplus L^{14}P_0 oplus (L^{13} oplus L{12} oplus dots oplus L oplus I)V;$$display$$

$$display$$P_i = L^{-14}(C_i oplus mkey oplus (L^{13} oplus L{12} oplus dots oplus L oplus I)V) =$$display$$

$$display$$= L^{-14}(C_i oplus C_0 oplus L^{14}P_0) = P_0 oplus L^{-14}(C_i oplus C_0);$$display$$

И вот та самая «магическая» формула для дешифровки остальных блоков шифртекста, из-за который мы сегодня собрались:

$$display$$P_i = P_0 oplus L^{-14}(C_0 oplus C_i).$$display$$

Примечание

В оригинальной реализации AES Rijndael операция MixColumns опущена на последнем раунде шифра в силу своей бесполезности на этом этапе. В данном решении это не учитывается (т. е. MixColumns используется и после сложения с последним раундовым ключом) для упрощения демонстрации результата.

Заключение, код, литература

$inline$L^{-14}$inline$

Сперва хотелось бы отметить, что матрицу $inline$L^{-14}$inline$ можно легко получить с помощью алгебраического аппарата Sage:

sage: L = matrix(ZZ, [<наша_матрица_L>]).base_extend(GF(2))
sage: invL = L.inverse()
sage: invL14 = invL^{-14}
sage: invL14.str()

Исходный код

Небольшое программное демо, которое покажет «вживую», как проходит взлом, выложено на гитхабе.

Вывод

Что можно сказать о задачах такого рода? Такие задачи являются отличным примером того, как такая, на первый взгляд, несущественная модификация оригинального алгоритма, как «кастомная» подстановка (которая даже на первый взгляд выглядит псевдослучайной, даже более того – проходит некоторую часть статистических тестов NIST'а! см. спойлер ниже) может выродить международный стандарт шифрования в тривиальное аффинное преобразование с известной матрицей.

Спасибо за внимание!

Список литературы

1. Algebraic Aspects of the Advanced Encryption Standard by Carlos Cid, Sean Murphy, Matthew Robshaw
2. Advances in Cryptology — CRYPTO 2015 – 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part 1

Автор: snovvcrash

Источник