Opened 6 years ago

Last modified 21 months ago

#7869 needs_revision defect

ntor-onion-key is padded with an equal sign

Reported by: rransom Owned by: Jigsaw52
Priority: Low Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-relay, intro, review-group-18
Cc: andrea, catalyst Actual Points:
Parent ID: Points:
Reviewer: catalyst, nickm Sponsor: Sponsor3-can

Description

Replying to sonu:

ntor-onion-key Od2Sj3UXFyDjwESLXk6fhatqW9z/oBL/vAKJ+tbDqUU=

The unnecessary “=” at the end of that string needs to go away now, or every Tor client will have to download a thousand or so of them every week forever.

Child Tickets

Change History (34)

comment:1 Changed 6 years ago by nickm_mobile

I would have thought that it would make no difference after compression, assuming you're fetching more than a few mds at once.

comment:2 Changed 6 years ago by nickm

Keywords: tor-relay added
Priority: blockernormal

By the numbers, I think this is a less critical issue than you think. Even uncompressed, this is on average a 0.23 percent (that is, less than a quarter of a percent) overhead on each microdescriptor. Compressed, it's 0.12% overhead or less once you're fetching a reasonable number of microdescriptors. A quarter of a percentage point of waste is just not a blocker.

That said, it *is* an easy fix to make the clients and servers not require that =, in case we want to omit it in the future for some reason.

comment:3 Changed 6 years ago by nickm

Status: newneeds_review

bug7869 makes the = optional, I think. Haven't tested it on a testing network yet, so I don't want to merge it till then.

comment:4 Changed 6 years ago by arma

Taking out a character which has no effect (other than bloating things) sounds like a win to me.

Unless the impact on other parsing tools will be so high that we worry they'll all give up or something I guess.

comment:5 Changed 6 years ago by nickm

Milestone: Tor: 0.2.4.x-finalTor: unspecified
Priority: normalminor
Status: needs_reviewaccepted

Merged the code "bug7869" -- now the = sign is optional. We'll need a pair of subsequent patches -- one to remove it from router descriptors and one to remove it from the consensus directory. We should do this once nobody (or next to nobody) is running the 0.2.4.7-alpha-dev versions that require the = sign. This will require a new consensus method. It'll be a couple of hours work, and let us save something less than a quarter of a percent in microdesc space. Now that clients can accept either format, not a huge issue.

comment:6 Changed 3 years ago by arma

Owner: nickm deleted
Severity: Normal
Status: acceptedassigned

Tor 0.2.4.7-alpha is long gone.

So if somebody wants to do up a patch here, now's a fine time.

Nick, I'm going to take the liberty of un-owner-ing you on this one.

It is a good bite-sized ticket for somebody who wants to get involved in Tor coding.

comment:7 Changed 3 years ago by arma

Status: assignednew

comment:8 Changed 3 years ago by teor

Keywords: easy intro added
Milestone: Tor: unspecifiedTor: 0.2.???

comment:9 Changed 3 years ago by teor

Milestone: Tor: 0.2.???Tor: 0.3.???

Milestone renamed

comment:10 Changed 2 years ago by nickm

Keywords: tor-03-unspecified-201612 added
Milestone: Tor: 0.3.???Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:11 Changed 2 years ago by steeve149

Owner: set to steeve149
Status: newassigned

comment:12 Changed 2 years ago by steeve149

Hey guys, this is my first patch and I'd really appreciate some guidance, where exactly are the route descriptors and the consensus directory? Additionally, what area of the documentation should I be looking at to answer questions like this on my own in the future?

comment:13 Changed 2 years ago by nickm

Router descriptors and consensus directories and other document formats are all described in dir-spec.txt, in the torspec git repository at https://gitweb.torproject.org/torspec.git .

In Tor, they're parsed in routerparse.c and encoded in router.c and dirvote.c.

The work-in-progress "torguts" documentation is a good place to start for finding your way around Tor: https://people.torproject.org/~nickm/tor-auto/internal/

And you can find descriptions of modules and functions either in the source, or indexed via doxygen at https://people.torproject.org/~nickm/tor-auto/doxygen/

