Free Rainbow Tables | Forum

Home of the Distributed Generator and Cracker
It is currently 19 Apr 2015, 17:29

All times are UTC + 1 hour [ DST ]




Post new topic This topic is locked, you cannot edit posts or make further replies.  [ 16 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: 27 Sep 2008, 20:59 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
index :

1.What is the max length of the password that freerainbowtables is able to crack?
Which combination of alphabet, char, symbol did covered in that hash?
How many types of encryption your table are able to crack? what are their success rate/ each type?

http://freerainbowtables.com/phpBB3/vie ... &f=8#p6839

2.Upload of Parts is being aborted

3.Cracking RAR protected archives

4.Is it possible to crack 16 char long NTLM password?

5.Why 12 characters, LowerAlpha, UpperAlpha, Numbers and Symbol-14 is infeasible.

6.How to use rcracki

7.The difference between DES and DES Crypt

8.Is it possible to generate rainbow tables for zip archives?

9.Time required to create a rainbow table ?

10.Is there a description of how indexed rainbow tables works?

11.Upper "limit" of chainLength ?

12.keySpace upper "limit" of FreeRainbowTables.com ?

_________________
a2480f25 blog.


Last edited by _haxxor_ on 09 Nov 2009, 20:51, edited 16 times in total.
Edited Topic and stickied global so thread gets more attention!


Top
 Profile  
 
 Post subject:
Posted: 27 Sep 2008, 21:06 


Top
  
 
PostPosted: 27 Sep 2008, 21:06 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
pointp wrote:
Your hash is AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBB:CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC

AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBB is the lm hash and
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC is the ntlm hash.

In fact, AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBB is 2 lm hashes, AAAAAAAAAAAAAAAA and BBBBBBBBBBBBBBBB
First part is the first 7 chars of your password and the second part is the 8+ chars of your password (max 14)
if you're password length is > 15, then lm hash is blank (AAD3B6... x2) and only ntlm.

LM hashes are case unsensitive, that's why generating Uppercase tables enough. NTLM isn't, that's why it allows us to "correct the case" and makes the cracking process faster.

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 29 Sep 2008, 20:41 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
mulysa wrote:
1. What is the max length of the password that freerainbowtables is able to crack?
2. Which combination of alphabet, char, symbol did covered in that hash?
9. How many types of encryption your table are able to crack? what are their success rate/ each type?

Sc00bz wrote:

Code:
Hash | Characters in password               | passwords of length | success rate
--------------------------------------------------------------------------------
ntlm | a-z, A-Z, 0-9, 32 symbols, and space | 1 to 6              | 99.9554%
ntlm | a-z, 0-9, 32 symbols, and space      | 1 to 7              | 99.936%
ntlm | a-z, A-Z, 0-9, and space             | 1 to 7              | 99.9215%
ntlm | a-z, 0-9, and space                  | 1 to 8              | 99.9304%
ntlm | A-Z, 0-9, and space                  | 1 to 8              | 99.9286%
ntlm | a-z and space                        | 1 to 9              | 99.9323%
ntlm | A-Z and space                        | 1 to 9              | 99.92%
ntlm | 0-9                                  | 1 to 12             | 99.9295%
md5  | a-z, A-Z, 0-9, 32 symbols, and space | 1 to 6              | 99.9415%
md5  | a-z, 0-9, 32 symbols, and space      | 1 to 7              | 99.5745%
md5  | a-z, A-Z, 0-9, and space             | 1 to 7              | 99.9303%
md5  | a-z, 0-9, and space                  | 1 to 8              | 99.5707%
md5  | A-Z, 0-9, and space                  | 1 to 8              | 99.9349%
md5  | a-z and space                        | 1 to 9              | 99.93%
md5  | A-Z and space                        | 1 to 9              | 99.9249%
md5  | 0-9                                  | 1 to 12             | 99.9325%
lm   | a-z, A-Z, 0-9, 32 symbols, and space | 1 to 7 "14"         | 99.9175%
lm   | A-Z and 0-9                          | 1 to 7 "14"         | 99.9%
md5  | 6 lower case letters followed by 1 to 3 numbers "7 to 9"   | 99.9368%
md5  | 7 lower case letters followed by 1 to 3 numbers "8 to 10"  | 99.9243%
ntlm | 6 lower case letters followed by 1 to 3 numbers "7 to 9"   | 99.9302%
ntlm | 7 lower case letters followed by 1 to 3 numbers "8 to 10"  | 99.9239%

* We are currently working on SHA-1 tables with similar stats as NTLM and MD5.

If you're going to generate rainbow tables it will take you about the same time as it will to brute force 1,040 passwords separately. With code that doesn't exist yet, you can get that down to about the same time as it will to brute force 26-52 passwords separately. So if you have less than that you *should not* generate rainbow tables. There are ways to cut the time down for generating the tables such as making non-perfect rainbow tables and lower success rates.

mulysa wrote:
6. In case If I need to generate more advanced hash table, what is the min hardware spec required to perform such task? Is it necessary to be a cluster? 2x Xeon Quadcore + 16 GB is enough?
You'll need about 5 Core2 Quads around 2.5 GHz and code that doesn't exist yet or 2 high end nVidia cards and code that doesn't exist yet to match the computing power of this site. Core2 processors are about 2.5 times faster than P4s and Xeons with the same number of cores and clock rate (at least from what I've tested). You can test your speed by looking up barsWF if you get like 42 million/sec/core on your Xeons than it's as fast as a Core2 if you get like 17 million/sec/core than this is expected. I'm assuming your Xeons are 2.5 GHz so add or subtract a little.

