Opened 2 years ago

Last modified 4 weeks ago

#22029 needs_review enhancement

Allow ed25519 keys to be banned in the approved-routers file

Reported by: teor Owned by: neel
Priority: Medium Milestone: Tor: 0.4.2.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: 034-triage-20180328, 034-removed-20180328
Cc: neel Actual Points:
Parent ID: Points: 1
Reviewer: teor Sponsor:

Description

Once we start pinning ed25519 keys, we should probably also allow directory authorities to ban them in approved-routers. This will allow us to migrate away from RSA keys at some point.

(Where else do we use RSA fingerprints?)

Child Tickets

TicketTypeStatusOwnerSummary
#29828enhancementnewAdd an approved_routers network to chutney
#30638tasknewTest banning ed25519 keys in the approved-routers file on moria1
#30642enhancementassignedneelAdd an ed25519_identity file to the data directory
#30644enhancementclosedneelAdd our own base-64 encoded ed25519 public key in dirserv_add_own_fingerprint()
#30677enhancementclosedneelMove FP_REJECT and similar constants to a header, so we can access them in the tests
#30691enhancementclosedneelRefactor decoding outside the if expression in dirserv_load_fingerprint_file()
#30692defectclosedWrite better unit tests for dirserv_load_fingerprint_file()

Change History (67)

comment:1 Changed 2 years ago by dgoulet

Oh fine idea!

Quick question here. Can a relay have N rsa keys (for N > 1) for 1 ed25519 key and still keep it's uptime/weight?

I'm asking here because we currently block by RSA fingerprint but what if I can rotate that everyday (or when blocked) but still keep my consensus weight because my ed25519 is still recognized by dirauths?

comment:2 in reply to:  1 Changed 2 years ago by teor

Replying to dgoulet:

Oh fine idea!

Quick question here. Can a relay have N rsa keys (for N > 1) for 1 ed25519 key and still keep it's uptime/weight?

Yes, but not for long.

The directory authorities keep a key pinning journal, but don't enforce it.

When we turn on key pinning, authorities won't vote for relays that change one key and keep the other the same.

I'm asking here because we currently block by RSA fingerprint but what if I can rotate that everyday (or when blocked) but still keep my consensus weight because my ed25519 is still recognized by dirauths?

The bandwidth script uses RSA fingerprints, so changing your RSA removes all your bandwidth.

In the far future, when we remove RSA keys, we will want to have a file that bans both RSA and ed25519 keys, to make the transition easier.

comment:3 Changed 23 months ago by dgoulet

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

comment:4 Changed 18 months ago by nickm

Milestone: Tor: 0.3.3.x-finalTor: 0.3.4.x-final

Deferring various "new"-status enhancement tickets to 0.3.4

comment:5 Changed 16 months ago by nickm

Keywords: 034-triage-20180328 added

comment:6 Changed 16 months ago by nickm

Keywords: 034-removed-20180328 added

Per our triage process, these tickets are pending removal from 0.3.4.

comment:7 Changed 16 months ago by nickm

Milestone: Tor: 0.3.4.x-finalTor: unspecified

These tickets, tagged with 034-removed-*, are no longer in-scope for 0.3.4. We can reconsider any of them, if time permits.

comment:8 Changed 9 months ago by neel

Owner: set to neel
Status: newassigned

comment:9 Changed 9 months ago by neel

Cc: neel added

comment:10 Changed 6 months ago by neel

The function dirserv_load_fingerprint_file() reads the file approved-routers. I have a few questions:

  1. Should the ed25519 key in the approved-routers file be a base16-encoded key (similar to what we do right now with RSA fingerprints)?
  2. Would it be okay that if a ed25519 key was given, I check keypin hashtable to get the relay's corresponding RSA key and then add it to the list? I propose will be done with a new function that searches the ed25519 keypin hash table for each entry until a matching ed25519 key is given, and then return a corresponding RSA key.

I am concerned with Point 2 however because of the O(n2) running time from needing to go through the list of all Tor relays. Another concern is that mapping ed25519 to RSA could mean we prolong the life of the RSA code.

Would it be better to overhaul the relay data structures to be ed25519-first and then do this?

comment:11 in reply to:  10 Changed 6 months ago by nickm

Replying to neel:

