- PVSM.RU - https://www.pvsm.ru -
Недавно в институте я столкнулся с любопытной криптографической задачей, которой хотел бы поделиться с Сообществом. Так как русскоязычных примеров решения таких учебных «головоломок» встречается немного, а сама задача рекомендована для начинающих свой путь специалистов (не обладающих глубокими знаниями предмета), я считаю, что такая статья может быть интересна юному криптоаналитику. Пожалуйте под кат.
Байтовая подстановка $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-архитектуры лежит итеративное применение раундовой функции к блоку 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-архитектуры огромную роль играют подстановки – биективные отображения вида $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, на этом ресурсе это делали уже не один раз: например, можно почитать такие замечательные статьи как эта [1], вот эта [2], и конечно официальную документацию [3] шифра.
Я постараюсь воспроизвести ход решения данной задачи с точки зрения малоопытного криптографа (самого себя), чтобы показать логику размышлений в случае, когда абсолютно не знаешь, за что взяться с начала.
Очевидно, что ключевая особенность этой задачи – это уязвимая подстановка (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, как раз представляющая преобразование $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$.
Обратимся к [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$.
$$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$.
В результате для бит-ориентированного представления понадобится такая матрица (под спойлером).
( 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 )
И соответствующее преобразование примет вид $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$ можно легко получить с помощью алгебраического аппарата Sage:
sage: L = matrix(ZZ, [<наша_матрица_L>]).base_extend(GF(2))
sage: invL = L.inverse()
sage: invL14 = invL^{-14}
sage: invL14.str()
Небольшое программное демо, которое покажет «вживую», как проходит взлом, выложено на гитхабе [4].
Что можно сказать о задачах такого рода? Такие задачи являются отличным примером того, как такая, на первый взгляд, несущественная модификация оригинального алгоритма, как «кастомная» подстановка (которая даже на первый взгляд выглядит псевдослучайной, даже более того – проходит некоторую часть статистических тестов NIST'а! см. спойлер ниже) может выродить международный стандарт шифрования в тривиальное аффинное преобразование с известной матрицей.
Спасибо за внимание!
Автор: snovvcrash
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/265467
Ссылки в тексте:
[1] эта: https://habrahabr.ru/post/112733/
[2] эта: https://habrahabr.ru/post/212235/
[3] документацию: https://csrc.nist.gov/csrc/media/publications/fips/197/final/documents/fips-197.pdf
[4] гитхабе: https://github.com/snovvcrash/aes256m-cracker
[5] Источник: https://habrahabr.ru/post/339910/?utm_source=habrahabr&utm_medium=rss&utm_campaign=sandbox
Нажмите здесь для печати.