You can find other information on getting started in the doc/HACKING subdirectory of the Tor source tree.

comment:14 in reply to:  13 Changed 2 years ago by steeve149

Replying to nickm:
Thanks for the reply, the resources you provided are very useful!

I can't seem to find the string mentioned in the ticket in any of the files you mentioned. Additionally, I searched the project using grep and didn't find the offending string anywhere. I did, however, find some places where a different string with the same pattern was used (ie

ntor-onion-key somekeyfollowedby=

).

Do we want to change these as well or just the exact string from the ticket? If not, this may be something that's already been resolved.

Thanks again, please let me know if there's anything I've missed.

grep command for reference:

grep -rnw '.' -e "ntor-onion-key Od2Sj3UXFyDjwESLXk6fhatqW9z/oBL/vAKJ+tbDqUU="

Last edited 2 years ago by steeve149 (previous) (diff)

comment:15 Changed 2 years ago by Jigsaw52

I tried to fix this. Here is my code: https://github.com/Jigsaw52/tor/tree/remove-padding-fix-7869

While fixing this issue, I noticed that the function curve25519_public_to_base64 does not behave according to its description. The description says 'Encode <b>pkey</b> as a base64-encoded string, without trailing "=" characters'. However, this function output still had the trailing "=".
I fixed this as well and fixed all the code and tests that used padded keys.

comment:16 Changed 2 years ago by Jigsaw52

Status: assignedneeds_review

comment:17 Changed 2 years ago by Jigsaw52

Owner: changed from steeve149 to Jigsaw52
Status: needs_reviewassigned

comment:18 Changed 2 years ago by Jigsaw52

Status: assignedneeds_review

comment:19 Changed 2 years ago by catalyst

Cc: catalyst added
Milestone: Tor: unspecifiedTor: 0.3.2.x-final
Reviewer: catalyst
Status: needs_reviewneeds_revision

[responding to a ping on IRC]

Thanks for the patch! 0.3.1.x is in feature freeze so I'm putting this in 0.3.2.x for now. (Though it might make it into 0.3.1.x if there is time? It doesn't seem urgent to get into 0.3.1.x but feel free to explain if you disagree.) #21872 means we have nicer macros for statically computing buffer lengths for various encodings, so I think it would be good to use them for this patch. Also I think base64_encode() appends a NUL terminator so we can probably delete the code that separately adds one.

comment:20 Changed 2 years ago by catalyst

I'm sorry, after I looked at the patch while more awake I realized that the NULs were to overwrite the = padding. base64_encode_nopad() seems like it would be a better option, though. I think it's kind of inelegant at the moment and requires that the destination buffer be large enough to hold the padded (and NUL-terminated) encoding, but using it here would eliminate some code duplication.

comment:21 Changed 2 years ago by Jigsaw52

Status: needs_revisionneeds_review

I followed your suggestion to use base64_encode_nopad() and changed the names of the constants to match the pattern used in #21872.

By the way, I found an interesting bug on #21872. If you look closely at the following macros:

#define BASE64_NOPAD_LEN(n) (CEIL_DIV((n) * 4, 3)
#define BASE32_NOPAD_LEN(n) (CEIL_DIV((n) * 8, 5)

#define BASE64_NOPAD_BUFSIZE(n) (BASE64_NOPAD_LEN(n) + 1))
#define BASE32_NOPAD_BUFSIZE(n) (BASE32_NOPAD_LEN(n) + 1))

You will notice that BASE64_NOPAD_LEN and BASE32_NOPAD_LEN are missing the closing parentheses.
Also, BASE64_NOPAD_BUFSIZE and BASE32_NOPAD_BUFSIZE have one extra closing parentheses.
If you use only BASE64_NOPAD_BUFSIZE and BASE32_NOPAD_BUFSIZE everything will be fine as both errors cancel each other out.

I fixed this on my branch and reopened #21872 to post a the fix for the macros.

The branch with all my changes merged into the current master is here: https://github.com/Jigsaw52/tor/tree/remove-padding-fix-7869_squashed

Last edited 2 years ago by Jigsaw52 (previous) (diff)

