Algorithm for creating a huge list of words

Question

Well, I know that it will sound bad, as if I'm going to use it for unethical things, but you have my word that I do not know.

I am writing a document for my course on computer and information security, and the topic that I have chosen is hashing methods. One of the points that I look at in my article is MD5, only one-sided, and the only way to crack the MD5 hash is to continuously create strings and use the MD5 function, and then compare it with the hash you want to crack.

I would like to create a really simple mock-up program that will be shown along with my article (we are making a presentation, and that would be great), so I would like to develop an algorithm that makes a line with each possible combination of characters up to 8 characters. For example, the output would be:

a, b, c, ..., aa, ab, ac, ... ba, bb, bc, etc. etc. etc.

It should include letters, numbers and symbols, if possible.

I partially used this algorithm, but, unfortunately, my programming skills do not fit the task. If someone can provide a complete algorithm for this, I would be very grateful.

Again, if you think I'm a liar, and I'm going to use it to hack, you do not need to leave an answer.

Thanks.:)

Answer 1

In Python, itertools.product does almost everything you need, although it does it in just one “number of repetitions,” so you have to iterate from 1 to 8 (not difficult ;-). Essentially:

import itertools import string # whatever you wish as alphabet (lower/upper, digits, punct, &c) myalphabet = string.ascii_lowercase + string.ascii_digits def prods(maxlen, alphabet=myalphabet): for i in range(1, maxlen+1): for s in itertools.product(alphabet, repeat=i): yield ''.join(s) 

Of course, for an alphabet of long N and K repetitions (8 in your case) this gives N + N ^ 2 + ... + N ^ K possibilities (2 901 713 047 668 possibilities for N = 36 and K = 8), but, that several trillion exits among friends! -)

Answer 2

To implement this, I would probably encode integers into base 36 (or more if you wanted characters).

1 = 1 2 = 2 ... a = 10 b = 12 ..

etc.

then you will have a number, for example 38, and do some divisions, that is:

38/36 = 1 remaider 2 = 12 in the base 36

then just run the for loop for your maximum number that you want to encode, something very large and print your encoded numbers.

just for fun i wrote this for you: http://pastebin.antiyes.com/index.php?id=327

Answer 3

It’s not true that the “only way to crack the MD5 hash” is to generate every possible line and look for collisions. In fact, if you have access to the original, it can be modified so that its MD5 matches what another file can create. This is described in the document at infosec.edu .

Even if you cannot modify the source file, there are rainbow MD5 checksum tables that can be used to generate collisions.

These facts make MD5 unsuitable for passwords or cryptography, and in fact the US government has banned its further use for secure applications.

Answer 4

If you already have access to the hashed version of the password, MD5 is broken to start with . However, when it comes to hashing, you will probably be better off using Rainbow Tables , Attack Dictionary, and Social Engineering using your brute force method. However, since you asked the algorithm to generate all the values, perhaps the following will be useful (C #):

 using System; using System.Text; namespace PossibiltyIterator { class Program { static readonly char[] Symbols = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '_', '+', '=', '/', '\\', '[', ']', '{', '}', ';', ':', '\'', '"', ',', '.', '<', '>', '?', '`', '~' }; const int MaxLength = 8; static void BuildWord(int currentLength, int desiredLength, char[] word) { if (currentLength == desiredLength) { Console.WriteLine(word); } else { for (int value = 0; value < Symbols.Length; ++value) { word[currentLength] = Symbols[value]; BuildWord(currentLength + 1, desiredLength, word); } } } static void Main(String[] args) { double totalValues = (Math.Pow(Symbols.Length, MaxLength + 1) - Symbols.Length)/(Symbols.Length - 1); Console.WriteLine("Warning! You are about to print: {0} values", totalValues); Console.WriteLine("Press any key to continue..."); Console.ReadKey(true /* intercept */); for (int desiredLength = 1; desiredLength <= MaxLength; ++desiredLength) { BuildWord(0 /* currentLength */, desiredLength, new char[MaxLength]); } } } } 

To be completely honest, this can be further optimized. Since he builds all the “words” of length 1, this works the second time when building words of length 2. It would be wiser to build words of length MaxLength, and then truncate one letter to build the word MaxLength-1.

Here is the optimized version ... note that it does NOT return words in the originally requested order.

 using System; using System.Text; namespace PossibiltyIterator { class Program { static readonly char[] Symbols = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '_', '+', '=', '/', '\\', '[', ']', '{', '}', ';', ':', '\'', '"', ',', '.', '<', '>', '?', '`', '~' }; const int MaxLength = 8; static void BuildWord(int currentLength, int desiredLength, char[] word) { if (currentLength != desiredLength) { for (int value = 0; value < Symbols.Length; ++value) { word[currentLength] = Symbols[value]; BuildWord(currentLength + 1, desiredLength, word); } word[currentLength] = '\0'; } Console.WriteLine(word); } static void Main(String[] args) { double totalValues = (Math.Pow(Symbols.Length, MaxLength + 1) - Symbols.Length)/(Symbols.Length - 1); char[] word = new char[MaxLength]; Console.WriteLine("Warning! You are about to print: {0} values", totalValues); Console.WriteLine("Press any key to continue..."); Console.ReadKey(true /* intercept */); BuildWord(0 /* currentLength */, MaxLength, new char[MaxLength]); } } } 

Answer 5

To fill out a message with a Java example that will output Base64-encoded MD64 of all possible character combinations using only characters 0-9 and az:

 MessageDigest digest = MessageDigest.getInstance("MD5"); int i = 0; while (true) { String raw = Integer.toString(i, Character.MAX_RADIX); byte[] md5 = digest.digest(raw.getBytes()); String base64 = new BigInteger(1, md5).toString(16); System.out.println(raw + " = " + base64); i++; }