OpenCL/C++ GRT code

[Bitweasil]

BTW NTLM step rate is at about 1.1 Bln for me on the GTX470. hehe just under half of FRTs current one.

Wait, the FRTU CUDA client is pushing 2B steps/sec on your 470? HOW?

[Sc00bz]

No that's 2 BLinks/sec for **ALL** of FRT. So FRT can be replaced with 2 GPUs.

blazer
Do you remember how many were cracked by just the first table?

[Sc00bz]

Wait a minute ALL of FRT can be replaced by ONE GTX470 since you can generate perfect rainbow tables in steps. Which will make it take about 1/2 the time. Note you can only generate in steps if you have all the generators connected with a fast LAN like 100 or 1000 (well I guess you could do that on the internet but that would be expensive) or well use only one computer.

[Bitweasil]

So, you can fit 6-8 GTX480s in a box if you do it right...

http://3.14.by/forum/viewtopic.php?f=8&t=1307

*drools*

[blazer]

how can you make perfect tables without making a lot of chains and going through them? can you somehow predict the merges and goto the next start point?

I'll go back and check how many hits there were with the first table, but form memorry most came from index 2.

OH wait i think i got it. Can you simply not "discard" the data between the start and end point and perform a massive lookup each link which will allow you to prematurely terminate generating that chain if it is going to merge. Probably not a great idea ur going to have to search through allooot of data. Though you could only keep the reduced data each step i guess, to cut down on space.

BTW: Imagine if you had 8x 5970 instead of 8x GTX480 hahahaha and used it for openCL, would smoke the GTX480

[Sc00bz]

how can you make perfect tables without making a lot of chains and going through them? can you somehow predict the merges and goto the next start point?
...
OH wait i think i got it. Can you simply not "discard" the data between the start and end point and perform a massive lookup each link which will allow you to prematurely terminate generating that chain if it is going to merge. Probably not a great idea ur going to have to search through allooot of data. Though you could only keep the reduced data each step i guess, to cut down on space.

Let's say you're trying to make an RT that has a chain length of 100,000 you start by making all the chains with a length of 25,000 then you sort and perfect. Then you extend those chains another 25,000 links and repeat until you get to all the chains that are left to a length of 100,000.

I figured this out then I found out that Ophcrack 1.0a had a generator that did this, but Ophcrack 1.0a didn't find or tell you how to find the optimal point which is kind of hard to find but I wrote a program to do it for me. You pick the the number of steps then you need to find the number of chains for each step that will make each step generate the same amount of links. The optimal number of steps depends on how fast a link takes and how fast you can sort. So it's pretty much a guess. The best you'll get with a table work factor of 13x (99.9025% success rate) is 1/3.226 the amount of links which is 4.0298x work done. To get the same success rate with imperfect tables you need a table work factor of 2.7578x. So the perfect table will take at least 46.12% more time to create, but the imperfect table will have about 1.6 times more chains.

[Bitweasil]

Sc00bz: With the reduction function/table index issues, simply incrementing index values by more than the chain length would fix it with the current code, yes?

So for chain length 200,000 use indexes 0, 300000, 600000, 900000 ?

[blazer]

hehee, wow very good idea, I always wondered how opcrack managed to compute such large tables. Doing everything in steps and extending them.

Wouldn't it be wise though to say build them like this.

For a chain length of 200 000
50 000, 30 000, 29 000, 25 000, 22 000, 20 000 .......

Eg we decrease the number chain length extensions each step for the generation to counter the merges rather than use a constant extension.
So all we have to do is work out the merge rate of the the GRT reduction function and then decrease our extension by that % upto a certain point before we waste too much time going through perfecting/sorting

Does that mean we need to start off with like 10x the amount of chains <<Bad idea i think
or
Do we do a chunk of chains per time

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

Actually I think I have a better idea sc00bz (could be worse)
Is this possible and would it be worse/better

for a chain length of 200 000 you designate for example 8 checkpoints
at 50 000, 40 000, 35 000, 25 000, 20 000, 15 000, 10 000, 5 000 <-- Hopefully that adds up

Now you generate say (using sequential start points)
1/ 10 000 000 chains @ 50 000 chainL
Perfect Sort + Make a copy
2/ partial perfect chains +40, 000 increment chainL
etc etc
3/ Reach last checkpoint and we should have a bunch of chains remaining at chain length 200 000 + we should have 8 checkpoint files containing end points at the different positions

