How to resolve the algorithm Parallel brute force step by step in the Haskell programming language

Published on 7 June 2024 03:52 AM
#Haskell

How to resolve the algorithm Parallel brute force step by step in the Haskell programming language

Table of Contents

Problem Statement

Find, through brute force, the five-letter passwords corresponding with the following SHA-256 hashes: 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

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Parallel brute force step by step in the Haskell programming language

Brute Force Cracking with Parallelism and Pipelining

Source Code Walkthrough:

First Version:

1. Importing Libraries:

  • Core libraries for concurrent programming, cryptography, and monadic operations.

2. Constants:

  • hashedValues: A list of hashed values (SHA256 digests) of known strings.

3. Brute Force Function: bruteForce

  • Parametrized by the number of cores to use (n).
  • Uses the par monad to parallelize the computation.
  • Generates different combinations of characters and hashes them to find matches in hashedValues.
  • Returns a list of matching string-hash value tuples.

4. Main Function:

  • Gets the number of available cores and sets the number of capabilities to that.
  • Runs the bruteForce function with the number of cores as the argument.
  • Prints the result by mapping a formatting function on the list of tuples.

Second Version:

1. Importing Libraries:

  • Additional libraries for channel-based concurrency and environment variable handling.

2. Type Definitions:

  • Decrypted: The decrypted string.
  • Encrypted: The SHA256 digest.
  • TestString: A list of 8-bit words representing characters.

3. Constants:

  • hashedValues: Same as in the first version.

4. Utility Function: chunks

  • Generates chunks of character combinations for parallel processing.

5. Matching Function: findMatch

  • Takes a TestString and an accumulator list of matching tuples.
  • Hashes the TestString, checks if the hash matches any value in hashedValues, and appends the matching tuple to the accumulator.

6. Search Worker Function: searchWorker

  • Reads chunks of TestString from a channel.
  • Finds matches using the findMatch function.
  • Writes the results to a channel.

7. Main Function:

  • Parses the number of workers (if provided) from command-line arguments.
  • Gets the number of available cores.
  • Sets the number of capabilities to the number of workers.
  • Creates channels for communication between main and worker threads.
  • Spawns worker threads.
  • Writes the chunks of character combinations to the channel.
  • Reads and prints the results from the channel.

Explanation:

The goal of this program is to brute-force crack a list of hashed values by trying different combinations of characters. The second version improves upon the first by using a pipelined approach with channels for communication between the main thread and worker threads. This allows for more efficient processing and reduces contention on shared resources.

The bruteForce function in the first version parallelizes the generation and hashing of character combinations, but it doesn't use any synchronization or communication between the parallel tasks. This can lead to race conditions and incorrect results.

In the second version, the searchWorker function reads chunks of character combinations from a channel, finds matches, and writes the results to another channel. The main thread controls the flow of data between the worker threads and itself, ensuring that results are processed in order and without any contention. This pipelined approach also allows for easy scaling by adding or removing worker threads as needed.

Overall, both versions of this program demonstrate techniques for parallelizing a brute-force cracking algorithm, but the second version provides a more efficient and scalable solution using channels.

Source code in the haskell programming language

import           Control.Concurrent (setNumCapabilities)
import           Crypto.Hash        (hashWith, SHA256 (..), Digest)
import           Control.Monad      (replicateM, join, (>=>))
import           Control.Monad.Par  (runPar, get, spawnP)
import           Data.ByteString    (pack)
import           Data.List.Split    (chunksOf)
import           GHC.Conc           (getNumProcessors)
import           Text.Printf        (printf)

hashedValues :: [Digest SHA256]
hashedValues = read <$>
  [ "3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b"
  , "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f"
  , "1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad" ]

bruteForce :: Int -> [(String, String)]
bruteForce n = runPar $ join <$> 
  (mapM (spawnP . foldr findMatch []) >=> mapM get) chunks
  where
    chunks = chunksOf (26^5 `div` n) $ replicateM 5 [97..122]
    findMatch s accum
      | hashed `elem` hashedValues = (show hashed, show bStr) : accum
      | otherwise = accum
      where
        bStr = pack s
        hashed = hashWith SHA256 bStr

main :: IO ()
main = do
  cpus <- getNumProcessors
  setNumCapabilities cpus
  printf "Using %d cores\n" cpus
  mapM_ (uncurry (printf "%s -> %s\n")) (bruteForce cpus)


import           Control.Concurrent      (forkIO, setNumCapabilities)
import           Control.Concurrent.Chan (Chan, newChan, readChan, writeList2Chan)
import           Control.Monad           (replicateM, replicateM_, forever)
import           Crypto.Hash             (SHA256(..), Digest, hashWith)
import           Data.Bifunctor          (first)
import           Data.ByteString         (ByteString, pack)
import           Data.Char               (isDigit)
import           Data.List.Split         (chunksOf)
import           Data.Word               (Word8)
import           GHC.Conc                (getNumProcessors)
import           System.Environment      (getArgs)
import           Text.Printf             (printf)

type Decrypted = String
type Encrypted = Digest SHA256
type TestString = [Word8]

hashedValues :: [Encrypted]
hashedValues = read <$>
  [ "3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b"
  , "74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f"
  , "1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad" ]

chunks :: [[TestString]]
chunks = chunksOf (10^3) $ replicateM 5 [97..122]

findMatch :: TestString -> [(Encrypted, Decrypted)] -> [(Encrypted, Decrypted)]
findMatch w acc
  | hashed `elem` hashedValues = (hashed, show bStr):acc
  | otherwise = acc
  where
    bStr = pack w
    hashed = hashWith SHA256 bStr

searchWorker :: Chan [TestString] -> Chan (Encrypted, Decrypted) -> IO ()
searchWorker batchChan resultChan = forever (readChan batchChan >>= writeList2Chan resultChan . foldr findMatch [])

parseInput :: [String] -> Int -> Int
parseInput [] n    = n
parseInput (s:_) n = if all isDigit s then read s else n

main :: IO ()
main = do
  workers <- getArgs
  cpus <- getNumProcessors
  let wCount = parseInput workers cpus
  setNumCapabilities wCount
  printf "Using %d workers on %d cpus.\n" wCount cpus
  resultChan <- newChan
  batchChan <- newChan
  replicateM_ wCount (forkIO $ searchWorker batchChan resultChan)
  writeList2Chan batchChan chunks
  replicateM_ (length hashedValues) (readChan resultChan >>= uncurry (printf "%s -> %s\n") . first show)

You may also check:How to resolve the algorithm The Twelve Days of Christmas step by step in the SparForte programming language
You may also check:How to resolve the algorithm Calendar step by step in the Scala programming language
You may also check:How to resolve the algorithm Find common directory path step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm Two bullet roulette step by step in the C programming language
You may also check:How to resolve the algorithm Memory allocation step by step in the Bracmat programming language