В июле 2013 года две научные статьи взволновали мир криптографии.
Они были опубликованы с разницей в несколько дней в онлайн-архиве и вместе описали новый, мощный метод сокрытия секретов в компьютерных программах.
Этот метод получил название «обфускация неразличимости», или IO. Авторы рекламировали его как «ядро» криптографии — универсальную структуру, на основе которой можно реконструировать такие знакомые инструменты, как открытые ключи и выборочно защищенные подписи.
Работы также продемонстрировали математический аппарат, лежащий в основе IO. Исследование привлекло большое внимание, однако за два года работы с ним специалисты столкнулись с довольно большим количеством практических трудностей, которые тормозили внедрение IO. Например, IO работает слишком медленно.
Задержки из-за обфускации программ измерялись на современных компьютерах в течение многих лет. Кроме того, оказалось, что метод не так безопасен математически, как хотелось бы.
Но за последние несколько месяцев появилась работа, демонстрирующая некоторые очень важные разработки с момента первоначального анонса в 2013 году.
Некоторые исследователи полагают, что рабочая версия системы может быть создана через десять лет или даже раньше.
«Сейчас кажется, что серьезных ограничений нет», — говорит Амит Сахай, ученый-компьютерщик из Калифорнийского университета и соавтор обеих статей.
«IO — мощная система, которая может делать все, что нам нужно».
Кроме того, исследователи полагают, что взломать его не смогут даже квантовые компьютеры.
Гора маленьких шагов
Описание IO начинается с примера двух программ, получающих один и тот же результат разными способами.Например, вычисление двух эквивалентных функций f(x) = x(a + b) и f(x) = ax + bx. Для любого набора из трех переменных a, b и x результат для обеих программ будет одинаковым.
IO утверждает, что можно зашифровать программы таким образом, что пользователь не сможет определить, какая из двух программ находится у него в распоряжении.
Работа 2013 года убедила многих, что IO может серьезно расширить сферу применения криптографии.
Но в работах не было примеров того, как эту возможность можно было бы применить на практике.
У исследователей было две проблемы: ускорить процесс и обеспечить достаточную безопасность ввода-вывода.
«На то, чтобы запутать таким образом и затем запустить программу, могут уйти сотни лет», — говорит Винод Вайкунтанатан, криптограф Массачусетского технологического института, участвовавший в работе над вводом-выводом.
«А когда результаты оказываются такими смешными, за конкретными цифрами уже не следишь».
Лисон Бишоп, программист из Колумбийского университета, продемонстрировал, как разбить ввод-вывод на серию небольших практических шагов.
Один из подходов, выбранных программистами для ускорения процесса, заключается в запутывании не одной большой программы, а связанных с ней более мелких.
Таким образом, обфускация должна будет проходить в два этапа.
Первый из них самый трудный.
Существующие методы ввода-вывода начинаются с начальной загрузки довольно небольшой программы.
Эта программа взаимодействует с большой «целевой» программой.
Программа начальной загрузки действует как защитная оболочка вокруг ввода и вывода целевой программы — она запутывает все, что входит и выходит, и в результате скрывает саму программу.
Но пока не ясно, как запутать даже небольшую программу.
«Мы как будто пытаемся найти первую брешь в этой броне», — говорит Сахай.
«Мы застряли в программе начальной загрузки».
Второй шаг оказался проще для исследователей.
После запуска программы начальной загрузки следующей задачей будет запутывание более длинных и разнообразных типов вычислений.
На ежегодном симпозиуме по теории вычислений (STOC) три группы исследователей представили работу о том, как перейти от обфускации любой отдельной схемы к обфускации произвольных типов вычислений (машин Тьюринга).
Это большой шаг.
Чтобы скрыть контур, исследователям необходимо заранее знать размер входных данных и каждый вычислительный шаг.
Компьютеры настроены на получение любого количества входных данных и выполнение дополнительных вычислений по мере их поступления.
Работа, представленная на симпозиуме, показала, как использовать специальную технику под названием «проколотое программирование», чтобы разбить вычисления на длинном наборе данных на серию дискретных шагов, связанных друг с другом.
«Основное техническое достижение заключается в том, чтобы применить ввод-вывод к циклам на локальных вычислительных этапах и связать все вместе, чтобы все вычисления были безопасными», — говорит Эллисон Бишоп, ученый-компьютерщик из Колумбийского университета.
Математически доказанная безопасность
Повышение эффективности ИО — практическая задача, но доказательство безопасности метода имеет основополагающее значение.Когда Сахай и Брент Уотерс, ученый-компьютерщик из Техасского университета в Остине, описали использование ввода-вывода в 2013 году, можно было только поверить, что этот метод позволит хранить секреты внутри программ.
Первоначальная работа была похожа на завязывание очень сложного узла — может показаться, что его сложно развязать, но без понимания его устройства нельзя быть уверенным, что для этого не существует простого метода.
«На тот момент существовала только некая конструкция — даже не было ясно, как доказать ее безопасность», — говорит Вайкунтанатан.
Брент Уотерс
С тех пор ситуация стала лучше.
Вся криптография основана на математике, которая определяет проблемы, которые должен решить злоумышленник, чтобы взломать код. Например, шифрование RSA использует произведение больших целых чисел.
Чтобы начать читать ваши электронные письма, злоумышленнику необходимо определить два больших целых числа, которые были перемножены для получения этого значения.
Эта задача считается невыполнимой при нынешних вычислительных мощностях.
Математика, лежащая в основе криптографической схемы, должна быть надежной, а также простой, хорошо проверенной и понятной — чтобы криптографы могли быть уверены, что проблема действительно так сложна, как кажется.
«Это должна быть математическая задача, которую мы можем понять.
В противном случае, как показывает опыт, его могут взломать», — говорит Сахай.
В 2013 году не было никаких практических предположений относительно безопасности ввода-вывода.
В следующем году исследователи из IBM опубликовали статью, в которой объем операций ввода-вывода сводился к нескольким предположениям, связанным с математическими объектами, называемыми «мультилинейными отображениями».
«Мы показали, что если хакер взломает IO, он решит одну из этих проблем», — пояснил Бишоп, один из авторов работы.
Полилинейные отображения появились в криптографии в 2013 году.
Эксперты еще не до конца изучили вопрос их достоверности.
«На данный момент, если вы взломаете одного из кандидатов на многолинейное картографирование, вы не слишком шокируете публику», — говорит Уотерс.
В настоящее время ученые-компьютерщики работают над заменой многолинейных отображений чем-то более понятным.
Лучшим кандидатом на данный момент является концепция «обучения на ошибках».
Он имеет общих «предков» с полилинейными отображениями в области, называемой «решетчатая криптография», поэтому существует вероятность того, что можно будет произвести замену.
Но пока никто не знает как.
Спешите за безопасностью
Несмотря на все трудности IO, эксперты считают, что криптография на его основе уже близка.Сахай отмечает, что в криптографии путь от идеи до реализации может занять 30 лет. А учитывая прогресс последних двух лет, ИО может занять меньше времени.
«Мы надеемся, что будет 10–15», — говорит он.
Основным шагом будет поиск менее сложной математической основы безопасности ввода-вывода.
Сейчас лучшие умы в этой области считают, что работа должна идти ускоренными темпами.
Бишоп сказал, что он «не будет спорить», что набор простых математических формул будет найден в течение десяти лет. Вайкунтанатан вообще считает, что на это потребуется «пару лет».
За последние два года в проект были вложены серьезные финансовые вложения.
Сахай руководит Центром шифрования в Калифорнийском университете в Лос-Анджелесе и получил грант в размере 5 миллионов долларов от Национального научного фонда.
DARPA основало исследовательскую программу SafeWare, цель которой — создание эффективных и универсальных методов обфускации программ.
Наплыв разработчиков, пытающихся реализовать IO, говорит как о привлекательности этой темы, так и о необходимости разработки новых методов криптографии.
Разработчики квантовых компьютеров тоже не дремлют, и после их появления большинство криптографических схем будут скомпрометированы.
За исключением, может быть, ИО.
Теги: #обфускация #обфускация неразличимости #обфускация неразличимости #информационная безопасность #Криптография
-
Салфетка — Мобильное Приложение Для Верстки
19 Oct, 24 -
Разведка С Помощью Geo2Ip И Обратного Whois
19 Oct, 24 -
Бета-Версия Skype 2.2 Выпущена Для Linux
19 Oct, 24