Now you use the next lot of sequential start points
Repeat, BUT since we now have the data for the above 8 check points we can perfect our next chains taking into account all those partial chains at the different checkpoints and we also up the number of starting chains to 15 000 000 since there will obviously be more merges.

Numbers were randomly picked so probably don't add up or bad use of numbers, but just was curious about this concept


Will this be implemented in the next GRT?

EDIT: Before you start generating, how bout we get some good configs so they aren't wasted like the ones i made.
btw, what happens if you don't increment the index greater than chainL ?

[Bitweasil]

The issue there is the memory requirements needed. To do this "merge reduction" bit, you basically have to generate the *entire tableset* to 50,000 then check/remove duplicates, and do the same thing as you go forward. It doesn't work nearly as well distributed, unless there's something about it I'm missing.

When talking about tables on the order of several TB, you'd need to do this locally with a cluster, I think. Something with a lot of bandwidth. The size of a partial table is the same as the size of a full table.

So... probably not the next generation.

[Sc00bz]

Sc00bz: With the reduction function/table index issues, simply incrementing index values by more than the chain length would fix it with the current code, yes?

So for chain length 200,000 use indexes 0, 300000, 600000, 900000 ?

For everyone who's following this the answer is yes. The minimum table index increment is chain length - 1 and anything higher than that is OK unless table index + chain length > 2 ^ 24.

Wouldn't it be wise though to say build them like this.

For a chain length of 200 000
50 000, 30 000, 29 000, 25 000, 22 000, 20 000 .......

Eg we decrease the number chain length extensions each step for the generation to counter the merges rather than use a constant extension.

Yes and it's hard to find by hand. Also it's easier to understand with a simple example of 25,000+25,000+25,000+25,000=100,000 because most people can do that *without* thinking.

Does that mean we need to start off with like 10x the amount of chains <<Bad idea i think
or
Do we do a chunk of chains per time

No we start out with how many we would normally start out with. You can't do it in chunks there won't be enough merging to make it worth it.

for a chain length of 200 000 you designate for example 8 checkpoints
at 50 000, 40 000, 35 000, 25 000, 20 000, 15 000, 10 000, 5 000 <-- Hopefully that adds up

Now you generate say (using sequential start points)
1/ 10 000 000 chains @ 50 000 chainL
Perfect Sort + Make a copy
2/ partial perfect chains +40, 000 increment chainL
etc etc
3/ Reach last checkpoint and we should have a bunch of chains remaining at chain length 200 000 + we should have 8 checkpoint files containing end points at the different positions

Now you use the next lot of sequential start points
Repeat, BUT since we now have the data for the above 8 check points we can perfect our next chains taking into account all those partial chains at the different checkpoints and we also up the number of starting chains to 15 000 000 since there will obviously be more merges.

Numbers were randomly picked so probably don't add up or bad use of numbers, but just was curious about this concept

No this is a bad idea because it uses a lot more disk space.

btw, what happens if you don't increment the index greater than chainL ?

The chains overlap and it's like creating basically one large table with a few extra links one some chains.
Each dot is a link and each line is a chain taken from a different table (table indexes 0,1,2,3):

Code: Select all

  .....................
   .....................
    .....................
     .....................

The issue there is the memory requirements needed. To do this "merge reduction" bit, you basically have to generate the *entire tableset* to 50,000 then check/remove duplicates, and do the same thing as you go forward. It doesn't work nearly as well distributed, unless there's something about it I'm missing.

When talking about tables on the order of several TB, you'd need to do this locally with a cluster, I think. Something with a lot of bandwidth. The size of a partial table is the same as the size of a full table.

I agree well until people get +10Mbps uploads, no bandwidth caps, and are able to connect to each other, but even then you'll be network limited. It stops becoming the issue when you get 100 Mbps unless you want to go crazy on number of steps or GPUs are much faster then. Oh right I said by 2014 rainbow tables will be pointless (because everyone will use salt by then). Wow was that optimistic I guess I didn't know how much people don't like change just look at Windows XP, IE6, and the homeless (some of them make 6 figures a year in change from people who I guess don't like change very much ).