Subject: [Cfrg] On W. Ladd's suffixed-Schnorr signature proposal RE: Signature proposal

From: Dan Brown <[email-masked]>
Date: Mon, 29 Jun 2015 14:35:18 +0000

Hi all,

Some very theoretical comments/questions on Watson Ladd's suffixed-Schnorr 
signature variant proposal below:

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
>
> A signer has a public key A that is a point on E, and a private key (v,k), 
> where
> A=kG for G the generator of the prime order subgroup of E, and s is a
> floor(log_2(p)+7)/8 string of bytes.  Let H be a hash function. We let 
> r=H(v||M)
> mod q  where H is taken as a little-endian string of bytes, compute R=rG, 
> and
> let c=H(M||R) mod q. Then let s=r-ck. The signature is (R,s).

[DB] For some narrow-pipe hashes H, there's a remote risk in computing r = 
H(v||M) in this prefixed-hash mode: it allows an attacker to use an extension 
attack and find M' extending such that r'= H(v||M') are related by a known 
extension function, say F, so r'=F(r).    Of course, this is just a non-linear 
relation between r and r', and there are no known ways to exploit it, because 
the known exploits require a linear relation between r and r' (to apply linear 
algebra), or else some kind of range bias in r and r' (to apply lattice 
methods).

So, this risk is definitely just a theoretical worry: and we can wave it away 
by relying on security properties of the resulting function F.  Better yet, it 
can be largely alleviated with a wide-pipe hash, or use a narrow-pipe hash of 
width larger than the modulus (effectively a wide-pipe), or by using something 
different than the prefix-construction, kind of like HMAC, because these 
methods seem to prevent the creation of the known relation F above.  Provided 
the latter counter-measures are not too costly compared to simple prefixing, 
they seem preferable to simple-prefixing.

Secondly, and even more theoretically, although I fully expect that the random 
oracle model (ROM) security proof(s) could easily work with this dual use of 
the hash, I wonder if such a result has been written up formally somewhere: 
just in case there's isn't some kind of surprising bad interaction between the 
two uses.

>
> A verifier computes c=H(M||R) mod q, and verifies that sG+cA=R. This scheme
> is secure in the ROM as it is yet another Schnorr signature variation. For 
> wide-
> pipe designs it's somewhat collision resistant.
>
[DB]  Neven, Smart and Warinschi documented the fact that Schnorr signatures 
need the hash to have certain security properties: including chosen-target 
random prefix preimage resistance ("RPP"), as well a second-preimage version 
of this ("RPSP").  One can argue that these security properties are plausible 
since nobody has broken them, despite the widespread popularity of 
prefixed-Schnorr.  For example, in addition to EdDSA, there are several 
Schnorr-like signature schemes standardized in ISO (and even in ANSI: 
X9.92-1).

By contrast, it seems that hardly anybody has seriously considered 
suffixed-Schnorr before.  As such, nobody has much incentive to try to 
directly cryptanalyze corresponding suffix-version of the 
Neven-Smart-Warinschi security properties of the hash.  Of course, these 
security properties still seem like very plausible security properties. 
Furthermore, (i) they hold true in the random oracle model (ROM) (but so do 
non-extension properties, so there are sometimes gap between ROM and real 
hashes), and (ii) Neven, Smart and Warinschi (NSW) state that these security 
properties are also implied by collision resistance of the hash.  That's a 
good start, but it would be nice to have even greater assurance provided by an 
incentive for direct cryptanalysis.  Is there some other well-established 
scheme that depends on such hash security properties?  Or, maybe one can 
further formalize the NSW argument about the collision resistance, and use a 
hash with sufficient collision resistance.  I have verified the NSW argument: 
I vaguely recall that there exist contrived pathological hashes that separate 
the collision resistance from preimage resistance, but I did not cross check 
these with the NSW argument.