Hackit 2013 - Nivel 2 (parte I)

Hola de nuevo, gente. Para darle gusto a marcan así como a los inexistentes lectores de este no-blog, vamos a publicar una posible solución al nivel 2 del hackit, la que se daba por hecho que cualquiera iba a intentar (aunque gracias a los chicos de DiarioLinux conocemos una forma más rápida) ;-)

Recordemos la prueba consistía en un archivo RAR cifrado, del que nos daban una pista sobre la contraeña:

 echo sha1(md5($password)); ?>
77134aa1b02b61cd841d2a81bf64796a31234e28

Tanto SHA1 como MD5 son funciones de resumen criptográfico (reducciones criptográficas, digests), esto es: cualquiera de las dos toma como entrada un flujo de octetos de tamaño arbitrario y producen una salida de tamaño fijo: 20 octetos (160bits) para SHA-1 y 16 octetos (128 bits) para MD5.

Existen muchas funciones que convierten unos datos arbitrarios en uno de tamaño fijo: por ejemplo la función CERO que, para cualquier dato de entrada siempre produce el resultado (constante) 0.

Las funciones de resumen criptográfico tienen interés porque su resultado no es trivial y cumple una serie de  propiedades, de las que cito las relevantes para entender como resolver el nivel, a continuación:

• Calcular la salida para unos datos de entrada no debe ser muy costoso.
• Para una misma entrada, la salida siempre es la misma.
• Es muy difícil (costoso) averiguar el mensaje original a partir del valor resumen.

Así pues, salvo que "hagamos trampa" y usemos tablas arcoíris propios o ajenos, como proponen en DiarioLinux, tendremos que usar un enfoque más... programático.

Implementaremos lo que se llama un "ataque basado en diccionario", esto es, partiremos de un diccionario de palabras e iremos computando los hashes o resúmenes de cada una de las palabras, a ver si encontramos una coincidencia con lo que nos proponen en el reto. Como en el enunciado se nos avisa que el "orgo" correspondiente nació en Whiston, supondremos que fala Inglés, y tiraremos del diccionario correspondiente:

#  apt-get install wbritish-insane
#  wc -l /usr/share/dict/british-english-insane
650656 /usr/share/dict/british-english-insane

Tenemos 650656 palabras para probar. Ahí es nada.

A continuación nos tenemos que currar algún programa que implemente el algoritmo del marinero:

Tome una palabra del fichero
Calcule el MD5 de dicha palabra
    Exprese el MD5 en hexadecimal, minúsculas (¡el MD5 son 16 octetos!)
Calcule el SHA1 del valor hexadecimal del paso anterior
¿Coincide con el valor con lo buscado? Pues si es que no, siguiente palabra. Y si es que sí, tenemos la palabra buscada.


En mi caso, el diccionario para la máquina Java estaba guardado en ~/temp. Ahí van la soluciones propuestas en Python, PHP (ya que así se planteaba en el reto) y JAVA.

El tiempo de ejecución en mi pc fue de 785 milisegundos para la versión Java, 1.1 segundos para PHP y de 2.12 segundos en Python; para obtener la clave 'hackster'. En qué andaría pensando el orgo para escoger esa contraseña ...

Python

#!/usr/bin/python
# Python 2.7.3

from hashlib import md5, sha1

with open("/usr/share/dict/british-english-insane", "rt") as f:
    for word in f.readlines():
        if sha1(md5(word.rstrip()).hexdigest()).hexdigest() == '77134aa1b02b61cd841d2a81bf64796a31234e28':
            print 'Your word is %s' % word
            exit

PHP

foreach (file("/usr/share/dict/british-english-insane", FILE_IGNORE_NEW_LINES) as $i => $palabra)
        if (sha1(md5($palabra)) == '77134aa1b02b61cd841d2a81bf64796a31234e28') {
                echo 'El password es '. $palabra ;
                break;
        }
?>

Java (hazte un café para mientras te lo lees y eso)

package org.euskal.hackit.passCrack;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException;
import java.nio.charset.Charset;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Hackit 2013 - Level 2 Cracker
 * 
 * @author cymo
 * 
 */

public class Crackit implements Runnable {

 /**
  * ; ?> 77134aa1b02b61cd841d2a81bf64796a31234e28
  * 
  * @param args
  */

 private static final int ERROR_LOADING_WORDLIST = 100;

 /**
  * Name of the dictionary to load & use
  */
 String dictName = "american-english-insane";

 /**
  * Words we are loading in memory as byte-arrays (faster to compare)
  */
 List<byte[]> wordList = new LinkedList<>();

 /**
  * The md5
  */
 MessageDigest md5;

