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.