ISE write-up for: draft-hao-schnorr-06
Abstract:
"This document describes Schnorr NIZK proof, a non-interactive variant
of the three-pass Schnorr identification scheme. The Schnorr NIZK
proof allows one to prove the knowledge of a discrete logarithm
without leaking any information about its value. It can serve as a
useful building block for many cryptographic protocols to ensure the
participants follow the protocol specification honestly. This
document specifies the Schnorr NIZK proof in both the finite field
and the elliptic curve settings."
This draft has no IANA Considerations.
The draft has not been discussed in any IETF WG.
It was reviewed for me by Stanislav Smyshlyaev and Tibor Jager.
The authors have made the changes suggested by the reviewers.
- - - - -
Stanislav Smyshlyaev's Review
Overall opinion: Minor changes needed
The -05 version addresses most of my concerns described in my brief review
for -04 version (in October 2016), but I’d still prefer some changes to be
made. The Schnorr signature scheme and the Schnorr NIZK proof have a
difficult history (including their relationship with DSA) – and I think it
is quite a good idea to have an RFC on them. We’ve had a discussion with
Feng Hao after -04 version, now I am not against publication of Schnorr
NIZK in a separate RFC (without signature scheme, though), so, in my
opinion, only minor changes are still needed.
In my previous review I said that it would be useful to give certain
recommendations about hash functions and elliptic curve parameters. Though
some words are now given, I’d recommend to change terms a bit: collision
resistance is not the property that is really needed for random oracle
model. Tibor’s proposal of saying “secure cryptographic hash function”
seems to be a good option – in this case we won’t go too far into details,
but would prevent using something non-cryptographic (e.g. HighwayHash). And
instead of saying “Recommended hash functions include…” I’d prefer to see a
more relaxed phrase like “e.g. SHA-256, SHA-512, …”.
I am not really sure that the comment about a simultaneous exponentiation
technique in 2.4 and in 3.4 is needed. The issue is that g (or G) is always
known beforehand (even before Bob is aware of Alice’s ID and her X (or Q) )
– so the table for powers of g (or G) can be precomputed beforehand, which
would make simultaneous exponentiation (with a necessity to generate a
precomputation table for a pair of (g, X) ) ineffective. Anyway, that’s not
critical and may remain unchanged, if the author wants it.
Though originally the scheme was named “an identification scheme”, the
scheme actually implements authentication (assumed identities are known
before the start of the protocol) thus I’d prefer to revise the terms in
the paper a bit.
The comment about the public key validation (for a case of a small
cofactor) in 3.4 should be specified a little – leaving only a reference
for [MOV96] looks not very convenient here: e.g. to say that at least it
must be verified that Q satisfies the curve equation and that 4*Q is
nonzero.
At the beginning of Section 4 I’d recommend to revise a phrase “to ensure
participants follow the specification properly” – maybe just to say about
participants possessing secret values?
In my opinion, the statement about equivalent proofs for DSA/ECDSA either
needs further deep comments (the models, the known results etc.) or just to
be removed. I think that in the current form it does not add anything
helpful, but leaves the reader unsatisfied, in fact there is a lot of
positive results for DSA/ECDSA (and a lot of additional results for ISO/IEC
14888-3 EC-RDSA).
In Section 5 the phrase “The assumption of an honest verifier naturally
holds because the verifier can be anyone” should be removed – it’s very
unclear and misleading, in my opinion.
It seems to me that the document is useful and should become an RFC in a
slightly revised form.
- - - - -
Tibor Jager's Review
Summary: This is a review of draft-hao-schnorr-05. It proposes several
changes to the specification and suggests an efficiency improvement to
the non-interactive variant of the protocols.
----------------------------------------
Major comments:
----------------------------------------
§2.2, "Bob chooses challenge c ... uniformly at random from [0,2^t-1]
... (e.g. t=80)"
The standard security proof of Schnorr's ID scheme assumes that c is
chosen uniformly at random from [0,q-1], where q is the subgroup order.
Section §5 mentions the provable security of Schnorr's ID-scheme and the
resulting NIZK-PoK, however, this applies only if the protocol specified
in this RFC matches the protocol considered in the security proof.
In the non-interactive setting, where c is derived with a hash function,
it will of course be inconvenient to demand c \in [0,q-1]. In this
setting, one should require that 2^t is at least equal to the order q of
the considered subgroup.
In general, t=80 seems to be too small, because colliding c-values may
enable attacks. Setting t to be twice the desired "security in bits"
(e.g., t=256 for "128-bit security") seems more reasonable.
----------------------------------------
§2.3, "the hash function H shall be collision-resistant"
Collision-resistance alone is not sufficient to instantiate the
Fiat-Shamir construction securely.
A contrived but illustrative example: requiring only
collision-resistance may mislead people implementing this RFC into
instantiating H with the identity map (or any other injective function
which is not a "good" cryptographic hash function). Such an
instantiation of H would be collision-resistant, but the resulting NIZK
protocol derived by applying the Fiat-Shamir transform is completely
insecure.
Actually, the hash function must "approximate a random oracle reasonably
well". Therefore I suggest to replace
"the hash function H shall be collision-resistant"
with
"the hash function H must be a secure cryptographic hash function, like
e.g. SHA-256, SHA-512, ...".
(This comment applies also to §5 "Security Considerations")
----------------------------------------
§2.3, "Usually, the boundary is implicitly defined, once the length of
items is publicly known"
Different protocols may use parameters of different size, therefore
assuming implicit boundaries seems dangerous. In particular, it may
enable cross-protocol attacks that exploit the fact that different
protocols may use different parameter sizes. Therefore it seems useful
to always require explicit boundaries here. This would also reduce
flexibility, and therefore improve interoperability of implementations.
----------------------------------------
§2.3, description of the non-interactive protocol:
In the current instantiation of the non-interactive protocol, the prover
sends (V,b) (along with UserID and OtherInfo), and the verifier first
computes c, and then checks for V = g^b * X^c mod p.
Assuming typical choices of p and q, this requires the transmission of
an element V of Zp, whose size is somewhere between 1024 and 4096 bits,
and an element b of Zq with expected size of about 160-512 bits.
It seems possible to reduce the amount of transmitted data to two
elements of Zq, by replacing (V,b) with (c,b):
- The prover of this optimised variant works exactly as in the protocol
described in the current document, except that it sends (c,b) instead of
(V,b)
- The verifier computes V = g^b * X^c, and then checks whether H(g || V
|| g^x || UserID || OtherInfo) = c.
This is a standard trick to reduce the size of Schnorr signatures, which
seems to be applicable here, too.
The security of this modified variant follows from the fact that one can
compute V from (c,b), and c from (V,b) (and the additional public
parameters). Therefore sending (c,b) is equivalent to sending (V,c,b),
which in turn is equivalent to sending (V,b).
----------------------------------------
§2.4, verification of proofs:
The full verification procedure of proofs (including verification of
group membership) should not be described in the "Computational Costs"
section, but earlier in the protocol specification (§2.2 and §2.3).
----------------------------------------
§3.3, using only the x-coordinates of points as hash inputs:
Is there any important reason why only the x-coordinates are used as
input to the hash function here? Hashing the entire group element seems
more compatible with the security proof of Schnorr's ID scheme, and
seems not to incur significant additional costs.
----------------------------------------
§5, "The assumption of an honest verifier naturally holds because the
verifier can be anyone."
I was not able to follow this argument. Actually, the reason why the
Fiat-Shamir transform requires only an honest-verifier ID scheme is
because the hash function (more precisely, the random oracle in the
security proof) implements an honest verifier, because it assigns a
uniformly random challenge c to each g^v sent by the prover to the hash
function oracle - this is exactly what a honest verifier would do.
----------------------------------------
§5, vulnerability to bad randomness.
Using Schnorr's ID scheme or its non-interactive variant with bad
randomness v in g^v mod p may reveal the secret discrete logarithm whose
knowledge the prover wants to prove.
For example, if the same random value V = g^v mod p is used twice by the
prover (e.g. because its random number generator fails), but the
verifier chooses different challenges c, c' (or the hash function is
used on two different OtherData, producing two different values c, c'),
then this reveals the prover's secret key:
The adversary observes two proof transcripts (V,c,b) and (V,c',b'),
which both verify. Then it computes
(b-b')/(c'-c) = (v-xc - v+xc')/(c'-c) = x mod p
which reveals the secret key x of the prover.
More generally, such an attack may even work for a slightly better (but
still bad) random number generator, where the value v is not repeated,
but the adversary knows a relation between two values v,v', such as v' =
v+r for some known value r. More precisely:
Suppose that the adversary observes two proof transcripts (V,c,b) and
(V',c',b'), which both verify. Suppose also that the adversary knows
that V' = g^v' = g^(v+r) = V * g^r mod p. Then it computes
(b-b'+r)/(c'-c) mod p = (v-xc - v-r+xc' + r) / (c-c') mod p = x mod p
Such potential weaknesses of Schnorr's ID scheme should be explained
very clearly in the Security Considerations section.
----------------------------------------
Minor comments:
----------------------------------------
§1.2 Notation
In the "mod p" setting, q denotes the order of the (sub)group generated
by generator g.
In the elliptic curve setting, q denote the characteristic of the base
field Fq, while n denotes the order of the group.
For clarity, it would be useful to let q denote the order of (sub)groups
throughout the document, to avoid confusion, and choose a different
character for the characteristic of the base field of the elliptic curve
group.
----------------------------------------
§2.2, "...must be a subgroup element ... which anyone can verify".
Please specify here how verification works exactly, or at least refer to
another part of the document which specifies this.
----------------------------------------
§3.2, "Alice publishes her public key Q = G x [x]".
The double meaning of symbol "x", first denoting multiplication and then
denoting a value x, is a bit unfortunate here. The earlier sections used
* as a symbol for multiplication. One may consider replacing the above
with "Q = G * [x]"
Furthermore, the value Q is not necessarily an actual "public key" in
all possible applications of the protocol standardised in this RFC. In
some protocol, it may e.g. be a message sent to establish a key via a
Diffie-Hellman like protocol, etc., while other values are used as
actual public keys. Instead, one could simply write
"Alice publishes an elliptic curve point Q = G * [x] of which she
wants to prove knowledge of the discrete logarithm w.r.t. generator G".
(This comment applies also to §3.4, etc.)
----------------------------------------
§4, "the OtherInfo should include extra information":
As also explained in the RFC draft, the non-interactive protocol is
vulnerable to replay attacks. In particular, if the protocol is used as
a Proof-of-Possession of the long-term secret to a CA, then it MUST be
ensured that the hash contains data that links the proof to one
particular key registration procedure.
----------------------------------------
§5, "A non-interactive ZK proof is often called a signature scheme"
While there exists a natural relation between ZK proofs and digital
signatures, the above statement is not true and therefore misleading.
E.g., one cannot simply replace a NIZK proof with a signature scheme in
general.
I think one can safely delete this sentence, it seems not to add
anything relevant to the specification of the protocol.
- - - - -