[tahoe-dev] Fwd: Small-key DSA variant

[David-Sarah Hopwood]

Zooko Wilcox-O'Hearn wrote:
> The small-key variant I'm asking about goes back to the ElGamal
> verification equation:
> 
> R^s / y^r = g^h mod p
> 
> but instead of solving for R, we solve for y in a similar way:
> 
> y = R^(s/r) / g^(h/r) mod p
> 
> This means that with an ElGamal style (R,s) signature, the verifier
> can derive y = g^x mod p. So he doesn't have to know the public key.
> Instead of letting the public key be y, we can make it H(y) for some
> hash function H. Then the verification is:
> 
> H(y) = H( R^(s/r) / g^(h/r) mod p )
> 
> We have increased the signature size from twice the size of q to the
> sum of the sizes of p and q (which is much bigger, for typical non-EC
> DSA groups). But we have decreased the public key from the size of p to
> the size of H.
> 
> Now the interesting question is whether H can be the size of the  
> security
> parameter, rather than twice the size like q. Maybe we could use an 80
> bit H. This would make for a very small public key (again at the expense
> of a much larger signature).
> 
> The idea would be that y is a fixed target, and a forger needs to come
> up with an R,s whose hash matches the hash of y. It's a second preimage
> problem, not a collision problem.

Hmm. If collisions on H are possible then an attacker can search for
two message/signature pairs with the same signature, (M1, (R,s)) and
(M2, (R,s)), such that the solutions for y have colliding hashes:

  H(R^(s / r) / g^(h_M1 / r) mod p) = H(R^(s / r) / g^(h_M2 / r) mod p)

and hence are verifiable by the same public key (their own key, that is,
not someone else's). This is a "duplicate signature" attack in the
terminology of <http://citeseer.ist.psu.edu/stern02flaws.html>.

Is that a valid attack on the intended security properties of Tahoe?
I think probably not, provided that no-one expects these signatures
to guarantee nonrepudiability.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com