Uso de entropía para la obtención de candidatos a texto plano
Agosto 3, 2012
El día 12 de Julio, a través de Facebook, publiqué un pequeño desafío en el cual se debía obtener el texto plano de una cadena cifrada.
El desafío en cuestión era:
"Gana una licencia original de ESET Smart Security Home Edition resolviendo un reto! Estos son los datos:
Algoritmo: RC2
Modo: ECB
Texto cifrado: jf3NiZlBlpU3kRe3Kndb5RfEqBrukWk/KoEx1mNYKTc="
El desafío se extendió en twitter para tener más cobertura, pero luego de dos semanas sin recibir respuestas decidí rifar la licencia.
Resolución
Durante el transcurso de las dos semanas se dieron las siguientes pistas:
Entropía de información http://es.wikipedia.org/wiki/Entropía_(información)!
if (entropy(variable) <= 4,7) then variable is a plaintext candidate
password can be found in a common wordlist.
Juntando las pistas y sin entrar en mucho detalle, construimos un pequeño script en PHP que permite obtener los posibles candidatos a texto plano usando el concepto de entropía:
// Decodificamos el texto cifrado para llevarlo a su estado natural
$cipher = base64_decode('jf3NiZlBlpU3kRe3Kndb5RfEqBrukWk/KoEx1mNYKTc=');
// Leemos las contraseñas de una lista con palabras comunes
$words = file('worst.txt');
foreach ($words as $word) {
$word = trim($word);
// Desciframos el texto usando una de las palabras comunes
// El algoritmo es RC2 y el modo ECB
$text = mcrypt_decrypt(MCRYPT_RC2, $word, $cipher, MCRYPT_MODE_ECB);
// En este punto se encuentra la magia
// Si la entropía del texto descifrado es menor o igual a 4.7
// entonces lo consideramos como un posible candidato a texto plano
if (entropy($text) <= 4.7) {
echo $word . "\t" . $text . "\t" . entropy($text) . PHP_EOL;
}
}
// Función de entropía que obtiene el grado de dispersión del texto plano
// a menor dispersión, mayor probabilidad de encontrar un texto coherente
// a mayor dispersión, mayor probabilidad de encontrar un texto binario
function entropy($text) {
$entropy = 0;
$len = strlen($text);
if ($len == 0)
return 0;
$map = array();
for ($i = 0; $i < 256; $i++)
$map[$i] = 0;
for ($i = 0; $i < $len; $i++)
$map[ord($text[$i])]++;
for ($i = 0; $i < 256; $i++) {
$p = $map[$i] / $len;
if ($p > 0) {
$entropy -= $p * (log($p) / log(2));
}
}
return $entropy;
}
Suponiendo que los únicos caracteres que conforman el texto plano son las veintiseis (26) letras del alfabeto latino (a - z), la entropía por carácter se calcula usando la fórmula "Logaritmo en base 2 de 26", que tiene como resultado 4,7.
Ejecutando el script observamos las posibles claves y valores para el texto plano:
Clave Candidato texto plano Entropía 123456 Quiero una licencia de 3537! 3.890 fuck G╩▄ı·Úæ$9 íÊùæYl4─çÝ─ cı♠\╣▄¾Ï♠ 4.625 love ►õÑq─#êC¾►▀\1‼↑±╠«ìD¿┤bàfbà▀¶‼← 4.687 sparky Á┌®§*,¯ê:~ ¬"Z¬®ê╔ü!>»oDåñZOh»,Ù 4.625 andrea ♠¯┌ºoòaR¨é└ù£┘ò\]aùÉp┘bh¾┌├µ|♫Kp 4.625 morgan _zß┴ó°QôYıùø►É%Ö▲ïÚ5÷╚┐┴ã▓5 ßı♫ 4.687 teens ]╬╬┼"G♀P«↑♠¨áxóÀb╬r2♫uä?.2♥╬‼|Ýæ 4.687 lakers k¸╗☼¶Ûµø]][#aª┬¤èª<┼?ªÑ║¸ƒ║¤Xîñ4 4.601 monster Ä╗↔·\7SÓ+_ 0ÿï♦┤Ï→ƒ7¨¶§l\ÙCÏÄu♦ 4.687 baby UÀ☺╣ÔÃ5yî(█º┴ÔD±¨vâyá|ÑÆ☼DÆU¨j| 4.562 squirt íÜ‗ð½♫ÆQ©╠ü ñ£©þ─↑³|ÜíJ(%Nº▲Qý³ 4.687 hunting õC♠/z♠¢═à♥█◄JUÂ\Y▓\1┌▓ÒÒ↑U⌂ÚÁiã▬ 4.687
El mismo concepto puede apreciarse en herramientas de criptografía como Cryptool:
La respuesta final al desafío era: Quiero una licencia de 3537!
Resolución alternativa
La resolución alternativa por Perverths0 es utilizar expresiones regulares para descartar cualquier texto en plano que no contenga caracteres ASCII, una muy buena idea también:
$method = 'RC2-ECB';
$decode = 'jf3NiZlBlpU3kRe3Kndb5RfEqBrukWk/KoEx1mNYKTc=';
$fp = fopen('cain.txt', 'r');
while ($linea = fgets($fp, 1024)) {
$pass = trim($linea);
$plain = mcrypt_decrypt(MCRYPT_RC2, $pass, base64_decode($decode), MCRYPT_MODE_ECB);
if (!preg_match('/[\x80-\xFF]/', $plain)) {
echo "La respuesta es: $pass - $plain";
break;
}
}
Archivado en: Criptografía, Retos informáticos |
Daniel, ¿cual es la función de esta parte del script?:
for ($i = 0; $i < $len; $i++)
$map[ord($text[$i])]++;
Porque no veo que se guarde el incremento en el array.
Muy bueno :), yo no supe como sacar la función de entropía, me hubiera ganado esa licencia
Juan: Es para contar la aparición de cada carácter en el texto, es un equivalente a:
$map[ord($text[$i])] = $map[ord($text[$i])] + 1
Más abajo se calcula la probabilidad de aparición de ese carácter:
$p = $map[$i] / $len;