В июле 2013 года мир криптографии взволновали две научные работы. Их опубликовали с разницей в несколько дней в онлайн-архиве, и вместе они описали новый, сильный метод, позволяющий скрывать секреты в компьютерных программах.
Метод назвали «обфускация неразличимости» [indistinguishability obfuscation], или IO. Авторы разрекламировали его как «основное ядро» криптографии – универсальную основу, на которой можно реконструировать такие известные инструменты, как публичные ключи и выборочно безопасные подписи. Также в работах демонстрировался математический аппарат, стоящий за IO.
Исследования привлекли очень много внимания, но за два года работы с ними специалисты встретились с довольно большим количеством практических трудностей, препятствующих внедрению IO. Например, IO слишком медленная. Задержки на обфускацию программ измеряются на современных компьютерах годами. Кроме того, оказалось, что метод не так безопасен математически, как того хотелось бы.
Но за последние несколько месяцев появились работы, в которых демонстрируются очень важные подвижки со времён изначального анонса 2013 года. Некоторые исследователи считают, что рабочую версию системы можно будет сделать лет через десять, или даже раньше. «Сейчас всё выглядит так, будто никаких серьёзных ограничений нет,- говорит Амит Сахай, программист из Калифорнийского университета, соавтор обеих научных работ. – IO – мощная система, и может сделать всё, что нам нужно». Кроме того, исследователи считают, что даже квантовые компьютеры не смогут его взломать.
Гора небольших шажков
Описание IO начинается с примера из двух программ, получающих одинаковый результат разными способами. Например, вычисляя две эквивалентные функции f(x) = x(a + b) и f(x) = ax + bx. Для любого набора из трёх переменных, a, b и x, результат у обоих программ будет одинаковым. IO утверждает, что можно таким образом зашифровать программы, что пользователь не сможет определить, какая из двух программ находится в его распоряжении.
Работы 2013 года убедили многих, что IO может серьёзно расширить область применения криптографии. Но в работах не было примеров того, как можно применить эту возможность на практике. У исследователей было две проблемы – ускорить процесс, и убедиться, что IO достаточно безопасна.
«Чтобы обфусцировать таким образом, и затем запустить программу, могут понадобиться сотни лет,- говорит Винод Вайкунтанатан [Vinod Vaikuntanathan], криптограф из MIT, вовлечённый в работу над IO. – И когда результаты получаются настолько смешными, за конкретными цифрами уже не следишь».
Элисон Бишоп, программист из Колумбийского университета, продемонстрировала, как разбить IO на последовательность небольших практических шагов
Один из выбранных программистами для ускорения процесса подходов – обфусцировать не одну большую программу, а связанные с ней менее крупные. Таким образом обфускация должна будет проходить в два этапа.
Первый – самый сложный. Существующие методы IO начинаются с бутстрапа достаточно небольшой программы. Эта программа взаимодействует с большой «целевой» программой. Программа-бутстрап работает, как оболочка безопасности вокруг вводом и выводом целевой программы – она обфусцирует всё, что входит и выходит, и в результате, скрывает и саму программу.
Но пока ещё непонятно, как обфусцировать даже небольшую программу. «Мы будто пытаемся найти в этой броне первую щель,- говорит Сахаи. – Мы застряли на программе-бутстрапе».
Второй шаг поддался исследователям легче. Когда программа-бутстрап работает, следующей задачей становится обфускация более длинных и разнообразных типов вычислений. На ежегодном симпозиуме по теории вычислений (STOC), три команды исследователей представили работы на тему, как пройти от обфускации одного любого контура до обфускации вычислений произвольного вида (машины Тьюринга).
Это большой шаг. Чтобы скрыть контур, исследователям нужно знать размер ввода и каждый шаг вычислений заранее. Компьютеры же настроены на получение любого количества данных на входе и делают дополнительные вычисления по мере поступления данных. Работа, представленная на симпозиуме, показала, как использовать специальную технику под названием «проколотого программирования» [punctured programming], чтобы обфусцировать вычисления по длинному набору данных в виде серий дискретных шагов, связанных друг с другом.
«Основное техническое достижение – применять IO к контурам на локальных шагах вычислений, и связывать всё вместе так, что в результате все вычисления оказываются защищёнными,- говорит Эллисон Бишоп, программист из Колумбийского университета.
Математически доказанная безопасность
Увеличение эффективности IO – практическая задача, а доказательство безопасности метода – фундаментальная.
Когда Сахаи и Брент Уотерс [Brent Waters], программист из Техасского университета, Остин, описали использование IO в 2013 году, оставалось только верить, что этот метод позволит сохранить секреты внутри программ. Изначальная работа была похожа на завязывание очень сложного узла – он может выглядеть так, будто его сложно развязать, но без понимания его структуры нельзя быть уверенным в том, что для этого не существует простого метода.
»В тот момент была лишь некая конструкция – не было даже понятно, как доказывать её безопасность",- говорит Вайкунтанатан.
Брент Уотерс
С тех пор ситуация стала лучше. Любая криптография основана на математике, определяющей задачи, которые должен решить атакующий для взлома кода. RSA-шифрование, к примеру, использует произведение больших целых чисел. Чтобы начать читать ваши емейлы, атакующему нужно определить два больших целых числа, перемножением которых было получено это значение. Эта задача при текущих вычислительных мощностях считается невыполнимой.
Математические расчёты, лежащие в основе криптографической схемы, должны быть прочными, а также простыми, хорошо проверенными и понятными – чтобы криптографы были уверены, что задача действительно так сложна, какой кажется.
«Это должна быть понятная нам математическая задача. Иначе, как показывает опыт, её можно взломать»,- говорит Сахаи.
В 2013 не существовало практических предположений по поводу безопасности IO. В следующем году исследователи из IBM выпустили работу, в которой IO сводится до нескольких предположений, связанных с математическими объектами под названием «полилинейные отображения». «Мы показали, что если хакер взламывает IO, он решает одну из таких задач»,- пояснил Бишоп, один из авторов работы.
Полилинейные отображения появились в криптографии в 2013 году. Эксперты ещё не полностью изучили вопрос их надёжности. «Пока что, если вы взломаете какого-нибудь кандидата из полилинейных отображений, вы не сильно шокируете общественность»,- говорит Уотерс.
В данный момент специалисты по информатике работают над тем, чтобы заменить полилинейные отображения чем-то более понятным. Лучшим кандидатом пока считается концепция «обучение с ошибками». У неё с полилинейными отображениями общие «предки» в области под названием «криптография на решётках», поэтому есть вероятность, что замену удастся произвести. Но пока никто не знает, как.
Спешка в обеспечении безопасности
Несмотря на все трудности IO, эксперты считают, что криптография на её основе уже близка. Сахай указывает, что в криптографии путь от идеи до реализации может занимать и 30 лет. И с учётом прогресса последних двух лет, на IO может понадобиться меньше времени. «Мы надеемся, что 10-15»,- говорит он.
Главным этапом станет находка менее сложной математической основы для безопасности IO. Сейчас лучшие умы в этой области считают, что работа должна пойти ускоренными темпами. Бишоп сказал, что «не станет спорить» с тем, что набор простых математических установок будет найден в течение десяти лет. Вайкунтанатан вообще считает, что это займёт «пару лет».
За последние два года произошли серьёзные финансовые вливания в проект. Сахай руководит Центром шифрования в UCLA, получил от Национального научного фонда грант в $5 миллионов. Агентство DARPA основало исследовательскую программу SafeWare, целью которой является создание эффективных и универсальных методов обфускации программ.
Спешка разработчиков, пытающихся внедрить IO, говорит как о привлекательности этой темы, так и о необходимости разработки новых методов криптографии. Разработчики квантовых компьютеров также не дремлют, и после их появления большинство криптографических схем окажутся скомпрометированы. За исключением, возможно, IO.
Автор: SLY_G
