Задачи по криптографии

Задачи по криптографии (Часть 1)

Если вы обладаете теоретическими знаниями в области криптографии и хотели бы применить свои навыки на практике, то данный пост именно для вас. Ребята с кафедры №42 «Криптология и кибербезопасность» Национального исследовательского ядерного университета «МИФИ» подготовили серию лабораторных работ по дисциплине «Криптографические средства обеспечения информационной безопасности».

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

Основы программирования криптографических алгоритмов

Приложение к лабораторной
Решение задач

В данной лабораторной работе предлагается изучить кодировку base64, научиться переводить данные в шестнадцатеричную систему, вспомнить операцию xor и режим шифрования ECB 🙂 Кроме того рассматривается атака на шифир xor - взлом XOR с повторяющимся ключом. Рассмотрим задания подробнее:

Задание 1.
Напишите код, конвертирующий hex представление массива байт в base64 представление, и код, проводящий обратное преобразование

Строка:

faea8766efd8b295a633908a3c0828b22640e1e9122c3c9cfb7b59b7cf3c9d448bf04d72cde3aaa0

После перекодирования в base64 должна представлять собой:

+uqHZu/YspWmM5CKPAgosiZA4ekSLDyc+3tZt888nUSL8E1yzeOqoA==

Задание 2.
Напишите функцию, которая принимает в качестве аргументов два буфера одинакового размера и возвращает их XOR

Строка:

8f29336f5e9af0919634f474d248addaf89f6e1f533752f52de2dae0ec3185f818c0892fdc873a69

после hex-декодирования и XOR со строкой:

bf7962a3c4e6313b134229e31c0219767ff59b88584a303010ab83650a3b1763e5b314c2f1e2f166

должна выдать строку:

305051cc9a7cc1aa8576dd97ce4ab4ac876af5970b7d62c53d495985e60a929bfd739ded2d65cb0f

Задание 3. XOR по одному символу.
К строке была применена операция XOR по 1 символу (все операции только с латинским символами в кодировке ASCII). XOR по одному символу - это операция, в которой над каждым байтом массива производится операция XOR с одним постоянным значением. Например, если массив состоит из 3 элементов [a,b,c], то после преобразования по d будет [xor(a,d),xor(b,d),xor(c,d)]. Найдите ключ и расшифруйте сообщение.

191f1911160b0c580c101d581d0e1114583f1914191b0c111b583d1508110a1d56

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

Задание 4. Детектирование XOR по одному символу
В архиве detectSingleCharacterXor 15 файлов. Возьмите файл с соответствующим вашему номеру в списке. В файле 60 строк, одна из них - результат шифрования XOR по одному символу.Определите ее и расшифруйте. Код из задания 3 должен вам в этом помочь.

Задание 5. XOR с повторяющимся ключом.
Эта операция проводит XOR каждого символа с соответствующим символом ключа. Реализуйте алгоритм.

Строка(55символов):

Never trouble about trouble until trouble troubles you!

С ключом(повторяющаяся строка «ICE», 55 символов):

ICEICEICEICEICEICEICEICEICEICEICEICEICEICEICEICEICEICEI

должна превратиться в строку:

726332c31653d312a3c21292c63242b2c303d63313b2c302b2f2069362b3d2a296937372636272526653d312a3c21292c3065302c3068

Задание 6. Взлом XOR с повторяющимся ключом.
В файле breakRepeatedKeyXor.txt находится зашифрованная строка в base64. Попробуйте взломать её

Задание 7.AES в режиме шифрования ECB.
Содержание файлаdecryptAesEcb.txt зашифровано AES-128-ECB и переведено в base64. Использован ключ:

YELLOW SUBMARINE

Расшифруйте сообщение. Если выполняете задание с использованием языка python, то используйте openssl. Воспользуйтесь любой удобной библиотекой, позволяющей работать с AES. Соответствующую документацию можно найти на сайте разработчика библиотеки.

Задание 8. Детектирование ECB.
В файле detectEcb.txt находятся строки в hex. Одна из них - результат шифрования в режиме ECB, размер блока - 16 байт. Определите эту строку. Напоминаем, проблема с ECB в том, что он не использует состояния и вывод всегда детерминирован: одни и те же 16 байтов открытого текста при одном ключе всегда произведут те же 16 байтов зашифрованного текста.

Атаки на режимы шифрования ECB и CBC

Приложение к лабораторной
Решение задач

В данной лабораторной работе будет изучен PKCS7 padding, unpading, будут рассмотрены различные атаки на режимы шифрования ECB и CBC

Задание 1. Реализация дополнения блока до нужной длины по стандарту PKCS7.
По стандарту PKCS7 каждый блок открытого текста дополняется байтами, значением которых является количество недостающих байт до длины блока. Пусть N = 20 - длина блока. Тогда при открытом тексте

YELLOW SUBMARINE

длинной L = 16, количество недостающих байт равно N - L = 20 - 16 = 4. Следовательно, необходимо дополнить строку байтами со значением 04. Итоговая строка:

YELLOW SUBMARINE\x04\x04\x04\x04

где "\x04" - символическое обозначение байта со значением 04. Реализуйте функцию, принимающую 2 параметра - строку и размер блока, выполняющую дополнение блока по стандарту PKCS7.

