[<prev] [next>] [thread-next>] [day] [month] [year] [list]
```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
```