Hackflash #6 : Extraire les mots d’un dictionnaire d’un binaire

Lors d'un challenge de forensics, il arrive souvent d'avoir à extraire des informations d'un dump de la mémoire, un gros fichier binaire.
Evidemment, il existe des outils pour cela, et le plus simple est sans doute d'utiliser un bon vieux grep -a. Toutefois, il peut être nécessaire d'avoir le faire soi-même.
Extraire le mots d'un dictionnaire d'un binaire en Python 3
La solution la plus simple est alors encore de rédiger un programme en Python.
Le programme suivant recherche les occurences des mots d'un dictionnaire dans un binaire.
Le dictionnaire est un bête fichier texte qui comprend un mot par ligne, comme par exemple :
poire
bananne
fraise
...
Le fichier binaire est lu bloc par bloc pour ne pas encombrer la mémoire s'il est volumineux. La taille d'un bloc, BLOCK_SIZE, est ajustable, pourvu qu'elle soit supérieure ou égale à la longueur du plus long des mots plus 2.
Un mot est repéré dans le fichier binaire en partant du principe qu'il est précédé (sauf au début de fichier) et suivi (sauf à la fin du fichier) d'un caractère qui n'est pas utilisé dans le dictionnaire, en l'espèce tout caractère [^a-zA-Z0-9], mais c'est ajustable.
BLOCK_SIZE = 10 * 1024 * 1024	# Supposé au moins égal à la longueur du plus long des mots
FILE_DUMP = 'ch37.raw'
FILE_WORDS = 'bip39.txt'
FILE_WORDS_UNSORTED = 'strings_results.txt'

data = bytearray ()
f = open (FILE_WORDS, 'rt')
words = f.read ().split ('\n')
f.close ()
words = [ w.encode ('utf-8') for w in words if len (w) != 0 ]	# Test pour éviter des emmerdes avec une dernière ligne vide
lenMin = min (map (len, words))
lenMax = max (map (len, words))
f = open (FILE_DUMP, 'rb')
filesize = f.seek (-1, 2) + 1
f.seek (0)
# L'idée est de rechercher un mot dans une plage, et chaque fois qu'une occurence est trouvée, de vérifier que l'octat qui le précède et celui qui le suit correspondent à des séparateurs (un octet différent de [0-9a-zA-Z] pour s'assurer que le mot, et seulement le mot, a été trouvé. Pour éviter des tests dans la boucle de recherche d'un mot, il faut s'assurer qu'en toutes circonstances, la plage courante débute et se termine par des octets qui sont exclus de la recherche : un octet initial qui sera testé comme séparateur si jamais la plage commence par un mot (à partir donc de son deuxième octet) ; un octet final qui sera testé comme séparateur si jamais la plage se termine par un mot (jusqu'à donc son avant-dernier octet).
data = bytearray ([0xff])	# Commencer par un octet qui n'est pas un goodChars
result = { w:[] for w in words }
offset = 0
goodChars = [ b for b in range (ord ('0'), ord ('9') + 1) ]
goodChars.extend ([ b for b in range (ord ('A'), ord ('Z') + 1) ])
goodChars.extend ([ b for b in range (ord ('a'), ord ('z') + 1) ])
print ('Searching for words...')
while True:
	block = f.read (BLOCK_SIZE)
	# Ce test, car le suivant seul ne suffit pas, occasionant une boucle infinie si len (data) >= lenMin en fin de fichier, car data[len (data) - lenMax + 1 - 1 - 1:] reste égal à data[len (data) - lenMax + 1 - 1 - 1:] puisque len (data) == lenMax - 1 + 1 + 1 et donc que data[len (data) - lenMax + 1 - 1 - 1:] == data[0:]
	if len (block) == 0:
		break
	# Tester s'il reste assez de données pour trouver le plus petit mot en entier
	if (len (data) + len (block)) < lenMin:
		break
	data.extend (block)
	# Si le bloc est le dernier, terminer la plage par un octet qui n'est pas un goodChars
	if f.tell () == filesize:
		data.append (0xff)
	print (f'\r[{offset}:{offset + len (block)}]', end='')
	# Ce qui suit est l'équivalent de la recherche de [^<goodChars>]<mot>[^<goodChars>] dans la plage. On s'assure que le préfixe et le suffixe existent toujours, c'est-à-dire même si la plage commence et/ou se termine par <mot>, en préfixant et en suffixant le fichier d'un [^goodChars], en l'occurence 0xff. Le gâchis dans cette boucle, c'est qu'à chaque mot, on reteste des parties de la plage où l'on a déjà trouvé des mots...
	for w in words:
