Join GitHub today
GitHub is home to over 31 million developers working together to host and review code, manage projects, and build software together.Sign up
Brute Force work distributor
Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Type||Name||Latest commit message||Commit time|
|Failed to load latest commit information.|
Clortho is the keymaster. Clortho is a tool to assist with exhaustive keyspace search using multiple systems. It divides up the keyspace and distributes work to a number of JtR worker processes which may change during the lifetime of the attempt. BACKGROUND Brute-force password cracking has been often used as a last-resort, as the limited capacity of even today's (2012) computers lead to half-word lengths measured in years. However, cracking passwords is an embarrassingly parallel problem, and several different strategies have been taken to divide the work. The most common approach scales for multiple cores on a single machine (OpenMP). However, it does not perform as well as simple divide-and-conquer, at least without parameter tuning. MPI scales well across a homogeneous cluster of machines, but does not allow for compute units to join and leave the cluster without restart. Markov mode has been used with some success, however it does not cover the entire keyspace without significant overhead. It does have the property of being memoryless - given the state N, getting to state N+X (or any arbitrary state) is trivial. Clortho originally divided Markov ranges, but even larger ranges (e.g. level 399) don't exhaust the keyspace. The 'Incremental' mode of John the Ripper (JtR) is based on the premise that exhaustive cracking never terminates on real-world charset/lengths, and thus uses frequency mappings to prioritize combinations. It does work well with mpi for homogeneous clusters, but does not lend itself to creating blocks of work in advance (more later). PURPOSE The purpose of Clortho is to meet two goals: * Exhaust the keyspace for a given length and plaintext alphabet * Use computing efficiently towards reaching the first goal The second goal implies a few qualities: * Over a reasonable time period, a 35000Kc/s system should contribute the work equivalent to ten 3500Kc/s systems. This is achieved by using a single-threaded JtR process for each core. * Compute power should be usable whether available continuously for the entire run, or for a shorter period of time. NON-GOALS Non-goals include optimizing individual passwords: modifying JtR incremental mode to *skip* encryption would still take ~2000 DAYS to generate and discard the entire keyspace, as it is effectively single threaded, and the algorithm increments well but does not have the memoryless properties of Markov. A previous effort modified JtR into two parts, a workload generator which determined stop/start points for a given work unit, and the Incremental cracker which would start and stop at these points. However the generator (effectively incremental mode without cracker.c functions) was only able to cover ~1.7E13 passwords in a 24 hour period - approx 0.27% of the keyspace. Further investigation in speeding incremental block generation is very interesting. For now, Clortho trades the intelligence of trigraph frequencies for fast work generation. HOW IT WORKS: WORK UNIT GENERATION On the server side, the workload (hashes) are gathered and the script 'brutus.py' segments the keyspace into chunks based on a target number of (single hash) combinations per job. For example, for a 2,136,000,000c target on the 8 character password space: ./brutus.py 2136000000 8 > newjob.work It is possible to hit multiple lengths in the same file by appending. Given the workunit above, lengths 1 through 5 become single work units, but the longer lengths use 51, 3,487, and 240,543 units. Remember that the number of salts your hash file contains will multiply the length the work unit takes to execute. It is also possible to alter/expand the alphabet (in both brutus and plugin at the same time!) CLIENT / SERVER The cgi-bin/server provides work units to clients. It is possible to give a particular IP address different work than the others, but the default files used are default.hashes and default.work. If there is no work available, clients are told to sleep for two minute and check back. The client.py creates one worker thread per system (using POSIX sysconf, this likely won't work on windows) and each worker will connect to the specified server, get a work unit, and report results back. If a password is found, it is removed from the hashes to speed up future work units. The worker threads use a program (plugin) to provide combinations to JtR --stdin mode. This does add overhead; the plugin alone generates work more quickly than stripped Incremental mentioned before, but it would be even more efficient to generate work within JtR. A sample work unit (test.*) is provided, which can be used to quickly verify configuration before providing real work to your clients. It contains a small amount of tiny work units, and both hashes which can be found in the work units. POTENTIAL ENHANCEMENTS / MAYBE-TODO * general stability / exception handling * client kill / removal from server command * client self-update * automatic purging of stale RUNNING jobs * plugin could be integrated into JtR. This may reduce the 12% overhead observed. * dynamic work unit sizing, based on client self-benchmarking