Analysis of Warrant Attacks on Some Threshold Proxy Signature Schemes

2.1 Initialization Phase

Let p be a large prime, q be a prime divisor of p – 1, g be a generator of order q in ℤp*, and h(.) be a secure one-way hash function. The parameters (p,q,g) are public. Suppose that P₀ stands for the original signer, and let G = {P_1, P₂, …, P_n} be the proxy group of n proxy signers. The original signer P₀ determines its private key by choosing an arbitrary x0∈ℤq* and the public key as y₀ = g^x₀modp. By the same way, each proxy signer P_i ∈ G owns its private key xi∈ℤq* and public key y_i = g^x_imodp, which are certified by the certificate authority (CA). Let m_W stand for a warrant that records the parameters t, n, the valid delegation time, and the identities of the original and proxy signers of the proxy group, etc. Also, ASID denotes the identities of the actual proxy signers.

2.2 Proxy Share Generation Phase

The original signer P₀ chooses a random integer k∈ℤq* and then computes K = g^kmodp. Then, P₀ computes σ = x₀h(m_W,K) + kmodq as the proxy group’s key and reports (σ,m_W,K) to the proxy signers of G. After receiving (σ,m_W,K), each proxy signer P_i ∈ G checks whether the equation gσ=y0h(mW,K)Kmodp holds or not. If it holds, each P_i regards σ as its proxy key.

2.3 Proxy Signature Generation Phase

For convenience, let D = {P₁, P₂, …, P_t} be the t actual proxy signers, ASID be the identities of them, C be the receiver, and m be the message to be signed. Then, D as a proxy group performs the following steps: 1) each P_i ∈ D chooses a random integer ki∈ℤq*, and then computes and reports r_i; = g^k_imodp; 2) after receiving r_j (j = 1,2, …, t, j ≠ i), each P_i ∈ D computes R=∏j=1trj modp and then S_t = k_iR + (t⁻¹σ + x_i)h(R,m,ASID)modq; 3) they send S_i to the designated receiver C via a secret channel; and 4) after receiving S_i, the receiver C checks whether the following equation holds:

If it holds, (r_iS_i) is a valid partial proxy signature; then he computes S=∑i=1tSimodq. Therefore, (R, S, K, m_W, ASID) is the threshold proxy signature of the message m.

2.4 Proxy Signature Verification Phase

From m_W, the verifier can get the threshold value t, and from ASID, he can know the number of actual proxy signers. The verifier checks the validity of the proxy signature (R, S, K, m_W, ASID) for the message m by checking the validity of the following equation

3.1 Case 1

In this case, we describe that after intercepting a valid proxy signature (R,S,K,m_W,ASID), an adversary (each malicious original or proxy signer) can change m_W, y_i and forge a proxy signature S (without knowing or changing secret partial signature S_j).

Without loss of generality, assume that P₁ is a malicious proxy signer who decides to forge a threshold proxy signature of a message m. Although, P₁ cannot generate a valid warrant m_W of the original signer, he can generate a valid warrant mW′. As a result, he can change the content of the warrant such as the threshold value t, the time constraint, etc.

Assume that P₁ decides to forge a threshold proxy signature of m and claim that it is generated by t′ proxy signers D′ = {P₁,P₂, …, P_t}, while the proxy group D′ knows nothing about the decision. Let ASID′ be the identities of the group D′. First, P₁ generates the warrant mW′ as he wants, chooses two random integers α, β∈ℤq*, and computes:

Then, he computes

and requests CA to replace his public key by y₁. Next he computes:

Since:

(R′,S′, K′, mW′, ASID′) is a valid threshold proxy signature of the message m. This kind of attack can be prevented using a policy such as restricting the proxy to update their keys or if CA asks P₁ for the Zero-Knowledge Proof of his private key x′₁ associated to new public key y₁.

3.2 Case 2

In 2007, Shao et al. [11], proposed another warrant attack on Yang’s scheme. In this case, we review this attack. Shao described how after intercepting a valid proxy signature (R,S,K,m_W,ASID) an adversary (each malicious original or proxy signer) can change m_W, σ and forge a proxy signature S (without knowing or changing secret partial signature S_j) in Yang’s scheme.

Suppose that a malicious original signer P₀ decides to forge a proxy signature generated by the proxy group D = {P₁,P₂, …, P_t}. Let ASID be the identities of D. Let (R,S,K,m_W,ASID) be a legal proxy signature of a message m generated by D on behalf of P₀. The malicious original signer P₀ can change the content of the warrant, such as the time constraint. P₀ forges a new warrant mW′ as he wants, chooses an integer k′∈ℤq* and computes K′ = g^k′modp. Then, P₀ computes σ′=x0h(mW′,K′)+k′modq and:

Then, (R,S′,K′, mW′,ASID′) can pass the verification equation, since:

4.1 Initialization Phase

The system parameters are the same as those in Section 2.1. However, the only difference is that in Hu’s scheme, CA requires that the original signer P₀ and each proxy signer P_i(1≤ i ≤n) offer the Zero-Knowledge Proof of its private key associated with its public key as follows: 1) CA randomly chooses e∈ℤq*, computes E = g^emodp, and sends E to P₀ to each P_i; 2) then, P_i, for i = 0, 1, ..., n, computes L_i=E^x_imodp, and sends L_i to CA; and 3) for each i = 0,1, ..., n, the certificate authority (CA) checks the equation yie=Li; if it holds, CA accepts their certification, otherwise he refuses it.

4.2 Proxy Share Generation Phase

The original signer P₀ chooses a random integer k∈ℤq* and then computes K = g^kmodp. Then, P₀ computes σ = x₀h(m_w,K) + kKmodq as the proxy group’s key. Accordingly, its public key is Q = g^σmodp. Then, P₀ chooses a t − 1 degree polynomial f(x) = σ + a₁x + ··· + a_i−1x^t−1modp and computes R_i = f(y_i)modp as each proxy signer secret key. He computes Q_i = g^R_imodp, A_j = g^σ_j modp and sends (y_i,R_i,m_w,K) to each proxy signer P_i via a secret channel and broadcasts Q_i,A_j. After receiving (y_i,R_i,m_w,K), each proxy signer P_i ∈ G checks whether the equation gRi=KKyoh(mW,K)∏l=1t-1Alyilmodp holds or not.

4.3 Proxy Signature Generation Phase

For convenience, let D = {P₁, P₂,...,P_t} be the t actual proxy signers, ASID be the identities of them, C be the receiver, and m be the message to be signed. Then, D as a proxy group performs the following steps: 1) each P_i ∈ D chooses a random integer ki∈ℤq* and then computes and reports r_i = g^k_imodp; 2) after receiving r_j (j = 1,2,... ,t, j ≠ i), each P_i ∈ D computes R=∏j=1trjmodp and the S_i = k_iR + (R_iW_i+ x_i)h(R, m, ASID) modq, where Wi=∏j=1,j≠ityjyj-yi

; 3) each P_i sends S_i to the designated receiver C via a secret channel; and 4) after receiving S_i, the receiver C checks whether the following equation holds:

If it holds, C computes S=∑i=1tSimodq. Therefore, (R, S, K, m_w, ASID) is the threshold proxy signature of the message m.

4.4 Proxy Signature Verification Phase

The verifier checks the validity of the proxy signature (R, S, K, m_w, ASID) for the message m by checking the validity of the following equation:

5.1 Warrant Attack

In the following section, we show that Hu’s scheme cannot resist warrant attacks, similarly to how we did so in Subsection 3.2. After intercepting a valid proxy signature generated by a subset of a proxy group, a malicious original signer can change the warrant and forge new proxy signatures.

Suppose that a malicious original signer P₀ wants to forge proxy signatures generated by the proxy group D = {P₁, P₂, ..., P_t}. Let ASID be the identities of D. Let (R,S,K,m_w,ASID) be a legal proxy signature of a message m generated by D on behalf of P₀. The malicious original signer P₀ can change the content of the warrant, such as the time constraint, etc. P₀ forges a new warrant mW′ as he wants, chooses an integer k′∈ℤq*, and computes K′ = g^k′ modp. Then, P₀ computes σ′=x0h(mW′,K′)+k′K′modq and replaces Q = g^σ modp with Q′ = g^σ′modp,Q_i = g^R_imodp for 1≤ i ≤ n, and A_j for an arbitrary 1 ≤ j ≤ t,j ≠ i with arbitrary numbers Qi′ for 1 ≤ i ≤ n and Aj′, respectively. Then, P₀ computes:

Similarly, (R,S′,K′, mW′, ASID) can pass the verification equation, since:

5.2 Our Improvement

In order to protect Hu’s scheme against the above attack, we recommend that the partial signature S_i be replaced by:

the partial signature verification equation is replaced by:

and the threshold proxy signature verification equation is replaced by:

Since m_w is a part of S_i, it is impossible for anyone to change m_w and forge a proxy signature after intercepting a valid proxy signature (R, S, K, m_w, ASID). Thus, a malicious original signer cannot forge a valid threshold proxy signature by a warrant attack.

6.1 Initialization Phase

This phase is similar to Hu’s scheme, CA requires that the original signer P₀ and each proxy signer P_i(1≤ i ≤ n) offer the Zero-Knowledge Proof of its private key associated with its public key as follows: CA randomly chooses a∈ℤq*, computes A = g^amodp, and sends A to P₀ to each P_i. Then, P_i for i = 0,1,..., n computes A_i = A^X_imodp and sends A_i to CA. For each i = 0,1,..., n, the CA checks the equation yia=Ai. If it holds, CA accepts their certification, otherwise he refuses it.

6.2 Proxy Share Generation Phase

This phase is the same as that in Subsection 2.2.

6.3 Proxy Signature Generation Phase

For convenience, let D = {P₁, P₂,...,P_t} be t actual proxy signers, ASID the identities of these t proxy signers, C the receiver of partial signatures, and m a message to be signed. Then D, as a proxy group, performs the following steps: 1) each P_i ∈ D chooses a random ki∈ℤq* and then computes and broadcasts r_i = g^k_imodp; 2) after receiving r_j (j = 1,2,..., t,j ≠ i), each P_i ∈ D computes:

3) then, he sends S_i to the designated receiver C via a secret channel; and 4) after receiving S_i, the receiver C checks whether the following equation holds:

If it holds, (r_i,S_i) is a valid partial proxy signature, and then he computes S=∑i=1tSi. Therefore, (R, S, K, m_W, ASID ) is the threshold proxy signature of the message m.

6.4 Proxy Signature Verification Phase

The verifier checks the validity of the proxy signature (R,S, K, m_W, ASID) for the message m by the following equation:

Proof

Indeed, we have:

Thus, K′ = (α − r)c⁻¹ mod q.

Theorem 2. (R′,S′,K′,m_W, ASID) given by:

is a valid proxy signature.

Proof

It is a valid proxy signature of the message m because:

Theorem 3. If y1=(y0h(mWK′)(∏i=2tyi)K′)-K′-1 mod p, then (R′,S′,K′ ,m_w, ASID) given by:

is a valid proxy signature.

proof

It is a valid proxy signature of the message m because:

Next, we examine the security of the proposed scheme.

7.1 Secrecy

In the proposed scheme, both signing and verification are based on discrete logarithm problems. Hence, no one can compute the original signer’s private key x₀ from his/her public key y₀ = g^x₀ mod p. Similarly, no one can compute the original signer’s private key x₀ from A₀ = A^x₀ mod p. On the other hand, no one can compute x₀ from the group proxy signature key σ = x₀h(m_w,K) + k mod q, because the parameter σ is computed by the Schnorr signature scheme, which is a provable secure random oracle model. Therefore, the original signature’s private key can be kept secretly and be reused during the span of the system.

Based on discrete logarithms, it is virtually impossible to obtain any proxy signer’s secret key x_i from the corresponding public key y_i = g^X_i mod p or from A_i = A^X_i mod p. Again, according to the Schnorr signature scheme, no one can compute x_i from the partial proxy signature S_i = k_i + (t⁻¹ σ + x_iK)h(R,m,m_w, ASID). Hence, our scheme preserves the security.

7.2 Proxy Protection

Although the proxy signing key σ is created by the original signer, the original signer cannot compute the partial proxy signature,

The original signer does not know P_t’s private key x_i, so according to the Schnorr signature scheme, it is very difficult for anyone to generate the partial proxy signature S_i of m. For the security of the Schnorr signature scheme, the random number k_i should not be reused with a different plain text. Therefore, the original signer cannot masquerade as a proxy signer to create a partial proxy signature. This protects the authority of the proxy signer.

7.3 Unforgeability

An intruder may try to derive a forged proxy signature by various ways. In the subsections below we will show that our scheme is secure against various attacks.

7.4 Non-repudiation

The property of non-repudiation is that both the original signer and the actual proxy signers cannot deny the generation of a valid proxy signature. Any valid proxy signature (R,S,K,m_w,ASID) of a message m should be generated by t or more proxy signers. This is because only P_i has the private key x_i. Thus, P_i cannot deny signing the partial proxy signature. Moreover, the warrant m_w and K are created by the original signer. The original signer cannot deny the proxy signers the power of signing messages. Therefore, the valid proxy signature can be signed on behalf of the original signer. Hence, both the original signer and the actual proxy signers cannot deny generating the valid proxy signature.

7.5 Time Constraint

Time constraint means the time during which the signing power of the proxy group is valid. In our scheme, only the original signer creates the warrant m_w, which contains the time constraint, and it is impossible for anyone to change m_w. In the verification stage, the verifier checks whether or not the warrant has expired. Therefore, our scheme satisfies the property of time constraint.

7.6 Known Signers

Finally, from ASID, the verifier can notice who the actual signers are. In our scheme, any receiver is able to identify the actual signers in the proxy group. Furthermore, the adversary cannot replace ASID by ASID′ satisfying h(R,m,m_w,ASID) = h(R,m,m_W, ASID′). Since h(·) is a collision resistant hash function, it is computationally infeasible to get such an ASID′. Therefore, our scheme satisfies the property of known signers.

From what has been analyzed above, we are certain that the necessary requirements of the (t, n) threshold proxy signature scheme are fulfilled in our scheme. Moreover, we compared the security of our scheme with the threshold proxy signature schemes proposed in [5,11,14] and summarized the results in Table 1.

Table 1

Security comparison of threshold schemes with proposed scheme