Dictionary File Vs. On-the-fly Processing

[imported_=Tron=]

The word generator is extremely simple, it takes less than ten CPU instructions to increment "aaaa" to "aaab".

Reading a word from a file would take hundreds, if not thousands, of CPU cycles. Add to that the actual physical speed of your hard disk.

I would expect an on-the-fly version to run several times faster.

I have to admit that your reasoning does seem to make sense and it might just be that you will prove me wrong in my assumption. Still, although not directly relevant to this discussion, a dictionary based attack will still outperform your approach since people tend to choose passwords using actual words, or modifications/combinations of existing words, instead of completely random letter sequences.

Anyway enough talk out of me, I'll make a dictionary file, compare the two methods, and produce my findings.

Sounds like a good idea, it will be interesting to take part of your findings.

[Virchanza]

I have to admit that your reasoning does seem to make sense and it might just be that you will prove me wrong in my assumption.

Here's what I'll do:

I'll capture the handshake for a WPA access point whose password is "zzzzz".

I'll create a dictionary file that has all the combinations from "aaaaa" to "zzzzz". I'll time how long Aircrack takes to crack the password. Then I'll use the built-in generator and see how long it takes. I think that's a fairly fair way of measuring it

Still, although not directly relevant to this discussion, a dictionary based attack will still outperform your approach since people tend to choose passwords using actual words, or modifications/combinations of existing words, instead of completely random letter sequences.

Ah of course, you have me there. This generator would be useful to use against people who "know what they're doing", for instance when I was back home my wireless key was "qwertyaaaaazzzzz56789sk".

Sounds like a good idea, it will be interesting to take part of your findings.

I'll got some time to spare now so I'm gonna make up the dictionary file and see how it compares to the "on-the-fly" version.

[Virchanza]

OK I have some results.

I cracked the "biscotte" password using two methods:

Dictionary File Method) I created a dictionary file and then ran Aircrack against the dictionary file.

On-the-fly Method) I assimilated the dictionary generator algorithm into Aircrack and tested combinations on-the-fly.

The Dictionary File Method took 90 seconds to test 10738 keys (giving an average of 119.31 k/s).
The On-the-fly Method took 100 seconds to test 10738 keys (giving an average of 107.38 k/s).

Without taking into account how long it took to create the dictionary file, we can see that the Dictionary File Method was faster (it took 0.9 times as long).

When I started the Dictionary File Method, the "keys per second" immediately jumped to 115 k/s and they stayed steady at that rate for the entire cracking process. The highest peak was about 117.40 k/s.
However, when I started the On-the-fly Method, it started off at 20 k/s and it took about 10 seconds to climb to 116 k/s, at which point it stayed steady for the rest of the cracking process. The On-the-fly method peaked just a tiny bit higher than the Dictionary File Method, at about 117.50. My guess is that during the first 10 seconds, the CPU cache organises itself so that the generator algorithm gets executed as quickly as possible. After the first 10 seconds, the On-the-fly Method is 0.0008% faster (which of course is negligible).

The problem with this test is that the first 10 seconds represents a large percentage of the total time taken to crack the key (about 11% of the total time). If we were to do a longer test that lasted a few hours, 10 seconds would become negligible, and the difference between the cracking times would be less than one thousanth of a percentile (0.0008%). To put that into perspective, it'd be like comparing "5 days and 20 minutes" against "5 days and 25 minutes".

Here's the benefits as I see them with the On-the-fly Method:
1) Extra time isn't wasted creating a dictionary file (note, in all the above measurements, I haven't included the time taken to create the dictionary file). I'm sure a lot of you know how long it can take to create a large dictionary file.
2) When the On-the-fly Method finds the password, the generator stops immediately and the cracked password is displayed on-screen. However, when you're making a dictionary file, you need to create all the combinations, you can't make the dictionary file generator stop making words at "biscotte".
3) You don't need 156 GiB of free hard disk space to store the dictionary file.
4) It's more convenient not having to flute around with a dictionary file.

Next thing I'm going to do is run a longer test with a bigger dictionary. Hopefully this will show that the On-the-fly Method is a vast improvement over the Dictionary File Method. (Really I should have done this straight away to show how superiour the On-the-fly Method is, but I didn't feel like leaving my laptop running for 5 hours cracking a password, also my hard disk is due a defragment so I didn't wanna f*** it up further with a big dictionary file).

OK so here's exactly what's going on:
1) I downloaded the source code for Aircrack.
2) I saw that Aircrack uses the "fgets" function to read words from a dictionary file.
3) I wrote a generator algorithm to masquerade as "fgets".
4) I assimilated my code into the Aircrack code making as little alterations as possible.

For people who want to try out the on-the-fly generator, here's what to do:
1) Download the source code for the latest Aircrack (rc1 or something like that)
2) I will make a subsitute "aircrack-ng.c" available for download.
3) Put my "aircrack-ng.c" file in place of the original in the source code folder.
3) Make, make install, try it out.

Give me a day or two to finish my changes to "aircrack-ng.c". (I don't like stamping my name on something and distributing it until I'm satisfied it meets my standards).

