Crypto в CTF

ТИПЫ ЗАДАНИЙ
Расшифровать текст
Заставить сервер выплюнуть флаг (или как-то по другому извлечь информацию о флаге с сервера)
Подобрать пароль
...

С ЧЕГО НАЧАТЬ?
Анализ того, что дано
Описание таска и его основное содержание
Разобрать какие криптопримитивы используются и зачем
Попытаться понять, в чем состоит твоя задача
Если криптопримитив реализован, то сравнить реализацию со стандартом (в интернетах)

Что такое криптография?

Свойства информации, обеспечиваемые криптографией
Конфиденциальность
Целостность
Аутентичность

Конфиденциальность
Конфиденциальность - секретность информации. Обеспечивается с помощью шифров.
Шифр - пятерка (X, Y, K, E, D), где
X - множество открытых текстов,
Y - множество закрытых текстов,
K - множество ключей,
E: X x K -> Y,
D: Y x K -> X,
D(E(x)) = x.
Примеры: Одноалфавитная замена, Шифр Виженера, RC4, AES, RSA, ...

Целостность
Целостность информации - свойство информации, позволяющее проверять, находится ли информация в изначальном виде или нет. Обеспечивается с помощью хэш-функций, кодов аутентификации сообщений(MAC), цифровых подписей.

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

Хэш-функции
Хэш-функция - тройка (X, Y, H)
X - множество сообщений, имеют произвольную длину
Y - множество хэшей. Все хэши имеют фиксированную длину
H: X -> Y - функция
Для криптографии используются хэш-функции, обладающие свойствами:
Необратимость
Стойкость к коллизиям
Примеры: md5(уже нет), sha1, sha256, sha512

Одноалфавитная замена
X - множество текстов букв из алфавита А
Y - множество текстов букв из алфавита B
K - множество подстановок из A в B
E(x) = k(x), k принадлежит K
D(x) = k*(x), k* принадлежит K*, множеству подстановок из B в A

Одноалфавитная замена

Аффинный шифр

Шифр Виженера

Другие шифры классической криптографии
Решетка Кардано, омофоническая замена, сцитала, столбцовая перестановка, ....
Подробнее - Сингх “Книга шифров”

Блочные шифры
Блочные шифры - вид шифров, обрабатывающий за одну итерацию блок из нескольких байт.
Текст должен быть разделен на блоки одинаковой длины. Соответственно, длина текста должна быть кратна длине блоков. Для того, чтобы этому соответствовать используется padding.
Примеры шифров: AES, DES

Поточные шифры
Поточные шифры - вид шифров, обрабатывающий за одну итерацию один байт(бит) путем сложения по модулю 2 с байтом(битом) гаммы.
Гамма как правило есть псевдослучайная последовательность байт, вырабатываемая генератором ключевого потока.
Текст может быть произвольной длины.
Примеры шифров: RC4, Salsa20

Блочные шифры. Режимы шифрования
ECB

Блочные шифры. Режимы шифрования
CBC

Блочные шифры. Режимы шифрования
CTR

Атаки на блочные шифры
Часто встречаются в CTF:
Атаки на шифрование и расшифрование по сторонним каналам ( padding oracle attack, compression attack, ....)
Использование шифра не по назначению (например, использование шифра для обеспечения целостности зашифрованного сообщения)
....

Атаки на поточные шифры
Часто встречаются в CTF:
Атаки с известным открытым текстом
Использование шифра не по назначению (например, использование шифра для обеспечения целостности зашифрованного сообщения)
Использование слабых генераторов ключевого потока
....

Немного о хэш-функциях

Атаки на хэш-функции
атаки по словарю
length-extension attack
поиск элемента из прообраза(для хэша U такого V, что H(U) = V), поиск коллизий - годится только для криптографически нестойких функций
...

Немного о криптографии с открытым ключом

RSA

РАБОЧАЯ СРЕДА
Python (или любой другой скриптовый язык)
Sage, libnum, pycrypto, …
Онлайн-сервисы (в интернетах, например http://www.cryptoclub.org/)
ручка с тетрадкой :)

С ЧЕГО НАЧАТЬ?
Анализ того, что дано
Описание таска и его основное содержание
Разобрать какие криптопримитивы используются и зачем
Попытаться понять, в чем состоит твоя задача
Если криптопримитив реализован, то сравнить реализацию со стандартом (в интернетах)