The function dirserv_load_fingerprint_file() reads the file approved-routers. I have a few questions:

  1. Should the ed25519 key in the approved-routers file be a base16-encoded key (similar to what we do right now with RSA fingerprints)?

I think it should base64-encoded; that's how ed25519 keys are printed everywhere else in Tor.

  1. Would it be okay that if a ed25519 key was given, I check keypin hashtable to get the relay's corresponding RSA key and then add it to the list? I propose will be done with a new function that searches the ed25519 keypin hash table for each entry until a matching ed25519 key is given, and then return a corresponding RSA key.

I think it should just store the ed25519 keys, and look up by the ed25519 key.

I am concerned with Point 2 however because of the O(n2) running time from needing to go through the list of all Tor relays. Another concern is that mapping ed25519 to RSA could mean we prolong the life of the RSA code.

Would it be better to overhaul the relay data structures to be ed25519-first and then do this?

I think that might be a good idea, but instead of being ed25519-only, we should make it handle both ed25519 _and_ RSA keys.

comment:12 Changed 6 months ago by neel

Thank you for your responses, nickm!

I do have a few more questions, however:

I think it should just store the ed25519 keys, and look up by the ed25519 key.

Does that mean something like authdir_config_t should be done for ed25519 (even if the digests are stored as a union), and then introduce a function like dirserv_get_status_impl() that takes in ed25519 keys. And then I should make dirserv_router_get_status() look at ed25519 keys as well?

comment:13 Changed 6 months ago by nickm

I would suggest adding a third element to authdir_config_t, a digest256map_t, mapping ed25519 identities to router_status_t elements. Would that work?

comment:14 Changed 6 months ago by neel

I would suggest adding a third element to authdir_config_t, a digest256map_t, mapping ed25519 identities to router_status_t elements. Would that work?

Yes. I thought about doing the same thing as well (even before you responded).

comment:15 Changed 6 months ago by neel

My patch is ready and the PR is here: https://github.com/torproject/tor/pull/682

comment:16 Changed 6 months ago by neel

Status: assignedneeds_review

comment:17 Changed 6 months ago by nickm

Milestone: Tor: unspecifiedTor: 0.4.1.x-final

comment:18 Changed 5 months ago by dgoulet

Reviewer: teor

comment:19 Changed 5 months ago by teor

Reviewer: teor

I don't have time to do this review next week: I need to focus on #23588 (large, IPv6, needs tests) and #29280 (chutney).

comment:20 Changed 5 months ago by asn

Reviewer: asn

comment:21 Changed 5 months ago by asn

Status: needs_reviewmerge_ready

Code looks reasonable in principle. Added some tech-debt related concerns to the PR. Let me know if you want to fix these, thanks!

comment:22 Changed 5 months ago by asn

Status: merge_readyneeds_revision

Oops, meant to toggle to needs_revision.

Last edited 5 months ago by asn (previous) (diff)

comment:23 Changed 5 months ago by neel

Status: needs_revisionneeds_review

I have simplified the if loop and pushed it.

I do not plan to write a test for add_ed25519_to_dir().

comment:24 in reply to:  23 Changed 4 months ago by asn

Status: needs_reviewneeds_revision

Replying to neel:

I have simplified the if loop and pushed it.

I do not plan to write a test for add_ed25519_to_dir().

Hello neel,

sounds good wrt not writing tests.

However, I still feel that the parts of dirserv_load_fingerprint_file() that got changed are still much measier than before. In particular:

  • It's not clear to me what happens if is_rsa and is_ed25519 are false. Is this case handled? Should it be handled?
  • It's not clear to me why the if statement needs to be if ((a||b)||c). Is this equivalent to (a||b||c)? Why the extra parentheses or why so many stuff in the same if? It's not clear to me what it's trying to do. Like, will it send a log_notice everytime is_rsa is true? That does not seem like the previous behavior. Please it would be great if this could be simplified and also a comment added (perhaps even in its own function).

My suggestion would be to move the nickname checking above the key-type checking and then do stuff based on the key-type more cleanly and more commented.

Sorry for the nitpicks. Thanks! :)

comment:25 Changed 4 months ago by neel

Status: needs_revisionneeds_review

That's fine.

I have updated my code and pushed it.

