VDF (Verifiable Delay Function) and PRP

[Prime95]

Originally Posted by kruoli

I'll leave my file on my server and keep a local copy of it. Additionally, I'll keep my ca. 25 GB of temporary files. If those could be helpful for testing, too, I could make them availible, too.

You can delete the 25GB of temporary files

[ZK19]

Originally Posted by preda

I know we are used to consider the res64 as the PRP result, but we should realize that res64 is a way of validating the PRP result (by running it again (DC) and comparing res64). While res64 is nice, what really matters and what we're really trying to find by doing PRP is the compositeness status of candidates, not the list of res64 of candidates
.

Hello,

I think this an interesting thread, and very useful work for the project. I wanted to add something that occurred to me, although somewhat late in the discussion now.

As noted, with topK above E the server generally can not cheaply verify the res64 or res2048 value. Although, after successfully verifying the certificate, the result of the PRP test is not in doubt. But if the PRP test indicates composite, and at later dates factor(s) are found, the residue could not be used, e.g. in the scheme R. Gerbicz showed here:

https://www.mersenneforum.org/showthread.php?t=23462

to cheaply show (in some cases) that the cofactor is composite, since the stored res2048 value itself could be invalid.

I'm not qualified nor very experienced in relevant fields, so there is a greater likelihood I've misunderstood. Or I might even have missed that this was considered and discounted as being out of scope (in which case I apologise in advance for not thoroughly enough reading around the topic!)

[Prime95]

Originally Posted by ZK19

... since the stored res2048 value itself could be invalid.

Thanks for weighing in.

The res64 and res2048 will be correct, but it is not proven.

What does that mean? Prime95 and gpuowl, grab the res64 value and, in prime95's case, the res2048 value on the way to TopK. Barring a program bug, or malicious user changing the available source code, these values will be correct. Proven means 3^TopK was performed correctly and the probably-prime/composite state of the Mersenne number is certain -- immune from program bugs and malicious users.

[retina]

Have you tested the VDF code in P95 with some of the known primes to check that the prime-found code works?

[Prime95]

Originally Posted by retina

Have you tested the VDF code in P95 with some of the known primes to check that the prime-found code works?

It works on M216091

[kriesel]

Originally Posted by retina

Have you tested the VDF code in P95 with some of the known primes to check that the prime-found code works?

As I recall, prime95/mprime contain special code preventing new retests on known Mersenne primes. So doing as you suggest involves disabling that in the source code. As far as I know there is no equivalent issue in Gpuowl.

[patnashev]

Roots of unity Attack

It is possible to conceal a prime by tampering with the proof and forcing the result of PRP test to be different than 1. In the simplest circumstances an attacker has to perform just two multiplications by -1 to spoil the proof. I was able to do it with 30406^8192+1, and from what I understand it was as easy with GIMPS too.

The attack uses my previous idea of injecting a root of unity into the proof. Ravi Fernando pointed out that it's still possible to contaminate both sides of the proof, with probability of a correct proof being inversely proportional to root's order. The attack happens entirely on client side, the server receives 100% valid proof. And it does not depend on hash hardening or the random exponent.

Attacker can multiply the result and some products by a root of unity during construction of the proof. The root will be raised to unpredictable powers, but
root^hash = root^(hash mod order)
For cubic roots the probability that both products in the certificate will have the same power of the root is 1/3. In cases where no squarings of the result happen at server side, the attacker can use -1 if the first hash is odd.
y_1 = -y*(-u1)^h0 = y*u1^h0
and -x_power will lose minus either with an even hash or when being validated x_power^distance.

It is important to note that the attacker needs to have a valid proof in the first place. Pietrzak pays no attention to roots of unity because they have no effect on the performance of his verifiable delay function. The result of the computation is not important for a VDF, but since it's important for us, we need to implement additional measures to make sure the attack is not practical.

The fix is simple: raise the result of PRP test to all small divisors of N-1, if you get 1 it's a cause for concern. For N=k*b^n+c, it's very easy to do so for c=1, but requires some sieving for c=-1. The depth of sieving should be rather large, because the attacker has some time and unlimited number of attempts to construct a fake proof.

In practice, the check against the attack is just an additional step performed by the server during generation of the certificate. All relevant software was updated to include such a step.

[chalsall]

Originally Posted by patnashev

The depth of sieving should be rather large, because the attacker has some time and unlimited number of attempts to construct a fake proof.

Wow. I sincerely envy those of you who can work at this level!

Guys, this sounds like there's currently a viable attack vector. Comments?

[kriesel]

Originally Posted by patnashev

The fix is simple: raise the result of PRP test to all small divisors of N-1, if you get 1 it's a cause for concern. For N=k*b^n+c, it's very easy to do so for c=1, but requires some sieving for c=-1. The depth of sieving should be rather large, because the attacker has some time and unlimited number of attempts to construct a fake proof.

In practice, the check against the attack is just an additional step performed by the server during generation of the certificate. All relevant software was updated to include such a step.

Does this mean for GIMPS we put back the factoring effort that we would have saved by optimizing for one primality test rather than two, but expend the second half on (N-1)/2 rather than on N?
Depending on what you mean by "small divisors" or "rather large" depth of sieving, that sounds to me like possibly a separate server-managed client-performed work assignment or multiple per GIMPS exponent. That much TF (and P-1?) and exponentiation may be too much for the PrimeNet server to take on. But your last line seems to indicate it's already in place on the server, so manageable load.
Why someone would want to conceal a Mersenne prime baffles me.

[Prime95]

Originally Posted by chalsall

Wow. I sincerely envy those of you who can work at this level!

Yes, Pavel's input has been greatly appreciated by Mihai and myself. He understands the math a whole lot better than I do.

Guys, this sounds like there's currently a viable attack vector. Comments?

Sort of, Pavel informed us of his findings a few days ago. The server proof processor has been upgraded to deal with the issue.

Prior to the fix, it would allow an attacker to find a Mersenne prime and then with some effort create a proof file that showed it was not a Mersenne prime. Why one would want to do this is beyond me.

The attack involves multiplying the final Fermat PRP result (for a prime this is one) by a root-of-unity. Minus one is one such possible root. Prior to the fix, the server would have seen the final PRP result of minus one and concluded "not a PRP". But now, we square the final result and turn the attacker's minus one back into one -- thwarting our madman's evil intent. There are other possible roots - like the modular cube root of one. We thwart this by also raising the final result to the third power. Pavel showed what the possible small roots of unity are so we could guard against all of them.

[chalsall]

Originally Posted by Prime95

Why one would want to do this is beyond me.

Why would someone want to make GIMPS slightly less efficient by reserving hundreds of thousands of P-1 assignments?

But the mere fact the vector was viable would mean you couldn't say *for sure* an MP hadn't been missed.

Originally Posted by Prime95

Pavel showed what the possible small roots of unity are so we could guard against all of them.

Sweet! So risk eliminated at no (or very little) computational cost (if I'm understanding correctly).