Pull to refresh

On Schnorr identification protocol compatibility with instant digital signature mode

Reading time6 min
Views534

This post describes a modification of the Schnorr identification protocol which is compatible with the instant digital signature mode.

Introduction

The article describes the interactive Schnorr identification protocol (hereinafter referred to as the Schnorr protocol) and formulates the problem of compatibility of this protocol with the instant digital signature (IDS) mode. This post shows how to modify the Schnorr protocol to provide such compatibility.

IDS-compatible Schnorr protocol

Recall that some information about the arithmetic of elliptic curve points, as well as an explanation of ECDLP and DLP, was explained by our previous publication.

For the sake of simplicity, we will leave everything that concerns the Schnorr protocol unchanged, including the key pair \{\mathbf{x},\mathsf{R}=[-\mathbf{x}]\mathsf{G}_1\} and the certificate \{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}.

If we interpret the necessary condition, then IDS-compatibility is possible when P and V are able to compute some common secret component. Such a component can be expressed as a shared session secret key. We will show how to do this using the example of the Schnorr protocol. Let's denote the cryptographic hash function as \hslash(\cdot).

Let's make some changes to the protocol. Let's use the following trick: we'll "hide" the ephemeris \phi at a point on the curve. This causes \textit {response} also turn into a point. As a result, we get the following protocol.

Protocol messages.

1.   P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{G}_1

2.   P \longleftarrow V :  \mathsf{T}=[\phi]\mathsf{G}_1

3.   P \longrightarrow  V  : \mathsf{N}=[\mathbf{x}]\mathsf{T}+\mathsf{S}

The actions of the parties.

P demonstrates to V that he posesses (knows) \mathbf{x}. In order to achieve this, the subsequent actions are executed:

1.   P selects \upsilon\in_R\!(0,m-1] (\textit {commitment}), computes \mathsf{S}=[\upsilon]\mathsf{G}_1 (\textit {witness}), verifies the condition \mathsf{S}\stackrel{?}\neq\infty. If \mathsf{S}=\infty then it chooses a new \upsilon and repeats all the necessary computations and checks;

2.   V reads an actual certificate \{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\} and checks the DS \mathfrak{B}\Leftarrow{\rm{Verify}}( \hslash(\mathsf{R}||D_{\mathsf{R}}), \Im_{\mathsf{R}}, \rm{P}_T), where \rm{P}_T is the trusted party's public key T. If \mathfrak{B}=False then the session ends. If \mathfrak{B}=True then it selects \phi\in_R\!(0, m-1] and computes \mathsf{T}=[\phi]\mathsf{G}_1 (\textit{challenge}). If \mathsf{T}=\infty then it selects a new \phi and repeats all the necessary computations and checks;

3.   P checks the condition \mathsf{T}\stackrel{?}\neq\infty, if it is true, then it computes \mathsf{N}=[\mathbf{x}]\mathsf{T}+\mathsf{S}=[\mathbf{x}\phi+\upsilon \pmod m]\mathsf{G}_1 (\textit{response}), otherwise the session ends;

4.   V computes \mathsf{Q}=\mathsf{N}+[\phi]\mathsf{R}. Then it checks x_{\mathsf{Q}}\stackrel{?}{=}x_{\mathsf{S}}. If equal then the proof is accepted, and rejected otherwise.

So, suppose that the identification step was successful and V accepted the proof provided by P.

At this point, P has the following set of data: \upsilon (\textit{commitment} by construction), \mathsf{T} (received from V as a \textit{challenge}). V knows \mathsf{S} (received from P as a \textit{witness}), \phi (by construction), \mathsf{N} (received from P as a \textit{response}).

The parties independently compute a shared session secret key in accordance with the following rules:

  1.  P computes \mathsf{A}=[\upsilon]\mathsf{T}=[\upsilon\phi\pmod m]\mathsf{G}_1, g_1=\hslash(x_{\mathsf{A}}\|y_{\mathsf{A}}).

  1.   V computes \mathsf{B}=[\phi]\mathsf{S}=[\phi\upsilon\pmod m]\mathsf{G}_1, g_3=\hslash(x_{\mathsf{B}}\|y_{\mathsf{B}}).

Obviously, \mathsf{A}=\mathsf{B} due to commutativity. Therefore, g_1=g_3. As for the IDS, then:

1.   P generates a signature for the given message M using g_1, given the value of the hash function \hslash(g_1\|M\|\ldots).

2.   V checks the signature for some message M' using g_3 given the hash function value \hslash(g_3\|M'\|\ldots).

The advantage of the above mentioned solution is that the changes relate to arithmetic operations and do not affect the logic of the protocol. This is an important circumstance, since any fundamental modifications would lead to the need to study the cryptographic strength of the new design with all the ensuing consequences.

Earlier, we noted that we have a protocol with similar functionality that solves this problem, but at the same time allows us to recognize that the prover belongs to a certain local community of registered participants.

Preliminary analysis

