Parallel brute force
You are encouraged to solve this task according to the task description, using any language you may know.
- 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 SHA-256 hashes by calling a library or through a custom implementation. Print each matching password, along with its SHA-256 hash.
Related task: SHA-256
C#
<lang csharp>using System; using System.Linq; using System.Text; using System.Threading.Tasks;
class Program {
static void Main(string[] args)
{
Parallel.For(0, 26, a => {
byte[] password = new byte[5];
byte[] hash;
byte[] one = StringHashToByteArray("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad");
byte[] two = StringHashToByteArray("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b");
byte[] three = StringHashToByteArray("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f");
password[0] = (byte)(97 + a);
var sha = System.Security.Cryptography.SHA256.Create();
for (password[1] = 97; password[1] < 123; password[1]++)
for (password[2] = 97; password[2] < 123; password[2]++)
for (password[3] = 97; password[3] < 123; password[3]++)
for (password[4] = 97; password[4] < 123; password[4]++)
{
hash = sha.ComputeHash(password);
if (matches(one, hash) || matches(two, hash) || matches(three, hash))
Console.WriteLine(Encoding.ASCII.GetString(password) + " => "
+ BitConverter.ToString(hash).ToLower().Replace("-", ""));
}
});
}
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 bool matches(byte[] a, byte[] b)
{
for (int i = 0; i < 32; i++)
if (a[i] != b[i])
return false;
return true;
}
}</lang>
- Output:
apple => 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b mmmmm => 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f zyzzx => 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad
Common Lisp
<lang lisp>(defpackage #:parallel-brute-force
(:use #:cl
#:lparallel))
(in-package #:parallel-brute-force)
(defparameter *alphabet* "abcdefghijklmnopqrstuvwxyz") (defparameter *hash0* "1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad") (defparameter *hash1* "3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b") (defparameter *hash2* "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f") (defparameter *kernel-size* 7)
(defun sha-256 (input)
(ironclad:byte-array-to-hex-string (ironclad:digest-sequence :sha256 (ironclad:ascii-string-to-byte-array input))))
(defun call-with-5-char-string (fun first-char)
(loop with str = (make-array 5 :element-type 'character :initial-element first-char)
for c1 across *alphabet*
do (setf (char str 1) c1)
(loop for c2 across *alphabet*
do (setf (char str 2) c2)
(loop for c3 across *alphabet*
do (setf (char str 3) c3)
(loop for c4 across *alphabet*
do (setf (char str 4) c4)
(funcall fun (copy-seq str)))))))
(defmacro with-5-char-string ((str first-char) &body body)
`(call-with-5-char-string (lambda (,str) ,@body) ,first-char))
(defun find-passwords-with (first-char)
(let (results)
(with-5-char-string (str first-char)
(let ((hash (sha-256 str)))
(when (or (string= hash *hash0*) (string= hash *hash1*) (string= hash *hash2*))
(push (list str hash) results))))
(nreverse results)))
(defun find-passwords ()
(setf *kernel* (make-kernel *kernel-size*))
(let ((results (unwind-protect
(pmapcan #'find-passwords-with *alphabet*)
(end-kernel))))
(dolist (r results)
(format t "~A: ~A~%" (first r) (second r)))))</lang>
- Output:
apple: 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b mmmmm: 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f zyzzx: 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad
F#
<lang fsharp> (* Nigel Galloway February 21st., 2017
- )
let N n i g e l =
let G = function
|"3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b"->Some(string n+string i+string g+string e+string l)
|"74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f"->Some(string n+string i+string g+string e+string l)
|"1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"->Some(string n+string i+string g+string e+string l)
|_->None
G ([|byte n;byte i;byte g;byte e;byte l|]|>System.Security.Cryptography.SHA256.Create().ComputeHash|>Array.map(fun (x:byte)->System.String.Format("{0:x2}",x))|>String.concat "")
open System.Threading.Tasks let n1 = Task.Factory.StartNew(fun ()->['a'..'m']|>List.collect(fun n->['a'..'m']|>List.collect(fun i->['a'..'m']|>List.collect(fun g->['a'..'z']|>List.collect(fun e->['a'..'z']|>List.choose(fun l->N n i g e l)))))) let n2 = Task.Factory.StartNew(fun ()->['a'..'m']|>List.collect(fun n->['a'..'m']|>List.collect(fun i->['n'..'z']|>List.collect(fun g->['a'..'z']|>List.collect(fun e->['a'..'z']|>List.choose(fun l->N n i g e l)))))) let n3 = Task.Factory.StartNew(fun ()->['a'..'m']|>List.collect(fun n->['n'..'z']|>List.collect(fun i->['a'..'m']|>List.collect(fun g->['a'..'z']|>List.collect(fun e->['a'..'z']|>List.choose(fun l->N n i g e l)))))) let n4 = Task.Factory.StartNew(fun ()->['a'..'m']|>List.collect(fun n->['n'..'z']|>List.collect(fun i->['n'..'z']|>List.collect(fun g->['a'..'z']|>List.collect(fun e->['a'..'z']|>List.choose(fun l->N n i g e l)))))) let n5 = Task.Factory.StartNew(fun ()->['n'..'z']|>List.collect(fun n->['a'..'m']|>List.collect(fun i->['a'..'m']|>List.collect(fun g->['a'..'z']|>List.collect(fun e->['a'..'z']|>List.choose(fun l->N n i g e l)))))) let n6 = Task.Factory.StartNew(fun ()->['n'..'z']|>List.collect(fun n->['a'..'m']|>List.collect(fun i->['n'..'z']|>List.collect(fun g->['a'..'z']|>List.collect(fun e->['a'..'z']|>List.choose(fun l->N n i g e l)))))) let n7 = Task.Factory.StartNew(fun ()->['n'..'z']|>List.collect(fun n->['n'..'z']|>List.collect(fun i->['a'..'m']|>List.collect(fun g->['a'..'z']|>List.collect(fun e->['a'..'z']|>List.choose(fun l->N n i g e l)))))) let n8 = Task.Factory.StartNew(fun ()->['n'..'z']|>List.collect(fun n->['n'..'z']|>List.collect(fun i->['n'..'z']|>List.collect(fun g->['a'..'z']|>List.collect(fun e->['a'..'z']|>List.choose(fun l->N n i g e l))))))
for r in n1.Result@n2.Result@n3.Result@n4.Result@n5.Result@n6.Result@n7.Result@n8.Result do printfn "%s" r </lang>
- Output:
mmmmm apple zyzzx
Go
This solution processes each hash in a concurrent goroutine. Goroutines run in parallel on a multicore system. <lang go>package main
import (
"crypto/sha256" "encoding/hex" "log" "sync"
)
var pwh = []string{
"1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad", "3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b", "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f",
}
func main() {
log.SetFlags(0)
var wg sync.WaitGroup
wg.Add(len(pwh))
for _, h := range pwh {
go bf(h, &wg)
}
wg.Wait()
}
func bf(h string, wg *sync.WaitGroup) {
var ha [sha256.Size]byte hex.Decode(ha[:], []byte(h))
p:
for p := []byte("aaaaa"); ; {
if sha256.Sum256(p) == ha {
log.Println(string(p), h)
}
for i, v := range p {
if v < 'z' {
p[i]++
continue p
}
p[i] = 'a'
}
wg.Done()
return
}
}</lang>
- Output:
apple 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b mmmmm 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f zyzzx 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad
A different approach is to process hashes one at a time but parallelize the search. This solution runs 26 goroutines, one for each possible password first letter. <lang go>package main
import (
"crypto/sha256" "encoding/hex" "log" "sync"
)
var pwh = []string{
"1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad", "3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b", "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f",
}
func main() {
log.SetFlags(0)
for _, h := range pwh {
pbf(h)
}
}
func pbf(h string) {
var ha [sha256.Size]byte
hex.Decode(ha[:], []byte(h))
var wg sync.WaitGroup
wg.Add(26)
for c := byte('a'); c <= 'z'; c++ {
go bf4(c, h, ha, &wg)
}
wg.Wait()
}
func bf4(c byte, h string, ha [sha256.Size]byte, wg *sync.WaitGroup) {
p := []byte("aaaaa")
p[0] = c
p1 := p[1:]
p:
for {
if sha256.Sum256(p) == ha {
log.Println(string(p), h)
}
for i, v := range p1 {
if v < 'z' {
p1[i]++
continue p
}
p1[i] = 'a'
}
wg.Done()
return
}
}</lang>
- Output:
zyzzx 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad apple 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b mmmmm 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f
Julia
<lang julia>@everywhere using SHA
@everywhere function bruteForceRange(startSerial, numberToDo)
targets = ["1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad",
"3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b",
"74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f"]
targets = map(hex2bytes, targets)
for count = 1 : numberToDo
password = [UInt8(97 + x) for x in digits(UInt8, startSerial + count, 26, 5)]
hashbytes = sha256(password)
if (hashbytes[1] == 0x11 || hashbytes[1] == 0x3a || hashbytes[1] == 0x74) && findfirst(targets, hashbytes) > 0
hexstring = join(hex(x,2) for x in hashbytes)
passwordstring = join(map(Char, password))
println("$passwordstring --> $hexstring")
end
end
return 0
end
@everywhere perThread = div(26^5, Sys.CPU_CORES) pmap(x -> bruteForceRange(x * perThread, perThread), 0:Sys.CPU_CORES-1) </lang>
- Output:
From worker 2: apple --> 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1bFrom worker 3: zyzzx --> 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad
From worker 4: mmmmm --> 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f
Perl 6
This solution can be changed from parallel to serial by removing the .race method.
<lang perl6>use Digest::SHA;
constant @alpha2 = 'aa' .. 'zz';
constant @alpha3 = 'aaa' .. 'zzz';
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>
- True to actual RC task, but slowest
constant @alpha2 = 'aa' .. 'zz'; constant @alpha3 = 'aaa' .. 'zzz';
- 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;
- 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>;
- 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).
<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