One more thing: My generator algorithm creates random words such as "fgb8fes". Obviously, you wouldn't find such a word in a normal English dictionary. Less-security-conscious people might create passwords such as "football", and of course if this is the case then you're better off using an English dictionary file than using my algorithm. However, if you're dealing with somebody who knows what they're doing, somebody who sets their password to "nd74k86ed9d36bits2hjitdwfhu", then the On-the-fly Method takes no prisoners.

[Barry]

One more thing: My generator algorithm creates random words such as "fgb8fes". Obviously, you wouldn't find such a word in a normal English dictionary. Less-security-conscious people might create passwords such as "football", and of course if this is the case then you're better off using an English dictionary file than using my algorithm. However, if you're dealing with somebody who knows what they're doing, somebody who sets their password to "nd74k86ed9d36bits2hjitdwfhu", then the On-the-fly Method takes no prisoners.

Thing is, how long would it take to actually get to "nd74k86ed9d36bits2hjitdwfhu"? From now on all my wpa keys are starting with a z.

[ShadowKill]

Thing is, how long would it take to actually get to "nd74k86ed9d36bits2hjitdwfhu"? From now on all my wpa keys are starting with a z.

I usually start attacking from z so hell....go for it

[imported_=Tron=]

Interesting result indeed. Nevertheless you could argue that as a starting point it will still be adviceable to use a standard dictionary approach to check for actual words. If this method fails your approach might be something to try out, although it would be nice to be able to skip the words already tested using the dictionary approach. With an additional wordlist including random characters this would be easy enough to achieve simply by extracting all duplicates from the second list, but I am not sure how to implement it into your approach without losing the benefits it poses.

As a side note someone who really knows what they are doing will be using both upper and lower case characters, and other symbols besides numbers and letters as well.

[Virchanza]

Interesting result indeed. Nevertheless you could argue that as a starting point it will still be adviceable to use a standard dictionary approach to check for actual words.

Ah yes, this would be the first approach.

If this method fails your approach might be something to try out, although it would be nice to be able to skip the words already tested using the dictionary approach. With an additional wordlist including random characters this would be easy enough to achieve simply by extracting all duplicates from the second list, but I am not sure how to implement it into your approach without losing the benefits it poses.

Firstly you could go through the dictionary file to see if the password is in the dictionary. If that doesn't bear any fruit, next thing to do is go through the dictionary "filling in the spaces" for words that don't exist. In this manner duplicate tests can be avoided.

As a side note someone who really knows what they are doing will be using both upper and lower case characters, and other symbols besides numbers and letters as well.

My generation algorithm currently asks the following questions:
1) What's the minimum length of the password? 4
2) What's the maximum length of the password? 8
3) Do you want to use all characters of ASCII (Y/N)? N
If not, Specify the list of characters to use: abcdefABCDEF
4) What word do you want to start counting at? dAcbaD

I realise how ridiculously long it would take to crack a random 10-letter password, which is why I'd be interested in making multiple machine work together on cracking it.

[imported_=Tron=]

Firstly you could go through the dictionary file to see if the password is in the dictionary. If that doesn't bear any fruit, next thing to do is go through the dictionary "filling in the spaces" for words that don't exist. In this manner duplicate tests can be avoided.

Yes exactly, but this would require you to actually create a wordlist with the spaces filled in, or at the very least make your script check the dictionary to determine which words already have been tested, thereby diminishing any speed benefits from your approach. Or am I missing something?

[Virchanza]

Yes exactly, but this would require you to actually create a wordlist with the spaces filled in, or at the very least make your script check the dictionary to determine which words already have been tested, thereby diminishing any speed benefits from your approach. Or am I missing something?

Say we have a dictionary file as follows:
aaa
aab
aad
aae

Firstly, we run the dictionary file against the handshake to see if the admin was stupid enough to make the password "football". If that fails, the generator algorithm can start off counting at "aaaa", but it won't try that combination straight away, it will be advancing through the dictionary file. It will see that the dictionary file already has "aaaa", so it will increment to "aaab". It will see that this also is in the dictionary file. Next it will increment to "aaac", and seeing that this is not in the dictionary file, it will test that combination. (The words in the dictionary file must be in alphabetical order for this to work).

The original dictionary file might be quite big, maybe even a gigabyte, but nowhere near the size of the file that would be needed for random words like "afs3228ssdf".

I think this would be a very good solution, i.e. to run the dictionary file and then "fill in the gaps" afterwards. Another good thing to do would be to run the "lowercase uppercase permutation" algorithm on the dictionary file.

So altogether it would be like:
1) Try the dictionary file first, using all uppercase/lowercase permutations (e.g. football, FOOTball, footBALL, etc.)
2) Run through the dictionary file filling in all the gaps

[thorin]

The word generator is extremely simple, it takes less than ten CPU instructions to increment "aaaa" to "aaab".

Reading a word from a file would take hundreds, if not thousands, of CPU cycles. Add to that the actual physical speed of your hard disk.

The later should only be true if you're repeatedly opening and closing the file.

There is lots of research on the time space trade off:
http://www.google.ca/search?q=passwo...pace+trade+off

The latest I recall seeing argued that using GPUs the trade off may be proven false, however, as far as I know using modern CPUs is still slower (over the long term, i.e.: with a huge dictionary/generation space). [Unless of course you're talking a Beowulf cluster or something like that].