Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Mon, 10 Aug 2015 16:06:17 +0200
From: Marek Wrzosek <marek.wrzosek@...il.com>
To: john-users@...ts.openwall.com
Subject: Can you help me? I need more valuable papers about time-memory
 trade-off.

Hi

I've been reading lately about rainbow tables (or more generally about
time-memory trade off). Philippe Oechslin's "Making a Faster
Cryptanalytic Time-Memory Trade-Off" paper is very educational but
doesn't tell anything useful about reduction functions. How are that
functions created? They should not only map cipher-text into plain-text
space but for t as the length of chain we'll need t-1 different
plain-texts from a single cipher-text.
Start points in rainbowcrack program are created randomly. For ophcrack
program there are already prepared tables but I can only guess how they
were created. E.g.:
for vista free table: "Based on a dictionary of 64k words, 4k suffixes,
64 prefixes and 4 alteration rules for a total of 238 passwords (274
billion)." But there is no information about charset used. Does all
reduction functions produce dictionary word from given hash? How it is
possible?
for vista proba free: "2^39 passwords selected according to the most
probable password patterns and the most probable character sequences
(2nd order Markov Model) within the patterns. Trained on the Rockyou
password set." And there is charset and password lengths.
For two other tables there are only informations about length and charset.
I can only imagine situations that start points are dictionary based or
that they come from Markov model but other "layers" including the end
point are pretty random.
Rainbowcrack on windows can use GPU (CUDA for NVidia cards and OpenCL
for AMD). I presume that GPU is helpful for generating the tables and
for searching (calculating R_t-1, then R_t-2, f_t-1 and so on) multiple
hashes in the same time.
And about salts... They are the known part of plain-text, very random
and greatly increasing the N in formula of P_success. Why there is an
opinion, repeated many times by many people, that we'll need to make
rainbow table for every possible salt? Why not just adjust chain length
and chain count accordingly? More advanced reduction functions would be
needed because plain-text would be in the form of SALTpassword and there
could be different salt strength (length and charset) and different
password strength. Moore law is working for time-memory trade-off faster
than on time part of it alone. Maybe today rainbow tables are more
useful tool for weaker password-storing schemes than it was in 2003.
Do you know any good papers that will answer above questions?

Best Regards
-- 
Marek Wrzosek
marek.wrzosek@...il.com

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.