mersenneforum.org > Math VDF (Verifiable Delay Function) and PRP
 Register FAQ Search Today's Posts Mark Forums Read

2020-06-21, 02:30   #166
preda

"Mihai Preda"
Apr 2015

27·32 Posts

Quote:
 Originally Posted by patnashev 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

 2020-06-22, 09:11 #167 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 7,013 Posts 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.
 2020-06-22, 09:43 #168 patnashev   "Pavel Atnashev" Mar 2020 37 Posts Do you construct the full exponent for each point or group them?
2020-06-22, 15:53   #169
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

7,013 Posts

Quote:
 Originally Posted by patnashev Do you construct the full exponent for each point or group them?
They are grouped. A very simple recursive routine does the trick.

 2020-06-22, 17:57 #170 patnashev   "Pavel Atnashev" Mar 2020 3710 Posts 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.
2020-06-22, 21:52   #171
preda

"Mihai Preda"
Apr 2015

27×32 Posts

Quote:
 Originally Posted by patnashev 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?

2020-06-22, 21:55   #172
preda

"Mihai Preda"
Apr 2015

27·32 Posts

Quote:
 Originally Posted by Prime95 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?

2020-06-22, 22:51   #173
patnashev

"Pavel Atnashev"
Mar 2020

1001012 Posts

Quote:
 Originally Posted by preda 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 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 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.

2020-06-22, 23:57   #174
preda

"Mihai Preda"
Apr 2015

100100000002 Posts

Quote:
 Originally Posted by patnashev 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.

2020-06-23, 01:09   #175
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

7,013 Posts

Quote:
 Originally Posted by preda 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
 main.c (8.7 KB, 15 views)

Last fiddled with by Prime95 on 2020-06-23 at 01:10

2020-06-23, 01:12   #176
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

7,013 Posts

Quote:
 Originally Posted by patnashev 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

 Similar Threads Thread Thread Starter Forum Replies Last Post rula Homework Help 3 2017-01-18 01:41 ixfd64 PrimeNet 7 2008-10-20 20:45 JHagerson Forum Feedback 1 2006-05-13 21:30 vaughan ElevenSmooth 5 2005-09-08 17:17 ltd Prime Sierpinski Project 10 2005-08-08 13:38

All times are UTC. The time now is 12:31.

Fri Aug 7 12:31:38 UTC 2020 up 21 days, 8:18, 1 user, load averages: 2.87, 2.45, 2.35