Parallel brute force: Difference between revisions
(→{{header|C sharp|C#}}: Simpler program) |
|||
Line 16: | Line 16: | ||
<lang csharp>using System; |
<lang csharp>using System; |
||
using System.Linq; |
using System.Linq; |
||
⚫ | |||
using System.Text; |
using System.Text; |
||
using System.Threading.Tasks; |
using System.Threading.Tasks; |
||
Line 24: | Line 23: | ||
static void Main(string[] args) |
static void Main(string[] args) |
||
{ |
{ |
||
Parallel.For(0, 26, a => { |
|||
⚫ | |||
byte[] password = new byte[5]; |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
var prey = new byte[][] { one, two, three }; |
|||
⚫ | |||
var dt = DateTime.Now; |
|||
⚫ | |||
int chunksize = 26 * 26 * 26 * 26 * 26 / Environment.ProcessorCount; |
|||
password[0] = (byte)(97 + a); |
|||
⚫ | |||
from i in Enumerable.Range(0, Environment.ProcessorCount) |
|||
⚫ | |||
select Task.Run(() => MatchesInRange(i * chunksize, (i + 1) * chunksize - 1, prey)) |
|||
for (password[2] = 97; password[2] < 123; password[2]++) |
|||
for (password[3] = 97; password[3] < 123; password[3]++) |
|||
Task.WaitAll(tasks); |
|||
for (password[4] = 97; password[4] < 123; password[4]++) |
|||
Console.WriteLine((DateTime.Now - dt).TotalMilliseconds + " milliseconds elapsed."); |
|||
⚫ | |||
⚫ | |||
if (matches(one, hash) || matches(two, hash) || matches(three, hash)) |
|||
⚫ | |||
+ BitConverter.ToString(hash).ToLower().Replace("-", "")); |
|||
⚫ | |||
⚫ | |||
} |
} |
||
static byte[] StringHashToByteArray(string s) |
static byte[] StringHashToByteArray(string s) |
||
Line 41: | Line 47: | ||
return Enumerable.Range(0, s.Length / 2).Select(i => (byte)Convert.ToInt16(s.Substring(i * 2, 2), 16)).ToArray(); |
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) |
|||
static void MatchesInRange(int start, int stop, byte[][] prey) |
|||
{ |
{ |
||
for (int i = 0; i < 32; i++) |
|||
if (a[i] != b[i]) |
|||
return false; |
|||
return true; |
|||
for (int seriali = start; seriali <= stop; seriali++) |
|||
{ |
|||
serial = seriali; |
|||
int divisor = 456976; // 26 * 26 * 26 * 26; |
|||
⚫ | |||
{ |
|||
letters[i] = (byte)(97 + Math.DivRem(serial, divisor, out serial)); |
|||
⚫ | |||
} |
|||
⚫ | |||
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])) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
⚫ | |||
} |
} |
||
}</lang> |
}</lang> |
Revision as of 23:21, 21 February 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
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