Diffie Hellman: ¿qué tan grande debe ser el número aleatorio?

Respuesta corta. Sí, creo que está bien elegir x como un número aleatorio de 160 bits. (No apostaría mi vida en ello, pero estoy bastante seguro de que está bien).

Detalles técnicos. Hay (al menos) dos formas de atacar a Diffie-Hellman.

1. Una forma es usar algoritmos sofisticados para calcular el logaritmo discreto, por ejemplo, basado en el tamiz de campo numérico o similar. El tiempo de ejecución de estos algoritmos depende del módulo principal p, y necesitas que p sea grande (ciertamente al menos 1024 bits) para resistir estos ataques.

2. Otra forma es usar algoritmos más básicos, como el algoritmo paso gigante paso bebé o el algoritmo de Pollard. El tiempo de ejecución de estos algoritmos depende del tamaño más pequeño de q o del tamaño del exponente x. Necesitas q sea grande (al menos 160 bits) para resistir estos ataques. Necesita que se elija el exponente de un espacio grande (es decir, al menos 160 bits de entropía) para resistir estos ataques.

Ya que hay dos ataques diferentes, deberás elegir tus parámetros para derrotar a ambos. Por eso necesita que su exponente tenga al menos 160 bits.

Ahora lo más conservador es elegir x uniformemente al azar en el intervalo [0, q-1] (o [2, q-2] si lo prefiere, realmente no importa). Esto seguramente será seguro, siempre y cuando p y q sean lo suficientemente grandes. La cita que sacó parece decir que X9.42 recomienda que utilice este enfoque conservador.

Sin embargo, en muchos casos puede obtener una optimización, a veces conocida como la optimización de corto exponente. La idea es que elija x uniformemente al azar de un intervalo más pequeño, digamos [0, 2 ¹⁶⁰ - 1]. Esto suele ser seguro, si el protocolo está diseñado correctamente, aunque ha habido algunas excepciones. El beneficio es que si q es grande, elegir una x más corta como esta puede mejorar significativamente el rendimiento.

Para el grupo que mencionas, q = (p-1) / 2. (*) En otras palabras, q tiene una longitud de alrededor de 1023 bits. Esto significa que lo más conservador es elegir que su x sea del rango completo [0, q-1], pero creo que probablemente pueda salirse con la optimización de corto exponente. Intenté leer los documentos de IKE y no encontré de inmediato una declaración explícita de si la optimización de corto exponente siempre es segura para IKE, aunque sí encontré algunos comentarios que parecen indicar que los desarrolladores anticiparon podría estar bien de usar.

Nota al pie (*): Puede inferir esto de la siguiente manera. RFC 2409 dice que las "propiedades de estos grupos se describen en [RFC2412]". La sección E.2 de RFC 2412 enumera el grupo correspondiente y enumera el mayor factor primo de la orden del grupo. Se puede verificar que el factor primo más grande sea (p-1) / 2. De esto se deduce que q = (p-1) / 2.

Editar 3/24: Me di cuenta, gracias a la respuesta de @ CodeinChaos, que mencionó que su razón para usar un exponente corto no es el rendimiento sino la entropía limitada en su PRNG. Me parece un poco extraño. ¿Qué PRNG estás usando? ¿Estás seguro de que tienes un PRNG de fuerza criptográfica? La mayoría de los PRNG criptográficos se pueden usar para extraer una cadena pseudoaleatoria de longitud arbitraria. Si el tuyo no lo hace, siempre puedes tomar la salida de tu PRNG y expandirla a una cadena pseudoaleatoria de 1024 bits: por ejemplo, generar una clave AES K de 128 bits, luego usar AES (K, 0), AES (K , 1), AES (K, 2), AES (K, 3), ..., AES (K, 7) para generar una cadena pseudoaleatoria de 1024 bits. Una vez que tenga una cadena pseudoaleatoria de 1024 bits (siempre que sea de calidad criptográfica y el RNG original tenga suficiente entropía), puede usarla como un exponente de longitud completa de 1024 bits.

Verifique que su RNG / PRNG sea criptográfico. Por ejemplo, /dev/urandom y CryptGenRandom son buenos, pero rand() , random() , drand48() son todos malos. ( /dev/random es fuerte pero innecesario; use /dev/urandom en su lugar, y podrá dibujar un exponente de longitud completa sin problemas). Busque en este sitio más información sobre PRNG de calidad criptográfica.

  

No hace falta decir que tengo un problema de capacidad de generación de ruido y ya estoy sufriendo, por lo que necesito la menor cantidad de ruido que aún mantiene el sistema seguro (con una seguridad de aproximadamente 112 bits equivalentes, que es aproximadamente el nivel de seguridad proporcionada por el DH con un 1024 bit prime).

Me gustaría usar un buen PRNG criptográfico que siembras (y en ocasiones vuelves a sembrar) con tu entropía real. De esa manera puedes crear fácilmente grandes cantidades de números aleatorios. Creo que fortuna es una opción popular para un PRNG.

Una vez que generar números aleatorios es barato, no hay razón para usar números más pequeños que el rango máximo. Pero como no estoy muy familiarizado con DH, no sé cuál es ese rango.

160 bits es suficiente para 1024 bit DH, pero será más débil que su AES de 256 bit. Consulte, por ejemplo, la Tabla 2 en NIST SP 800-57 , o esta calculadora de longitud de clave . (Para equivalencia con claves simétricas de 256 bits, recomiendan 15360 bits DH (con un número aleatorio de 512 bits) o, más prácticamente, utilizando una curva elíptica de 512 bits.)

Entonces, si su sistema heredado le impide utilizar un intercambio de claves más fuerte, utilizar una clave de 256 bits puede ser una pérdida de tiempo.