phc-discussions - Re: [PHC] A review per day

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]

Message-ID: <540A0506.8070204@ciphershed.org>
Date: Fri, 05 Sep 2014 14:46:30 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - Makwa

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 09/05/2014 01:40 PM, Bill Cox wrote:
> A property that these groups share is that the order of any
> particular sub-group starting with any residue of n minus 1 divides
> numMaxOrder. NumMaxOrder is always (p-3)/2, which is even because p
> is = 3 mod 4. If we just want to avoid the worst bad primes, we
> could require that (p-3)/4 be equal to twice a prime.

This works really well!  I'm calling Makwa primes (safe primes == 3
mod 4) "solid" Makwa primes if (p-3)/4 is also prime.  Here's the list
of solid Makwa primes below 10,000:

Solid primes: 11, 23, 47, 167, 359, 719, 1439, 2039, 2879, 4079, 4127,
4919, 5639, 5807, 5927, 6047, 7247, 7559, 7607, 7727, 9839

- From the previous runs, I see that squaring groups modulo a Blum
integer n = p*q, where p and q are Makwa primes, that there will
always be exactly 4 sizes of groups:

1-long: 3 residues total (including 1)
factor of (p-3)/2 long: p-3 residues
factor of (q-3)/2 long: q-3 residues
factor of (p-3)*(q-3)/2: (p-3)*(q-3)/4 residues

This is simply an observation, not a proof.  Some work would have to
be done by some more number theory inclined person than me to show
this formally.

When (p-3)/4 is prime, and (q-3)/4 is prime, then (p-3)*(q-3)/4 is a
multiple of 4 times two large primes.  The only way this splits is
either into 2 or 4 sets of quadratic residues, meaning that the cycle
length when using "solid" Makwa primes is:

cycle length >= (p-3)*(q-3)/16

For large p and q, this is aproximately 1/16th of n, or only a loss of
at 2 bits.

It looks like we could guarantee this strength.  The code is very
simple to write.  The main downside is that "solid" primes are a small
subset of Makwa primes.  They are quite a bit harder to find than safe
primes.

Here's 10 random results with solid Makwa primes, demonstrating the
strength of this concept:

Finding totals for 6047 4127
Average = 1 , distribution = {1557841: 6231364, 1031: 4124, 1511:
6044, 1: 3} , chance of sub-optimal = 0.162956708566 %
Finding totals for 7247 5639
Average = 1 , distribution = {1: 3, 2818: 5636, 1811: 7244, 5103398:
10206796} , chance of sub-optimal = 0.126060710909 %
Finding totals for 6047 7559
Average = 1 , distribution = {1: 3, 3778: 7556, 5708558: 11417116,
1511: 6044} , chance of sub-optimal = 0.119003887682 %
Finding totals for 7727 5807
Average = 1 , distribution = {2801881: 11207524, 1451: 5804, 1931:
7724, 1: 3} , chance of sub-optimal = 0.120585809445 %
Finding totals for 6047 9839
Average = 1 , distribution = {1: 3, 2459: 9836, 3715549: 14862196,
1511: 6044} , chance of sub-optimal = 0.10675437333 %
Finding totals for 9839 5927
Average = 1 , distribution = {1: 3, 2962: 5924, 2459: 9836, 7283558:
14567116} , chance of sub-optimal = 0.108092510402 %
Finding totals for 7247 7559
Average = 1 , distribution = {1: 3, 3778: 7556, 1811: 7244, 6841958:
13683916} , chance of sub-optimal = 0.108061199007 %
Finding totals for 5639 7607
Average = 1 , distribution = {1: 3, 5357018: 10714036, 2818: 5636,
3802: 7604} , chance of sub-optimal = 0.123451622727 %
Finding totals for 9839 5639
Average = 1 , distribution = {1: 3, 2818: 5636, 2459: 9836, 6929462:
13858924} , chance of sub-optimal = 0.111536362764 %

Maybe I should read the rest of the Makwa paper... but I finished the
security section, and there was no mention of picking safe primes, but
that goes without saying, and no mention of other requirements other
than p == 3 mod 4.  Is this test already taken into account when
picking Makwa primes?

Bill
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJUCgUDAAoJEAcQZQdOpZUZD68P/1zW0dUluGS15hEVgveIQsdT
q+4FHUTCvxmQZABgTvwg6C8VcUybgG+kGqfSwD4x4M0GYg3yKDk9XR4IeYrAbwUT
Z6tl9esgUAP8HXCsXh8Ox7uF/XONaelxxN1ZuAaMxhCU27LRn61BTy0a9v3dLd7Q
OHQjzMRxOwMzGbNZYSKtLXB4Zmhv6gMIoNr1mfhkXjKXvb3YQu6Orz875uxuxZVQ
/TU9nvHaSsB6zBiF8GTlbBOwEytL41Ib+FZ+7sYZv/JgSuPdUWFk5HgPTPHiZJRA
bovjmWMGzSKnf533zb27CMdWdnhOge9Q4NAV+T6cjkBlZxSs2OyU0A2em4IW+HBS
ZCrUpwK1eI9MgFuwZBdrAP6Ekgra6cEkVrZgDaI5gYanCj6VCvy0BI2ZrRolz61c
JGtziOJe8OU+1wMLTR/z/EPC1rWs+QgQGFEYJxDYC7v4gjFYqLwIPXeYLFnx5F65
s2iVQlYpwFWIR0LWSlm0LogzpZNkgBP/wSxjiGYcPjbusXAKbLPhOP5qT/L1pCbf
dslP8fhEGq3rW+M20mN0C2EfyPRzzdQRt/JsVxOUwrUyYJ9Ph60NolMLxzpBmbpJ
CxLAQ5Snd8QTOkVN31ixr1C0Vw/99PBiSSo1k/sI+yPIjznpVBPElnAaIB6eVlyd
rqnfTvVhcRx5YkMQc4M5
=EItL
-----END PGP SIGNATURE-----