C question
Forum: Programming and Scripting
Topic: C question
started by: curaga
Posted by curaga on Jan. 12 2008,13:35
I want to have a program output all possible words up to 30 letters, like:a
b
..
aa
ab
..
aaa
aab
aac
I tried some methods, but the only one that worked was creating a loop for every depth. There must be a simpler way to do this. Any ideas?
Edit: I wish to test my RSA password strength, how long it would take to break it.
Posted by mikshaw on Jan. 12 2008,15:03
Check out regular expressions. I don't know how they work in C, but there is probably more than one way to set it up.There are also security tools available to test things like password strength.
Posted by curaga on Jan. 12 2008,15:12
Too bad John doesn't support RSA ;)
Posted by curaga on Jan. 12 2008,18:10
Thanks. All that was needed was Bash afterall. With the regex syntax {a..z} 
Posted by curaga on Jan. 12 2008,18:23
Hm. Appears that after 10 letter words or so bash runs out of memory. And consumes all ram and 100+mb swap. So it isn't practical for long words, which I need 
Back to drawing board..
Posted by WDef on Jan. 12 2008,21:35
For doing a whole lot of permutations, something like C is going to be a lot quicker than a high level scripting language like bash.AFAIK there's no such thing as regexes in C with the standard libraries. You have to match and extract strings from first principles using string functions, it's a pain in the balls.
I recall there may be a non-standard lib for C that does regexes though. C++ does do regexes.
Do you have a reason to avoid looping? I expect most approaches would most likely loop to do this.
EDIT: googling yields this:
< http://linux.duke.edu/~mstenn....#SEC185 >
If you had a lot of perms to do, maybe try the GSL library.
EDIT1:
echo {a..z} needs version 3 of bash. No wonder I didn't recognize this.
Posted by ^thehatsrule^ on Jan. 12 2008,23:58
| Quote |
| Do you have a reason to avoid looping? |
Posted by WDef on Jan. 13 2008,02:07
Perl can do it in one line in a shell:| Code Sample |
| $ perl -e 'for $i( "a" ... "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" ){print $i, "\n"}' |
If you want more complicated eg both upper and lower case plus digits etc I can post a solution.
Posted by curaga on Jan. 13 2008,10:58
I didn't have a specific reason to avoid loops, I'm just lazy when I noticed I'd have to do 31 for-loops and long if lines.Thanks WDef, I knew there had to be a simpler way than 40+ lines of C code.
Since I have a comparably low processor, P3 1Ghz, I will probably output that to a file and trim it in some ways. My password consists of 4 lowercase words of english, finnish and quenya. I consider it quite strong, but still want to test how long it would take to break on my comp. Someone knowing me might have this information also, so I will strip at least these: all lines containing 3+ of the same letter (aaa..), all lines containing x, z, or q because they are very rare (and I didn't use them ;)), and some combinations not even remotely words (gaga).
No piping that to a file though, it would take (only!) about 4 * 10^23 exabytes.
Posted by curaga on Jan. 13 2008,11:09
One more thing to ask. Since bash wants to read the whole set before going into it's for loop, could perl handle that line-by-line?So that I wouldn't waste all my ram+swap and then find out the script got killed before even starting.
The bash version:
for line in `theappthatliststhemall`; do
echo $line | openssl rsa -noout -text -passin stdin -in mykey
done
Edit: I would need the finnish letters of ä and ö also. Substituting ö for z in your one-liner did not print them..
Posted by WDef on Jan. 13 2008,11:14
I'm don't think 4 chars of anything is very strong, though I'll have to look up what quenya is, or ask some Scandinavian friends!Even that Perl one-liner will get through the full lower case 4-char password space in no time.
You probably know that each char of pw length increases the brute force crack time exponentially.
Even with humongous computing resources, brute force is likely to be a waste of time on good long random passwords from a wide space of chars including %!@#/\| ., etc. You start measuring crack times in aeons. The weakness is usually in the relative non-randomness of the passphrase (recognizable words etc) or the encryption implementation itself.
Posted by curaga on Jan. 13 2008,11:24
It's 4 words, not 4 chars. It's 30 chars total..BTW, Quenya is Tolkien's high elvish. It's spoken in the movies too. That's a fun part too, as the subtitles say different things than the actors ;)
Posted by WDef on Jan. 13 2008,11:43
| Quote |
| My password consists of 4 lowercase words of english, finnish and quenya. |
Ah! Then that's a different problem. I don't think any cracker in their right mind is going to try to brute force a 30-char passphrase. Instead, they'll do a dictionary-based attack using the three nominated languages, perhaps first trying to narrow the search space using word frequencies. But I'm not an expert.
I'm sure the answer to your Perl questions is yes but I have to eat now.
Posted by curaga on Jan. 13 2008,11:51
Sure, go have a meal.
Wordlists, well, since I'm pretty much the only one using Quenya in a password, I highly doubt anyone has put a wordlist up for it. And then there's the fact both finnish and quenya are suffix-based, ie a words meaning is modified by modifying the word, instead of prepositions like in english. So there are countless variations of a single word.
Posted by WDef on Jan. 13 2008,15:24
I have my doubts about this being a practical test for hardness at least in this particular universe and not for a passphrase built from words - nonetheless, this should work in principle with those Finnish chars in the set.Here I'm testing it on a blowfish encrypted file 'encryptedfile' with a simple 2-char passphrase "at", which it brute force cracked in about 1 second.
Change the openssl command string to suit your rsa key cracking issue.
| Code Sample |
#!/usr/bin/perl # curagacrack.pl my $n = 30; # max len of passphrase my @set = ( "ä", "ö", "a" .."z" ); # ranges and lists to permute my $result; sub create_perm($$){ my($cur,$max)=@_; if($cur>=$max){ # print "$result\n"; setpgrp (0,0); system("echo $result | 2>/dev/null /opt/tor/local/bin/openssl bf -pass stdin -d -in encryptefile -out out.txt && file -b out.txt | grep -q '^ASCII text' && echo -n 'Found passphrase: ' && echo $result && kill 0"); return; } for(@set){ substr($result,$cur,1)=$_; create_perm($cur+1,$max); } } for ($j=1;$j<=$n;$j++){ create_perm(0,$j); } |
That will run the openssl command on each loop iteration (slow) and exit rudely when it is successful. For a 30 char passphrase this may not be within the lifetime of this universe; you might like to prove the concept on a short passphrase.
I found the permutation code on another board and adapted. There is other code on the perlmonks board which is probably more efficient.
It would be quicker to directly compare against the known password string also.
This doesn't filter out aaa etc. Close the shell to kill it off, I didn't put a signal trap in.
(Revision for me since if I don't so a little Perl every few months it starts to look like Finnish to me ;=) ):
Posted by humpty on Jan. 13 2008,16:05
yeh, wdef's code is somewhat similar to some c code i used before to generate strings;just change MAX to 30 and the 'check' routine.
| Code Sample |
#include <stdio.h> #define MAX 4 int check (char *s) { printf ("%s\n", s); if (!strcmp (s, "help")) return (1); return (0); } //-------------------------------------- char s[MAX+1]; int try_again (int pos) { char c; s[pos+1]='\0'; for (c='a'; c<'z'+1; c++) { s[pos] = c; if (check (s)) return(1); //success! if (pos == MAX-1) continue; if (try_again (pos+1)) return(1); } return (0); } //-------------------------------------- int main () { if (try_again (0)) printf ("cracked :)\n"); else printf ("failed :(\n"); } |
the trick is to recurse, but to also use a global var so you don't blow the stack memory!
Posted by curaga on Jan. 13 2008,16:31
I don't understand this part:if (!strcmp (s, "help")) return (1);
So if the string is not found, return success?
Posted by WDef on Jan. 13 2008,16:33
Ah - that's the perversity of Cthe strings are equal when strcmp fails!
Posted by curaga on Jan. 13 2008,16:36
Agreed.. Weird indeed, considering the function is "compare strings".How about a modification to the perl code similar to dd, that when you receive SIGUSR1 you output where you are going?
Posted by WDef on Jan. 13 2008,16:37
There's one problem with openssl for this brute forcing purpose: it will output binary garbage and return success when given certain incorrect passphrases. So it appears to decrypt when it doesn't.As a workaround, I've just edited the example above so it runs cat on the outputted file - it it isn't text, cat will return 1 and the program won't exit. That should get rid of false positives (I think).
Posted by curaga on Jan. 13 2008,16:42
Um, I didn't know rsa used blowfish?
Posted by WDef on Jan. 13 2008,16:44
I dunno. I'm just using openssl on a blowfish encrypted file to test the thing so I don't muck around with keys. Change it to do rsa.And I was wrong about cat. Wonder where I got that idea .. back in a minute with another way to discard false positives.
Posted by curaga on Jan. 13 2008,16:50
I think it's not needed. With rsa, if the phrase is correct, it outputs the unencrypted contents to stdin, but I've never seen it output binary garbage. For returning 0 with certain passphrases, I've yet to see that..How would you implement the signal trap for SIGUSR1 to print $result?
Posted by curaga on Jan. 13 2008,16:54
Hey, changing Vulcanian to Finnish... 
Ei jaksa uskoa että tämä muka näyttää oudolta :P
Posted by WDef on Jan. 13 2008,16:57
No offence intended about Finnish - if it reads like Perl to me it must be a very nice language! But I don't speak it.RSA: That's good to know, so not a problem. Are you sure? With a 3-char passphrase I hit about 7 false positives out of many thousands before hitting the real passphrase. It doesn't do it on all incorrect passphrases. Perhaps only with certain ciphers, I don't know. Have seen that complain before but I can't recall the cipher. Of course, it can be seen as a benefit precisely because it can slow brute forcing.
Posted by curaga on Jan. 13 2008,17:28
I'm not sure, but I did go through about 15mb of wordlists without a single false positive.
Posted by WDef on Jan. 13 2008,17:36
OK. One workaround for my blowfish example, assuming the unencrypted source/key was ASCII text, is to use the file command and only let through decrypted results that are plain ascii. [Editing that into the post anyway.]
Re SIGINT - it should print the successful password before exiting. Or, did you mean you want to know how far we got through the perms before quitting without success? (ie what subset is not the passphrase?).
For these tests I'm encrypting a text file with:
openssl bf -in plaintext.txt -out encryptedfile
Posted by curaga on Jan. 13 2008,17:52
Here's my current one, I know nothing of perl, but still edited it :^)| Quote |
| #!/usr/bin/perl # curagacrack.pl my $n = 30; # max len of passphrase my @set = ( "ä", "ö", "y", "a" .. "p", "r" .. "v" ); # ranges and lists to permute my $result; sub create_perm($$){ my($cur,$max)=@_; if($cur>=$max){ print "$result\n"; setpgrp (0,0); system("echo $result | 2>/dev/null openssl rsa -noout -text -passin stdin -in mykey && echo -n 'Found passphrase: ' && echo $result && kill 0"); return; } for(@set){ substr($result,$cur,1)=$_; create_perm($cur+1,$max); } } for ($j=8;$j<=$n;$j++){ create_perm(0,$j); } |
Oh, with the SIGnalling I meant that since it goes faster if it doesn't print every tried option, if I wanted to know where it's going before it has finished, I'd send it a SIGUSR1 and it would print the current $result and continue guessing.
Is perl really this light? Top shows only 1% cpu usage with this, and my system feels faster than using compiled C variants.
Well, back to the filtering.
for(@set){
substr($result,$cur,1)=$_;
create_perm($cur+1,$max);
}
I assume this part should be changed to something like this:
for(@set){
substr($result,$cur,1)=$_;
if $result=*aaa* then continue
..
create_perm($cur+1,$max);
}
Posted by ^thehatsrule^ on Jan. 13 2008,18:00
About strcmp:The reason for this is that some compilers give -1 for a < string comparison, and a 1 for a > string comparison, and so a 0 is an exact match.
IMO it's better to explicitly specify the comparison to 0 though to show it (as returning 0 can mean success as well like exit status)
Interesting use of different languages...
Posted by WDef on Jan. 13 2008,18:47
I'm eating again ;(0), then a movie, I'll post later.What it looks like is you want a regex that detects 3 or more repeated adjacent chars as a substring? Or do you only want to filter out passphrases that are just one repeated char for the whole string?
Hacking away by yourself is a good way to get curious about Perl. It's very fault tolerant compared with many languages - it's possible to just guess syntax and get it right sometimes.
Posted by humpty on Jan. 14 2008,15:00
| Quote (^thehatsrule^ @ Jan. 13 2008,21:00) |
| About strcmp: The reason for this is that some compilers give -1 for a < string comparison, and a 1 for a > string comparison, and so a 0 is an exact match. IMO it's better to explicitly specify the comparison to 0 though to show it (as returning 0 can mean success as well like exit status) Interesting use of different languages... |
i've always seen 'strcmp' as "string compare and tell me if there's a difference". i suppose 'strdiff' could be more appropriate.
Posted by curaga on Jan. 14 2008,15:56
| Quote |
| What it looks like is you want a regex that detects 3 or more repeated adjacent chars as a substring? |
Thank you, very much. I hope I don't stress you too much
Posted by WDef on Jan. 14 2008,23:50
Stress is my middle name lately (unfortunately).
Posted by WDef on Jan. 15 2008,17:10
Here it is with:1. skips strings containing 3 adjacent same chars
2. only prints current perm on receipt of SIGHUP signal (eg pkill -1 cur.pl), but can print all perms if set $printall = 1.
It's not worth filtering out single char passphrases. There's only one set of them.
So output on my test blowfish encrypted file (password = art) looks like:
| Code Sample |
dsl@box:~# ./cur.pl Skipping result with 3 chars ööö Skipping result with 3 chars aaa Current perm = aoc Found passphrase: art Terminated |
Current perm = aoc was where I sent it a pkill -1 cur.pl from another shell.
Comment out the line that prints skipped perms if you wish, it's for debugging.
| Code Sample |
#!/usr/bin/perl # curagacrack.pl use strict; use warnings; my $n = 30; # max len of passphrase my $j; my @set = ( "ö", "a" .."z" ); # ranges and lists to permute our $result = ""; my $printall = 0; # don't print perms #~ my $printall = 1; # print every perm sub print_perm { print "Current perm = $result\n"; } sub create_perm { my ($cur,$max)=@_; my ($k, $str); if($cur>=$max){ if ($printall == 1){ while ($k lt $cur){ $str .= "\b"; $k++; } print "$result$str"; } system("echo $result | 2>/dev/null openssl bf -pass stdin -d -in encryptedfile -out out.txt && file -b out.txt | grep -q '^ASCII text' && echo -n 'Found passphrase: ' && echo $result && kill 0"); return; } foreach my $c(@set){ substr($result,$cur,1)=$c; if (($max ge 3) && ($result =~ /$c{3}$/)) { print "Skipping result with 3 chars $result\n"; next; } create_perm($cur+1,$max); } } $SIG{'HUP'} = 'print_perm'; for ($j=1;$j<=$n;$j++){ create_perm(0,$j); } |
Posted by curaga on Jan. 16 2008,16:01
Thx. A typo maybe, if printall is set to 1 perl will print all tried options but also complain "using an unitialized value in string lt on line 27". Not a biggie, since I just tested with it set to 1, but will let it go with printall 0.By strings consisting of 1 characters I meant strings like aaaaaaaaaaaa.
Posted by curaga on Jan. 17 2008,15:18
Okay, the fire test began yesterday. I chose a new password of 22 chars for this test, with the same charateristics of my previous one. This to prevent waiting of a lifetime.In order to behave like a smart cracker, I decided to run multiple processes simultaniously. That, with the optimization of skipping permutations with 3+ of the same char, should bring the time to an acceptable window. And will still be an interesting result.
To simulate a multi-core environment, I shared the work to 4 of my (8) comps. Each of them runs two processes, distributed like this:
P1 100Mhz - length 1-3 and 4-6
P1 133Mhz - length 7-8 and 9-10
P3 733Mhz - length 11-13 and 14-16
P3 1Ghz - length 17-19 and 20-23
First three have nothing to do but this, but the final one (my best comp :P) is my main comp, which will be used for daily tasks such as browsing, so the cracking processes are niced to 19 on this comp (I'm on it now, too
)
Posted by WDef on Jan. 17 2008,23:14
Amazing, I didn't think it would actually be useful code! That uninitialized var error is easily fixed. Re: multiple instances - a proper cracking prog would use threads to tackle different slabs of the passphrase space simultaneously.
I've been trying the perl module Algorithm::Permute on this, which is many times faster than that hack above. I've installed it and think I follow how to use it, but am having issues passing its results to openssl via system for unknown reasons.
So I've posted on Perl Monks to try to get some help from those Enlightened Priests of Perl.
When I have it working I'll post the improved code and a module extension - that should speed up your cracking by several orders of magnitude.
Posted by curaga on Jan. 18 2008,13:03
No need for the module ext - I can easily use cpan
Posted by WDef on Jan. 18 2008,16:38
Here is the permute module anyway, for use with the gtk2 .dsl extension which contains perl-5.8.7:< http://www.uploadhut.com/id169109/AlgorithmPermute-pm-5.8.7.dsl >
Turns out my code wasn't broken after all, I just wasn't waiting long enough! Doesn't mean it couldn't be improveable. A few points:
1. It's fast. You can see how fast it is by commenting out the system call to openssl (which slows everything down) and turning printall on ( = 1). The Algorithm::Permute module is written in XS code so is efficient. This is the brand new version of the module (0.11).
2. It doesn't work though perms in lexicographic order ie the earlier program always started with the 1st char in the set etc. I don't follow the order at this stage.
3. As I discovered after adding one, there's no need for a filter to remove adjacent chars that are repeated say 3 times, since, in order to make it repeat chars, you just have to repeat the range or list in @set the number of times that you want to allow repetitions from that subset. We want to allow 2x reprtitions but not 3x, so just repeat the entire contents of your existing @set once.
So for eg in my test:
| Code Sample |
my @set = ( "r", "r", "t", "t", "a" .."d", "a" .."d" ); # ranges and lists to permute |
will produce perms containing 'aa' but not 'aaa' etc.
Here it is:
| Code Sample |
#!/usr/bin/perl # Demonstration brute force password cracker use strict; use warnings; use Algorithm::Permute; #==========================// SETTINGS // ========================= my @set = ( 'a'..'d', 'r', 't', 'a'..'d'); my $printall = 0; # set to 1 to print every perm my $startlen; my $endlen; # Leave the following commented out to do all length perms within @set #~ $startlen = 3; # begin processing with strings of length $startlen #~ $endlen = 5; # end processing with strings of length $endlen #================================================================ my $perm = ""; my $k; my $i; sub print_perm { print "Perm no. $k = $perm\n"; } #================================// MAIN // ======================= $SIG{'HUP'} = 'print_perm'; # print current perm on receipt of sighup $k = 0; my $setlen = $#set + 1; # defaults unless (defined($startlen)) { $startlen = 1 } unless (defined($endlen)) { $endlen = $setlen } unless ($startlen >= 1) { die "Error: startlen must be >= 1" } unless ($endlen >= $startlen) { die "Error: startlen must be <= endlen" } unless ($endlen <= $setlen) { die "Error: endlen must be <= $setlen" } foreach $i ($startlen..$endlen) { my $p = new Algorithm::Permute([@set], $i); my @res; while (@res = $p->next) { $k++; $perm = join("", @res); if ($printall == 1) { print "$k $perm\n"; } system("echo $perm | 2>/dev/null openssl bf -pass stdin -d -in encryptedfile -out out.txt && file -b out.txt | grep -q '^ASCII text'") == 0 && die "Found passphrase \"$perm\""; } } |
EDIT1: added perm counter to sighup print
EDIT2: added variable length string ranges and defaults
Posted by curaga on Jan. 18 2008,17:06
Will try that soon. There's something wrong with your previous 3+ char recognition with long strings (with over 15 chars none got skipped, despite the string ääääääääääääääö having clearly more than three adjacent ä's). I guess that doesn't matter anymore though.Anyway, is it guaranteed that this new algorithm does try every combination?
Posted by WDef on Jan. 18 2008,17:11
if (($max ge 3) && ($result =~ /$c{3}$/)) { should have been (I think)
if (($max >= 3) && ($result =~ /$c{3,}$/)) {
[EDIT: classic mistake confusing string and numeric comparisons ]
If that didn't work would have applied a regex somewhere like:
=~ /(.)\1\1/
which would match any string containing 3 or more identical adjacent chars.
You might notice the similarity to sed syntax. Perl regex's are much easier and more intuitive and you do a lot less escaping of backslashes and brackets and other hassles.
Posted by curaga on Jan. 18 2008,17:24
Is the new algorithm guaranteed to try every combination?
Posted by WDef on Jan. 18 2008,17:31
AKAIK - it's taken from the Algorithm::Permute man page, basically just put in a loop to do all string lengths between 1 and the number of elements in @set.There's also benchmarks on the man page comparing speeds to other implementations.
There may possibly be a faster way of using the module via the callback interface but I'll have to think and maybe post somewhere about that. [ EDIT I doubt it . The callback thing won't take a perm length argument, and the man page warns against trying to change the array mid execution. ]
EDIT: I've updated the above to allow for setting desired string length ranges.
Posted by WDef on Jan. 20 2008,12:26
Yesterday I had a crack at a version using threads, but there were segfaults - I think Algorithm::Permute is probably not thread-safe. Googling reveals this is likely since (a) any module that does not explicitly state it is thread-safe should be assumed not to be, and (b) it's written in XS code and XS code modules are less likely to be thread-safe.Anyway I have some other improvements in mind for speed increases.
Posted by curaga on Jan. 29 2008,18:32
The smaller ones have run through - aka all under 7 chars. That proved my pass isn't 7 chars or less. Oh well.Then I did a quick reschedule - new dial is:
8-9, 10-11, 12-13, 14-15, 16-17, 18-19, 20-21, 22-23; that is, one process goes through two lengths, instead of one going from 8 to 23. These are all running on the main lappy - load averages have floated above 15 for some time now
I haven't yet applied the fix for adjacent chars, maybe I should have? Haven't had time.
Posted by curaga on Feb. 03 2008,07:16
After running one process with the fix for two days, I've come to conclusion it works great.So, I applied it to all, and restarted.
Load averages are only 12 now, so it has a good speedup effect.
Posted by WDef on Feb. 04 2008,04:52
Glad it's working out :=)One inefficiency is it is generating some perms more than once - because we want the module to allow repetition of chars the same perm can come up again. The module's API doesn't seem to have a way to prevent that. However, that's probably outweighed by the speed gains of using the module Cf. Perl code from scratch.
I'm sure there would be more efficient, optimized, purpose-designed cracking progs written in Assembly or something that avoid generating the same perm more than once etc.
In any case, there's still the main holdup - that of trying every combination on openssl, which far outweighs other bottlenecks.
There may be a faster perm Perl module around than this or some Perl programmer has very probably written a better approach - I might have a look.
Regardless, this is still infinitely better than trying to do it by brute force in bash. Perl is much better suited to this type of task.
EDIT1:Thought I'd bookmark this link which discusses migrating a similar type of simple prog from badly-written Perl to much faster C:
< http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/203958 >
EDIT2: This is interesting reading about the (very different) word list approach used in "Crack" by its author:
< http://www.crypticide.com/dropsafe/article/733 >
Posted by curaga on Mar. 25 2008,14:52
Status report. They have been running for 46 days nonstop now. They have punched through about 5 million combinations. This is nice, and still not cracked.About a week ago I ordered a new comp for me; I feel the need for more power
It's a huge bang-for-the-euro combination. Specs:
Core 2 Duo E2160 @3Ghz
2GB Kingston ram 667Mhz (2x 1gb sticks in dual channel)
160gb HD
And, as I'm not a gamer, didn't waste my time with a graphics card. I will put in one of my pci ones, most likely the best, Ati Rage II+dvd.
Total price 267 euros.
It's a really powerful one, hopefully more like 8x my current best one (this P3). As with all my other comps, I will build the OS for it, to gain as much speed as possible. Also this is my first 64-bit capable machine, so I will make the OS fully 64-bit, to get 10-20% more power for some apps. Plus optimize boot speed, and load parts to ram, I like my operating systems blazing
So, when it arrives, and I finish the OS, this cracking will move onto it. Despite having to start over, I'm quite confident that it, with 2 brutal cores, will take my pass down. It's just a matter, and question, of time.
Posted by WDef on Mar. 28 2008,23:19
Wow, your certainly serious about this project! New machine sounds *nice*.I suspect that to do permutation with replacement without producing redundant perms we're supposed to use the Mathematics::Combinatronics module or something.
Best that I either get some help on Perlmonks (probably a good idea), or we work out how to write this in C. I do have access to an A#1 world guru C/C++ programmer at work who might help me if I get stuck. Let's see.
How long before your new box comes onstream?
Posted by curaga on Mar. 29 2008,07:36
It will hopefully be delivered next week *sigh*, as they have all parts but the mobo is backordered.This comp is for other tasks also, I couldn't have afforded a new one just for this
Oh, I use 10 modified versions of your previous perl core, and 1 of the new one with the Permutate module (because the prev ones' starting point could be modified). I agree writing this in C might bring great speed gains also.
Also, the 5 million was just a guess, as my log file only includes *skipped* ones
So hopefully they have gone through more.
Posted by curaga on April 04 2008,16:50
It came today. I just put it together and set clocks; right now it's booting Knoppix toram for stability testing.
Posted by curaga on April 06 2008,14:01
...And Aero64 is 80% finished; it's now a full CLI environment, and the process has started. It's way faster than my old comp. 12000 BogoMips The rest to add is just cream to the cake, X, a WM etc. I think I'll try E17, it looks so beautiful in the videos ;)
Posted by WDef on April 06 2008,14:47
Sounds niceE17 is very interesting, I have run it on my RedHatty install but that usually has KDE for kapps that won't seem to build or run on anything else. The uci in the repo runs on dsl too.
There's a commercial cut down derivative of E17 for embedded systems and other linux with all sorts of built in media support and fancy transitions etc made by FluffySpider in Australia - its libraries are only ~600K. You'll find it running on various MIDs and set top boxes etc.
Posted by curaga on April 09 2008,14:16
It ran the same amount in 5.4 days as the old laptop in 44 days, thus making it 8.15 times faster. My guess was pretty close ;)
Posted by curaga on April 12 2008,10:49
This seems to be turning to my blog. X is up and running, so is E17, and some apps, such as epdfview and Mplayer. It also feels nice to have 4x compiling speed compared to the old laptop while at the same time running the cracking processes that put load averages to 18 ;)
Enlightenment is really beautiful. Beauty at my fingertips, wasn't it. The next apps I need are some officy-ish like Abiword and Gnumeric, and then the question of a browser. I'm torn between Opera 9.5 beta and Firefox 3.0 beta. Opera fan, but 9.5 is too buggy currently. FF 2 would also be a choice, but who wants to use something that old ^^
Then the bad sides: the graphics card. Ati Rage II+dvd. While being advanced for the time, it's too limited for anything but desktop use. No Xrender acceleration. No 3d acceleration. XV is limited to 720- pixels wide movies. On the plus side, the lack of XV doesn't stop me from doing anything; I tested a 1080p H.264 trailer and it ran smoothly.
Posted by pixelbox on April 14 2008,01:35
| Quote (curaga @ Jan. 12 2008,13:23) |
| Hm. Appears that after 10 letter words or so bash runs out of memory. And consumes all ram and 100+mb swap. So it isn't practical for long words, which I need Back to drawing board.. |
It's not as pain in the balls with C,
create file with the words you will search - ie. not in array or string, assign one variable for the current searched word and change that same variable for the new search from the file, it will not have problems with memory
Posted by curaga on April 14 2008,13:45
That way I would have trouble with HD space..
Posted by pixelbox on April 14 2008,15:51
| Quote (curaga @ April 14 2008,09:45) |
| That way I would have trouble with HD space.. |
OK, you're right.
Define letters (and or signs) in array as integer numbers, than create words (loops) as strings in real time calling the number from array, loop the numbers and not strings (ie 4 bytes less per letter). Than final word as string is for check (or count).
1 + (2x2) + (3x3x3) + (4x4x4x4) + .... until 13, thats a lot of combinations which means not HD space in this case but fastest PC work of more than days (months?)... that is also countable (how many flops needs program) = that's not much, but access to the password object is making time needed and thats a lot time if Big HD file or network access for up to 13.
Just a program for looping would be measured in seconds.
Posted by curaga on April 14 2008,17:39
Yeah, that's a good idea, also very much like the one humpty posted earlier. Currently the perl implementation of Wdef is running, I will perhaps create a C program later, but I don't have time until sunday.
Posted by WDef on April 15 2008,13:55
I would use someone else's already-optimized and tested C code or library to do permutations rather than use my own - it's almost certainly likely to be faster, have a better algorithm, and generally work better. There is a non-standard library for this as I recall.Also, I've found a Perl module to do permutations with replacement without generating redundant perms (unlike Algorithm::Permute):
< http://search.cpan.org/~tyemq....duction >
It also claims to have very low zero memory useage.
I don't think it's an XScode module, so i don't know about speed.
Posted by curaga on April 15 2008,15:57
I'm not in a hurry, a custom solution is what I feel like testing anyway..
Posted by WDef on April 16 2008,20:59
One of the Monks on Perlmonks said we might like to try Algorithm::CombinatoricsThis is XScode and so is supposed to be fast, and it does permutations with repetition so it doesn't generate redundant perms.
So you only put the desired ranges in once in the array @set.
It will generate all the perms with replacement, so I've put a regex filter in to skip perms containing 3 adjacent identical chars as Curaga wished. Those perms still get generated but won't get tested on openssl. Not sure which generation cost (redundant perms or perms with more than 3 adjacent chars) is more inefficient - a bit of math would work it it out I suppose.
EDIT: this generates perms in the more or less expected alphabetic order so you can see just how far you are into a particular subset when you send it a SIGHUP to print.
I'd be interested in hearing how this seems to compare speed-wise.
| Code Sample |
#!/usr/bin/perl # curagacrack2.pl # Demonstration brute force password cracker #2 using use Algorithm::Combinatorics use strict; use warnings; use Algorithm::Combinatorics qw(variations_with_repetition); #==========================// SETTINGS // ========================= my @set = ( 'a'..'z', 'A'..'Z', '0'..'9' ); my $skip = 1; # filter: set to 1 to skip any perm containing 3 adjacent identical chars my $printall = 0; # set to 1 to print every perm my $startlen; my $endlen; # Leave the following commented out to do all length perms within @set #~ $startlen = 3; # begin processing with strings of length $startlen #~ $endlen = 5; # end processing with strings of length $endlen #================================================================ my $perm = ""; my $k; my $i; sub print_perm { print "Perm no. $k = $perm\n"; } #================================// MAIN // ======================= $SIG{'HUP'} = 'print_perm'; # print current perm on receipt of sighup $k = 0; my $setlen = $#set + 1; # defaults unless (defined($startlen)) { $startlen = 1 } unless (defined($endlen)) { $endlen = $setlen } unless ($startlen >= 1) { die "Error: startlen must be >= 1" } unless ($endlen >= $startlen) { die "Error: startlen must be <= endlen" } unless ($endlen <= $setlen) { die "Error: endlen must be <= $setlen" } foreach $i ($startlen..$endlen) { my $p = variations_with_repetition(\@set, $i); my $c; while ( $c = $p->next) { $k++; $perm = join("", @$c); if ($printall == 1) { print "$k $perm\n"; } if (($skip == 1) && ($perm =~ /(.)\1\1/)){ next } system("echo $perm | 2>/dev/null openssl bf -pass stdin -d -in encryptedfile -out out.txt && file -b out.txt | grep -qE '^ASCII.+text'") == 0 && die "Found passphrase \"$perm\""; } } |
Posted by WDef on April 18 2008,19:50
FYI, custom solutions notwithstanding: I do like fooling around with Perl on this - nonetheless I just compiled a C prog called "combina".This not surprisingly does appear to be faster than the Perl, but I was pleasantly surprised to see not as much faster as I might have expected. Rough "tests" suggest something like 20-50% faster, but that's just trying a few short passwords and it will depend on what password and the order im which the perms are generated, so it might average out to not much difference (or not). XScode is, in fact, interfacing with C libaries via Perl as I understand(?) it so, indirecly, it is a way of using C.
| Code Sample |
| time combina -a -A -n -p 1 -k 5 | ( while read PW; do if 2>/dev/null openssl bf -pass pass:$PW -d -in encryptedfile -out out.txt; then if file -b out.txt | grep -qE '^ASCII.+text'; then echo "Found passphrase $PW"; exit; else continue; fi; fi; done ) |
This found the highly challenging (not) password "zz" in 20 sec.
The Perl above took 25 sec over the same name space. There was a greater difference with other passwords.
(I'll post combina.uci to the repo anyway.)
Posted by curaga on May 07 2008,16:31
After some months of intense hacking away, and still not gotten even close, I decided to give up ;) I was hoping I could find out the time needed to crack it, but it's way too good for that. I did prove it's really good though, and that it would take years even with a top notch comp.
Posted by WDef on May 08 2008,11:38
Got me looking at some Perl modules I'd never looked at anyway, which was interesting.