Задание 2. Проверка дополнения PKCS7
Необходимо написать функцию, которая проверяет правильным ли образом составлено PKCS7 дополнение из задания 1 и если правильно, отрезает из строки лишние байты. Например, строка:

ICEICEBABY\x04\x04\x04\x04

имеет правильное дополнение,и результат работы функции должен выглядеть как

ICEICEBABYА

строки

ICEICEBABY\x05\x05\x05\x05

ICEICEBABY\x01\x02\x03\x04

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

Задание 3. Атака на CBC режим. Bit-flipping

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

comment1=cooking%20MCs;userdata=

и в конец строку

;comment2=%20like%20a%20pound%20of%20bacon

Так же должна присутствовать фильтрация входной строки на символы "=" ";". Далее функция полностью шифрует в режиме AES-128-CBC достроенную строку.

3. Задача - необходимо изменить шифртекст (результат Функции1), не зная ключа, таким образом, чтобы после расшифрования там находилась подстрока admin=true. Реализуем функцию, которая будет расшифровывать получившуюся строку и искать в ней подстроку admin=true.

CBC имеет следующие особенности:
1. При изменении 1 бита в текущем блоке,расшифрованный блок сильно изменяется.
2. В следующем блоке расшифрованного текста возникает ошибка в 1 бит на соответствующей позиции

Задание4. Функция детектирования режима ECB.

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

1. Реализуйте функцию,которая шифрует данные на случайном ключе, то есть функция генерирует случайные 16 байт ключа и шифрует на них, используя AES-128 в режимах ECB, CBC.
2. Сделайте так, чтобы функция шифровала входную строку с вероятностью 50% в режиме ECB, и с вероятностью 50 % в режиме CBC.
3. В теле функции перед шифрованием добавьте к inputStr случайное количество (5-10) байт в начало строки и в конец.
4. Реализуйте функцию, которая будет детектировать в каком режиме было зашифровано ваше сообщение.

Задание 5.Побайтовое дешифрование режима ECB или почему не стоит пользоваться ECB.

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

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

unknownStrBase64="Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkgaGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBqdXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUgYnkK"

Это строка в Base64. Предварительно нужно автоматически декодировать эту строку. Не смотрите на результат декодирования. Идея в том, что вы не должны знать ее содержание.

3. Итак, у Вас есть функция следующего вида

AES_128_ECB(your_string || decodeBase64(unknownStrBase64), random-key)

Теперь нужно написать функцию которая с помощью вашей входной строки (your_string) расшифровывает неизвестную строку (unknownStrBase64)

4. Как же это сделать...
a) Сначала необходимо детектировать длину блока, хотя мы это и знаем, все равно это будет полезно: Для этого в your_string передается строка состоящая из одинаковых байт: "A" "AA" "AAA" и так далее... пока не поймем какой будет размер блока.
б) Теперь, когда мы знаем размер блока, необходимо подать в переменную your_string строку на один байт(символ) короче, чем блок. Например, если длина блока 8 байт, то мы подаем строку "ААААААА" длиной 7. Как вы должны догадаться, на последнее место встанет первый символ неизвестной строки(unknownStr).
в) Теперь нужно перебрать все возможные варианты этого последнего байта и сравнить с выходным результатом из пункта б). Для этого нужно осуществить перебор по всем возможным символам по размеру блока. Пусть размер блока 8, тогда входная строка должна быть "АААААААА" "АААААААB" "АААААААC" и так далее...
г) Итак, мы получили первый байт (символ) неизвестной строки, теперь необходимо сделать тоже самое для остальной строки. Пусть первый символ будет "E". Так для второй строки, при размере блока 8, перебор всех возможных значений последнего байта будет осуществляется по строке "ААААААE*", то есть "ААААААЕА" "ААААААEB" и так далее.
д) Оцените трудоемкость дешифрования сообщения.

Задание 6. Подмена шифртекста, зашифрованного в режиме ECB
1. Первое, что нужно сделать, это написать функцию,которая будет переводить строку в объект, пусть дана строка в формате

foo=bar&baz=qux&zap=zazzle

Данную строку необходимо преобразовать в объект, то есть на выходе получить объект:

{foo: 'bar',baz: 'qux',zap: 'zazzle'}

2. Далее напишем функцию profile_for(email), которая:
а) принимает на вход строку с почтой;
б) генерирует объект профиля;
в) кодирует его в строку и возвращает пользователю.

Например:

profile_for("foo@bar.com") {
email: 'foo@bar.com',
uid: 10,
role: 'user'
}

кодируем его в строку:

email=foo@bar.com&uid=10&role=user

Заметим, что в строку email нельзя передавать символы "&" "=" и прочие символы,которые не содержатся в почтовом адресе.
3. Теперь зашифруем получившуюся строку в режиме ECB с неизвестным, далее неизменным, ключом.
4. Теперь получившийся шифртекст нужно изменить так, чтобы после расшифрования получилось

{
email: 'foo@bar.com,
uid: 10,
role: 'admin'
}

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

Задание 7.
Усложним задачу. Модифицируем функцию из задания 5, пусть теперь в начало строки добавляется случайное количество байт.Таким образом, функция выглядит так:

AES_128_ECB(random_prefix||your_string||decodebase64(unknowStrBase64),random_key)

где random_prefix - случайное количество байт. Задача - расшифровать unknowStrBase64.