let's kick an old topic back to live... is there any progress here? are there plans for implementing the new reduction function in distrtgen&rcracki?
Sc00bz, any changes? Did you change the reduction function 'to be compatible with a similar method that uses CUDA's instruction/function __umul24()' ?

now that is a good question. *stickie* so it wont get lost in this section

Does the fast reduction function generate an even distribution of passwords when given actual chains? It's quite possible (and very easy) to create a fast reduction function that generates good output on test uniform input, but generates rubbish when run in actual chains. Not that I've been fighting with this or anything.

a good question, but i think sc00bz will have thought about it... sc00bz, did you actually read the last few questions? (if not, this is another 'bump' )

I would love to implement a new reduction function. I won't care about the backwards compatibility.
But i must admit i have no idea about how i should design a reduction function.

"To have an even distribution of passwords, when used in the context of actual chain running." A uniform set of inputs generating a uniform set of outputs is not sufficient for a good reduction function. Learned this one the hard way...

I read it but I was trying to make a bad ass MD5 implementation that is easy to use. It currently does MMX, SSE2, MMX interlaced with SSE2 (shhh "top top secret thing"), 64 bit SSE2 2x interlaced, and 64 bit SSE2 3x interlaced. I want to add SSE5 and AVX support so when those come out in the next few years you can get the benefit of them right away, but I won't add those for awhile. The only problem is that I have it set up with defines which define which algorithm the macros use. I really wanted to be able to use different algorithms in the same program so that the program can choose which one to use at run time not compile time. So that's my next task and maybe then it will be really easy to use. Ohh good news is that it works on both Windows and Linux. It also has awesomeness of 4 sets of macros for different sized passwords (7, 11, 15, 19, and 55) reverse for brute force, brute force, rainbow table early stop, and full. "Rainbow table early stop" breaks compatibility but if your max password length is 7 or less it will be able to skip 56.25% the last round making it 14.0625% faster. If the max password length is more than 7 it can skip 12.5% of the last round making it 3.125% faster. The brute force macros make it like 31.25% faster. As soon as I get this the way I like it, making the MD4 version will be very easy to add. I should just write this the testing program in C++ and tell you if it works but I like assembly.

It sounds like your working on the worlds fastest md5 password hash routine

I think i got a crazy idea about how to make a reduction function. Please comment of how you think it would work.
A hash is usually of 128 bits or more bits.
What if we take a specified amount of bits and map it to a plaintext?
In the case of md5, we could use 6 bits of the 128 bit hash for each character and then "reduce" it to the amount of characters available in the current charset.

So if the hash starts with 6FF4... and we use the charset loweralpha-numeric (36 characters), the bits would look like 0110 1111 1111 0100
We use the first 6 bits 011011 (27 decimal) which would be a plaintext 1 and the next 6 bits 111111 (63 decimal) which is then reduced (its above the 36 available chars) We could reduce it by bit shifting right until it comes below or equal to the 35 decimal (1 bitshift) in which case it will be 31 and is mapped to plaintext 4

Using 6 bits, we would have a max of 64 characters in the charset, and max plainlen of 21 characters (it should be suffient for now). If we use 7 bits / character, we could have 128 chars in the character set, but is limited to max 18 chars. Optionally we could make it flexible so if the charset is smaller, you can have longer passwords. (numeric tables only needs 4 bits)

Using this way you dont have 64 bit divides, only bit shifting.
Because your using more than 64 bits of the hash, merging chains are less likely to happen.
Downside is you have to store the full 128 bits of the hash (or just the amount of bits you actually use (for a 1-7 character alpha-numeric, using 6 bits/character, you have to store 7*6 = 42 bits of the hash, but for longer passwords and charsets it can be above 64 bits)
Another thing is how to apply the reduction offset and current chain position to the hash to prevent merges from happening in different positions of the chain.

edit: updated with more info

sounds simple, first think that comes to mind: i miss the position in the chain

Read the update

You would have to slice out the position to the different parts of the hash you use. I have to think a little more about it.
If you do a simple addition to the number it will just affect the first 1-5 plaintext characters and i dont think that would distribute the plaintexts evenly.

Maybe you could use the position to check if you should bitshift a character at a specific position.
If the current position is 100, the bits would be 0110 0100. So character 3, 6 and 7 should be bitshifted to the right 1 time each. (im reading from the right to the left for some reason)

This does not work as good as you think it does.

You could try using several different mappings depending on chain position and table index or some kind of crazy mixing function but it still comes down to you only have 64 different choices which will make some passwords more likely to show up than others.

Hmm well if you could randomly scramble the character set given like a 32 bit number then this could work. Then you still need to figure out how many characters are in the password which will take another 32 bits. Hmm I guess that works it leaves you with 10 character max for loweralpha-numeric. Only thing is that your randomly scramble the character set function better be really good.

There's always this idea, find a fast random number generator and seed it with the 128 bit hash.

I might be needing some coffee, but i don't get the issue with plaintext distribution... isn't the hash random enough for us not to worry about it?