Progress on the GPU accelerated RTs!

[Bitweasil]

Yes.

full US charset = mixalpha-numeric-symbol32-space

Len 95.

That's really the only thing I'm interested in right now.

[1epi]

charSetLen = 95
keySpace (7+8) = 95^7 + 95^8 = 69833729609375 = 2^45.9889 ~ 2^46

euc = chainCount / (tableWorkFactor / 2 + 1)
tableWorkFactor = chainLen * chainCount / keySpace

chainLen = 200000
chainCount = 400000000
tableWorkFactor = 200000*400000000/95^7 = 1.1455782248419423404
euc = 400000000 / (1.1455782248419423404 / 2 + 1) = 254325260 = 0.63581315 * 400000000 (63.5813 %, 36.418685 % are duplicates)

So your reduction function is not as good as the old one, that rainbow crack used.
Their merge rate is 36.4 % and yours is 41.2 %.

I can't predict the final merge rate on different chain lengths (hence I can't give you configurations for perfect rainbow tables), maybe Sc00bz can come up with a formula for you, try and ask him.
It's important to have perfect rainbow tables, and all the math, because this way it's easier for me to give you exact numbers. When dealing with non-perfect tables, the formula (nonperfectTableSuccessRate ˜ 1 - product i = 1 to chainLen of 1 - euc(i) / keySpace) that predicts the success rate is hard to "reverse", in order to extract the chainLen.
If you know the expectedUnique chains, it's a hell of a lot easier ( perfectTableSuccessRate = 1 - (1 - expectedUniqueChains / keySpace) ^ chainLen ) to extract the chainLen from this formula.

Talk to Sc00bz about this. Ask him to try to find out the formula that gives you the expectedUniqueChains, given your reduction function.

[Bitweasil]

I suspected my reduction function isn't quite as ideal as the RC one, but it's also *much* faster - which is the goal.

For the chain merging rates, would this be a value that could be constructed empirically? Test a bunch of different values & work out the merge rates?

IIRC the general guideline for perfect tables was a work factor of ~10x - once you got a 90% merge rate, things would be pretty solid.

However, why would one *need* perfect tables? They're more space efficient, and more time efficient, but you're throwing away a lot of work. On smaller keyspaces, this doesn't matter, but on a large keyspace, space is cheaper than compute time. IMHO. Depending on the requirements.

Also, perfect tables reduce the false positive rate - important, but when chain regen is being done on a GPU, it matters a bit less. You can rip through a few thousand chains in a hurry vs doing it on the CPU.

I'd be happy to discuss it further with you at some point, though - the theoretical math behind the table sizes is something I'm definitely weak on right now.

[sapling]

So long weekend of drinking so I may be way off in left field and making no sense.
When looking for duplicates the function only occurs per table right? And it occurs during the sorting function I thought?
So to reduce the amount of time it takes for anything CPU or GPU and making more efficient tables would you just want to create a huge single table?
I mean obviously for a 95, 8 to have a 98% or more chance of cracking a hash the single table would need to be 500GB's in size at 200,000 chain length...
But what your trying to say here is that if you have to generate chains half of them are going to be duplicates so if your generating at 400M/s on 2 GPU's your still only getting 400M/s because half are going to be duplicates?

[Bitweasil]

Code: Select all

$ ../../bin/linux/release/GRTCrack -s 32d93ad2312aeb35fe808a7ed644fa16 -h MD5 /mnt/array1/GRT/MD5* --threads 512 --blocks 512 -m 1000
Hash type: MD5
CUDA Device Information:

Device 0: "GeForce GTX 295"
  CUDA Driver Version:                           2.30
  CUDA Runtime Version:                          2.30
  Number of cores:                               240
  Clock rate:                                    1.24 GHz
  Performance Number:                            37260
  Note: Performance number is clock in mhz * core count, for comparing devices.
Processing GRT table /mnt/array1/GRT/MD5-idx1-chr95-cl200000-full.grt

Table version:   1
Hash:            MD5
Password length: 7
Table index:     1
Chain length:    200000
Num chains:      10000000
Perfect table:   No
Charset length:  95
Charset:          !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR
                 STUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~



Launching run group 1 of 1
Kernel Time: 13.574 ms  Done: 99.72%       
Searching table...                         


Step 199900 / 200000 (99.95%), 70894 chains found       

Hashes found: 70894 Chains to regen: 139738

Regenerating Chains...             


Kernel Time: 938.053 ms  Step rate: 422.02 M/s Done: 48.21%

FOUND PASSWORD!

Password:
Kr4km#!


*grins*

The search part is still slow. I should have timed it, but this was 30-60 minutes to crack.

Still better than the 48h it would take to brute force len7...

I want to put together a few more utility functions, and then I'll bundle it up and try to release it!

[Bitweasil]

Hm...

I think I should look into doing a linear read through the table, at least for smaller tables. Or as a command line option.

The 12GB tables I've got on a big RAID array take 25+ mins to search through, and 60s to linear read through.

[sapling]

Whats your raid array specs? Disk Size, Disk Speed, Cache per disk, Raid ? Interfaced via ? Controller Specs?

[Bitweasil]

Oh, something or other...

6x Seagate 1.5TB disks in a Linux software RAID6 array.

ST31500341AS drives, 7200 RPM. Not sure on cache, it doesn't really matter with the random workloads I'm throwing at it.

[Bitweasil]

So...

This involved a 12GB perfect table, chain length 200k, 24 bits of index file (~200M of index file).

This is on a fast server with a GTX295 in it (only using one core), and a ton of disk bandwidth, but it's a RAID - so slow seek times.

Code: Select all

Password (between the ' marks): 'Pa5$w0d'
Hex: 0x50613524773064

real    2m12.367s
user    1m23.420s
sys     0m16.510s


Code: Select all

Password (between the ' marks): 'K#n&r4Z'
Hex: 0x4B236E2672345A

real    1m51.962s
user    1m4.740s
sys     0m15.320s


I'm happy with that speed. I can make some additional tweaks, but that's in the realm of "more than good enough."

Sorry about the delays in progress, I've had a lot going on the past few weeks, parents in town, girlfriend, life, etc...

Until I made tonight's changes, it was taking ~25 mins per password per table on a high performance server. Not terrible, but not exactly great.

I'm *much* happier with this performance.

Time to wrap up some code for people to try out... Linux 64-bit only right now.

[Bitweasil]

Update:

Getting beta feedback, still could use a few more testers before release on Sun.

I've added some performance monitoring stuff for a few areas that didn't have it before.

I've added a --silent switch to the cracker that stifles all output except Password:<password> stuff.

I also have NTLM table *gen* working - still working on the cracking code for it. I can't promise that for Sun, but I'm trying.

Anyone else excited for this release?