[Solved] algorithm for slicing brute force keyspace [closed]

by


Let’s start with a slightly simpler problem. All keys are 8 numeric digits, and you have 10 machines.

Simple enough – one machine checks 0???????, another checks 1??????? and so on. Note that this slicing doesn’t care that you’re doing multiprocessing – it’s just allocating ranges by fixing one of the digits.

Your version is only slightly more involved. Each slice has a range for the first digit (and maybe the second, maybe more, depending how equal you need the slice-sizes to be).

Assume you want two-character prefixes. Do the checks for single-character passwords up front, so you no longer have to worry about those – there aren’t enough of them to worry about multi-processing.

Then (conceptually, at least) you make a list of two-character prefixes, and divide up that list.

What do I mean by “conceptually”? There are 62 valid characters (26 uppercase, 26 lowercase, 10 digits). So there are 62*62 = 3844 possible two-character prefixes. But you don’t need to list them all out to determine which prefix happens at which position. If there are five processors, I want that list of prefixes into 5. So there are 6 boundaries between slices…

Bound   0     1     2     3     4     5
        |     |     |     |     |     |
Slice   |  1  |  2  |  3  |  4  |  5  |

The positions of the bounds within those 3844 prefixes are…

|-------+------------+--------|
| Bound | Calc       | Result |
|-------+------------+--------|
|     0 | (3844*0)/5 |      0 |
|     1 | (3844*1)/5 |    768 |
|     2 | (3844*2)/5 |   1537 |
|     3 | (3844*3)/5 |   2306 |
|     4 | (3844*4)/5 |   3075 |
|     5 | (3844*5)/5 |   3844 |
|-------+------------+--------|

So the slices are…

|-------+------------------|
| Slice | Indexes          |
|-------+------------------|
|     1 |    0 <= i <  768 |
|     2 |  768 <= i < 1537 |
|     3 | 1537 <= i < 2306 |
|     4 | 2306 <= i < 3075 |
|     5 | 3075 <= i < 3844 |
|-------+------------------|

For each processor to keep track of how many prefixes it has handled so far is no real problem, but it needs to know where to start, so we need to convert an index to a two-character prefix. Assuming you use codes 0 to 61 (62 different codes) for lowercase, then uppercase, then digits, here’s how you convert for bound 1…

  • 768 / 62 = 12 remainder 24
  • Character 12 (with zero = a) is m
  • Character 24 is y
  • The two-character prefix is “my”.

So your first slice is from “aa” up to, but not including “my”. The processor dealing with that just has to try every possible suffix, including the empty suffix.

solved algorithm for slicing brute force keyspace [closed]