Давая пользователям доступ к установочным файлам программ, компании неизбежно раскрывают свои профессиональные секреты и наработки, и ничто не останавливает злобонравных конкурентов от беззастенчивого копирования и воровства чужих алгоритмов. Обратим внимание и на другой пример, это важные обновления (патчи), исправляющие ошибки в операционных системах. Почти мгновенно очередное обновление анализируется хакерами, они выявляют проблему которую это обновление чинит, и атакуют несчастных, не успевших вовремя обновиться, пользователей.
Эти две ситуации связывает одна фундаментальная проблема, а именно: написанная человеком программа может быть человеком же и понята, проанализирована, разобрана. А что если существовал бы алгоритм, который бы мог до неузнаваемости, необратимо переделать программу при этом сохраняя ее функциональность? Так чтобы программу совершенно невозможно было бы понять, но при этом она работала бы ничуть не хуже исходной? Такой алгоритм и называется «обфусцирующий» или «обфускатор».В распоряжении разработчиков на данный момент не существует хороших обфускаторов, а те обфускаторы, которые широко используются сегодня, весьма примитивны — они могут переставлять инструкции, заменять имена переменных, вставлять куски кода, которые на самом деле имеют нулевой эффект и делать аналогичные вещи, которые в целом можно назвать «безопасность через непонятность». Но такие обфускации при небольшом усердии легко деобфусцировать, а потому это не преграда для хороших хакеров.
Но что же конкретно мы хотим от обфускатора? «Невозможность понять программу» которую он выдает звучит весьма туманно…
В 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.
Комментарии (70)
m1el
22.04.2015 21:11+19>Обфускация программ — это прорывная
Нет. Что-то я не вижу статей о супер-обфускаторах, которые никто не может обратить.
>самая горячая сегодня
Нет. Наверное, это первая статья об обфускацию на хабре за 2015 год.
>область криптографии
Нет. В криптрографии не занимаются security through obscurity.
>формально: если имеются две разные программы, но с абсолютно идентичными функциональностями
В реальном мире не бывает двух программ с абсолютно идентичной функциональностью, если это не одна и та же программа.
Единственная работающая цель обфускации — давать головную боль тому, кто пытается разобраться с внутренностями программы.
Все остальные цели или не достигаются, или некорректны.
Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.
hellman
22.04.2015 21:48-8> Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.
Представьте программу, которая берет например sha1 хэш от входа, использует его как ключ для расшифровки остальной части кода. Насколько большой запас терпения нужен чтобы разобраться, что же делает программа?
Вот и связь с криптографией.
> В криптрографии не занимаются security through obscurity.
А как же whitebox имплементации шифров?m1el
22.04.2015 22:23+5>Представьте программу, которая берет например sha1 хэш от входа, использует его как ключ для расшифровки остальной части кода.
Это ортогонально обфускации. Я могу узнать, что одна часть программы расшифровывает другую, и окажусь в том же положении, если бы программа не была обфусцирована. Как только я получаю вход, я могу расшифровать вторую частьпрограммы и продолжить деобфускацию.
>А как же whitebox имплементации шифров?
Их пытаются изобрести для DRM, это задача, сломанная по определению.
Вообще, что спорить — дайте программу, которая расшифровывает данные из stdin, использует известный алгоритм шифрования, а я попытаюсь выдрать из нее ключ.
Я ставлю на что, это неосуществимо в общем случае.hellman
22.04.2015 22:51-4> Я могу узнать, что одна часть программы расшифровывает другую, и окажусь в том же положении, если бы программа не была обфусцирована
А если для каждого входа отдельный код? Узнав один вход, вы не узнаете что будет на другом. Если вход известен, деобфускация не нужна, можно просто запустить программу на этом входе и узнать выход (черный ящик). Но больше по программе вы ничего сказать не можете.
Конечно, такая обфускация непрактична, но и топик-то о теории.
> это задача, сломанная по определению. Я ставлю на что, это неосуществимо в общем случае.
Спорить не буду, вполне возможно. Но опять же, топик о теории. Докажите.
vedenin1980
22.04.2015 23:51+7А если для каждого входа отдельный код? Узнав один вход, вы не узнаете что будет на другом. Если вход известен, деобфускация не нужна, можно просто запустить программу на этом входе и узнать выход (черный ящик). Но больше по программе вы ничего сказать не можете.
Не имеет значение кол-во шифрований, все равно вы будите должны процессору передать код который тот должен будет выполнить. Предположим, что у вас есть элементарный алгоритм z = x + y. Как вы его сможете зашифровать так чтобы процессор понял что нужно сделать, а человек нет? По сути, любая обфускация это просто создания огромного кол-ва лишних операций чтобы скрыть истинные, но истинные все равно нужно выполнять, а значит это попытка зашифровать сообщение в случае когда и алгоритм шифрования и все ключи всем известны, что невозможно по определению.hellman
23.04.2015 00:31-4> все ключи всем известны
Ключ — это вход для программы. На известных входах можно просто запустить программу и не нужна никакая деобфускация. Но и информации о программе это даст ровно то, что f(x1) = y1.
Вот например мы обфусцируем программу f(x,y) = x + y если x != 31337 иначе f(x,y) = -1. Код получается такой:
1. считаем хитрый хэш от входа
2. если хэш = 1234567, расшифровать и выполнить код1 (ключ = вход)
3. иначе вывести x + y
Чем не обфускация в самом обычном понимании? Исходный код «запутан». Неизвестно, что программа делает, может там бэкдор вообще? Конечно, видно «подозрительное» место. Но может это тот самый «мусор» добавленный обфускатором? Может хэш нереально выполнить? Вот и получается, что криптография сводится к деобфускации.
vedenin1980
23.04.2015 00:45+5Чем не обфускация в самом обычном понимании? Исходный код «запутан».
Это лишь означает что мы шагнем на шаг -1 и определим как считается хитрый хэш. И так шагаем назад пока не придем к началу начал.
И тут два варианта:
1) ключ расшифровки каждый раз приходит откуда извне, по сути тоже самое что все программа работала на веб сервисе,
2) мы найдем изначальные ключи и сможем расшифровать весь алгоритм при неограниченном времени,
Проблема обфускация в следующем: как по вашему можно ли зашифровать текст так чтобы из двух дешифровщиков один всегда мог его расшифровать, а второй всегда не мог, при том что знания ключей, алгоритмов и возможности дешифровщиков абсолютно одинаковые? Правильно это невозможно, тогда почему вы верите в возможность такого шифрования, чтобы процессор всегда смог дешифровать, а человек не мог?hellman
23.04.2015 01:01-3Ещё раз — никуда шагать не надо, если вход известен. На известном входе можно просто запустить программу.
> ключ расшифровки каждый раз приходит откуда извне, по сути тоже самое что все программа работала на веб сервисе,
Вот и не то же самое. Веб-сервис — черный ящик, у вас нет шансов узнать о программе ничего кроме выводов на запрошенные входы. В случае моей программы код у вас есть. Но не взламывая хэша, нельзя определить, является ли код под хэшем мусором или нет
Следуя вашей логике, не получается деобфусцировать — значит программа — веб-сервис. А ведь это и есть цель обфускации — из программы сделали черный ящик.vedenin1980
23.04.2015 01:44+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 очень редкое значение это не выстрелит, если очень частое станет известно ещё во время тестирования. По большому счету автоматически такие трюки не сделать, а в ручном режиме больше сил будет потрачено на защиту, чем на её взлом.vedenin1980
23.04.2015 02:15+1Я правильно понимаю суть вашей защиты, мы парсим большой текстовый файл по хитрому алгоритму и если вдруг встречаем слово «глокакуздра», понимаем что оно равно нужному нам хешу, расшифровываем и запускаем секретный код?
Ну, во-первых, очень редко когда такая защита применима. Во-вторых, много бессмысленного ручного труда. В-третьих, такую защиту можно взломать просто как я описал выше, обнаруживая у пользователя переход в зашифрованный блок и расшифровку его с последующим фиксом в следующей версии. Ну, максимум это немного осложнит жизнь ворам.hellman
23.04.2015 02:55-1Я сразу написал, что такая обфускация непрактична. Это был контрпример к
> Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.
Топик о теоретических подходах к определению обфускации и теоретических пределах. Мой пример — «игрушечный» и к практике имеет мало отношения. Я хотел показать, что криптография по сути может являться обфускацией. Если заменить hash(x) == 123456 на x == 123456 то ведь будет очевидно, что делает код? А если взять что-то посередине, функцию попроще? Где граница между обфускацией и криптографией?
hellman
23.04.2015 02:17Ну вот — уже патчим код, посылаем юзера, айяйяй. Статично никак? Значит обфускация работает.
creker
23.04.2015 02:03+4Раз уж вы о теории, то сколько бы не написали таких вариантов кода для разных входов, все равно их все можно восстановить и вся программа будет как на ладони. Ваш пример это ровно тоже самое, что рядом с шифрованным блоком данных положить ключ. В итоге это вырождается в обычный обфусцированный код с кучей мусора, который нормальным специалистом так или иначе отсеивается.
А если мы учтем практичность, то количество комбинаций вход-код будет очень мало, поэтому все становится просто элементарным.
Именно поэтому единственные варианты, которые до сих пор применяют серьезные конторы это:
-ключ приходит по сети
-ключ находится в самом кристалле процессора
Но это все тоже самое security through obscurity и в конечно итоге все выплывает наружу.
grossws
23.04.2015 04:02Плюс вариант, когда важная часть алгоритма реализуется на внешнем устройстве и/или сервисе. Тогда приходим к черному ящику.
stepik777
22.04.2015 21:54-4>самая горячая сегодня
На хабре много о чём статей нет, значит всего этого не существует?
Нет. Наверное, это первая статья об обфускацию на хабре за 2015 год.
>область криптографии
Это не security through obscurity.
Нет. В криптрографии не занимаются security through obscurity.
Откуда же тогда столько статей на эту тему: scholar.google.com/scholar?start=0&q=Indistinguishability+Obfuscation&hl=en
Единственная работающая цель обфускации — давать головную боль тому, кто пытается разобраться с внутренностями программы.
У вас конечно же есть доказательство этого факта?
Все остальные цели или не достигаются, или некорректны.
Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.m1el
22.04.2015 22:05+3>У вас конечно же есть доказательство этого факта?
Например то, что нет схем DRM, которая имплементирована целиком в софте, которую еще не обошли.
matiouchkine
24.04.2015 08:20+1Не ради холивара, но просто для уточнения: невозможность наблюдения ни разу не аргумент в пользу невозможности события. (© Бозон Хиггса и Сэр Гравитон.)
Indemsys
22.04.2015 22:27Имея большой запас терпения, можно разобраться в любой обфусцированной программе и выписать алгоритм.
Если предположить, что гомоморфное шифрование (из предыдущей статьи автора) существует, то тогда алгоритмы шифруются элементарно.
Скажем алгоритм некоей нелинейной цифровой фильтации. Его секретом являются коэффициенты.
Наука пока не в курсе, как имея знания о сигналах на входе и выходе такого фильтра восстановить его структуру.
Вы беретесь дизассемблировать и узнать коэффициенты, а оказывается что они зашифрованы и вот в таком зашифрованном виде участвуют в вычислениях. Сами вычисления, естественно, уже не будут напоминать фильтр. Входной поток тоже получаете зашифрованный. Выходной проток, конечно, расшифровывается, но шифрование несимметричное.
И все, тупик. Ничего сделать невозможно.vedenin1980
22.04.2015 23:27+2Это не обфусцированние программы — мы получаем несколько потоков зашифрованных данных, делаем какие-то операции над ними, расшифровываем их и получаем не шифрованные данные, при чем тут шифрование кода программы?
По сути, раз входной поток кто-то где-то шифрует, то и секретные коэффициенты можно там же сразу наложить, то есть это лишь частный случай некоторого алгоритма на чужом сервисе к которому у нас нет доступа.Indemsys
23.04.2015 07:30Фильтрация идет на стороне клиента. Сервер не при чем.
Ну возьмем тогда сжатие для простоты понимания.
Эти алгоритмы тоже базируются на волшебных константах. На сервере сжимается на клиенте разжимается.
Но с помощью гомоморфного шифрования константы становятся недоступными.
И насколько я понял принцип гомоморфного шифрования алгоритм тоже меняется до неузнаваемости.
valerini Автор
23.04.2015 04:41-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). Функциональности — идентичны (но второй вариант гораздо проще и легче в реализации). Поэтому обфускация неразличимости второго варианта будет неотличима от обфускации неразличимости первого варианта и вы не сможете получить доступ к скрытой от вас функциональности, ее как будто в коде нет!m1el
23.04.2015 04:48+9>Шифр AES — это ни что иное как security by obscurity
Нет. Все знают алгоритм AES. Конечный пользователь знает секретный ключ. Единственное ограничение — третьи лица не знают секретный ключ.
«White box encryption» предлагает такое решение, при котором конечному пользователю дают софт, который может расшифровать AES, но при этом пользователь не может выдрать ключ из софта, потому что программа запутанная.
>Но вместо этого вы можете в начале программы задать права доступа (permissions), закодировать их прямо в код
Это называется «DRM» и эта идея неполноценна в корне.valerini Автор
23.04.2015 10:02-4> Нет. Все знают алгоритм AES. Конечный пользователь знает секретный ключ. Единственное ограничение — третьи лица не знают секретный ключ.
Security by obscurity в отношении к алгоритму — это не имение математического доказательства его устойчивости. AES такого не имеет, AES показывает устойчивость к статистическим тестам и существующим атакам, но никто не гарантирует, что хорошую атаку невозможно или очень сложно найти в принципе.
> Это называется «DRM» и эта идея неполноценна в корне.
DRM — это собирательный термин. Что именно вы считаете «неполноценным в корне»?
Теория доказывает, что приведенный выше мной пример полностью устойчив, т.е. получить доступ к скрытой функциональности, если вы используете обфускацию неразличимости, невозможно.
rocknrollnerd
23.04.2015 10:43+4> Security by obscurity в отношении к алгоритму — это не имение математического доказательства его устойчивости.
In security engineering, security through obscurity is the use of secrecy of the design or implementation to provide security.
А то, знаете, так можно далеко зайти. Для RSA тоже нет математического доказательства устойчивости (более того, для квантового компьютера есть доказательство неустойчивости). Существование односторонних функций как таковых вообще не доказано, и само по себе чистая эвристика — «что-то, что вроде работает и пока никто не взломал».
m1el
23.04.2015 10:54+6Мне надоело показывать, что каждое утверждение в комменте является некорректным, или бессмыссленным.
> это не имение математического доказательства его «устойчивости».
Ни один алгоритм шифрования не имеет доказательства его устойчивости. Есть алгоритмы, которые оприваются на NP-полные задачи. Есть другие алгоритмы, для которых еще не известны атаки. Ни для одних, ни для других доказательства «устойчивости» нет.
> Что именно вы считаете «неполноценным в корне»?
Попытки техническими средствами ограничить круг действий, которые может совершить пользователь с цифровым контентом.
Например: защита от копирования, «активация» софта, бессмысленное требование подключения к серверу или выключение фич.
> Теория доказывает, что приведенный выше мной пример полностью устойчив
Что это нам теория говорит об ограничении функциональности через «установку прав в начале программы»?
Это две разные функции, теория неприменима.
Например, функция P1(«Нарисуй круг»)=(рисует круг) и P2(«Нарисуй круг»)=(купите про версию фотошопа)
> получить доступ к скрытой функциональности, если вы используете обфускацию неразличимости, невозможно.
Что это нам теория говорит об «скрытой функциональности»? Ничего.rocknrollnerd
23.04.2015 18:37+4> Ни один алгоритм шифрования не имеет доказательства его устойчивости.
Одноразовый блокнот — имеет, прошу прощения за занудство)I'm fun at parties
amarao
22.04.2015 22:30Алгоритм нельзя украсть, так как он не является объектом авторского права.
valerini Автор
23.04.2015 04:50А как же патенты на алгоритмы? Причем патенты, которые, естественно не раскрывают все know-hows.
grossws
23.04.2015 05:44+4Мир не ограничен США
valerini Автор
23.04.2015 06:40«Авторские права на все виды программ для ЭВМ (в том числе на операционные системы и программные комплексы), которые могут быть выражены на любом языке и в любой форме, включая исходный текст и объектный код, охраняются так же, как авторские права на произведения литературы.» Статья 1261 Гражданского Кодекса РФ
«Правообладатель в течение срока действия исключительного права на программу для ЭВМ или на базу данных может по своему желанию зарегистрировать такую программу или такую базу данных в федеральном органе исполнительной власти по интеллектуальной собственности.» Статья 1262 Гражданского Кодекса РФgrossws
23.04.2015 14:48И причём здесь
патенты на алгоритмы
? Авторские и смежные права на произведение (в т. ч. программу для ЭВМ) не имеют никакого отношения к патентам (кроме того, что тоже обсуждаются в 4 части ГК РФ).
Ivan_83
22.04.2015 22:53-2Да да, надо прятать исходники и никому не показывать, ведь БГ так делал и теперь самый богатый чел на планете :)
В реальности интересных алгоритмов единицы, именно алгоритмов, а не конкретных технических решений.
Те вот RAR это алгоритм, а nginx решение. Последнее можно сделать и самому, просто нужно долго кодить и вникать. А первое долго думать.
Но почти всегда есть аналоги в свободном доступе, часто с исходниками.
На практике обфускацию видел во всяких навесных защитах на виндовый софт и вирусах.
vedenin1980
23.04.2015 00:08Тот новый вид обфускатора называется «Обфускация Неразличимости» («Indistinguishability Obfuscation» — «iO»), формально: если имеются две разные программы, но с абсолютно идентичными функциональностями, то обфускации этих двух программ будут неотличимы друг от друга.
На пальцах, у меня есть программа с алгоритмом «x = y + z — t» она неотличима от по функциональности от программы «x = y — t + z», ни от программы «x = z — t + y». C точки зрения, определения «Обфускация Неразличимости» банальная перестановка суммы слагаемых дает нам эту самую идеальную обфускацию! Как вы прекрасно понимаете конкуренту достаточно получить лишь один из алгоритмов с абсолютно идентичными функциональностями (и желательно близко по размеру и сложности оригинальному), чему такая «Обфускация Неразличимости» никак не помешает. Ну, какая мне разница что алгоритм полученный после реверс инженеринга будет не совсем таким же как тот что был изначальный, если его функциональность идентична оригиналу?
Другими словами, весь этот великий алгоритм это проста игра с определениями: «дадим новое определение Искусственного интеллекта. ИИ это программа способная сложить два числа. Ура, теперь в моем калькуляторе живет ИИ!»hellman
23.04.2015 01:23-1В статье [3] как раз доказывается, что «Indistinguishability Obfuscation» — лучшее, чего можно достичь.
«На пальцах»,
представьте произвольную идеальную обфускацию этого же алгоритма (x = y + z — t). Скормим этот (кем-то) обфусцированный код тому же идеальному обфускатору. Что же он выведет? А выведет он «банальную перестановку суммы» x = y + z — t, ведь исходные программы функционально одинаковы, значит и обфусцированные версии должны быть неотличимы. А это значит, что мы эффективно деобфусцировали исходную идеальную обфускацию и поэтому наш обфускатор (перестановка слагаемых) не хуже того идеального.
Вы можете сказать, что тогда хорошая обфускация невозможна — ведь предложенные вами «обфускации» подходят под определение, а значит это лучшее, чего можно достичь. Вот только мелочь: заверните ваш метод в эффективный алгоритм, да так, чтобы любой запутанный код, эквивалентный (x = y + z — t) он тоже развернул в x = y + z — t. Тогда действительно обфускация невозможна, ведь ваш алгоритм будет отличным деобфускатором.hellman
23.04.2015 01:41-1Опечатка, «Скормим этот (кем-то) обфусцированный код тому же идеальному обфускатору» — конечно же код скормим Indistinguishability обфускатору (который по предположению vedenin1980 может выводить просто перестановку слагаемых).
vedenin1980
23.04.2015 01:58если имеются две разные программы, но с абсолютно идентичными функциональностями, то обфускации этих двух программ будут неотличимы друг от друга.
Тут вы скорее всего где-то ошиблись в переводе, если функциональности всегда одинаковые это не две разные программы, а одна программа по разному переписанная, то есть если f(P1) всегда равна f(P2), где f — результат работы программы, то для нас программы по сути одинаковы.
Assimilator
23.04.2015 01:43-6Первая картинка, правая сторона на стринги очень смахивает. А я всё думал, почему эта тема меня внезапно заинтересовала?
#Весна
valerini Автор
23.04.2015 05:00Давайте я приведу пример, может быть это многое прояснит (он из одного из предыдущих комментариев):
Вы написали мощную программу — Photoshop Ultimate Edition, но есть пользователь, который хочет минимум функциональности от Photoshop, он хочет делать простейшую обработку своих фотографий, он не хочет платить 700$. Для него вы хотите выпустить Photoshop Light Edition за 300$. Чтобы это сделать сегодня, вам надо удалить всю ненужную функциональность и пересобрать весь проект (это первый вариант программы — P1). Если вы хотите сделать Photoshop Web Edition, вам опять же надо сделать то же самое. Но вместо этого вы можете в начале программы задать права доступа (permissions), закодировать их прямо в код и в самом коде вы будете проверять, если у пользователя есть необходимые права, ему будет доступна та или иная опция, если нет, то нет (это второй вариант программы — P2). Функциональности — идентичны, поэтому обфускация неразличимости второго варианта будет неотличима от обфускации неразличимости первого варианта, и вы не сможете получить доступ к скрытой от вас функциональности, ее как будто в коде нет! Второй вариант, однако, гораздо проще и легче в реализации и породит гораздо меньше ошибок.
acmer
23.04.2015 05:06Вот будет смешно, если iO делает NP из P задачи.
valerini Автор
23.04.2015 05:14+1О, знаете что iO делает… она делает вот какую прикольную штуку: называется Witness Encryption (WE). В WE вы шифруете свое сообщение для, например, SAT формулы и только тот может его расшифровать, кто знает выполняющий набор к этой формуле! (вместо SAT может быть любая другая NP полная задача). Но вам для шифрования необязательно знать выполняющий набор.
qw1
23.04.2015 12:39+1Мне непонятно, как это применить для обфускации того же фотошопа.
Секретный выполняющий набор присутствует на компьютере пользователя? Если нет, зачем он вообще нужен. Если да, какой же он секретный.valerini Автор
23.04.2015 21:06Я говорю о сведении задачи построения Witness Encryption к задачи построения indistinguishability Obfuscation. Это теоретический результат. Секретный выполняющий набор может нигде не хранится, его может не знать человек, который шифрует. Но человек, который хочет расшифровать сообщение должен найти этот выполняющий набор. Это просто очень на мой взгляд интересная своего рода связь теории сложности с криптографией.
qw1
23.04.2015 22:50+1Было бы неплохо объяснить это в статье, потому что в русском интернете вообще ничего нет.
AlexanderS
23.04.2015 13:55Хех. Буквально два часа назад усиленно искал обфускатор для HDL кода. Пришел к выводу что проще и надёжнее ngc'шником отдать =)
daeto
23.04.2015 16:04Не являюсь специалистом по теме, даже не владею всем понятийным аппаратом в полной мере, но всё же.
На первый взгляд, в данной статье указан в явном виде базовый примитив, который уже давно используется для определения безопасности криптографических примитивов. А именно, схема доказательства некоторых свойств стойкости алгоритмов с точки зрения неразличимости для некоторого advisor (советника) выхода алгоритма и случайного выхода, но расширенный также на выход другого алгоритма.
То, что этот базовый примитив можно выразить в терминах обфускации схем вычислений, это хорошо — удобная абстракция обычно подталкивает развитие отрасль знаний. В PDF часть этих результатов указана (как я понял, сведение других понятий к понятию неразличимой обфускации). Думаю, там ещё много всего интересного, но пока не успеваю подробно прочитать и понять.
Но можете объяснить, что ещё стоит понять из вашей статьи, на что обратить внимание? Думаю, многие на данном ресурсе будут ждать конкретной схемы обфускации, которая решит все их возможные проблемы. Можете ли вы для них подчеркнуть, есть ли готовые практические алгоритмы, а также какие теоретические задачи iO уже решила, которые были не решены раньше?valerini Автор
23.04.2015 22:12Да, вы очень хорошо сформулировали суть — это удобная абстракция. Схемы для этой обфускации еще более медленные, к сожалению, чем даже для 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 и которые пока не решены без нее.
robert_ayrapetyan
Очень громкое и ложное утверждение, мода на эту тему иссякла лет 10 назад, лишь гики с креклаба сегодня с улыбкой вспомнят про vmprotect и execryptor. Все ушло в веб, и доступа к «установочным файлам программ» у пользователей нет, по причине физического исчезновения этих самых «установочных файлов». На мобильных платформах та же самая картина — логика любого приложения\сервиса находится на сервере. Вы можете вспомнить про игры, но никто в здравом уме не будет их реверсить, чтобы понять какие-то тайны и секреты, а обфускация внесет непомерные тормоза в игровой процесс…
Newbilius
Безотносительно темы статьи, говорить о том, что «всё уходит в облака» несколько преждевременно. Фото, видео и аудио-редакторы всё-ещё не могут жить в облаке так, что бы их использование не причиняло боль. Google Docs и аналоги очень неплохи, пока речь не идёт о документах в несколько десятков страниц. 1С и прочие тоже вроде должны неплохо жить в облаке, но коробочные их версии всё-ещё почему то активно покупают. Научный софт, медицинский, производственный… Много чего в облако не ушло и не уйдёт в ближайшее время. Точнее, уже лет 5 слышу, как всё уходит в облака, но указанный мною софт всё-равно как туда уйти не может. Удивительно блин…
robert_ayrapetyan
Весь тот софт что вы перечислили использует очень малый процент пользователей. Модные нынче вещи, такие как общение (соц. сети, почта, мессенджеры), просмотр видео, поиск\покупки, не знаю что еще — у пользователя в руках лишь оббертка над апи.
Вот почему-то Скайп еще вспомнился с его знаменитым неломаемым протоколом (хотя вроде уже поломали). Мне кажется, что реверсить клиент Скайпа — это последнее что вы должны сделать, если захотите написать свой аналог.
Myosotis
А перечисленные вами «модные нынче вещи» и не интересны в плане исследования исходного кода (тут более интересно смотреть на содержимое отправляемых пакетов и на уязвимости сервера).
И что-то я не заметила физического исчезновения установочных файлов антивирусов, которые стоят далеко не у маленького процента пользователей.
robert_ayrapetyan
Ну что вы… Поверьте, все самые востребованные алгоритмы (подсовывание нужной рекламы и т.п.) — все в соц. сетях и почте. Про установочные файлы антивирусов… Это о чем вообще?
Myosotis
Так это о вашей цитате
robert_ayrapetyan
Я понял, но это был сарказм вообще-то и я надеялся что кто-то все же распишет что именно собирается обфусцировать в установочных файлах (любых программ) и что они вообще делают в статье. Вы, например, понимаете что такое «установочные фалы» и какова их роль?
qw1
Установочные файлы очень важно обфусцировать, иначе злые хакеры взломают и сделают чекбоксы «мэйлру агент» и «яндекс-браузер» выключенными по умолчанию.
stepik777
Эта статья о науке криптографии, а не о каких-то программах для обфускации экзешников. Облака и что куда ушло здесь совершенно не при чём.
robert_ayrapetyan
Смысл понятия «Обфускатор Неразличимости», вокруг которого построена вся ваша статья, совершенно не раскрыт. Кроме громких заявлений, что это «теория всего», все криптографы
посрамленыпотрясены и т.п. в статье ничего нет. Спасибо за авторитетные источники в конце, но как-то не хочется тратить время на прочтение 44 страниц текста, изобилующего формулами.stepik777
Это не моя статья и я согласен с вами на счёт того что суть не раскрыта.
robert_ayrapetyan
Простите, проглядел момент с авторством.
Вот вы говорите что статья «не о каких-то программах для обфускации экзешников», но ведь статья называется «Обфускация программ» и в самом начале автор акцентирует на этом внимание. Сразу показалось подозрительным — «Давая пользователям доступ к установочным файлам программ...», я подумал, что автор просто неточно выразился, но теперь я понимаю что, скорее всего, дело в полном отрыве от реальности и непонимании предмета защиты.
Если даже допустить, что существуют методы, превращающие любой алгоритм в «черный ящик», то как вся эта теория применима на практике?
Вот, например, одна статья из, так сказать, «раннего», где я описываю метод использования чужого кода без каких либо попыток вникнуть в его суть. Как «Обфускация Неразличимости» поможет уберечься от такого «лома»?
Как «Обфускация Неразличимости» будет влиять на производительность?
Кроме того, не кажется ли вам, что «Обфускация Неразличимости» конфликтует с фундаментальным принципом, на котором зиждется современная криптография — принципом Керкгоффса?
valerini Автор
Обфускацию черного ящика построить нельзя. Обфускация Неразличимости это лучшее, что теоретически возможно воплотить в жизнь на сегодняшний день. Кроме того, из существования ее вытекает существование многих других важных криптографических примитивов. Что бы вы хотели еще о ней узнать? Как она строится? На это не хватит страницы текста и без формул тут не обойтись. Как она строится не так важно, потому что существующая конструкция лишь кандидат, она очень неэффективна. Если вас интересует только практические, а не теоретические аспекты, то надо подождать появления лучших схем прежде чем разбираться.
robert_ayrapetyan
К теории как раз вопросов нет, авторитетные лица занимаются гомоморфными методами шифрования не один десяток лет. Вопрос именно к прикладным аспектам, а именно попыткам применить данный метод ко всему чему можно и нельзя, без оглядки на то, имеет ли такое приложение какой-либо практический смысл. Даже если отбросить существующие проблемы в производительности и размерах, представить что их нет, зачем тащить это в код, исполняемый на машине пользователя (ведь именно об этом ваша статья)?
CrashLogger
Применительно к вебу, обфускация актуальна для Javascript и платных PHP библиотек. Ну и для вредоносного ПО конечно тоже.
KvanTTT
Для JavaScript актуальна разве что минификация кода для уменьшения его размера, что, отчасти, является и обфускацией тоже.
domix32
Mara smiles upon you!