Parallel brute force: Difference between revisions
(Add Perl) |
(Added Rust solution) |
||
Line 607: | Line 607: | ||
(#"mmmmm" . "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f") |
(#"mmmmm" . "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f") |
||
(#"zyzzx" . "1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"))</pre> |
(#"zyzzx" . "1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"))</pre> |
||
=={{header|Rust}}== |
|||
In this solution the number of threads is the number of logical processors on the machine. `distribute_work()` distributes the work more or less equally between the threads. |
|||
<lang Rust>// [dependencies] |
|||
// rust-crypto = "0.2.36" |
|||
// num_cpus = "1.7.0" |
|||
// hex = "0.2.0" |
|||
extern crate crypto; |
|||
extern crate num_cpus; |
|||
extern crate hex; |
|||
use std::thread; |
|||
use std::cmp::min; |
|||
use crypto::sha2::Sha256; |
|||
use crypto::digest::Digest; |
|||
use hex::{FromHex, ToHex}; |
|||
fn main() { |
|||
let hashes = vec![ |
|||
decode("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"), |
|||
decode("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b"), |
|||
decode("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f"), |
|||
]; |
|||
let mut threads = Vec::new(); |
|||
let mut ranges = distribute_work(); |
|||
while let Some(range) = ranges.pop() { |
|||
let hashes = hashes.clone(); |
|||
threads.push(thread::spawn( |
|||
move || search(range.0, range.1, hashes.clone()), |
|||
)); |
|||
} |
|||
while let Some(t) = threads.pop() { |
|||
t.join().ok(); |
|||
} |
|||
} |
|||
fn search(from: [u8; 5], to: [u8; 5], hashes: Vec<[u8; 256 / 8]>) { |
|||
let mut password = from.clone(); |
|||
while password <= to { |
|||
let mut sha256 = Sha256::new(); |
|||
sha256.input(&password); |
|||
let mut result = [0u8; 256 / 8]; |
|||
sha256.result(&mut result); |
|||
for hash in hashes.iter() { |
|||
if *hash == result { |
|||
println!( |
|||
"{}{}{}{}{} {}", |
|||
password[0] as char, |
|||
password[1] as char, |
|||
password[2] as char, |
|||
password[3] as char, |
|||
password[4] as char, |
|||
hash.to_hex() |
|||
); |
|||
} |
|||
} |
|||
password = next(&password); |
|||
} |
|||
} |
|||
fn next(password: &[u8; 5]) -> [u8; 5] { |
|||
let mut result = password.clone(); |
|||
for i in (0..result.len()).rev() { |
|||
if result[i] == b'z' { |
|||
if i == 0 { |
|||
result[i] = b'z' + 1; |
|||
} else { |
|||
result[i] = b'a'; |
|||
} |
|||
} else { |
|||
result[i] += 1; |
|||
break; |
|||
} |
|||
} |
|||
result.clone() |
|||
} |
|||
fn distribute_work() -> Vec<([u8; 5], [u8; 5])> { |
|||
let mut ranges = Vec::new(); |
|||
let num_cpus = min(num_cpus::get(), 26) as u8; |
|||
let div = 25 / num_cpus; |
|||
let mut remainder = 25 % num_cpus; |
|||
let mut from = b'a'; |
|||
while from < b'z' { |
|||
let to = from + div + |
|||
if remainder > 0 { |
|||
remainder -= 1; |
|||
1 |
|||
} else { |
|||
0 |
|||
}; |
|||
ranges.push(( |
|||
[from, from, from, from, from + 1].clone(), |
|||
[to, to, to, to, to].clone(), |
|||
)); |
|||
from = to; |
|||
} |
|||
ranges[0].0[4] = b'a'; |
|||
ranges.clone() |
|||
} |
|||
fn decode(string: &str) -> [u8; 256 / 8] { |
|||
let mut result = [0; 256 / 8]; |
|||
let vec = Vec::from_hex(string).unwrap(); |
|||
for i in 0..result.len() { |
|||
result[i] = vec[i]; |
|||
} |
|||
result.clone() |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
apple 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b |
|||
zyzzx 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad |
|||
mmmmm 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
Revision as of 18:04, 2 October 2017
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
BaCon
<lang qbasic>PRAGMA INCLUDE <openssl/sha.h> PRAGMA LDFLAGS -lcrypto
OPTION MEMTYPE unsigned char
LOCAL buffer[32], passwd[5] TYPE unsigned char LOCAL result TYPE unsigned char* LOCAL a,b,c,d,e TYPE int
DATA "3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b", "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f", "1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"
WHILE TRUE
READ secret$ IF NOT(LEN(secret$)) THEN BREAK
FOR i = 0 TO 31 buffer[i] = DEC(MID$(secret$, i*2+1, 2)) NEXT
FOR a = 97 TO 122 FOR b = 97 TO 122 FOR c = 97 TO 122 FOR d = 97 TO 122 FOR e = 97 TO 122 passwd[0] = a passwd[1] = b passwd[2] = c passwd[3] = d passwd[4] = e
result = SHA256(passwd, 5, 0)
FOR i = 0 TO SHA256_DIGEST_LENGTH-1 IF PEEK(result+i) != buffer[i] THEN BREAK NEXT IF i = SHA256_DIGEST_LENGTH THEN PRINT a,b,c,d,e,secret$ FORMAT "%c%c%c%c%c:%s\n" BREAK 5 END IF NEXT NEXT NEXT NEXT NEXT
WEND</lang>
- Output:
apple:3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b mmmmm:74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f zyzzx:1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad
C
<lang c>// $ gcc -o parabrutfor parabrutfor.c -fopenmp -lssl -lcrypto // $ export OMP_NUM_THREADS=4 // $ ./parabrutfor
- include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <omp.h>
- include <openssl/sha.h>
typedef unsigned char byte;
int matches(byte *a, byte* b) { for (int i = 0; i < 32; i++) if (a[i] != b[i]) return 0; return 1; }
byte* StringHashToByteArray(const char* s) {
byte* hash = (byte*) malloc(32);
char two[3];
two[2] = 0;
for (int i = 0; i < 32; i++) {
two[0] = s[i * 2];
two[1] = s[i * 2 + 1];
hash[i] = (byte)strtol(two, 0, 16);
}
return hash;
}
void printResult(byte* password, byte* hash) { char sPass[6]; memcpy(sPass, password, 5); sPass[5] = 0; printf("%s => ", sPass); for (int i = 0; i < SHA256_DIGEST_LENGTH; i++) printf("%02x", hash[i]); printf("\n"); }
int main(int argc, char **argv) {
- pragma omp parallel
{
- pragma omp for
for (int a = 0; a < 26; a++) { byte password[5] = { 97 + a }; byte* one = StringHashToByteArray("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"); byte* two = StringHashToByteArray("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b"); byte* three = StringHashToByteArray("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f"); 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]++) { byte *hash = SHA256(password, 5, 0); if (matches(one, hash) || matches(two, hash) || matches(three, hash)) printResult(password, hash); } free(one); free(two); free(three); } }
return 0; }</lang>
- Output:
apple => 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b mmmmm => 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f zyzzx => 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad
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 runs 26 goroutines, one for each possible password first letter. Goroutines run in parallel on a multicore system. <lang go>package main
import (
"crypto/sha256" "encoding/hex" "log" "sync"
)
var hh = []string{
"1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad", "3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b", "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f",
}
func main() {
log.SetFlags(0) hd := make([][sha256.Size]byte, len(hh)) for i, h := range hh { hex.Decode(hd[i][:], []byte(h)) } var wg sync.WaitGroup wg.Add(26) for c := byte('a'); c <= 'z'; c++ { go bf4(c, hd, &wg) } wg.Wait()
}
func bf4(c byte, hd [][sha256.Size]byte, wg *sync.WaitGroup) {
p := []byte("aaaaa") p[0] = c p1 := p[1:]
p:
for { ph := sha256.Sum256(p) for i, h := range hd { if h == ph { log.Println(string(p), hh[i]) } } 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
Uses threads library to do naive search using 26 threads ("aaaaa" .. "azzzz", "baaaa" .. "bzzzz", etc.). No effort is made to early exit. <lang>use Digest::SHA qw/sha256_hex/; use threads; use threads::shared; my @results :shared;
print "$_ : ",join(" ",search($_)), "\n" for (qw/
1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f
/);
sub search {
my $hash = shift; @results = (); $_->join() for map { threads->create('tsearch', $_, $hash) } 0..25; return @results;
}
sub tsearch {
my($tnum, $hash) = @_; my $s = chr(ord("a")+$tnum) . "aaaa";
for (1..456976) { # 26^4 push @results, $s if sha256_hex($s) eq $hash; $s++; }
}</lang>
- Output:
1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad : zyzzx 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b : apple 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f : mmmmm
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
Racket
Tests are included firstly to check it works, but they also provide an opportunity to time the single threaded version.
<lang racket>#lang racket/base (require racket/place
racket/list racket/match ;; requires sha package. install it in DrRacket's "File/Install Package..." ;; or with raco: ;; % raco pkg install sha sha (only-in openssl/sha1 hex-string->bytes))
(define (brute css targs)
(define (sub-work i) (let ((cs (list-ref css i))) (in-range (car cs) (cdr cs)))) (define-values (as bs cs ds es) (apply values (map sub-work (range 5)))) (define s (make-bytes 5)) (for*/list ((a as) #:when (bytes-set! s 0 a) (b bs) #:when (bytes-set! s 1 b) (c cs) #:when (bytes-set! s 2 c) (d ds) #:when (bytes-set! s 3 d) (e es) #:when (bytes-set! s 4 e) (h (in-value (sha256 s))) (t (in-list targs)) #:when (bytes=? t h)) (eprintf "found ~s -> ~s~%" t s) (cons (bytes-copy s) t)))
- ---------------------------------------------------------------------------------------------------
(unless (place-enabled?) (error "We're using places... they're not enabled!"))
(define target-list
(map hex-string->bytes (list "1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad" "3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b" "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f")))
(define (run-place/assign-task sub-task)
(define there (place here (match-define (cons work targs) (place-channel-get here)) (place-channel-put here (brute work targs)))) (place-channel-put there (cons sub-task target-list)) there)
(define (task->subtasks css n-tasks)
(match css [(list (and initial-range (cons A Z+)) common-tail ...) (define step (quotient (+ n-tasks (- Z+ A)) n-tasks)) (for/list ((a (in-range A Z+ step))) ;; replace the head with a sub-task head (cons (cons a (min (+ a step) Z+)) common-tail))]))
(define readable-pair (match-lambda [(cons x (app bytes->hex-string s)) (cons x s)]))
(define (parallel-brute css (n-tasks (processor-count)))
(define the-places (map run-place/assign-task (task->subtasks css n-tasks))) (define collected-results (append* (map place-channel-get the-places))) (map readable-pair collected-results))
(define 5-char-lowercase-work
(make-list 5 (cons (char->integer #\a) (add1 (char->integer #\z)))))
- ---------------------------------------------------------------------------------------------------
(module+ main
(time (parallel-brute 5-char-lowercase-work)))
- ---------------------------------------------------------------------------------------------------
(module+ test
(require rackunit) (check-equal? (bytes->hex-string (sha256 #"mmmmm")) "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f" "SHA-256 works as expected")
(check-equal? (hex-string->bytes "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f") #"t\341\273b\370\332\273\201%\245\210R\266;\337n\256\366g\313V\254\177|\333\246\3270\\P\242/" "This is the raw value we'll be hashing to") (define m-idx (char->integer #\m)) (define m-idx+ (add1 m-idx)) (check-equal? (brute (make-list 5 (cons m-idx m-idx+)) target-list) (list (cons #"mmmmm" #"t\341\273b\370\332\273\201%\245\210R\266;\337n\256\366g\313V\254\177|\333\246\3270\\P\242/")))
;; Brute works without parallelism ;; check when you have the time... it takes a minute (literally) (check-equal? (time (brute 5-char-lowercase-work target-list)) '((#"apple" . #":{\323\3426\n=)\356\2446\374\373~D\3075\321\27\304-\34\0305B\vk\231B\335O\e") (#"mmmmm" . #"t\341\273b\370\332\273\201%\245\210R\266;\337n\256\366g\313V\254\177|\333\246\3270\\P\242/") (#"zyzzx" . #"\21\25\335\200\17\352\254\357\337H\37\37\220p7J*\201\342x\200\361\2079m\266yX\262\a\313\255")) "without parallelism, it works"))</lang>
- Output:
Test phase of run:
found #"t\341\273b\370\332\273\201%\245\210R\266;\337n\256\366g\313V\254\177|\333\246\3270\\P\242/" -> #"mmmmm" found #":{\323\3426\n=)\356\2446\374\373~D\3075\321\27\304-\34\0305B\vk\231B\335O\e" -> #"apple" found #"t\341\273b\370\332\273\201%\245\210R\266;\337n\256\366g\313V\254\177|\333\246\3270\\P\242/" -> #"mmmmm" found #"\21\25\335\200\17\352\254\357\337H\37\37\220p7J*\201\342x\200\361\2079m\266yX\262\a\313\255" -> #"zyzzx" cpu time: 19593 real time: 19581 gc time: 2247
Main phase of run:
found #"\21\25\335\200\17\352\254\357\337H\37\37\220p7J*\201\342x\200\361\2079m\266yX\262\a\313\255" -> #"zyzzx" found #":{\323\3426\n=)\356\2446\374\373~D\3075\321\27\304-\34\0305B\vk\231B\335O\e" -> #"apple" found #"t\341\273b\370\332\273\201%\245\210R\266;\337n\256\366g\313V\254\177|\333\246\3270\\P\242/" -> #"mmmmm" cpu time: 30641 real time: 4681 gc time: 0 '((#"apple" . "3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b") (#"mmmmm" . "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f") (#"zyzzx" . "1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"))
Rust
In this solution the number of threads is the number of logical processors on the machine. `distribute_work()` distributes the work more or less equally between the threads.
<lang Rust>// [dependencies] // rust-crypto = "0.2.36" // num_cpus = "1.7.0" // hex = "0.2.0"
extern crate crypto; extern crate num_cpus; extern crate hex;
use std::thread; use std::cmp::min; use crypto::sha2::Sha256; use crypto::digest::Digest; use hex::{FromHex, ToHex};
fn main() {
let hashes = vec![ decode("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"), decode("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b"), decode("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f"), ];
let mut threads = Vec::new(); let mut ranges = distribute_work();
while let Some(range) = ranges.pop() { let hashes = hashes.clone(); threads.push(thread::spawn( move || search(range.0, range.1, hashes.clone()), )); }
while let Some(t) = threads.pop() { t.join().ok(); }
}
fn search(from: [u8; 5], to: [u8; 5], hashes: Vec<[u8; 256 / 8]>) {
let mut password = from.clone();
while password <= to { let mut sha256 = Sha256::new(); sha256.input(&password); let mut result = [0u8; 256 / 8]; sha256.result(&mut result);
for hash in hashes.iter() { if *hash == result { println!( "{}{}{}{}{} {}", password[0] as char, password[1] as char, password[2] as char, password[3] as char, password[4] as char, hash.to_hex() ); } }
password = next(&password); }
}
fn next(password: &[u8; 5]) -> [u8; 5] {
let mut result = password.clone(); for i in (0..result.len()).rev() { if result[i] == b'z' { if i == 0 { result[i] = b'z' + 1; } else { result[i] = b'a'; } } else { result[i] += 1; break; } } result.clone()
}
fn distribute_work() -> Vec<([u8; 5], [u8; 5])> {
let mut ranges = Vec::new(); let num_cpus = min(num_cpus::get(), 26) as u8;
let div = 25 / num_cpus; let mut remainder = 25 % num_cpus; let mut from = b'a'; while from < b'z' {
let to = from + div + if remainder > 0 { remainder -= 1; 1 } else { 0 };
ranges.push(( [from, from, from, from, from + 1].clone(), [to, to, to, to, to].clone(), ));
from = to; } ranges[0].0[4] = b'a';
ranges.clone()
}
fn decode(string: &str) -> [u8; 256 / 8] {
let mut result = [0; 256 / 8]; let vec = Vec::from_hex(string).unwrap(); for i in 0..result.len() { result[i] = vec[i]; } result.clone()
}</lang>
- Output:
apple 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b zyzzx 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad mmmmm 74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f
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