Free Rainbow Tables | Forum

Home of the Distributed Generator and Cracker
It is currently 30 May 2015, 22:22

All times are UTC + 1 hour [ DST ]




Post new topic This topic is locked, you cannot edit posts or make further replies.  [ 47 posts ]  Go to page Previous  1, 2, 3, 4  Next
Author Message
PostPosted: 27 Jan 2011, 19:31 
Offline
MΩth √G∑∏∫∪≤

Joined: 03 Dec 2007, 11:37
Posts: 1061
quel wrote:
[A-Z][a-z]{5}[a-z0-9]{2}[0-9]{1,3} = 26 * 11,881,376 * 1296 * 1110 = 167,086,810,575,360 ≈ 2^47.2476

26 * 11,881,376 * 1296 * 1110 = 444,393,878,722,560 ≈ 2^48.6588

_________________
http://www.tobtu.com/


Top
 Profile  
 
 Post subject:
Posted: 27 Jan 2011, 19:35 


Top
  
 
PostPosted: 27 Jan 2011, 19:35 
Offline
Total Hash Enlightenment

Joined: 15 Jul 2009, 22:38
Posts: 1486
Location: Dallas, TX, USA
Sc00bz wrote:
quel wrote:
[A-Z][a-z]{5}[a-z0-9]{2}[0-9]{1,3} = 26 * 11,881,376 * 1296 * 1110 = 167,086,810,575,360 ≈ 2^47.2476

26 * 11,881,376 * 1296 * 1110 = 444,393,878,722,560 ≈ 2^48.6588


Thanks again Sc00bz. Also, geez I had the numbers right but I apparently can't even enter them into bc without screwing it up.


Top
 Profile  
 
PostPosted: 27 Jan 2011, 21:19 
Offline
Total Hash Enlightenment

Joined: 15 Jul 2009, 22:38
Posts: 1486
Location: Dallas, TX, USA
[A-Z][a-z]{5}[a-z0-9]{2}[0-9]{1,3} = 26 * 11,881,376 * 1296 * 1110 = 444,393,878,722,560 ≈ 2^48.6588

The last set, md5_mixalpha-numeric-space#1-8_0, is coming out to about 30 days for total generation. Sc00b'z calculator estimate @ 5bil links/s gives: 29 d 13 h. We're currently doing 5.6bil links/s and the start of the set was slower and closer to 4bil links/s.

A crude over approximation from Sc00b'z calculator with Key space ≈ 2 ^ 48.7211 at 5bil links/s gives us 54 days.

I have to evaluate the cost of the subkey spaces causing more reduction function calls (IndexToPlain.) I already have the hybrid changes complete for distrrtgen (cpu) and rcracki_mt courtesy again of Sc00bz via his hybrid2 post and should be able to test those tonight. The changes should be trivial to bring to distrrtgen_cuda and then I can really compare speed versus a similar keyspace that isn't a hybrid set.

