search

coniks-sys / coniks-go

A CONIKS implementation in Golang
http://coniks.org
Other
116 stars 30 forks source link

Uniqueness of VRF is violated #175

Closed masomel closed 7 years ago

masomel commented 7 years ago

An attacker can choose a different rs when computing s. Rather than s = H2(h, [r]G, [r]H), the attacker computes s = H2(h, [a]G, [b]H) and claims that the VRF output is [(b-a)/s + k] H rather than[k]H and t = a-sk.

This checks out because the verifier checks that s == H2(h, [t]G + [s]([k]G), [t]H + [s]VRF). s == H2(h, [a]G, [b]H) Because [t]G+[s]([k]G) = [a]G. [t]H + [s]VRF = [a-sk]H + [b-a+sk]H = [b]H. The attack succeeds at producing a non-unique value for VRF.

http://eprint.iacr.org/2012/577.pdf Page 4:

Goldberg and Reyzin (March 2017) discovered that if one does not hash the unique identifier when computing the challenge of the proof system, the uniqueness of the VRF from DDH assumption is violated. Therefore, when using the VRF, it is important to hash the unique identifier as well.

Thanks to Sharon Goldberg and Leonid Reyzin for reporting this bug.

gdbelvin commented 7 years ago

Cross referencing google/keytransparency#567