Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Sat, 29 Aug 2015 20:45:02 +0300
From: Aleksey Cherepanov <lyosha@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: length based branching

Common case of data based branching is length based branching. I guess
that some raw formats could get 10%+ speed up if they had a limit on
length and threated part of message block as constants. Also we have
some formats with length limits, most notable for me is raw-sha1-ng:
length limit 15 but it gives 30% speed up.

Separate queues were discussed. But they are complex. I got simpler
solution but not that generic: use 1 pack as in current
implementations, but introduce a bar: if all passwords are shorter
than this length, then a fast algo is used, otherwise slower one that
is capable to handle these lengths.

It is not fully optimal but it can give speed up for common cases
without much coding. I assume that most candidates are not very long.
Also I guess that sequential candidates have similar lengths quite
often (due to rules). As an improvement, john could do local
reordering to fill packs better.

To determine bar, it is possible to check common lists like
rockyou+rules=all. In case of raw-sha1, there is limit implied by
algo: length <= 15 -> algo from raw-sha1-ng, otherwise -> algo from
raw-sha1.

Also it would be nice to implement "fallbacks" in all algorithms with
small limit on length. (Length limits of dynamics were raised.) Or at
least, warn when algorithm does not support desired length (it is
needed to distinguish truncating formats and just not working
formats).

$ john --list=format-all-details | grep -F 'Max. password length in bytes' | grep -o '[0-9]*' | sort -n | uniq -c
      2 7
      6 8
      2 12
      1 14
      3 15
      8 16
      2 20
      9 23
      1 24
      1 30
      9 31
     28 32
      1 35
      4 39
      2 46
      1 47
      1 51
      1 53
     39 55
      2 57
      4 63
     18 64
      1 66
      3 72
      2 75
      1 78
      1 79
      1 80
      8 81
      1 84
      1 95
      2 99
      1 107
    383 110
      3 111
      3 120
     93 125

BTW some sha512 based dynamics could have max length 111 instead of 110.

Format label                         dynamic_86
Max. password length in bytes        110
Algorithm name                       sha512($s.sha512($p)) 128/128 SSE4.1 2x

Format label                         dynamic_80
Max. password length in bytes        110
Algorithm name                       sha512($p) 128/128 SSE4.1 2x

Format label                         Raw-SHA512
Max. password length in bytes        111

Thanks!

-- 
Regards,
Aleksey Cherepanov

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