Oracle Coherence et Rainbow table

9 août 2010 Olivier Bourgain Aucun commentaire

Dans cet article nous verrons comment utiliser Oracle Coherence pour retrouver les mots de passe ayant servi à générer des hash.
Deux approches naïves sont envisageables pour cracker un hash : la force brute et la base de données. La première consiste à essayer toutes les combinaisons possibles de mots de passe, mais le problème est le temps de calcul nécessaire, car les fonctions de hashage sont généralement très lentes. La seconde consiste à calculer en amont les hashs de toutes les mots de passe possible, et à les stocker dans une base de données ; mais cette attaque nécessite un espace de stockage énorme.
Les Rainbow tables sont conçues pour optimiser l’équilibre entre puissance de calcul et la consommation mémoire, à mi-chemin entre les deux approches précédentes.

Rainbow table

Une Rainbow table est une variante de la Map classique, dont les clés sont les hashs et les valeurs les mots de passe correspondants. La subtilité est que le hash n’est pas directement obtenu par digestion du mot de passe, mais après l’application successive de fonctions de digestion et de réduction. L’opération de réduction permet de générer, à partir d’un hash, une nouvelle chaîne de caractère appartenant à l’ensemble des mots de passe potentiels (sur laquelle on pourra à nouveau appliquer un hash, etc.).

A partir d’un mot de passe potentiel initial, si l’on applique N fois (1000, par exemple) les fonctions de hashage et de réduction, on obtient un hash final représentant de manière unique le trajet passant par N-1 mots de passe et hashs intermédiaires. Grâce à ce système, une Rainbow table de 1 Mo couvre l’équivalent d’1 Go de données.
Malheureusement, il est possible d’obtenir des collisions, car la réduction de deux hashs différents peut mener à la même chaîne de caractères. Pour éviter ce phénomène, il est fortement recommandé d’utiliser une fonction de réduction différente par colonne virtuelle de la table. Les collisions sont ainsi beaucoup plus rares, puisqu’il faudrait que les deux hashs conflictuels appartiennent à la même colonne – ce qui a N fois moins de chances de se produire (1000 fois moins, toujours dans notre exemple).
Pour cracker un hash (et donc retrouver le mot de passe l’ayant produit), la première étape consiste à déterminer la ligne de la table à laquelle il appartient. Pour cela, on commence par vérifier si le hash correspond directement à un hash final de la Rainbow table.

Si oui, le mot de passe recherché est celui produit par l’opération de réduction à l’étape N-1 (999) de notre chemin virtuel sur cette ligne, et il n’y a plus qu’à le recalculer comme expliqué plus bas.
Si non, peut-être le mot de passe recherché est-il dans la colonne N-2 ? Si c’est le cas, l’application des fonctions de hashage+réduction de l’étape N-1 devrait produire le hash final de la ligne, que nous connaissons. En appliquant ce raisonnement récursivement jusqu’à l’étape 1, on peut facilement vérifier tous les éléments virtuels de toutes les lignes de notre Rainbow table.

Une fois déterminée la ligne contenant le mot de passe, il suffit de la parcourir à partir de son mot de passe initial. En appliquant à chaque élément de la liste la fonctions de hashage ou de réduction appropriée, on arrive au mot de passe intermédiaire produisant le hash que l’on cherche à cracker.
Évidement, si le hash a été produit en appliquant un sel (salt), la rainbow table va donner le mot de passe salé et pas le mot de passe initial…
Dans ce cas, notre chaîne ne va stocker que df45cvj11sag en clé et password en valeur, toutes les valeurs intermédiaires peuvent êtres retrouvées en effectuant à nouveau les étapes de hashage et de réduction à partir de la valeur initiale, celle stockée dans la table.

Coherence

Après avoir brièvement présenté le fonctionnement des Rainbow tables, intéressons-nous à Coherence, une solution de cache distribué que nous utiliserons pour stocker la table.
Coherence s’utilise comme une Map normale, et pour créer un cluster il suffit d’importer le jar de Coherence (disponible ici) et d’obtenir une référence sur un cache. La création du cache s’il n’existe pas et sa mise en cluster se font automatiquement.
On va donc effectuer un simple :

NamedCache rainbow = CacheFactory.getCache(“rainbow”);

Et on obtient un NamedCache, implémente l’interface Map et se manipule donc comme tel.
Pour générer la rainbow table, nous allons comme expliqué plus haut enchaîner des digestions puis des réductions sur la chaîne de départ. Le code ressemble donc à :

