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 SHA-256 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.

Related task: SHA-256

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

Perl 6

This solution can be changed from parallel to serial by removing the .race method. <lang perl6>use Digest::SHA;

constant @alpha2 = [X~] <a m z>,

; constant @alpha3 = [X~] <m p z>, <l m z>, <e m x>; my %WANTED = set < 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad >; sub find_it ( $first_two ) { return gather for $first_two «~« @alpha3 -> $password { my $digest_hex = sha256($password).list.fmt('%02x', ); take "$password => $digest_hex" if %WANTED{$digest_hex}; } } .say for flat @alpha2.race.map: &find_it; </lang>

Output:

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

Testers can adjust the run speed by replacing the @alpha constants with any of the below: <lang perl6>

1. True to actual RC task, but slowest

constant @alpha2 = 'aa' .. 'zz'; constant @alpha3 = 'aaa' .. 'zzz';

1. Reduced alphabets for speed during development

constant @alpha2 = [X~] <a m p y z> xx 2; constant @alpha3 = [X~] <e l m p x z> xx 3;

1. Alphabets reduced by position for even more speed

constant @alpha2 = [X~] <a m z>,

; constant @alpha3 = [X~] <m p z>, <l m z>, <e m x>;

1. Completely cheating

constant @alpha2 = <ap mm zy>; constant @alpha3 = <ple mmm zzx>;</lang>

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.

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=9, // how we will split task, THREADS<=26

     CHR_a="a".toAsc();

fcn crack(c,n,hashes){ // thread

  sha256:=MsgHash.SHA256; // the SHA-256 hash method, byte bucket
  bytes,hash := Data(),Data().howza(0); // byte buckets to reduce garbage production
  firstLtrs:=(c+CHR_a).walker(n);
  ltrs:=CHR_a.walker;	// iterator starting at 97/"a"
  foreach a,b,c,d,e in (firstLtrs,ltrs(26),ltrs(26),ltrs(26),ltrs(26)){ 
     if(not hashes2go) return(); // all cracked, stop, not really needed
     bytes.clear(a,b,c,d,e);     // recycle Data, faster than creating Strings
     sha256(bytes,1,hash);	  // put hash in hash
     if(hashes.holds(hash)){
        println(bytes.text," --> ",hash.pump(String,"%02x".fmt));

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

     }
  }

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

         "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f",

"1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"); // convert hex strings to binary; cuts down conversions during crack fcn hex2binary(s){ s.pump(Data,Void.Read,fcn(a,b){ (a+b).toInt(16) }) } hashes:=hashes.apply(hex2binary);

hashes2go.set(hashes.len()); // number of codes to crack num,xtra := 26/THREADS, 26%THREADS; // try for the most even spread over threads s:=0; do(THREADS){ // start threads

  n:=num + ((xtra-=1)>=0); 
  crack.launch(s.toInt(),n,hashes); 
  s+=n;

} hashes2go.waitFor(0); // wait until all cracked, just exit, OS kills threads</lang>

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

real	0m3.261s
user	0m22.160s
sys	0m0.140s