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:

Description

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

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

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

Child Tickets

Change History (9)

comment:1 Changed 5 years ago by nickm

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.

comment:2 Changed 5 years ago by nickm

Status: newneeds_review

Okay, I've gotten this ready for review.

comment:3 Changed 5 years ago by nickm

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 in reply to:  3 Changed 5 years ago by NickHopper

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.

Version 0, edited 5 years ago by NickHopper (next)

comment:5 Changed 5 years ago by nickm

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

comment:6 Changed 5 years ago by nickm

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 asn

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:8 Changed 5 years ago by nickm

Okay, I think I addressed those.

comment:9 Changed 5 years ago by nickm

Resolution: implemented
Status: needs_reviewclosed

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.

Note: See TracTickets for help on using tickets.