mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-06-21, 02:30   #166
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

3·5·7·11 Posts
Default

Quote:
Originally Posted by patnashev View Post
Besides attacks, there are also hardware and software errors. And we're much more likely to see them than an attack.
OK, but I don't consider the danger of HW and SW errors an argument for the "hash hacking". I would need a clear reason for why that hash manipulation is needed or useful. Otherwise it's just black magic with unclear benefit.

Specifically: half of the hashes are even; why is that a problem?

Last fiddled with by preda on 2020-06-21 at 02:40
preda is offline   Reply With Quote
Old 2020-06-22, 09:11   #167
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11011100000112 Posts
Default

This is easier to code than I expected! I just created a power=8 proof of M216091 and successfully verified it.

Using 48-bit hashes, the proof construction cost was the equivalent of 15K squarings.
Server-side cost was 2K squarings.
Prime95 is online now   Reply With Quote
Old 2020-06-22, 09:43   #168
patnashev
 
"Pavel Atnashev"
Mar 2020

458 Posts
Default

Do you construct the full exponent for each point or group them?
patnashev is offline   Reply With Quote
Old 2020-06-22, 15:53   #169
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7,043 Posts
Default

Quote:
Originally Posted by patnashev View Post
Do you construct the full exponent for each point or group them?
They are grouped. A very simple recursive routine does the trick.
Prime95 is online now   Reply With Quote
Old 2020-06-22, 17:57   #170
patnashev
 
"Pavel Atnashev"
Mar 2020

37 Posts
Default

A time for hacking fun.

The random exponent is required to have no divisors <1000 in my code. After disabling this check I was able to "hide" a 321 prime by multiplying the result by 3rd root of unity. Every third certificate passes validation.
Code:
***** cert.txt
Certificate RES64: 2C2CCA7B6A1F7703  Time : 4.290 sec.
3*2^2291610+1 is not prime.  Proth RES64: 0000000000000002  Time : 125.660 ms.
***** CERT_DC.TXT
Certificate RES64: 2C2CCA7B6A1F7703  Time : 52.338 sec.
*****
This is because when the random exponent is divisible by 3, the 3rd root of unity turns into 1 and has no effect on the verification process. Generally this works when gcd(random, N-1) != 1.

I strengthened the random to contain no divisors < 10^6. Can also check the gcd, but this doesn't look necessary for Proth numbers.
patnashev is offline   Reply With Quote
Old 2020-06-22, 21:52   #171
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

3·5·7·11 Posts
Default

Quote:
Originally Posted by patnashev View Post
A time for hacking fun.

The random exponent is required to have no divisors <1000 in my code. After disabling this check I was able to "hide" a 321 prime by multiplying the result by 3rd root of unity. Every third certificate passes validation.
Code:
***** cert.txt
Certificate RES64: 2C2CCA7B6A1F7703  Time : 4.290 sec.
3*2^2291610+1 is not prime.  Proth RES64: 0000000000000002  Time : 125.660 ms.
***** CERT_DC.TXT
Certificate RES64: 2C2CCA7B6A1F7703  Time : 52.338 sec.
*****
This is because when the random exponent is divisible by 3, the 3rd root of unity turns into 1 and has no effect on the verification process. Generally this works when gcd(random, N-1) != 1.

I strengthened the random to contain no divisors < 10^6. Can also check the gcd, but this doesn't look necessary for Proth numbers.
What do you mean when you say "by multiplying the result by the 3rd root of unitity", what is the "result"?

Why do you use the 3rd root instead of the 2nd root of unity? (I would expect the factor "2" to be the worst in the hash, why not use that?)

How would the attack look for a (small) mersenne number?
preda is offline   Reply With Quote
Old 2020-06-22, 21:55   #172
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

22038 Posts
Default

Quote:
Originally Posted by Prime95 View Post
They are grouped. A very simple recursive routine does the trick.
Grouped -- does that mean that you keep a large number of residues (up to thousands) up in RAM? Or do you R/W temporaries to disk?
preda is offline   Reply With Quote
Old 2020-06-22, 22:51   #173
patnashev
 
"Pavel Atnashev"
Mar 2020

37 Posts
Default

Quote:
Originally Posted by preda View Post
What do you mean when you say "by multiplying the result by the 3rd root of unitity", what is the "result"?
The y of Pietrzak VDF, the last point that is uploaded along with a proof. But I do the manipulation before calculation of the proof, so all hashes are computed correctly.

Quote:
Originally Posted by preda View Post
Why do you use the 3rd root instead of the 2nd root of unity?
Because the last point is not the end of the test, there's also a short tail, a few squarings. If I used 2nd root it'd turn into 1 too soon and wouldn't survive until the end of test.

Quote:
Originally Posted by preda View Post
How would the attack look for a (small) mersenne number?
Find a prime Mersenne number N. Find the smallest factor of N-1 which is not 2. Find root = x^((N-1)/factor) != 1. Multiply the last point by root. Pray that the random exponent has this factor too.
patnashev is offline   Reply With Quote
Old 2020-06-22, 23:57   #174
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

3×5×7×11 Posts
Default

Quote:
Originally Posted by patnashev View Post
The y of Pietrzak VDF, the last point that is uploaded along with a proof. But I do the manipulation before calculation of the proof, so all hashes are computed correctly.
[...]
Find a prime Mersenne number N. Find the smallest factor of N-1 which is not 2. Find root = x^((N-1)/factor) != 1. Multiply the last point by root. Pray that the random exponent has this factor too.
OK it seems I'm a bit slow understanding this, please explain in a bit more detail:

Let's assume N-1 has 3 as a factor.

So you find R3!=1 such that R3^3==1, ok. You multiply Y (the final residue) by R3, this is the "faked result". What do you next?

If you compute the middles in the usual way from the true saved residues, the proof would not verify. -- isn't that so? Even if we say that *all* the random hashes are multiples of 3.
preda is offline   Reply With Quote
Old 2020-06-23, 01:09   #175
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

156038 Posts
Default

Quote:
Originally Posted by preda View Post
Grouped -- does that mean that you keep a large number of residues (up to thousands) up in RAM? Or do you R/W temporaries to disk?
Residues are written to disk as the PRP test progresses. At test end, the residues are read from disk - only one in memory at a time - to produce the proof.

I took "grouped" to mean that we do not raise a residue to the power of a product of hashes (e.g. r0 ^ (h0 * h1 * h2)). My proof-of-concept proof generator is attached. calc_middle is the recursive routine that calculates a Middle value to output.
Attached Files
File Type: c main.c (8.7 KB, 18 views)

Last fiddled with by Prime95 on 2020-06-23 at 01:10
Prime95 is online now   Reply With Quote
Old 2020-06-23, 01:12   #176
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7,043 Posts
Default

Quote:
Originally Posted by patnashev View Post
The random exponent is required to have no divisors <1000 in my code.
I changed my random exponent to a prime number between 33 and 48 bits. Stole some Rosetta C code for Miller-Rabin test.

Last fiddled with by Prime95 on 2020-06-23 at 01:12
Prime95 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
phi function rula Homework Help 3 2017-01-18 01:41
delay in crediting? ixfd64 PrimeNet 7 2008-10-20 20:45
Why delay between posts? JHagerson Forum Feedback 1 2006-05-13 21:30
Minimum delay between server connections vaughan ElevenSmooth 5 2005-09-08 17:17
Stats delay ltd Prime Sierpinski Project 10 2005-08-08 13:38

All times are UTC. The time now is 23:19.

Fri Aug 14 23:19:43 UTC 2020 up 1 day, 19:55, 0 users, load averages: 1.05, 1.09, 1.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.