KAZ-SIGN

[Scott Fluhrer (sfluhrer)]

I have examined KAZ-SIGN (https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/kaz-sign-spec-web.pdf), and it would appear that the hard problem it relies on is not Quantum Resistant (and hence the signature algorithm it is based on is not).

 

The problem they state is, given A, g, N (composite) and Q, find x such that:

 

g^{Q^x} = A \bmod N

 

However, it would appear that three applications of Shor’s algorithm would be sufficient to recover x:

 

1. Find z with g^z = A \pmod N
2. Factor N to be able to compute \phi(N) (actually, with KAZ, we don’t need to do this step, as it has \phi(N) in the system parameters)
3. Find x with Q^x = z \pmod \phi(N)

 

Being able to solve this allows us to recover the private key from the public key

 

Section 4 of the submission (which covers Quantum Resistance) only addresses Grover’s algorithm.

 

In addition, this being hard is also in conflict with the key generation, signing and verification algorithms they give (Algorithms 1-3) – those have several steps where you are expected to solve a discrete logarithm (either to base N or to base \phi(N)).

 

Hence, unless either I completely misunderstood this submission, I think we can drop this one.

[Scott Fluhrer (sfluhrer)]

Immediately after hitting send, I noticed that they specify that N is a product of a number of smallish primes; this makes the discrete log problem easy – however it makes all the steps I outlined below in solving the hard problem also easy for a classical computer…

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM4PR11MB5455CFFD58AE7AE779BFDB37C13BA%40DM4PR11MB5455.namprd11.prod.outlook.com.

[D. J. Bernstein]

KAZ-SIGN, like SIKE, doesn't claim that discrete logs are hard. It says
that they're easy for the selected groups. It uses them in the stated
algorithms and software. It then argues that the ways that the attacker
can use discrete logs are blocked by the details of the verification
process. See the documentation, especially Sections 8 and 9.

'Scott Fluhrer (sfluhrer)' via pqc-forum writes:
> Being able to solve this allows us to recover the private key from the
> public key

No. There are many solutions to this equation, and whichever solution
you pick (even if you get past the existence question in your step 3)
has negligible chance of being the private key.

Perhaps you meant "a private key", but then you have to define this
concept and, more to the point, argue that signatures produced by this
replacement key will pass verification.

It's not hard to see that they won't _always_ pass. A full analysis is
trickier than one might expect. In any case, for verifiability, claims
of fast attacks should be consistently backed up by scripts that
demonstrate those attacks against the official software.

(In cases where quantum computers are claimed to be essential for a fast
attack, the risk of error is even higher, and there should be even more
attention to applying known error-detection techniques.)

I wrote an attack script in a way that should be reasonably robust
against variations in the verification details. I don't see how the
verification procedure could be tweaked to block this attack while still
accepting the signatures generated by the legitimate signer.

---D. J. Bernstein