Printable View
Hi,
I know there are quite a few distributed computing projects out there, but has anyone ever thought of one to compute rainbow tables? I'm wondering if there is any reason it wouldn't work. The finished tables could be available for the public via a torrent file, so you wouldn't need to worry about the cost of the bandwitdth of that many people downloading rainbow tables. I think this would be a useful project, but can anyone find any flaws in it?
Thanks. :)
There are tables on the net to use already and 99.999% of people have no space for such a monster and really who wants to dl multiple terabytes? (or at very least many, many gigs)
I've yet to find good rainbow tables that are free, and you'd have to be using a ridiculous amount of characters to have a terabyte-sized rainbow table. I'd definately download a 10-20gig rainbow table if available.
Jareds411
AFAIK most rainbow tables are produced using distributed computing techniques. I guess government agencies may use supercomputers?
I have seen 14 character (all keyboard characters) upper & lower case tables on sale for $800. They take up 60 Gb :eek: They were produced using distributed computing, but I am afraid that I cannot remember the exact resources that were used..............it took quite a few months.
As for "free"..................what would be the justification for providing them "free"?
:)
Hi
Nihil is right - rainbow tables can be produced in distributed mode.
But Jareds411, I salute you for the idea, which you had independently :)
It is possible to run the generation in embarrassingly parallel mode[1],
which shows "optimal" scaling - there is no communication from one node
to the other involved. Example for 7-byte password:
1. CPU: starting with a, and check the corresponding keyspace.
2. CPU: starting with b
...
70. CPU: starting with !
Feasibility?
Let us take an alphabet with 70 symbols (alphanumerics plus some specials).
- Each CPU has to look at a keyspace 70^6 = 117 billion elements.
- Assume a MD5 calculation of about 3.5 million hashes per second (I just run that benchmark
on a standard CPU (3Ghz, 32bit) using pure MD5 (fixed passwords, no comparison,
no writing to disc), so it is an upper limit)
-> 10 hours per CPU needed. (lower limit. reallife: multiply with 4 :) )
-> 700 CPU hours in total needed.
-> non-compressed file: 24 byte * 117 billion = 2.6 TB
-> compressed: ~ 250 GB
I claim, a Beowulf-Cluster provides as good a performance
as a supercomputer :) MD5 seems awkward to optimise for
vector-computation, the memory involved in the computation
is small (ie will fit into L2 or L3). This is just a guess of course,
and the whole considerations does not involve additional I/O time)
Cheers.
[1] http://en.wikipedia.org/wiki/Embarra...rallel_problem
I've seen a couple of rainbow tables provided free, this one esspecially
http://rainbowtables.shmoo.com/
i2c
I don't think that the "free" ones are much more than proof of concept exercises. AFAIK they will only work with 7 character passes.
The amount of computing power and effort required to set up full blown tables makes it highly unlikely that they will be provided free.
i2c
You will notice that the tables in your link are missing the "€" symbol. :D
The justification for providing the tables for free would be that people provided their processor time for free, so why not everyone share in the rewards too?
Well,
I think that it is just too large a project. Also, the tables get very large once you get beyond the 14 character limit of Windows 9x systems. Just think about ASCII characters as well :eek:
Anyway, what use would they have, other than to law enforcement agencies or professional recovery companies?
I really cannot see anyone bothering in a home computing environment.
Hi
I did a few benchmarks in order to answer Jareds411 question -
I think my point of argumentation was not clear from my previous
post. Following is a "Proof of concept", as nihil pointed it out :),
which supports his conclusion.
-> Distributed computation (eg. a la seti@home) does not
make sense in a (standard) home-user environment
Considering a 1Mbit/s sustained internet connection, it takes you as
much time to download a rainbow-table as to generate one youself!
Object: rainbow table, 70-symbols alphabet, 7-chars password
Production time (MD5, 70^7 non-optimised, standard CPU) : takes 1000h to produce
Download time (high compression (theory): 256 GByte table): takes 580h to download
It is your choice: Shall I use my bandwidth or my CPU?
Note: Apart from all this, authentication mechanisms should not
depend on the "uncrackablity" of some hashes - which should not
be "available" anyway. But, well, common-user real-world just is
like that.
Cheers.
P.s. I am happy if you can point out the errors in my chain of
argumentation.
------------------------
For the interested ones:
Benchmark results (70^5 passwords, I/O added!) - because I can :D
(gcc=gnu cc, icc=intel compiler, mcc=microsoft compiler)
Code:XEON 3Ghz (gcc -O3) : 15m53.080s
XEON 3Ghz (icc -O3 -axW) : 12m19.424s
OPTERON 1.8 Ghz (gcc -O3): 17m53.259s
ITANIUM 1.6 Ghz (icc -O3): 12m30.017s
ITANIUM 1.6 Ghz (gcc -O3): 14m19.163s
AMD 3Ghz (mcc) : 13m28.013s
As you can see, very different architectures result in the same performance,
if one uses non-optimised, unspecific code for the machine. From experience,
speed gains of factor 2 to 100 (!) can be achieved by simply the
- choice of an optimal data structure
- choice of an optimal order of the computation
without even making use of further advantages of SSEx-instructions! I also
started a run on an old-generation cray, but it performed too bad, so I stopped
in order not to waste precious computation time.
Hi sec_ware
I cannot see anything wrong with your argument, even if your numbers may not be absolutely accurate. I think they clearly indicate the ball park that we are dealing with. And you were only looking at the MD5 hash?
Downloading huge tables would hardly be an option, as who would host these huge tables and have the bandwidth to support people downloading them? :confused:
The big ones I have seen come on DVDs or CDs, and quite a lot of them. Who is going to pay for the media, burn it then ship it? After all, the people who would notionally subscribe to this project would only be contributing computer time?
Who would assemble the end result. Burn it to DVDs, process requests, pack the product and ship it? That takes TIME as well as money.
Anyway, most of us would have to spend a fair amount on the additional storage required to handle huge rainbow tables. In fact, I suspect that a lot would have to build a whole new box :eek:
I just think that the whole project would be too large and costly.
If you look at SETI and Folding, they have a properly funded and organised administrative infrastructure to collect and collate data, and they are not sending massive files to the contributors.
Just my thoughts
Hi Nihil
The numbers (alphabet, password-length) are taken for illustrative purposes
only, as well as the algorithm chosen. I had a MD5 implementation at hand,
so I used it. DES and MD4, although used in the [NT]LM, are of no interest
for my purposes :)
I think, you made the point.
Useful tables are computationally expensive and huge. Standard distribution
channels are not suited for those kind of products. Who is interested in
100+ DVD's except specialised companies, global players and government/military,
and in addition, has the necessary equipment? And who is offering such a service
with profit worth the effort? Sarca[1] sells 18 Gbyte LM Hash Tables on 5 DVD's
for 95 Euro...Cheap, but you won't come far with those tables I claim.
In a home-user environment, tables of dictionary-like entries would be more promising,
and can be generated locally in principle as effective as by downloading it...
Cheers.
[1] http://sarcaprj.wayreth.eu.org/
I can tell you where you're wrong. :p First, I'm talking about using LM hashes, and if you read the rainbowcrack faq you'll see that MD5 takes way less time to compute. Also, your estimated size of the rainbow table is rather huge.
Edit: No one host needs to host these. I sugested using Bittorrent in my first post, which means the people that downloaded it would also host it.
Jareds,
I see your points - and you are right from you point of view and sources.
Let me elaborate :)
My choice MD5 did not reflect your initial goal. You would like to generate
LM hashes rainbow table. Note, I have assumed 3.5 Mio hashes a second
for MD5 (but benchmarked 2 Mio. hashes), while Oechslin[1] achieved in
2003 700.000 a second for LM...
My estimate of the required table size is based on the assumption of a
100% crack. One entry in my table (unoptimised) requires 7 bytes for the
password and 16 bytes for the MD5 hash about 24 bytes per hash :)
The number of possible values is based on your alphabet: I took a
huge number of elements (70), hence my estimate.
The number of elements in the alphabet, the length of the password, but
also the to be achieved percentage of successful "cracks" does massively
influence the size of the keyspace = size of disk storage.
Example configuration 4: (from antsight.com[2]): LM hash!
Plaintext-Password: 1-7 bytes
Alphabet: 68 bytes
Success-Rate: 99.9%
Disk-usage: 119 GB !
If you want a useful, accurate table, this is the amount of
storage you will need, disregarding the computation time,
for <=7 byte passwords!
Cheers.
[1] http://lasecwww.epfl.ch/~oechslin/pu...s/crypto03.pdf , p4
[2] http://www.antsight.com/zsl/rainbowc...igurations.htm
jareds411
I am sure that you must appreciate that a set of rainbow tables to handle a Win2K or XP pass of 127 characters is going to be rather substantial, particularly with all keyboard AND ASCII characters included?Quote:
Also, your estimated size of the rainbow table is rather huge.
Oh sure, on their itsy bitsy home computers? :D For these tables to be any good they HAVE to be big. And bittorrent is just a file sharing app like any other.................someone has to pay for the bandwidth.Quote:
No one host needs to host these. I sugested using Bittorrent in my first post, which means the people that downloaded it would also host it.
Now I get 0.5 Gb a day on my ADSL plan. That would be like 120 days worth for 60Gb tables that you can buy for $800? With me paying for the electricity, the wear and tear on my equipment, and taking the risk of an electrical fire?...............and that would be me doing nothing myself..........
Anyway, the question has not been raised, so I shall...............this stuff is for cracking passwords, not a generally approved activity?..............and I am going to leave my system open to people who want that sort of stuff.............. :rolleyes:
No Way!
Actualy it was designed specificaly to share large files. It is far from like any other file sharing app.http://www.bittorrent.com/introduction.htmlQuote:
And bittorrent is just a file sharing app like any other.................someone has to pay for the bandwidth.
Gives a fair over view of how it works
Jinxy,
Bittorrent is not designed for the size/volume that we are talking about here. Neither are most home ADSL services. Hence it is effectively no different from any other file sharing system, it is just as impractical as the rest.
Unless you wish to be limited to proof of concept type offerings as I mentioned earlier.
My cable internet gets unlimited bandwidth. :P
As an experiment I thought I would d/l one of the free rainbow tables. 10 gig let's see how long it takes.
There is only 10 seeds and 11 leachers and i'm not at full speed yet. So i'm looking at about 24 hours.
Seems doable to me.
Just an FYI, the LM hash tables availble there are for 1-7 and a standard LM hash used by windows is two seperate 7 character hashes pushed together so these tables can be used for pass up to 14 characterQuote:
Originally posted here by nihil
I don't think that the "free" ones are much more than proof of concept exercises. AFAIK they will only work with 7 character passes.
The amount of computing power and effort required to set up full blown tables makes it highly unlikely that they will be provided free.
i2c
You will notice that the tables in your link are missing the "€" symbol. :D
edit = there is rainbowtables.shmoo.com
Hi
staticblackz, thanks for the reminder! Mea culpa, excellent
comment. With the 68 symbols alphabet - configuration (116 GB)
given above, you will crack most LM hashes[1].
One more reason to disable the storage of LM hashes[2] for
downwards compatibilities! :)
To be nitpicking, but complete: The full possible alphabet for
theLM hash consists of 142 symbols. The table size then will
be about 170 times larger, ie 20 TB :D
Cheers
[1] http://www.antionline.com/showthread...r=1#post828847
[2] http://support.microsoft.com/default.../q299/6/56.asp
In addition to staticblackz post, I would also like to remind you that LM hases are all coverted to uppercase before hashing, and the special characters '/', '\', '[', ']', ':', ';', '|,' ,'=', ',','+', '*', '?', '<', '>' are not allowed. I suspect a keyspace of 142 characters is a bit generous. :)
-Maestr0
After reading the entire thread, it becomes apparent that each one having a complete rainbow table (all possible keyboard chars in any encryption format) would be entirely insane to say the least.
So why not use technology such as bittorrent, seti at home, distributed.net and build a system whereby instead of housing the entire table, we could house only 50MB or 1GB or whatever seems viable.
Set up a few distributed servers running databases that corrolate who has which segment, add in a frontend which allowes users to submit passwords, and have the frontend servers send off queries to the various backends...
This might take longer than a minute or two to get all the answers back, but it negates the need for housing 20TB of data or spending 1000hours generating tables...
You can even add various frontends (web based, ssh/telnet etc.) for various types of users as well as control the backends to allow only requests between certain times etc.
The biggest challange here would not be space or bandwidth, but making sure that the entire 20TB is online at any given point in time - with a little thought i'm sure we could combat that by allowing a logging server taking ID's (each new request has a unique ID) and matching them against what's currently online, and sending back information with regard to which segments were tried and which havn't - allowing you to resubmit it, or even have it e-mailed to you.
Just a thought....
No, spoken like a true dork.........the biggest challenge would be staying out of the Federal Pen with Bubba for company................jeez............get a life will you?Quote:
The biggest challange here would not be space or bandwidth, but making sure that the entire 20TB is online at any given point in time
You might as well set up a store selling sawed off pump action shotguns and carnival masks :D
Who is going to host it?..............if you think the RIAA are bad.............just try some of the crap you are suggesting and see what happens :eek:
/me would rather spit in the face of the RIAA, than the NSA, FBI, SS, Interpol, CIA and whatever. Those guys don't mess around................trust me.
I have still not had a logical answer as to why anyone would LEGITIMATELY want
such a service :rolleyes:
EDIT: Please provide an answer, as it seems to me that anyone with a legitimate need for this password cracking technology will have the funds to properly host and support it.
I see no merit in making it available to sh1tbag skiddies, which is what seems to be being proposed here?
You could also say why would anyone want Lophcrack, john the ripper, nmap, nessus, satan and the list goes on and on and on. Who was it that said, "because it's there"???Quote:
I have still not had a logical answer as to why anyone would LEGITIMATELY want
such a service
Thats not what I see here. I see two trains of interest:Quote:
I see no merit in making it available to sh1tbag skiddies, which is what seems to be being proposed here?
1/ The distributed compiling of rainbow tables and their mathamatical effectiveness.
2/ The huge size of the results and how they could be effectivly distributed.
One of the, absolute, best things about the internet. It is based on open standards and is a medium for the free and unhindered sharing of data/information. This has lead to a multitude of un-forseen problems, script kiddies, virii, malware and crackers etc, etc and other emergant systems. However, these problems have forced people to think to a higher level, to combat these problems.
This is how I see this thread.
I have simplified this argument
Just an idea that crossed my mind what about a BitTorrent style Distributed rainbowtable. Once someone generates new table, that gives them access to a program of some type that allows access to others running the same and runs the hash on their tables so just a large network of rainbowtables interconnected. That solves the HardDrive space issues but there is also a dependency issue as the same with bittorrent. You need lots of people. Any Thoughts?