Encontré el término "oráculo criptográfico" y, a pesar de un poco de googlear, no pude encontrar una definición clara y concisa. ¿Qué es un oráculo criptográfico y qué hace? ¿Alguien puede dar un ejemplo?
Un oracle es una persona que conoce el número de teléfono celular personal de un dios. Esto le permite a él (o ella) obtener cierta información que generalmente se considera fuera del alcance de los simples mortales, como los atisbos del futuro. En criptografía, es lo mismo, excepto que no hay ninguna deidad involucrada: un oráculo es cualquier sistema que puede proporcionar información adicional sobre un sistema, que de lo contrario no estaría disponible.
Por ejemplo, considere el cifrado asimétrico con RSA . El enlace estándar a los estados indica cómo se debe cifrar una parte de los datos con una clave pública. En particular, el cifrado comienza con una operación de relleno , en la cual el dato se expande primero agregando un encabezado, de modo que la longitud de los datos rellenados coincida con la longitud de la clave pública RSA. El encabezado debe comenzar con los dos bytes 0x00 0x02 , seguidos de al menos ocho bytes aleatorios distintos de cero, y luego otro 0x00 . Una vez que se han rellenado los datos, es hora de aplicar la operación matemática que está en el núcleo de la operación RSA (exponenciación modular). Los detalles del relleno son importantes para la seguridad.
El resultado del cifrado es un módulo de enteros, el módulo RSA , un entero grande que forma parte de la clave pública. Para una clave RSA de 1024 bits, el módulo n es un valor entero mayor que 21023 , pero más pequeño que 2 1024 . Un fragmento de datos correctamente cifrado, con RSA, produce un valor entero entre 1 y n-1 . Sin embargo, el relleno implica alguna estructura , como se muestra arriba. La parte de descifrado DEBE encontrar, después del descifrado, un encabezado PKCS # 1 correctamente formado, que comience con el 0x00 0x02 bytes, seguido de al menos ocho bytes distintos de cero, y debe haber un 0x00 que marque el final del encabezado . Por lo tanto, no todos los enteros entre 1 y n-1 son mensajes encriptados con RSA válidos (menos de 1 cada 65000 tales enteros producirían un relleno apropiado al descifrar).
Saber si un número entero dado n proporcionaría, al descifrar, una estructura de relleno válida, se supone que es inviable para quien no conoce la clave privada. El propietario de la clave privada (la deidad) obtiene esa información, y mucho más: si el descifrado funciona, el propietario de la clave privada recibe el mensaje, que es el punto de descifrado. Supongamos que hay es una entidad, en algún lugar, que puede decirle si un módulo entero dado n es un dato válido encriptado con RSA; esa entidad no le daría el resultado de descifrado completo, solo le diría si el descifrado funcionaría o no. Esa es una información de un bit, una visión reducida de lo que obtendría la deidad. La entidad es tu oráculo: devuelve partes de la información que normalmente está disponible solo para el propietario de la clave privada.
Resulta que que, dado el acceso a tal oráculo, es posible reconstruir la clave privada, enviando números enteros especialmente diseñados, modulo n (toma aproximadamente un millón de tales valores y bastante matemática, pero se puede hacer). También resulta que la mayoría de las implementaciones de SSL / TLS de esa época (que fue en 1999) actuaron involuntariamente como oráculos: si usted envió, como cliente, un mensaje ClientKeyExchange no cifrado por RSA, el servidor respondía con un mensaje de error específico ("duh, su mensaje ClientKeyExchange apesta"), mientras que si el descifrado funcionaba, el servidor seguía con el protocolo, usando sea cual sea el valor que haya descifrado (generalmente desconocido para el cliente si el cliente envió un valor aleatorio, por lo que el protocolo falló más tarde, pero el cliente podría ver la diferencia entre un relleno válido y otro no válido). Por lo tanto, con tal implementación, un atacante podría (después de aproximadamente un millón de conexiones fallidas) reconstruir la clave privada del servidor, lo que generalmente se considera algo malo.
Eso es lo que son los oráculos: una descripción matemática de una fuga de datos, que se utilizará en las pruebas de seguridad. En el caso de RSA, esto demuestra que saber si un valor tiene un relleno correcto o no es de alguna manera equivalente a aprender la clave privada (si conoce la clave privada, puede intentar la desencriptación y ver el relleno por sí mismo; el ataque de Bleichenbacher muestra que también funciona al revés).
Un oráculo es algo que puede inmediatamente ( O(1) ) darte la respuesta a algún problema, generalmente un problema imposible o imposible. Por ejemplo, un "Halting-problem Oracle" podría decirle de inmediato si un determinado programa en una determinada entrada se detiene o no, aunque el problema de la detención sea incompatible para nosotros, simples mortales. Sin embargo, a veces podemos probar algunas propiedades útiles pretendiendo que existen ciertos oráculos.
En los documentos criptográficos, por ejemplo, los oráculos se usan con más frecuencia para mostrar que, incluso si nuestros atacantes tuvieran acceso a algún oráculo aparentemente imposible, todavía no lo harían Tienes alguna ventaja (significativa) para romper nuestra seguridad. Por ejemplo, una propiedad importante de los algoritmos de cifrado (llamada resistencia a ataques conocidos de texto simple ) es que si un atacante recibe un mensaje cifrado con su clave m' y quiere saber el mensaje original m (o descifre su clave) , luego les da otro mensaje n y su cifrado con su clave n' no debería ayudarles a hacerlo de ninguna manera.
Llevando esto al extremo ( ataque de texto simple elegido ) : dale un atacante un oráculo que puede cifrar o descifrar cualquier mensaje con su clave excepto para m y m' . Incluso en estas condiciones extremas, quisiéramos demostrar para nuestro cifrado que el atacante con el oráculo no tendrá ninguna ventaja en encontrar m (o su clave) que el atacante sin el oráculo. Esto significaría que nuestro cifrado está a salvo de los ataques de texto sin formato elegidos.
[Editar]
Aquí hay otro ejemplo práctico. En la pregunta ¿Podría un programa alguna vez saber si otro programa juega al ajedrez? , demostramos que no existe tal programa asumiendo primero que es un oráculo de detección de ajedrez, luego mostrar su existencia conduce a una imposibilidad lógica.
Los oráculos criptográficos son un método de entrada / salida de caja negra.
Responderá a cualquier entrada con una respuesta pseudoaleatoria pero siempre dará la misma salida para una entrada específica.
Generalmente se usan para funciones hash donde la aleatoriedad es importante para una mayor seguridad.
Obviamente, todavía habrá problemas de seguridad, ya que es solo una función matemática que está devolviendo números aparentemente pseudoaleatorios, pero obviamente son más fuertes que algunos de sus equivalentes menos aleatorios.
Aquí hay un documento sólido sobre ellos y su diseño: enlace
Apareciendo en muchas formas, a menudo con un aire de confusión, el oráculo es esencialmente una capacidad imaginada que puede atribuirse al lado de la seguridad o al atacante, y se utiliza como una herramienta útil para evaluar la seguridad, si usted es cuidado de distinguir entre el buen oráculo y el "iffy" oráculo.
Vea un video de 5 minutos en The Crypto Academy
]
Lea otras preguntas en las etiquetas cryptography