[tor-bugs] #22006 [Core Tor/Tor]: prop224: Validate ed25519 pubkeys to remove torsion component

Tor Bug Tracker & Wiki blackhole at torproject.org
Tue Jun 20 22:36:46 UTC 2017


#22006: prop224: Validate ed25519 pubkeys to remove torsion component
-------------------------------------------------+-------------------------
 Reporter:  asn                                  |          Owner:  asn
     Type:  defect                               |         Status:
                                                 |  needs_review
 Priority:  Medium                               |      Milestone:  Tor:
                                                 |  0.3.2.x-final
Component:  Core Tor/Tor                         |        Version:
 Severity:  Normal                               |     Resolution:
 Keywords:  tor-hs, prop224, ed25519, review-    |  Actual Points:
  group-18                                       |
Parent ID:  #21888                               |         Points:
 Reviewer:  nickm                                |        Sponsor:
                                                 |  SponsorR-can
-------------------------------------------------+-------------------------
Changes (by isis):

 * cc: isis (added)


Comment:

 Hi, I know this is a bikesheddy topic… so I'm sorry for adding to it. (And
 also for giving written input very late in the process.)

 However it would not only be safer, but also faster to use Decaf point
 compression as the wire format and key format. We'd need to create code to
 do Schnorr-style signatures within the Decaf group, but this would be
 trivial.  [https://github.com/isislovecruft/tor22006 Here's some code I
 wrote] to benchmark the key validation in the current design, versus if we
 used Decaf instead:

 {{{
 extern crate core;

 #[cfg(all(test, feature = "bench"))]
 extern crate test;

 #[cfg(test)]
 extern crate rand;

 extern crate curve25519_dalek;

 use curve25519_dalek::constants;

 use curve25519_dalek::curve::CompressedEdwardsY;
 use curve25519_dalek::curve::ExtendedPoint;
 use curve25519_dalek::curve::Identity;
 use curve25519_dalek::curve::IsIdentity;

 use curve25519_dalek::decaf::CompressedDecaf;
 use curve25519_dalek::decaf::DecafPoint;


 // The public key for an ed25519 scheme is a compressed edwards point (the
 // Y-coordinate and the sign of X).

 pub fn mult_by_cofactor_and_validate(key: &CompressedEdwardsY) ->
 Option<ExtendedPoint> {
     // decompression of Y in any sane curve25519 library should check
 validation
     // by computing:
     //
     //    Z ← fe(1)
     //    u ← Y² - Z
     //    v ← dY² + Z
     //    check ← sqrt(u/v)
     //
     // If `v` is nonzero and `check` is okay (meaning that `u/v` is
 square),
     // then the point is valid.
     let p: Option<ExtendedPoint> = key.decompress();
     let q: ExtendedPoint;

     match p.is_some() {
         true  => q = p.unwrap().mult_by_cofactor() * constants::l,
         false => return None, // the point was invalid
     }

     // We also need to check that the point is not the identity (the
     // identity point X:Y:Z:T == 0:1:1:0 is a valid point, but we
     // shouldn't accept it as a key)
     match q.is_identity() {
         true  => return None, // point * l * cofactor the identity
         false => return Some(q),
     }
 }

 // Decaf decompression ensures both that the point is a valid point on
 // the curve and that it is within a prime-order group.
 pub fn decaf_decompress(key: &CompressedDecaf) -> Option<DecafPoint> {
     let p: Option<DecafPoint>;

     // The constant-time equality check for a decaf point is only
     // defined (in dalek) for the compressed version, and works by byte
     // comparison.
     match *key == CompressedDecaf::identity() {
         true  => return None, // the point was the identity
         false => p = key.decompress(),
     }

     match p.is_some() {
         true  => return p,
         false => return None, // invalid decaf point
     }
 }

 #[cfg(all(test, feature = "bench"))]
 mod bench {
     use super::*;

     use test::Bencher;
     use rand::OsRng;

     use curve25519_dalek::scalar::Scalar;

     #[bench]
     fn current_design(b: &mut Bencher) {
         let mut csprng: OsRng = OsRng::new().unwrap();
         let a: Scalar = Scalar::random(&mut csprng);
         let p: ExtendedPoint = &a * &constants::ED25519_BASEPOINT;
         let key: CompressedEdwardsY = p.compress_edwards();

         b.iter(| | mult_by_cofactor_and_validate(&key) )
     }

     #[bench]
         fn with_decaf_instead(b: &mut Bencher) {
         let mut csprng: OsRng = OsRng::new().unwrap();
         let p: DecafPoint = DecafPoint::random(&mut csprng);
         let key: CompressedDecaf = p.compress();

         b.iter(| | decaf_decompress(&key) )
     }
 }
 }}}

 The results are:

 {{{
 ∃!isisⒶwintermute:(master *)~/code/rust/tor22006 ∴ cargo bench
 --features="bench"
    Compiling tor22006 v0.1.0 (file:///home/isis/code/rust/tor22006)
          Finished release [optimized] target(s) in 1.2 secs
                     Running target/release/deps/tor22006-4d45ae24d96b617f

 running 2 tests
 test bench::current_design     ... bench:     114,570 ns/iter (+/- 30,244)
 test bench::with_decaf_instead ... bench:       7,730 ns/iter (+/-  2,377)

 test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out
 }}}

 So you'd be getting ''better'' safety guarantees (the Decaf compression
 scheme guarantees the points are in a prime-order group) for cheaper, and
 you'd never need to worry about where and when to multiply by the cofactor
 and the order.

 Essentially what's happening here is that Decaf decompression is actually
 slightly cheaper than the standard decompression for a Twisted Edwards
 Y-coordinate. Even though it's cheaper, it has point validation built in.
 So if you go the other route, it's not only the expense of the
 decompression that is higher, but you then need to check that `8P * l` is
 not equal to the identity, which amounts to three point doublings ''and''
 a scalar multiplication in extra costs.  (The check for `q.is_identity()`
 is the same cost as the `*key == CompressedDecaf::identity()`, i.e. both
 just do a byte-for-byte comparison of the underlying 32-byte array.)
 Additionally, (as asn already noted) you'll have to keep doing this all
 over the place, and for quite a lot of routers.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/22006#comment:13>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online


More information about the tor-bugs mailing list