python

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

  • суббота, 14 октября 2017 г. в 03:13:31
https://habrahabr.ru/post/339910/
  • Математика
  • Криптография
  • Информационная безопасность
  • Python


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

image


Условие


Байтовая подстановка $\pi_8$ шифра AES-256 определяется некоторой последовательностью операций в поле $GF(2^8)$, и также может быть задана массивом из 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 бит).
Раундовая функция состоит из трех преобразований:

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

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

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

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


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

Процесс расшифрования выполняется с помощью обратных преобразований:

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

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


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


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

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

Решение


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

Разведка


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

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

# sboxm = [ <модифицированная_подстановка> ]
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 является результатом применения какой-либо линейной функции к диапазону чисел $\overline{0, 255}$.

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

$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&1\end{pmatrix}$ — двоичная матрица размера 8x8,

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

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

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

Генерируем вырожденные подстановки длины 2^n
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('\n\t', end='')
		for i in range(length):
			if not (i % dim) and i:
				print('\n\t', 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, как раз представляющая преобразование $S$ в LSX-шифре, теперь выглядит как $a \mapsto Ma \oplus v$, где $a$ — шифруемый блок, $M$ и $v$ описаны выше.

Следовательно, бит-ориентированное представление операции SubBytes пример вид:

$A \mapsto SB*A \oplus V$, где
$A$ — 128-битное представление блока $a$;

$SB = \begin{pmatrix}M&0&0&0\\0&M&0&0\\0&0&M&0\\...&...&...&...\\0&0&0&M\end{pmatrix}$; $V = \begin{pmatrix}v\\v\\v\\...\\v\end{pmatrix}$.

ShiftRows


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

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

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

MixColumns


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


Здесь потрудней: необходимо оригинальную MDS-матрицу над полем $GF(2^8)$ привести к эквивалентной форме над $GF(2)$. Для этого вспомним, что алгебраическая структура поля $GF(2^8)$ вытекает из рассмотрения кольца многочленов (переменной $x$) с коэффициентами из $GF(2)$ по модулю некоторого многочлена $f(x)$ степени 8 (a.k.a. фактор кольцо $GF(2)[x]/f(x)$). Для AES'а $f(x)=x^8 + x^4 + x^3 + 1$ — неприводимый над $GF(2)$ полином 8-й степени.

Далее: любой элемент из $GF(2^8)$ представим как сумма базисных $\{1, x, x^2, \dots, x^7\}$. Тогда запомним результаты умножения элемента $02 = x$ на все базисные:

$x * 1 = x;\\ x * x = x^2;\\ x * x^2 = x^3;\\ x * x^3 = x^4;\\ x * x^4 = x^5;\\ x * x^5 = x^6;\\ x * x^6 = x^7;\\ x * x^7 = x^8 (mod f(x)) = x^4 + x^3 + x + 1.$


Так как выполняется дистрибутивность по сложению и умножению, в совокупности с рассуждениями выше элемент $02$ можно представить в виде матрицы с коэффициентами из $GF(2)$:

$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&0\end{pmatrix}.$


Тогда очевидно, что элемент $01$ перейдет в единичную матрицу $C_1 = I_{8x8}$, а элемент $03$ перейдет в $C_3 = C_2 \oplus C_1$.

Для проверки наших рассуждений можно заглянуть в [2], где предлагается аналогичная матрица $C_2$ для бит-ориентированного умножения на элемент $02$ из $GF(2^8)$.

В результате, принимая во внимание то, что во время оригинальной трансформации MixColumns строка MDS-матрицы умножается на столбец состояния state, составим матрицу $MC$ для бит-ориентированного представления данной трансформации (под спойлером).

MC
( C2 00 00 00 C3 00 00 00 C1 00 00 00 C1 00 00 00 )
( 00 C2 00 00 00 C3 00 00 00 C1 00 00 00 C1 00 00 )
( 00 00 C2 00 00 00 C3 00 00 00 C1 00 00 00 C1 00 )
( 00 00 00 C2 00 00 00 C3 00 00 00 C1 00 00 00 C1 )
( C1 00 00 00 C2 00 00 00 C3 00 00 00 C1 00 00 00 )
( 00 C1 00 00 00 C2 00 00 00 C3 00 00 00 C1 00 00 )
( 00 00 C1 00 00 00 C2 00 00 00 C3 00 00 00 C1 00 )
( 00 00 00 C1 00 00 00 C2 00 00 00 C3 00 00 00 C1 )
( C1 00 00 00 C1 00 00 00 C2 00 00 00 C3 00 00 00 )
( 00 C1 00 00 00 C1 00 00 00 C2 00 00 00 C3 00 00 )
( 00 00 C1 00 00 00 C1 00 00 00 C2 00 00 00 C3 00 )
( 00 00 00 C1 00 00 00 C1 00 00 00 C2 00 00 00 C3 )
( C3 00 00 00 C1 00 00 00 C1 00 00 00 C2 00 00 00 )
( 00 C3 00 00 00 C1 00 00 00 C1 00 00 00 C2 00 00 )
( 00 00 C3 00 00 00 C1 00 00 00 C1 00 00 00 C2 00 )
( 00 00 00 C3 00 00 00 C1 00 00 00 C1 00 00 00 C2 )


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

Атака


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

Один раунд


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

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

$a \mapsto AddRoundKey(MixColumns(ShiftRows(SubBytes(a)))).$


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

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


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

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


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

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


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

$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.$


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

$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;$

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


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

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

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

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


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

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


Примечание


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

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


$L^{-14}$


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

Как это сделать
sage: L = matrix(ZZ, [ <наша_матрица_L> ]).base_extend(GF(2))
sage: invL = L.inverse()
sage: invL14 = invL^(-14)
sage: invL14.str()


Исходный код


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

Вывод


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

NIST Statistical Test Suite
Данная подстановка прошла:
  • Monobit Frequency Test
  • Block Frequency Test
  • Runs Test
  • Serial Test
  • Approximate Entropy Test
  • Cumulative Sums Test


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

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


  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