Again please give me some indication of pleasure or displeasure with the proposed set, including any thoughts or suggestions. If we decide to go with this set about the only remaining item is deciding on a chain length. We can go higher (if we cross ~65,535 then we have to use indexes that aren't 0,1,2,3 but that detail can be 'hidden' in rti2), lower, or again 60k. I haven't done any disk space estimations. I do have to focus on testing the hybrid fixes and getting new distrrtgen binaries (and server side validation) pushed out so we are running quite low on time remaining to pick.

I'm fine with the set taking longer to generate than the previous set as I was overly optimistic on getting all the work and optimizations completed during that set. Two months isn't a big deal but if we are looking at longer generation time then we probably should scale back our pick for now since we'd want to really be sure of our choices as well as code changes before we embark on such a long set. For now please limit remarks to the next set that we will be kicking off within the next week. After that one is going then I suggest we start this discussion all over again and really hit the statistics and evaluate hash algorithm needs as well as table set needs.


Top
 Profile  
 
PostPosted: 27 Jan 2011, 22:55 
Offline
Developer

Joined: 30 Mar 2008, 15:37
Posts: 865
just a quick comment from my side... in almost all serious domains i encounter and extract hashes from, minimum password length is set to 8... i rarely see 6...


Top
 Profile  
 
PostPosted: 27 Jan 2011, 23:03 
Offline
Total Hash Enlightenment

Joined: 15 Jul 2009, 22:38
Posts: 1486
Location: Dallas, TX, USA
neinbrucke wrote:
just a quick comment from my side... in almost all serious domains i encounter and extract hashes from, minimum password length is set to 8... i rarely see 6...


Well, we're covered since I want to do 9+ so we don't overlap with ntlm_mixalpha-numeric#1-8 :)


Top
 Profile  
 
PostPosted: 28 Jan 2011, 06:41 
Offline
MΩth √G∑∏∫∪≤

Joined: 03 Dec 2007, 11:37
Posts: 1061
Looking at [A-Z][a-z]{5}[a-z0-9]{2}[0-9]{1,3} I wanted to see if passwords in this subset [A-Z][a-z]{5}[0-9][a-z][0-9]{1,3} are common since they account for over 20% of the key space.
Aaaaaa0a0
Aaaaaa0a00
Aaaaaa0a000

Rockyou:
96 unique 104 total with the subset of the key space vs 60,172 unique 74,217 total with the full key space.
0.1595% of unique and 0.1401% of total

phpBB:
4 unique 4 total with the subset of the key space vs 510 unique 533 total with the full key space.
0.7843% of unique and 0.7505% of total

Almost half the passwords from the subset of the key space had 2k[1-9] at the end.

----------------

The only problem is if we get ride of it then it's going to need a code change. Unless we save [A-Z][a-z]{5}[0-9]{3,5} for later.

[A-Z][a-z]{6}[a-z0-9][0-9]{1,3}
Aaaaaaan0
Aaaaaaan00
Aaaaaaan000
320,951,134,632,960 ≈ 2^48.1893

Rockyou:
45168 unique 57242 total with the subset of the key space vs 60,172 unique 74,217 total with the full key space.
75.0648% of unique and 77.1279% of total

phpBB:
396 unique 411 total with the subset of the key space vs 510 unique 533 total with the full key space.
77.6471% of unique and 77.1107% of total

-----

[A-Z][a-z]{5}[0-9]{3,5}
Aaaaaa000
Aaaaaa0000
Aaaaaa00000
34,289,651,136,000 ≈ 2^44.9628

Rockyou:
14,908 unique 16,871 total with the subset of the key space vs 60,172 unique 74,217 total with the full key space.
24.7756% of unique and 22.7320% of total

phpBB:
153 unique 161 total with the subset of the key space vs 510 unique 533 total with the full key space.
30.0000% of unique and 30.2064% of total

_________________
http://www.tobtu.com/


Top
 Profile  
 
PostPosted: 28 Jan 2011, 20:13 
Offline
Total Hash Enlightenment

Joined: 15 Jul 2009, 22:38
Posts: 1486
Location: Dallas, TX, USA
Scoobz wrote:
The only problem is if we get ride of it then it's going to need a code change. Unless we save [A-Z][a-z]{5}[0-9]{3,5} for later.

[A-Z][a-z]{6}[a-z0-9][0-9]{1,3}


Sc00bz, as always your analysis and math are much appreciated and valuable to the project. As far as representative of a corporate environment PapaSmurf and I have only small experience and I defer to tittentei on that particular topic. Though, it appears neinbrucke is getting interested in returning from the dead as well and he may also offer insight that helps us as well.

rubendodge did some analysis that I haven't had time to look at but again based on rockyou and other public lists.

I am certainly intrigued at the idea of doing the set you proposed which still brings us up to length 11 and saving the other set you propose, with a smaller keyspace, as a complement to this set. As you point out the "later" set would require some heavier changes.

So overall the question for the current set is currently:
Code:
[A-Z][a-z]{5}[a-z0-9]{2}[0-9]{1,3} = 26 * 11,881,376 * 1296 * 1110 = 444,393,878,722,560 ≈ 2^48.6588
[A-Z][a-z]{6}[a-z0-9][0-9]{1,3} = 26 * 308,915,776 * 36 * 1110 = 320,951,134,632,960 ≈ 2^48.1893


The first one would cover Summer2010 and is closer to tittentei's original request. The second one would not cover Summer2010.


Top
 Profile  
 
PostPosted: 29 Jan 2011, 15:15 
Offline
Developer

Joined: 30 Mar 2008, 15:37
Posts: 865
maybe double up and go for:
Code:
[A-Z][a-z]{4}[a-z0-9]{3}[0-9]{1,3} = 26 * 456976 * 46656 * 1110 = 615,314,601,308,160 ≈ 2^49.1283


or maybe instead of 0-9 at the end, go for [0-9!] ? Seems like ! is the most used special char at the end... but maybe leave that for a future set based on better statistics :)
(hmm, gets quite a lot bigger with 1 extra char:
Code:
[A-Z][a-z]{4}[a-z0-9]{3}[0-9!]{1,3} = 26 * 456976 * 46656 * 1463 = 810,995,731,273,728 ≈ 2^49.5267

ok, never mind;P)


