john-users - Re: keyspace, mask password and dumb bruteforce

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 21 Jan 2009 21:51:47 -0600
From: Billy Newsom <billy@...c.us>
To: john-users@...ts.openwall.com
Subject: Re: keyspace, mask password and dumb bruteforce

Steve Bergman wrote:
> Solar Designer wrote:
>> The exception is when you're willing to throw a lot of computing
>> resources at cracking one publicly known hash, and you cannot or don't
>> care to optimize the order in which candidate passwords are tried.
>>   
> If I may throw in a comment to put this in a perspective that the mind 
> can more easily grasp, (since the human mind tends not to deal well with 
> extreme scale), the keyspace for a unix password of maximum length 8 is, 
> I think, 95^8 + 95^7 + 95^6 + 95^5 + 95^4 + 95^3 + 95^2 + 95^1 + 95^0 = 
> 6704780954517121, which we can call about 6.7e15. This is a 
> mind-bogglingly huge number. Last I looked, seti@...e, which is far and 
> away *the* most popular distributed project (no other project on BOINC 
> can touch it) had about a half a million cores running their client.  
> Assuming that all of these cores are as fast as one core of a Q6600 
> (which they aren't), and that  all of them ran full out 24 hours a day 
> (which they don't), then if the *entire* power of the seti@...e 
> distributed network were focused, with 0% efficiency loss due to 
> distribution overhead, upon one md5 hash with one salt, without 
> optimizing the password candidate order, they would be guaranteed to 
> crack it in about 2 weeks.  On average it would take a week.
> 
> I'm no expert. But it seems to me that this is a problem where a little 
> finesse is worth more than one *hell* of a lot of brute force.
> 
> Perhaps there is more potential in coming up with ideas to even further 
> optimize candidate password selection for individual scenarios than 
> there is in distributing the processing to more machines.  The 'brute' 
> in 'brute force' is there for a reason. ;-)

Yeah, you bet that the distributed.net and SETI type of projects are neither 
efficient or intuitive if you are going to compare it against the 
socially-engineered thinking behind John. Not my point at all. I was 
originally saying that if you take a project with all its networking bells and 
  distribution whistles, and you make the server run smart like John to 
socially engineer a fast password crack, and send out the best candidate 
choices to the client johns, then you will get the best of #1 intelligent 
cracking and speed, and #2, distribution and key management (or should I say 
candidate management).

Whatever the goal is, whether its dumb brute forcing RC5-72 or it is 
intelligently cracking NTLM passwords, you can use a hive mentality to make 
sure everything buzzes along from one central command head. Again, my point is 
that the distributed projects have the networking and sharing loads code, 
which is pretty well established. John is a fast cracker. Just do both. The 
master john would be the queen and decide who in the hive gets what. The idea 
is to split up the process WAY SMARTER than telling core 0 to try 0-5 
character passwords, core 1 to try 6 characters, core 2 to try 7 characters, 
and core 4 gets the nice and not-so-equal job of trying 8 characters. That is 
the sort of advice we read about john when someone talks about distributing 
load. It's absurd.

And to get on with it, the exact same principle of the queen bee distributor 
of the candidates can apply equally well with a multi-core PC of 2016, which 
might have 64 cores, and a distributed network of 100 rackmounted servers, 
available today.

Parallelism is lacking in john. That's the point. But by the way, I got a 
crack with john in 9 minutes recently that will be eventually solved by my 
Xeon quad after around 24 hours of stupid brute forcing. I hate stupid. But 
that is the state of the art for a lot of crackers out there, regardless. So I 
know what you are saying that brute force is not an answer... I agree. Let's 
go with smart... and extend it to be distributed smart.

And one more thing. This may sound like a wild idea, but probably in the next 
few years, we won't have to run john or jack or jill or any cracker for some 
of the older types of password tables. We will likely just find someone's 
rainbow tables with, for example all of the md5 hashes with or without salt, 
SHA1 or whatever, and perhaps we pay them a nominal fee, but we just type in 
the hash and salt, and they will have the data in a MySQL database that they 
have generated. Free versions of many millions of hashes are already available 
today. So basically, it will be faster for them to give you the answer than it 
does to take your PayPal money.

I mean with all of the time spent on cracking, not too much effort has been 
put into just doing a hash ONCE and for all, and then just comparing its 
result on the fly the next time you need it.

> -Steve
> 


-- 
To unsubscribe, e-mail john-users-unsubscribe@...ts.openwall.com and reply
to the automated confirmation request that will be sent to you.