[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150829174502.GA8442@openwall.com>
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
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
