phc-discussions - Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Sun, 9 Feb 2014 12:25:26 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

On Sun, Feb 9, 2014 at 8:01 AM, Bill Cox <waywardgeek@...il.com> wrote:
> Going back to constant multiplication, my slow algorithm finished
> overnight and got the same 7-add/sub answer.  Here's it's computation
> of 1812433253:
>
> 2 = 1 << 1
> 3 = 2 + 1
> 24 = 3 << 3
> 27 = 24 + 3
> 55296 = 27 << 11
> 16 = 2 << 3
> 15 = 16 - 1
> 55311 = 55296 + 15
> 1812430848 = 55311 << 15
> 19 = 16 + 3
> 2432 = 19 << 7
> 2405 = 2432 - 27
> 1812433253 = 1812430848 + 2405
>
> That was a fun little hack :-)
>
> Bill

I win :-)  Mine actually is faster than what Spiral generated.  Mine
has 4 levels of add/sub, while Spiral had 5.  Here's the calculation:

Spiral:
t3 = shl(t0, 2);
0  4 = 1 << 2
t2 = add(t0, t3);
1  5 = 4 + 1
t5 = shl(t0, 5);
0  32 = 1 << 5
t4 = add(t2, t5);
2  37 = 5 + 32
t7 = shl(t4, 6);
2  2,380 = 37 << 6
t6 = add(t4, t7);
3  2,405 = 2380 + 37
t9 = shl(t2, 26);
1  335,544,320 = 5 << 26
t8 = sub(t9, t6);
4  335,541,915 = 335,544,320 - 2,405
t11 = shl(t0, 4);
0  16 = 1 << 4
t10 = sub(t11, t0);
1  15 = 16 - 1
t13 = shl(t0, 16);
0  65,536 = 1 << 16
t12 = add(t10, t13);
2  65,551 = 65,536 + 15
t14 = shl(t12, 15);
2  2,147,975,168 = 65,551 << 15
t1 = sub(t14, t8);
5  1,812,433,253 = 2,147,975,168 - 335,541,915

My hack:
0 2 = 1 << 1
1 3 = 2 + 1
1 24 = 3 << 3
2 27 = 24 + 3
2 55296 = 27 << 11
0 16 = 2 << 3
1 15 = 16 - 1
3 55311 = 55296 + 15
3 1812430848 = 55311 << 15
2 19 = 16 + 3
2 2432 = 19 << 7
3 2405 = 2432 - 27
4 1812433253 = 1812430848 + 2405

My code was actually minimizing add/sub levels, not the total number.
It's just lucky that it only took 7.  It cannot be done in fewer than
4 levels of add/sub.  Gates are practically free now days, so what
matters is speed.

Bill