Ofuscación de caja negra

Propuesta de primitiva criptográfica

En criptografía , la ofuscación de caja negra fue una primitiva criptográfica propuesta que permitiría ofuscar un programa informático de tal manera que fuera imposible determinar nada sobre él excepto su comportamiento de entrada y salida. ^{[1] Se ha} demostrado que la ofuscación de caja negra es imposible, incluso en principio. ^[2]

Imposibilidad

Los programas inofuscables

Barak et al. construyeron una familia de programas no ofuscables, para los cuales un atacante eficiente siempre puede aprender más de cualquier código ofuscado que del acceso a caja negra. ^{[2] [3]}

En términos generales, comienzan diseñando un par especial de programas que no se pueden ofuscar juntos. Para algunas cadenas seleccionadas al azar de una longitud fija predeterminada , definen un programa como aquel que calcula ${\displaystyle \alpha ,\beta }$ ${\displaystyle k}$

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

y el otro programa a uno que calcula

${\displaystyle 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}}.}$

(Aquí, interpreta su entrada como el código de una máquina de Turing . La segunda condición en la definición de es evitar que la función sea incomputable ). ${\displaystyle D_{\alpha ,\beta }}$ ${\displaystyle D_{\alpha ,\beta }}$

Si un atacante eficiente solo tiene acceso a la caja negra, argumentaron Barak et al., entonces el atacante solo tiene una probabilidad exponencialmente pequeña de adivinar la contraseña , y por lo tanto no puede distinguir el par de programas de un par donde se reemplaza por algún programa que siempre genera "0". Sin embargo, si el atacante tiene acceso a cualquier implementación ofuscada de , entonces el atacante encontrará con una probabilidad de 1, mientras que el atacante siempre encontrará a menos que (lo que debería suceder con una probabilidad insignificante). Esto significa que el atacante siempre puede distinguir el par del par con acceso al código ofuscado, pero no el acceso a la caja negra. Dado que ningún ofuscador puede prevenir este ataque, Barak et al. concluyen que no existe ningún ofuscador de caja negra para pares de programas. ^{[2] [3]} ${\displaystyle \alpha }$ ${\displaystyle C_{\alpha ,\beta }}$ ${\displaystyle Z}$ ${\displaystyle C'_{\alpha ,\beta },D'_{\alpha ,\beta }}$ ${\displaystyle C_{\alpha ,\beta },D_{\alpha ,\beta }}$ ${\displaystyle D'_{\alpha ,\beta }(C'_{\alpha ,\beta })=1}$ ${\displaystyle D'_{\alpha ,\beta }(Z)=0}$ ${\displaystyle \beta =0}$ ${\displaystyle (C'_{\alpha ,\beta },D'_{\alpha ,\beta })}$ ${\displaystyle (Z,D'_{\alpha ,\beta })}$

Para concluir el argumento, Barak et al. definen un tercer programa para implementar la funcionalidad de los dos anteriores:

${\displaystyle 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}}.}$

Dado que se pueden recuperar implementaciones equivalentemente eficientes de una de conectando de forma fija el valor de , Barak et al. concluyen que tampoco se puede ofuscar, lo que concluye su argumento. ^[2] ${\displaystyle C_{\alpha ,\beta },D_{\alpha ,\beta }}$ ${\displaystyle F_{\alpha ,\beta }}$ ${\displaystyle b}$ ${\displaystyle F_{\alpha ,\beta }}$

Variantes imposibles de ofuscación de caja negra y otros tipos de programas no ofuscables

En su artículo, Barak et al. también prueban lo siguiente (condicionado a suposiciones criptográficas apropiadas ): ^[2]

• Hay circuitos no ofuscables .
• No existe ningún ofuscador aproximado de caja negra .
• Existen criptosistemas de clave privada probabilísticos, seguros y no ofuscables .
• Existen esquemas de firma digital deterministas, seguros y no ofuscables.
• Existen esquemas de autenticación de mensajes deterministas, seguros y no ofuscables.
• Existen funciones pseudoaleatorias seguras y no ofuscables .
• Para muchos protocolos que son seguros en el modelo de oráculo aleatorio , el protocolo se vuelve inseguro si el oráculo aleatorio se reemplaza con una función hash criptográfica artificial ; en particular, los esquemas Fiat-Shamir pueden ser atacados.
• Hay circuitos no ofuscables en TC0 (es decir, circuitos de umbral de profundidad constante).
• Existen algoritmos de muestreo que no se pueden ofuscar (de hecho, no se pueden ofuscar de manera aproximada).
• No existe ningún esquema de marca de agua de software seguro .

Variantes más débiles

En su artículo original que explora la ofuscación de caja negra, Barak et al. definieron dos nociones más débiles de ofuscación criptográfica que no descartaron: ofuscación de indistinguibilidad y ofuscación de extractabilidad (a la que llamaron "ofuscación de entradas diferentes"). De manera informal, un ofuscador de indistinguibilidad debería convertir programas de entrada con la misma funcionalidad en programas de salida de tal manera que las salidas no puedan ser relacionadas eficientemente con las entradas por un atacante limitado, y un ofuscador de extractabilidad debería ser un ofuscador de tal manera que si el atacante eficiente pudiera relacionar las salidas con las entradas para dos programas cualesquiera, entonces el atacante también podría producir una entrada de tal manera que los dos programas que se están ofuscando produzcan salidas diferentes. (Tenga en cuenta que un ofuscador de extractabilidad es necesariamente un ofuscador de indistinguibilidad). ^{[2] [4]}

A partir de 2020 , se está investigando ^[update]una implementación candidata de ofuscación de indistinguibilidad . ^[5] En 2013, Boyle et al. exploraron varias implementaciones candidatas de ofuscación de extractabilidad. ^[4]

Referencias

1. Goldwasser, Shafi; Rothblum, Guy N. (1 de julio de 2014). "Sobre la mejor ofuscación posible" (PDF) . Revista de criptología . 27 (3): 480–505. doi :10.1007/s00145-013-9151-z. hdl : 1721.1/129413 . ISSN  1432-1378. S2CID  1186014.
2. Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke (3 de mayo de 2012). "Sobre la (im)posibilidad de ofuscar programas" (PDF) . Revista de la ACM . 59 (2): 6:1–6:48. doi :10.1145/2160158.2160159. ISSN  0004-5411. S2CID  2409597.
3. "Ofuscación criptográfica y software 'imposible de hackear'". Algunas reflexiones sobre ingeniería criptográfica . 2014-02-21 . Consultado el 2021-03-14 .
4. Boyle, Elette; Chung, Kai-Min; Pass, Rafael (2013). "Sobre la ofuscación de la extractabilidad (también conocida como entradas diferentes)". Archivo de ePrints de criptología .
5. Klarreich, Erica (10 de noviembre de 2020). "Los científicos informáticos logran la 'joya de la corona' de la criptografía". Revista Quanta . Consultado el 10 de noviembre de 2020 .