comment:22 Changed 2 years ago by nickm

Keywords: tor-03-unspecified-201612 removed

Remove an old triaging keyword.

comment:23 Changed 2 years ago by catalyst

Keywords: easy removed

Thanks for the updated patches! We were talking about this ticket on IRC and concluded that it still needs additional work, which I'll try to summarize. (nickm, please correct me if I got any of this wrong!) This work includes making a new consensus method, which means updating dir-spec.txt and the consensus method logic in dirvote.c. The sole changes in the new consensus method would relate to padding of base64-encoded ed25519 public keys.

Different directory authorities might create diverging consensus votes if they make different choices about including = padding in ntor-onion-key. This could be considered an existing ambiguity in dir-spec.txt.. The new consensus method would require the absence of padding in ntor-onion-key, while older ones would require its presence. Any changes to test_microdesc.c should not change any of the reference ntor-onion-key lines for the older microdesc formats.

I'm sorry if this is turning out to be more work than you expected. I'm removing the "easy" keyword but keeping "intro" because it's clearly no longer an "easy" task but it does touch a lot of different stuff in a not-too-complicated way and therefore is a good way to get to know the Tor code base better. Please feel free to continue revising your patch, or alternatively some of us could work on it after 0.3.1 is closer to release.

comment:24 Changed 2 years ago by catalyst

Status: needs_reviewneeds_revision

comment:25 Changed 2 years ago by Jigsaw52

Status: needs_revisionneeds_review

I did the required changes and merged again with the current master. Here are the branches:

tor: https://github.com/Jigsaw52/tor/tree/remove-padding-fix-7869_v2_squashed
torspec: https://github.com/Jigsaw52/torspec/tree/remove-padding-fix-7869

comment:26 Changed 2 years ago by teor

Looks decent to me at a quick glance, but I'll leave it to others more familiar with the code to do the full review and test.

comment:27 Changed 2 years ago by Jigsaw52

I just realized the memcpy is unnecessary. I removed it but I cannot test right now. I'll recheck that it compiles and the tests pass later.

Last edited 2 years ago by Jigsaw52 (previous) (diff)

comment:28 Changed 2 years ago by Jigsaw52

I've tested it now and it seems to work fine without the memcpy.

comment:29 Changed 2 years ago by nickm

Keywords: review-group-18 added

comment:30 Changed 2 years ago by catalyst

Thanks for the updated patches, and sorry about the delay. I'll comment on the torspec changes first.

The patch to dir-spec.txt looks good. It could possibly be more specific about referring to the microdescriptors rather than router descriptors (where I think we should still allow optional padding because they're self-signed).

There are a few more places that need updated text about ntor-onion-key:

  • Section 3.3 (Computing microdescriptors) should mention that prior to consensus method 27, = padding is required, and the padding must be absent in consensus method 27 and later.
  • Section 3.8.1 (Forward compatibility) should get an additional line for "27".

There might be other places I missed; please let me know if you find others!

comment:31 Changed 2 years ago by nickm

Reviewer: catalystcatalyst, nickm

comment:32 Changed 2 years ago by nickm

Status: needs_reviewneeds_revision

Additionally:

  • I'm concerned about test coverage. Has anyone checked?
  • curve25519_public_to_base64 seems to have gotten a lot longer than before. Maybe there should be a way to pass the no-padding flag downward to the base64_encode function. Or maybe curve25519_public_to_base64_nopad() should be a separate function? It seems that nearly all callers of curve25519_public_to_base64() use the no-padding variant, and this patch would be much simpler without having an extra argument added.
  • It doesn't seem that authorities actually advertise or allow support for MIN_METHOD_FOR_UNPADDED_NTOR_KEY. See MAX_SUPPORTED_CONSENSUS_METHOD and its users for the necessary changes.

comment:33 Changed 23 months ago by catalyst

Sponsor: Sponsor3-can

comment:34 Changed 21 months ago by nickm

Milestone: Tor: 0.3.2.x-finalTor: unspecified

Mark some needs_revision tickets as unspecified. If/when the revisions happen, they can go back into a live milestone.

Note: See TracTickets for help on using tickets.