Network Working Group D. Eastlake, 3rd Request For Comments: 1750 DEC Categoría: Informativa S. Crocker CyberCash J. Schiller MIT Diciembre 1994 Traducción al Castellano: Octubre 2004 Rubén Afonso Francos rafrancos@terra.es Recomendaciones sobre la aleatoriedad en el ámbito de la seguridad Estatus de este memorándum Este memorándum proporciona información para la comunidad Internet, no especifica ningún tipo de estándar de Internet y su distribución es ilimitada. Resumen Los sistemas de seguridad actuales se basan en algoritmos criptográficos, cada vez más robustos, que resisten cualquier intento de análisis mediante búsqueda de patrones. Sin embargo, la seguridad que proporcionan depende de la capacidad para generar valores secretos como contraseñas, claves criptográficas y similares. El uso de métodos pseudo-aleatorios para obtener todos estos elementos puede derivar en pseudo-seguridad. A un atacante experimentado que se enfrente a estos sistemas le puede resultar más fácil reproducir las condiciones en las que se obtuvieron los valores secretos, buscando en un reducido conjunto de posibilidades, que encontrar dichos valores dentro del espacio de búsqueda total. Elegir valores aleatorios para defenderse ante un atacante decidido y con recursos suficientes es sorprendentemente difícil. Este documento señala muchos errores cometidos al obtener dichos valores utilizando técnicas tradicionales de generación de números pseudo-aleatorios, y recomienda el uso de métodos realmente aleatorios basados en hardware, mostrando cómo los componentes existentes en muchos equipos actuales pueden ser utilizados para este propósito. También se dan sugerencias para solventar el problema cuando no se puede recurrir a soluciones basadas en hardware, y ejemplos del tamaño que deben tener los valores aleatorios para algunas aplicaciones en concreto. Leech [Pág. 1] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 Agradecimientos Las siguientes personas (en orden alfabético) proporcionaron comentarios que fueron añadidos a este documento: David M. Balenson (TIS) Don Coppersmith (IBM) Don T. Davis (consultant) Carl Ellison (Stratus) Marc Horowitz (MIT) Christian Huitema (INRIA) Charlie Kaufman (IRIS) Steve Kent (BBN) Hal Murray (DEC) Neil Haller (Bellcore) Richard Pitkin (DEC) Tim Redmond (TIS) Doug Tygar (CMU) Tabla de Contenidos 1. Introducción........................................... 3 2. Requisitos............................................. 4 3. Secuencias pseudo-aleatorias tradicionales............. 5 4. Impredecibilidad....................................... 7 4.1 Inconvenientes de los relojes y número de serie....... 8 4.2 Intervalos de tiempo y contenido de eventos externos.. 9 4.3 La falacia de las operaciones complicadas............. 9 4.4 La falacia de la selección dentro de un conjunto grande de datos...................................... 10 5. El hardware, una fuente de aleatoriedad............... 10 5.1 Cantidad necesitada.................................. 11 5.2 Sensibilidad al sesgo................................ 11 5.2.1 Eliminación de sesgos utilizando la paridad de flujo................................... 11 5.2.2 Eliminación de sesgos utilizando mapeados de transición............................. 13 5.2.3 Eliminación de sesgos utilizando la FFT............ 14 5.2.4 Eliminación de sesgos utilizando la compresión..... 14 5.3 El hardware existente puede ser utilizado como fuente de aleatoriedad............................... 15 5.3.1 Utilizando la entrada de vídeo/sonido existente.... 15 5.3.2 Utilizando las unidades de disco disponibles....... 15 6. Estrategias recomendadas si se carece de hardware al que recurrir....................................... 16 6.1 Funciones de mezcla.................................. 16 6.1.1 Una función de mezcla trivial...................... 16 6.1.2 Funciones de mezcla más robustas................... 17 Leech [Pág. 2] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 6.1.3 Diffie-Hellman como una función de mezcla.......... 19 6.1.4 Utilizando una función de mezcla para aumentar los bits aleatorios....................... 19 6.1.5 Otros factores a tener en cuenta al elegir una función de mezcla.................................. 19 6.2 Fuentes de aleatoriedad no basadas en hardware....... 20 6.3 Secuencias criptográficas robustas................... 21 6.3.1 Secuencias tradicionales robustas.................. 22 6.3.2 El generador de secuencias Blum Blum Shub.......... 23 7. Estándares para la creación de claves................. 24 7.1 Recomendaciones del Departamento de Defensa Estadounidense para la creación de contraseñas........24 7.2 Creación de claves mediante X9.17.................... 25 8. Ejemplos del grado de aleatoriedad recomendado........ 25 8.1 Creación de contraseñas.............................. 25 8.2 Una clave criptográfica de alta seguridad............ 26 8.2.1 Esfuerzo por comprobación de clave................. 27 8.2.2 Ataques por encuentro a medio camino............... 27 8.2.3 Otras consideraciones.............................. 28 9. Conclusiones.......................................... 29 10. Consideraciones de seguridad......................... 29 Referencias.............................................. 29 Direcciones de los Autores............................... 31 1. Introducción El uso de software criptográfico se está extendiéndo y los sistemas como Kerberos, PEM, PGP, etc, están madurando y convirtiéndose en elementos habituales de las redes [PEM]. Estos sistemas proporcionan bastante protección contra técnicas como el "snooping" y el "spoofing". Sin embargo, existe un posible fallo. La creación de números secretos e impredecibles (es decir, aleatorios) forma parte del corazón de todos los sistemas criptográficos. En la actualidad, el diseño de aplicaciones criptográficas se encuentra con la falta de medios fácilmente accesibles para generar dichos números. Para el desarrollador de éstas que quiere crear una clave o un método de creación de claves que funcione en una gama amplia de hardware, la única estrategia segura es forzar al sistema local a que proporcione un conjunto de rutinas destinadas a generar números aleatorios. Esta solución es, como mínimo, cutre, propensa a errores y desagradable. Es importante recordar que lo que se necesitan son datos que tengan una probabilidad muy baja de ser adivinados o determinados por un adversario. Esto no se cumple si se utilizan datos pseudo-aleatorios que sólo satisfacen las pruebas estadísticas tradicionales de aleatoriedad o que están basados en fuentes de rango limitado, como Leech [Pág. 3] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 los relojes. Estos valores muchas veces son descubiertos por un adversario después de haber rastreado un espacio de búsqueda vergonzosamente pequeño. Este documento de carácter informativo sugiere técnicas para producir valores aleatorios resistentes a un ataque semejante y recomienda que los sistemas futuros sean capaces de obtener números aleatorios mediante hardware especializado o proporcionen acceso al hardware existente que pueda utilizarse para tal propósito. También se sugieren alternativas en el caso de que no se pueda disponer de dicho hardware. Finalmente, se dan algunas estimaciones del número de bits aleatorios necesarios para algunas aplicaciones en concreto. 2. Requisitos Probablemente la contraseña del usuario, normalmente una simple cadena de caracteres, sea la aplicación más común donde se necesita aleatoriedad. Obviamente, una contraseña que se puede adivinar no proporciona seguridad alguna. (En las contraseñas reutilizables es deseable que el usuario sea capaz de recordarla. Esto puede llevar a que se utilicen cadenas de caracteres pronunciables o frases con palabras comunes. Pero esto sólo afecta al formato de la información contenida en la contraseña, no al hecho de que la contraseña sea muy difícil de adivinar). Otros requisitos provienen del mundo de la criptografía. Las técnicas criptográficas pueden utilizarse para proporcionar muchos servicios, como confidencialidad y autenticación. Éstos se basan en elementos, tradicionalmente llamados "claves", que son desconocidos e imposibles de adivinar para un adversario. En algunos casos, como en el cifrado simétrico con claves de un solo uso [CRYPTO*], o el Estándar de Cifrado de Datos de los Estados Unidos [DES], todas las partes que desean comunicarse de forma confidencial y/o identificarse deben conocer la misma clave secreta. Otras veces, utilizando lo que se conoce como criptografía asimétrica o de "clave pública", se usan parejas de claves. Una de las claves es privada y debe ser mantenida en secreto, la otra puede ser de dominio público. Intentar averiguar la clave privada a partir de la pública es computacionalmente inabordable [ASYMMETRIC, CRYPTO*]. La cantidad y frecuencia de los valores aleatorios requeridos varían en gran medida dependiendo del sistema criptográfico en cuestión. Utilizando RSA [CRYPTO*], éstos sólo se necesitan cuando se construye el par de claves, pudiendo después firmar un número indeterminado de mensajes. El Algoritmo de Firma Digital que ha sido propuesto por el Instituto Americano de Estándares y Tecnología (NIST), requiere números aleatorios en cada firma. Y cifrar con una clave de un solo Leech [Pág. 4] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 uso, en principio la técnica de cifrado más fuerte posible, necesita un volumen de aleatoriedad igual al total de mensajes que van a ser procesados. En la mayoría de estos casos, un adversario puede intentar encontrar la clave "secreta" mediante prueba y error. (Lo que es posible siempre y cuando la clave sea suficientemente menor que el mensaje de forma que la clave correcta pueda identificarse de forma inequívoca). La probabilidad de que tenga éxito en esta tarea debe ser reducida hasta que se considere necesario, lo que depende de la aplicación en particular. El tamaño del espacio de búsqueda está relacionado con la cantidad de "información" existente, hablando en términos de la teoría de la información [SHANNON], que depende del número de valores posibles y de la probabilidad de cada valor de la siguiente manera: ----- \ Bits de información = \ - p * log ( p ) / i 2 i / ----- donde i varía desde 1 hasta el número de posibles valores secretos y p sub i es la probabilidad del i-ésimo valor. (Como p sub i es menor que uno, el logaritmo será negativo así que los elementos de la suma serán no negativos). Si hay 2^n valores diferentes con igual probabilidad existen n bits de información y un adversario tendría, de media, que comprobar la mitad de los valores, o 2^(n-1), antes de averiguar el valor secreto. Si los valores no son equiprobables, existirá menos información y necesitará, de media, menor número de pruebas. Además, cualquier valor imposible o muy poco probable, puede ser ignorado inicialmente por el adversario, que buscará primero entre los valores con mayor probabilidad. Por ejemplo, consideremos un sistema criptográfico que utilice claves de 56 bits. Si éstas son obtenidas con un generador de números pseudo-aleatorio que es inicializado con una semilla de 8 bits, el adversario sólo tendrá que buscar entre 256 claves posibles (utilizando el generador de números pseudo-aleatorios con cada posible semilla), no entre las 2^56 claves que en un principio puede parecer. En estas claves de 56 bits sólo hay 8 bits de "información". 3. Secuencias pseudo-aleatorias tradicionales. La mayoría de las fuentes tradicionales de aleatoriedad recurren a fuentes deterministas de números "pseudo-aleatorios", normalmente Leech [Pág. 5] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 inicializadas con un valor "semilla" y usan operaciones aritméticas o lógicas para construir una secuencia de valores. En [KNUTH] hay una exposición clásica de los números pseudo- aleatorios. Las aplicaciones que menciona son simulaciones de fenómenos naturales, muestreo, análisis numérico, testeo de programas de ordenador, toma de decisiones y juegos. Ninguno de estos ejemplos tiene las mismas características que el tipo de seguridad que estamos tratando en este documento. Sólo en los últimos dos casos podría existir un adversario que intentase averiguar el valor aleatorio. Sin embargo, en ambos el adversario normalmente sólo tiene una posibilidad de usar el valor que haya averiguado. A la hora de encontrar contraseñas o intentar romper un sistema de cifrado, el adversario normalmente tiene muchas, puede que ilimitadas, oportunidades de averiguar el valor correcto y debería presuponerse que va a ayudarse de un ordenador. Para comprobar la aleatoriedad de un número, Knuth sugiere una serie de pruebas incluyendo mediciones estadísticas y espectrales, que analizan cosas como la autocorrelación entre diferentes partes de la secuencia "aleatoria" o la distribución de sus valores. Una secuencia aleatoria estática, invariante, como la secuencia "aleatoria" proporcionada por las Tablas Estándares de Matemáticas CRC [CRC], podría superar dichas pruebas. Una técnica habitual de generación de números pseudo-aleatorios, conocida como generador lineal congruente de números pseudo- aleatorios, es la aritmética modular, donde el valor N+1-ésimo se calcula a partir del N-ésimo de la siguiente manera: V = ( V * a + b )(Mod c) N+1 N Este método está estrechamente relacionado con los generadores de números pseudo-aleatorios de registro de desplazamiento lineal, que son, criptográficamente hablando, conocidos en profundidad [SHIFT*]. En estos generadores, los bits se introducen en un registro de desplazamiento que realiza un OR Exclusivo (suma binaria sin acarreo) de los bits elegidos. Leech [Pág. 6] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 Por ejemplo: +----+ +----+ +----+ +----+ | B | <-- | B | <-- | B | <-- . . . . . . <-- | B | <-+ | 0 | | 1 | | 2 | | n | | +----+ +----+ +----+ +----+ | | | | | | | V +-----+ | V +----------------> | | V +-----------------------------> | XOR | +---------------------------------------------------> | | +-----+ V = ( ( V * 2 ) + B .xor. B ... )(Mod 2^n) N+1 N 0 2 La eficacia de los algoritmos tradicionales generadores de números pseudo-aleatorios se mide realizando pruebas estadísticas a las secuencias que construyen. Si elegimos cuidadosamente los valores iniciales de V, a, b, y c, o la ubicación de los registros de desplazamiento, el proceso anterior puede producir estadísticas muy buenas. Estas secuencias pueden ser adecuadas para simulaciones (experimentos de MonteCarlo) siempre que la secuencia sea ortogonal al espacio que se explora, pero incluso cuando esto se cumple, la existencia de patrones puede dar lugar a problemas. Sin embargo, dichas secuencias son desaconsejables para su uso en aplicaciones criptográficas, ya que, si se conoce el estado inicial, son completamente predecibles. Dependiendo del generador de números pseudo-aleatorios, la observación de una parte de la secuencia puede permitir conocer la misma en su totalidad [CRYPTO*, STERN]. Por ejemplo, con el generador anterior, se puede averiguar V(n+1) conociendo el valor de V(n). De hecho, se ha demostrado que con estas técnicas, incluso conociendo únicamente un bit de los valores pseudo-aleatorios, se puede determinar la semilla a partir de una parte de la secuencia. Se han roto todos los generadores lineales congruentes y se conocen técnicas para romper todos los generadores polinomiales congruentes [KRACZYK]. 4. Impredecibilidad La aleatoriedad en el sentido tradicional descrita en la sección 3 no es la misma que la requerida en el ámbito de la seguridad. Por ejemplo, las series constantes que son de dominio público, como Leech [Pág. 7] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 las que vienen en las tablas CRC, son muy débiles al ataque de un adversario. Una vez que éste las ha estudiado o es capaz de predecirlas, puede atravesar fácilmente cualquier barrera de seguridad, existente y futura, que esté basada en dicha secuencia [CRC]. Esas tablas ni siquiera tienen buenas propiedades estadísticas. Los siguientes apartados describen las limitaciones de algunas técnicas y fuentes de obtención de aleatoriedad. 4.1 Inconvenientes de los relojes y números de serie Los relojes y elementos similares del hardware o de los sistemas operativos, proporcionan bastante menos bits reales de aleatoriedad de lo que podría parecer. Las pruebas realizadas con los relojes de numerosos sistemas operativos revelan que su comportamiento puede variar de forma inesperada. Una versión de un sistema operativo en un ordenador puede proporcionar, digamos, precisión de microsegundos mientras que una configuración diferente del "mismo" sistema puede mantener fijos los bits menos significativos y sólo utilizar los bits más significativos, disminuyendo así la precisión. Esto significa que lecturas sucesivas del reloj pueden llegar a producir valores idénticos incluso si, ateniéndonos a su precisión nominal, ha transcurrido el tiempo suficiente para que el valor del reloj haya cambiado. También hay casos en los que realizar lecturas sucesivas del reloj produce secuencias artificiales debido a la existencia de código adicional que ¡incrementa el valor del reloj en una unidad! si detecta que el valor de éste no ha cambiado entre dos lecturas consecutivas. El diseño de código de aplicación portable que se base en relojes del sistema para generar números impredecibles es particularmente arriesgado ya que el diseñador de sistemas no siempre conoce las características del reloj que va a utilizar la aplicación. El uso de números de serie de componentes, como las direcciones Ethernet, también contienen menos bits de aleatoriedad de lo esperado. Estos valores suelen estar muy estructurados y los subcampos pueden tener un rango limitado de valores posibles fácilmente predecibles basándose en la fecha aproximada de fabricación o similares. Por ejemplo, se sabe que la mayoría de las tarjetas Ethernet instaladas en equipos de la marca DEC fueron fabricadas por la propia compañía, lo que delimita significativamente el rango de direcciones posibles. Este tipo de problemas con los relojes y números de serie hacen que el comportamiento del código sea impredecible, especialmente si va a utilizarse en diferentes sistemas o plataformas. Leech [Pág. 8] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 4.2 Intervalos de tiempo y contenido de eventos externos Es posible medir el tiempo y contenido de eventos generados por el usuario como un movimiento de ratón o una pulsación de tecla, por ejemplo. Éstos pueden, dentro de ciertas limitaciones, ser considerados buenas fuentes de aleatoriedad. En algunos sistemas, los datos de entrada como las pulsaciones de teclado se almacenan en un búfer, pero, aunque éstos tengan suficiente aleatoriedad, puede que no exista una forma sencilla de acceder al mismo. Otro problema es que no existen métodos estándar para obtener información sobre intervalos de tiempo. Esto hace que sea difícil diseñar programas fácilmente portables que utilicen estos mecanismos. Datos como el número de movimientos de ratón o las teclas pulsadas suelen ser más fácilmente accesibles que los intervalos de tiempo pero es posible que sean menos aleatorios ya que las entradas del usuario pueden ser altamente repetitivas. Otros eventos externos, como el tiempo de llegada de paquetes en una red, también debe ser utilizados con cierta precaución y debe considerarse la posibilidad de que el adversario pueda manipularlos. 4.3 La falacia de las operaciones complicadas Una estrategia que puede dar una falsa apariencia de impredecibilidad es construir una clave utilizando un algoritmo extremadamente complicado (o un buen generador tradicional de números pseudoaleatorios con buenas propiedades estadísticas) usando el reloj del sistema como semilla inicial. Un adversario que supiese, de forma aproximada, cuando se inicializó el generador tendría que probar un número relativamente pequeño de semillas ya que conocería el valor aproximado del reloj del sistema. Con este método se podrían obtener muchos bits pseudo-aleatorios pero el espacio de búsqueda que dicho adversario tendría que explorar sería bastante reducido. Aplicar operaciones complicadas a los datos no es de ayuda si el adversario puede saber qué operaciones son y no hay suficiente aleatoriedad en el valor inicial de la semilla. Incluso si se desconocen dichas operaciones, se puede llegar a anular la seguridad partiendo de un número pequeño de semillas y observando los resultados generados. Otro estrategia errónea es presuponer que un algoritmo generador de números pseudo-aleatorios extremadamente complicado producirá números aleatorios robustos sin un apoyo teórico o un análisis del algoritmo en cuestión. Cerca del principio del capítulo 3 de [KNUTH], el autor describe un algoritmo que puede servir como ejemplo de esta falacia. Se suponía que dicho algoritmo expresado en lenguaje máquina, sin Leech [Pág. 9] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 comentarios, sería tan complicado que una persona que intentase leer el código sería incapaz de saber qué estaba haciendo el programa. Desafortunadamente, la implementación de este algoritmo demostró que su salida, casi inmediatamente, converge a un valor que se repite constantemente en un caso y a un reducido ciclo de números en el otro. Si se tiene un número reducido de de semillas, las operaciones complicadas no sólo no ayudan sino que además, la elección de un algoritmo a ciegas, sin estudio previo, ¡puede eliminar la aleatoriedad de una buena semilla!. 4.4 La falacia de la selección dentro de un conjunto grande de datos Otra estrategia que puede dar una apariencia errónea de aleatoriedad es elegir al azar elementos de un conjunto grande de datos y suponer que su fortaleza está relacionada con el número total de bits del conjunto. Por ejemplo, los servidores de USENET a fecha de este documento procesan 35 megabytes de información al día. Escogemos un elemento de 32 bits al azar a partir de una posición inicial aleatoria, pero esto no significa que tengamos 32*8 = 256 bits de aleatoriedad. Aunque supongamos que muchos de esos datos pertenecen al lenguaje humano y probablemente tengan 2 ó 3 bits de información por byte no proporcionan 32*2.5 = 80 bits de aleatoriedad. Para un adversario que tenga acceso a los mismos 35 megabytes la aleatoriedad estará en el punto de inicio de la selección. Es decir, en este ejemplo en concreto, tendremos como mucho 25 bits de aleatoriedad. Podemos aplicar el mismo razonamiento a la selección de valores de un CD ROM, CD de audio o cualquier otro conjunto de datos de conocimiento público. El hecho de que se escoja un valor de un conjunto muy grande importa muy poco si el adversario tiene acceso al mismo. Sin embargo, esta estrategia puede ser de ayuda si el conjunto del que se extraen los datos es inaccesible para el adversario, como los búfers de un sistema multiusuario, por ejemplo. 5. El hardware, una fuente de aleatoriedad ¿Existe alguna esperanza de conseguir aleatoriedad robusta y portable en el futuro? Tal vez. Todo lo que se necesita es una fuente física de números impredecibles. Una fuente de ruido térmico o de desintegración radiactiva y un oscilador no limitado bastarían para resolver el problema [GIFFORD]. Esto es hardware trivial que podría incluirse fácilmente como parte estándar de la arquitectura de un ordenador. Además, cualquier sistema que tenga un disco giratorio o similar dispone de una buena fuente de aleatoriedad [DAVIS]. Todo lo que se necesita es la Leech [Pág. 10] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 concienciación de los vendedores de ordenadores de que esta pequeña cantidad de componentes adicionales y el software para utilizarlo son algo necesario. 5.1 Cantidad necesitada ¿Cuánta aleatoriedad se necesita? ¿Es posible cuantificar los requisitos en, digamos, números de bits aleatorios por segundo? La respuesta es que no se necesita mucha. En DES, la clave tiene una longitud de 56 bits y, como veremos en un ejemplo en la sección 8, incluso una clave para un sistema de máxima seguridad presumiblemente no necesitará más de 200 bits. Si lo que se necesita es una serie de claves, ésta puede crearse a partir de una buena semilla utilizando una secuencia criptográfica robusta, como se explica en la sección 6.3. Con estas técnicas, unos pocos cientos de bits aleatorios generados una vez al día serían suficientes. Incluso si los bits aleatorios son obtenidos lentamente, del orden de uno por segundo, y no es posible superponer el proceso, en aplicaciones de alta seguridad una espera ocasional de 200 segundos se podría considerar aceptable. Estas cifras se pueden alcanzar fácilmente, hasta una persona lanzando una moneda repetidamente podría satisfacerlas. Prácticamente cualquier hardware es mucho más rápido. 5.2 Sensibilidad al sesgo ¿Hay algún requisito específico sobre la función de distribución de los números aleatorios? La buena noticia es que no tiene por qué ser uniforme. Todo lo que se necesita es una estimación adecuada de su no-uniformidad para poder aproximar su rendimiento. A continuación se dan dos técnicas sencillas para eliminar sesgos en el flujo de datos; en la sección 6.1.2 se sugieren métodos más robustos. 5.2.1 Eliminación de sesgos utilizando la paridad del flujo Supongamos que tenemos una función mediante la cual podemos convertir una cadena de bits suficientemente larga en "cero" o "uno". Dicha función no será uniforme pero podrá acercarse tanto como se quiera. Podemos utilizar la paridad de la cadena para este propósito, con la ventaja de que sirve para cualquier sesgo, además de que su implementación en hardware es totalmente trivial. El siguiente análisis proporciona el número de bits que se deben muestrear: Supongamos que el ratio de unos y ceros es 0.5 + e : 0.5 - e, donde e Leech [Pág. 11] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 se encuentra entre 0 y 0.5 y es una medida de la "excentricidad" de la distribución. Supongamos también que la función de paridad utiliza muestras de N bits. La probabilidad de que la paridad sea cero o uno será la suma de los elementos pares o impares en la expansión binomial de (p + q)^N, donde p = 0.5 + e es la probabilidad de que sea uno y q = 0.5 - e, la probabilidad de que sea cero. Estas sumas pueden ser calculadas fácilmente como N N 1/2 * ( ( p + q ) + ( p - q ) ) y N N 1/2 * ( ( p + q ) - ( p - q ) ). (Cada una corresponde con la probabilidad de que la paridad sea 1 dependiendo de si N es par o impar.) Ya que p + q = 1 y p - q = 2e, estas expresiones se reducen a N 1/2 * [1 + (2e) ] y N 1/2 * [1 - (2e) ]. Ninguna de las dos será exactamente 0.5 a menos que e sea cero, pero podemos hacer que se acerquen a 0.5 tanto como queramos. Si queremos que las probabilidades estén a una distancia delta (d), de por ejemplo, 0.5, entonces N ( 0.5 + ( 0.5 * (2e) ) ) < 0.5 + d. Con N tenemos que N > log (2d)/log (2e). (2e es menor que 1, por lo que su logaritmo es negativo. Dividir entre un número negativo hace que el sentido de la inecuación cambie.) Leech [Pág. 12] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 La siguiente tabla proporciona la longitud necesaria de la cadena a muestrear, según el grado del sesgo, para poder estar a menos de 0.001 de una distribución 50/50. +---------+--------+-------+ | Prob(1) | e | N | +---------+--------+-------+ | 0.5 | 0.00 | 1 | | 0.6 | 0.10 | 4 | | 0.7 | 0.20 | 7 | | 0.8 | 0.30 | 13 | | 0.9 | 0.40 | 28 | | 0.95 | 0.45 | 59 | | 0.99 | 0.49 | 308 | +---------+--------+-------+ La última fila revela que, incluso si el 99% de la cadena son unos, la paridad de una cadena de 308 bits estará a menos de 0.001 de una distribución 50/50. 5.2.2 Eliminación de sesgos utilizando mapeados de transición Otra técnica, originalmente atribuida a von Neumann [VON NEUMANN], es tratar una cadena de bits como una secuencia de pares no superpuestos. Entonces se puede desechar cualquier secuencia 00 o 11, e interpretar 01 como 0 y 10 como 1. Suponiendo que la probabilidad de 1 es 0.5+e y que la probabilidad de 0 es 0.5-e, donde e es la excentricidad de la fuente, tal y como se describió en la sección anterior, la probabilidad de cada pareja es: +--------+-----------------------------------------+ | pareja | probabilidad | +--------+-----------------------------------------+ | 00 | (0.5 - e)^2 = 0.25 - e + e^2 | | 01 | (0.5 - e)*(0.5 + e) = 0.25 - e^2 | | 10 | (0.5 + e)*(0.5 - e) = 0.25 - e^2 | | 11 | (0.5 + e)^2 = 0.25 + e + e^2 | +--------+-----------------------------------------+ Esta técnica eliminará totalmente cualquier desviación a expensas de utilizar un número indeterminado de bits de entrada para cualquier número de bits de salida. La probabilidad de desechar una pareja en particular es 0.5 + 2e^2 por lo que el número esperado de bits de entrada necesarios para obtener X bits de salida es X/(0.25 - e^2). Este método presupone que los bits son cogidos de una secuencia donde la probabilidad de ser 0 ó 1 es igual para todos los bits y éstos no Leech [Pág. 13] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 están correlados, es decir, su distribución es independiente. Si, por ejemplo, hubiesen bits alternados provenientes de dos fuentes correladas, el análisis anterior no sería válido. Esta técnica también sirve para mostrar como un análisis estadístico sencillo puede ser erróneo si uno no está constantemente buscando patrones que puedan ser aprovechados por un atacante. Si el algoritmo fuese ligeramente distinto, de forma que se utilizasen parejas de bits sucesivas en lugar de parejas no superpuestas, el análisis estadístico sería el mismo; sin embargo, la serie de ceros y unos resultante, en lugar de ser aleatoria sería totalmente predecible. 5.2.3 Eliminación de sesgos utilizando la FFT Incluso cuando los datos son bits muy correlados o desviados, es posible que contengan cantidades aprovechables de aleatoriedad. Ésta puede ser extraída mediante el uso de la Transformada Discreta de Fourier o su variante optimizada, la FFT (Transformada Rápida de Fourier). Utilizando la transformada de Fourier de los datos se pueden eliminar correlaciones. Si se procesan la información y siguen existiendo restos de correlación se pueden crear líneas espectrales cercanas a la independencia estadística y aleatoriedad normalmente distribuida [BRILLINGER]. 5.2.4 Eliminación de sesgos utilizando compresión Utilizar las técnicas de compresión en sentido inverso al habitual puede proporcionar otro método para eliminar el sesgo de una secuencia de bits. Esto se deriva directamente de la definición de compresión inversa y la fórmula sobre la cantidad de información contenida en una secuencia, tratada en la sección 2. Como la compresión es reversible, la cantidad de información existente en la entrada más larga será la misma que la presente en la salida más corta. Según la ecuación de la información de Shannon, esto sólo es posible si, de media, las probabilidades de las diferentes secuencias cortas están distribuidas más uniformemente que las probabilidades de las secuencias más largas. Es decir, las secuencias más cortas están más "desequilibradas" respecto de la entrada. Sin embargo, muchas técnicas de compresión añaden datos predecibles al flujo de salida generado, en ocasiones de forma periódica, o patrones propios. Este método debería ser visto como una solución sencilla en comparación con las técnicas descritas anteriormente o en la sección 6.1.2. Como mínimo, debería ignorarse el comienzo de la secuencia comprimida resultante y utilizarse solamente los últimos bits de la misma. Leech [Pág. 14] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 5.3 El hardware existente puede ser utilizado como fuente de aleatoriedad. Como se expone a continuación, muchos ordenadores tienen componentes que pueden, con precaución, utilizarse para generar valores aleatorios de verdad. 5.3.1 Utilizando la entrada de vídeo/sonido existente. Cada vez hay más ordenadores que tienen entradas para digitalizar valores analógicos del mundo real, como el sonido desde un micrófono o la entrada de vídeo de una cámara. Bajo circunstancias adecuadas, dichas entradas pueden proporcionar cantidades bastante grandes de bits aleatorios. Si el sistema tiene ganancia suficiente para detectar algo, los datos obtenidos de una entrada de sonido sin que tenga nada conectada o una cámara con el objetivo tapado son, en esencia, ruido térmico. Por ejemplo, en una estación de trabajo SPARC se puede leer del dispositivo /dev/audio sin que haya nada en el conector del micrófono. Estos datos son ruido aleatorio aunque no debería ser considerados fiables sin antes comprobar que el componente no está roto, y, en cualquier caso, se debería eliminar el sesgo existente. Si queremos eliminar el sesgo de un flujo de datos, combinando esto con las técnicas de compresión, se puede, al menos en entornos UNIX, obtener una gran cantidad de datos aleatorios de calidad media ejecutando el siguiente comando: cat /dev/audio | compress - >archivo-con-bits-aleatorios 5.3.2 Utilizando las unidades de disco disponibles Las unidades de disco suelen sufrir variaciones aleatorias en su velocidad de giro debido al caos existente en las turbulencias de aire [DAVIS]. Si añadimos elementos de bajo nivel capaces de recoger el tiempo de búsqueda invertido por la unidad se pueden obtener mediciones que incluyan dicha aleatoriedad. Estos datos suelen estar altamente correlados por lo que necesitan bastante tratamiento, incluyendo el uso de la FFT (ver la sección 5.2.3). A pesar de todo, las pruebas han demostrado que, con dicho procesamiento, las unidades de disco pueden producir fácilmente 100 bits por minuto o más de datos aleatorios de excelente calidad. El hecho de que los fallos en las unidades de disco normalmente sean detectados rápidamente hace que sea muy difícil que esta forma de obtención de números aleatorios se vea afectada por mal funcionamiento de los componentes. Leech [Pág. 15] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 6. Estrategias recomendadas si se carece de hardware al que recurrir ¿Cuál es la mejor estrategia a seguir para generar números aleatorios correctamente si se carece de una fuente hardware? Obtener datos aleatorios de muchas fuentes no correladas y mezclarlos utilizando una función robusta. Ésta preservará la aleatoriedad existente en cualquiera de las fuentes incluso si los otros datos son conocidos o fácilmente adivinables. Esta estrategia es recomendable incluso si se tiene una buena fuente hardware ya que los componentes también pueden fallar, aunque debería ponderarse esto y la posibilidad de errores debidos a la complejidad del software utilizado. 6.1 Funciones de mezcla Una función de mezcla robusta es aquella que combina dos o más entradas para producir una salida donde cada bit es una función no lineal compleja de todos los bits de entrada. De media, cambiar cualquier bit de entrada modificará alrededor de la mitad de los bits de salida. Como la relación es compleja y no lineal, no se puede garantizar qué bits de salida cambiarán al modificar un bit en particular de la entrada. Considérese el problema de convertir una cadena de bits sesgada hacia el 0 ó el 1 en una cadena más corta con mayor aleatoriedad, tal y como se trata en la sección 5.2. Se necesita una función de mezcla robusta, que combine los bits de entrada para producir un número menor de bits de salida. El método proporcionado en la sección 5.2.1, la paridad, es simplemente el resultado de realizar sucesivas operaciones OR Exclusivas sobre cada bit de la secuencia; en breve veremos que se trata de una función de mezcla trivial. En la sección 6.1.2 se analiza el uso de funciones de mezcla más sólidas para extraer más aleatoriedad de una cadena de bits sesgada. 6.1.1 Una función de mezcla trivial La entrada de la función OR Exclusiva (XOR), equivalente a la suma sin acarreo, es un ejemplo de entrada de un sólo bit, tal y como se muestra en la siguiente tabla. Esta función es un caso degenerado donde el bit de salida siempre cambia al cambiar alguno de los bits de entrada. Aunque sencilla, es bastante ilustrativa: Leech [Pág. 16] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 +-----------+-----------+----------+ | entrada 1 | entrada 2 | entrada | +-----------+-----------+----------+ | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | +-----------+-----------+----------+ Si las entradas 1 y 2 están incorreladas y las combinamos de esa forma, el bit de salida será mejor (menos sesgado) que los de entrada de entrada. Si suponemos una "excentricidad" e, igual que en la sección 5.2, la excentricidad de salida estará relacionada con la excentricidad de entrada con la siguiente fórmula: e = 2 * e * e salida entrada 1 entrada 2 Como e nunca será mayor que 1/2, la excentricidad siempre se mejorará, excepto en el caso de que al menos una de las entradas sea constante y esté totalmente sesgada. Esto se muestra más claramente en la siguiente tabla. La fila superior y columna izquierda son las excentricidades de las dos entradas, las demás casillas, las excentricidades de salida: +--------+--------+--------+--------+--------+--------+--------+ | e | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 | +--------+--------+--------+--------+--------+--------+--------+ | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | | 0.10 | 0.00 | 0.02 | 0.04 | 0.06 | 0.08 | 0.10 | | 0.20 | 0.00 | 0.04 | 0.08 | 0.12 | 0.16 | 0.20 | | 0.30 | 0.00 | 0.06 | 0.12 | 0.18 | 0.24 | 0.30 | | 0.40 | 0.00 | 0.08 | 0.16 | 0.24 | 0.32 | 0.40 | | 0.50 | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 | +--------+--------+--------+--------+--------+--------+--------+ Sin embargo, hay que tener en cuenta que estos datos presuponen que las entradas no están correladas. Si las entradas fuesen, por ejemplo, la paridad del número de minutos transcurridos desde medianoche medidos en dos relojes con precisión de segundos, cada uno podría parecer aleatorio si los muestreamos a intervalos aleatorios mayores que un minuto. Si ambos fuesen muestreados y combinados mediante XOR, el resultado sería casi siempre cero. 6.1.2 Funciones de mezcla más robustas. El Estándar de Cifrado de Datos Del Gobierno de Los Estados Unidos [DES] es un ejemplo de una función de mezcla robusta para mezclar Leech [Pág. 17] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 valores de varios bits. La entrada consta de 120 bits (64 bits de "datos" y 56 bits para la "clave") y produce una salida de 64 bits donde cada uno de éstos depende de los bits de entrada a través de una función no lineal compleja. Si lo que queremos es mezclar todos los bits de entrada, datos y clave, también podemos utilizar otras funciones sólidas de cifrado que tengan esta característica. Una familia de buenas funciones de mezcla son los "resúmenes de mensaje", o funciones "hashing", como el Estándar de Resumen de Mensajes del Gobierno de Los Estados Unidos [SHS] y las funciones MD2, MD4, y MD5 [MD2, MD4, MD5]. Producen una salida mezclando los bits de entrada, y ésta puede tener un tamaño arbitrario. La familia MD* produce salidas de 128 bits mientras que la de SHS es de 160 bits. Aunque las funciones de resumen de mensajes han sido diseñadas para entradas de tamaño variable, DES y otras funciones de cifrado también pueden ser utilizadas con entradas de cualquier tamaño. Si nos bastan 64 bits de salida, podemos agrupar la entrada en conjuntos de 64 bits de datos y claves de 56 bits, rellenando con cero si es necesario; estas claves se utilizarán para cifrar sucesivamente los datos utilizando DES en Modo de Libro Electrónico de Códigos [DES MODES]. Si se requiere que la salida tenga más de 64 bits se puede recurrir a combinaciones más sofisticadas. Por ejemplo, si la entrada se divide en tres conjuntos A, B y C, se puede utilizar DES cifrando A utilizando sucesivamente B y C como claves para producir la primera parte de la salida, después cifrar B con C y con A como claves para obtener más bits de salida y, si es necesario, cifrar C utilizando como claves A y B. Todavía es posible obtener más bits de salida si invertimos el orden de las claves que se ha dado anteriormente. Lo mismo puede hacerse utilizando funciones hashing, agrupando los datos de entrada en bloques para obtener varias salidas. Pero hay que tener en cuenta que es imposible obtener más bits de aleatoriedad de salida que los bits de aleatoriedad de entrada. Para ver un ejemplo del uso de una función de mezcla reconsideremos el caso de una cadena de 308 bits donde cada uno está sesgado hacia el cero en un 99%. El método de la paridad, analizado en la sección 5.2.1, redujo esta cadena a un único bit con una probabilidad 1/1000 de estar igualmente sesgado hacia el cero o el uno. Pero según la ecuación de la información de la sección 2, la cadena en cuestión contiene 5 bits de información. Si la tratásemos con SHS o MD5 y cogiésemos los últimos 5 bits del resultado obtendríamos 5 bits de aleatoriedad, en lugar de un sólo bit. Leech [Pág. 18] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 6.1.3 Diffie-Hellman como una función de mezcla El intercambio de claves exponenciales de Diffie-Hellman es una técnica que se basa en un secreto compartido entre dos partes de forma que para una tercera parte resulta computacionalmente inabordable obtener dicho secreto aún pudiendo analizar todos los mensajes que se hayan intercambiado los dos extremos. Este secreto compartido es una mezcla de valores generados por cada una de las partes [D-H]. Si éstos son aleatorios, la aleatoriedad presente en el secreto es el total de la aleatoriedad de los valores generados por ambas partes, suponiendo que éstos no están correlados. 6.1.4 Utilizando una función de mezcla para aumentar los bits aleatorios Aunque no es necesario que en una función de mezcla el total de bits de salida sea menor o igual que el total de bits de entrada, los bits "mezclados" resultantes no pueden aumentar la cantidad de impredecibilidad presente en las entradas. Por esto, cuatro entradas de 32 bits con 12 bits de aleatoriedad en cada una (la entrada puede tomar cualquiera de 4096 valores posibles) no pueden producir una salida con más de 48 bits de aleatoriedad. La salida puede expandirse cientos o miles de bits mezclándola, por ejemplo, repetidas veces con números enteros, pero un adversario inteligente el espacio de búsqueda seguirá siendo de 2^48 posibilidades. Es más, obtener menos bits de salida que los utilizados como entrada tiende a reducir la aleatoriedad de la salida de la misma forma que el Or Exclusivo genera un bit a partir de dos. La última tabla de la sección 6.1.1 revela que si mezclamos un bit aleatorio con un bit constante mediante una operación XOR obtendremos un bit aleatorio. Aunque esto es cierto, no proporciona una forma de "replicar" un bit aleatorio en más de uno. Por ejemplo, si mezclamos un bit aleatorio con un 0 y luego con un 1, obtendremos una secuencia de dos bits pero ésta siempre será 01 ó 10. Como hay sólo dos posibles valores, seguiremos teniendo un sólo bit de aleatoriedad: el bit utilizado inicialmente. 6.1.5 Otros factores a tener cuenta al elegir una función de mezcla DES tiene la ventaja de que ha sido analizado exhaustivamente en búsqueda de debilidades, está muy documentado y su implementación tanto en hardware como en software se ha extendido por todo el mundo, incluso el código fuente se puede obtener de servidores FTP anónimos. La familia de SHS y MD* son algoritmos más jóvenes que han sido menos estudiados pero no hay razón para creer que contengan debilidades. Tanto MD5 como SHS derivan del anterior algoritmo MD4. El código fuente de todos ellos se puede encontrar en FTP anónimos [SHS, MD2, Leech [Pág. 19] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 MD4, MD5]. DES y SHS han sido aprobados para su uso por parte de la Agencia de Seguridad Nacional de los Estados Unidos (NSA) en base a su capacidad para mantener la confidencialidad de los datos. Aunque esto es motivo de especulaciones y debates, las investigaciones sobre DES a lo largo de los años han indicado que las modificaciones realizadas por la NSA en su diseño, originario de IBM, han sido principalmente para reforzarlo, y no se han encontrado fallos o vulnerabilidades especiales en él. También es cierto que las modificaciones que la NSA realizó al MD4 para crear el SHS fortalecieron el algoritmo, posiblemente contra debilidades aún no conocidas por la comunidad criptográfica. DES, SHS, MD4 y MD5 se pueden utilizar para cualquier propósito en general sin necesidad de pago alguno. MD2 tiene licencia gratuita sólo para uso no lucrativo junto con el programa Privacy Enhanced Mail [PEM]. Entre los algoritmos MD*, algunos creen que, igual que "Ricitos de Oro y los Tres Osos", MD2 es robusto pero demasiado lento, MD4 es rápido pero demasiado débil, y MD5 es el término medio. Otra ventaja de los algoritmos MD* y similares funciones hashing sobre los algoritmos de cifrado es que aquellos no están sujetos a las leyes impuestas por el Gobierno de los Estados Unidos que prohiben la exportación o importación de software y hardware de cifrado/descifrado. Lo mismo puede decirse de DES cuando se utiliza para construir un hash irreversible, pero la mayoría de las aplicaciones utilizan DES como cifrado reversible. 6.2 Fuentes de aleatoriedad no basadas en hardware Las mejores entradas para las funciones de mezcla son las que poseen aleatoriedad obtenida de hardware como tiempos invertidos por la unidad de disco al influirle las turbulencias del aire, las entradas de sonido con ruido térmico o la desintegración radiactiva. Sin embargo, si no se dispone de ninguno de éstos existen otras posibilidades, como los relojes del sistema, los búfers de entrada/salida, números de serie de usuarios/sistema/hardware/red y/o direcciones, intervalos de tiempo y datos de entrada del usuario. Desafortunadamente, bajo ciertas condiciones cualquiera de estas fuentes puede producir valores predecibles o limitados. Algunas de estas fuentes podrían ser muy buenas en sistemas multiusuario donde, en esencia, cada usuario del sistema es una potencial fuente de aleatoriedad. Sin embargo, en sistemas monousuario, como el típico PC IBM o Apple Macintosh, un adversario podría reproducir las condiciones iniciales e introducir datos en el proceso de mezcla que estuviesen lo suficientemente correlados como Leech [Pág. 20] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 para permitir una búsqueda exhaustiva. Se recomienda utilizar múltiples entradas aleatorias junto con una buena función de mezcla, pero incluso esto, con determinadas entradas en particular, puede resultar insuficiente. Por ejemplo, los intervalos de tiempo y el contenido de pulsaciones de teclado "aleatorias" por parte de un usuario pueden originar cientos de bits aleatorios pero es aconsejable tomar algunas precauciones, como por ejemplo, podemos suponer que hay unos pocos bits de aleatoriedad si el intervalo de tiempo entre pulsaciones no coincide con un intervalo previamente recogido y también podemos establecer que no obtendremos bits de aleatoriedad de la pulsación inicial, o si el tiempo de pulsación o el carácter tecleado ya han sido introducidos anteriormente. Estos tiempos y caracteres podrían mezclarse y luego combinarse con otros valores como lecturas del reloj, por ejemplo. Esta estrategia puede dar lugar a código portable para generar buenos números aleatorios para su uso en seguridad incluso si algunas de las entradas son potencialmente débiles en alguno de los sistemas en los que se utilice. Sin embargo, puede que sea insuficiente frente a un ataque de alto nivel contra un sistema monousuario, especialmente si el adversario ha sido cada capaz de observar el proceso de generación anteriormente. Sigue siendo preferible una fuente de aleatoriedad basada en hardware. 6.3 Secuencias criptográficas robustas A veces se necesita una secuencia de valores aleatorios. Aunque es posible que un adversario conozca algunos de éstos, en general, no debería ser capaz de predecir otros valores de la secuencia a partir de los que ya conoce. Lo más acertado es comenzar con una buena semilla aleatoria, realizar una serie de pasos criptográficamente robustos a partir de la misma [CRYPTO2, CRYPTO3], y asegurar que ninguno de sus elementos revela con exactitud el estado en el que se encuentra el generador en cada instante. Si es posible calcular cada valor de la secuencia a partir de su predecesor, puede conocerse cualquier valor de la misma, incluidos todos los valores generados en el futuro. Ésto ocurriría, por ejemplo, si cada valor fuese una función constante de los valores anteriores, incluso si se trata de una función de resumen de mensajes robusta y no reversible. Hay que resaltar que si la técnica utilizada para generar la secuencia de claves es lo suficientemente rápida, puede usarse con facilidad como base para un sistema de confidencialidad. Si las dos partes usan la misma técnica para elaborar la secuencia y comienzan con la misma semilla, generarán la misma secuencia. A ésta entonces Leech [Pág. 21] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 podría aplicársele una operación xor con los datos que se van a enviar, cifrarla, y aplicársele de nuevo una operación xor al al recibirla, quedando de nuevo descifrada gracias a las propiedades de reversibilidad de la operación xor. 6.3.1 Secuencias tradicionales robustas Tradicionalmente, una forma de elaborar secuencias robustas ha sido aplicar una función hash al resultado de unir la semilla con enteros o similares y enmascarar el valor resultante para limitar la información referente al estado del generador que el adversario pueda llegar a deducir. También es posible utilizar un algoritmo de "cifrado" con una clave aleatoria para cifrar y retroalimentar con una parte o la totalidad de la salida el valor cifrado en la siguiente iteración. Normalmente con el algoritmo de cifrado se especifican las técnicas de retroalimentación más adecuadas. A continuación se muestra un ejemplo del uso conjunto de desplazamientos y enmascaramientos para la retroalimentación de salida. Este tipo de realimentación es la recomendada por el Gobierno de Los Estados Unidos para utilizar en unión con DES [DES MODES]. +---------------+ | V | | | n | +--+------------+ | | +---------+ | +---------> | | +-------+ +--+ | Cifrado | <--- | Clave | | +-------- | | +-------+ | | +---------+ V V +------------+--+ | V | | | n+1 | +---------------+ Hay que resaltar que un desplazamiento de una sola unidad es equivalente a la técnica del registro de desplazamiento descrita anteriormente, en la sección 3, pero con la diferencia importante de que ahora la retroalimentación es una función no lineal compleja de todos los bits en lugar de una función lineal sencilla o combinaciones polinómicas de la salida a partir de unos pocos bits elegidos. Donald W. Davies ha demostrado que, comparado con la reintroducción de todos los bits de salida en la entrada, este tipo de Leech [Pág. 22] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 retroalimentación de salida utilizando desplazamientos parciales debilita el algoritmo de forma significativa. En concreto para DES, si ciframos sucesivamente un valor de 64 bits encontraremos una repetición en 2^63 iteraciones, aproximadamente. Retroalimentar con menos de 64 (y más de 0) bits también conducirá a una repetición, en un intervalo comprendido entre ¡2**31 y 2**32 iteraciones! Si generamos una secuencia utilizando estos métodos, predecir un valor de la misma a partir de otros conocidos es equivalente a romper el criptosistema, es decir, a, teniendo solamente información parcial, invertir la función hash "no reversible". Cuanta menos información se revele en cada iteración más difícil será para un adversario predecir la secuencia. Por eso es mejor utilizar un solo bit de cada valor. Se ha demostrado que en algunos casos esto hace imposible romper el criptosistema incluso cuando éste es reversible y puede romperse si se conocen todos los valores de la secuencia. 6.3.2 El Generador de secuencias Blum Blum Shub En la actualidad, el generador más robusto existente es el denominado generador Blum Blum Shub, por sus inventores [BBS]. Además es muy simple y está basado en los residuos cuadráticos. Su única desventaja es que, comparado con las técnicas tradiciones de la sección 6.3.1, tiene mayores requisitos computacionales. Esto no es una pega importante si se utiliza para cosas poco frecuentes, como la elaboración de claves de sesión. Simplemente hay que elegir dos números primos grandes, llamémosles "p" y "q", con la condición de que ambos proporcionen un resto igual a 3 si se dividen entre 4. Supongamos n = p * q. A continuación se elige un número aleatorio x que sea primo relativo de n. La semilla inicial del generador y el método para calcular los valores de la secuencia son: 2 s = ( x )(Mod n) 0 2 s = ( s )(Mod n) i+1 i Hay que tener la precaución de utilizar solamente unos pocos bits del final de cada s. Utilizar únicamente el bit de menor orden siempre es seguro. Si no se usan más de Leech [Pág. 23] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 log ( log ( s ) ) 2 2 i bits de menor orden, llegar a predecir cualquier bit de la secuencia generada es tan difícil como factorizar n. Mientras el valor inicial x sea secreto, incluso se puede hacer público n. Una característica interesante de este generador es que se puede calcular directamente cualquier valor de s. En particular i ( ( 2 )(Mod (( p - 1 ) * ( q - 1 )) ) ) s = ( s )(Mod n) i 0 lo que significa que, en aplicaciones donde se obtengan muchas claves utilizando esta técnica, no es necesario almacenarlas todas. Cada clave puede ser indexada y recuperada a partir del índice y el valor inicial de s y n. 7. Estándares para la creación de claves Existen muchos estándares para la creación de claves, dos de los cuales se describen a continuación. Ambos utilizan DES pero se podría sustituir por cualquier función de mezcla igual de robusta o más. 7.1 Recomendaciones del Departamento de Defensa estadounidense para la creación de Contraseñas. El Departamento de Defensa de los Estados Unidos ha especificado recomendaciones para la creación de contraseñas [DoD]. En ellas se sugiere el uso del Estándar de Cifrado de Datos [DES] en Modo Salida de Retroalimentación [DES MODES] de la siguiente forma: utilizar un vector de inicialización creado a partir de el reloj del sistema, identificador del sistema, identificador del usuario, y fecha y hora; utilizar una clave creada a partir de los registros de interrupción del sistema, registros de estado del sistema, y contadores del sistema; y, como texto plano, usar un valor de 64 bits generado externamente de forma aleatoria e introducido en forma de 8 caracteres por un administrador del sistema. La contraseña se calcula a partir de los 64 bits de "texto cifrado" Leech [Pág. 24] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 generado por DES en Modo Salida de Retroalimentación de 64 bits. De estos 64 bits se pueden utilizar los que se quiera y expandirlos en una palabra, frase pronunciable u otro formato si la contraseña va a ser recordada por una persona. 7.2 Creación de Claves mediante X9.17 Para generar una secuencia de claves, el Instituto Nacional Americano de Estándares (ANSI) ha recomendado el siguiente método: s es la semilla inicial de 64 bits. 0 g es la secuencia de claves de 64 bits generadas n k es una clave aleatoria reservada para generar la secuencia de claves t es el instante en el que se crea cada clave, con la mayor precisión posible (hasta 64 bits). DES ( K,Q) es el resultado de cifrar, utilizando DES, el valor Q con la clave K g = DES ( k, DES ( k, t ) .xor. s ) n n s = DES ( k, DES ( k, t ) .xor. g ) n+1 n Si g sub n va a ser utilizado como clave DES, debería ajustarse la paridad cada ocho bits, pero para calcular el siguiente s debería utilizarse g con todos sus bits, sin modificar ninguno de los 64. 8. Ejemplos del grado de aleatoriedad recomendado A continuación se muestran dos ejemplos con cálculos aproximados sobre la aleatoriedad necesitada en el ámbito de la seguridad. El primero trata sobre contraseñas, orientado a una seguridad media, mientras que el segundo presupone la necesidad de una clave criptográfica de seguridad muy alta. 8.1 Creación de contraseñas Supongamos que la contraseña de un usuario cambia una vez al año y que se necesita que la probabilidad de que un adversario pueda averiguarla sea menor de uno entre cien. Supongamos también que la Leech [Pág. 25] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 única forma de comprobar la validez de una contraseña es enviarla al sistema. Esto nos lleva a preguntarnos cada cuánto tiempo puede un adversario probar las contraseñas. Supongamos que se ha introducido un retardo de forma que, como mucho, se pueda comprobar una contraseña cada 6 segundos. Esto implica 600 pruebas a la hora, alrededor de 15000 al día y cerca de 5000000 en un año. Si existe algún tipo de monitorización es muy poco probable que alguien pueda estar haciendo intentos de forma continuada durante un año. De hecho, incluso si los archivos de incidencias se comprueban una vez al mes, es factible suponer que se puedan realizar alrededor de 500000 pruebas antes de que se detecte el ataque y se tomen medidas para cambiar las contraseñas y dificultar nuevas intentos. Una posibilidad entre mil de encontrar la contraseña en 500000 intentos implica la existencia de un espacio muestral de al menos 500000000 de contraseñas, alrededor de 2^29. Es decir, se necesitan 29 bits de aleatoriedad, lo que probablemente pueda conseguirse utilizando las recomendaciones del US DoD para la creación de contraseñas: 8 entradas, con una media probable de 5 bits de aleatoriedad en cada una (ver la sección 7.1). Utilizando una lista de 1000 palabras, podría expresarse la contraseña como una frase de tres palabras (1000000000 posibilidades) o, usando letras minúsculas y números, seis palabras ((26+10)^6 = 2176782336 posibilidades). Para contraseñas aún más seguras, el número de bits aumenta. Disminuir la probabilidad entre 1000 implica multiplicar el espacio de búsqueda por el mismo factor, lo que añade alrededor de 10 bits. Tener sólo una probabilidad entre un millón de averiguar una contraseña en el escenario anterior requeriría 39 bits de aleatoriedad y una contraseña que fuese una frase de cuatro palabras extraídas de una lista de 1000 palabras, o bien ocho letras o números. Para llegar a una posibilidad entre 10^9 se necesitarían 49 bits de aleatoriedad lo que requeriría de una frase de 5 palabras o una contraseña de 10 letras o números. Por supuesto, en un sistema real también influyen otros factores. Por ejemplo, cuanto mayores y más difíciles de recordar sean las contraseñas, mayor es la probabilidad de que los usuarios las apunten en una nota de papel, lo que aumenta el riesgo de que la seguridad se vea comprometida. 8.2 Una clave criptográfica de alta seguridad Supongamos que se necesita una clave de alta seguridad para cifrado/descifrado simétrico entre dos partes. Supongamos también que un adversario puede observar las comunicaciones y conoce el algoritmo que se utiliza. Dentro de las posibilidades, el adversario puede incluso probar con claves aleatorias con la esperanza de encontrar la Leech [Pág. 26] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 que se esté utilizando. También supongamos que los intentos mediante fuerza bruta son la mejor opción que tiene este adversario. 8.2.1 Esfuerzo por comprobación de clave ¿Cuánto cuesta probar cada clave? En las aplicaciones de alta seguridad lo mejor es asumir que poco. Incluso cuando una sola comprobación necesite cientos de miles de ciclos de procesador o más, puede que exista algún patrón que permita comprobar bloques enteros de cientos de claves con un coste mucho menor. Por esto probablemente es mejor no suponer más de un par de cientos de ciclos por comprobación. (No existe un límite inferior claro para esto ya que varios ordenadores trabajando en paralelo sobre bits con un cifrado débil podrían probar muchas, puede que bloques, claves en paralelo. Sin embargo, necesitamos fijar algún límite inferior y esperamos que se haya utilizado un algoritmo razonablemente robusto para nuestra hipotética aplicación de alta seguridad.) Si el adversario puede controlar un procesador altamente paralelo o una gran red de estaciones de trabajo, 2*10^10 ciclos por segundo es, probablemente, la menor asunción posible hoy en día. Mirando hacia delante sólo un par de años, existirá al menos una mejora en un orden de magnitud. Es decir, es razonable suponer que se puedan comprobar 10^9 claves por segundo, o 3.6*10^11 a la hora, o 6*10^13 a la semana, o 2.4*10^14 al mes. Esto implica la necesidad de al menos 51 bits de aleatoriedad en las claves para asegurarse de que no puedan ser descubiertas en un mes. Incluso es posible que, de aquí a unos pocos años, un adversario con el interés y los recursos suficientes pueda romper la clave en 2 semanas (de media sólo tendría que probar con la mitad de las claves posibles). 8.2.2 Ataques por encuentro a medio camino Si se dispone del texto plano, previamente elegido o no, su texto cifrado equivalente, y además la estructura del algoritmo de cifrado lo permite, es posible llevar a cabo un "ataque por encuentro a medio camino". (En un ataque conociendo texto plano, el adversario conoce parte o todo el texto que se ha cifrado, posiblemente alguna cabecera estándar o campos de acompañamiento. En un ataque sobre texto plano elegido, el adversario puede forzar a que se cifre una parte del texto en concreto, posiblemente insertando información y enviándola a través del canal de cifrado). Una explicación simplificada del funcionamiento del ataque por encuentro a medio camino es la siguiente: el adversario puede cifrar a medias un texto plano, conocido o elegido, utilizando la primera mitad de todas las claves posibles, ordenar la salida, y descifrarla usando la segunda mitad de las claves. Si se encuentra una Leech [Pág. 27] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 coincidencia, la clave completa puede recomponerse a partir de las mitades y utilizarse para descifrar otras partes del mensaje u otros mensajes. En el mejor caso, este tipo de ataque reducirá a la mitad el trabajo requerido por el adversario, añadiendo al nivel de esfuerzo un factor grande pero constante. Para asegurar un cierto grado de seguridad contra esta técnica se necesita duplicar la cantidad de aleatoriedad de la clave hasta un mínimo de 102 bits. El ataque por encuentro a medio camino presupone que el algoritmo criptográfico puede ser descompuesto de esta manera, pero esto no puede decidirse sin tener un conocimiento profundo de éste último. Incluso si un algoritmo sencillo no es débil ante este ataque, un intento de producir un algoritmo más robusto aplicándolo dos veces (o dos algoritmos diferentes secuencialmente) con diferentes claves podría proporcionar menos seguridad de la esperada, ya que el algoritmo compuesto podría ser objeto de un ataque por encuentro a medio camino. Para realizar un ataque de este tipo puede que se necesiten mucho recursos, pero éstos están al alcance de los servicios de seguridad de un país grande. Prácticamente todos los países espían el tráfico de los gobiernos de otras naciones y se cree que muchos países también hacen lo mismo con el tráfico comercial para obtener beneficios económicos. 8.2.3 Otras consideraciones Como no hemos ni siquiera considerado las capacidades del hardware especializado para romper códigos o simplemente el margen de seguridad que queremos dar a las suposiciones realizadas, probablemente 128 bits de aleatoriedad, lo que implica una longitud mínima de 128 bits, es un buen mínimo para una clave criptográfica de alta seguridad. Si las dos partes implicadas acceden a crear una clave mediante intercambio Diffie-Hellman [D-H], en principio cada una sólo tendría que proporcionar la mitad de la aleatoriedad necesaria. Sin embargo, es probable que las entradas aleatorias que ambas utilicen estén correladas por lo que es mejor suponer que cada parte debe proporcionar al menos 96 bits de aleatoriedad para obtener una seguridad muy alta usando este método.. Esta cantidad de aleatoriedad en las entradas está más allá del límite recomendado por el Departamento de Defensa Estadounidense para la creación de contraseñas y podría necesitar intervalos de pulsaciones de teclado, hardware de obtención de números aleatorios u otras fuentes. Debería destacarse que los cálculos sobre la longitud de clave expuestos anteriormente son discutibles y dependen de suposiciones Leech [Pág. 28] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 sobre el algoritmo criptográfico utilizado. En algunos casos, un profesional con conocimientos profundos de técnicas de criptoanálisis y de la fortaleza del algoritmo en uso puede decidir usar claves con longitud menor a la mitad de la longitud mínima aquí sugerida. 9. Conclusiones La obtención de valores impredecibles y "aleatorios" para su uso en seguridad es algo necesario pero difícil. Hemos mostrado como las técnicas basadas en hardware para producir dichos valores son relativamente simples. En particular, la cantidad y la calidad no tienen por qué ser elevados y se podría utilizar el hardware existente en los ordenadores, como los discos duros. Las técnicas computacionales actuales permiten procesar valores con poca aleatoriedad obtenidos de varias, o una única, fuente y producir pocos valores de alta calidad, materia prima para la creación de claves. Ante la falta de fuentes hardware de aleatoriedad, normalmente se pueden utilizar, con precaución, varias fuentes basadas en software; sin embargo, la mayor parte de de los sistemas modernos ya poseen componentes, como unidades de disco o entradas de audio, que pueden ser utilizados para producir valores de alta aleatoriedad. Una vez se dispone de suficientes valores de buena calidad (unos pocos cientos de bits) para la creación de claves, hay métodos computacionales para producir secuencias robustas de valores impredecibles a partir de dichos valores semilla. 10. Consideraciones de seguridad Todo este documento trata sobre técnicas y recomendaciones para generar valores aleatorios que puedan ser utilizados como contraseñas, claves criptográficas y similares en el ámbito de la seguridad. Referencias [ASYMETRIC] - Secure Communications and Asymmetric Cryptosystems, editado por Gustavus J. Simmons, AAAS Selected Symposium 69, Westview Press, Inc. [BBS] - A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, v. 15, n. 2, 1986, L. Blum, M. Blum, & M. Shub. [BRILLINGER] - Time Series: Data Analysis and Theory, Holden-Day, 1981, David Brillinger. Leech [Pág. 29] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 [CRC] - C.R.C. Standard Mathematical Tables, Chemical Rubber Publishing Company. [CRYPTO1] - Cryptography: A Primer, A Wiley-Interscience Publication, John Wiley & Sons, 1981, Alan G. Konheim. [CRYPTO2] - Cryptography: A New Dimension in Computer Data Security, A Wiley-Interscience Publication, John Wiley & Sons, 1982, Carl H. Meyer & Stephen M. Matyas. [CRYPTO3] - Applied Cryptography: Protocols, Algorithms, and Source Code in C, John Wiley & Sons, 1994, Bruce Schneier. [DAVIS] - Cryptographic Randomness from Air Turbulence in Disk Drives, Advances in Cryptology - Crypto '94, Springer-Verlag Lecture Notes in Computer Science #839, 1984, Don Davis, Ross Ihaka, and Philip Fernstermacher. [DES] - Data Encryption Standard, United States of America, Department of Commerce, National Institute of Standards and Technology, Federal Information Processing Standard (FIPS) 46-1. - Data Encryption Algorithm, American National Standards Institute, ANSI X3.92-1981. (Ver también FIPS 112, Password Usage, que incluye código FORTRAN para implementar DES.) [DES MODES] - DES Modes of Operation, United States of America, Department of Commerce, National Institute of Standards and Technology, Federal Information Processing Standard (FIPS) 81. - Data Encryption Algorithm - Modes of Operation, American National Standards Institute, ANSI X3.106-1983. [D-H] - New Directions in Cryptography, IEEE Transactions on Information Technology, Noviembre, 1976, Whitfield Diffie and Martin E. Hellman. [DoD] - Password Management Guideline, United States of America, Department of Defense, Computer Security Center, CSC-STD-002-85. (Ver también FIPS 112, Password Usage, que incorpora CSC-STD-002-85 como uno de sus apéndices.) [GIFFORD] - Natural Random Number, MIT/LCS/TM-371, Septiembre 1988, David K. Gifford [KNUTH] - The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Chapter 3: Random Numbers. Addison Wesley Publishing Company, Segunda Edición 1982, Donald E. Knuth. Leech [Pág. 30] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 [KRAWCZYK] - How to Predict Congruential Generators, Journal of Algorithms, V. 13, N. 4, Diciembre 1992, H. Krawczyk [MD2] - The MD2 Message-Digest Algorithm, RFC1319, Abril 1992, B. Kaliski [MD4] - The MD4 Message-Digest Algorithm, RFC1320, Abril 1992, R. Rivest [MD5] - The MD5 Message-Digest Algorithm, RFC1321, Abril 1992, R. Rivest [PEM] - RFCs 1421 al 1424: - RFC 1424, Privacy Enhancement for Internet Electronic Mail: Part IV: Key Certification and Related Services, 02/10/1993, B. Kaliski - RFC 1423, Privacy Enhancement for Internet Electronic Mail: Part III: Algorithms, Modes, and Identifiers, 02/10/1993, D. Balenson - RFC 1422, Privacy Enhancement for Internet Electronic Mail: Part II: Certificate-Based Key Management, 02/10/1993, S. Kent - RFC 1421, Privacy Enhancement for Internet Electronic Mail: Part I: Message Encryption and Authentication Procedures, 02/10/1993, J. Linn [SHANNON] - The Mathematical Theory of Communication, University of Illinois Press, 1963, Claude E. Shannon. (extraído de: Bell System Technical Journal, Julio y Octubre 1948) [SHIFT1] - Shift Register Sequences, Aegean Park Press, Revised Edition 1982, Solomon W. Golomb. [SHIFT2] - Cryptanalysis of Shift-Register Generated Stream Cypher Systems, Aegean Park Press, 1984, Wayne G. Barker. [SHS] - Secure Hash Standard, United States of American, National Institute of Science and Technology, Federal Information Processing Standard (FIPS) 180, Abril 1993. [STERN] - Secret Linear Congruential Generators are not Cryptograhically Secure, Proceedings of IEEE STOC, 1987, J. Stern. [VON NEUMANN] - Various techniques used in connection with random digits, von Neumann's Collected Works, Vol. 5, Pergamon Press, 1963, J. von Neumann. Direcciones de los Autores Donald E. Eastlake 3rd Digital Equipment Corporation 550 King Street, LKG2-1/BB3 Littleton, MA 01460 Leech [Pág. 31] RFC 1750 La aleatoriedad en seguridad Diciembre 1994 Teléfono: +1 508 486 6577(w) +1 508 287 4877(h) Correo Electrónico: dee@lkg.dec.com Stephen D. Crocker CyberCash Inc. 2086 Hunters Crest Way Vienna, VA 22181 Teléfono: +1 703-620-1222(w) +1 703-391-2651 (fax) Correo Electrónico: crocker@cybercash.com Jeffrey I. Schiller Massachusetts Institute of Technology 77 Massachusetts Avenue Cambridge, MA 02139 Teléfono: +1 617 253 0161(w) Correo Electrónico: jis@mit.edu Leech [Pág. 32]