Re^2: gettin back crypted password

If we're going to brute force it, let's at least be clever :-). One assumption that cuts down the complexity immensely is that for a user password, it needs to be typed from the keyboard. That limits us to printable ASCII. According to my local ascii man page, printable ASCII starts at 32 (SPACE) and ends at 126 (~). However, one flaw in your attempt is that it assumes a password of exactly 8 characters. No more, no less. Let's see if we can fix that. What we really have here is a base-94 counting system (there are 95 characters in the range from 32 - 126). So, let's see if we can implement that.

use strict;
use warnings;

use Math::BaseArith;

my $max_length = 8;
for(my $i = 0; $i < 95**$max_length; $i++) {
   my @base;
   if ($i) { #can't take log(0)
      @base = ("95") x (int((log $i) / (log 95))+1);
   }  
   else {
      @base = ("95") x (int((log 1) / (log 95))+1);
   }  
   
   my $num = encode($i, \@base);
   my $password = join('', map {chr($_+32)} @$num);
}
[download]

Now for the complexity analysis. Generating every string of up to length 8 with each character being chosen from a pool of 95 available will create (95**(8+1))-1 strings. By my math, that's 6634204312890624 strings...which is about 0.03% of your estimate. At a billion a second, this will take 19 years...a significant savings over 584!

P.S. I used ascii 32 - 126 because it was contiguous. I leave it as an exercise to the reader to add things like tab that can be typed in a keyboard but are not in that range. :-)

thor

Feel the white light, the light within Be your own disciple, fan the sparks of will For all of us waiting, your kingdom will come

Update: Changed the number base from 94 to 95, as per 5mi11er's observation. Also noted that I misplaced a decimal on the time calculations...it's a whole lot better than I thought!

Comment on Re^2: gettin back crypted password Download Code

Replies are listed 'Best First'.
Re^3: gettin back crypted password by Anonymous Monk on Mar 09, 2005 at 14:22 UTC
All control characters are easily typed from the keyboard as well. For instance, a newline can be inputted by typing: `CTRL-V CTRL-J` [download] at least, on any Unix terminal I know (and didn't set 'stty lnext' to something else). I can generate characters from the 128+ range by using the ALT key, which is xmodmapped to the appropriate modifier. I still regulary use passwords with control characters in them - a very old habit I picked up when I first starting using computers. Way back, in the late 70s, we had hardcopy terminals (terminals without a monitor, but a keyboard and a paper roll). Everything a program outputted, appeared on paper. Everything you typed as well, including your password. And paper doesn't have a clear screen function. The only way to not have your password widely known was to use control characters in the password. But you had to be careful, not all control characters were non-printable.... No, this wasn't a very secure system.	[reply] [d/l]
Re^3: gettin back crypted password by 5mi11er (Deacon) on Mar 09, 2005 at 17:58 UTC
Actually, it's 95 characters. 126-32=94, but the space character is valid, as is the ~, subtracting on the included lower bounds, rather than on the first excluded lower bound, means your answer is off by one. How many valid characters are between '2' and '6' inclusive? 6-2 = 4, but the valid characters are 2,3,4,5 & 6. 5 of them. -Scott	[reply]
Re^4: gettin back crypted password by thor (Priest) on Mar 09, 2005 at 19:46 UTC
My fault. Though my error in logic was slightly different. When we use the digits 0-9, we're doing base 9+1=10. Here, we want to use the digits 32-126, except shifted down by 32, so we subtract 32 from both endpoints to get the range 0-94. Thus, we want to use base 94+1=95 arithmetic. I'll update my original node. Thanks! thor `Feel the white light, the light within Be your own disciple, fan the sparks of will For all of us waiting, your kingdom will come`	[reply]