Top
 Profile  
 
PostPosted: 29 Jan 2011, 22:55 
Offline
Total Hash Enlightenment

Joined: 15 Jul 2009, 22:38
Posts: 1486
Location: Dallas, TX, USA
Final decisions need to be made within about the next 24 hours

neinbrucke wrote:
maybe double up and go for:
Code:
[A-Z][a-z]{4}[a-z0-9]{3}[0-9]{1,3} = 26 * 456976 * 46656 * 1110 = 615,314,601,308,160 ≈ 2^49.1283


or maybe instead of 0-9 at the end, go for [0-9!] ? Seems like ! is the most used special char at the end... but maybe leave that for a future set based on better statistics :)
(hmm, gets quite a lot bigger with 1 extra char:
Code:
[A-Z][a-z]{4}[a-z0-9]{3}[0-9!]{1,3} = 26 * 456976 * 46656 * 1463 = 810,995,731,273,728 ≈ 2^49.5267

ok, never mind;P)


Hrm until I finish all the RTI2 work we'd literally have to make a new charset in charset.txt for something like numeric-exclamation and yes we should probably keep the keyspace a bit smaller for now :)

Also, this next set with the multiple sub-key spaces for hybrids initially is going to run quite a bit slower until optimizations are finished. I'm doing more benchmarking to know with more certainty but factoring in the extra IndexToPlain calls, and some optimizations already complete, my earlier remark "with Key space ≈ 2 ^ 48.7211 at 5bil links/s gives us 54 days" is more accurately reflected closer to 90 days. Thus I'm not inclined to press for a larger set but will list it here as an option.

Edit: neinbrucke pointed out in irc that ntlm is faster than md5 which I didn't factor in above.

I think this list represents those sets in the running for our next set. I think the first two listed are the most likely picks. Please check the math, agree, disagree, etc. as we will run out of new WUs for assignment in about 24 hours time. Additionally, any thoughts on chain length must happen quickly as well. Though, given that this set may be going for 3 months my first concern is we pick the right coverage with all presently available data and insight. If you feel strongly for or against a set, speak now. If you want to rank these 3 in order of preference, that is also welcomed. While it was actually unintentional, the ordering of this list reflects my ordered preference.

Code:
[A-Z][a-z]{5}[a-z0-9]{2}[0-9]{1,3} = 26 * 11,881,376 * 1296 * 1110 = 444,393,878,722,560 ≈ 2^48.6588
[A-Z][a-z]{6}[a-z0-9][0-9]{1,3} = 26 * 308,915,776 * 36 * 1110 = 320,951,134,632,960 ≈ 2^48.1893
[A-Z][a-z]{4}[a-z0-9]{3}[0-9]{1,3} = 26 * 456976 * 46656 * 1110 = 615,314,601,308,160 ≈ 2^49.1283


Sc00bz especially, but anyone as well, let me know what you think about chain length vs size on disk vs brute force point vs cryptanalytic time. The only assumption about changes that is currently safe to make is that it will be a format likely very similar to RTI2 but with headers very similar to Sc00bz's. I mention this mostly for purposes of disk size of the completed set. However, if we want to push the chain length up then we can make the indexes "weird" but handle it internally in the format so we don't have forum threads about why we don't have 0, 1, 2, and 3. I was overly optimistic on how much work I would complete during this last set and this last set when faster than I expected. Thus, I don't want to make assumptions regarding optimizations, sse, and cuda support being complete in rcracki_mt. This pessimism leads me to think that keeping the chain length under ~65535 is likely best. Hopefully this set does give enough time to get some evaluation of this last set at 60k with some optimizations that we can make a more sound decision on chain length for the next set.


