Implement ed25519 primitives for proposals 220, 224, 228

For proposal 220, we need ed25519 with detached signatures. (#12498 (moved))

For proposal 224 (#12424 (moved)), we need ed25519 with key blinding (#8106 (moved)).

For proposal 228, we need the ability to convert curve25519 keys to ed25519 keys. (#12499 (moved))

changed milestone to %Tor: 0.2.6.x-final

added component::core tor/tor milestone::Tor: 0.2.6.x-final nickm-patch priority::high prop220 prop224 prop228 resolution::implemented status::closed tor-relay type::defect labels

I have these things implemented in a branch called "ed25519_ref10", based on the ref10 implementation of ed25519. (We can add support for floodyberry's ed25519-donna later if the performance turns out to suck.)

They're all tested, but they need a bit more documentation and testing before I'd call them ready for review. The blinding implementation especially took me longer than it should have, and I'm wondering whether I really read the algorithm description correctly.

Okay, I've gotten this ready for review.

Trac:
Status: new to needs_review

The key blinding part of this will IMO be the trickiest part of the design to review. For reference, I tried to follow https://www-users.cs.umn.edu/~hopper/basic-proof.pdf , but with these changes:

In Nick Hopper's writeup, he changes the formula for r in blinded signatures from H(k,m) to H(k,t,m). To simplify the logic, I went with H(H(k,s_t), m) -- this allows me to derive secret keys (a',k') as a'=s_t * a, k' = H(k,s_t). Does this also work?

I'm using 's_t' in place of 't' nearly everywhere.

AFAICT, Nick's document doesn't mention exactly how to multiply a by s_t. I'm doing it modulo the group order l -- I think that's right. I'm also applying the regular secret-key bit-manipulations to 's_t' before I multiply by it. It appears to be necessary to clear the high bits -- is it safe to leave the low bits uncleared?

Replying to nickm:

In Nick Hopper's writeup, he changes the formula for r in blinded signatures from H(k,m) to H(k,t,m). To simplify the logic, I went with H(H(k,s_t), m) -- this allows me to derive secret keys (a',k') as a'=s_t * a, k' = H(k,s_t). Does this also work?

Yes, this will work without breaking the security proof.

I'm using 's_t' in place of 't' nearly everywhere.

I only see one place t is used other than in the derivation of s_t, in the derivation of the symmetric key k_t. Using s_t in place of t should be fine here, since the security proof only relies on the reduction knowing s_t.

AFAICT, Nick's document doesn't mention exactly how to multiply a by s_t. I'm doing it modulo the group order l -- I think that's right. I'm also applying the regular secret-key bit-manipulations to 's_t' before I multiply by it. It appears to be necessary to clear the high bits -- is it safe to leave the low bits uncleared?

Reducing a' modulo l is right. It's my understanding that it's always safe to leave the low bits of an exponent in Ed25519 uncleared - clearing them is just a small optimization.

Just added a Python implementation and some test vectors generated by that python implementation.

Apply a nickm-patch keyword to tickets in needs_review in 0.2.6 where I wrote the patch, so I know which ones I can('t) review myself.

Trac:
Keywords: tor-relay prop220 prop224 prop228 deleted, prop220, tor-relay, prop224, prop228, nickm-patch added

I pushed a code review in branch ed25519_ref10_asn_review in https://git.torproject.org/user/asn/tor.git. Here it is: https://gitweb.torproject.org/user/asn/tor.git/commitdiff/c885f2468421eb6b767ddd0f8f42250033c30764

Okay, I think I addressed those.

Merging to master. This still needs more attention, and I'll continue to seek feedback on the crypto parts, but we need to start implementing the things that need it.

Trac:
Status: needs_review to closed
Resolution: N/A to implemented

closed

moved to tpo/core/tor#12980 (closed)