prop224: Validate ed25519 pubkeys to remove torsion component

changed milestone to %Tor: 0.3.2.x-final

added component::core tor/tor ed25519 milestone::Tor: 0.3.2.x-final owner::asn parent::21888 priority::medium prop224 resolution::fixed review-group-18 reviewer::isis reviewer::nickm severity::normal sponsor::R-can status::closed tor-hs type::defect labels

Trac:
Description: We should validate ed25519 pubkeys used in prop224 (like the blinded key) to make sure there is no torsion components. In the case of the blinded key, this ensures that there are no equivalent keys due to the torsion component.

Please see: https://lists.torproject.org/pipermail/tor-dev/2017-April/012164.html https://lists.torproject.org/pipermail/tor-dev/2017-April/012213.html

to

We should validate ed25519 pubkeys used in prop224 (like the blinded key) to make sure there is no torsion components. In the case of the onion address ed25519, this ensures that there are no equivalent onion addresses due to the torsion component.

Please see: https://lists.torproject.org/pipermail/tor-dev/2017-April/012164.html https://lists.torproject.org/pipermail/tor-dev/2017-April/012213.html

Pushed initial branch at bug22006.

I want to write another unittest to ensure that the validation function catches evil pubkeys. I need Ian's help with that; will come back to this soon. Not marking this as needs_review yet.

Trac:
Owner: N/A to asn
Status: new to assigned

New branch posted at bug22006_v2.

I posted it on [tor-dev] as well, so that Ian can see it: https://lists.torproject.org/pipermail/tor-dev/2017-April/012229.html

I will mark it as needs_review after I get an ACK from Ian.

OK, since Ian no longer has review comments for this branch, I'm pushing a squashed bug22006_v3 branch and marking it as needs_review.

Gitlab review here: https://gitlab.com/asn/tor/merge_requests/15

The only thing I don't like here is that in 60ed3d0e2 there is no way to know that we are actually checking all ed25519 keys from the network. I scanned the codebase to find places where we receive ed25519 keys, and I think I identified all the high-level places in the code that accept such keys but I don't know if I found all of them.

I did this because Ian suggested it here: https://lists.torproject.org/pipermail/tor-dev/2017-April/012230.html

If we want to take this seriously and ensure that we do it for all keys received on the net, we could add a int key_is_validated flag to ed25519_public_key_t, and throw a BUG() (or return -1) if we ever try to verify a signature with a non-validated pubkey.

What do you guys think? FWIW, for most cases this is not a life-or-death validation, but more like a nice thing to do to avoid any edge-case esoteric attacks.

Trac:
Status: assigned to needs_review

Here is a review by Yawning:

12:46 < Yawning> the donna code will crash when built with sse2
12:48 < asn> how do i build with sse2?
12:49 < Yawning> you do a 32 bit intel build on something modern
12:49 < Yawning> iirc
12:49 < Yawning> I don't remember what I did
12:50 < Yawning> #if defined(__SSE2__) && !defined(CPU_X86_64)
12:51 < Yawning> or you could add ALIGN(16) in the right place to `  ge25519 Point, Result;`
12:52 < Yawning> or since modern x86 has fast unaligned load/stores anyway
12:52 < Yawning> you could go and change the places that would cause it to crash, so the alignment requirement isn't there
12:53 < Yawning> though I guess people building tor for 32 bit intel are running on potatos
12:54 < Yawning> does doing the validation as part of `ed25519_public_from_base64` mean that when parsing the consensus it will eventually do 
                 several thousand scalar multiplys

Trac:
Status: needs_review to needs_revision

OK pushed a fixup commit that adds the ALIGN calls that Yawning suggested in the donna code. It seems to be a common idiom in the donna code so it should be the right thing. I tried to reproduce the SSE2 crash but I couldn't repro it. Yawning said that he didn't see the crash himself, but he thought that it would crash because of the lack of ALIGN calls.

So now, the last issue is whether we want our validation (which includes a scalar mult) running 7k times everytime we receive a consensus, and also everytime we receive a descriptor etc. It's currently the case, since Ian suggested we do so and he said the validation is not particularly expensive. I tested it on my laptop and I didn't notice any speed difference from validating 7k ed25519 keys when receiving the consensus, however perhaps this might be more battery-drain in mobile devices, etc. Nick any opinions here?

