В июле 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.
Метод назвали «обфускация неразличимости» [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.
Комментарии (9)
Biga
17.01.2016 09:23+1Можно сильно обфусцировать только критическую часть приложения, которая потребляет мизерное кол-во ресурсов, которая даже при замедлении в тысячу раз сможет работать за приемлимое время. Например, квестовую систему в игре.
Недавно писали, что китайцы до сих пор не могут взломать пару новых игр и, мол, ходят слухи, что успехи обфусцирования начинают опережать успехи взломщиков. С такими исследованиями — вполне может быть.
icoz
17.01.2016 14:05+1Читайте внимательнее. Одна (!) группа заявила, что один (!) их товарищ ковыряет эту защиту уже месяц — и пока не сломал.
Вся проблема заключается в отсутствии специализированного отладчика для 64битного режима.
Так что защита не устоит либо перед одним человеком, если у него будет специальный инструментарий, либо перед группой спецов, которым за это платят.
И вообще вся та история пахнет заказным заявлением и пиаром.
Mixim333
17.01.2016 10:25+2Лично мне кажется, что лет через 10-15 вообще не будет не opensource-приложений. Для примера, возьмем Microsoft и открытие, по-моему, в 2014 году кода .NET (https://github.com/Microsoft/dotnet) и кучи других проектов (https://github.com/Microsoft/). По-моему, все больше и больше майнтейнеров открывают свои исходники, делают первые шаги к этому, так что обфускация скоро станет таким же архаизмом, как дискеты 5 1/4" для рядовых пользователей.
DeOhrenelli
17.01.2016 12:05+1Там (во всех этих исследованиях обфускации) фантастическая дыра в подходе. Обфускация работает против обратной инженерии человеком (теорему Райса еще никто не отменял, и несмотря на то, что современные компьютеры — ни разу не машины Тюринга других средств оценки качества анализа программ с точки зрения сложности у нас все равно нет). Человек из исследуемой картины выкинут, причем исключительно потому, что для реверсера нельзя составить качественную модель.
iXCray
17.01.2016 12:26+2Пусть лучше придумают, как сделать так, чтоб все программы разрабатывались без ошибок, а не шифровать военный говнокод :D
stepik777
17.01.2016 13:54+1На хабре кстати была статья на эту тему.
Термин обфускация здесь не очень хорошо выбран и сбивает с толку, как видно по предыдущим комментаторам. С того же ответа, что и в первом комменте к этой статье:
Indistinguishability obfuscation is a rather esoteric property, which is not what non-academic think about when they hear «obfuscation»; the terminology is a misnomer. That property means that if you can encode some «processing» as a circuit (roughly speaking a piece of code which can be unrolled, with no infinite loop), such that there are several possible distinct circuits which yield the same results, then indistinguishability obfuscation allows publication of an «obfuscated circuit» such that anybody can run the circuit and obtain the result, but outsider cannot know which of the possible circuits was used as a basis internally.
What good IO can make, by itself, is unclear.
CodeRush
Не могу не процитировать часть вот этого ответа на SO, который однозначно стоит прочитать целиком:
В общем, насколько я понял из статей и процитированного ответа, там вся теоретическая обфускация разбивается о практическую производительность, и с этим за пару лет ничего сделать не получится.