[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 21:09:27 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
-------------------------------------------------+-------------------------

Comment (by isis):

 Hi, I know this is a bikesheddy topic… so I'm sorry for adding to it.

 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::curve::CompressedEdwardsY;
 use curve25519_dalek::curve::ExtendedPoint;
 use curve25519_dalek::curve::Identity;

 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(),
         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_small_order() {
         true  => return None, // the point was of small order
         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 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::constants;
     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.4 secs
             Running target/release/deps/tor22006-4d45ae24d96b617f

 running 2 tests
 test bench::current_design     ... bench:      21,857 ns/iter (+/- 2,998)
 test bench::with_decaf_instead ... bench:       7,770 ns/iter (+/- 1,238)

 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.

--
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