Information Security
Cryptography
Python
Mathematics
12 October 2017

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

From Sandbox
Недавно в институте я столкнулся с любопытной криптографической задачей, которой хотел бы поделиться с Сообществом. Одним предложением задачу могу обозначить, как "Атака на 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$ к каждому байту блока;
$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, на этом ресурсе это делали уже не один раз: например, можно почитать такие замечательные статьи как эта, вот эта, и, конечно, официальную документацию шифра.

Решение


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

Разведка


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

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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Usage: python3 dc.py

from itertools import product


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

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

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

	return count_prob == length


if __name__ == '__main__':
	# sboxm = [ <модифицированная_подстановка> ]
	print(dc(sboxm))

И не удивляемся результату: оказывается, таблица имеет вырожденный вид – в каждой ее строке есть запись с вероятностью 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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Usage: python3 generate_affine_sbox.py <sbox_length>

import numpy as np
import random
import math
import sys

from itertools import product


# ----------------------------------------------------------
# ---------------------- 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, d in product( *([list(range(length))]*2) ):
		diff_table[c ^ d][sbox[c] ^ sbox[d]] += 1

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

	return count_prob == length


# ----------------------------------------------------------
# -------------------------- 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 + x + 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

+41
31.7k 122
Comments 3
Top of the day