Скоро может появиться почти идеальная компьютерная защита.

Технологии

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

Метод получил название «неразличимость обфускации» (запутывания кода —прим. Newочём), или просто НО. Авторы описывали его как центральный узел всей криптографии — единую основу, которая реконструирует знакомые криптографические инструменты, такие как общественные ключи и частично защищенные подписи. В исследованиях также была предпринята первая попытка описать НО математически.

В то время эти работы вызвали огромный интерес, но в течение двух следующих лет исследователи столкнулись с рядом практических проблем, преграждающих путь к использованию НО. Например, НО работает чрезвычайно медленно. Запутывание кода программы происходит с задержками, которые измеряются не в минутах и даже не в часах, но в целых жизнях. Кроме того, этот метод не так математически безопасен, как должен быть.

Но за последние несколько месяцев в ряде исследований были представлены наиболее важные достижения, которые удалось совершить с 2013 года. Некоторые ученые-программисты считают, что мы получим рабочую систему в течение десятилетия, а может и раньше.

«Кажется, что на сегодняшний день у нас нет серьезных ограничений, — заявил Амит Сахай, специалист по информатике из Университета Калифорнии в Лос-Анджелесе и соавтор обеих публикаций. — НО очень мощный метод, и с его помощью можно сделать все, что мы только захотим»

Если НО можно будет сконструировать из простых математических условий, то, как считают ученые, ее не сможет взломать даже квантовый компьютер. (Квантовая защитная криптографическая система — очень запутанная вещь; ни один метод защиты данных не доказал своей устойчивости к алгоритмам на квантовой основе. — прим. автора статьи)

Длинная цепочка из коротких шагов

Неразличимость обфускации начинается с установки двух программ, которые вычисляют одинаковый результат различными путями — например, эквивалентными функциями f(x) = x(a + b) и f(x) = ax + bx. Для любого набора исходных данных, то есть значений a, b и x, одна программа выдает тот же результат, что и другая, но рассчитывает она этот результат другим способом. Согласно НО, при наличии этих программ, их можно будет зашифровать так, что ни один пользователь не сможет узнать, какая у него версия, сколько бы он не копался.

Статьи 2013 года убедили многих людей в том, что НО сможет резко расширить сферу применения криптографии. Но в исследованиях не уточнялось, как это сделать на практике. У исследователей и так есть две большие проблемы: во-первых, нужно ускорить процесс шифрования данных, а во-вторых, убедиться в том, что НО действительно безопасна.

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

Эллисон Бишоп, программист из Колумбийского университета, показывает, как с помощью простых шагов взломать НО. Фото Райана Джона Ли, Колумбийский университет

Принятая программистами стратегия по ускорению работы НО состоит в том, чтобы вместо шифрования кода одной большой программы переключиться на шифрование кодов маленьких подпрограмм. Исследователи считают, что обфускация будет проводиться в два шага. Усовершенствование любого из них повысит общую эффективность.

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

Еще никто не придумал, как эффективно скрыть даже маленькую программу самонастройки.

«Эта работа похожа на поиск иголки в стоге сена. Мы плотно застряли на этой программе самонастройки», — сообщил Сахай.

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

Это большой скачок. Чтобы зашифровать одну операцию, исследователям нужно знать размер входа и точную последовательность предстоящих расчетов. Компьютеры, напротив, настроены на то, чтобы считывать данные любой длины, совершая дополнительные расчеты по мере их поступления. Работы, представленные на STOC, показали, как можно использовать технику дискретного программирования, чтобы зашифровать длинные неоконченные расчеты в виде серии прерывистых, связанных друг с другом небольших вычислительных операций.

«Главное техническое достижение заключается в том, что мы применили НО для каждой из последовательных вычислительных операций и связали их вместе так, что под защитой оказалось все вычисление целиком», — заявила Эллисон Бишоп, программист из Колумбийского университета и соавтор одной из работ, представленных на STOC.

Математически доказанная защита

На пути к эффективности НО стоит практическая проблема. Для ее решения нужно доказать, что НО действительно безопасна.

Когда Сахай и программист из Техасского университета в Остине Брент Уотерс описали использование НО в 2013 году, заявление о том, что этот способ шифрования защитит данные внутри программы, должно было быть принято на веру. Их первоначальная работа была похожа на распутывание очень сложного узла — казалось, что это чрезвычайно сложно, но без понимания структуры самого узла нельзя было с уверенностью заявить, что нет простого способа его развязать.

«В тот момент у нас была лишь концепция, и мы даже не понимали, как можно доказать ее эффективность. У нас не было ни единой зацепки», — поделился Вайкунтанатан.

Брент Уотерс, программист из Техасского университета в Остине, демонстрирует, каким мощным криптографическим инструментом может быть НО. Фото Кристины Мюррей

