Идёт гонка за создание новых способов защиты данных и коммуникаций от угроз, исходящих от сверхмощных квантовых компьютеров
Мало кто из нас обращал внимание на небольшой символ замочка, появляющийся в наших веб-браузерах каждый раз, когда мы заходим на сайт интернет-магазина, отправляем и получаем емейлы, проверяем наш банковский счёт или кредитную карту. Однако он сигнализирует о том, что онлайн-сервисы используют HTTPS, веб-протокол, шифрующий данные, которые мы отправляем по интернету, и те ответы, что мы получаем. Эта и другие формы шифрования защищают различные электронные коммуникации, а также такие вещи, как пароли, цифровые подписи и истории болезней.
Квантовые компьютеры могут подорвать эту криптографическую защиту. Сегодня эти машины пока недостаточно мощны, но они быстро эволюционируют. Возможно, что не позднее, чем через десять лет – а возможно, и раньше – эти машины смогут стать угрозой для широко используемых методов криптографии. Именно поэтому исследователи и компании, занимающиеся безопасностью, наперегонки разрабатывают новые подходы к криптографии, которые смогут выдержать будущие квантовые атаки хакеров.
Как работает цифровое шифрование?
Существуют два основных типа шифрования. Симметричное шифрование требует, чтобы у отправителя и получателя были в наличии идентичные цифровые ключи для зашифровки и расшифровки данных, а асимметричное – или шифрование с публичным ключом – использует публично доступный ключ, позволяющий людям зашифровывать сообщения для получателя, единолично владеющего приватным ключом, позволяющим их расшифровывать.
Иногда два этих подхода используются вместе. В случае с HTTPS, к примеру, веб-браузеры используют публичные ключи для проверки достоверности сайтов и получения ключа для симметричного шифрования коммуникаций.
Цель – не дать хакерам при помощи значительных вычислительных мощностей попытаться угадать используемые ключи. Для этого популярные криптографические методы, включая RSA и шифрование с помощью эллиптических кривых, обычно используют т.н. односторонние функции с потайным входом – математические конструкции, которые относительно легко вычислять в одну сторону для получения ключей, но очень сложно для злоумышленника подвергнуть обратному инжинирингу.
Хакеры могут попытаться взломать код, подбирая все возможные варианты ключа. Но защищающиеся стороны очень усложняют им эту задачу, используя пары очень длинных ключей – как в 2048-битной RSA, использующей ключи длиной в 617 десятичных чисел. Перебор всех возможных вариантов приватных ключей займёт тысячи – если не миллионы – лет у обычных компьютеров.
Почему квантовые компьютеры несут угрозу шифрованию?
Поскольку они могут помочь хакерам гораздо быстрее пробираться через алгоритмические потайные ходы. В отличие от классических компьютеров, использующих биты, способные принимать лишь значения 1 или 0, квантовые машины используют кубиты, способные одновременно представлять различные возможные состояния, промежуточные между 0 и 1 – это явление называется суперпозицией. Они также могут влиять друг на друга на расстоянии благодаря такому явлению, как запутанность.
Благодаря этому явлению добавление нескольких дополнительных кубитов может привести к экспоненциальным скачкам вычислительной мощности. Квантовая машина с 300 кубитами способна представлять больше значений, чем количество атомов в наблюдаемой Вселенной. Предполагая, что квантовые компьютеры смогут преодолеть некоторые присущие им ограничения, касающиеся быстродействия, когда-нибудь их можно будет использовать для проверки всех возможных вариантов криптографического ключа за относительно недолгое время.
Хакеры также, скорее всего, попытаются использовать во вред алгоритмы оптимизации определенных задач. Один из таких алгоритмов, опубликованный Ловом Гровером из AT&T Bell Labs, помогает квантовым компьютерам гораздо быстрее искать варианты. Другой алгоритм, опубликованный в 1994 году Питером Шором, тогда также работавшим в Bell Labs, а теперь профессором в MIT, помогает квантовым компьютерам невероятно быстро находить простые множители целых чисел.
Алгоритм Шора угрожает таким системам с публичным ключом, как RSA, чья математическая защита в частности зависит от того, насколько сложно провести обратный инжиниринг результата перемножения очень больших простых чисел (разложение на множители). В отчёте по квантовым вычислениям, опубликованном в прошлом году национальной академией наук, инженерного дела и медицины США, предсказывается, что мощный квантовый компьютер, на котором работает алгоритм Шора, сможет взламывать 1024-битные варианты RSA менее, чем за день.
Смогут ли квантовые компьютеры взламывать криптографическую защиту в ближайшее время?
Маловероятно. Исследование национальных академий утверждает, что для того, чтобы представлять реальную угрозу, квантовым компьютерам понадобится гораздо больше вычислительной мощности, чем имеется у наилучших из них на сегодня.
Однако, год, в котором квантовый взлом кодов станет серьёзной головной болью – который некоторые исследователи безопасности окрестили Y2Q – может подобраться неожиданно быстро. В 2015 году исследователи заключили, что для достаточно быстрого взлома 2048-битного RSA шифрования квантовому компьютеру понадобится миллиард кубитов. В более современной работе указывается, что компьютер с 20 млн кубитов сможет справиться с этой задачей всего за 8 часов.
Это находится далеко за пределами возможностей самых мощных из сегодняшних компьютеров, обладающих всего 128 кубитами. Но прогресс квантовых вычислений непредсказуем. Без криптографической защиты, учитывающей квантовые вычисления, всякие сервисы – от робомобилей до военного оборудования, финансовых транзакций и коммуникаций – подвержены угрозе атаки со стороны хакеров, получивших доступ к квантовым компьютерам.
Любое предприятие или правительство, рассчитывающее хранить данные несколько десятилетий, должно уже сейчас задуматься над тем, какие риски несёт в себе новая технология, поскольку используемое ими сегодня шифрование может быть взломано в будущем. На перекодирование огромных объёмов исторических данных в более надёжный вид могут уйти года, поэтому лучше будет применять надёжное кодирование сегодня. Отсюда проистекает запрос на постквантовую криптографию.
Какой будет постквантовая криптография?
Это разработка новых видов криптографических методов, которые можно применять с использованием сегодняшних классических компьютеров, но которые при этом будут неуязвимы перед завтрашними квантовыми.
Одна из линий обороны – увеличение размеров цифровых ключей для значительного увеличения количества вариантов, в которых нужно будет вести поиск перебором. К примеру, простое удвоение размера ключа с 128 до 256 бит учетверяет количество возможных вариантов, которые придётся перебрать квантовой машине, использующей алгоритм Гровера.
Ещё один подход включает использование более сложных функций с потайным входом, таких, чтобы с ними тяжело было справиться даже мощному квантовому компьютеру, исполняющему алгоритм Шора. Исследователи работают над широким спектром подходов, включая такие экзотические, как криптография на решётках и протокол обмена ключами с использованием суперсингулярных изогений.
Цель исследований – выбрать один или несколько методов, которые затем можно будет широко применять. Национальный институт стандартов и технологий США запустил в 2016 году разработку стандартов постквантового шифрования для правительственного использования. Он уже сузил изначальный набор заявок с 69 до 26, но говорит, что первые черновики стандартов, скорее всего, появятся не ранее 2022 года.
Критическая важность этой задачи связана с тем, что технологии шифрования глубоко внедрены во множество различных систем, поэтому на их переделку и внедрение новых алгоритмов потребуется очень много времени. В исследовании национальных академий от прошлого года отмечено, что на полное избавление от одного широко использовавшегося криптографического алгоритма, оказавшегося уязвимым, ушло более 10 лет. Учитывая скорость развития квантовых компьютеров, возможно, у мира осталось не так уж много времени, чтобы разобраться с этой новой проблемой безопасности.
Комментарии (21)
Kodath
30.08.2019 10:19-1На перекодирование огромных объёмов исторических данных в более надёжный вид могут уйти года, поэтому лучше будет применять надёжное кодирование сегодня.
Да и когда доживем до этих «домашних» квантовых компьютеров — ими же и перекодировать сможем.ne_kotin
30.08.2019 11:05+1Да и когда доживем до этих «домашних» квантовых компьютеров
Не доживем. Там есть принципиальные физические ограничения.
vassabi
30.08.2019 10:53этот призыв надо адресовать не криптографам, а производителям железа. Какая там квантовая криптография, когда они выпускают сотни подключенных к интернету устройств логином и паролем админ: админ?
Victor_koly
30.08.2019 12:46Меняйте пароль на роутере, если пихаете его в инет.
P.S. Хотя я себе не менял, только на Wi-Fi.Mur81
30.08.2019 13:34Так особо выдающиеся производители умудряются логин/пароль рута захардкодить.
Victor_koly
30.08.2019 14:01Печально.
P.S. А где-то на роутере можно логины менять? Как-то даже не знал, на каких-то TP-Link действительно можно.Mur81
30.08.2019 16:15Да полно где можно. Но это не гарантирует от того, что в коде может быть зашит какой-нибудь root с паролем Qwe123.
thevladmartin
31.08.2019 12:16Как раз «соседний» пост на тему камер в де-факто открытом доступе в IoT.
Тут уже, увы, не все знают азы безопасности и забывают, что у того, чему не нужен доступ к инету, этого доступа быть и не должно.
В принципе, проэксплойтить уязвимость можно даже с самым сложным логином и паролем, другая проблема в том, что у большинства IoT-устройств лог/пасс admin:admin и стандартные порты. Хотя, конечно, там и Ханипотов — море…
CryptoPirate
30.08.2019 11:12+1Национальный институт стандартов и технологий США запустил в 2016 году разработку стандартов постквантового шифрования для правительственного использования.
Не разработку, а конкурс. Это очень важная разница в данном случае. Куча специалистов по шифрованию со всего мира представили варианты алгоритмов на конкурс. Там никто не пилит свой закрытый алгоритм, а всё идёт в открытую, анализом и взломом занимаются, опять же, специалисты по шифрованию и математике со всего мира.starpeer
31.08.2019 07:44Ага, в открытую, особенно вчера отожгли на конкурсе по низкоресурсным алгоритмам: «вы знаете, вы нам до фига алгоритмов на сабмитили, поэтому мы решили некоторые выкинуть из дальнейшего рассмотрения»
mikeee1
30.08.2019 11:43Если будет найден способ скейлинга кубитов, то в том же кубическом миллиметре вещества можно будет иметь ~10^18 кубит. Это уже настолько много, что нужно придумывать какие-то алгоритмы, где расшифровка невозможна простыми методами перебора.
OneOfUs
30.08.2019 12:50На сколько помню матчасть кубитов, там есть ограничение на расстояние между кубитами. В том плане, что слишком близко их не посадишь, иначе они будут влиять друг на друга. Вроде бы ещё не решили эту проблему
Victor_koly
30.08.2019 12:40ключи длиной в 617 десятичных чисел
Со временем взлома порядка (10^617 секунд/«кол-во ядер*частоту»)? Я в курсе, что там все же не так сложно, но все равно взлом кажется слишком долгим.
trolley813
30.08.2019 13:15+2ключи длиной в 617 десятичных чисел
В очередной раз путают числа и цифры...
BOM
30.08.2019 15:36+2Мало кто из нас обращал внимание на небольшой символ замочка, появляющийся в наших веб-браузерах
Да, конечно. Понятия не имеем что это.
saboteur_kiev
30.08.2019 19:32+2Мало кто из нас обращал внимание на небольшой символ замочка, появляющийся в наших веб-браузерах каждый раз, когда мы заходим на сайт интернет-магазина, отправляем и получаем емейлы, проверяем наш банковский счёт или кредитную карту.
Хм…
starpeer
31.08.2019 07:56Это находится далеко за пределами возможностей самых мощных из сегодняшних компьютеров, обладающих всего 128 кубитами
Со 128-ми кубитами- это явный загон. Ригетти только анонсировали 128 кубит, а не сделали его, так что пока рекорд 72
Исследователи работают над широким спектром подходов, включая такие экзотические, как криптография на решётках и протокол обмена ключами с использованием суперсингулярных изогений.
Когда это решетки стали экзотическими? NTRU известна с 90-х, кроме того, это стандарт X9.
И правильно говорить на изогениях суперсигулярных эллиптических кривыхVictor_koly
31.08.2019 13:59Вот тут что-то было про «изогении между суперсингулярными кривыми»:
habr.com/ru/company/aktiv-company/blog/332494
saipr
Если убрать из контекста слово "квантовые", а где-то заменить просто на "компьютерные", то это изречение можно было читать или слышать и в 60-х и в 70-х и так до нащих дней.
А компьютерная защита жива, здравствует и развивается. Так что можно уверенно сказать, что все будет Хорошо!