String Permutation

[Shafayat]

Here is an algorithm I coded out just for fun. It can successfully generate any number of string of any length.

Here is the fully commented version:

expandcollapse popup

; //======== String Permutation Example ========\\
; \\============================================//
; //=============== by Shafayat ================\\
; \\============================================//
;
; This Example Shows How to do "String Permutation"
; or Essentially "Brute Force String Generation"
; with pure autoit.
; It is quite fast an algorithm when working with
; few characters (which is the common scenerio
; in Practical Life.
; It takes somewhat 2.6 seconds on my i7 PC. (should
; not take more than 5 secs on any modern day PC.)

; \\============================================//
; //================ Initialize ================\\
; \\============================================//

#include <Array.au3> ; For OutPut Only.

; \\============================================//
; //================ User Input ================\\
; \\============================================//

$string = 'abcdefghijklmnopqrstuvwxyz' ; The Set of Characters to work with.
$totalchars = 4 ; Lenght of every "word"
$output = @ScriptDir & "\TextList.txt" ; File to save to.
$separator = @CRLF

; \\============================================//
; //=============== Main  Script ===============\\
; \\============================================//

Global $chars = StringSplit($string, "") ; Convert to array.

$limit = $chars[0] ^ $totalchars + 1 ; Pre-calculate the size so that we do not have to ReDim
Global $array[$limit] ; Declare as Global to minimize Parsing time

For $j = 1 To $totalchars ; Loop and increase "indent (the position to add next character)"
    Fill($j) ; Call the fuction to fill a full row
Next

if Not FileRecycle($output) Then FileDelete($output) ; Ensure that previous file does NOT exist
FileWrite($output, _ArrayToString($array, $separator)) ; Save
ShellExecute($output) ; Run
Exit ; Do I have to comment this one too?

; \\============================================//
; //=============== Main  Script ===============\\
; \\============================================//

Func Fill($indent)
    Local $i = 0, $char = "", $num = 0 ; i = index, char = current character, num = order of char from $Chars array.
    Local $numofloops = $chars[0] ^ $indent ; Get the number of loops.
    Local $looplenght = $chars[0] ^ ($totalchars - $indent) ; Get the number of recursion required in every loop.

    For $z = 1 To $numofloops
        If $num = $chars[0] Then $num = 0 ; num can't be more than number of characters in string.
        $num += 1 ; increase by one
        $char = $chars[$num] ; get current character. (faster than using value from array directly)
        For $y = 1 To $looplenght
            $i += 1 ; i = index always needs to be increased
            $array[$i] &= $char ; Add value
        Next
    Next
EndFunc   ;==>Fill

Here is a slim-striped simplified version if you want to take a quick look.

#include <Array.au3>

$string = 'ABCDEFGH'
$totalchars = 5
$output = @ScriptDir & "\TextList.txt"
$separator = @CRLF

$chars = StringSplit($string, "")
$limit = $chars[0] ^ $totalchars + 1
Dim $array[$limit]

For $indent = 1 To $totalchars
    Dim $i = 0, $char = "", $num = 0
    $numofloops = $chars[0] ^ $indent
    $looplenght = $chars[0] ^ ($totalchars - $indent)

    For $z = 1 To $numofloops
        If $num = $chars[0] Then $num = 0
        $num += 1
        $char = $chars[$num]
        For $y = 1 To $looplenght
            $i += 1
            $array[$i] &= $char
        Next
    Next
Next

If Not FileRecycle($output) Then FileDelete($output)
FileWrite($output, _ArrayToString($array, $separator))
ShellExecute($output)
Exit

Edited May 11, 2010 by Shafayat

[James]

Wow that is quick! Very cool, I assume the same algorithm would work with numbers? Of course it is!

Edited May 11, 2010 by JamesBrooks

[Shafayat]

I'm glad that you like it.

There is a limitation in the number of array elements in autoit and hereby a limitation in this algorithm. I'm trying to create a solution using memory structure.

[IchBistTod]

I'm glad that you like it.

There is a limitation in the number of array elements in autoit and hereby a limitation in this algorithm. I'm trying to create a solution using memory structure.

yes

I was trying to crack my 36 character password

for $xi=1 to 36
    $array = ""
    $separator = ""
$string = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()' ; The Set of Characters to work with.
$totalchars = $xi ; Lenght of every "word"
$output = @ScriptDir & "\TextList.txt" ; File to save to.
$separator = @CRLF
Global $chars = StringSplit($string, "") ; Convert to array.

$limit = $chars[0] ^ $totalchars + 1 ; Pre-calculate the size so that we do not have to ReDim
Global $array[$limit] ; Declare as Global to minimize Parsing time

For $j = 1 To $totalchars ; Loop and increase "indent (the position to add next character)"
    Fill($j) ; Call the fuction to fill a full row
Next

FileWrite($output, _ArrayToString($array, $separator)) ; Save
Next

C:\Users\admin\Desktop\stringpermutation.au3 (15) : ==> Array maximum size exceeded.:

Global $array[$limit]

Global $array[^ ERROR

cant wait until this limitation is removed

Edited May 12, 2010 by IchBistTod

[James]

cant wait until this limitation is removed

I get the same problem. Although a quick glance, I couldn't see what's going wrong with it. AutoIt can definitely handle a 36 dimension array, I've done hundreds before.

James

[IchBistTod]

I get the same problem. Although a quick glance, I couldn't see what's going wrong with it. AutoIt can definitely handle a 36 dimension array, I've done hundreds before.

James

its the number of elements in a single dimension that it can not handle.

If broken into a muti-dimensional array or if using direct memory structures was used this limitation could be bypassed.

Edited May 12, 2010 by IchBistTod

[UEZ]

yes

I was trying to crack my 36 character password

for $xi=1 to 36
    $array = ""
    $separator = ""
$string = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()' ; The Set of Characters to work with.
$totalchars = $xi ; Lenght of every "word"
$output = @ScriptDir & "\TextList.txt" ; File to save to.
$separator = @CRLF
Global $chars = StringSplit($string, "") ; Convert to array.

$limit = $chars[0] ^ $totalchars + 1 ; Pre-calculate the size so that we do not have to ReDim
Global $array[$limit] ; Declare as Global to minimize Parsing time

For $j = 1 To $totalchars ; Loop and increase "indent (the position to add next character)"
 Fill($j) ; Call the fuction to fill a full row
Next

FileWrite($output, _ArrayToString($array, $separator)) ; Save
Next

C:\Users\admin\Desktop\stringpermutation.au3 (15) : ==> Array maximum size exceeded.:

Global $array[$limit]

Global $array[^ ERROR

cant wait until this limitation is removed

According to help file 1D arrays are limited to 0x1000000 -> 16777216 elements!

Btw, the calculation for the array dimension is an exponential function -> $limit = $chars[0] ^ $totalchars!

Did you realize what amount of memory you will need for your string? Or how long it will take to bruteforce?

BR,

UEZ

Edited May 12, 2010 by UEZ

[Shafayat]

Well 36 character long password is a bit of overkill, mate.

Question 1. How do you remember that long a password?

Question 2. When do you wish that password to be cracked? After a few billion years?

[James]

its the number of elements in a single dimension that it can not handle.

If broken into a muti-dimensional array or if using direct memory structures was used this limitation could be bypassed.

Like UEZ said, AutoIt can handle a thousand dimensions and more.

James

[wraithdu]

Another way to do this is to use my _ArrayCombinations and _ArrayPermute functions from Array.au3. You would create combinations from your total element set in the size of your password, for example create combinations of 8 characters from the 26 letters of the alphabet, then permute each combination for all possible passwords.

Edited May 12, 2010 by wraithdu

[monoceres]

Remember, the number of permutations are n!. Go figure what happens with 36 elements

[James]

Remember, the number of permutations are n!. Go figure what happens with 36 elements

Valik cries a little bit

[wraithdu]

Hehe, an 8 character password from just lowercase letters... 62,990,928,000 different possibilities.

[James]

Hehe, an 8 character password from just lowercase letters... 62,990,928,000 different possibilities.

Valik just caused a massive flood. He will forever hate you.

[Datenshi]

26^32 = 1.90172246 * 10^45

English alphabet, 26chars..32 characters in password.

I put together a generator before(Not much of the code was done by me), so i could try and break my wlan password. Generates 00000000 - 99999999

$outputlen = 8
$inputlen = 10
dim $input[$inputlen] = [0,1,2,3,4,5,6,7,8,9]
dim $index[$outputlen]
$fhandle = fileopen("numbersLF.txt",1)

$nMaxVal = $inputlen ^ $outputlen

$msg = ""

for $nCounter = 1 to $nMaxVal

    $output = ""
    for $i = 0 to $outputlen-1
        $output &= $input[$index[$i]]
    next
    FileWriteLine($fhandle,$msg & $output & @LF)

    $val = $nCounter

    for $n = $outputlen-1 to 0 step -1
        $index[$n] = mod($val,$inputlen)
        $val = int($val / $inputlen)
    next
    sleep(0)
next

Ended up with about 1 million different passwords in my database, then "attacked" my password with the GPU, Tried about 20k passwords a second if i remember correctly(hash table). Without precomputed hashes id get max 6000keys/s

Edited May 13, 2010 by Datenshi

[IchBistTod]

According to help file 1D arrays are limited to 0x1000000 -> 16777216 elements!

Btw, the calculation for the array dimension is an exponential function -> $limit = $chars[0] ^ $totalchars!

Did you realize what amount of memory you will need for your string? Or how long it will take to bruteforce?

BR,

UEZ

using multiple processes on my 16 core server, and creating a database out of the passwords, it shouldn't take too long.

and the amount of memory, It has 32 gigs of RAM(also I have found by emptying the working set of the process as its permutating strings it keeps the RAM used per process down to 8MB[from 2GB]) + 1TB (2x 216GB SSD) SSD. seperating it into 16 processes, it shouldnt take too long. 3.5GHz/core.

The issue is just getting passed the limitation in the number of elements storable in one array.

Well 36 character long password is a bit of overkill, mate.

Question 1. How do you remember that long a password?

Question 2. When do you wish that password to be cracked? After a few billion years?

1. Its a set of uper, loswer case, numbers and symbols that put together have meanings.

2.once I get the database put together(should take a few weeks to make the database) any password between 1-26 characters could be cracked via a mysqlite query in a matter of seconds.

so the few weeks of waiting for my server to generate the database of passwords(and their MD5 equivalents) this could be a useful tool for decoding MD5 hashes, or even just a proof of concept, for such purposes.

I already got this working on passwords up to 4 characters long.

[IchBistTod]

Like UEZ said, AutoIt can handle a thousand dimensions and more.

James

this is exceeded using this string abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*() by the third level of permutation

[IchBistTod]

Remember, the number of permutations are n!. Go figure what happens with 36 elements

as I said, with my string it exceeds the number available by the 3rd level.

[JRowe]

IchBistTod, google Rainbow Tables. Further discussion on this site is not advised. The concept and the math behind it, though, are fascinating, and you'd probably enjoy learning about them.

[IchBistTod]

IchBistTod, google Rainbow Tables. Further discussion on this site is not advised. The concept and the math behind it, though, are fascinating, and you'd probably enjoy learning about them.

im just waiting for either someone else, or to find the spare time for me myself to be able to overcome the limitation with array for the permutation issue.

I wont further discuss what im using it for, or post the code on the forums for my application of the permutation script, because I know some people could use it for bad uses.

But im sure we are all curious beyond that use even just to get past the limitation and see just how far this permutation can go.

On another note rainbow tables seem interesting, but the method im employing with storing all possible info in a database via permutation is much faster and much more effective(takes about 5 seconds to complete a query even for salted hashes) but thats the end of discussion on MD5 hashes in this thread.

Edited May 13, 2010 by IchBistTod