20200619, 20:13  #155  
"Pavel Atnashev"
Mar 2020
53_{8} Posts 
Quote:
Quote:
Applying random exponent to both sides of the certificate takes little time and basically "encrypts" the certificate for the original tester. (A[N1]^random, res64(B[N1]^random)) 

20200620, 00:09  #156  
"Mihai Preda"
Apr 2015
7×173 Posts 
Quote:
It also generalizes nicely, e.g.: there is a new work type, consisting of the tuple: <candidate, startresidue, numberofsquarings> The client of such a task would run "numberofsquarings" starting from "startresidue" modulo "candidate". (here "candidate" is a general expression of the candidate a* b^c +d ) The result (what the server receives back) of executing such a worktype is, at the server's choice, either the res64 (res128?) or the full final residue. Such a worktype 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" systemtesting 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) 

20200620, 00:21  #157 
P90 years forever!
Aug 2002
Yeehaw, FL
2·3,581 Posts 

20200620, 00:33  #158  
"Mihai Preda"
Apr 2015
7×173 Posts 
Quote:
1. hash of final residue (such as: sha3256, previously res64) 2. full final residue 3. proof If "proof" is requested, the "numberofsquarings" included in the task must be a multiple of 2^power (where "power" can be included in the task or fixed beforehand). 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 20200620 at 00:41 

20200620, 09:30  #159  
"Mihai Preda"
Apr 2015
10010111011_{2} Posts 
Quote:
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 20200620 at 09:34 

20200620, 09:39  #160 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5740_{10} Posts 
... today.
But in a few years perhaps 2T iterations becomes easy? I'd say, let's not go down the 32bit route. From past history 32bits used to be considered enoughtomakethingsimpossible. But look what happened, "suddenly" 32bits became almost trivial as computers became more powerful. 
20200620, 10:11  #161 
"Robert Gerbicz"
Oct 2005
Hungary
2×3×233 Posts 
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.

20200620, 10:16  #162 
"Mihai Preda"
Apr 2015
7×173 Posts 
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 20200620 at 10:17 
20200620, 12:32  #163 
"Pavel Atnashev"
Mar 2020
43 Posts 
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.

20200620, 13:30  #164  
"Mihai Preda"
Apr 2015
2273_{8} Posts 
Quote:
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 20200620 at 13:34 

20200620, 14:01  #165 
"Pavel Atnashev"
Mar 2020
43 Posts 
No.
Besides attacks, there are also hardware and software errors. And we're much more likely to see them than an attack. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
phi function  rula  Homework Help  3  20170118 01:41 
delay in crediting?  ixfd64  PrimeNet  7  20081020 20:45 
Why delay between posts?  JHagerson  Forum Feedback  1  20060513 21:30 
Minimum delay between server connections  vaughan  ElevenSmooth  5  20050908 17:17 
Stats delay  ltd  Prime Sierpinski Project  10  20050808 13:38 