[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150626071711.GA24310@openwall.com>
Date: Fri, 26 Jun 2015 10:17:11 +0300
From: Aleksey Cherepanov <lyosha@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: precomputed attacks for john: rainbow tables and
other ways
On Thu, Jun 25, 2015 at 02:26:56PM -0400, Alain Espinosa wrote:
> 2- 2^31 is too small. In a high end GPU we can exhaust the key space
> in 0.14 second for NTLM hashes or 0.25 for MD5. Yes, less than one
> second.
That's fine, then 1 gpu precompute tasks for a lot of computers
quickly. Everything can tried not waiting for months. It still may be
useful in case of low gpu + high cpu resources.
> 3- One thing worth investigating is mix rainbow tables with John
> incremental or Markov mode, so we had a small rainbow table with the
> more probable candidates. We need to ensure the probability of
> repetitions remains low, but this is interesting, particularly for
> high password lengths where full rainbow tables are to big.
It is possible to put most interesting passwords to the beginning.
(they are already there in case of incremental; I don't know if it is
possible to pick them by numbers), so most interesting passwords has
smaller numbers. Then you start chains from them and store all these
chains, thus you guarantee that these candidates are in table. In
addition you get a lot of candidates from other part of key space
randomly. Tracking can be modified: engine could track only
interesting candidates reducing number of chains to store, so
memory_size/8 candidates could be tracked. But chains would hit
tracked part when difference of sizes of interesting part and other
part is huge.
Another idea about tracking: at any point, we are sure that we tried
all candidates in the beginning. So we can skip their tracking. Also
we can postpone tracking of tail. We can track a frame in key space
and move it when beginning is filled tightly.
For instance
******....*...**....*...*
^
All candidates on the left hand side were tried due to
sequential tries.
So with framing:
v1 v2
******....*...__...._..._
^3 ^4 ^^5
1 is the beginning of the frame.
2 is the end of the frame.
3 is our position in sequential tries.
4 is a tried candidate, it was hit by middle of some chain.
5 are tried candidates hit by middle of chains, but we don't track
them now.
Then we shift our frame and continue generation:
v v
******....*..............
^
This way we need only frame size of memory and skip closest findings
hoping that hits in the tail will be repeated after the shift of the
frame.
Thanks!
--
Regards,
Aleksey Cherepanov
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.