С тех пор ситуация улучшилась. Любая хорошая криптографическая схема опирается на метематику, которая определяет проблемы, с которыми столкнется хакер при взломе кода. Шифрование по методу Райвеста-Шамира-Адлемана, например, использует произведение двух больших простых чисел. Чтобы прочитать вашу электронную почту, хакеру нужно будет на основании произведения определить два простых множителя — эта задача считается нерешаемой из-за пределов современной вычислительной мощности.

Математические условия, лежащие в основе криптографических схем, должны быть сложно решаемыми. В то же время они должны быть однозначными, давно проверенными и понятными, чтобы криптографы ясно представляли степень их сложности.

«Это должна быть такая математическая задача, которую мы хорошо понимаем. Иначе, как учит нас опыт, она скорее всего окажется взломанной» — отметил Сахай.

В 2013 году НО не имела работающих на практике защитных условий. В апреле 2014 года Уотерс, Бишоп и Крейг Джентри, ученый из исследовательского центра Томаса Дж. Уотсона в Йорктаун Хайтсе, Нью Йорк, опубликовали несколько статей с обсуждением проблем НО, а также набором простейших условий, связанных с математическими объектами под названием многолинейные карты. (Сахай был соавтором одной из публикаций.)

«Мы заявляем, что если хакер захочет взломать НО, ему придется решить одну из этих задач», — отметила Бишоп.

Многолинейные карты были введены в криптографию только в 2013 году. У экспертов не хватило времени строго оценить степень их надежности.

«Если вы прямо сейчас взломаете многолинейную карту, то никто не будет шокирован», — заметил Уотерс.

В настоящее время ученые-программисты стараются выяснить, как заменить многолинейные карты более понятными математическими препятствиями. Самым лучшим вариантом представляется «обучение на ошибках», одна из задач машинного обучения. Обучение на ошибках и многолинейные карты имеют общую математическую основу в области решеточной криптографии — именно поэтому они могут легко подменить друг друга. Тем не менее, до сих пор никто не понял, как это сделать.

«Мы как будто стоим перед расщелиной. Противоположный край так близко, мы можем допрыгнуть до него, но это не так-то просто», — делится Вайкунтанатен.

Погоня за безопасностью

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

«Мы надеемся уложиться в 10-15 лет», — заявил Сахай.

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

Вайкунтанатан настроен еще оптимистичнее: «Я бы даже сказал, что это займет пару лет»

Оптимизм — не единственный ресурс, вложенный в исследования НО за последние два года. Сейчас Сахай работает директором Центра функционального шифрования в Калифорнийском университете. Этот центр, работа которого посвящена исследованию обфускации во главе с Уотерсом и Бишоп, был образован в 2014 году и существует на средства гранта Национального научного фонда размером в 5 миллионов долларов. Прошлой осенью Агентство по перспективным оборонным научно-исследовательским разработкам США объявило о создании SafeWare, научно-исследовательской программы, поддерживающей создание «высокоэффективных и широкоприменяемых программ, основанных на методах обфускации с математически проверенным уровнем безопасности».

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

Автор: Кевин Харнетт.
Оригинал: Wired.

Перевела: Мария Гёрке
Редактировали: Артём Слободчиков и Евгений Урываев

Оцените статью
Добавить комментарий
  1. Артемий Александрович
    Артемий Александрович

    Security by obscurity?

  2. Василий Плешаков
    Василий Плешаков

    Я программист и я ничего не понял. У вас переводчики, знакомые с темами переводимых материалов?

  3. Кирилл Барковский
    Кирилл Барковский

    Я специалист по компьютерной безопасности и все понял) Но это всего лишь защита программного кода.

  4. Дмитрий Грушин
    Дмитрий Грушин

    Передайте, пжалста, вашему переводчику, что я ему желаю всю жизнь читать профессиональную литературу с переведёнными аббревиатурами. Как старые советские переводы научных статей. Все эти НМЖД, САШ, вот это вот всё.

    1. Богдан Рустамович
      Богдан Рустамович

      Dmitry, “игрофикация” из предыдущей статьи еще. АЖ ТРИСЁТ!

  5. Дмитрий Кобыжча
    Дмитрий Кобыжча

    Прочитал три раза, понял далеко не всё.

  6. Игнат Закатов
    Игнат Закатов

    плохой перевод ????

  7. Артём Кочикьян
    Артём Кочикьян

    Дочитал до второго абзаца после первой картинки и пошел читать оригинал.

    1. Василий Плешаков
      Василий Плешаков

      Artyom, надо сказать что и оригинал написан для “широкого круга читателей”

  8. Хуан Рико
    Хуан Рико

    справедливости ради надо заметить, что уже достаточно давно существует много RSA алгоритмов, которые с математической точки зрения более чем надёжны (для обычных компьютеров), но вот в протоколах, которые реализуют этот алгоритм, постоянно находят те или иные уязвимости.