lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening linuxcveannounce PHC  
Open Source and information security mailing list archives
 

Date: Fri, 05 Sep 2014 13:40:45 0400 From: Bill Cox <waywardgeek@...hershed.org> To: discussions@...swordhashing.net Subject: Re: [PHC] A review per day  Makwa BEGIN PGP SIGNED MESSAGE Hash: SHA1 I am finding difficult to skip Makwa, since I think it has such potential. Makwa is in a category where the code doesn't matter. It could totally suck, and that would be OK. So long as the *idea* is solid, it should move forward. However, the code does not suck. It looks decent, though I have no intention of doing a careful code review right now. Instead of moving on, I am busy trying to convince myself that Makwa is secure from a mathematical point of view. The concern I am working through right now is trying to convince myself that Makwa will have good long cycle lengths when squaring over and over, with effectively zero chance of getting a weak cycle where finding the square root is many times easier. Makwa chooses random large primes of similar size that are "safe primes" (if it doesn't, it needs to!), and that are congruent to 3 mod 4. My theory is that we want p and q to be "good" primes, in that the squaring group will contain all residues other than 1. That would be (p1)/2  1 elements. About half of all safe primes congruent to 3 mod 4 seem to have this property. The other half don't. Here's some basic data about the "good" and "bad" safe primes below 1000 that are congruent to 3 mod 4: Good primes: 7 11 23 59 107 167 263 347 359 587 839 887 983 Bad primes: 47 83 179 227 383 467 479 503 563 719 863 Good prime 7: Order 3 numMaxOrder 2 Good prime 11: Order 5 numMaxOrder 4 Good prime 23: Order 11 numMaxOrder 10 Good prime 59: Order 29 numMaxOrder 28 Good prime 107: Order 53 numMaxOrder 52 Good prime 167: Order 83 numMaxOrder 82 Good prime 263: Order 131 numMaxOrder 130 Good prime 347: Order 173 numMaxOrder 172 Good prime 359: Order 179 numMaxOrder 178 Good prime 587: Order 293 numMaxOrder 292 Good prime 839: Order 419 numMaxOrder 418 Good prime 887: Order 443 numMaxOrder 442 Good prime 983: Order 491 numMaxOrder 490 Bad prime 47: Order 12 numMaxOrder 22 Bad prime 83: Order 21 numMaxOrder 40 Bad prime 179: Order 12 numMaxOrder 88 Bad prime 227: Order 29 numMaxOrder 112 Bad prime 383: Order 96 numMaxOrder 190 Bad prime 467: Order 30 numMaxOrder 232 Bad prime 479: Order 120 numMaxOrder 238 Bad prime 503: Order 51 numMaxOrder 250 Bad prime 563: Order 71 numMaxOrder 280 Bad prime 719: Order 180 numMaxOrder 358 Bad prime 863: Order 44 numMaxOrder 430 Is there any fast way to determine if a prime is a "good" vs "bad" prime? Note that the squaring subgroups can have significantly lower order for "bad" primes. This does not exactly translate to the typical squaring group orders for Blum integers, but from my testing in Python, there is a strong correlation with higher group orders when when we start with "good" primes. A property that these groups share is that the order of any particular subgroup starting with any residue of n minus 1 divides numMaxOrder. NumMaxOrder is always (p3)/2, which is even because p is = 3 mod 4. If we just want to avoid the worst bad primes, we could require that (p3)/4 be equal to twice a prime. Here's "good" primes up to 10,000: 7, 11, 23, 59, 107, 167, 263, 347, 359, 587, 839, 887, 983, 1019, 1307, 1319, 2039, 2459, 2903, 2999, 3467, 3803, 3863, 3947, 4139, 4283, 4679, 4919, 5099, 5387, 5399, 5483, 5639, 5879, 5927, 6599, 6827, 6983, 7079, 7559, 7607, 7703, 8039, 8699, 8747 Here's "bad" primes up to 10,000: 47, 83, 179, 227, 383, 467, 479, 503, 563, 719, 863, 1187, 1283, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2063, 2099, 2207, 2447, 2579, 2819, 2879, 2963, 3023, 3119, 3167, 3203, 3623, 3779, 4007, 4079, 4127, 4259, 4547, 4703, 4787, 4799, 5087, 5507, 5807, 5939, 6047, 6659, 6719, 6779, 6899, 7187, 7247, 7523, 7643, 7727, 7823, 8147, 8423, 8543, 8783, 8819, 8963, 9467, 9587, 9743, 9839, 9887 Here's 10 random "good" runs using "good" primes: Finding totals for 5879 5099 Average = 1 , distribution = {1: 3, 2938: 5876, 287924: 7486024, 2548: 5096} , chance of suboptimal = 0.146391909616 % Finding totals for 5483 5399 Average = 1 , distribution = {1: 3, 2698: 5396, 2740: 5480, 3696260: 7392520} , chance of suboptimal = 0.146946017633 % Finding totals for 6983 4139 Average = 1 , distribution = {1: 3, 3490: 6980, 3608660: 7217320, 2068: 4136} , chance of suboptimal = 0.153822976164 % Finding totals for 5099 6983 Average = 1 , distribution = {1: 3, 3490: 6980, 4446260: 8892520, 2548: 5096} , chance of suboptimal = 0.135649005643 % Finding totals for 5927 7559 Average = 1 , distribution = {1: 3, 5595218: 11190436, 3778: 7556, 2962: 5924} , chance of suboptimal = 0.120341819679 % Finding totals for 7703 4679 Average = 1 , distribution = {1: 3, 3850: 7700, 2338: 4676, 642950: 9001300} , chance of suboptimal = 0.137335709426 % Finding totals for 3863 5483 Average = 1 , distribution = {1: 3, 1930: 3860, 2740: 5480, 528820: 5288200} , chance of suboptimal = 0.176364778917 % Finding totals for 7079 5099 Average = 1 , distribution = {1: 3, 3538: 7076, 4507412: 9014824, 2548: 5096} , chance of suboptimal = 0.134873173244 % Finding totals for 8747 5927 Average = 1 , distribution = {1: 3, 2962: 5924, 6474932: 12949864, 4372: 8744} , chance of suboptimal = 0.113162562329 % The number before the : in the total number of residues in cycles with this length. Here's 10 random "bad runs using "bad" primes: Finding totals for 6779 8819 Average = 1 , distribution = {1: 3, 266684: 14934304, 484: 6776, 551: 8816} , chance of suboptimal = 0.104315086008 % Finding totals for 4259 7523 Average = 1 , distribution = {1: 3, 188: 7520, 25004: 8001280, 532: 4256} , chance of suboptimal = 0.146997544883 % Finding totals for 5807 3779 Average = 1 , distribution = {684872: 5478976, 1: 3, 1451: 5804, 472: 3776} , chance of suboptimal = 0.174599562472 % Finding totals for 4799 7643 Average = 1 , distribution = {1: 3, 916036: 9160360, 764: 7640, 1199: 4796} , chance of suboptimal = 0.135607462891 % Finding totals for 5807 9839 Average = 1 , distribution = {3568009: 14272036, 1451: 5804, 2459: 9836, 1: 3} , chance of suboptimal = 0.109485942398 % Finding totals for 4127 9743 Average = 1 , distribution = {502097: 10041940, 1031: 4124, 487: 9740, 1: 3} , chance of suboptimal = 0.137900419131 % Finding totals for 4007 8819 Average = 1 , distribution = {1: 3, 157586: 8824816, 286: 4004, 551: 8816} , chance of suboptimal = 0.145095313352 % Finding totals for 8423 5507 Average = 1 , distribution = {579296: 11585920, 1: 3, 842: 8420, 1376: 5504} , chance of suboptimal = 0.120061928403 % Finding totals for 6659 9467 Average = 1 , distribution = {11648: 15748096, 1: 3, 1664: 6656, 364: 9464} , chance of suboptimal = 0.102275919917 % Finding totals for 7187 4127 Average = 1 , distribution = {1: 3, 1851676: 7406704, 1796: 7184, 1031: 4124} , chance of suboptimal = 0.152480144621 % The bad run has quite a bit lower cycle lengths on average. I've seen runs with bad primes where the max cycle lengths were lower than p and q. Can anyone point me to the relavant literature so I don't keep working on stuff that's well known? Thanks, Bill BEGIN PGP SIGNATURE Version: GnuPG v1 iQIcBAEBAgAGBQJUCfWZAAoJEAcQZQdOpZUZ8IoP/2Bz+Tf5lLdV32JD8rKfogqT TDedgzJ6HGSuE4tcfGoEqr0pjs3qOoAE7tYHdYG2Tp7bw6wiWLQTSf2rb044B3Ac sG/94srUvQ2yFzGYEi9PfpW2CFj1S9RZvZMGdHD9uK1YNK1cgqDh3/9W7I2cdSWs n/9v6dIvEu0uwz8w/2lDv8cqjjpcLGk2f30lEQ22HRbBWesDN4xSZOVn6QDxWDG1 KWXwxl0bvIeZB+WhW4issXNqelJAhCSQEsHqVezbCGEZezSLb2fNlKo4qqE5ES2P v1RmtfBCteWHeq7rK0/YLF2lH8GKrMrbEXrfeDghMSBjeVq+7OpubIPIsPr06Sxm 7mmK7tdQIPO2P8Pkd+J1WLiCu3EvdyCrP6hqoE/dqGqwilm69q4qo55l/wT9ULbd 1Zgrqym9PksT7ABgJeFKvi5J30OX5sVNiN5e+DvLtDq1LCqfYjOK7GsBMO+YQpEm 8Dk2lpHz9VGy8uwgpo/qXe3SHQqDyC3E4kEd7TQqMF3h2kH1n7hsMTmGReVfVxt9 rp1217OCfUZSjbk0Cn1Mvij+pPBRrkIK7HldR8q+35mymDe6PtN2aBHgbffq2JUt sVFpaMXvMJv5XZUXs/FlAm5AW1hA64NYvWB2T0rT5gr19XrLDhFkUs1jB9WkwWmx W6ur6LEgWWOVA2gEd6+i =uEr5 END PGP SIGNATURE
Powered by blists  more mailing lists