Me demore un poquito con la publicacion de este problema del coding contest, pero aca esta. Fue el problema que mas me motivo cuando lei de que trataba. Es un problema sobre criptografia y seguridad informatica. Veamos de que trata:

Enunciado

Dennis fue uno de los diseñadores del sistema UNIX junto a Ken. Lamentablemente falleció en 2011, en la misma semana que Steve Jobs. El otro funeral se llevó toda la atención, pero su amigo Ken pudo recuperar las líneas del archivo /etc/shadow correspondientes al usuario dennis de tres sistemas de diferentes épocas:

dennis:ox45K6RsEUfmQ:
dennis:$1$42dJ1xYh$MfrRke8/Ej3h5.vMtNEhC.:
dennis:$6$SZGpKoPi$GGGqHYKy6PO/H5nvV0AmaGB/5krnxVuz2k2uX81O.CF5nYctE5RlR/rzJQCL3ZsF8yratCRbSR2ZuwKzvve.D0:
Dennis siempre usaba letras minúsculas para sus passwords, y éstos nunca tenían más de seis caracteres.

 - ¿Cómo se llamaba el perro de Dennis?
 - ¿Cuál era su color favorito?
 - ¿De qué equipo era hincha?

Resolucion

Hay que saber que existen varios archivos importantes en un sistema Linux, que almacenan información referente a los usuarios y al sistema.

Dos archivos importantes son /etc/passwd y /etc/shadow. Inicialmente las contraseñas de los usuarios eran almacenadas en el archivo /etc/passwd, pero esto suponia un riesgo ya que dicho archivo podia ser accedido por cualquier usuario. Posteriormente para mejorar la seguridad lo que se hizo fue almacenar los hash de las contraseñas en el archivo /etc/shadow al cual solo pueda tener acceso el usuario root, quedando en el archivo /etc/passwd informacion del usuario como nombre completo, username, directorio home, entre algunos otros mas.

Generalmente en cualquier sistema informático medianamente seguro, la contraseña no se almacena en texto plano sino que se hashea, es decir se le aplica alguna funcion de hash y se guarda el hash resultante. Posteriormente lo que se hace para realizar el logeo, es cuando el usuario se logea, se le aplica la misma funcion de hash al password que ingresa, y se comparan ambos hash, en caso de ser correcto el login es satisfactorio.

Analizando una de las lineas del archivo /etc/shadow se observa:

dennis:$1$42dJ1xYh$MfrRke8/Ej3h5.vMtNEhC.:
   |    |      |           |
 user  id     salt       hash

Cada linea representa al usuario, en este caso dennis, y una cadena que contiene la informacion del password. Esta cadena esta compuesta de varios campos que se encuentran separados por “$”. Estos campos representan:

• id : es el identificador de la funcion hash utilizada

• salt : es un dato aleatorio que se agrega a la funcion de hash, disminuyendo la efectividad de los ataques por diccionario lo que aumenta la seguridad.

• hash : es el hash resultante de la contraseña y el salt.

Mirando el fichero del problema

dennis:ox45K6RsEUfmQ:
dennis:$1$42dJ1xYh$MfrRke8/Ej3h5.vMtNEhC.:
dennis:$6$SZGpKoPi$GGGqHYKy6PO/H5nvV0AmaGB/5krnxVuz2k2uX81O.CF5nYctE5RlR/rzJQCL3ZsF8yratCRbSR2ZuwKzvve.D0:

En el primer caso se uso DES, en el segundo MD5, y en el ultimo SHA-512.

Conociendo el algoritmo utilizado y el salt se va a empezar por un ataque de diccionario y en caso de no encontrar la solucion se pasa a un ataque por fuerza bruta. En el caso del ataque por diccionario, primero se usara un diccionario que contiene los passwords mas utilizados, obtenido de Jhon the Ripper, y el segundo diccionario a probar, es el archivo de words comunes presente en el sistema Debian(generalmente es un diccionario de palabras americanas).

La generación de los hashes se realiza con la libreria crypt de python, que es una implementacion de la utilidad de sistema crypt().

Una particularidad del problema es que las contraseñas son todas en minúsculas y no tienen mas de 6 caracteres. Por lo que las palabras del diccionario se pasaran todas a minusculas y se evitan las que superen la longitud máxima.

El script resultante que propusé es:

Ejecucion del Script

El script utilizado esta programado en Python 2.7 y hace uso de las librerias crypt, sys y time. De la siguiente forma se invoca al script:

$ python getpass.py shadowfile

Donde shadowfile el archivo shadow con las contraseñas. Para este caso seria

$ python getpass.py shadowfile

El programa lee linea por linea el archivo y pregunta para que password se quiere realizar el crackeo.

El resultado es:

Se va intentar crackear 3 hashes con una longitud maxima por password de 6
Se va a realizar ataque por diccionario
Se usa el diccionario john.txt
El password para $6$SZGpKoPi$GGGqHYKy6PO/H5nvV0AmaGB/5krnxVuz2k2uX81O.CF5nYctE5RlR/rzJQCL3ZsF8yratCRbSR2ZuwKzvve.D0 es knicks
Enlapsed time:  2.76981282234
El password para $1$42dJ1xYh$MfrRke8/Ej3h5.vMtNEhC. es white
Enlapsed time:  3.18808293343
Se usa el diccionario /etc/dictionaries-common/words
El password para ox45K6RsEUfmQ es fido
Enlapsed time:  3.28093099594

El perro de Dennis se llamaba fido. Su color favorito era el blanco, y era incha de los Knicks. Un detalle es que la palabra “fido” la tomo del diccionario, pero en el mismo se contraba escrito “Fido” con la f mayuscala, si no hubiera pasado las letras a minusculas, se huviera usado la generacion de palabras, y hubiera sido mucho mas lento. El en caso del ataque de fuerza bruta, la generacion de las palabras no es eficiente, habria que buscar alguna forma de mejorarla. Una particularidad