Parallel brute force

Parallel brute force is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Find, through brute force, the five-letter passwords corresponding with the following SHA256 hashes:

1. 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad
2. 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b
3. 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f

Your program should naively iterate through all possible passwords consisting only of five lower-case ASCII English letters. It should use concurrent or parallel processing, if your language supports that feature. You may calculate SHA256 hashes by calling a library or through a custom implementation. Print each matching password, along with its SHA256 value. Optionally, measure how long your program takes to run, and print that time.

C#

  <lang csharp>using System; using System.Linq; using System.Security.Cryptography; using System.Text; using System.Threading.Tasks;

class Program {

   static void Main(string[] args)
   {
       byte[] one = StringHashToByteArray("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad");
       byte[] two = StringHashToByteArray("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b");
       byte[] three = StringHashToByteArray("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f");
       var prey = new byte[][] { one, two, three };
       var dt = DateTime.Now;
       int chunksize = 26 * 26 * 26 * 26 * 26 / Environment.ProcessorCount;
       Task[] tasks = (
                       from i in Enumerable.Range(0, Environment.ProcessorCount)
                       select Task.Run(() => MatchesInRange(i * chunksize, (i + 1) * chunksize - 1, prey))
                     ).ToArray();
       Task.WaitAll(tasks);
       Console.WriteLine((DateTime.Now - dt).TotalMilliseconds + " milliseconds elapsed.");
   }
   static byte[] StringHashToByteArray(string s)
   {
       return Enumerable.Range(0, s.Length / 2).Select(i => (byte)Convert.ToInt16(s.Substring(i * 2, 2), 16)).ToArray();
   }

   static void MatchesInRange(int start, int stop, byte[][] prey)
   {
       byte[] letters = new byte[5];
       byte[] hash;
       int serial;
       var shaFactory = new SHA256Managed();
       for (int seriali = start; seriali <= stop; seriali++)
       {
           serial = seriali;
           int divisor = 456976; // 26 * 26 * 26 * 26;
           for (int i = 0; i < 5; i++)
           {
               letters[i] = (byte)(97 + Math.DivRem(serial, divisor, out serial));
               divisor /= 26;
           }
           hash = shaFactory.ComputeHash(letters);
           if (hash[0] == prey[0][0] || hash[0] == prey[1][0] || hash[0] == prey[2][0])
           {
               if (Enumerable.SequenceEqual(hash, prey[0]) || Enumerable.SequenceEqual(hash, prey[1]) || Enumerable.SequenceEqual(hash, prey[2]))
               {
                   Console.WriteLine(Encoding.ASCII.GetString(letters) + " => " + BitConverter.ToString(hash).ToLower().Replace("-", ""));
               }
           }
       }
   }

}</lang>

Output:

apple => 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b
mmmmm => 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f
zyzzx => 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad

Python

<lang python>import multiprocessing from hashlib import sha256

def HashFromSerial(serial):

   divisor = 456976
   letters = []
   for i in range(5):
       letter, serial = divmod(serial, divisor)
       letters.append( 97 + int(letter) )
       divisor /= 26
   return (letters, sha256(bytes(letters)).digest())

def main():

   h1 = bytes().fromhex("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad")
   h2 = bytes().fromhex("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b")
   h3 = bytes().fromhex("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f")
   numpasswords = int(26 ** 5)
   chunksize = int(numpasswords / multiprocessing.cpu_count())
   with multiprocessing.Pool() as p:
       for (letters, digest) in p.imap_unordered(HashFromSerial, range(numpasswords), chunksize):
           if digest == h1 or digest == h2 or digest == h3:
               password = "".join(chr(x) for x in letters)
               print(password + " => " + digest.hex())

if __name__ == "__main__":

   main()</lang>

Output:

apple => 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b
mmmmm => 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f
zyzzx => 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad

zkl

The built in thread message passing object uses the OS to do the heavy lifting and, as a result, isn't suited to high through put (ie passing passwords to cracking threads, equally distributing passwords to each cracking thread). Instead, each thread gets a range of passwords to crack and use signals to coordinate. Way more code with the drawback that one thread may have to do all the work.

Linux scheduling is strange, the fastest number of threads isn't the number of cores available and the app seems to be throttled.

This was run on a Intel i7 4 core 8 thread Linux box.

Uses the message hashing extension library (DLL).

Translation of: C#

<lang zkl>var [const] MsgHash=Import.lib("zklMsgHash"); var [const] gotEm=Atomic.Int(); // global signal for all threads

const THREADS=6, NUM=26/THREADS, CHR_a="a".toAsc(); // how we will split task

fcn crack(c,hashes){ // thread

  sha256,bytes := MsgHash.SHA256, Data(); // the SHA-256 hash method, byte bucket
  firstLetters:=(c+CHR_a).walker((c+NUM-1).min(25)+CHR_a);
  letters:=CHR_a.walker;	// iterator starting at 97/"a"
  foreach a,b,c,d,e in (firstLetters,letters(26),letters(26),letters(26),letters(26)){ 
     bytes.clear(a,b,c,d,e);   // recycle Data, faster than creating Strings
     hash:=sha256(bytes);
     if(hashes.holds(hash)){
        println(bytes.text," --> ",hash);

gotEm.dec(); // I cracked one, let mom thread know

     }
  }

}</lang> <lang zkl>hashes:=T("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b",

         "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f",

"1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"); gotEm.set(hashes.len()); // number of codes to crack foreach n in ([0..25,NUM]){ crack.launch(n,hashes) } // start threads gotEm.waitFor(0); // wait util all cracked, just exit, OS kills threads</lang>

mmmmm --> 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f
apple --> 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b
zyzzx --> 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad

real	0m8.496s
user	0m35.804s
sys	0m0.252s