comment:26 Changed 4 months ago by asn

Hey neel,

this is much better, but I still don't quite agree with this code block:

+    if (!is_valid_key ||
+        base16_decode(digest_tmp, sizeof(digest_tmp), fingerprint,
+                      HEX_DIGEST_LEN) != sizeof(digest_tmp) ||
+        digest256_from_base64(digest256_tmp, fingerprint) < 0) {
+      log_notice(LD_CONFIG,
+                 "Invalid fingerprint (nickname '%s', "
+                 "fingerprint %s). Skipping.",
+                 nickname, fingerprint);
+      continue;
+    }

I don't understand why we do an extra decode (either the base16_decode or the digest256_from_base64() is not useful at this point) when we already know the type of the key?

I coded an alternative approach in: https://github.com/torproject/tor/pull/810

Let me know if you like it and feel free to put it in merge_ready if so.

Thanks! :)

comment:27 Changed 4 months ago by neel

Status: needs_reviewmerge_ready

Your patch looks good to me.

comment:28 Changed 4 months ago by teor

Status: merge_readyneeds_revision

Hi, this patch contains at least one memory safety issue, and at least one crashing bug.

Please fix these issues. I added comments to the pull request.

I don't want to merge this patch unless there are unit tests for the new and modified functions. I want some automated checks for the issues that made it past review.

I would also like someone to actually run the code on an authority. If you want to use chutney, the networks/bwfile and torrc_templates/authority-bwfile.tmpl could be copied and modified to use an approved_routers file.

comment:29 Changed 4 months ago by teor

I opened #29828 for the chutney change.

comment:30 Changed 4 months ago by neel

I will make corrections to asn's branch by merging asn's changes into my branch and I will fix the issues myself.

I will also add a test.

comment:31 Changed 4 months ago by neel

My old PR has asn's commit from his PR, as well as another commit for .

I did not include a test, but he reason why a test isn't added for add_ed25519_to_dir() is because the similar RSA functions (add_fingerprint_to_dir()) were inside a #define 0 in test_dir.c:

#if 0
  /* Okay, now for the directories. */
  {
    fingerprint_list = smartlist_new();
    crypto_pk_get_fingerprint(pk2, buf, 1);
    add_fingerprint_to_dir(buf, fingerprint_list, 0);
    crypto_pk_get_fingerprint(pk1, buf, 1);
    add_fingerprint_to_dir(buf, fingerprint_list, 0);
  }

#endif /* 0 */

and wouldn't have run in the tests.

My old PR is used for these changes: https://github.com/torproject/tor/pull/682

comment:32 Changed 4 months ago by neel

Status: needs_revisionneeds_review

Passes CI. Setting as needs_review.

comment:33 in reply to:  31 Changed 4 months ago by teor

Status: needs_reviewneeds_revision

Replying to teor:

Hi, this patch contains at least one memory safety issue, and at least one crashing bug.

I don't want to merge this patch unless there are unit tests for the new and modified functions. I want some automated checks for the issues that made it past review.

I would also like someone to actually run the code on an authority. If you want to use chutney, the networks/bwfile and torrc_templates/authority-bwfile.tmpl could be copied and modified to use an approved_routers file.

Replying to neel:

I did not include a test, but he reason why a test isn't added for add_ed25519_to_dir() is because the similar RSA functions (add_fingerprint_to_dir()) were inside a #define 0 in test_dir.c:

and wouldn't have run in the tests.

We require unit tests for new code, so that we can find issues in new code.
There were memory safety issues and crashing bugs in this code, and they made it past the review.
So this code needs unit tests.
It also needs to be tested on an authority.

If you would like, you can also write working tests for the old RSA functions.

comment:34 Changed 4 months ago by neel

Status: needs_revisionneeds_review

I have created tests for the ed25519 and RSA functions. However, this did require moving some code from process_descs.c to process_descs.h so it can be used by the test.

comment:35 in reply to:  34 Changed 4 months ago by teor

Replying to neel:

I have created tests for the ed25519 and RSA functions. However, this did require moving some code from process_descs.c to process_descs.h so it can be used by the test.

Thanks!

I'd like to see a test for dirserv_load_fingerprint_file(), because the memory safety bugs were in that function. The existing test for dirserv_read_measured_bandwidth() is a good example of a unit test that reads a file.

