[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150502220242.GA17153@openwall.com>
Date: Sun, 3 May 2015 01:02:42 +0300
From: Aleksey Cherepanov <lyosha@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: optimization idea for salted hashes
It is possible to lift some computations from the loop for some salted
hashes.
As the base, I consider a loop over all pairs salt + candidate. So if
a part of code is computed only for salt not depending on candidate
then it is possible to precompute it once for each salt. Similarly if
a part of code is computed only for candidate not depending on salt
then it may be computed once per candidate (it may be easy to
implement if we have "for each candidate { for each salt { ... }}"
structure of the loop).
For instance in
dynamic_156 RIPEMD320($s.RIPEMD320($p))
it is possible to pull out RIPEMD320($p) and compute like
$pp = RIPEMD320($p1)
RIPEMD320($s1.$pp)
RIPEMD320($s2.$pp)
...
$pp = RIPEMD320($p2)
RIPEMD320($s1.$pp)
RIPEMD320($s2.$pp)
...
More interesting case:
dynamic_157 RIPEMD320(RIPEMD320($s).RIPEMD320($p))
It is possible to precompute RIPEMD320($s) once for each hash and
RIPEMD320($p) once for each candidate as above.
The list of dynamics possible for that optimization (based on
$ ./JohnTheRipper/run/john --list=format-details --format=dynamic | cut -f 1,7 | grep '\$s'):
dynamic_6 md5(md5($p).$s) 128/128 SSE4.1 10x4x3
dynamic_8 md5(md5($s).$p) 128/128 SSE4.1 10x4x3
dynamic_9 md5($s.md5($p)) 128/128 SSE4.1 10x4x3
dynamic_12 md5(md5($s).md5($p)) (IPB) 128/128 SSE4.1 10x4x3
dynamic_13 md5(md5($p).md5($s)) 128/128 SSE4.1 10x4x3
dynamic_14 md5($s.md5($p).$s) 128/128 SSE4.1 10x4x3
dynamic_15 md5($u.md5($p).$s) 128/128 SSE4.1 10x4x3
dynamic_16 md5(md5(md5($p).$s).$s2) 128/128 SSE4.1 10x4x3
dynamic_38 sha1($s.sha1($s.sha1($p))) (Wolt3BB) 128/128 SSE4.1 10x4x1
dynamic_39 md5($s.pad16($p)) (net-md5) 128/128 SSE4.1 10x4x3
dynamic_40 sha1($s.pad20($p)) (net-sha1) 128/128 SSE4.1 10x4x1
dynamic_55 sha224(sha224($p).$s) 128/128 SSE4.1 4x
dynamic_56 sha224($s.sha224($p)) 128/128 SSE4.1 4x
dynamic_57 sha224(sha224($s).sha224($p)) 128/128 SSE4.1 4x
dynamic_65 sha256(sha256($p).$s) 128/128 SSE4.1 4x
dynamic_66 sha256($s.sha256($p)) 128/128 SSE4.1 4x
dynamic_67 sha256(sha256($s).sha256($p)) 128/128 SSE4.1 4x
dynamic_75 sha384(sha384($p).$s) 64/64 128x1 sha2-OpenSSL
dynamic_76 sha384($s.sha384($p)) 64/64 128x1 sha2-OpenSSL
dynamic_77 sha384(sha384($s).sha384($p)) 64/64 128x1 sha2-OpenSSL
dynamic_85 sha512(sha512($p).$s) 64/64 128x1 sha2-OpenSSL
dynamic_86 sha512($s.sha512($p)) 64/64 128x1 sha2-OpenSSL
dynamic_87 sha512(sha512($s).sha512($p)) 64/64 128x1 sha2-OpenSSL
dynamic_95 GOST(GOST($p).$s) 64/64 128x1
dynamic_96 GOST($s.GOST($p)) 64/64 128x1
dynamic_97 GOST(GOST($s).GOST($p)) 64/64 128x1
dynamic_105 WHIRLPOOL(WHIRLPOOL($p).$s) 64/64 128x1 OpenSSL
dynamic_106 WHIRLPOOL($s.WHIRLPOOL($p)) 64/64 128x1 OpenSSL
dynamic_107 WHIRLPOOL(WHIRLPOOL($s).WHIRLPOOL($p)) 64/64 128x1 OpenSSL
dynamic_115 Tiger(Tiger($p).$s) 32/64 128x1 sph_tiger
dynamic_116 Tiger($s.Tiger($p)) 32/64 128x1 sph_tiger
dynamic_117 Tiger(Tiger($s).Tiger($p)) 32/64 128x1 sph_tiger
dynamic_125 RIPEMD128(RIPEMD128($p).$s) 32/64 128x1 sph_ripmd
dynamic_126 RIPEMD128($s.RIPEMD128($p)) 32/64 128x1 sph_ripmd
dynamic_127 RIPEMD128(RIPEMD128($s).RIPEMD128($p)) 32/64 128x1 sph_ripmd
dynamic_135 RIPEMD160(RIPEMD160($p).$s) 32/64 128x1 sph_ripmd
dynamic_136 RIPEMD160($s.RIPEMD160($p)) 32/64 128x1 sph_ripmd
dynamic_137 RIPEMD160(RIPEMD160($s).RIPEMD160($p)) 32/64 128x1 sph_ripmd
dynamic_145 RIPEMD256(RIPEMD256($p).$s) 32/64 128x1 sph_ripmd
dynamic_146 RIPEMD256($s.RIPEMD256($p)) 32/64 128x1 sph_ripmd
dynamic_147 RIPEMD256(RIPEMD256($s).RIPEMD256($p)) 32/64 128x1 sph_ripmd
dynamic_155 RIPEMD320(RIPEMD320($p).$s) 32/64 128x1 sph_ripmd
dynamic_156 RIPEMD320($s.RIPEMD320($p)) 32/64 128x1 sph_ripmd
dynamic_157 RIPEMD320(RIPEMD320($s).RIPEMD320($p)) 32/64 128x1 sph_ripmd
dynamic_1007 md5(md5($p).$s) (vBulletin) 128/128 SSE4.1 10x4x3
dynamic_1011 md5($p.md5($s)) (WebEdition CMS) 128/128 SSE4.1 10x4x3
dynamic_1012 md5($p.md5($s)) (WebEdition CMS) 128/128 SSE4.1 10x4x3
dynamic_1033 sha1_64(unicode($pass).$salt) 128/128 SSE4.1 10x4x1
dynamic_1501 sha1($salt.sha1($pass)) (Redmine) 128/128 SSE4.1 10x4x1
dynamic_1502 sha1(sha1($pass).$salt) (XenForo SHA-1) 128/128 SSE4.1 10x4x1
dynamic_1503 sha256(sha256($pass).$salt) (XenForo SHA-256) 128/128 SSE4.1 4x
dynamic_2006 md5(md5($p).$s) (PW > 55 bytes, sse2) 128/128 SSE4.1 10x4x3
dynamic_2008 md5(md5($s).$p) (PW > 23 bytes, sse2) 128/128 SSE4.1 10x4x3
dynamic_2009 md5($s.md5($p)) (PW > 55 or salt > 23 bytes, sse2) 128/128 SSE4.1 10x4x3
dynamic_2014 md5($s.md5($p).$s) (PW > 55 or salt > 11 bytes, sse2) 128/128 SSE4.1 10x4x3
MediaWiki md5($s.md5($p)) 128/128 SSE4.1 10x4x3
PHPS md5(md5($p).$s) 128/128 SSE4.1 10x4x3
Is the optimization implemented in john?
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.
