Modelo de oráculo aleatorio

El modelo de oráculo aleatorio es un heurística usada para proveer argumentos de seguridad para protocolos criptográficos modelizando ciertos algoritmos, normalmente funciones hash criptográficas, como oráculos (teóricamente una caja negra) que responde a cada consulta con una respuesta realmente aleatoria elegida uniformemente en su rango de salida (funciones aleatorias perfectas). A este tipo de oráculos se les llama oráculos aleatorios.

[1] El modelo de oráculo aleatorio fue introducido por Bellare and Rogaway.[2] Fue diseñado para mostrar la dificultad de romper algoritmos criptográficos modelizando ciertas partes del cifrador (normalmente la función hash) como funciones aleatorias.

Por ejemplo los esquemas de relleno de RSA OAEP y PSS, los cuales son estandards del cifrado y la firma digital, encuentran su justificación formal en el modelo de oráculo aleatorio.

Crítica a su validez[3]

Recientes estudios han mostrado que los protocolos probados seguros en el modelo de oráculo aleatorio no siempre lo son cuando los oráculos aleatorios son instanciados con funciones computables eficientemente.[4] Por ejemplo Canetti, Goldreich y Halevi[5] probaron que existe un esquema de firma digital que es segura en el modelo de oráculo aleatorio pero inseguro cuando la función aleatoria es reemplazada con una función computable en tiempo polinomial. Ha habido otros estudios que han llegado a conclusiones similares[6][7][8][9]

El significado exacto de estos resultados es un punto de controversia en la comunidad criptográfica, algunos creen que sus construcciones artificiales son evidencias de la fortaleza del modelo de oráculo aleatorio, otros creen que la existencia de tales esquemas es indicación suficiente para que el modelo sea abandonado. Entre otras cosas algunos detractores[10] aseguran que los oráculos aleatorios nunca pueden ser realizados en la práctica desde el momento en que estas funciones son privadas mientras que las funciones hash son objetos públicos.

En cualquier caso, usar el modelo de oráculo aleatorio para 'probar' la seguridad de un protocolo criptográfico reduce la fortaleza de la prueba ya que asume como cierto que:

  • Los adversarios no explotan ciertas propiedades de la función hash escogida.
  • Las funciones hash se comportan como funciones aleatorias.
  • Todos los valores aleatorios son efectivamente aleatorios.

y estas premisas puede que no sean ciertas en el mundo real.

Referencias
  1. Alexander W. Dent,"Adapting the weaknesses of the Random Oracle model to the Generic Group model".Royal Holloway, University of London, Egham Hill, Egham, Surrey. United Kingdom. 2002
  2. M. Bellare and P. Rogaway. "Random Oracles are Practical: A Paradigm for Designing Effecient Protocols" Proceedings of the First ACM Conference on Computer and Communications Security, 1993.
  3. Gagne, Martin,"A study of the random oracle model".Ph.D., University of California, Davis, 2008
  4. Alexander W. Dent,"Adapting the weaknesses of the Random Oracle model to the Generic Group model".Royal Holloway, University of London, Egham Hill, Egham, Surrey. United Kingdom. 2002
  5. R. Canetti, O. Goldreich and S. Halevi "The random oracle methodoly revisited" 1998
  6. S. Goldwasser and Y. Taumann. On the (In)security of the Fiat-Shamir Paradigm. In Proceedings of the 44th IEEE Symposium on Foundation of Computer Science, pp. 102-115, 2003.
  7. M. Bellare, A. Boldyreva and A. Palacio. An Un-Instantiable Random-Oracle-Model Scheme for a Hybrid- Encryption Problem, In Advances in Cryptology – EUROCRYPT 2004, LNCS 3027, pp. 171-188, 2004
  8. R. Canetti, O. Goldreich and S. Halevi. On the Random-Oracle Methodology as Applied to Length-Restricted Signature Schemes. In Proceedings of the First Theory of Cryptography Conference, LNCS 2951, pp. 40-57,2004
  9. U. Maurer, R. Renner and C. Holenstein. Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. In Theory of Cryptography – TCC 2004, LNCS 2951, pp. 21-39, 2004
  10. S. Contini et all, "A Critical Look at Cryptographic Hash Function Literature"
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.