You force-pushed your changes over the old branch. When you did that, GitHub deleted my old review comments. I also can't tell which code I have already reviewed, and which code has been changed by your most recent changes. I don't have time to do a full review of your branch this week, so I'll have a look at it next week.

In future, please add commits to the branch, rather than force-pushing your changes. When people review your tor pull requests, please add new commits for any pull request changes. Then reviewers won't have to do full reviews every time you make a change.

If you want to change an existing commit, you can add fixup commits using:

git commit --fixup (existing commit hash)

Then we will squash before we merge,

comment:36 Changed 4 months ago by teor

Status: needs_reviewneeds_revision

comment:37 Changed 4 months ago by neel

Status: needs_revisionneeds_review

I have added a dirserv_load_fingerprint_file() test.

comment:38 Changed 3 months ago by asn

Status: needs_reviewneeds_revision

Thanks for the code neel.

I pointed out a bug in your code in the PR. Also, I think it's naughty to non-trivially edit code in a commit named Add add_ed25519_to_dir() and add_fingerprint_to_dir() tests, ideally that would be its own commit.

Can you please squash your branch, rebase it to master, and make a new PR for it?

Thanks! :)

comment:39 Changed 3 months ago by neel

Status: needs_revisionneeds_review

Squashed PR with the bugfix here: https://github.com/torproject/tor/pull/968

comment:40 Changed 3 months ago by asn

Status: needs_reviewneeds_revision

I'm so sorry but in my previous message I meant for you to squash the squash! commits and the commits that edit other commits (like d44ff1c). And also to properly decouple the f7b5e4c test-related changes from behavior-related changes. Sorry for the confusion and for not clarifying properly.

I think this is a complex enough change that I wouldn't want it to merge as a single commit. Can you please chop-up your latest PR into separate commits to make it more clear why all these changes are necessary to achieve the final result? Also perhaps split code-commits from test-commits.

Thanks and sorry for the confusion again.

comment:41 Changed 3 months ago by neel

Status: needs_revisionneeds_review

Sorry for yet another PR, but I have done the requested squashing (for your squash) and separating commits (for f7b5e4c). It is not one big commit like the last PR.

The new PR is here: https://github.com/torproject/tor/pull/970

comment:42 Changed 3 months ago by asn

LGTM!

comment:43 Changed 3 months ago by asn

Status: needs_reviewmerge_ready

comment:44 Changed 3 months ago by teor

Status: merge_readyneeds_revision

Hi, there is at least one major bug in this pull request. I will submit a review on the pull request.

comment:45 Changed 3 months ago by teor

There are two major bugs in this code:

dirserv_get_status_impl() is also called from dirserv_would_reject_router().
But dirserv_would_reject_router() was not updated to check the ed25519 identity key.

A call to dirserv_get_status_impl() is in the wrong place.
The ed25519 key is only checked if there is a KEYPIN_MISMATCH.

Please add some tests for dirserv_router_get_status() and dirserv_would_reject_router() that fail on the current code, but succeed when you fix these bugs.

Does this change fail practracker?
The existing code is already complex, so you should not increase function sizes. Instead, split the new code out into new functions.
I am not sure if you should split files: maybe we should open another ticket, and do that after 0.4.0 stable?

comment:46 Changed 3 months ago by teor

Also, this pull request does not update the man page for the approved routers file.

Embarassingly, there are two entries in the man page for this file:

 DataDirectory/approved-routers

    Only used by authoritative directory servers. This file lists the status of routers by their identity fingerprint. Each line lists a status and a fingerprint separated by whitespace. See your fingerprint file in the DataDirectory for an example line. If the status is !reject then descriptors from the given identity (fingerprint) are rejected by this server. If it is !invalid then descriptors are accepted but marked in the directory as not valid, that is, not recommended.

 DataDirectory/approved-routers

    Authorities only. This file is used to configure which relays are known to be valid, invalid, and so forth.

comment:47 Changed 3 months ago by neel

Status: needs_revisionneeds_review

I have added the requested changes. Setting as needs ewview.

comment:48 Changed 2 months ago by nickm

Milestone: Tor: 0.4.1.x-finalTor: 0.4.2.x-final

comment:49 Changed 8 weeks ago by teor

