Обфускация программ — это прорывная, самая горячая сегодня, область криптографии. За последние два года написано свыше 70ти статей по этой теме, она вызывает жаркие дискуссии, создает настоящие гонки между исследовательскими группами, открывает полигон для научных изысканий. Более того, оказывается, что обфускация — фундаментальный, образующий примитив, который порождает практически всё, что мы имеем в криптографии сегодня. Разберемся, с тем что же это такое.

Давая пользователям доступ к установочным файлам программ, компании неизбежно раскрывают свои профессиональные секреты и наработки, и ничто не останавливает злобонравных конкурентов от беззастенчивого копирования и воровства чужих алгоритмов. Обратим внимание и на другой пример, это важные обновления (патчи), исправляющие ошибки в операционных системах. Почти мгновенно очередное обновление анализируется хакерами, они выявляют проблему которую это обновление чинит, и атакуют несчастных, не успевших вовремя обновиться, пользователей.
Эти две ситуации связывает одна фундаментальная проблема, а именно: написанная человеком программа может быть человеком же и понята, проанализирована, разобрана. А что если существовал бы алгоритм, который бы мог до неузнаваемости, необратимо переделать программу при этом сохраняя ее функциональность? Так чтобы программу совершенно невозможно было бы понять, но при этом она работала бы ничуть не хуже исходной? Такой алгоритм и называется «обфусцирующий» или «обфускатор».

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

Но что же конкретно мы хотим от обфускатора? «Невозможность понять программу» которую он выдает звучит весьма туманно…

В 2001[1] году впервые было предложено формальное определение: результирующая программа, выдаваемая обфускатором, должна давать не больше информации, чем просто напросто черный ящик, который имитирует входное/выходное поведение исходной программы. То есть не должно быть никакой разницы между обфусцированным кодом программы и, например, веб сервисом, который просто возвращает результат программы на данном ему входе. Такой алгоритм получил название «Обфускация Черного Ящика» («Black Box Obfuscation»). К сожалению, в той же статье было показано что такой обфускатор невозможно построить для всех программ. А именно, есть весьма специфический класс программ, который невозможно обфусцировать: это программы которые на собственном входе возвращают некоторый секрет[1], Theorem 3.4. С тех пор это направление исследований заглохло, люди приуныли и обфускация программ целых 12 лет считалась невозможной.

В 2013[2] году в этой области был совершен прорыв, теоретиками было вытащено на свет другое определение и предложена настоящая конструкция для него. Этот новый вид обфускатора называется «Обфускация Неразличимости» («Indistinguishability Obfuscation» — «iO»), формально: если имеются две разные программы, но с абсолютно идентичными функциональностями, то обфускации этих двух программ будут неотличимы друг от друга. То есть, если я имею программы P1, P2, такие что для любого входа x, P1(x) = P2(x), а O — это обфускатор неразличимости, который принимает на вход программу P и возвращает новую программу O(P), то невозможно будет отличить O(P1) и O(P2). То есть вы не сможете сказать, какая обфускация какой изначальной программе принадлежит, то ли O(P1) — это обфускация P1, то ли это обфускация P2. (Обфускатор O — вероятностный алгоритм). На первый взгляд, не понятно, на сколько хорош такой обфускатор. Ответ на этот вопрос, о котором рассказывается в следующих двух параграфах, сотряс сообщество криптографов.

В 2007[3] году был исследован «лучший» обфускатор. Было предложено называть обфускатор «лучшим», если обфусцированная программа сообщает не больше информации, чем любая другая программа с той же функциональностью. И было показано, что Обфускатор Неразличимости — это и есть «лучший» обфускатор. Таким образом конструкция-кандидат лучшего обфускатора на свете уже у нас в кармане! И скоро не надо будет изощряться в перепутывании инструкций и переименовании переменных.

Но на этом история не заканчивается, к величайшему удивлению криптографов по всему миру, оказалось, что Обфускатор Неразличимости вместе с односторонними функциями (One-Way Functions) вместе дают:

  • криптографию публичного ключа (public key encryption)
  • короткие цифровые подписи (short signatures)
  • неинтерактивные доказательства с нулевым разглашением (NIZKs — Non-Interactive Zero Knowledge Proofs)
  • забывчивую передачу (Oblivious Transfer)
  • протокол конфиденциального вычисления (Multi-party computation protocols)
  • протокол вещания (Broadcast encryption)
  • оспариваемое шифрование (Deniable encryption) (в этой схеме можно предоставить ложный ключ к шифру, которые расшифрует все посланные вами сообщения во что вам угодно)
  • вместе с полностью гомоморфным шифрованием, дают функциональное шифрование (Functional Encryption)
  • и многое, многое другое


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

Ссылки


[1] Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S. and Yang K. «On the (im) possibility of obfuscating programs.» CRYPTO 2001.
[2] Garg S., Gentry C., Halevi S., Raykova M., Sahai A., and Waters B. «Candidate indistinguishability obfuscation and functional encryption for all circuits.» FOCS 2013. (pdf)
[3] Goldwasser S., and Guy N. R. «On best-possible obfuscation.» TCC 2007.