#			print (f'\r[{offset}:{offset + len (block)}] {w.decode ("utf-8")}', end='')
		o = 1
		# Rechercher le mot à partir du deuxième octet de la plage, le premier étant le dernier du bloc précédent, ou 0xff (ie : pas un goodChars) dans le cas du premier bloc
		# Cela dispense de vérifier que data[o - 1] existe (ie : (o - 1) != -1) dans la boucle
		# De même, ne rechercher le mot que jusqu'à l'avant-dernier octet de la plage, le dernier étant le premier du bloc suivant, ou 0xff (ie : pas un goodChars) dans le cas du dernier bloc
		# Cela dispense de vérifier que data[o + len (w)] existe (ie : (o + len (w)) != len (data)) dans la boucle
		while (o := data.find (w, o, -1)) != -1:
			# Ce test préserve d'un recouvrement, car s'il y avait recouvrement, l'un ou l'autre des octets testés serait un goodChars
			if (data[o - 1] not in goodChars) and (data[o + len (w)] not in goodChars):
				# Stocker l'indice en excluant le 0xff qui a été préfixé au premier bloc
				result[w].append (offset + o - 1)
			o = o + 1
	# Reprendre la recherche en présumant qu'au mieux la plage courante (moins son dernier octet qui n'a pas été impliqué dans les recherches, sinon pour tester si c'est séparateur) pourrait se terminer par le mot le plus long, de longueur N, amputé de son dernier caractère (qui pourrait donc être ce dernier octet de la plage courante), si bien qu'il faut commencer la prochaine plage par les N - 1 derniers de la plage courante, plus le dernier octet de cette plage, bref les N derniers octets de la plage courante. Par ailleurs, il faut que la nouvelle plage débute par un octet qui ne sera pas impliqué dans les recherches, mais testé pour voir si c'est un séparateur. Bref, il faut que la nouvelle plage débute par les N + 1 derniers octets de la plage courante.
	# La difficulté, c'est qu'en reprenant ainsi la recherche sur une partie de la plage où elle a déjà été conduite, on risque de trouver des mots qu'elle contient, qui ont déjà été trouvés. Par exemple, si la plage se termine par " x ab" (elle s'est donc terminée au "a" inclus), et que le dictionnaire contient "x" et "abcd", alors la recherche a permis de trouver le "x", et elle reprend dans une plage qui débute par " x ab" (à partir donc du "x"), si bien que le "x" va être trouvé de nouveau. Ces cas devant être tout de même rares, le moins exigeant en temps de calcul (à vrai dire, il serait possible d'utiliser un set plutôt qu'une liste pour la liste des offsets, car un set ne peut pas contenir de doublons si bien que tout appel à .add () entraîne une vérification, mais bon...) est de purger la liste des offsets des occurences de chaque mot à la fin, pour s'assurer qu'un offset n'y apparaît qu'une fois, plutôt que de rajouter un test sur la présence d'un offset dans cette liste chaque fois qu'une occurence est trouvée 
	offset = offset + len (data) - lenMax + 1 - 1 - 1
	data = data[len (data) - lenMax + 1 - 1 - 1:]
f.close ()
# Purger la liste des offsets de chaque mot de ses doublons pour la raison expliquée plus tôt. En profiter pour générer le résultat. Passer par la génération d'un set est incomparablement plus rapide qu'une boucle...
print ('\nRemoving duplicates...')
result = { w:set (result[w]) for w in result }
print ('\nDumping results...')
f = open (FILE_WORDS_UNSORTED, 'wt')
data = ''.join ([ f'{w.decode ("utf-8")}\t{o}\n' for w in result for o in result[w] ])
data = data[:-1]	# Pour éviter une ligne vide à la fin
f.write (data)
f.close ()
print ('Done!')
Hackflash #6 : Extraire les mots d’un dictionnaire d’un binaire