Before we merge, we need to test that this code works. So we should write a chutney test for the approved-routers file, and run it with our other chutney tests in tor's CI. (And chutney's CI.) See #29828.

We should also test on a public authority after we merge this feature. (#30638.)

We're also missing a data directory file containing the base64-encoded ed25519 public key. I'll open a child ticket for that file.

comment:50 Changed 8 weeks ago by teor

I did a review on this code.

Thanks for the improvements and fixes.
But this code still contains quite a few logic errors and memory safety issues.

Here's how you can help us do faster reviews of your code:

  • Don't force-push. When you force-push, we have to review the whole branch again.
  • Instead, add new commits that fix the issues from the review.
  • For each comment in the review, reply with the commit hash of the new commit that fixes the issue.

comment:51 Changed 8 weeks ago by teor

Status: needs_reviewneeds_revision

comment:52 Changed 8 weeks ago by neel

Status: needs_revisionneeds_review

I have made the requested changes I could and pushed them.

I had to include one merge as CI wouldn't run as GitHub said my branch conflicts with master. Sorry about that.

Also, I have many commits but most of them are fixup commits so they should be easy to squash.

comment:53 Changed 8 weeks ago by teor

Hi, here's how you can help us review these changes:

For each comment in the review, reply with the commit hash of the new commit that fixes the issue.

comment:54 Changed 7 weeks ago by neel

I have done so. Sorry if I took long to respond.

Could you please review this?

comment:55 Changed 7 weeks ago by teor

I don't have time to review the changes this week, but maybe asn does.

We will need to implement a lot of the child tickets before we merge this code: #30644, #30677, #30691, and #30692.

I would also be useful to have #29828 and #30642.

comment:56 Changed 6 weeks ago by teor

Reviewer: asnteor

asn asked me to take over review for this ticket.

comment:57 Changed 6 weeks ago by neel

I am using the same PR for the child tickets. I have added #30691 to the same branch, and will also add #30644, #30677, and #30692.

I have a copy of the pre-child tickets branch on GitHub as well.

comment:58 Changed 6 weeks ago by teor

Status: needs_reviewneeds_revision

Let me know when the child tickets are all done, and I'll do a review.

Some of the child tickets are independent, and we can review them separately, I'm happy to make pull requests once I see the code.

comment:59 Changed 5 weeks ago by neel

Status: needs_revisionneeds_review

I believe you (teor) wanted #30644 as a separate branch.

I had to create two new PRs:

https://github.com/torproject/tor/pull/1124 with #22029, #30677, #30691, and #30692.

https://github.com/torproject/tor/pull/1125 for #30644 only.

I'm very sorry for new PRs. The only other option is deleting commits and force pushes which you asked me to avoid.

They are based on the same branches as the old PR 970.

comment:60 Changed 5 weeks ago by neel

Also, the commit hashes for the previous bugs (pre-30644) are the same.

comment:62 Changed 5 weeks ago by neel

The new PR is on a separate branch

comment:63 Changed 5 weeks ago by teor

Thanks for these changes.

I'm going to review this PR, because it contains all the comments:
https://github.com/torproject/tor/pull/970

Then we can merge this PR:
https://github.com/torproject/tor/pull/1124

comment:64 Changed 5 weeks ago by teor

Looks like we can't split the branch for #30644, sorry!
Let's go back to putting #30644 on https://github.com/torproject/tor/pull/970
PR 970 has all the code review comments, so it is the easiest branch for me to review.

We should still do #30642 in a different branch, because it should be independent of all this new code,

comment:65 Changed 4 weeks ago by neel

I have added the commits to PR#970.

comment:66 Changed 4 weeks ago by neel

What's the status of the code review for the PR? I added it to GitHub here: https://github.com/torproject/tor/pull/970 (Same PR as usual)

comment:67 in reply to:  66 Changed 4 weeks ago by teor

Replying to neel:

What's the status of the code review for the PR? I added it to GitHub here: https://github.com/torproject/tor/pull/970 (Same PR as usual)

Code reviews are usually done within a week or two after the code is ready.
This branch was ready 4 days ago, 2 of those days were weekend days.

Since it's a complex branch, which I want to split for merging, it might take a little longer.

Note: See TracTickets for help on using tickets.