mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-06-19, 20:13   #155
patnashev
 
"Pavel Atnashev"
Mar 2020

37 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Bonus, the server upon receiving the big proof file can immediately perform the steps to calculate A[N-1], B[N-1] and discard all the middle values in the proof file, saving server disk space. Even lop B[N-1] down to res64 bits saving more space.
Yes, exactly! No need to store the full proof. Process it immediately and queue the certificate for validation.

Quote:
Originally Posted by Prime95 View Post
In your opinion, is there any security risk in sending A[N-1] to the original tester?
Yes, the risk is real. It's not only the cheaters who want to fake the original test, it's also those lazy ones who rather return their stored B[N-1] than perform a few iterations. And the B[N-1] can be wrong due to hardware error at proof generation stage, which will be detected by the consensus of good verifiers.

Applying random exponent to both sides of the certificate takes little time and basically "encrypts" the certificate for the original tester. (A[N-1]^random, res64(B[N-1]^random))
patnashev is offline   Reply With Quote
Old 2020-06-20, 00:09   #156
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

5×229 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Bonus, the server upon receiving the big proof file can immediately perform the steps to calculate A[N-1], B[N-1] and discard all the middle values in the proof file, saving server disk space. Even lop B[N-1] down to res64 bits saving more space.
OK this sounds good!

It also generalizes nicely, e.g.: there is a new work type, consisting of the tuple:

<candidate, start-residue, number-of-squarings>

The client of such a task would run "number-of-squarings" starting from "start-residue" modulo "candidate".

(here "candidate" is a general expression of the candidate a* b^c +d
Quote:
Originally Posted by Prime95 View Post
Examples: M1234567, 653*3^123456-15
)

The result (what the server receives back) of executing such a work-type is, at the server's choice, either the res64 (res128?) or the full final residue.

Such a work-type would encompass both the classic PRP and the proof "certificate verification". It also allows splitting large PRP tests in smaller pieces, which should address the problem of "abandoned PRP tests" (where a large test is started by a new participant, progresses to e.g. 20% and is abandoned afterwards, work lost; it might even allow useful work to be extracted from the "just heat my CPU to the max for 1hour" system-testing mprime users.)

The drawback, as always, is that full residues are large -- 12MB for 100M exponent (the encoding of the "residue" would support representing small values like "3" without paying the space).

Advantages:
- supports proof "certificate verification"
- supports classic mersenne PRP
- allows splitting one PRP test in multiple sequential tasks
- allows a stronger form of the "offset/shift" protection, secure and without client changes (using the residue^random trick)

(side question: this might be a good time to switch to res128 from res64)
preda is offline   Reply With Quote
Old 2020-06-20, 00:21   #157
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1B6016 Posts
Default

Quote:
Originally Posted by preda View Post
(side question: this might be a good time to switch to res128 from res64)
I was thinking a 256-bit SHA-3 result.
Prime95 is offline   Reply With Quote
Old 2020-06-20, 00:33   #158
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

5×229 Posts
Default

Quote:
Originally Posted by preda View Post

<candidate, start-residue, number-of-squarings>

The client of such a task would run "number-of-squarings" starting from "start-residue" modulo "candidate".

The result (what the server receives back) of executing such a work-type is, at the server's choice, either the res64 (res128?) or the full final residue.
The result would be, at the server's choice, one of:
1. hash of final residue (such as: sha3-256, previously res64)
2. full final residue
3. proof

If "proof" is requested, the "number-of-squarings" included in the task must be a multiple of 2^power (where "power" can be included in the task or fixed before-hand).

Edit: in fact case 2 above, "full final residue", is just a particular situation of Proof with power==0. So it doesn't need special handling, reducing to just two cases.

Last fiddled with by preda on 2020-06-20 at 00:41
preda is offline   Reply With Quote
Old 2020-06-20, 09:30   #159
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

100011110012 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Compromise, 48-bits?

Algorithm:
x = sha-3-256(something)
x = x & (2^48 - 1)
if (x < 2^32) x += 2^48
x = x | 1
while (some combo of x divisible by 3,5,7 or x is composite or x == previous_hash_value) x += 2
return x
I would like to see a clearer explanation of why 32bits won't work, or why it does work. Absent that, I'd prefer to stick with 64, and without the hacks.

I don't like the "hash hardening" scheme -- what attack specifically does it prevent? In particular I don't get why what factors the hash has, or whether it has a small value, matters at all.

Let's consider "the worst possible of all" hash value, zero. The attacker knows that a hash value of 0 is great for him, because it removes the left half from the verification, i.e.:
(A^h *M)^q == M^h *B becomes when h==0: M^q==B.

All the attacker has to do to take advantage of this presumed weakness is this:
1. take some M (by guess, random, or sequential)
2. compute B by raising M to q -- doing a significant number of PRP iterations, let's say at least 1000 iterations in all cases.
3. compute SHA3(B), check low32==zero
4. repeat.

