Contenido principal

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:
:arrow: Entropía de información http://es.wikipedia.org/wiki/Entropía_(información)!
:arrow: if (entropy(variable) <= 4,7) then variable is a plaintext candidate
:arrow: 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:

<?php

// 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:

Entropía de información

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:

<?php

$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 |

2 comentarios

  1. Juan Escobar Agosto 3, 2012 @ 8:03 am

    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 :D

  2. Sysroot Agosto 3, 2012 @ 12:09 pm

    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;

Deja un comentario