#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 _______________________________________________ tor-bugs mailing list tor-bugs@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs