[Crypto-panel] Review of draft-hao-schnorr-05

[Tibor Jager <[e-mail]>]

Dear Nick et al.,

Please find below my review of draft-hao-schnorr-05.

Best regards,
Tibor



Document: draft-hao-schnorr-05
Reviewer: Tibor Jager
Review Date: 2017-03-03

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.