Квантовый хакинг: о взломе квантовых программ
Life-Hack [Жизнь-Взлом]/ХакингКвантовые технологии — один из главных трендов в современном мире IT. Хотя полноценный квантовый компьютер, который с легкостью решает невозможные для кремниевой электроники задачи, ученым собрать пока не удалось, в мире широко производятся системы квантовой криптографии. Их прелесть в том, что перехватить информацию, передаваемую по такой системе связи, попросту невозможно. Тем не менее, полностью исключать возможность успешного взлома системы квантовой криптографии тоже нельзя.
С защитой информации складывается парадоксальная ситуация. С одной стороны, считается, что современные методы шифрования вполне надежны. Для подбора ключа к текстам даже суперкомпьютерам потребуются годы. И оснований для особой тревоги нет. Но тогда почему во многих странах киберугрозы называются одной из главных проблем национальной безопасности. Защитой информации озабочены не только специалисты, но и политики. Принимаются национальные программы противодействия новым киберугрозам.
Действительно, современные системы защиты информации способны противостоять классическим хакерским атакам. Но ситуация кардинально изменится, как только за дело возьмется квантовый компьютер. С его помощью злоумышленники быстро подберут ключ для доступа к данным, зашифрованным большинством известных алгоритмов.
Программы для квантового компьютера тоже могут содержать уязвимости. Эти уязвимости могут позволять удалённо выполнять какие-то вычисления.
Как же написать шеллкод для программы, уязвимой к исполнению квантового кода?
Квантовое программирование — это тоже программирование, и в квантовых программах тоже могут быть уязвимости. Автор задачи создал сервис, который симулирует некоторые квантовые вычисления с использованием секретного значения («флага») и пользовательского ввода.
В решении задачи есть две части: реверс-инжиниринг логики .NET-приложения на Q# и собственно программирование квантового эксплойта.
Реверс-инжинирим
Нам даны скомпилированные файлы проекта в виде нескольких DLL на Q# и ELF-файл сервиса. Исходников нет.
Вооружившись инструментами dotPeek и dnSpy, принимаемся декомпилировать DLL и изучать логику приложения.
Эти инструменты, конечно, не умеют декомпилировать .NET-байткод в Q#-код, поэтому мы получаем лишь C#-код, причём с некоторыми потерями. Каждый из инструментов не справляется с декомпиляцией некоторых кусков кода, но суммарно картина видна.
Так, при помощи dotPeek разбираемся с точкой входа в ZN.Runner.dll:
Тут можно разобрать, что программа считывает флаг из файла, далее считывает строку, переданную пользователем, затем производит какое-то преобразование над этими буферами и выдаёт результат.
Открываем код процедуры Program.TransformBytesAsync, которая производит интересующее нас преобразование:
Итак, всё выглядит довольно непонятно, но, не обращая внимание на преобразования типов, мы можем понять, что по всей видимости флаг и наша строка попадают в квантовый симулятор, и сами вычисления реализованы в классе TransformBytes, который можно найти в файле ZN.Quantum.dll.
Здесь нам перестаёт помогать dotPeek, и приходится обратиться к dnSpy. Низкоуровневый класс TransformBytes, который мы видим в декомпиляторе, соответствует такой штуке, как операция (operation) в Q#. Тело операции имплементировано в методе __Body__ декомпилированного класса:
По декомпилированному коду видно, что поочерёдно для каждого байта флага производятся следующие операции:
- Инициализируется массив iqarray из 8 кубитов,
- При помощи ConstructOperations создаётся массив унитарных преобразований (тип IUnitary) iqarray2,
- Применяется NumberToBigEndian к байту флага, результат записывается в iqarray,
- К iqarray применяется Microsoft.Quantum.Canon.QFT,
- К первому кубиту (iqarray[0]) применяются операции из массива iqarray2 при помощи ApplyOperations.
Операция ConstructOperations формирует массив (последовательность) квантовых гейтов в зависимости от строк, считанных из ввода через CycleStringReader:
Для исполнения доступны следующие операции, которые будут применены к первому кубиту из нашего массива:
- Adjoint (сопряжение)
- I (тождественная операция)
- X, Y, Z
- CX, CY, CZ
- Rx, Ry, Rz
- CNOT
- SWAP (можно поменять местами первый кубит с i-м)
Операция NumberToBigEndian «намазывает» классические биты целочисленного аргумента на массив кубитов, так что изначально каждый кубит равен 0 или 1:
Следом применяется операция QFT, т.е. квантовое преобразование Фурье. Именно это преобразование делает вывод программы случайным набором битов вместо битов флага.
В итоге выполняется операция ApplyOperations, которая просто берёт массив гейтов, полученный при помощи ConstructOperations, и последовательно применяет их после QFT.
Суть задачи
Таким образом, мы разобрались, что программа считывает флаг, «рандомизирует» его при помощи QFT, после чего исполняет контролируемый нами квантовый код из ограниченного множества гейтов.
По сути программа уязвима к удалённому исполнению (почти) произвольного кода в квантовой машине. Это то, что обычно называется RCE.
Наша задача — написать эксплойт для этой уязвимости, составив из доступных нам гейтов такой код, что мы сможем обратить действие QFT.
Отправив этот набор гейтов на сервер, в ответ мы детерминированно получим изначальное значение флага!
Пишем квантовый эксплойт
Применение квантовой операции — суть умножение на матрицу. Квантовое преобразование Фурье — это перемножение некоторого количества матриц. Преобразование может быть применено к серии кубитов, в нашем случае это массив из 8 кубитов.
На картинке ниже из Википедии схематично показана работа QFT для n кубитов:
Здесь H — это гейт Адамара, замечательное преобразование, в результате которого кубит при измерении будет равновероятно возвращать 0 или 1. Матрица этого оператора выглядит следующим образом:
Rk — это контролируемые версии фазовых вращений, матрица которых для 2 кубитов выглядит так:
Для того, чтобы построить обратное преобразование, нам нужно выполнить операции в обратном порядке, при этом вместо каждой матрицы брать эрмитово-сопряжённую ей (поскольку все преобразования унитарны).
Но вот незадача: у нас в наборе гейтов, доступных в ConstructOperations, нет ни H, ни Rk, ни сопряжённых им операторов (кстати, оператор Адамара сопряжён сам себе).
Значит, нам надо как-то выразить эти операторы через доступные нам. Оказывается, гейт Адамара мы можем выразить, например, через операторы Z и Ry(pi/2), что легко проверить, перемножив соответствующие матрицы.
С контролируемыми вращениями сложнее: листая документацию Q# по доступным операторам можно заметить, что самая похожая матрица у оператора Rz. На самом деле, это как раз то, что нам нужно, поскольку Rz с подходящим аргументом отличается от Rk только в глобальной фазе, что не влияет на результат вычислений.
Вот только кое-чего нам не хватает в Rz: контролируемости. Её мы можем достичь при помощи такой хитрости: если нам нужно выполнить контролируемое вращение Rz(theta), мы сначала выполним Rz(theta/2), затем контролируемое вращение вокруг оси X (CX), затем Rz(-theta/2) и снова CX.
Поскольку оператор X «разворачивает» направление вращения Rz, мы получим как раз нужный эффект зависимости от контрольного бита: если контрольный бит равен 0, композиция двух Rz с разными знаками «сократится», а если контрольный бит ненулевой, то они приплюсуются, и мы получим полное вращение Rz(theta).
Итоговый алгоритм следующий:
- Применяем H к первому кубиту,
- Поочерёдно для каждого последующего кубита:
- выполняем SWAP, чтобы в дальнейшем работать с ним; поочерёдно применяем Rk с каждым предыдущим кубитом в качественно контрольного; применяем H; повторяем SWAP, чтоб вернуть кубит на место.
- Применяем ко всему набору кубитов последовательность транспозиций SWAP, которые в композиции дают инверсию (т.е. переворачиваем массив).
Последний шаг, конечно, можно выполнить и на клиентской стороне, а не в квантовом коде.
Ниже приведён код эксплойта на Python:
from math import pi
from socket import socket
s = socket()
s.connect(('quantum.kelte.cc', 17171))
prog = ''
# Hadamard for the 0th qubit
prog += 'H\n'
for i in xrange(1, 8):
# Take the ith qubit
prog += 'SWAP %s\n' % i
ids = list(range(i - 1, 0, -1)) + [i] # We have 0 swapped with i
for j in xrange(len(ids)):
theta = -pi / (2 ** j) / 4
# Controlled (global phase adjusted) R1 implementation
prog += 'Rz %f\n' % theta
prog += 'CX %s\n' % ids[j]
prog += 'Rz %f\n' % -theta
prog += 'CX %s\n' % ids[j]
# Apply Hadamard
prog += 'H\n'
# Swap back with the 0th qubit
prog += 'SWAP %s\n' % i
# Reverse all the qubits
prog += '''SWAP 1
SWAP 6
SWAP 1
SWAP 2
SWAP 5
SWAP 2
SWAP 3
SWAP 4
SWAP 3
SWAP 7
'''
# Implement Hadamard
prog = prog.replace('H', 'Z Ry %f' % (pi / 2)).replace('\n', ' ')
s.recv(128)
s.send('%s\n' % prog.strip())
print(s.recv(56).strip().decode('hex'))
Запускаем и получаем флаг: ZN{Qu4NtuM_H3ll0_w0RLD_2021}.
Квантовые вычисления представляют угрозу кибербезопасности
В основе асиметричной криптографии лежит два ключа: один может зашифровать данные, другой используется для их расшифровки. Теоретически квантовые компьютеры будут способны решать задачи существенно быстрее по сравнению с обычными компьютерами и смогут расшифровывать закрытые ключи. Учитывая темпы развития квантовых вычислений, это может случиться уже через 5-10 лет.
Споявлением квантовых компьютеров традиционное шифрование перестанет быть эффективным. Это значит, что пострадает вся ценная информация, которая передается в зашифрованном виде, под угрозой окажутся банковские транзакции и криптовалюта, злоумышленники смогут получать доступ к критически важным энергетическим объектам из любой точки мира и т.д. Как отметил эксперт, данная проблема затронет не только разведсообщество и экспертов в сфере кибербезопасности, но и социальные платформы и мессенджеры, такие как WhatsApp, использующие ключи для авторизации пользователей.
Информационная безопасность в эпоху квантовых технологий
Появление квантовых компьютеров существенно меняет подходы к организации защиты информации.
Развитие современных технологий уже привело к созданию новой реальности для бизнеса – цифровой экономики. В условиях стремительного роста объемов потребительской и коммерческой информации, а также ее постоянного обмена защита данных и доверие ставятся в один ряд с другими важнейшими требованиями, предъявляемыми к бизнесу. 83 % руководителей российских компаний отмечают, что взлом систем кибербезопасности негативно скажется на доверии к бизнесу в целом.
Квантовые технологии могут значительно более эффективно выполнять параллельные вычисления по сравнению с «классическими» компьютерами. Уже разработаны алгоритмы, которые позволят квантовому компьютеру сократить время подбора пароля и дешифровки информации до нескольких часов или минут.
Почему компаниям стоит уже сейчас предпринимать действия для защиты информации от этой угрозы уже сейчас?
- Мгновенно перейти на новые методы защиты информации невозможно, требуется существенное изменение инфраструктуры, текущих методов работы и финансовые вложения.
- Злоумышленники могут перехватывать конфиденциальную информацию, которая передается в зашифрованном виде и имеет стратегическую важность, и сразу после появления квантового компьютера расшифровать ее.
Защита, гарантированная законами физики
Квантовая криптография направлена на защиту информации, передаваемой между отдельными пользователями системы или источниками данных в одной сети. Ее основная цель – защитить ключ шифрования от возможного перехвата. Данная задача выполняется благодаря тому, что нарушитель, пытающийся перехватить квантовый обмен, обязательно оставит явные следы. Благодаря защищенной передаче закрытых ключей квантовая криптография сможет обеспечить долгосрочную защиту информации. Эта технология не требует создания новой инфраструктуры и может работать на уже существующих оптоволоконных линиях, взаимодействуя с используемыми устройствами шифрования. Вместе с тем аппаратные решения пока относительно дороги.
Новое поколение математичеcких алгоритмов
Постквантовая криптография – направление исследования новых алгоритмов шифрования, которые сложны для взлома как «классическими», так и квантовыми компьютерами. На данный момент на рынке отсутствуют единые признанные стандарты постквантового шифрования, доказавшие свою эффективность. Возможна ситуация, при которой с развитием квантовых компьютеров выбранный алгоритм уже не обеспечит требуемый уровень защиты и его придется менять. Поэтому важно сразу выбрать оптимальный алгоритм.