Vrf uniqueness was violated (quickfix)

liamsi commented 7 years ago

Adopt VRF to update in CONIKS paper …

add unique identifier: also hash h=H1(m), g^x and h^x (the VRF output) and not only with random nonce r (g^r, h^r); additionally hash m into H2 (as before)
like in the paper add the base-point and public-key
skip outdated test-vectors
renamed some vars according to naming in the paper
unrelated: remove formatting version of test-output where no placeholder is used

fixes #175

maditya commented 7 years ago

cc @r2ishiguro

r2ishiguro commented 7 years ago

@Liamsi , I just wonder if you had considered this IETF draft? https://tools.ietf.org/html/draft-goldbe-vrf-00 The proposed hash is different than ours. Since we're sharing the code, maybe it's a good idea to keep the code in sync and the draft could be a good one to refer to...?

liamsi commented 7 years ago

Yes, we (the CONIKS team) are currently discussing to switch to this IETF draft (a good alternative would be OWS's vxeddsa). I think it's a good idea to implement the IETF version soon. If we do so, sure, let's keep the code in sync!

liamsi commented 7 years ago

I would propose to implement two versions independently and share test-vectors. What do you think of this idea? I still need to discuss with my team-members, though.

r2ishiguro commented 7 years ago

You mean, we implement the same algorithm (probably EC-VRF-ED25519-SHA256?) independently and compare the results? Sounds good to me, but after that I'd like to share one implementation. Maybe we can create a new repository just for VRF in GitHub, or we can refer to the coniks-sys or coname repository.

liamsi commented 7 years ago

Yes, sounds good to me!

liamsi commented 7 years ago

Maybe we can create a new repository just for VRF in GitHub, or we can refer to the coniks-sys or coname repository.

I think a single dedicated repo makes sense as the VRF might become useful for other projects, too. Did you also have a look on vxeddsa BTW? (it is conceptually very similar to the VRF already used here and in coname but it doesn't suffer from this uniqueness problem)

r2ishiguro commented 7 years ago

I looked it over. It looks the same except the way the hash value is constructed. The draft looks simpler and if it doesn't require SHA3, it might have a benefit a little bit.

r2ishiguro commented 7 years ago

Here's a result from my implementation:

alpha: 6d657373616765 x: 1fcce948db9fc312902d49745249cfd287de1a764fd48afb3cd0bdd0a8d74674885f642c8390293eb74d08cf38d3333771e9e319cfd12a21429eeff2eddeebd2 P: 885f642c8390293eb74d08cf38d3333771e9e319cfd12a21429eeff2eddeebd2 pi: 033236f8991d15d073ff8754645f0a11071e3092227d85c243833d006b5cfe9dc0a89beb44a930f357073f49aaddc8f2d708a943c27b552a61f3594e39a59a8d49dc393cd22e48c0fbde5628c1c298924d vrf: 3236f8991d15d073ff8754645f0a11071e3092227d85c243833d006b5cfe9d h: 025120c3e33ae1f9829486fa11653d2dd33ce79b9d7321b912c487eac515d27261

I used golang.org/x/crypto/ed25519.GenerateKey() to generate (x, P). h = ECVRF_hash_to_curve(alpha, g^x = P) as specified in the draft. Sometimes I needed to iterate more than 100 to get a valid curve.. For Ed25519, there should be more efficient way to generate a curve, I guess, but for now I just followed the draft.

As for implementation, I used "golang.org/x/crypto/ed25519/internal/edwards25519" but it's internal so I couldn't import it. I copied it as-is into my repository for now.. Maybe we should ask Google to incorporate VRF into ed25519...?

andres-erbsen commented 7 years ago

I tried, as far as I remember the pull request never got looked at. Clarification: this was for the now-broken vrf from the original coniks paper, a better-justified design might have a better chance.

liamsi commented 7 years ago

I looked it over. It looks the same except the way the hash value is constructed. The draft looks simpler and if it doesn't require SHA3, it might have a benefit a little bit.

Vxeddsa doesn't use SHA3 either. Also, vxeddsa's hash_to_curve might be faster. We have a work in progress PR on that, too: https://github.com/coniks-sys/coniks-go/pull/167 Another thing to currently consider: the draft is still a draft and it might change.

masomel commented 7 years ago

@r2ishiguro @andres-erbsen Would either of you be willing to review this PR? It LGTM, but it'd be great to have a more expert review before we merge this.

r2ishiguro commented 7 years ago

LGTM, too. FYI, I'm exchanging emails with Sharon and Leonid about the test vectors. They seem to be "tweaking" the spec right now. I'll keep you informed.

masomel commented 7 years ago

Thanks @r2ishiguro! And sounds good, hopefully we can get the ball rolling on that soon.

coniks-sys / coniks-go

Vrf uniqueness was violated (quickfix) #176