Opened 5 years ago
Closed 5 years ago
#12980 closed defect (implemented)
Implement ed25519 primitives for proposals 220, 224, 228
Reported by: | nickm | Owned by: | |
---|---|---|---|
Priority: | High | Milestone: | Tor: 0.2.6.x-final |
Component: | Core Tor/Tor | Version: | |
Severity: | Keywords: | tor-relay, prop220, prop224, prop228, nickm-patch | |
Cc: | Actual Points: | ||
Parent ID: | Points: | ||
Reviewer: | Sponsor: |
Child Tickets
Change History (9)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
Status: | new → needs_review |
---|
Okay, I've gotten this ready for review.
comment:3 follow-up: 4 Changed 5 years ago by
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?
comment:4 Changed 5 years ago by
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 secret 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.
comment:5 Changed 5 years ago by
Just added a Python implementation and some test vectors generated by that python implementation.
comment:6 Changed 5 years ago by
Keywords: | nickm-patch added |
---|
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.
comment:7 Changed 5 years ago by
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
comment:9 Changed 5 years ago by
Resolution: | → implemented |
---|---|
Status: | needs_review → closed |
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.
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.