 /**
  * The sha1
  */
 MessageDigest sha1;

 /**
  * Expected hash, as byte-array
  */
 byte[] expectedHash;

 /**
  * Constructor
  */
 Crackit() {
  String hash = "77134aa1b02b61cd841d2a81bf64796a31234e28"; // sha1(md5($password)

  expectedHash = new byte[hash.length() / 2];
  // Convert the hexstring-value to a bytearraybacked-value
  for (int i = 0; i < hash.length(); i += 2) {
   String strByte = "" + hash.charAt(i) + hash.charAt(i + 1);
   expectedHash[i / 2] = Integer.valueOf(strByte, 16).byteValue();
  }

 }

 public static void main(String[] args) {
  Crackit program = new Crackit();
  long initMillis = System.currentTimeMillis();
  program.run();
  System.out.println(String.format("Excecution took: %d milliseconds", System.currentTimeMillis() - initMillis));
 }

 @Override
 public void run() {
  try {
   // Load wordList
   loadWordList();
   // Create MessageDigests
   initDigests();
   // Iterate cracking
   iterateCracking();
  } catch (UnsupportedEncodingException e) {
   e.printStackTrace();
   System.exit(102);
  }

 }

 /**
  * Iterate over the dictionary, computing sha1(md5(word)) and comparing it
  * to the desired result
  * 
  * @throws UnsupportedEncodingException
  *             If your JVM is broken enough not to support ASCII encoding
  */
 private void iterateCracking() throws UnsupportedEncodingException {

  int i = 0;
  for (byte[] word : wordList) {
   if (i > 0 && i % 100 == 0)
    System.out.printf("Progress: %d of %d (%s)\n", i,
      wordList.size(), new String(word, "ASCII"));
   ++i;
   byte[] md5Bytes = md5.digest(word); // this is binary!
   byte[] md5AsHex = Conversion.byteArray2HexAsciiByteArray(md5Bytes);
   byte[] result = sha1.digest(md5AsHex); // get the sha1

   if (Arrays.equals(result, expectedHash)) {
    System.out.printf("The missing word is: %s\n", new String(word,
      "ASCII"));
    return;
   }
  }
  System.out.println("Password not found in dictionary :S");

 }

 /**
  * Create the message digests
  */
 protected void initDigests() {
  try {
   md5 = MessageDigest.getInstance("MD5");
   sha1 = MessageDigest.getInstance("SHA1");
  } catch (NoSuchAlgorithmException e) {
   e.printStackTrace();
   System.exit(101);
  }
  System.out.println("Message Digests Succesfully Created!");
 }

 /**
  * Loads a list of words from a file located at ~/temp
  */
 private void loadWordList() {
  String home = System.getProperty("user.home");
  String fileSeparator = System.getProperty("file.separator");
  String fileName = home + fileSeparator + "temp" + fileSeparator
    + dictName;
  try {
   BufferedReader br = new BufferedReader(new InputStreamReader(
     new FileInputStream(fileName), Charset.forName("ASCII")));
   String line = br.readLine();

   while (line != null) {
    // do not store the words as strings but as byte[]
    wordList.add(line.getBytes("ASCII")); 
    line = br.readLine();
   }
   br.close();
   System.out.printf("Wordlist of %d words, loaded\n", wordList.size());
  } catch (IOException e) {
   e.printStackTrace();
   System.exit(ERROR_LOADING_WORDLIST);
  }

 }

}

/**
 * Helper class to convert a binary-value backed by a byte[], to a hex-value
 * backed by another byte[]
 * 
 * @author cymo
 * 
 */
class Conversion {
 private static final int a_OFFSET = 'a' - 0x0a;
 /**
  * Helper variable for MD5s only!
  */
 private static byte[] resultHelper = new byte[32];
 
 /**
  * Thread UNSAFE method to convert a bin-value (byte[]) to a byte[] backed
  * asciihex value
/>
  * 
  * @param binaryArray
  *            The binary value to convert
  * @return The asciihex-value backed by a byte[]
  */
 static byte[] byteArray2HexAsciiByteArray(byte[] binaryArray) {

  int i = 0;
  for (byte b : binaryArray) {
   resultHelper[i] = (byte) ((b & 0xF0) >>> 4);
   resultHelper[i] += ((resultHelper[i++] <= 9) ? '0'
     : a_OFFSET);
   resultHelper[i] = (byte) (b & 0x0F);
   resultHelper[i] += ((resultHelper[i++] <= 9) ? '0'
     : a_OFFSET);
  }

  return resultHelper;
 }
}

Nos vemos (bueno, es un decir, lector inexistente) en la parte II donde explicaremos una vía alternativa a la DL para obtener las contraseñas de Maven.