* Note that you can convert these rainbow tables to fit into a MySQL database or another database, but for the most part it will not be practical. That and code to do that probably doesn't exist.

---------
viewtopic.php?p=6826#p6826

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 14 Oct 2008, 18:57 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
PowerBlade wrote:
If you have a uncracked hash, you can now click on the "Status" field and see the progress of each table

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 17 Oct 2008, 20:44 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
Cracking RAR protected archives
txeriff wrote:
Hi all,

Do you know how to crack rar passwd protected archieve?

What rainbow table i need for it?

thanks!

_haxxor_ wrote:
yep ... :( brute force ... because there is no hash in the protected rar file, the archive is encrypted with the password ... so only if you have a same rar file, with the exact same content you could "compare" the two of them and find very fast the password..."advanced archive password recovery" or something...can do this kind of attack.

Sc00bz wrote:
Oh also I looked into the source and it appears that there is a salt added to the password. So this means you can't create a rainbow table that will crack a password for a specific file type, but that also assumes that the file type has a header that is at least 16 bytes long and is always the same. Oh wait that would only work if the compression algorithm uses a one pass method or is not compressed at all.

----------
viewtopic.php?f=2&t=563&p=4038#p4038

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 17 Oct 2008, 20:54 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
Is it possible to crack 16 char long NTLM password?
quick answer : NO
long answer :
Sc00bz wrote:
What Morello would need is 16 characters, LowerAlpha, UpperAlpha, Numbers and Symbol-32. Which has a key space 2^29.90 larger than the one above. In another topic I said it would be like 114 years before we would create a table this big.

Ohh hey I have a nice formula. Figure out the largest key space of a table we can do in 2 years. It's about 2^51 currently.

years = 2 * log2(2^(105 - 51) + 1) is almost equal to 2 * (105 - 51) = 108 years.

Key spaces of tables.
log2((26+26+10+14) ^ 12) = 74.98
log2((26+26+10+32) ^ 16) = 104.87

--------
viewtopic.php?p=2800#p2800

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 17 Oct 2008, 20:58 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
Why 12 characters, LowerAlpha, UpperAlpha, Numbers and Symbol-14 is infeasible.
Sc00bz wrote:
log2((26+26+10+14) ^ 12) = 74.98
To store an index you'll need at least 75 bits but currently everything is in 64 bit numbers. So even if you wanted to do this which will take forever and over 64 EiB of disk space. It will also take a rewrite of how "everything" works.

rows = multiplier * key space / chain length = 10 * (26+26+10+14)^12 / 100,000
size = rows * bytes per row / bytes per EiB = 3,713,326,247,319,550,139 * 20 / 2 ^ 60 = 64.42 EiB

http://en.wikipedia.org/wiki/EiB

** Side Note 1 **
15,000 chains/sec (current speed) means it will only take 7,844,496 years

If you can take into account disk space increases by a factor of 10 about every 5 years and computing power increases by a factor of 2 every 2 years.
So if everyone upgrades their computers every 2 years and no one else joins, then these tables will be done in 44 years, but this will be very expensive for a site that can only raise about $250 in a couple months. The hard drives will be $720/yr and servers well you could buy one or two and just swap out and store the HDs somewhere saving a lot of money on servers.

With that said in 44 years Microsoft won't even be around so making this for NTLM would be dumb same with MD5, SHA1, SHA256, ect. MD5 "should not used in new applications" and SHA1 is also kinda dead. SHA256 is alive and kicking but the next round of hash functions are being made now and in a few years SHA256 will be kinda dead. Also in 44 years 12 characters, LowerAlpha, UpperAlpha, Numbers and Symbol-14 is only 1.9 years away starting from scratch. Well this is all assuming the world doesn't end in 2012 :roll:.


** Side Note 2 **
multiplier is not really talked about since it's just something you find out after you pick key space, chain length, chains/file, files/table, and number of tables.
Let's look at a real world multiplier.

(I think there's going to be 4 of these tables)
md5_loweralpha-numeric-symbol32-space#1-7_0_10000x70000000_distrrtgen_0
...
md5_loweralpha-numeric-symbol32-space#1-7_0_10000x70000000_distrrtgen_219
md5_loweralpha-numeric-symbol32-space#1-7_1_10000x70000000_distrrtgen_0
...
md5_loweralpha-numeric-symbol32-space#1-7_1_10000x70000000_distrrtgen_219

26+10+32+1 = 69
key space = 69 + 69^2 + ... + 69^7 = 7,555,858,447,479
work = chain length * chains/file * files/table * tables (so far) = 10,000 * 70,000,000 * 220 * 2 = 308,000,000,000,000
multiplier = work / key space = 40.76

----------------
viewtopic.php?p=1665#p1665

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 24 Oct 2008, 17:22 
Offline
Perfect Table
User avatar

Joined: 12 May 2008, 11:02
Posts: 809
How to use rcracki:

in general you use these commands :

rcracki.exe [table_dir]\*.rti -h [hash (one)]
or
rcracki.exe [table_dir]\*.rti -l [hash list]

what is important ?! :

the dir of the tables must not contain spaces! or you have to put it into quotes ( "C:\Documents and Settings\...." )

LM hashes have to be split into parts! : as you should already know from a bit above lm hashes are actualy 2 hashes (16 byte each). You HAVE to split them so rcracki can use them. otherwise it will give an error : "this table contains hashes with length 8 only"

rcracki requires this to be installed !!!

_________________
Image


Top
 Profile  
 
PostPosted: 04 Nov 2008, 17:52 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
The difference between DES and DES Crypt
Sc00bz wrote:
There is a big difference. DES Crypt does DES 25 times which is why it will take 25 times longer to crack than DES.

-----
viewtopic.php?p=7569#p7569
Sc00bz wrote:
"UNIX crypt" doesn't tell you which one it is since there is the DES, BSDi extended DES, MD5 ("$1$"), Blowfish ("$2$" or "$2a$"), and SHA ("$5$" or "$6$"). I like "DES crypt(3)" but I just call it "DES crypt." Most people call these password hashing schemes crypt(3).

-------
viewtopic.php?p=7576#p7576

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 16 Dec 2008, 12:31 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
Is it possible to generate rainbow tables for zip archives?
short answer NO.

Sc00bz wrote:
lx45803 wrote:
If they're possible, I'd like to see zip tables, 1-16 characters if they can be generated fast enough. Really irritating to download a big zip file only to find it has a password.

Zip files are salted, which means you can not create a rainbow table for them. FYI zip files use PBKDF2 HMAC-SHA1 to generate the encryption key.


viewtopic.php?p=8897#p8897

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 30 Jun 2009, 10:57 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
Time required to create a rainbow table ?

hours_required = key_space * work_factor / step_speed / 3600
where:
character_set_length = 69
min_password_length = 1
max_password_length = 7
key_space = (character_set_length ^ (max_password_length + 1) - character_set_length ^ min_password_length) / (character_set_length - 1) = 7,555,858,447,479
step_speed in links per second, a quad core probably gets like 3 million per second on winrtgen.
work_factor = chain_length * chains / key_space
work_factor is chosen depending on table accuracy wanted. These work factors are found by guess and check and work for most key spaces and chain lengths (small chain lengths like 100 will be off by a little).

non-perfect table sets:
9.4 (2.35 per table, 4 tables) for a 99.80% (miss 1 in 500) non-perfect table set.
11 (2.75 per table, 4 tables) for a 99.90% (miss 1 in 1000) non-perfect table set.

perfect table sets:
10.86 (2.715 per table, 4 tables) for a 99.00% (miss 1 in 100) perfect table set.
17.84 (4.46 per table, 4 tables) for a 99.60% (miss 1 in 250) perfect table set.
28 (7 per table, 4 tables) for a 99.80% (miss 1 in 500) perfect table set.
52 (13 per table, 4 tables) for a 99.90% (miss 1 in 1000) perfect table set.

-Sc00bz-
--------
viewtopic.php?p=10909#p10909

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 07 Jul 2009, 01:25 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
Optimum number of tables for minimizing the space-time needed to crack a hash with a success rate of 99.9% is 4 tables.
"Optimum success rate" doesn't exist this is something you just pick. This depends on how long you want to spend creating rainbow tables and disk space.
"Optimum time for computing" is basically the same as "optimum success rate" as they are directly related. The only thing you can change that only effects one of them is number of tables and perfect vs non-perfect.

* How do you determine the best number of tables?
As you can see from the data for a 99.9% success rate the best space-time for cracking is 4 tables for either perfect or non-perfect rainbow tables. For perfect rainbow tables you might want to do 5 tables as it takes less than half the time to generate 4 tables.
Perfect Rainbow Tables "99.9%"
Code:
         |           |           | Less      | Smaller Than | Smaller Than |
         |           |           | Total     | Previous     | Previous     |
         | Work Per  | Total     | Work Than | (Const Chain | (Const Total | Total Success
Tables   | Table     | Work      | Previous  | Length)      | Pre-work)    | Rate
---------+-----------+-----------+-----------+--------------+--------------+-----------------
1 Tables |       N/A |       N/A |           |              |              | 86.46462849% Max
2 Tables |       N/A |       N/A |           |              |              | 98.16793718% Max
3 Tables |       N/A |       N/A |           |              |              | 99.75202349% Max
4 Tables | 12.78300x | 51.13200x |           |              |              | 99.90100293%
5 Tables |  4.48860x | 22.44300x |    56.11% |      0.0001% |      -11.80% | 99.90100191%
6 Tables |  2.72220x | 16.33320x |    27.22% |      0.0007% |       -9.54% | 99.90099547%
7 Tables |  1.95350x | 13.67450x |    16.28% |     -0.0006% |       -8.01% | 99.90099836%
8 Tables |  1.52334x | 12.18672x |    10.88% |     -0.0006% |       -6.91% | 99.90100114%

Non-Perfect Rainbow Tables "99.9%"
Code:
         |           |           | Less      | Smaller Than | Smaller Than |
         |           |           | Total     | Previous     | Previous     |
         | Work Per  | Total     | Work Than | (Const Chain | (Const Total | Total Success
Tables   | Table     | Work      | Previous  | Length)      | Pre-work)    | Rate
---------+-----------+-----------+-----------+--------------+--------------+-----------------
1 Table  | 61.52000x | 61.52000x |           |              |              | 99.90100449%
2 Tables |  9.27400x | 18.54800x |    69.85% |     69.8505% |       57.36% | 99.90099964%
3 Tables |  4.33500x | 13.00500x |    29.88% |     29.8846% |       14.13% | 99.90100885%
4 Tables |  2.74900x | 10.99600x |    15.45% |     15.4479% |        2.37% | 99.90106579%
5 Tables |  1.99450x |  9.97250x |     9.31% |      9.3079% |       -1.40% | 99.90100455%
6 Tables |  1.55950x |  9.35700x |     6.17% |      6.1720% |       -2.78% | 99.90099853%
7 Tables |  1.27810x |  8.94670x |     4.38% |      4.3850% |       -3.28% | 99.90099297%
8 Tables |  1.08180x |  8.65440x |     3.27% |      3.2671% |       -3.41% | 99.90101465%

* How do you determine the best indexes?
It appears that if you bit pack all the data the best index is such that there are about 15 to 30 chains per index, but all you do is increase or decrease the index until you find the smallest total table size. You may want to do a smaller index if you want to load the whole index in memory. Having an index smaller than the optimal by one or two bits indexed will only make the total size a few percent bigger.

* How do you determine the best chain length vs chain count?
What ever feels right. One way to measure how good a table is, is to do "key space / (chain length * (chain length + 1) / 2 * number of tables)" this number should be at least 10000. This number is roughly the point where you should do brute forcing if you have that many hashes. Chain count is found by calculating "work factor * key space / chain length."

Please note that rainbow crack's "chain length" is one higher than the "real chain length."
One last thing perfect rainbow tables are faster since they don't need to check for as many false alarms as non-perfect rainbow tables.

Perfect:
Code:
      |        |        |        |         |          |                         | Brute | Generation
      |        |        | Chain  | Pre-    |          |                         | Force | Time (at
Chars | Tables | Chains | Length | Perfect | Perfect  | Perfect and Indexed (*) | Point | .5MLink/s)
------+--------+--------+--------+---------+----------+-------------------------+-------+-----------
   69 |      4 | 4,829M | 20,000 | 288 GiB | 38.9 GiB | 15.95 GiB (25,33+18=51) | 9,444 | 8,943 Days
   69 |      5 | 1,696M | 20,000 | 126 GiB | 38.9 GiB | 15.45 GiB (25,31+18=49) | 7,555 | 3,926 Days
   69 |      5 | 1,896M | 17,889 | 141 GiB | 43.5 GiB | 17.20 GiB (25,31+18=49) | 9,444 | 3,926 Days
   51 |      4 | 1,672M |  7,000 | 100 GiB | 13.5 GiB |  5.16 GiB (24,31+16=47) | 9,339 | 1,084 Days
   51 |      5 |   587M |  7,000 |  44 GiB | 13.5 GiB |  5.08 GiB (23,30+17=47) | 7,471 |   476 Days
   51 |      5 |   656M |  6,261 |  49 GiB | 15.1 GiB |  5.66 GiB (23,30+17=47) | 9,339 |   475 Days

* (bits indexed,bits per start point+bits per end point=bits per chain)

Non-Perfect:
Code:
      |        |        | Chain  |          | Brute Force | Generation Time
Chars | Tables | Chains | Length | Size     | Point       | (at .5MLink/s)
------+--------+--------+--------+----------+-------------+----------------
   69 |      4 | 1,039M | 20,000 | 61.9 GiB |       9,444 |      1,924 Days
   51 |      4 |   360M |  7,000 | 21.4 GiB |       9,339 |        233 Days

_haxxor_ wrote:
Btw how did you get 10000 ?
"One way to measure how good a table is, is to do "key space / (chain length * (chain length + 1) / 2 * number of tables)" this number should be at least 10000."

I just picked a number that isn't really low. The higher the number the better as long as the size of the tables are manageable. It's basically so that someone doesn't pick a chain length of 100 or 10,000,000. You should also look at the time it takes to generate the end points when cracking a hash and make sure it is not too high. Also a nice little trick for indexing is to make the number of chains just under 2^n (where n is an integer). This way the tables are slightly more space efficient.


- Sc00bz -

viewtopic.php?p=10958#p10958

update 19.08.2010
-------------------
1 : 0.8646462849 Max (rainbow table)
2 : 1-(1-0.8646462849)^2 = 0.98167937181 (miss 1 in 54.58)
3 : 1-(1-0.8646462849)^3 = 0.9975202349 (miss 1 in 403.26)
4 : 1-(1-0.8646462849)^4 = 0.99966435458 (miss 1 in 2979.33)
5 : 1-(1-0.8646462849)^5 = 0.9999545691458 (miss 1 in 22011.62)
6 : 1-(1-0.8646462849)^6 = 0.99999385076511 (miss 1 in 162624.34)
7 : 1-(1-0.8646462849)^7 = 0.99999916767821 (miss 1 in 1201486.78)
8 : 1-(1-0.8646462849)^8 = 0.999999887342154 (miss 1 in 8876718.86)
9 : 1-(1-0.8646462849)^9 = 0.999999984751342 (miss 1 in 65582192.15)
10 : 1-(1-0.8646462849)^10 = 0.99999999793603749 (miss 1 in 484528573.5)
...
n : 1-(1-0.8646462849)^n

Sc00bz wrote:
1epi wrote:
Sc00bz, how did you get 0.8646462849 for one table ?
273/(206+3 sqrt(1338)) ? why ?

Pick pretty much any keySpace
Set chainCount = keySpace
I picked a chainLen of 50000 for that, but it doesn't change much as the chain length goes up.
expectedUniqueChains = euc(chainLen)
euc(1) = chainCount
euc(i) = keySpace * (1 - e ^ (-euc(i - 1) / keySpace))
perfectTableSuccessRate = 1 - (1 - uniqueChains / keySpace) ^ chainLen <--- that's about equal for some reason I'm getting a memory allocation error with that character.

10k: 86.4587076220994%
20k: 86.4622770147352%
50k: 86.4646284852614%
100k: 86.4654875417649%
150k: 86.4657912004252%
200k: 86.4659483369251%
500k: 86.4662457462117%

http://cryptohaze.com/forum/viewtopic.php?p=738#p738

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 11 Jul 2009, 23:31 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
Is there a description of how indexed rainbow tables works?

Since rainbow tables can be really big they are split into several files usually 1 GiB in size. N and M are the totals for all the files in the rainbow table. All the rainbow table sets currently generated at FRT have 4 tables: "_0_" "_1_" "_2_" and "_3_" Except the really old ones that basically got thrown out. So if you see a rainbow table set with 40 *.rti or *.rt files it means that each rainbow table is split into 10 parts each.

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

rt tables (*.rt) (16 bytes / row):
Start point 1 (64 bits), end point 1 (64 bits)
Start point 2 (64 bits), end point 2 (64 bits)
...
Start point N (64 bits), end point N (64 bits)
The start point and end point pairs are sorted on the end point. So to do a search for "my end point" you can do a binary search for it since the table is sorted by the end points.

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

rti tables (*.rti) (8 bytes / row and N is number of chains):
Start point 1 (48 bits), end point 1 (16 bits)
Start point 2 (48 bits), end point 2 (16 bits)
...
Start point N (48 bits), end point N (16 bits)

rti tables (*.rti.index) (11 bytes / row and M is int((key space + 65535) / 65536)):
end point prefix 1 (40 bits), first chain 1 (32 bits), chain count 1 (16 bits)
end point prefix 2 (40 bits), first chain 2 (32 bits), chain count 2 (16 bits)
...
end point prefix M (40 bits), first chain M (32 bits), chain count M (16 bits)

To get the full end point you do "(end point prefix X << 16) + end point Y" where Y is between "first chain X" and "first chain X + chain count X - 1"
So to do a search for "my end point" you do "my end point prefix = my end point >> 16" and search for "my end point prefix" in a *.rti.index file lets say it's row Z (my end point prefix == end point prefix Z). Now you read "chain count Z" rows from the *.rti file starting with row "first chain Z" then you see if "my end point" is one of them.

---Sc00bz---

Thank you for the post, but I am still not sure I understand. Could you seperate the parts where the table is generated, and the parts where the table is searched? Also, it doesnt see that the bits add up right (to 64). Could you explain?

---shifter1---

For rti tables the chains are generated with incremental start points instead of random start points. Since we don't generate more than 2^48 chains per table the start point can fit in a 48 bit field. Also since tables have a key space of less than 2^56 the end point can be store with 56 bits (16 bits in the end point field and 40 bits in the end point prefix field).

Let's say we have a key space of 0x5ffff and we generate these 8 chains:
Code:
Start points              -  End points
00 00 00 00  00 00 00 00  -  00 00 00 00  00 00 e8 79
00 00 00 00  00 00 00 01  -  00 00 00 00  00 02 60 12
00 00 00 00  00 00 00 02  -  00 00 00 00  00 01 fd af
00 00 00 00  00 00 00 03  -  00 00 00 00  00 03 3a 16
00 00 00 00  00 00 00 04  -  00 00 00 00  00 02 d2 f2
00 00 00 00  00 00 00 05  -  00 00 00 00  00 03 3a 16
00 00 00 00  00 00 00 06  -  00 00 00 00  00 05 33 fb
00 00 00 00  00 00 00 07  -  00 00 00 00  00 04 3f c4

This is how it would look like in a finished rt file:
Code:
Start points              -  End points
00 00 00 00  00 00 00 00  -  00 00 00 00  00 00 e8 79
00 00 00 00  00 00 00 02  -  00 00 00 00  00 01 fd af
00 00 00 00  00 00 00 01  -  00 00 00 00  00 02 60 12
00 00 00 00  00 00 00 04  -  00 00 00 00  00 02 d2 f2
00 00 00 00  00 00 00 03  -  00 00 00 00  00 03 3a 16
00 00 00 00  00 00 00 05  -  00 00 00 00  00 03 3a 16
00 00 00 00  00 00 00 07  -  00 00 00 00  00 04 3f c4
00 00 00 00  00 00 00 06  -  00 00 00 00  00 05 33 fb

That is a non-perfect table FRT creates perfect tables this just means that merged chains (duplicate end points) are removed.
Code:
Start points              -  End points
00 00 00 00  00 00 00 00  -  00 00 00 00  00 00 e8 79
00 00 00 00  00 00 00 02  -  00 00 00 00  00 01 fd af
00 00 00 00  00 00 00 01  -  00 00 00 00  00 02 60 12
00 00 00 00  00 00 00 04  -  00 00 00 00  00 02 d2 f2
00 00 00 00  00 00 00 03  -  00 00 00 00  00 03 3a 16
00 00 00 00  00 00 00 07  -  00 00 00 00  00 04 3f c4
00 00 00 00  00 00 00 06  -  00 00 00 00  00 05 33 fb

Then it is indexed:
The .rti file:
Code:
Start points       -  End points
00 00 00 00 00 00  -  e8 79
00 00 00 00 00 02  -  fd af
00 00 00 00 00 01  -  60 12
00 00 00 00 00 04  -  d2 f2
00 00 00 00 00 03  -  3a 16
00 00 00 00 00 07  -  3f c4
00 00 00 00 00 06  -  33 fb

The .rti.index file:
Code:
End point
prefixes        -  First chain  -  Chain count
00 00 00 00 00  -  00 00 00 00  -  00 01
00 00 00 00 01  -  00 00 00 01  -  00 01
00 00 00 00 02  -  00 00 00 02  -  00 02
00 00 00 00 03  -  00 00 00 04  -  00 01
00 00 00 00 04  -  00 00 00 05  -  00 01
00 00 00 00 05  -  00 00 00 06  -  00 01

* Note that all fields are stored in little endian so the bytes are flipped in each of the fields:
Code:
00 00 00 00  00 00 00 02  -  00 00 00 00  00 01 fd af
would be
02 00 00 00  00 00 00 00  -  af fd 01 00  00 00 00 00

00 00 00 00 03  -  00 00 00 04  -  00 01
would be
03 00 00 00 00  -  04 00 00 00  -  01 00

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

Searching for end point "00 00 00 00 00 02 d2 f2" (I'm just going to do linear search instead of binary search to make this easier)
.rt file:
Code:
Start points              -  End points
00 00 00 00  00 00 00 00  -  00 00 00 00  00 00 e8 79 <- not "00 00 00 00 00 02 d2 f2"
00 00 00 00  00 00 00 02  -  00 00 00 00  00 01 fd af <- not "00 00 00 00 00 02 d2 f2"
00 00 00 00  00 00 00 01  -  00 00 00 00  00 02 60 12 <- not "00 00 00 00 00 02 d2 f2"
00 00 00 00  00 00 00 04  -  00 00 00 00  00 02 d2 f2 <- found "00 00 00 00 00 02 d2 f2"
00 00 00 00  00 00 00 03  -  00 00 00 00  00 03 3a 16
00 00 00 00  00 00 00 05  -  00 00 00 00  00 03 3a 16
00 00 00 00  00 00 00 07  -  00 00 00 00  00 04 3f c4
00 00 00 00  00 00 00 06  -  00 00 00 00  00 05 33 fb

-------
Searching for end point "00 *00 00 00 00 02* **d2 f2**" in rti file format
Searching for "*00 00 00 00 02*" in the end point prefixes column (I'm just going to do linear search instead of binary search to make this easier).
.rti.index file:
Code:
End point
prefixes        -  First chain  -  Chain count
00 00 00 00 00  -  00 00 00 00  -  00 01  <- not "*00 00 00 00 02*"
00 00 00 00 01  -  00 00 00 01  -  00 01  <- not "*00 00 00 00 02*"
00 00 00 00 02  - +00 00 00 02+ - -00 02- <- found "*00 00 00 00 02*" now we go to chain number "+00 00 00 02+" and there are "-00 02-" chains with this end point prefix
00 00 00 00 03  -  00 00 00 04  -  00 01
00 00 00 00 04  -  00 00 00 05  -  00 01
00 00 00 00 05  -  00 00 00 06  -  00 01

.rti file:
Code:
Start points       -  End points
00 00 00 00 00 00  -  e8 79  <- chain number  "00 00 00 00"
00 00 00 00 00 02  -  fd af  <- chain number  "00 00 00 01"
00 00 00 00 00 01  - .60 12. <- chain number "+00 00 00 02+" <- ".60 12." not "**d2 f2**"
00 00 00 00 00 04  - ,d2 f2, <- chain number  "00 00 00 03"  <- ",d2 f2," found "**d2 f2**"
00 00 00 00 00 03  -  3a 16  <- chain number  "00 00 00 04"
00 00 00 00 00 07  -  3f c4  <- chain number  "00 00 00 05"
00 00 00 00 00 06  -  33 fb  <- chain number  "00 00 00 06"


---Sc00bz---

viewtopic.php?f=2&t=1223

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 14 Oct 2009, 13:35 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
Upper "limit" of chainLength ?

65537 you can go higher but the table index needs to be weird.
Code:
Chain Length Range    | Table Indexes
----------------------+----------------------
        2 -    65,537 | 0,   1,   2,   3, ...
   65,538 -   131,073 | 0,   2,   4,   6, ...
  131,074 -   262,145 | 0,   4,   8,  12, ...
  262,146 -   524,289 | 0,   8,  16,  24, ...
  524,290 - 1,048,577 | 0,  16,  32,  48, ...
1,048,578 - 2,097,153 | 0,  32,  64,  96, ...
2,097,154 - 4,194,305 | 0,  64, 128, 192, ...
4,194,306 - 8,388,609 | 0, 128, 256, 384, ...


_haxxor_ wrote:
how did you get those numbers?

Code:
for (nPos = 0; nPos < nRainbowChainLen - 1; nPos++)
{
   cwc.IndexToPlain();
   cwc.PlainToHash();
   cwc.HashToIndex(nPos);
}

Code:
m_nReduceOffset = 65536 * nRainbowTableIndex;
...
void CChainWalkContext::HashToIndex(int nPos)
{
   m_nIndex = (*(uint64*)m_Hash + m_nReduceOffset + nPos) % m_nPlainSpaceTotal;
}

So nPos can be 0 to 65535 (2^16-1) when calling HashToIndex() without interfering with the table index. For nPos to be 65535, nRainbowChainLen needs to be 65537 (2^16+1). Once nRainbowChainLen is more than 65537 you need to the table index to have it's lowest bit zero. So 0, 2, 4, 6, ... in binary it's 000, 010, 100, 110, ...

When nPos reaches 2^17 (nRainbowChainLen > 2^17+1) it will interfere with the table index so you need the lowest two bit to be zero. So 0, 4, 8, 12, ... in binary it's 0000, 0100, 1000, 1100, ...

-Sc00bz
----------
viewtopic.php?f=2&t=1449

_________________
a2480f25 blog.


Top
 Profile  
 
PostPosted: 09 Nov 2009, 20:43 
Offline
Perfect Table

Joined: 02 Apr 2008, 15:10
Posts: 927
Location: Bucharest, Romania
keySpace upper "limit" of FreeRainbowTables.com ?

Short answer : ~ 2^51
Sc00bz's explanation :

The limit is something higher than 2^51.38 and that's being limited by 20 mbps bandwidth and it will take 66 days for 99.9%. Only problem is it's 2TB so not many people will be able to download it if the server had enough bandwidth to upload it. For some reason no one knows (99% of people) how to set up their router to forward ports to their computer or sets maximum upload to near zero. So torrents don't work to well.

Code:
Table Set                              | log2(key space)
---------------------------------------+----------------
mixalpha-numeric#1-8                   |      47.66
hybrid(loweralpha#7-7,numeric#1-3)#0-0 |      43.08
loweralpha-space#1-9                   |      42.85
alpha-space#1-9                        |      42.85
all-space#1-7                          |      42.78
loweralpha-numeric-symbol32-space#1-7  |      42.78
mixalpha-numeric-space#1-7             |      41.86
loweralpha-numeric-space#1-8           |      41.72
alpha-numeric-space#1-8                |      41.72
numeric#1-12                           |      40.02
mixalpha-numeric-all-space#1-6         |      39.43
hybrid(loweralpha#6-6,numeric#1-3)#0-0 |      38.38
alpha-numeric#1-7                      |      36.23

_________________
a2480f25 blog.


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

All times are UTC + 1 hour [ DST ]


Who is online

Users browsing this forum: Google [Bot] and 2 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:  
cron
Powered by phpBB® Forum Software © phpBB Group