Обфускация черного ящика

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

невозможность

Незапутываемые программы

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

В общих чертах они начинают с разработки специальной пары программ, которые невозможно запутать вместе. Для некоторых случайно выбранных строк $\alpha ,\beta$ фиксированной, заранее определенной длины $k$, определите одну программу как программу, которая вычисляет

$C_{\alpha ,\beta }(x):={\begin{cases}\beta &{\text{if }}x=\alpha \\0&{\text{otherwise}}\end{cases}}$

а другая программа - к той, которая вычисляет

$D_{\alpha ,\beta }(X):={\begin{cases}1&{\text{if }}X(\alpha )=\beta {\text{ and }}X{\text{ runs in time}}\leq {\text{poly}}(k)\\0&{\text{otherwise}}\end{cases}}.$

(Здесь, $D_{\alpha ,\beta }$ интерпретирует вводимые данные как код машины Тьюринга . Второе условие в определении $D_{\alpha ,\beta }$ состоит в том, чтобы функция не была невычислимой .)

Если эффективный злоумышленник имеет доступ только к «черному ящику», Барак и др. утверждается, то у злоумышленника есть только экспоненциально малый шанс угадать пароль. $\alpha$, и поэтому не может отличить пару программ от пары, где $C_{\alpha ,\beta }$ заменяется какой-то программой $Z$ который всегда выводит «0». Однако, если злоумышленник имеет доступ к каким-либо запутанным реализациям $C'_{\alpha ,\beta },D'_{\alpha ,\beta }$ из $C_{\alpha ,\beta },D_{\alpha ,\beta }$, то злоумышленник найдет $D'_{\alpha ,\beta }(C'_{\alpha ,\beta })=1$ с вероятностью 1, тогда как злоумышленник всегда найдет $D'_{\alpha ,\beta }(Z)=0$ пока не $\beta =0$ (что должно произойти с ничтожной вероятностью). Это значит, что злоумышленник всегда сможет отличить пару $(C'_{\alpha ,\beta },D'_{\alpha ,\beta })$ из пары $(Z,D'_{\alpha ,\beta })$ с доступом к запутанному коду, но не с доступом к «черному ящику». Поскольку ни один обфускатор не может предотвратить эту атаку, Барак и др. пришли к выводу, что не существует обфускатора «черного ящика» для пар программ.

В заключение аргумента Barak et al. определим третью программу для реализации функциональности двух предыдущих:

$F_{\alpha ,\beta }(b,x):={\begin{cases}C_{\alpha ,\beta }(x)&{\text{if }}b=0\\D_{\alpha ,\beta }(x)&{\text{if }}b=1\\\end{cases}}.$

Поскольку эквивалентно эффективные реализации $C_{\alpha ,\beta },D_{\alpha ,\beta }$ можно восстановить с одного из $F_{\alpha ,\beta }$ путем жесткого определения значения $b$, Барак и др. сделать вывод, что $F_{\alpha ,\beta }$ также не могут быть запутаны, что и завершает их аргументацию.

Невозможные варианты обфускации черного ящика и другие типы незапутываемых программ.

В своей статье Барак и др. также докажите следующее (при условии соответствующих криптографических предположений ):

• Есть незапутанные схемы .
• Не существует приблизительного обфускатора черного ящика.
• Существуют незапутанные, безопасные, вероятностные криптосистемы с закрытым ключом .
• Существуют незапутанные, безопасные и детерминированные схемы цифровой подписи .
• Существуют незапутанные, безопасные и детерминированные схемы аутентификации сообщений .
• Существуют необфускабельные, безопасные псевдослучайные функции .
• Для многих протоколов, которые безопасны в модели случайного оракула , протокол становится небезопасным, если случайный оракул заменяется искусственной криптографической хэш-функцией ; в частности, схемы Фиата-Шамира . могут быть атакованы
• есть необфускируемые схемы В TC0 (то есть пороговые схемы постоянной глубины).
• Существуют необфусцируемые алгоритмы выборки (фактически их невозможно запутать приблизительно).
• Не существует безопасной схемы нанесения водяных знаков в программном обеспечении .

Более слабые варианты

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

По состоянию на 2020 год , кандидатская реализация запутывания неотличимости находится в стадии изучения. В 2013 году Бойл и др. исследовал несколько возможных реализаций запутывания извлекаемости.