Opened 8 months ago

Closed 6 months ago

#22006 closed defect (fixed)

prop224: Validate ed25519 pubkeys to remove torsion component

Reported by: asn Owned by: asn
Priority: Medium Milestone: Tor: 0.3.2.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-hs, prop224, ed25519, review-group-18
Cc: isis Actual Points:
Parent ID: #21888 Points:
Reviewer: nickm, isis Sponsor: SponsorR-can

Description (last modified by asn)

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

Child Tickets

Change History (28)

comment:1 Changed 8 months ago by asn

Description: modified (diff)

comment:2 Changed 8 months ago by asn

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.

comment:3 Changed 8 months ago by dgoulet

Owner: set to asn
Status: newassigned

comment:4 Changed 8 months ago by asn

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.

comment:5 Changed 8 months ago by asn

Status: assignedneeds_review

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.

comment:6 Changed 7 months ago by asn

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

comment:7 Changed 7 months ago by asn

Status: needs_reviewneeds_revision

comment:8 Changed 7 months ago by asn

Status: needs_revisionneeds_review

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?

comment:9 Changed 7 months ago by nickm

Milestone: Tor: 0.3.1.x-finalTor: 0.3.2.x-final

asn says this is ok to defer

comment:10 Changed 6 months ago by asn

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.

comment:11 Changed 6 months ago by nickm

Keywords: review-group-18 added

comment:12 Changed 6 months ago by nickm

Reviewer: nickm

comment:13 Changed 6 months ago by isis

Cc: isis added

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_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() * 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 * cofactor is the identity
    }
}

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

Last edited 6 months ago by isis (previous) (diff)

comment:14 Changed 6 months ago by nickm

Status: needs_reviewneeds_revision

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.

comment:15 in reply to:  14 ; Changed 6 months ago by 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?

comment:16 in reply to:  15 Changed 6 months ago by isis

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. :)

comment:17 in reply to:  14 ; Changed 6 months ago by isis

Reviewer: nickmnickm, isis

Replying to nickm:

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

comment:18 in reply to:  17 Changed 6 months ago by 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.

comment:19 Changed 6 months ago by asn

Status: needs_revisionneeds_review

OK pushed a new branch here with the ambitious name bug22006_final!

This branch:

  • Removes the old commit that validated all sorts of ed25519 pubkeys, and now only does it before keypinning on the dirauth side. This implements the behavior of comment:10.

Note that we also need to do this check on our prop224 client-side code which was the original purpose of this ticket, but the prop224 code is not ready yet. I can make a ticket about this so we don't forget.

  • Based on isis' review, I'm now checking the retval of ge25519_unpack_negative_vartime() and also I removed the useless memwipes. I had to check the func signature to do the retval checking, so it's a non-trivial fixup commit but not hard to review.
  • It also addresses the points of nick's review, particularly the one about missing documentation.
Last edited 6 months ago by asn (previous) (diff)

comment:20 Changed 6 months ago by nickm

lgtm. Isis, does this look good to you?

comment:21 Changed 6 months ago by nickm

maybe add another fixup commit to improve this message:

+      log_warn(LD_DIRSERV, "Received bad key from %s (source %s)",
+               router_describe(ri), source);

That is, it would be better to say what's wrong with the key.

comment:22 Changed 6 months ago by catalyst

It would be nice to have a summary of what security goals this validation accomplishes, given that ed25519 signature verification already nulls out the cofactor. (e.g., what can an adversary do with a non-canonical onion address and no private key for it?) Also, I suspect that the HS and non-HS cases have slightly different security goals, and these would be good to distinguish.

Terminology nit: all the sources I can easily find define a torsion point as one that has finite order. So as I understand it, all ed25519 points are "torsion points". Maybe use "small-torsion component or "small-order component" instead of "torsion component"?

comment:23 in reply to:  20 Changed 6 months ago by isis

Replying to nickm:

lgtm. Isis, does this look good to you?

lgtm

comment:24 Changed 6 months ago by nickm

Milestone: Tor: 0.3.2.x-finalTor: 0.3.1.x-final

Squashed as asn_bug22006_final_squashed.

Merged to 0.3.2.

Marking for possible 0.3.1 backport.

comment:25 Changed 6 months ago by dgoulet

Some extra \n in the log_warn():

log_warn(LD_CRYPTO, "ed25519 pubkey is the identity\n");
log_warn(LD_CRYPTO, "ed25519 group order scalarmult failed\n");
log_warn(LD_CRYPTO, "ed25519 validation failed\n")

comment:26 Changed 6 months ago by nickm

Fixed on the branch and merged into master. Thanks!

comment:27 Changed 6 months ago by catalyst

I'm inclined to recommend against backporting. prop224 HS are not in 0.3.1.x, and in the non-HS case, I think these patches add code complexity at a late stage of the release process without sufficient benefit.

comment:28 Changed 6 months ago by nickm

Milestone: Tor: 0.3.1.x-finalTor: 0.3.2.x-final
Resolution: fixed
Status: needs_reviewclosed

"No backport" it is.

Note: See TracTickets for help on using tickets.