Главная » Хабрахабр » [Перевод] Криптография после высадки инопланетян

[Перевод] Криптография после высадки инопланетян

Автор статьи: Брюс Шнайер — американский криптограф, писатель и специалист по компьютерной безопасности. Автор нескольких книг по безопасности, криптографии и ИБ. Основатель криптографической компании Counterpane Internet Security, Inc., член совета директоров Международной ассоциации криптологических исследований и член консультативного совета Информационного центра электронной приватности.

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

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

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

Добавление одного бита ключа увеличивает сложность шифрования менее чем на процент (грубо говоря), но удваивает сложность взлома. С симметричной криптографией, используемой для шифрования сообщений, файлов и дисков, этот дисбаланс экспоненциален и усиливается по мере увеличения ключей. Таким образом, 256-битный ключ кажется лишь вдвое сложне, чем 128-битный, но (с нашими текущими знаниями математики) его в 340 282 366 920 938 463 463 374 607 431 768 211 456 раз сложнее сломать.

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

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

По своей природе они хорошо приспособлены к вычислениям, которые необходимы для обращения этих односторонних функций. Квантовые компьютеры обещают изменить многое из этого. Алгоритм Гровера показывает, что квантовый компьютер ускоряет атаки настолько, что эффективная длина ключа уменьшается вдвое. Для симметричной криптографии это не так уж плохо. То есть 256-битный ключ так же сложен для квантового компьютера, как 128-битный ключ для обычного компьютера: оба они безопасны в обозримом будущем.

Алгоритм Шора легко ломает все популярные алгоритмы с открытым ключом, основанные как на факторизации, так и на дискретном логарифмировании. Для криптографии с открытым ключом результаты страшнее. Этого недостаточно для устойчивого развития. Удвоение длины ключа увеличивает сложность взлома в восемь раз.

Мы также не знаем, какие практические трудности возникнут, когда мы попытаемся реализовать алгоритмы Гровера или Шора на чём-нибудь кроме ключей игрушечного размера (механизм коррекции ошибок на квантовом компьютере легко может стать непреодолимой проблемой). По поводу двух последних абзацев есть много оговорок, главная из которых заключается в том, что квантовые компьютеры, способные делать что-либо подобное, в настоящее время не существуют, и никто не знает, когда мы сможем построить такой — и сможем ли вообще. Я ставлю на то, что мы преодолеем инженерные проблемы, и что будет много достижений и новых методов, но понадобится время, чтобы их изобрести. С другой стороны, мы не знаем, какие ещё методы будут обнаружены, как только люди начнут работать с настоящими квантовыми компьютерами. Так же, как нам потребовались десятилетия, чтобы сконструировать карманные суперкомпьютеры, потребуются десятилетия, чтобы проработать все инженерные проблемы, необходимые для создания достаточно мощных квантовых компьютеров.

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

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

Это станет огромным ударом по безопасности и сломает многие системы, но мы сможем адаптироваться. Если это произойдёт, мы останемся в мире без криптографии с открытым ключом. И сейчас стандарт сотовой связи GSM выполняет как аутентификацию, так и распределение ключей — в большом масштабе — только с симметричной криптографией. В 1980-х годах Kerberos была полностью симметричной системой аутентификации и шифрования. (Представьте, что пара участников связи получает часть ключа сеанса от каждого из пяти различных серверов ключей). Да, эти системы имеют централизованные точки доверия и отказа, но можно разработать другие системы, которые используют как секретное разделение, так и секретное совместное использование, чтобы свести к минимуму этот риск. Мы можем использовать внеполосные протоколы: например, ваш телефон поможет сгенерировать ключ для компьютера. Повсеместное распространение коммуникаций облегчает ситуацию. Развитие аппаратного обеспечения тоже поможет защитить ключи в этом мире. Для дополнительной безопасности можно использовать личную регистрацию: возможно, в магазине, где вы покупаете смартфон или регистрируете интернет-сервис. Мы знаем, что криптография основана на доверии, и у нас гораздо больше методов управления доверием, чем в первые годы существования интернета. Я ничего не пытаюсь изобрести, только говорю, что что есть много возможностей. Некоторые важные технологии, такие как прямая секретность, станут гораздо сложнее, но пока симметричная криптография работает, у нас сохранится защита.

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

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

В основе односторонних функций лежат несколько математических теорий, которые ещё не доказаны. Есть ещё один сценарий будущего, не говоря о квантовых компьютеров. Так же, как умный криптограф может найти новый трюк, который облегчает взлом определённого алгоритма, мы можем представить себе инопланетян с достаточной математической теорией, чтобы сломать все алгоритмы шифрования. Это одна из открытых проблем в компьютерной науке. Криптография с открытым ключом — это теория чисел, потенциально уязвимая для математически более грамотных пришельцев. Для нас сегодня это просто смешно. Представьте вариант AES с 512-битным блоком и размером ключа, и шифрованием в 128 раундов. Симметричная криптография настолько нелинейно сложна, а длина ключа так легко увеличивается, что будущее сложно вообразить. Если только не придумать принципиально новую математику, такое шифрование будет безопасно до тех пор, пока компьютеры не сделают из чего-то другого, кроме материи, в каком-нибудь другом измерении.

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Знакомимся с альфа-версией снапшотов томов в Kubernetes

перев.: оригинальная статья была недавно опубликована в блоге Kubernetes и написана сотрудниками компаний Google и Huawei (Jing Xu, Xing Yang, Saad Ali), активную деятельность которых вы непременно видели в GitHub'е проекта, если когда-либо интересовались фичами и проблемами K8s, связанными с ...

Лучшие специалисты — те, которых подготовил сам: курс по тестированию игр от экспертов Mail.Ru Group

Ru Group «Игросфера Воронеж». В сентябре на базе Воронежского государственного университета был запущен новый образовательный проект Mail. Для студентов открылись два семестровых курса в формате бесплатного дополнительного образования: «Разработка игр на Unity» и «Тестирование игровых проектов». Роман Гуров, преподаватель «Игросферы» ...