Top
 Profile  
 
PostPosted: 29 Jan 2011, 23:10 
Offline
Developer

Joined: 30 Mar 2008, 15:37
Posts: 865
i vote for first set.

i'd say 60k chain length won't hurt us that much i guess... although ntlm should be faster then md5, but i think the trouble with 'crazy indexes' needs more work to not have users go nuts.


Top
 Profile  
 
PostPosted: 29 Jan 2011, 23:32 
Offline
Total Hash Enlightenment

Joined: 15 Jul 2009, 22:38
Posts: 1486
Location: Dallas, TX, USA
On disk size alone @ 60k chain length I'm vetoing neinbrucke's recent entry of
Code:
[A-Z][a-z]{4}[a-z0-9]{3}[0-9]{1,3} = 26 * 456976 * 46656 * 1110 = 615,314,601,308,160 ≈ 2^49.1283


Top
 Profile  
 
PostPosted: 30 Jan 2011, 04:08 
Offline
MΩth √G∑∏∫∪≤

Joined: 03 Dec 2007, 11:37
Posts: 1061
Code:
#1 [A-Z][a-z]{5}[a-z0-9]{2}[0-9]{1,3} = 444,393,878,722,560 ≈ 2^48.6588
#2 [A-Z][a-z]{6}[a-z0-9][0-9]{1,3}    = 320,951,134,632,960 ≈ 2^48.1893

   | Chain  | Brute Force |
   | Length | Point       | Size
---+--------+-------------+--------
#1 | 70,000 |      45,347 | 313 GB
#1 | 60,000 |      61,722 | 364 GB
#1 | 50,000 |      88,881 | 436 GB
---+--------+-------------+--------
#2 | 70,000 |      32,751 | 224 GB
#2 | 60,000 |      44,577 | 263 GB
#2 | 50,000 |      64,192 | 315 GB
#2 | 40,000 |     100,300 | 393 GB

I'd say #1 60k or #2 50k.

_________________
http://www.tobtu.com/


Top
 Profile  
 
PostPosted: 30 Jan 2011, 17:51 
Offline
Site Admin

Joined: 26 Aug 2010, 02:40
Posts: 105
Interesting.

I'm a fan of #1 at 60k, largely because #2 appears to be subset of #1. I'm not against having a job that starts in the 90 day range given that we continue to see increased compute power from an expanding user base.


Top
 Profile  
 
PostPosted: 30 Jan 2011, 18:43 
Offline
Total Hash Enlightenment

Joined: 15 Jul 2009, 22:38
Posts: 1486
Location: Dallas, TX, USA
ok lets do

Code:
[A-Z][a-z]{5}[a-z0-9]{2}[0-9]{1,3} = 444,393,878,722,560 ≈ 2^48.6588


@ 60k chain length

All WUs have currently been assigned to computers. I hope to finish hybrid2 changes and push out the new server side components and client distrrtgens later today.


Top
 Profile  
 
PostPosted: 31 Jan 2011, 03:08 
Offline
MΩth √G∑∏∫∪≤

Joined: 03 Dec 2007, 11:37
Posts: 1061
Code:
#1 [A-Z][a-z]{5}[a-z0-9][a-z0-9][0-9]{1,3} = 444,393,878,722,560 ≈ 2^48.6588
#4 [A-Z][a-z]{5}[0-9]   [a-z]   [0-9]{1,3} =  89,153,092,953,600 ≈ 2^46.3414

#2 is a subset of #1. The only thing is #1 also contains #4 which is about 20% of the total key space but accounts for less than 1% of the crackable passwords from the phpBB and Rockyou lists. If we could do "#1 - #4" I would vote for that.

_________________
http://www.tobtu.com/


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic This topic is locked, you cannot edit posts or make further replies.  [ 47 posts ]  Go to page Previous  1, 2, 3, 4  Next

All times are UTC + 1 hour [ DST ]


Who is online

Users browsing this forum: No registered users and 0 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group