Обеспечение безопасности в криптографических ключах от идеального к реальному (часть 2)
Обеспечение безопасности от идеального до реализованного в криптографических ключах (часть 1). Почему «длина ключа 128 бит» не обязательно означает «128 бит безопасности».
Часть 2: Атаки столкновения
Я просто дам определение двум методам атаки, которые в сочетании образуют атаки столкновений — атака дня рождения и атака «встреча посередине» — как мы их обычно называем.
Атака на день рождения
Как следует из названия, эта атака основана на парадоксе дня рождения, который выглядит примерно так: если у вас, скажем, 23 человека в комнате, вероятность дублирования дней рождения превышает 50%. Фактически, для этого парадокса требуется 23 человека, чтобы иметь вероятность > 50%. Эта атака основана на идее создания дубликатов или коллизий со скоростью, превышающей ожидаемую. Чтобы удовлетворить нашу цель, мы можем определить его просто, как:
Для N различных значений можно ожидать, что начальное столкновение произойдет в окрестности квадратного корня из N случайно выбранных значений. Вы просто ждете второго появления одного значения в одном и том же наборе значений.
Для тех, кто на самом деле анализирует основу для этой атаки, это не парадокс в том смысле, что он противоречит сам себе, будь то логически или что-то в этом роде. Это тем более парадоксально, что содержит правдивость математики, в которой есть противоречие тому, какой может быть естественная когнитивная реакция человека на проблему. Другими словами, кто-то может опасаться обоснованности проблемы с точки зрения того, насколько здравым является вывод, поэтому делая это случаем, «противоречащим общепринятому мнению», а не «противоречащим самому себе».
Атака «встреча посередине»
В отличие от своего родственника выше, эта атака основана на перекрытии двух наборов значений. Эта атака не только дает больше применимых преимуществ, но и гораздо более гибкая. Рассмотрим следующий сценарий:
Где N — все возможные значения, а P и Q — пары наборов элементов, можно предположить ожидание коллизии, когда PQ/N близко к 1, если вероятность совпадения равна 1/N. P, подобный Q, подобный квадратному корню из N, конечно, является границей дня рождения, которая наиболее эффективна.
Именно здесь в игру вступает гибкость атак типа «встреча посередине». Иногда простота поиска элементов для одного набора выше, чем для другого, что справедливо, если PQ подобен N.
Различия между этими двумя атаками очень просто очертить. Атаки по случаю дня рождения связаны с повторяющимся появлением одиночных значений в одном наборе, тогда как атаки типа «встреча посередине» демонстрируют практику перекрытия двух наборов.
Итак, почему мы обеспокоены этим?
Меньшие 128-битные ключи или аналогичные криптографические значения обеспечат нам n /2-битную безопасность, поэтому в случае 128-битных мы отображаем сложность 2^64, что намного ниже желаемого уровня безопасности. Это основная причина нашего беспокойства по поводу коллизий и их последствий при недостаточной длине ключа. В противном случае использование 128-битных ключей может быть не таким рискованным. Сложность, которую это накладывает, делает ее самой громоздкой проблемой, с которой приходится иметь дело, наряду со сложностями того, что нужно, чтобы получить правильную энтропию с первого раза. Итак, вот оно. Второй антагонист – коллизионная атака. Это верховая езда с энтропией, поэтому вам следует подходить к ним с одинаковой осторожностью.
Даже если мы можем обеспечить n битов энтропии для получения n битов безопасности, мы все равно должны добавить дополнительный ключевой материал на уровне режима работы, чтобы помешать эффективности атак столкновений. Это само по себе является угрозой безопасности из-за дополнительной сложности, которую мы не хотим навязывать нашему процессу принятия решений. В нашем случае гораздо проще добиться достаточной безопасности за счет простоты. Опять же, оставайтесь с большими клавишами. 256-бит, если можно. Я объясню это ниже.
Я уверен, что найдутся те, кто не найдет удовлетворения в выборе более простого пути, поэтому для всех вас рассмотрите следующую процедуру для использования n -битных ключей для обеспечения n -битной безопасности:
Во-первых, мы должны удовлетворять критерию криптографически надежного источника ключа, будь то псевдослучайный или производный от пароля (где сложность пространства ключа учитывается в рамках этикета выбора пароля). Таким образом, мы устанавливаем n для n измерений ключа к энтропии. Специальным добавлением дополнительного ключевого материала мы эффективно смягчаем влияние определенных атак столкновений, однако мы делаем это за счет излишней сложности. Кого волнует, успешно ли мы внедрили, казалось бы, посредственную систему безопасности. Мы совершили смертный грех криптографии — сложность. Тупик.
Почему 256-битные ключи лучше
Очевидно, что успешно развернуть 128-битный ключ довольно сложно. Не невозможно достичь 128-битной безопасности с помощью 128-битного ключа, но дело в том, что 256-битный ключ обладает гибкостью, позволяющей достичь этого уровня безопасности с гораздо большей простотой. Это довольно привлекательно, если принять во внимание цель нашей разработки и основную суть того, как мы хотим получить криптографическую защиту для начала — максимально упрощенным способом. Вот почему я предлагаю использовать 256-битные ключи. Простота почти всегда является самым консервативным выбором. Кроме того, почему бы не запрыгнуть на этот порожденный распродажами битовый вагон и не пожинать плоды безопасности в процессе?
Причина выбора 256-битных ключей проста. Криптографически эффективный, консервативно заботящийся о безопасности, гибкий, устойчивый к коллизиям и способный гораздо проще обеспечить 128-битную защиту при устранении проблемных энтропийных проблем. Они больше подходят для нашей цели дизайна. Помните, как мы определили уровень безопасности как желательно 128-битный? Ну, 256-битные ключи, сталкиваясь с методологией атаки столкновений, представляют сложность 2 ^ 128. Вот так. Насколько более удобной может быть безопасность для этой парадигмы? Это устанавливает короткое, но однозначно доказуемое золотое правило:
2n бит ключа для n бит безопасности.
Престижность тем, кто клянется этим правилом, поскольку это окончательное изображение покаяния от злых путей сложности. Что еще можно желать от утопической семантики, кроме доступного получения большей безопасности за счет большей простоты? Элис и Боб гордились бы тобой прямо сейчас.
Разрабатывая это правило с учетом 128-битной безопасности, вы обеспечиваете себе запас безопасности, который считается достаточным при сегодняшней криптографической позиции, а также вводите определяющий столп безопасности — простоту. По сравнению с любым другим подходом эта философия эмпирична.
Целью этого является указать, что безопасность зависит не только от длины вашего ключа, но и от его качества. В целях безопасности и простоты рекомендуется использовать 256-битные ключи. Конечно, в этом случае мы использовали ключ большего размера, но не только из-за его размера. Это обеспечивает простое качество, так как для получения ключа меньшего размера потребуется гораздо больше усилий. Это действительно беспроигрышная ситуация для нас.
Это яркий пример старой поговорки: «Важен не размер, а то, как вы используете то, что у вас есть».
Итак, за короткое время мы рассмотрели довольно много областей, от энтропии до атак столкновений. Поскольку мы приближаемся к прекращению, вам может быть интересно, была ли когда-нибудь тема; есть. По сути, это стратегия – консерватизм. Уровни безопасности являются одним из наиболее само собой разумеющихся аспектов криптографической безопасности. В этой статье рассматривается только один аспект этого, а именно длина ключа; столь же важно учитывать и другие аспекты, такие как длина блока. Однако обо всем по порядку, поэтому разумно начать этот поиск консерватизма с длины криптографического ключа. Будьте строги в том, откуда берутся ваши ключи, но не скупитесь на биты; для безопасности важны как безопасный источник вывода, так и достаточная длина.
Я оставлю вам два слова: напевайте, или напевайте, или, по крайней мере, вышивайте свой криптографический режим, для дальнейшего использования – энтропия и достаточно. Два колокола должны звенеть при мысли об этих словах. Нам нужна неопределенность; нам нужны случайные, непредсказуемые источники. Это соответствует ощущению максимальной «энтропии», какой мы хотим видеть наши ключи. Кроме того, мы хотим установить длину, которая соответствует цели прочности проекта, в смысле более консервативного подхода к атакам, чтобы наш уровень безопасности отображался более точно; чтобы получить то, что мы хотим, мы удваиваем это, что мы и используем. Когда мы говорим, что хотим установить рабочую нагрузку в 2^ n шагов, было бы неплохо иметь небольшую передышку. Это соответствует ощущению «достаточно», как мы хотим, побитово.
Нынешнее состояние дел прогрессировало, хотя и с некоторой долей регресса. Хотя сообщество, возможно, не восприняло ее так, как надеялось, академические круги за десятилетия энергичного анализа дали нам стратегические способы сделать криптографию искусством, удовлетворяющим обычные потребности на различных уровнях; это дало нам тактику, которая работает, даже если мы, в некотором смысле, ограничены младенчеством в разработке, когда сталкиваемся с неизвестным прогрессом в криптоанализе. Суть в том, что в реализованном, практическом мире наша цель — имитировать идеальный, теоретический мир в надежде, что наше предположение о безопасности достижимо с разумной точностью.
Мы узнали, что имитация идеального мира является побочным эффектом имитации идеального пользователя; неудача в реальном мире в большинстве случаев является результатом неудачи пользователя. Таким образом, важно, чтобы мы подходили к идеальным отметкам с идеальным мышлением; если мы этого не сделаем, система выйдет из строя. Легко разработать плохую криптографию; еще проще использовать плохую криптографию. Серьезность этого вопроса в том, что иногда это не очевидно; иногда это может быть даже неразличимо, пока не станет слишком поздно. Это перекликается с важностью идеального пользователя для создания политик, которые ни в какой форме не допускают послаблений в разработке и развертывании.
Чтобы иметь хоть какую-то мыслимую надежду на получение уровня безопасности, хотя бы близкого к нашей предполагаемой цели проектирования, все сводится к совершенству нашей стратегии и политики, от концептуализации до реализации; эта статья описывает небольшую иллюстрацию того, что должно быть среди того, к чему приближаются таким образом. Почему это так достойно пламенной проповеди? Видите ли, качество того, как мы используем криптографию, — это, в конечном счете, и есть практическая криптография. Хорошая безопасность зависит от правильного использования хорошей криптографии. Если оставить в стороне биты и цифры, это «ключ» к полезной криптографии. Это Евангелие.
Обеспечение безопасности в криптографических ключах от идеального к реализованному (часть 1). Почему «длина ключа 128 бит» не обязательно означает «128 бит безопасности».