Ataques de búsqueda de claves

En general, para la mayoría de los sistemas criptográficos, las claves criptográficas deben ser lo más aleatorias posible. Para la mayoría de los cifrados simétricos, las claves pueden y deben ser un conjunto de bits verdaderamente aleatorio. Para la mayoría de los cifrados asimétricos, las claves privadas son números elegidos al azar con ciertas restricciones (como primalidad o ser generadores en un grupo) o son el resultado de cálculos basados ​​en un conjunto de números aleatorios con algunas restricciones. En ambos casos, el material de la clave presenta una alta entropía . En contraste, la mayoría de los datos sin comprimir en la memoria de una computadora tienen una entropía relativamente baja. Como resultado, si se sabe que una clave existe en la memoria en su forma original, es probable que destaque sobre el fondo de datos que no son clave debido a su alta entropía, y un atacante solo necesita buscar claves coincidentes en áreas de memoria o almacenamiento que tengan una alta entropía.

El contraste entre la baja entropía de la mayoría de los datos y la alta entropía de los datos clave es suficiente para resultar evidente a simple vista. La imagen de la derecha muestra un ejemplo de ello.

Si bien la búsqueda estadística de claves puede ser eficaz para reducir la cantidad de memoria que se debe buscar, aún requiere probar áreas de alta entropía para verificar si contienen el material de clave correcto. En ciertos casos, particularmente en el contexto de los sistemas de cifrado de clave pública , es posible determinar patrones que deben aparecer en el material de clave y luego limitar la búsqueda a las áreas donde se encuentran estos patrones.

Shamir y van Someren ^{[ 1 ]} demostraron un ejemplo de este enfoque analítico para encontrar claves privadas RSA donde se conoce la clave pública y tiene un exponente público pequeño. En el sistema RSA, la clave pública es un par${\displaystyle (n,e)}$, dónde${\displaystyle n=pq}$donde p y q son dos números primos grandes. La clave privada correspondiente es${\displaystyle (n,d)}$(o a veces)${\displaystyle (p,q,d)}$o alguna variante de la misma) donde${\displaystyle ed\equiv 1{\pmod {\phi (n)}}}$, lo que significa que e multiplicado por d es equivalente a 1, módulo${\displaystyle \phi (n)}$donde φ representa la función totiente de Euler y es el tamaño del grupo multiplicativo módulo n. En el caso de una clave RSA:

${\displaystyle \phi (n)=(p-1)(q-1)=np-q+1}$

Encontrar el valor de${\displaystyle \phi (n)}$La factorización de n permite la factorización de n, y la seguridad del criptosistema RSA se basa en la dificultad de hacerlo. Por lo tanto, un atacante no puede determinar d con exactitud, dados e y n . Sin embargo, un atacante puede conocer bastante sobre cómo es d , dado el conocimiento de que p y q generalmente se eligen con la misma longitud en bits y ambos están "cerca" de la raíz cuadrada de n . Por lo tanto, un atacante puede aproximar una estimación de:

${\displaystyle \phi (n)\approx \phi '(n)=n-2{\sqrt {n}}}$

y, por lo general, esta aproximación será correcta en la mitad más significativa de los bits de su representación binaria. La relación entre e y d significa que:

${\displaystyle d=(1+k.\phi (n))/e}$

donde se desconoce el valor exacto de k pero${\displaystyle 0<k<e.}$Utilizando este hecho y la aproximación${\displaystyle \phi '(n)}$, el atacante puede enumerar un conjunto de valores posibles para la mitad superior de la representación binaria de d para cada valor posible de k . Estos patrones binarios se pueden probar muchos órdenes de magnitud más rápido que realizando un descifrado de prueba. Además, en el caso común de${\displaystyle e=3}$Se puede demostrar que${\displaystyle k=2,}$lo que permite determinar con exactitud la mitad superior de los bits de d y buscarla directamente.