Key image can be computed from public key

[PlasmaPower]

As h = H(L) * g, yk = xk * g, and y = xk * h, we can transform y to y = xk * H(L) * g = H(L) * xk * g = H(L) * yk which means that y, the key image, can be computed from the public key (and the list of all public keys). This makes identifying the signer of a ring signature trivial, as you simply need to check if the key image matches each of the public keys.

To fix this, you need to use a function that computes a curve point directly from a hash. There are several potential algorithms for this, such as:

• https://tools.ietf.org/html/draft-irtf-cfrg-vrf-02#section-5.4.1
• https://tools.ietf.org/html/draft-sullivan-hash-to-curve-00

It also seems that I'm not the first person to find this issue in other implementations of the same algorithm: https://web.archive.org/web/20160218042108/shnoe.wordpress.com/2016/02/11/de-anonymizing-shadowcash-and-oz-coin/

[Acentelles]

Hi @PlasmaPower , Thank you for spotting this vulnerability. We've addressed it here

[sdiehl]

The addition of this algorithm should fix the information leak.

https://github.com/adjoint-io/aos-signature/pull/6/files#diff-9e6d8fae973f4fc26ef551d36f508ba7R212

[PlasmaPower]

The fix looks good but the README should also be updated, and I'm not sure what the correct notation is. Thanks!