For a 32bit hash, the expected number of repeats of the above loop until zero is found is 2 billion (i.e. half of 2^32), which multiplied with 1000 PRP iterations comes to 2 trillion PRP iterations. I say, not a practical attack, [much] more expensive than "just run the damn test".

Not to mention what the work would be with a 64bit hash..

Last fiddled with by preda on 2020-06-20 at 09:34
preda is offline   Reply With Quote
Old 2020-06-20, 09:39   #160
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×32×311 Posts
Default

Quote:
Originally Posted by preda View Post
... 2 trillion PRP iterations. I say, not a practical attack ...
... today.

But in a few years perhaps 2T iterations becomes easy?

I'd say, let's not go down the 32-bit route. From past history 32-bits used to be considered enough-to-make-things-impossible. But look what happened, "suddenly" 32-bits became almost trivial as computers became more powerful.
retina is online now   Reply With Quote
Old 2020-06-20, 10:11   #161
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

23·32·19 Posts
Default

Quote:
Originally Posted by preda View Post
Let's consider "the worst possible of all" hash value, zero. The attacker knows that a hash value of 0 is great for him, because it removes the left half from the verification, i.e.:
(A^h *M)^q == M^h *B becomes when h==0: M^q==B.
You can easily avoid this just set hash=2*hash+1, even if you'd this for every computed hash then no hash value will be zero among h_i.
R. Gerbicz is offline   Reply With Quote
Old 2020-06-20, 10:16   #162
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

114510 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
You can easily avoid this just set hash=2*hash+1, even if you'd this for every computed hash then no hash value will be zero among h_i.
Yes, but I'm not convinced that anything is gained (that the security is improved) by doing that transformation, thus I'd prefer to not do it. There was no mention in the paper of the author being afraid of particular hash values, I really don't think that's the weak point.

Last fiddled with by preda on 2020-06-20 at 10:17
preda is offline   Reply With Quote
Old 2020-06-20, 12:32   #163
patnashev
 
"Pavel Atnashev"
Mar 2020

1001012 Posts
Default

As a matter of fact, the proof is not unique. I ran simulations at small numbers and found some ways to decrease the number of parasitic proofs. First of all, check that x_t != 0 and gcd(x_t, N) = 1. This check can't fail in normal circumstances, but hardware errors can make it happen. Then there're a lot of proofs that differ from each other only by roots of unity modulo N. Since we do exponentiations, roots of unity just disapper from the calculated values. And while the probability of encountering one is low, and it's not practical to look for them on purpose, I feel more comfortable when hashes do not contain small divisors, thus reducing the probability of gcd(hash, phi(N)) != 1.
patnashev is offline   Reply With Quote
Old 2020-06-20, 13:30   #164
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

114510 Posts
Default

Quote:
Originally Posted by patnashev View Post
As a matter of fact, the proof is not unique. I ran simulations at small numbers and found some ways to decrease the number of parasitic proofs. First of all, check that x_t != 0 and gcd(x_t, N) = 1. This check can't fail in normal circumstances, but hardware errors can make it happen. Then there're a lot of proofs that differ from each other only by roots of unity modulo N. Since we do exponentiations, roots of unity just disapper from the calculated values. And while the probability of encountering one is low, and it's not practical to look for them on purpose, I feel more comfortable when hashes do not contain small divisors, thus reducing the probability of gcd(hash, phi(N)) != 1.
We don't require the proof to be unique. We're only concerned with having the correct final residue, that is contained in the proof. In fact, this is the statement of the proof:
starting from A, doing topK iterations, you reach B. The "middles" contained in the proof are there just to offer an easy way to check the statement.

Do you see a way to fake the final residue?

Can you explain in a bit more detail what is the problem with the roots of unity? How easy can they be discovered, and how can they be used for an attack?


PS: I realize A is always 3 in the current setup, and as such is not included in the proof. Maybe we should generalize and allow any starting point, but that's a different topic.

Last fiddled with by preda on 2020-06-20 at 13:34
preda is offline   Reply With Quote
Old 2020-06-20, 14:01   #165
patnashev
 
"Pavel Atnashev"
Mar 2020

37 Posts
Default

Quote:
Originally Posted by preda View Post
Do you see a way to fake the final residue?
No.

Quote:
Originally Posted by preda View Post
Can you explain in a bit more detail what is the problem with the roots of unity? How easy can they be discovered, and how can they be used for an attack?
Besides attacks, there are also hardware and software errors. And we're much more likely to see them than an attack.
patnashev is offline   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 00:40.

Tue Aug 4 00:40:32 UTC 2020 up 17 days, 20:27, 0 users, load averages: 1.87, 1.49, 1.45

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.