Как я научился криптоанализу с симметричным ключом


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

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

Давайте сначала отметим Поразительный факт, что блочный шифр DES, разработанный около 50 много лет назад, никогда не сломанный. Размер ключа (90 бит) был выбран преднамеренно и поэтому не учитывается. Линейный криптоанализ до некоторой степени работает, но в основном непрактичен. S-блоки DES в основном устойчивы к дифференциальному криптоанализу, что само по себе является очень интересным фактом – DES был сделан так, чтобы быть устойчивым к дифференциальному криптоанализу. Другие широко известные атаки, обнаруженные в следующие 50, не взломали DES.

Это демонстрирует простой факт о криптографии с симметричным ключом. Много лет назад исследователям удалось создать в основном устойчивый примитив с симметричным ключом 56. Смешивание независимых преобразований для устранения корреляции ввода-вывода оказалось не таким сложным, что, возможно, и не очень удивительный факт.

Теперь работа в криптоанализе полезна, потому что:

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

Когда это приводит к недостаткам:

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

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

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

Шаг 1. Решите, нравится ли вам криптовалюта с симметричным ключом

Цель здесь – понять, нравится вам это направление работы или нет. Во время 90 этот учебник увидел свет: «Курс самообучения по криптоанализу блочных шифров» . Автор B.Schneier.

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

  • 8-раундовый RC5 без каких-либо вращений
  • 8-раундовый RC5 с числом оборотов, равным количеству раунда.
  • 12 – круглый DES без каких-либо S-блоков
  • 8 раундов правила B Скипджека
  • 4 раунда DES
  • 6-этапный DES.

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

Шаг 2: Освойте несколько методов криптоаналитической атаки.

А теперь пора читать статьи. Это замечательный этап обучения. Большинство атак в криптоанализе происходят от дифференциального криптоанализа, линейного криптоанализа, алгебраического криптоанализа или каких-либо алгоритмических атак в стиле «разделяй и властвуй». Обучите себя этим типам атак как можно больше. Эти методы являются основой, но существует нескончаемый поток рекомбинаций, уточнений и вариантов. Лучший ресурс, с которым я столкнулся, это: «Методы симметричного криптоанализа» Д. Ховратовича. . Хотел бы я внимательно прочитать его на ранних этапах моей карьеры с симметричным ключом.

Изучите основы этих атак, прочитав статьи. Посмотрите конференции, такие как FSE, Asiacrypt, Africacrypt, Latincrypt, SAC, Indocrypt и сайт eprint IACR, и выберите наиболее эффективные усовершенствования этих методов. Поэкспериментируйте с этими вариантами атак в коде и получите четкое представление о том, как они работают.

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

Шаг 3: Опубликуйте статью в криптоанализе.

Ваша следующая цель – опубликовать доклад на криптоконференции. Пора надеть шляпу, напоминающую бюрократическую . Определите пару предлагаемых примитивов, которые имеют значение (например, они могут конкурировать в общедоступных усилиях по стандартизации, предлагаться для определенного типа среды и т. Д.). Посмотрите на вариант этих примитивов с уменьшенным количеством раундов и выясните, какая техника атаки работает лучше всего. Помните, что на предыдущем этапе вы узнали не только о том, как работают криптоаналитические методы, вы также ознакомились с документами конференции по симметричным ключевым словам и определили, какие методы атак лучше всего подходят с учетом конструкции определенного примитива (например, на основе ARX или S-box).

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

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

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

Эта фаза не является На самом деле речь идет не о получении потрясающего результата, а о тщательной оценке определенного метода атаки против цели, а также о том, как научиться писать статью и отправлять ее на конференцию. Когда вы пишете статью в LaTeX, убедитесь, что формат такой же, как и у других статей на этой конференции. Не допускайте, чтобы ваши ссылки в конце документа были испорчены (есть формат, которому следует следовать) или не содержали спецификации, не забудьте иметь раздел «В этой статье мы …» и структурировать свою статью должным образом. В общем, находясь в Риме, делайте то же, что и римляне.

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

Шаг 4: Найдите неизвестное

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

Мы считаем, что больше проверок безопасности или больше тестов ничего не изменили бы. Основная проблема заключалась в том, что рецензенты не знали, что искать.

Проект DASP использует эту цитату, чтобы мотивировать раздел, в котором обсуждается поиск неизвестных атак. Цитата предполагает, что исследователь безопасности просматривает список известных атак (как описано выше) и пытается их применить. В каком-то смысле это правильно. Чтобы заполнить распорядок дня, нужно начинать с чего-то существенного, и список известных техник – это всего лишь. Такой список также служит цели заполнения табелей рабочего времени в различных формах, например, суммирования ежедневной работы на работе.

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

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

Удачного поиска ошибок с симметричным ключом! Если бы я мог помочь на каком-либо этапе или помочь решить, имеет ли путешествие смысл в данных обстоятельствах, напишите мне, и я постараюсь помочь как могу.