Hi, my questions are: why do you need "step"? What are you going to do with, for example, every 5th permutation?

Also, can you limit the problem to only finding permutations of a certain length? Or at least split the problem into several iterations, each of which only finds permutations of a certain length?

If the program will be multithreaded, it would be faster to split the problem by blocks instead of by steps. In other words, right now if you have 5 threads, one thread would generate 0..5..10..15..20..25 etc.

And the next thread 1..6..11..16..21..26 etc

But why not split it so the first thread generates 0..1..2..3..4, and the next thread generates 25..26..27..28..29

I'll leave you with this link to a solution I gave to a brute force permutation generating question very similar to yours. By using extra space, I was able to generate permutations very quickly (but only if step=1 and the length is fixed): codereview.stackexchange.com/questions/38474/…

You probably won't believe, but that algorithm you gave me a link to is the one I was starting from with that bruteforce business. If you want to, google "Woodpecker hash bruteforce". That's what I'm working with. Two threads are always faster than one. So, two threads will generate all permutations from range [1-10000] than one thread, right? The same is with three threads. That's why I'm not using blocks of numbers.

The version you'll get when you get to the official site appears to be pretty slow now. Why? Because of that algorithm I asked my question about.

So, every N-th permutation's gonna get hashed and then compared to original hash (the one the user wanna bruteforce).

I see, you some sort of specialize in brute-force? :)

Are you getting notifications about new messages in that chat room?

Hi sorry, I'm here now so I read what you said. But I'm not 100% in this room, just checking now and then.

So if you started with the thing that I suggested, did you read my solution to it?

Ah, OK. I've just checked your code and it's damn fast!! How did you do it??!! My code seems to really suck! My _ EGO_ is feeling just like peace of sh*t now...

Well I explained it in my answer. Basically I used an array of alphabetSize ^ 2 strings

Suppose the alphabet was just a-z

And the length was 5 letters long

I generated these strings: aaaaa aaaab aaaac ... aaaba aaabb aaabc ... aaaza aaazb aaazc ... aaazz

So then right away I could send 26*26 strings in a row to the next function that needed to process each string

And then to generate the next 26*26 strings, all I do is increment one character across the entire array of 676 strings:

I increment the 3rd character (change all from 'a' to 'b'):

aabaa aabab aabac ... aabba aabbb aabbc ... aabzy aabzz

It's much faster because I am basically doing 676 increments and only check for wraparound (from 'z' to 'a') once, instead of doing it once for each string.

Essentially it's kind of like unrolling your conv() function 676 times

Anyways, you should study the code I wrote and see what it's doing. Then adapt that kind of solution to your own code. Still, I think that the permutation generation should be pretty fast compared to whatever processing you are doing on each string (hashing it?) So even if the improved permutation generation is 100x faster than the old way, I doubt that your program as a whole will get faster by more than a few percentage points. It depends on what you are doing with the string though.

Well, that's extremely fast! So, your code uses lots of memory, but works faster. My code uses as little memory as possible, so it's pretty slow. The latest improvement I made to my code made it run 60_(!!!) times faster. That was to do with hash comparing. Still, the code I'm currently using (not the one in the question) is _seven times slower.

I've just forked your repo so I won't lose it. Thank you very much for your explanations!

Sure. So I see that you are doing a brute force dictionary search to find the string that hashes to a particular hash?

I wonder if you can speed it up by performing the hash to a certain point and then "forking" the hash

For example, if you try to hash "aaaaa", you can hash the first four letters "aaaa"

And then, preserving the state, now hash the final letter "a", but then try all letters "a"-"z"

In other words, if you can perform a partial hash and then permute the final letters, you can save the time of hashing the first N letters which should be the same

I don't quite get the idea. The hash of "aaaaa" is different from the hash of "aaaa". How am I going to combine the hashes of the first letters and the last one?

It probably wouldn't work though. I just looked up SHA-1 and it uses a 512-bit block size so the entire string would need to fit into that block

The idea would work with something simpler like a checksum or a CRC

where you feed one byte at a time into the algorightm

So checksum("aaaaa") = checksum("aaaa") + checksum("a") for example, and you can precompute checksum("aaaa") and then do all the single letter values

But for the hashes you are working with, I don't think that is possible

I'm wondering though, are you actually doing a SHA-1 on something small like 8 letters long? Do you pad the rest out with zeroes?

I'm using OpenSSL to make hashes. It's possible to call something like update(Hash, new_data), but how am I going to 'preserve the state'?

I'm working with md2, md4, md5, sha-1 and sha-2

But are you hashing small strings?

I was just reading the wikipedia on SHA-1 and MD-5 and they use 512 bit blocks

Yes, up to 10 characters long or even smaller.

OK interesting.

If you have access to a Windows or Mac OS computer, you could download the program I'm developing and see how it works.

I'm not an expert at SHA-1. But it might be the case that SHA1("aaaaa") and SHA1("aaaab") are related in a way where you can compute SHA1("aaaab") faster than doing the whole hash if you already know the answer to SHA1("aaaa") and SHA1("aaaaa")

From skimming the SHA-1 algorithm, it's probably faster to just recompute the hash than to try and figure out a clever way of reusing partial computations. If it were that easy to relate SHA1("aaaaa") to SHA1("aaaab"), then SHA-1 would be easy to crack.

Speaking about OpenSSL's implementation, they have AlgoName_Update() method that allows to add more data to the AlgoName_CTX pointer.

But that should recompute the whole hash, I think.

Right.

I'm just thinking that hashing is the slowest part of your program. Generating one permutation probably takes < 10% of the time that it takes to do a SHA-1 hash on that permutation.

So the way to really speed up your program is to figure out a way to hash faster. Which is why I was thinking of doing "partial hashes", but that doesn't work

That means, the easiest way to speed up the program is to speed up one of its bottlenecks - combination generation. And the hardest - to implement my own MD5/SHA-1 etc algorithm

...which will definitely be much slower than the existing implementations :)

Are you just trying to find a collision?

In other words, you have a SHA-1 hash, and you just want to find some block that hashes to the same thing?

Or do you actually have a SHA-1 hash of a small string like a password, and you are trying to dictionary search for that password?

If you actually have the hash of a password, I'm sure there are some string patterns that are more likely to be the password than others.

If it's just trying to find a random collision, a brute force attack wouldn't work too well.

Nevermind I looked at your website and I can see that you are looking for actual small strings.

Here are some tests that show that the version that's currently used in my app ("old") is very slow compared to other versions ("j3") is the one I was asking about. Yes, "j2" is faster in that case, but it fails to generate correct permutations if step is greater or equal to the alphabet's length.

Wordlist brute-force is also implemented, but the most interesting part for me is generating permutations of letters.

"conv" version was written in C++ and it turns out to be very slow. I think it's because I don't know C++ well enough.

The maximum speed I achieved was about 8 MH/s using four threads on an Intel Core i5 with an MD5 hash. Now I'm looking forward to an x7 speed increase.

Okay, I've got to go now. If you have any questions or suggestions on speed improvement or anything else, feel free to leave a message here. I really appreciated the conversation. Cheers.