Trac:
Status: needs_revision to needs_review

asn says this is ok to defer

Trac:
Milestone: Tor: 0.3.1.x-final to Tor: 0.3.2.x-final

We discussed this with Nick, and decided that the best course of action here might be to do this validation for all HS public keys, and also for all received ed25519 public keys but only on the dirauth-side.

So instead of having clients do validation for all received public keys (which can be quite heavy since consensuses contain 7k of them), we do it only on the dirauth side.

Trac:
Keywords: tor-hs prop224 ed25519 deleted, review-group-18, prop224, tor-hs, ed25519 added

Trac:
Reviewer: N/A to nickm

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. 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_order_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() * constants::l,
        false => return None, // the point was invalid
    }

    // We need to check that p*l is the identity (the identity point
    // is X:Y:Z:T == 0:1:1:0 since this shows there is no torsion               
    // component)
    match q.is_identity() {
        true  => return Some(q),
        false => return None, // point * ell is the identity
    }
}

// Decaf decompression assures 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_order_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 P * l is not equal to the identity, which amounts to 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.

Trac:
Cc: N/A to isis

I left some quick notes on the patch. I need somebody mathy to look at the actual multiplication functions, since they're outside my comfort zone.

The final functional commit, which makes all the keys get validated, can't stay -- it's too slow. Let's do the discussed-above option instead. Please let me know if you need any help figuring out how to do the authority-side logic: the keypin functionality should make it easy.

I don't think we can do decaf encoding on ed25519 identities: they are already published in descriptors and interpreted widely. For hidden services and decaf, I don't know how hard the transition would be. The only place to change the encoding would be in .onion addresses, and I don't know whether there's time/energy to do that in the current state of prop224.

Trac:
Status: needs_review to needs_revision

Replying to nickm:

I don't think we can do decaf encoding on ed25519 identities: they are already published in descriptors and interpreted widely. For hidden services and decaf, I don't know how hard the transition would be. The only place to change the encoding would be in .onion addresses, and I don't know whether there's time/energy to do that in the current state of prop224.

Happy to be overruled here, but, does this imply that we should stick to the current encoding for onion addresses, since if we have to maintain two different encodings forever, and other people building Tors will forever need to build both kinds, that will make everybody sad?

Replying to arma:

Replying to nickm:

I don't think we can do decaf encoding on ed25519 identities: they are already published in descriptors and interpreted widely. For hidden services and decaf, I don't know how hard the transition would be. The only place to change the encoding would be in .onion addresses, and I don't know whether there's time/energy to do that in the current state of prop224.

Happy to be overruled here, but, does this imply that we should stick to the current encoding for onion addresses, since if we have to maintain two different encodings forever, and other people building Tors will forever need to build both kinds, that will make everybody sad?

Right. I was mostly just writing it down out of hopefulness, and for posterity's sake, so that when the current really slow thing really does become way too slow, we can revisit the point compression formats and speed it up by ~15x. It would be a breaking change, and I'd suggest there be an actual proposal for the improvement. (Also, I've been in discussions with Mike Hamburg to standardise "Decaf for 25519" a.k.a. "Ristretto", and I hear Trevor Perrin is doing some work to standardise "Schnorr-like signatures for Decaf" a.k.a. "Schnorrcaf". It would be wise to hold off the proposal until the standards are finalised. :)

Replying to nickm:

I left some quick notes on the patch. I need somebody mathy to look at the actual multiplication functions

Trac:
Reviewer: nickm to nickm, isis

Replying to isis:

Replying to nickm:

I left some quick notes on the patch. I need somebody mathy to look at the actual multiplication functions

A couple minor things:

In ed25519_donna_scalarmult_with_group_order() since it's unpacking the public key from bytes into a point, perhaps we should not ignore the return value of ge25519_unpack_negative_vartime(), since the latter function will return 0 if the point wasn't on the curve (refer to the check ← sqrt(u/v) comment from my code above for what the check in the unpacking function is doing).
The cleanups at the end of ed25519_donna_scalarmult_with_group_order() seem like they might be unnecessary overhead, since all those variables are public, but it doesn't really harm anything to memwipe them.

LGTM though.

prop224: Validate ed25519 pubkeys to remove torsion component

Child items ...

Activity