String Permutation

[Shafayat]

So, finally, I've started a topic which is definitely hot. kidding.

I actually planned to work on rainbow tables even before I posted this algorithm. Really fascinating stuff. But this does mark the end of line for this thread. Anyway, should someone overcome the limitation and has a perfectly working algorithm then please post it here because that is nothing illegal. I do not feel too motivated to do that myself as I'm extremely lazy.

Btw, this algorithm works on c++ easily with dynamic memory allocation. I didn't try pure c though.

[wraithdu]

I was asked for an example of using my array functions for this. However storing everything in an array is not very practical as we're talking about a huge number of possibilities. I'll show how you can do it with my functions on a small scale, but from a practical standpoint you'll have to rework the functions to spit out one possibility at a time. Then you can do what you want with it: try it, store it in a database, whatever.

The basic idea is to get all the combinations of a certain size from your data set, then permute each combination.

#NoTrayIcon
#include <Array.au3>

$data = StringSplit("abcdefghijklmno", "", 2) ; sample 15 element data set
$aCombo = _ArrayCombinations($data, 4, "") ; unique combinations of 4 elements from the data set
_ArrayDisplay($aCombo, "Combinations")

For $i = 1 To $aCombo[0]
    ; create an array from each possible combination and permute it
    ; each permutation is a unique 4 element set
    $aSet = StringSplit($aCombo[$i], "", 2)
    $aPerm = _ArrayPermute($aSet)
    For $j = 1 To $aPerm[0]
        ; print the permutations
        ConsoleWrite($aPerm[$j] & @CRLF)
    Next
Next

[IchBistTod]

I was asked for an example of using my array functions for this. However storing everything in an array is not very practical as we're talking about a huge number of possibilities. I'll show how you can do it with my functions on a small scale, but from a practical standpoint you'll have to rework the functions to spit out one possibility at a time. Then you can do what you want with it: try it, store it in a database, whatever.

The basic idea is to get all the combinations of a certain size from your data set, then permute each combination.

#NoTrayIcon
#include <Array.au3>

$data = StringSplit("abcdefghijklmno", "", 2) ; sample 15 element data set
$aCombo = _ArrayCombinations($data, 4, "") ; unique combinations of 4 elements from the data set
_ArrayDisplay($aCombo, "Combinations")

For $i = 1 To $aCombo[0]
    ; create an array from each possible combination and permute it
    ; each permutation is a unique 4 element set
    $aSet = StringSplit($aCombo[$i], "", 2)
    $aPerm = _ArrayPermute($aSet)
    For $j = 1 To $aPerm[0]
        ; print the permutations
        ConsoleWrite($aPerm[$j] & @CRLF)
    Next
Next

its a little slower....

but it bypasses the limit.

the string split slows it down considerably....

and what do you mean by "from a practical standpoint you'll have to rework the functions to spit out one possibility at a time" is that not what "For $i = 1 To $aCombo[0]" is doing with each possible set? working them one at a time?

Wouldnt it be faster to find a way to use multiple processes to parse this in 2,4,8,16(however many cores you have since it maxes out one core per process) processes?

I;ve been pondering this... and I can currently grasp a way to do this, with the way its stored in an array, unless I use 4 loops to make the possible sets into 4 strings with separators then send each to a process which will split the string back into an array and process it, effectively cutting the processing time by 1/4th or 1/nth.

But even this seems like there should be an easier way, then again I continue to choose to research into this at around 3-6AM and am sleep deprived....

[Datenshi]

IchBistTod, According to my (perhaps flawed) calculation, you'd pretty much have to save money for a million years to buy large enough storage for that database.

[IchBistTod]

IchBistTod, According to my (perhaps flawed) calculation, you'd pretty much have to save money for a million years to buy large enough storage for that database.

Its a good thing I have a lot of money then huh?

I just realized Im probably going to need around 5TB-10TB.

So while its going to be expensive, its by no means overly expensive.

The only thing making it expensive is the fact im going to use solid state drives.

[Datenshi]

Is this right? assuming 1char = 1byte

72^32 / 1099511627776 = 2.47422995 × 10^47 TB

1099511627776 = bytes for 1TB

72 = total num of possible chars

32 = number of total chars per string

On another note, You a millionaire?

Edited May 13, 2010 by Datenshi

[wraithdu]

I looked at this a bit more, and you just can't use my functions for something this big. AutoIt simply can't do the math (in fact cannot even store the result!) to calculate the total number of combinations. Without that number, the algorithm cannot work. The total number of combinations of 36 elements from your 72 element set is 442,512,540,276,836,779,204 (Win7's calculator was able to work this out). The maximum value that can be stored in an unsigned 64-bit integer is 18,446,744,073,709,551,615. So... you got a problem. Maybe you can find another combinations formula that does not require the total number of combinations to be pre-calculated?

The permutation function does not need a pre-calculated total, but it is a recursive function. It can be modified to work on one permutation at a time instead of building the huge result array. In my limited testing it seems to run without constantly eating memory (which would crash in the long run). So if you can solve the combinations problem, you might be ok. Either way... it would take 1000 lifetimes to calculate all your possible passwords. You would need to calculate and test 36! permutations of each of 442,512,540,276,836,779,204 combinations...

(Win7 calculator says roughly 1.6461171200383066856475410595698e+62 in total.)

Just forget about it

Edited May 13, 2010 by wraithdu

[monoceres]

This is too stupid to find words for. IchBistTod, you do realize that password cracking is an extremely well researched art?

Even extremely optimized MD5 crackers running on modern high-end graphics card don't have a snowballs chance in hell to crack long passwords. And I've seen people going up to 1 billion hashes/second.

The mere fact that you're talking about this in an autoit script thread and suggesting saving to files is ridiculous.

Are you a troll? Of so, well played.

Anyways, if you produce this magic then expect to be contacted by every government agency in the word and spend the rest of your life as a celebrity.

Because no one, thought about saving all possible hashes to a file and then search that one (you know, fetching an hash form a file is probably less efficient that calculating the hash).

[Datenshi]

lol, monoceres you're such a buzz kill

What if i worked out for 1million years, i bet id be able to lift the planet earth.

Discuss...

Edited May 13, 2010 by Datenshi

[Mat]

lol, monoceres you're such a buzz kill

What if i worked out for 1million years, i bet id be able to lift the planet earth.

Discuss...

Nope. No workout required. Give me a place to stand and I will move the Earth.

[JRowe]

You just need a really, really, long stick.

[IchBistTod]

This is too stupid to find words for. IchBistTod, you do realize that password cracking is an extremely well researched art?

Even extremely optimized MD5 crackers running on modern high-end graphics card don't have a snowballs chance in hell to crack long passwords. And I've seen people going up to 1 billion hashes/second.

The mere fact that you're talking about this in an autoit script thread and suggesting saving to files is ridiculous.

Are you a troll? Of so, well played.

Anyways, if you produce this magic then expect to be contacted by every government agency in the word and spend the rest of your life as a celebrity.

Because no one, thought about saving all possible hashes to a file and then search that one (you know, fetching an hash form a file is probably less efficient that calculating the hash).

on one note, using a sql query to pull data from a database of precompiled hashes would be much faster than generating the hashes.

beyond that... I already sucesfully had it cracking ANY password up to 5 characters long in a matter of two days via this method, on my home pc, not my server.

So its more than possible....

However you say a billion hashes a second, I assume this would be in C++?

If you know where I could find code like this, Please tell me, as it would be very usefull to generating my MD5 databases.

[IchBistTod]

Is this right? assuming 1char = 1byte

72^32 / 1099511627776 = 2.47422995 × 10^47 TB

1099511627776 = bytes for 1TB

72 = total num of possible chars

32 = number of total chars per string

On another note, You a millionaire?

not a millionaire, but close

perhaps I would be if I didnt spend so much money.

[monoceres]

on one note, using a sql query to pull data from a database of precompiled hashes would be much faster than generating the hashes.

beyond that... I already sucesfully had it cracking ANY password up to 5 characters long in a matter of two days via this method, on my home pc, not my server.

So its more than possible....

Not faster at all. 1 billion md5-hashes is ~15 GB of data. You will not be able to get disc speed of 15 GB/s.

Also, 5 characters are trivial examples, there is software that does the same you did, in the matter of minutes.

However you say a billion hashes a second, I assume this would be in C++?

If you know where I could find code like this, Please tell me, as it would be very usefull to generating my MD5 databases.

Language is irrelevant. Hardware is the key.

I just checked and 5*10^9 hashed / s is not impossible on good hardware.

But even with this, the task of cracking long password are next to impossible.

I'm not sure if you've learned this in first grade yet, but this is an exponential curve.

http://en.wikipedia.org/wiki/File:Exp.svg

Your 5 char example is somewhere where the curve hasn't risen noticeable yet and 32 chars are somewhere over the roof of your house.

Please realize, there are people who have spent most of their lives on the subject, people who really are geniuses. Do you really think their work can be crushed with a good home server and a slow script language?

You're making a complete fool of yourself.

[IchBistTod]

Not faster at all. 1 billion md5-hashes is ~15 GB of data. You will not be able to get disc speed of 15 GB/s.

Also, 5 characters are trivial examples, there is software that does the same you did, in the matter of minutes.

Language is irrelevant. Hardware is the key.

I just checked and 5*10^9 hashed / s is not impossible on good hardware.

But even with this, the task of cracking long password are next to impossible.

I'm not sure if you've learned this in first grade yet, but this is an exponential curve.

http://en.wikipedia.org/wiki/File:Exp.svg

Your 5 char example is somewhere where the curve hasn't risen noticeable yet and 32 chars are somewhere over the roof of your house.

Please realize, there are people who have spent most of their lives on the subject, people who really are geniuses. Do you really think their work can be crushed with a good home server and a slow script language?

You're making a complete fool of yourself.

solid state drives are fast enough.

I am aware of the curve.

And I am making a fool of myself?

With the money I have I am able to built far better than a "good home server".

And you contradict yourself, saying it depends on hardware, not language, as you have implied using autoit will affect the outcome. Which I agree with, but still not wise to contradict yourself when calling me a fool.

But after I will allow autoit to continue to work on the database, as I look into programming a similar app in a lower level language. (C, C++, Delphi, etc)

Edited May 13, 2010 by IchBistTod

[MvGulik]

whatever Edited February 7, 2011 by MvGulik

[James]

IchBistTod,

Stop bragging how much money you have. The people who have spent their lives on this will have ten fold what you do. Governments employ real geniuses, not some kid with money to crack these, so far, it's impossible.

Solid State Drives will not make an impact noticeable to you, you'll still be dead when they're finally cracked.

Bragging about the money you supposedly have makes you look like a fool. The more you brag, the more myself and others here will disrespect you.

James

[JRowe]

It's a matter of math, not cleverness, hardware, or computational power.

If you're going to iterate through each permutation of a given length for a given set of characters, then X amount of time is going to be spent on each iteration.

X is determined by your algorithm or lookup time. Generally, an algorithm can be designed that is faster than a lookup. Lets say, for the sake of this discussion, that X is .0001 ms.

That means it takes .0001 ms to get the candidate password and test it. This would be a phenomenally fast setup. (Aside from that, most security systems are brute-force proof, so this would be a toy.)

So there are 442,512,540,276,836,779,204 possible 30 character passwords. It takes you .0001 ms to test each combination.

442,512,540,276,836,779,204 * .0001 = 44251254027683677.9204 ms

44251254027683677.9204 ms = 44251254027683.6779204 seconds.

737520900461.395 minutes

12292015007.69 hours

512167291.99 days

1,403,198.06 years

It would take you 1.403 million years to test all possible 30 character passwords. I'm pretty sure you'll be dead by then, Tod.

[wraithdu]

Actually, it's 442,512,540,276,836,779,204 possible 36 character COMBINATIONS... you then have to test all the PERMUTATIONS of EACH combination. So multiply your figures by 36! (factorial). I think the universe will be dead by then.

[JRowe]

What's interesting to me is that there are whole classes of numbers and combinations that can be algorithmically searched to crack passwords, even though they're more than 30 characters long, because true randomness is difficult. What that practically amounts to is the idea that you (or at least, the NSA) can take IchBistTod's harddrive, run several of these algorithms, and crack his password within weeks or even days, even though the complete search space is infinitely larger than the subset used to crack it.

It's also interesting that we can conceive the scope of these numbers, even though they're larger than the number of particles in the universe. I think everyone met or exceeded their nerd quota, today. Possibly for the year, or even the rest of the decade.

Edited May 15, 2010 by JRowe