22 апреля 2015 в 20:20

Обфускация программ

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

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

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

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

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

imageВ 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) вместе дают:
image
  • криптографию публичного ключа (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.
Валерия Николаенко @valerini
карма
30,0
рейтинг 0,0
Похожие публикации
Самое читаемое Разработка

Комментарии (75)

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

    Очень громкое и ложное утверждение, мода на эту тему иссякла лет 10 назад, лишь гики с креклаба сегодня с улыбкой вспомнят про vmprotect и execryptor. Все ушло в веб, и доступа к «установочным файлам программ» у пользователей нет, по причине физического исчезновения этих самых «установочных файлов». На мобильных платформах та же самая картина — логика любого приложения\сервиса находится на сервере. Вы можете вспомнить про игры, но никто в здравом уме не будет их реверсить, чтобы понять какие-то тайны и секреты, а обфускация внесет непомерные тормоза в игровой процесс…
    • +6
      Безотносительно темы статьи, говорить о том, что «всё уходит в облака» несколько преждевременно. Фото, видео и аудио-редакторы всё-ещё не могут жить в облаке так, что бы их использование не причиняло боль. Google Docs и аналоги очень неплохи, пока речь не идёт о документах в несколько десятков страниц. 1С и прочие тоже вроде должны неплохо жить в облаке, но коробочные их версии всё-ещё почему то активно покупают. Научный софт, медицинский, производственный… Много чего в облако не ушло и не уйдёт в ближайшее время. Точнее, уже лет 5 слышу, как всё уходит в облака, но указанный мною софт всё-равно как туда уйти не может. Удивительно блин…
      • –1
        Весь тот софт что вы перечислили использует очень малый процент пользователей. Модные нынче вещи, такие как общение (соц. сети, почта, мессенджеры), просмотр видео, поиск\покупки, не знаю что еще — у пользователя в руках лишь оббертка над апи.

        Вот почему-то Скайп еще вспомнился с его знаменитым неломаемым протоколом (хотя вроде уже поломали). Мне кажется, что реверсить клиент Скайпа — это последнее что вы должны сделать, если захотите написать свой аналог.
        • +2
          А перечисленные вами «модные нынче вещи» и не интересны в плане исследования исходного кода (тут более интересно смотреть на содержимое отправляемых пакетов и на уязвимости сервера).
          И что-то я не заметила физического исчезновения установочных файлов антивирусов, которые стоят далеко не у маленького процента пользователей.
          • –2
            Ну что вы… Поверьте, все самые востребованные алгоритмы (подсовывание нужной рекламы и т.п.) — все в соц. сетях и почте. Про установочные файлы антивирусов… Это о чем вообще?
            • 0
              Так это о вашей цитате
              Все ушло в веб, и доступа к «установочным файлам программ» у пользователей нет, по причине физического исчезновения этих самых «установочных файлов».
              • +1
                Я понял, но это был сарказм вообще-то и я надеялся что кто-то все же распишет что именно собирается обфусцировать в установочных файлах (любых программ) и что они вообще делают в статье. Вы, например, понимаете что такое «установочные фалы» и какова их роль?
                • +5
                  Установочные файлы очень важно обфусцировать, иначе злые хакеры взломают и сделают чекбоксы «мэйлру агент» и «яндекс-браузер» выключенными по умолчанию.
    • +1
      Эта статья о науке криптографии, а не о каких-то программах для обфускации экзешников. Облака и что куда ушло здесь совершенно не при чём.
      • +12
        Смысл понятия «Обфускатор Неразличимости», вокруг которого построена вся ваша статья, совершенно не раскрыт. Кроме громких заявлений, что это «теория всего», все криптографы посрамлены потрясены и т.п. в статье ничего нет. Спасибо за авторитетные источники в конце, но как-то не хочется тратить время на прочтение 44 страниц текста, изобилующего формулами.
        • +3
          Это не моя статья и я согласен с вами на счёт того что суть не раскрыта.
          • +2
            Простите, проглядел момент с авторством.
            Вот вы говорите что статья «не о каких-то программах для обфускации экзешников», но ведь статья называется «Обфускация программ» и в самом начале автор акцентирует на этом внимание. Сразу показалось подозрительным — «Давая пользователям доступ к установочным файлам программ...», я подумал, что автор просто неточно выразился, но теперь я понимаю что, скорее всего, дело в полном отрыве от реальности и непонимании предмета защиты.
            Если даже допустить, что существуют методы, превращающие любой алгоритм в «черный ящик», то как вся эта теория применима на практике?
            Вот, например, одна статья из, так сказать, «раннего», где я описываю метод использования чужого кода без каких либо попыток вникнуть в его суть. Как «Обфускация Неразличимости» поможет уберечься от такого «лома»?
            Как «Обфускация Неразличимости» будет влиять на производительность?
            Кроме того, не кажется ли вам, что «Обфускация Неразличимости» конфликтует с фундаментальным принципом, на котором зиждется современная криптография — принципом Керкгоффса?
        • 0
          Обфускацию черного ящика построить нельзя. Обфускация Неразличимости это лучшее, что теоретически возможно воплотить в жизнь на сегодняшний день. Кроме того, из существования ее вытекает существование многих других важных криптографических примитивов. Что бы вы хотели еще о ней узнать? Как она строится? На это не хватит страницы текста и без формул тут не обойтись. Как она строится не так важно, потому что существующая конструкция лишь кандидат, она очень неэффективна. Если вас интересует только практические, а не теоретические аспекты, то надо подождать появления лучших схем прежде чем разбираться.
          • 0
            К теории как раз вопросов нет, авторитетные лица занимаются гомоморфными методами шифрования не один десяток лет. Вопрос именно к прикладным аспектам, а именно попыткам применить данный метод ко всему чему можно и нельзя, без оглядки на то, имеет ли такое приложение какой-либо практический смысл. Даже если отбросить существующие проблемы в производительности и размерах, представить что их нет, зачем тащить это в код, исполняемый на машине пользователя (ведь именно об этом ваша статья)?
    • 0
      Применительно к вебу, обфускация актуальна для Javascript и платных PHP библиотек. Ну и для вредоносного ПО конечно тоже.
      • 0
        Для JavaScript актуальна разве что минификация кода для уменьшения его размера, что, отчасти, является и обфускацией тоже.
  • +19
    >Обфускация программ — это прорывная
    Нет. Что-то я не вижу статей о супер-обфускаторах, которые никто не может обратить.
    >самая горячая сегодня
    Нет. Наверное, это первая статья об обфускацию на хабре за 2015 год.
    >область криптографии
    Нет. В криптрографии не занимаются security through obscurity.

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

    Единственная работающая цель обфускации — давать головную боль тому, кто пытается разобраться с внутренностями программы.
    Все остальные цели или не достигаются, или некорректны.
    Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.
    • –8
      > Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.
      Представьте программу, которая берет например sha1 хэш от входа, использует его как ключ для расшифровки остальной части кода. Насколько большой запас терпения нужен чтобы разобраться, что же делает программа?

      Вот и связь с криптографией.

      > В криптрографии не занимаются security through obscurity.
      А как же whitebox имплементации шифров?
      • +5
        >Представьте программу, которая берет например sha1 хэш от входа, использует его как ключ для расшифровки остальной части кода.
        Это ортогонально обфускации. Я могу узнать, что одна часть программы расшифровывает другую, и окажусь в том же положении, если бы программа не была обфусцирована. Как только я получаю вход, я могу расшифровать вторую частьпрограммы и продолжить деобфускацию.

        >А как же whitebox имплементации шифров?
        Их пытаются изобрести для DRM, это задача, сломанная по определению.
        Вообще, что спорить — дайте программу, которая расшифровывает данные из stdin, использует известный алгоритм шифрования, а я попытаюсь выдрать из нее ключ.
        Я ставлю на что, это неосуществимо в общем случае.
        • –4
          > Я могу узнать, что одна часть программы расшифровывает другую, и окажусь в том же положении, если бы программа не была обфусцирована
          А если для каждого входа отдельный код? Узнав один вход, вы не узнаете что будет на другом. Если вход известен, деобфускация не нужна, можно просто запустить программу на этом входе и узнать выход (черный ящик). Но больше по программе вы ничего сказать не можете.

          Конечно, такая обфускация непрактична, но и топик-то о теории.

          > это задача, сломанная по определению. Я ставлю на что, это неосуществимо в общем случае.
          Спорить не буду, вполне возможно. Но опять же, топик о теории. Докажите.
          • +7
            А если для каждого входа отдельный код? Узнав один вход, вы не узнаете что будет на другом. Если вход известен, деобфускация не нужна, можно просто запустить программу на этом входе и узнать выход (черный ящик). Но больше по программе вы ничего сказать не можете.

            Не имеет значение кол-во шифрований, все равно вы будите должны процессору передать код который тот должен будет выполнить. Предположим, что у вас есть элементарный алгоритм z = x + y. Как вы его сможете зашифровать так чтобы процессор понял что нужно сделать, а человек нет? По сути, любая обфускация это просто создания огромного кол-ва лишних операций чтобы скрыть истинные, но истинные все равно нужно выполнять, а значит это попытка зашифровать сообщение в случае когда и алгоритм шифрования и все ключи всем известны, что невозможно по определению.
            • –4
              > все ключи всем известны
              Ключ — это вход для программы. На известных входах можно просто запустить программу и не нужна никакая деобфускация. Но и информации о программе это даст ровно то, что f(x1) = y1.

              Вот например мы обфусцируем программу f(x,y) = x + y если x != 31337 иначе f(x,y) = -1. Код получается такой:

              1. считаем хитрый хэш от входа
              2. если хэш = 1234567, расшифровать и выполнить код1 (ключ = вход)
              3. иначе вывести x + y

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

              • +5
                Чем не обфускация в самом обычном понимании? Исходный код «запутан».

                Это лишь означает что мы шагнем на шаг -1 и определим как считается хитрый хэш. И так шагаем назад пока не придем к началу начал.
                И тут два варианта:
                1) ключ расшифровки каждый раз приходит откуда извне, по сути тоже самое что все программа работала на веб сервисе,
                2) мы найдем изначальные ключи и сможем расшифровать весь алгоритм при неограниченном времени,

                Проблема обфускация в следующем: как по вашему можно ли зашифровать текст так чтобы из двух дешифровщиков один всегда мог его расшифровать, а второй всегда не мог, при том что знания ключей, алгоритмов и возможности дешифровщиков абсолютно одинаковые? Правильно это невозможно, тогда почему вы верите в возможность такого шифрования, чтобы процессор всегда смог дешифровать, а человек не мог?
                • –3
                  Ещё раз — никуда шагать не надо, если вход известен. На известном входе можно просто запустить программу.

                  > ключ расшифровки каждый раз приходит откуда извне, по сути тоже самое что все программа работала на веб сервисе,

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

                  Следуя вашей логике, не получается деобфусцировать — значит программа — веб-сервис. А ведь это и есть цель обфускации — из программы сделали черный ящик.
                  • +2
                    Вот например мы обфусцируем программу f(x,y) = x + y если x != 31337 иначе f(x,y) = -1. Код получается такой:

                    1. считаем хитрый хэш от входа
                    2. если хэш = 1234567, расшифровать и выполнить код1 (ключ = вход)
                    3. иначе вывести x + y

                    Проблема в том что как только в исходных данных появится x == 31337, весь алгоритм станет понятным. Я бы написал тут следующий алгоритм программы:
                    1. считаем хитрый хэш от входа
                    2. если хэш = 1234567, расшифровать код1 и отправить его мне по email, выводим пользователю ошибку «будет скоро исправлено»,
                    3. иначе вывести x + y

                    Если x == 31337 очень редкое значение это не выстрелит, если очень частое станет известно ещё во время тестирования. По большому счету автоматически такие трюки не сделать, а в ручном режиме больше сил будет потрачено на защиту, чем на её взлом.
                    • +1
                      Я правильно понимаю суть вашей защиты, мы парсим большой текстовый файл по хитрому алгоритму и если вдруг встречаем слово «глокакуздра», понимаем что оно равно нужному нам хешу, расшифровываем и запускаем секретный код?
                      Ну, во-первых, очень редко когда такая защита применима. Во-вторых, много бессмысленного ручного труда. В-третьих, такую защиту можно взломать просто как я описал выше, обнаруживая у пользователя переход в зашифрованный блок и расшифровку его с последующим фиксом в следующей версии. Ну, максимум это немного осложнит жизнь ворам.
                      • –1
                        Я сразу написал, что такая обфускация непрактична. Это был контрпример к

                        > Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.

                        Топик о теоретических подходах к определению обфускации и теоретических пределах. Мой пример — «игрушечный» и к практике имеет мало отношения. Я хотел показать, что криптография по сути может являться обфускацией. Если заменить hash(x) == 123456 на x == 123456 то ведь будет очевидно, что делает код? А если взять что-то посередине, функцию попроще? Где граница между обфускацией и криптографией?
                    • 0
                      Ну вот — уже патчим код, посылаем юзера, айяйяй. Статично никак? Значит обфускация работает.
              • +4
                Ключ — это вход для программы.
                Извините, но вы когда-нибудь IDA запускали?
              • +4
                Раз уж вы о теории, то сколько бы не написали таких вариантов кода для разных входов, все равно их все можно восстановить и вся программа будет как на ладони. Ваш пример это ровно тоже самое, что рядом с шифрованным блоком данных положить ключ. В итоге это вырождается в обычный обфусцированный код с кучей мусора, который нормальным специалистом так или иначе отсеивается.
                А если мы учтем практичность, то количество комбинаций вход-код будет очень мало, поэтому все становится просто элементарным.

                Именно поэтому единственные варианты, которые до сих пор применяют серьезные конторы это:
                -ключ приходит по сети
                -ключ находится в самом кристалле процессора
                Но это все тоже самое security through obscurity и в конечно итоге все выплывает наружу.
                • 0
                  Плюс вариант, когда важная часть алгоритма реализуется на внешнем устройстве и/или сервисе. Тогда приходим к черному ящику.
    • –4
      >самая горячая сегодня
      Нет. Наверное, это первая статья об обфускацию на хабре за 2015 год.
      На хабре много о чём статей нет, значит всего этого не существует?

      >область криптографии
      Нет. В криптрографии не занимаются security through obscurity.
      Это не security through obscurity.
      Откуда же тогда столько статей на эту тему: scholar.google.com/scholar?start=0&q=Indistinguishability+Obfuscation&hl=en

      Единственная работающая цель обфускации — давать головную боль тому, кто пытается разобраться с внутренностями программы.
      Все остальные цели или не достигаются, или некорректны.

      Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.
      У вас конечно же есть доказательство этого факта?
      • +3
        >У вас конечно же есть доказательство этого факта?
        Например то, что нет схем DRM, которая имплементирована целиком в софте, которую еще не обошли.
        • +1
          Не ради холивара, но просто для уточнения: невозможность наблюдения ни разу не аргумент в пользу невозможности события. (© Бозон Хиггса и Сэр Гравитон.)
    • 0
      Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.


      Если предположить, что гомоморфное шифрование (из предыдущей статьи автора) существует, то тогда алгоритмы шифруются элементарно.

      Скажем алгоритм некоей нелинейной цифровой фильтации. Его секретом являются коэффициенты.
      Наука пока не в курсе, как имея знания о сигналах на входе и выходе такого фильтра восстановить его структуру.
      Вы беретесь дизассемблировать и узнать коэффициенты, а оказывается что они зашифрованы и вот в таком зашифрованном виде участвуют в вычислениях. Сами вычисления, естественно, уже не будут напоминать фильтр. Входной поток тоже получаете зашифрованный. Выходной проток, конечно, расшифровывается, но шифрование несимметричное.
      И все, тупик. Ничего сделать невозможно.
      • +2
        Это не обфусцированние программы — мы получаем несколько потоков зашифрованных данных, делаем какие-то операции над ними, расшифровываем их и получаем не шифрованные данные, при чем тут шифрование кода программы?

        По сути, раз входной поток кто-то где-то шифрует, то и секретные коэффициенты можно там же сразу наложить, то есть это лишь частный случай некоторого алгоритма на чужом сервисе к которому у нас нет доступа.
        • 0
          Фильтрация идет на стороне клиента. Сервер не при чем.
          Ну возьмем тогда сжатие для простоты понимания.
          Эти алгоритмы тоже базируются на волшебных константах. На сервере сжимается на клиенте разжимается.
          Но с помощью гомоморфного шифрования константы становятся недоступными.
          И насколько я понял принцип гомоморфного шифрования алгоритм тоже меняется до неузнаваемости.
    • –9
      > Нет. В криптрографии не занимаются security through obscurity.

      Шифр AES — это ни что иное как security by obscurity и этот шифр ваш браузер использует каждый день. Кроме того весь ваш трафик шифруется исключительно AES, «настоящие» криптографические примитивы (RSA или Diffie-Hellman) используются только для того, чтобы установить общий для двух сторон ключ для AES.

      > В реальном мире не бывает двух программ с абсолютно идентичной функциональностью

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

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

      Давайте я лучше приведу пример: вы написали мощную программу — Photoshop Ultimate edition, но есть пользователь, который хочет минимум функциональности от Photoshop, он хочет делать простейшую обработку своих фотографий, он не хочет платить 700$. Для него вы хотите выпустить Photoshop Light за 300$. Чтобы это сделать сегодня, вам надо удалить всю ненужную функциональность и пересобрать весь проект (это первый вариант программы — P1). Если вы хотите сделать Photoshop Web edition, вам опять же надо сделать то же самое. Но вместо этого вы можете в начале программы задать права доступа (permissions), закодировать их прямо в код (hardcore them into the code) и в самом коде вы будете проверять, если у пользователя есть необходимые права, ему будет доступна та или иная опция, если нет, то нет (это второй вариант программы — P2). Функциональности — идентичны (но второй вариант гораздо проще и легче в реализации). Поэтому обфускация неразличимости второго варианта будет неотличима от обфускации неразличимости первого варианта и вы не сможете получить доступ к скрытой от вас функциональности, ее как будто в коде нет!
      • +9
        >Шифр AES — это ни что иное как security by obscurity
        Нет. Все знают алгоритм AES. Конечный пользователь знает секретный ключ. Единственное ограничение — третьи лица не знают секретный ключ.

        «White box encryption» предлагает такое решение, при котором конечному пользователю дают софт, который может расшифровать AES, но при этом пользователь не может выдрать ключ из софта, потому что программа запутанная.

        >Но вместо этого вы можете в начале программы задать права доступа (permissions), закодировать их прямо в код
        Это называется «DRM» и эта идея неполноценна в корне.
        • –4
          > Нет. Все знают алгоритм AES. Конечный пользователь знает секретный ключ. Единственное ограничение — третьи лица не знают секретный ключ.

          Security by obscurity в отношении к алгоритму — это не имение математического доказательства его устойчивости. AES такого не имеет, AES показывает устойчивость к статистическим тестам и существующим атакам, но никто не гарантирует, что хорошую атаку невозможно или очень сложно найти в принципе.

          > Это называется «DRM» и эта идея неполноценна в корне.

          DRM — это собирательный термин. Что именно вы считаете «неполноценным в корне»?
          Теория доказывает, что приведенный выше мной пример полностью устойчив, т.е. получить доступ к скрытой функциональности, если вы используете обфускацию неразличимости, невозможно.
          • +4
            > Security by obscurity в отношении к алгоритму — это не имение математического доказательства его устойчивости.

            In security engineering, security through obscurity is the use of secrecy of the design or implementation to provide security.


            А то, знаете, так можно далеко зайти. Для RSA тоже нет математического доказательства устойчивости (более того, для квантового компьютера есть доказательство неустойчивости). Существование односторонних функций как таковых вообще не доказано, и само по себе чистая эвристика — «что-то, что вроде работает и пока никто не взломал».
          • +6
            Мне надоело показывать, что каждое утверждение в комменте является некорректным, или бессмыссленным.

            > это не имение математического доказательства его «устойчивости».
            Ни один алгоритм шифрования не имеет доказательства его устойчивости. Есть алгоритмы, которые оприваются на NP-полные задачи. Есть другие алгоритмы, для которых еще не известны атаки. Ни для одних, ни для других доказательства «устойчивости» нет.

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

            > Теория доказывает, что приведенный выше мной пример полностью устойчив
            Что это нам теория говорит об ограничении функциональности через «установку прав в начале программы»?
            Это две разные функции, теория неприменима.
            Например, функция P1(«Нарисуй круг»)=(рисует круг) и P2(«Нарисуй круг»)=(купите про версию фотошопа)

            > получить доступ к скрытой функциональности, если вы используете обфускацию неразличимости, невозможно.
            Что это нам теория говорит об «скрытой функциональности»? Ничего.
            • +4
              > Ни один алгоритм шифрования не имеет доказательства его устойчивости.

              Одноразовый блокнот — имеет, прошу прощения за занудство) I'm fun at parties
              • +1
                Забыл про него :)
    • 0
      >Обфускация программ — это прорывная
      > Нет. Что-то я не вижу статей о супер-обфускаторах, которые никто не может обратить.
      > самая горячая сегодня
      > Нет. Наверное, это первая статья об обфускацию на хабре за 2015 год.

      < Читать надо статьи на английском и не на хабре

      > область криптографии
      > Нет. В криптрографии не занимаются security through obscurity.

      < obscurity это не математическая обфускация.

      > В реальном мире не бывает двух программ с абсолютно идентичной функциональностью, если это не одна и та же программа.

      < i+=2 vs i++; i++;

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

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

        > i+=2 vs i++; i++;

        1. Математически, это две одинаковые программы и они скомпилируются в один и тот же машинный код оптимизирующим компилятором.
        2. Если они скомпилируются в разный код, то будут отличаться по таймигу.
        3. Это не программа из реального мира.

        > абсолютно некорректное утверждение.

        История показывает обратное — люди разбирают существующие программы и неимоверное количество кряков в прошлом это весомый аргумент в мою сторону. Какие ваши аргументы?
        • 0
          Как я уже писал ниже из существования универсальной математической обфускации следовало бы существование систем WhiteBox криптографии, возможно было бы построить ассиметричные схемы шифрования на основе симметричных, возможно было бы построить системы полного гомоморфного шифрования и многое другое.

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

          Суть заключаются в том, что ещё никто не реализовал обфускацию с математической точки зрения, и данная работа первая в этом роде.

          Далее возникает вопрос о том, чего мы хотим от обфускации в смысле защиты ПО. Пусть есть функция f(x)=x+с_1. Ясно, что как бы мы не обфусцировали её то по любому представлению функции элементарно можно определить с_1.

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

          Суть понятия обфускации можно понять в следующем примере. Пусть у нас есть произвольная функция f(x).
          Пусть x и значение функции имеют размер в 16 бит. Идеальная обфускация функции — это просто таблица значений f(x) от x. Очевидно, что это не эффективная обфускация, но зато она удовлетворяет определению в терминах черного ящика. Мы не получим из кода обфусцированной функции больше информации чем от доступа к оракулу f(x). Т.е. процесс запуска функции на различных входах и таблица значений дают нам одинаковую информацию с одинаковой асимптотикой. При этом если вид f(x) невозможно эффективно восстановить по парам вход выход, то ничего нельзя будет у знать о f(x) по её коду. Чтобы прочувствовать это
          возьмите какую-нибудь нетривиальную функцию типа f(x) = sin(x/100)+x^x+x!, запишите её в виде таблицы значений и попробуйте её восстановить. В этом заключается суть понятия обфускации в терминах определения черного ящика.

          Вычислительно неразличимая обфускация это нечто другое. Вот пример из жизни, где она может пригодиться. Пусть мы разрабатываем ПО и хотим сделать демо версию. Можно просто ограничить функциональность на ровне интерфейса — это быстро, но небезопасно. Можно долго выпиливать код из исходноков, это надежно, но долго. А можно применить iO. Возьмем ПО, ограниченое на уровне интерфейса. Тогда iO от такого ПО будет вычислительно неотличимо от реальной демо версии ПО. Следовательно, мы легко и быстро сделали надежную демо версию ПО.
          • 0
            Да, я уже говорил, что я читал научные статьи про математическую обфускацию.
            Основная проблема, которую я вижу — есть классы функций, которые нельзя безопасно обфусцировать,
            и есть *некоторые* функции, для которых придумали обфускацию. Этих функций очень мало, они «скучные» или их роль может выполнить другим путем.

            > обфускация ПО для противодействия поиска уязвимости по патчу

            Я вижу две проблемы:
            — мне дается код, который я не должен понимать и он должен предоставить мне «безопасность». Security though obscurity.
            — для детектирования «атаки» может понадобиться такая функция, которую невозможно безопасно обфусцировать.

            > маркировка ПО.

            Зачем?

            > Существование универсальной обфускации в терминах определения чёрного ящика дало бы нам полную защиту ПО от обратной разработки.

            Это *совершенно* ужасная цель.

            > Можно просто ограничить функциональность на ровне интерфейса

            Я уже много раз говорил это, но повторюсь: DRM это фундаментально плохая идея. Она не несет *ничего* хорошего.
  • 0
    Алгоритм нельзя украсть, так как он не является объектом авторского права.
    • 0
      А как же патенты на алгоритмы? Причем патенты, которые, естественно не раскрывают все know-hows.
      • +4
        Мир не ограничен США
        • 0
          «Авторские права на все виды программ для ЭВМ (в том числе на операционные системы и программные комплексы), которые могут быть выражены на любом языке и в любой форме, включая исходный текст и объектный код, охраняются так же, как авторские права на произведения литературы.» Статья 1261 Гражданского Кодекса РФ

          «Правообладатель в течение срока действия исключительного права на программу для ЭВМ или на базу данных может по своему желанию зарегистрировать такую программу или такую базу данных в федеральном органе исполнительной власти по интеллектуальной собственности.» Статья 1262 Гражданского Кодекса РФ
          • 0
            И причём здесь
            патенты на алгоритмы
            ? Авторские и смежные права на произведение (в т. ч. программу для ЭВМ) не имеют никакого отношения к патентам (кроме того, что тоже обсуждаются в 4 части ГК РФ).
  • –2
    Да да, надо прятать исходники и никому не показывать, ведь БГ так делал и теперь самый богатый чел на планете :)

    В реальности интересных алгоритмов единицы, именно алгоритмов, а не конкретных технических решений.
    Те вот RAR это алгоритм, а nginx решение. Последнее можно сделать и самому, просто нужно долго кодить и вникать. А первое долго думать.
    Но почти всегда есть аналоги в свободном доступе, часто с исходниками.

    На практике обфускацию видел во всяких навесных защитах на виндовый софт и вирусах.
  • 0
    Тот новый вид обфускатора называется «Обфускация Неразличимости» («Indistinguishability Obfuscation» — «iO»), формально: если имеются две разные программы, но с абсолютно идентичными функциональностями, то обфускации этих двух программ будут неотличимы друг от друга.

    На пальцах, у меня есть программа с алгоритмом «x = y + z — t» она неотличима от по функциональности от программы «x = y — t + z», ни от программы «x = z — t + y». C точки зрения, определения «Обфускация Неразличимости» банальная перестановка суммы слагаемых дает нам эту самую идеальную обфускацию! Как вы прекрасно понимаете конкуренту достаточно получить лишь один из алгоритмов с абсолютно идентичными функциональностями (и желательно близко по размеру и сложности оригинальному), чему такая «Обфускация Неразличимости» никак не помешает. Ну, какая мне разница что алгоритм полученный после реверс инженеринга будет не совсем таким же как тот что был изначальный, если его функциональность идентична оригиналу?

    Другими словами, весь этот великий алгоритм это проста игра с определениями: «дадим новое определение Искусственного интеллекта. ИИ это программа способная сложить два числа. Ура, теперь в моем калькуляторе живет ИИ!»
    • –1
      В статье [3] как раз доказывается, что «Indistinguishability Obfuscation» — лучшее, чего можно достичь.

      «На пальцах»,
      представьте произвольную идеальную обфускацию этого же алгоритма (x = y + z — t). Скормим этот (кем-то) обфусцированный код тому же идеальному обфускатору. Что же он выведет? А выведет он «банальную перестановку суммы» x = y + z — t, ведь исходные программы функционально одинаковы, значит и обфусцированные версии должны быть неотличимы. А это значит, что мы эффективно деобфусцировали исходную идеальную обфускацию и поэтому наш обфускатор (перестановка слагаемых) не хуже того идеального.

      Вы можете сказать, что тогда хорошая обфускация невозможна — ведь предложенные вами «обфускации» подходят под определение, а значит это лучшее, чего можно достичь. Вот только мелочь: заверните ваш метод в эффективный алгоритм, да так, чтобы любой запутанный код, эквивалентный (x = y + z — t) он тоже развернул в x = y + z — t. Тогда действительно обфускация невозможна, ведь ваш алгоритм будет отличным деобфускатором.
      • –1
        Опечатка, «Скормим этот (кем-то) обфусцированный код тому же идеальному обфускатору» — конечно же код скормим Indistinguishability обфускатору (который по предположению vedenin1980 может выводить просто перестановку слагаемых).
        • 0
          если имеются две разные программы, но с абсолютно идентичными функциональностями, то обфускации этих двух программ будут неотличимы друг от друга.

          Тут вы скорее всего где-то ошиблись в переводе, если функциональности всегда одинаковые это не две разные программы, а одна программа по разному переписанная, то есть если f(P1) всегда равна f(P2), где f — результат работы программы, то для нас программы по сути одинаковы.
          • –1
            Вы где такое определение «программы» нашли?
  • –6
    Первая картинка, правая сторона на стринги очень смахивает. А я всё думал, почему эта тема меня внезапно заинтересовала?
    #Весна
  • 0
    Давайте я приведу пример, может быть это многое прояснит (он из одного из предыдущих комментариев):

    Вы написали мощную программу — Photoshop Ultimate Edition, но есть пользователь, который хочет минимум функциональности от Photoshop, он хочет делать простейшую обработку своих фотографий, он не хочет платить 700$. Для него вы хотите выпустить Photoshop Light Edition за 300$. Чтобы это сделать сегодня, вам надо удалить всю ненужную функциональность и пересобрать весь проект (это первый вариант программы — P1). Если вы хотите сделать Photoshop Web Edition, вам опять же надо сделать то же самое. Но вместо этого вы можете в начале программы задать права доступа (permissions), закодировать их прямо в код и в самом коде вы будете проверять, если у пользователя есть необходимые права, ему будет доступна та или иная опция, если нет, то нет (это второй вариант программы — P2). Функциональности — идентичны, поэтому обфускация неразличимости второго варианта будет неотличима от обфускации неразличимости первого варианта, и вы не сможете получить доступ к скрытой от вас функциональности, ее как будто в коде нет! Второй вариант, однако, гораздо проще и легче в реализации и породит гораздо меньше ошибок.
    • +1
      То есть, покупая Photoshop Light Edition с ограниченным функционалом, оно будет всё равно весить как Photoshop Ultimate Edition?
      • +2
        Может быть чуть больше, ведь туда добавлен функционал проверки прав доступа
  • 0
    Вот будет смешно, если iO делает NP из P задачи.
    • +1
      О, знаете что iO делает… она делает вот какую прикольную штуку: называется Witness Encryption (WE). В WE вы шифруете свое сообщение для, например, SAT формулы и только тот может его расшифровать, кто знает выполняющий набор к этой формуле! (вместо SAT может быть любая другая NP полная задача). Но вам для шифрования необязательно знать выполняющий набор.
      • +1
        Мне непонятно, как это применить для обфускации того же фотошопа.

        Секретный выполняющий набор присутствует на компьютере пользователя? Если нет, зачем он вообще нужен. Если да, какой же он секретный.
        • 0
          Я говорю о сведении задачи построения Witness Encryption к задачи построения indistinguishability Obfuscation. Это теоретический результат. Секретный выполняющий набор может нигде не хранится, его может не знать человек, который шифрует. Но человек, который хочет расшифровать сообщение должен найти этот выполняющий набор. Это просто очень на мой взгляд интересная своего рода связь теории сложности с криптографией.
          • +1
            Было бы неплохо объяснить это в статье, потому что в русском интернете вообще ничего нет.
  • 0
    Мне не хочется читать литературу по ссылкам, но a1 ~ a2 => f(a1) = f(a2) реализовать невозможно.
    • 0
      Не очень понимаю, что вы имеете в виду… Что такое a1, a2 и f?
  • 0
    Хех. Буквально два часа назад усиленно искал обфускатор для HDL кода. Пришел к выводу что проще и надёжнее ngc'шником отдать =)
  • 0
    Не являюсь специалистом по теме, даже не владею всем понятийным аппаратом в полной мере, но всё же.

    На первый взгляд, в данной статье указан в явном виде базовый примитив, который уже давно используется для определения безопасности криптографических примитивов. А именно, схема доказательства некоторых свойств стойкости алгоритмов с точки зрения неразличимости для некоторого advisor (советника) выхода алгоритма и случайного выхода, но расширенный также на выход другого алгоритма.

    То, что этот базовый примитив можно выразить в терминах обфускации схем вычислений, это хорошо — удобная абстракция обычно подталкивает развитие отрасль знаний. В PDF часть этих результатов указана (как я понял, сведение других понятий к понятию неразличимой обфускации). Думаю, там ещё много всего интересного, но пока не успеваю подробно прочитать и понять.

    Но можете объяснить, что ещё стоит понять из вашей статьи, на что обратить внимание? Думаю, многие на данном ресурсе будут ждать конкретной схемы обфускации, которая решит все их возможные проблемы. Можете ли вы для них подчеркнуть, есть ли готовые практические алгоритмы, а также какие теоретические задачи iO уже решила, которые были не решены раньше?
    • 0
      Да, вы очень хорошо сформулировали суть — это удобная абстракция. Схемы для этой обфускации еще более медленные, к сожалению, чем даже для Fully Homomorphic Encryption. Так что пока эта тема представляет только теоретический интерес. Конкретная схема обфускации есть, но она основана на нестандартном предположении (nonstandart assumption), т.е. это не хорошо всеми изученные RSA assumption или discrete log, а новое предположение, которое не очень понятно, как анализировать, потому что оно очень громоздко…

      iO решила, например, deniable encryption. Это задача очень долго в теории была открытой. Приложение этого шифрования очень привлекательно: допустим, вас поймали мошенники и хотят, чтобы бы вы предоставить им свои секретные ключи, чтобы они могли расшифровать всю вашу переписку. Если вы пользовались не обычной схемой шифрования, а deniable encryption, вы можете создать фальшивый секретный ключ, который будет неотличим от настоящего, но при этом расшифрует все ваши сообщения во что-нибудь другое что вы подготовите заранее, такой же длины.

      iO дает асимптотически самые короткие электронные подписи. Т.е. теоретически довольно долго искали подписи, которые так сложно подделать, как просто напросто угадать все биты подписи. Раньше если мы хотели, чтобы атакующий делал не более 2^λ операций, длины подписи должна была быть 2λ бит — то есть в два раза больше, чем теоретически возможно. А iO дает подписи оптимальной длины — λ.

      iO дает возможность n > 2 пользователям согласовать общий ключ, без помощи какой-либо централизованной системы (NIKE — non-interactive key exchange). Каждый пользователь пишет что-то на «доску», после того, как все что-то написали, все пользователи считывают все значения с доски и после произведения некоторых операций, все они должны получить общий ключ, который не будет известен никому, кто ничего не писал на доску.

      Есть еще много задач, которые решила iO и которые пока не решены без нее.
  • +2
    Ужаснейший перевод: от слов «криптографию публичного ключа», «обфускация неразличимости» выворачивает наизнанку.

    Отсутствует понимание сути как у комментирующих, так и, возможно, у автора.

    Начну с того, что Indistinguishability Obfuscation корректнее переводить как вычислительно неразличимая обфускация,
    согласно, например, этому определению en.wikipedia.org/wiki/Computational_indistinguishability.

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

    В статье [1] доказывается невозможность построения системы универсальной обфускации и вводится более слабое определение вычислительно неразличимой обфускации + доказывается её существование. Поэтому работа [2] есть просто конкретная реализация iO.

    Важно понимать, что сама iO — это криптографический примитив, применимость которого не столь очевидна, как универсальной обфускации. В статье показано, как на основе iO получить функциональное шифрование и больше ничего.

    Далее. Конструкция из [2] требует существования системы полного гомоморфного шифрования, что уже переводит работу в разряд теоретических. На сколько я знаю, самый эффективный (и пока ещё общепризнанно стойкий) метод гомоморфного шифрования требует использования ключа в несколько Гб.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.