public void create(Tools tools) {
for (int j = 0; settings.getTableSize(); j++) {
String password = randomPassword(settings.getPasswordLength(),settings.getCharacterSet()); // create a random password
String finalHash = finalHash(tools, password); // Hash and reduce it a lot a time
rainbow.put(finalHash, password); // Store the initial password and the final hash
}
}
private String finalHash(Tools tools, String password) {
int passwordLength = settings.getPasswordLength();
String characterSet = settings.getCharacterSet();
String hash = tools.hash(password);
for (int i = 0; i < settings.getChainLength() – 1; i++) {
String intermediatePassword = tools.reduce(hash.getBytes(), i,characterSet, passwordLength);
hash = tools.hash(intermediatePassword);
< div style=”font-family: monospace; font-weight: normal; font-style: normal; margin:0; padding:0; background:inherit;”> }
return hash;
}

Cette façon de faire n’est pas optimale du point de vue du réseau puisque l’opération “put” va déclencher deux appels réseau, un pour enregistrer la nouvelle entrée, et un autre pour renvoyer l’ancienne valeur (ou null si elle est créée). On va donc utiliser une Map locale pour servir de buffer :

public void create(Tools tools) {
Map<String, String> map = new HashMap<String, String>();
for (int i = 0; i < settings.getTableSize() / 1000; i++) {
for (int j = 0; j < 1000; j++) {
// create a random password
String password = randomPassword(settings.getPasswordLength(),settings.getCharacterSet());
// Hash and reduce it a lot a time
String finalHash = finalHash(tools, password);
// Store the initial password and the final hash
map.put(finalHash, password);
}
// store objects by 1000 to improve network performance
rainbow.putAll(map);
map.clear();
}
}

Ainsi, les entrées sont stockées par 1000, ce qui réduit le nombre d’appels réseau, de plus il n’y a pas de retour à la fonction putAll, ce qui réduit 2000 appels réseau à un seul.
Une fois notre table créée, on peut commencer à cracker les hash.

public String crack(String hash) {
byte[] hashToCrack = hash.getBytes();
for (int i = settings.getChainLength() – 1; i >= 0; i–) {
byte[] finalHash = finalHash(hashToCrack, i);
for (Object key : rainbow.keySet()) {
if (key.toString().equals(new String(finalHash))) {
// the hash matches a key in the table, the password may be in this row
String password = findPasswordInRow(key.toString(),new String(hashToCrack));
if (password != null) {
// we found the password
return password;
} else {
// hash collision ?
}
}
}
}
// Not found
return null;
}
private String findPasswordInRow(~~String key, String hashToCrack) {~~
String password = (String) CacheFactory.getCache(cacheName).get(key);
for (int j = 0; j <= settings.getChainLength(); j++) {
String hash = tools.hash(password);
if (hash.equals(hashToCrack)) {
System.out.println(“got it”);
return password;
}
password = tools.reduce(hash.getBytes(), j, settings.getCharacterSet(), settings.getPasswordLength());
}
// hash not found
return null;
}
private byte[] finalHash(byte[] hash, int index) {
for (int i = index; i < settings.getChainLength() – 1; i++) {
String password = tools.reduce(hash, i, settings.getCharacterSet(),settings.getPasswordLength());
hash = tools.hash(password).getBytes();
}
return hash;
}

Pour vérifier que notre méthode “crack” fonctionne correctement, ajoutons manuellement l’entrée qui doit donner le bon résultat :

public void createWithKnowPassword(Tools tools, String password) {
// Hash and reduce it a lot a time
String finalHash = finalHash(tools, password);
// Store the password and the final hash
rainbow.put(finalHash, password);
System.out.println(“hash final de “ + password + ” = “ + finalHash);
}

En utilisant “olivier” comme mot de passe initial, on obtient le hash bc481f4a213cb8442d6c38a17d58de43. On peut donc vérifier que le vrai hash de “olivier” (d3ca5dde60f88db606021eeba2499c02) permet de retrouver “olivier“.

Conclusion

Nous avons vu que la Rainbow table permet d’optimiser l’équilibre entre espace de stockage et puissance de calcul. Coherence permet ensuite de la manipuler de façon transparente, et même de la partager entre plusieurs applications. La facilité avec laquelle il est possible de cracker des mots de passe grâce aux Rainbow tables souligne l’importance d’utiliser un algorithme de cryptage sûr et d’utiliser un salt sur les mots de passe.
Dans le prochain article, nous verrons comment paralléliser les traitements sur les nœuds du cluster.
Références :
wikipedia
coding horror