|
Re: gettin back crypted password
by merlyn (Sage) on Mar 08, 2005 at 04:59 UTC
|
| [reply] |
Re: gettin back crypted password
by Zaxo (Archbishop) on Mar 08, 2005 at 05:05 UTC
|
The way to use crypt for passwords is to apply it to an offered password and see if the crypted hash matches the stored one. That way, the password is stored nowhere on the machine. That is a feature.
It all works because the encryption is irreversable.
| [reply] |
|
|
Actually, it works because the encryption is well-defined. You can't decrypt because the encryption is irreversible.
| [reply] |
|
|
| [reply] |
Re: gettin back crypted password
by tilly (Archbishop) on Mar 08, 2005 at 05:00 UTC
|
There shouldn't be. But there is, because when crypt was designed nobody envisioned it being attacked with the kind of computing power that is now routine. However you aren't supposed to do that.
Therefore the answer is that you should use better cryptography and accept that the answer is "no".
UPDATE I got confused about which crypt Perl uses internally. The crypt program on Unix is easily broken. The crypt library call is not. However most people pick bad passwords, so it is easy to just brute-force through likely passwords and you'll successfully "decrypt" a lot of passwords.
| [reply] |
Re: gettin back crypted password
by InfiniteLoop (Hermit) on Mar 08, 2005 at 05:31 UTC
|
As others have mentioned here, the right way to use crypt is to compare the "crypt" of the user entered password with the one stored in the application. | [reply] |
Re: gettin back crypted password
by Anonymous Monk on Mar 08, 2005 at 10:42 UTC
|
Assuming you have traditional, 8 character passwords:
sub decrypt {
my $crypted = shift;
my $str = "";
foreach my $s1 (0 .. 255) {
my $str = $str . chr $s1;
foreach my $s2 (0 .. 255) {
my $str = $str . chr $s2;
foreach my $s3 (0 .. 255) {
my $str = $str . chr $3;
foreach my $s4 (0 .. 255) {
my $str = $str . chr $4;
foreach my $s5 (0 .. 255) {
my $str = $str . chr $5;
foreach my $s6 (0 .. 255) {
my $str = $str . chr $6;
foreach my $s7 (0 .. 255) {
my $str = $str . chr $7;
foreach my $s8 (0 .. 255) {
my $str = $str . $chr $8;
if ($cryped eq crypt($str, $crypted)) {
return $str
}
}
}
}
}
}
}
}
}
}
This will take at most 18446744073709551616 tries. If you do a billion of them per second, it only takes about 584 years at most. Less 293 years expected! | [reply]
[d/l] |
|
|
The only legitimate reason for doing this would be to return to the user their password if they've forgotten it. Because it's impossible, you are better off creating a new random password and emailing them.
Nefarious people don't nessarily have to brute force the actual password - they just need to find a hashing collision. i.e. if password "foo" and "bar" both hash to "abc", then they are identical as far as the password check goes. This may not seem like much of a distinction (especially as the hash is often longer, and the input salted), but it means if the hash algorithm is weak, then it can be exploited. I believe there has been some preliminary weakness in SHA (some researchers suggest that it could be cracked in, say, 75 years rather than 100 years), but overall they appear strong.
And if you allow passwords of length less than 1..
sub decrypt {
my $crypted = shift;
my $str = "";
foreach my $s1 (0 .. 255) {
my $str = $str . chr $s1;
if ($cryped eq crypt($str, $crypted)) {
return $str
}
foreach my $s2 (0 .. 255) {
my $str = $str . chr $s2;
if ($cryped eq crypt($str, $crypted)) {
return $str
}
foreach my $s3 (0 .. 255) {
my $str = $str . chr $3;
if ($cryped eq crypt($str, $crypted)) {
return $str
}
foreach my $s4 (0 .. 255) {
my $str = $str . chr $4;
if ($cryped eq crypt($str, $crypted)) {
return $str
}
foreach my $s5 (0 .. 255) {
my $str = $str . chr $5;
if ($cryped eq crypt($str, $crypted)) {
return $str
}
foreach my $s6 (0 .. 255) {
my $str = $str . chr $6;
if ($cryped eq crypt($str, $crypted)) {
return $str
}
foreach my $s7 (0 .. 255) {
my $str = $str . chr $7;
if ($cryped eq crypt($str, $crypted)) {
return $str
}
foreach my $s8 (0 .. 255) {
my $str = $str . $chr $8;
if ($cryped eq crypt($str, $crypted)) {
return $str
}
}
}
}
}
}
}
}
}
}
| [reply]
[d/l] |
|
|
And if you allow passwords of length less than 1.
My algorithm already checks that! Sure, for Perl it looks like all the strings are 8 characters, but the check is done by a C routine, who thinks that strings ends before the first \0 character.
It could be a bit optimized to take advantage of this, but all it does is save a few years of running time, at the expense of uglier, and harder to maintain, code. More code as well, and we all know that programmer time is more expensive than CPU time.
| [reply] |
|
|
|
|
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);
}
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
| [reply]
[d/l] |
|
|
All control characters are easily typed from the keyboard as well. For instance, a newline can be inputted by typing:
CTRL-V CTRL-J
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] |
|
|
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] |
|
|
|
|
| [reply] |