Let's note that \upsilon, \phi are only known to P and V, respectively. Then an attacker can get \upsilon or \phi by finding an ECDLP solution given \mathsf{S} or \mathsf{T} respectively. It is also possible to find a DLP solution if e_m(\mathsf{S}, \mathsf{G}_1) or e_m(\mathsf{T}, \mathsf{G}_1). The purpose of the e_m(\cdot, \cdot) function, as well as the relationship between ECDLP and DLP, is explained in Appendix A. Since g_1=g_3, only someone who knows \upsilon or \phi, as well as the secret key of an arbitrary DS scheme chosen for this goal is able to generate the IDS.

An active attacker, using interception and blocking techniques, is able to impose \mathsf{S}'=[\upsilon']\mathsf{G}_1 instead of \mathsf{S}, \mathsf{T}'=[\phi']\mathsf {G}_1 instead of \mathsf{T} and \mathsf{N}'=[\mathbf{x}]\mathsf{T}'+\mathsf{S}' instead of \mathsf{N} when \upsilon'\neq \upsilon, \phi'\neq\phi. For example, these may be messages from another session. However, V will overwhelmingly reject the provided proof, since \mathsf{Q}'=\mathsf{N}'+[\phi]\mathsf{R}=[\mathbf{x}(\phi'-\phi)+ \upsilon'\pmod m]\mathsf{G}_1 and x_{\mathsf{Q}'}=x_{\mathsf{S}'} with negligible probability. In addition, \mathsf{A}'=[\upsilon]\mathsf{T}'=[\upsilon\phi'\pmod m]\mathsf{G}_1, \mathsf{B}'=[\phi]\mathsf{S}'=[\phi\upsilon'\pmod m]\mathsf{G}_1 and \mathsf{A}'=\mathsf{B}' with negligible probability.

The amount of information transmitted

We will use the compact curve point representation [Cohen_etc._2006] (section 13.2.5).

The point \mathsf{Q} is given by a pair of coordinates x_{\mathsf{Q}}, y_{\mathsf{Q}} \in\mathbb{F}_p. If \mathsf{Q} belongs to the curve, then the equation y_{\mathsf{Q}}^2=x_{\mathsf{Q}}^3+ax_{\mathsf{Q}}+b is true for some a, b\in\mathbb{F }_p. This equation can be interpreted as y_{\mathsf{Q}}^2 \equiv r \bmod p, where r is a quadratic residue and then there are only two solutions \pm y_\mathsf{Q}. For y_\mathsf{Q}<p the solution is -y_\mathsf{Q}\bmod p=p-y_\mathsf{Q}. If y_{\mathsf{Q}} is even, then (p-y_{\mathsf{Q}}) is odd, and vice versa. In the general case, of two solutions, one is always even and the other is odd.

Let the point \mathsf{Q} be represented by the coordinate x_{\mathsf{Q}}. We will transmit over the communication channel (x_{\mathsf{Q}}, \mathfrak{s}), where \mathfrak{s} is a binary variable that allows us to determine the desired solution from a pair of possible ones. Let's make it a rule that \mathfrak{s}=0 means even, and \mathfrak{s}=1 means odd. For example, for (x_\mathsf{Q}, 1) one should get a pair \{y_{\mathsf{Q}}, p-y_{\mathsf{Q}}\} and then choose an odd solution from this pair.

\lceil\log_{2}p\rceil+1 bits of memory is required to store an arbitrary point on the curve. In \mathbb{F}_p, the square root is computed using the Tonelli-Shanks algorithm of asymptotic computational complexity O(\log_{2}^2{p}) [Cohen_etc._2006] (section 11.1.5).

Then, to restore the \mathsf{Q} point, it's necessary to perform the following actions:

1.   For a given coordinate x_{\mathsf{Q}}, a certain coordinate y_* is computed using the Tonelli-Shanks algorithm.

2.   If (\mathfrak{s}=1)\land(y_*\bmod 2\neq 0) then y_\mathsf{Q}=y_*.

3.   If (\mathfrak{s}=1)\land(y_*\bmod 2=0) then y_\mathsf{Q}=p-y_*.

4.   If (\mathfrak{s}=0)\land(y_*\bmod 2=0) then y_\mathsf{Q}=y_*.

5.   If (\mathfrak{s}=0)\land(y_*\bmod 2\neq 0) then y_\mathsf{Q}=p-y_*.

If the compact representation is used, then 3(\lceil\log_{2}{p}\rceil+1) bits would need to be transmitted to deliver \mathsf{S}, \mathsf{T}, and \mathsf{N} in total. For comparison, in the original Schnorr protocol, under the same conditions, for the delivery of \mathsf{S}, \phi and \psi in total, it is necessary to send 2(\lceil\log_{2}m\rceil)+\lceil\log_{2}p \rceil+1 bits.

Computation optimization

The complexity depends on the methods for computing the scalar multiplication, as well as the choice of the computing platform. Thus, for example, tests that were carried out using a test bench implemented in the Scala v2.13.6 programming language on a MacBook Pro (15-inch, 2016) hardware platform with a 4-core Intel Core i7 processor running macOS Monterey version 12.6.2 using primitives from the PBC library show that due to the preprocessing possible for the constant \mathsf{G}_1, the scalar product \mathsf{Q}_1=[\alpha]\mathsf{G}_1 is on average 85.37% more efficient than the scalar products \mathsf{Q}_2=[\alpha]\mathsf{P}, where \mathsf{P}\neq\mathsf{G}_1\neq const. The measurement results are summarized in Table 1.

IDS mode and public key certificates

P owns the key pair \{\mathbf{x}, \mathsf{R}\}. A corresponding certificate is issued for the public key \mathsf{R}. The following question needs to be answered: what benefit can be gained from the IDS mode with a public key certificate?

Let the certificate \{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\} be issued for the public key \mathsf{R}, where \Im_{\mathsf{R}} \Leftarrow{\rm{Sign}}(\hslash(\mathsf{R}||D_{\mathsf{R}}), \rm{S}_T) — DS of trusted party T, D_{\mathsf{R} } — personal data of P and \rm{S}_T — secret key of T, intended for generating the certificate's DS.

Let's set up a thought experiment and, in the absence of the DS mode, assume that P sends V some digitally certified personal data D'. Furthermore, P claims that D' is his own personal data. It should be noted right away that this data could have been obtained in various ways, for example, as a result of collusion, the use of social engineering methods, or simply copied from publicly available long-term memory. To verify the digital signature, V must use the public key \mathsf{P}' from the certificate \{D',\mathsf{P}', \Im_{\mathsf{P}'}\}. Let's also assume that all necessary checks have confirmed the authenticity and integrity of \mathsf{P}', D'.

As a result, V has two certificates \{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\} and \{D',\mathsf{P}', \Im_{ \mathsf{P}'}\}, each issued by a trusted CA. Consider the case when D_{\mathsf{R}}\neq D' (D_{\mathsf{R}}=D' is treated uniquely). As a result, V is unable to make a correct choice about D_{\mathsf{R}} or D' because there is no decision criterion. Obviously, such uncertainty is unacceptable.

If the IDS mode is enabled, then when making a decision about D_{\mathsf{R}} or D', V relies on the proof that was provided to P at the identification stage. V reasons using the following logic.

A DS for personal data can only be generated by someone who simultaneously has access to the variables of a separate identification protocol session, both public and secret, including the secret key for generating a DS.

Let's assume that the digital signature was obtained as a result of collusion. To do this, an attacker must force the owner of personal data to certify this data with his DS, but with the inclusion of some auxiliary data, about which the certifier does not know anything. Based on the associated risk model, such an event seems implausible. It is overwhelmingly likely that the witness will refuse to include such data fearing undesirable consequences, such as implicit debt imposition, blacklisting, account blocking, and so on.

Open verification in the Schnorr protocol

The peculiarity of the Schnorr protocol is that anyone with access to the variables \mathsf{S}, \phi, and \psi can verify the correctness of the evaluation made by V towards the proof given by P.

Indeed, the variables mentioned above are transmitted over an insecure communication channel and, therefore, are publicly available. Since anyone can use the public key \mathsf{R}, it is not necessary to have V authority to compute \mathsf{Q}=[\psi]\mathsf{G}_1+[\phi]\mathsf{R}= [\psi-\phi\mathbf{x}\pmod m]\mathsf{G}_1 and then check x_{\mathsf{Q}}\stackrel{?}{=}x_{\mathsf{S}}.

The practical meaning here is the ability to control the actions of both V and P. This is important in the case when disagreements may arise. For example, when P claims to have provided the correct proof, but V denies it.

Summary

Estimates of the amount of transmitted information for the original Schnorr protocol and the modification described above differ insignificantly.

The original Schnorr protocol uses three scalar multiplications, while the modification of the protocol uses four such multiplications. Since the scalar multiplications \mathsf{S}=[\upsilon]\mathsf{G}_1 and \mathsf{T}=[\phi]\mathsf{G}_1 are computed using the generating element \mathsf{G}_1, the optimization is possible. This optimization allows to reduce computational complexity in exchange for the allocation of additional memory for storing intermediate results (see Table 1). Note that in the original protocol, when computing the point \mathsf{Q}=[\psi]\mathsf{G}_1+[\phi]\mathsf{R}, only partial optimization is allowed. However, in the modified protocol, when computing the points \mathsf{N} and \mathsf{Q}=\mathsf{N}+[\phi]\mathsf{R}, as well as the scalar multiplications \mathsf{A}=[\upsilon]\mathsf{T} and \mathsf{B}=[\phi]\mathsf{S} such optimization is impossible.

In the proposed modification of the protocol, open verification is not feasible.

Conclusion

It should be attested that we were able to solve the problem for a particular protocol in a relatively simple way. However, for an arbitrary identification protocol, the problem of compatibility with the IDS mode remains open. In the future, we will attempt to find a solution to the problem for some well-known identification protocol that is different from the Schnorr protocol.

The text of the article in pdf format can be downloaded here.

Bibliography

[Cohen_etc._2006] Cohen, H., Frey, G., Roberto Avanzi, R., Doche C., Lange, T., Nguyen, K. and Vercauteren, F. Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall /CRC, 2006.

Tags:
Hubs:
Rating0
Comments0

Articles