Opened 2 years ago

Closed 2 years ago

#26228 closed defect (fixed)

Clarify/determine specification for padding bytes, (formerly also PADDING cell)

Reported by: dmr Owned by: dmr
Priority: Medium Milestone: Tor: 0.3.5.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-spec, prop295-assigned-sponsor-v
Cc: nickm, isis, arma, teor, atagar Actual Points:
Parent ID: #26869 Points:
Reviewer: nickm Sponsor: SponsorV

Description (last modified by dmr)

EDIT: strikethrough content below is now covered in #26870 instead

Background

I was trying to interpret the tor-spec for padding bytes, and ending up asking nickm for some clarification over IRC.
nickm suggested most of the cc'd for the ticket - I added atagar, too.

Unclear areas

Here are the points that need clarification / specification:

Discussion: padding bytes

For the padding bytes that are not part of PADDING cells, nickm offered the following as a non-exhaustive set of possible forward-compatible options:

  • "the [padding] bytes SHOULD be zero, and that implementations MUST ignore them"
  • "The first 8 padding bytes MUST be zero; all subsequent padding bytes SHOULD be randomized. Implementations MUST ignore padding bytes"
  • "All padding bytes should be randomized; implemenations MUST ignore unrecognized padding bytes"

... and mentioned that "[he doesn't] know enough of the argument in favor of randomization to have a very strong preference"

Inconsistency: PADDING cell payload

(see bullet above)

These references highlight the inconsistency:

[1] PADDING: Payload is unused. per sec 3 "Cell Packet format".
implies 0 bytes of payload, so the rest should be padded per that section
[2] The contents of a PADDING, VPADDING, or DROP cell SHOULD be chosen randomly, and MUST be ignored. per sec 7.2 "Link padding".
implies the payload of a PADDING cell actually is the rest of the size of the cell, and that it SHOULD be chosen randomly

The PADDING cells were mentioned in IRC but not discussed.
I think a simple change to make the spec consistent between the two sections would be this:
PADDING: Payload contains random data. (See Sec 7.2)

However, given the other points here, is that correct?

Child Tickets

Change History (20)

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

Replying to dmr:

Background

I was trying to interpret the tor-spec for padding bytes, and ending up asking nickm for some clarification over IRC.

Discussion: padding bytes

For the padding bytes that are not part of PADDING cells, nickm offered the following as a non-exhaustive set of possible forward-compatible options:

  • "the [padding] bytes SHOULD be zero, and that implementations MUST ignore them"
  • "The first 8 padding bytes MUST be zero; all subsequent padding bytes SHOULD be randomized. Implementations MUST ignore padding bytes"

I think this is a good option, because it balances the advantages of randomised payloads vs forwards compatibility,

Here's how adding a new field would work in practice:

  • the first N bytes of padding become the new "number of items" field (N <= 8)
  • the number of items determines the length of the new payload fields
  • the rest of the cell remains padding, with 8 bytes of zeroes followed by random bytes
  • "All padding bytes should be randomized; implemenations MUST ignore unrecognized padding bytes"

... and mentioned that "[he doesn't] know enough of the argument in favor of randomization to have a very strong preference"

Neither do I, but I remember Isis saying that it was ok to just have zero bytes. But I can't remember why.

Inconsistency: PADDING cell payload

(see bullet above)

These references highlight the inconsistency:

[1] PADDING: Payload is unused. per sec 3 "Cell Packet format".

implies 0 bytes of payload, so the rest should be padded per that section

[2] The contents of a PADDING, VPADDING, or DROP cell SHOULD be chosen randomly, and MUST be ignored. per sec 7.2 "Link padding".

implies the payload of a PADDING cell actually is the rest of the size of the cell, and that it SHOULD be chosen randomly

Unless the contents of a cell include payload and padding.

The PADDING cells were mentioned in IRC but not discussed.
I think a simple change to make the spec consistent between the two sections would be this:

PADDING: Payload contains random data. (See Sec 7.2)

However, given the other points here, is that correct?

No, the payload of a cell is the data that an implementation SHOULD parse. Calling the [V]PADDING and DROP content a "payload" adds to the confusion, because implementations SHOULD NOT parse the content of these cells. (It's meaningless.)

Instead, let's say that these cells have zero-length payloads, and then define padding bytes consistently.

comment:2 Changed 2 years ago by dmr

Inconsistency: PADDING cell payload

Responding on the PADDING cells / family. I don't think I can further add to the design discussion on the padding portion of the other cells. (I now feel like I might have mixed two independent topics into a single ticket. Oops. They still need to roughly not conflict with each other, though.)

I don't want to get pedantic here, but the terminology is a bit confusing throughout.
I'm looking to make it easier to understand (and thus implement).

Unless the contents of a cell include payload and padding.

Thanks for pointing that out! I think we should make the meaning of "contents" here clearer. That's what tripped me up and seems to be the biggest point of misunderstanding for me.

Right now, the spec's terminology mixes a bit between contents, payload, and padding. It's it bit hard to figure out what is what.

Since "contents" is a pretty general term, and is used in the spec in different scopes (along with the verb "contains" which often implies contents), it might be better for section 7.2 to explicitly say what SHOULD be randomized.

No, the payload of a cell is the data that an implementation SHOULD parse. Calling the [V]PADDING and DROP content a "payload" adds to the confusion, because implementations SHOULD NOT parse the content of these cells. (It's meaningless.)

I agree about adding to the confusion. I think some amount of confusion will remain in the spec, because of how "payload" is introduced (see bit below). In the RELAY_DROP case, for instance, the Data is probably the "contents" that section 7.2 refers to.

So overall, again, I think it's probably best to explicitly say what fields SHOULD be randomized.

I'm happy to write a patch for this if you think that approach is best. Please let me know!

English is hard (feel free to skip over this, or read for additional details)

Unfortunately the word "contents" could be interpreted as any of the following:

  • payload only
  • padding only
  • payload and padding
  • payload, padding, and CircID (for [V]PADDING cells)

Instead, let's say that these cells have zero-length payloads, and then define padding bytes consistently.

I think that would be harder in practice, based on the way "Payload" is introduced, which makes it a bit confusing already.

Payload (padded with 0 bytes) is defined to be [PAYLOAD_LEN bytes] in fixed-width cells or Payload to be [Length bytes] in the variable-length cells.

Note that in the latter case, the Payload bytes of a VPADDING cell is exactly what teor said shouldn't be considered payload: padding.

It gets a bit more confusing when considering RELAY_DROP cells, which have the fixed-width cell "layer" of payload, and within that, the Data of the RELAY_DROP cell.

So overall, I think the easiest thing is to define what SHOULD be randomized for each of the cell types, in the context of section 7.2.

comment:3 Changed 2 years ago by arma

My preference would be for padding cells to have a 0 byte payload currently, and then we randomize the non payload portions of relay cells like we (sometimes) say we do.

Maybe I'm missing something, but I don't understand why we'd want to do a hybrid "8 bytes of 0's and then random after that" model for the non payload portions of the relay cells.

As a concrete example, see proposal 289 for a case where we will want the non payload part of the relay data cell to be random (even if it's only one byte).

comment:4 Changed 2 years ago by dgoulet

Cc: dgoulet removed
Milestone: Tor: unspecified

comment:5 Changed 2 years ago by nickm

I'd currently suggest the following:

Let's document what we do now in the spec (SHOULD set to zero, MUST ignore) and have a proposal if we want to do something else in the future.

comment:6 in reply to:  5 ; Changed 2 years ago by dmr

Owner: set to dmr
Status: newassigned

Replying to nickm:

I'd currently suggest the following:

Let's document what we do now in the spec (SHOULD set to zero, MUST ignore) and have a proposal if we want to do something else in the future.

Assigning to self. I'll take care of the patch above and note anything left for the ticket / other tickets.
To clarify: I won't be writing said proposal for randomness / extent thereof.

comment:7 in reply to:  6 Changed 2 years ago by dmr

Status: assignedneeds_review

Replying to dmr:

Assigning to self. I'll take care of the patch above [...]

PR here:
https://github.com/torproject/torspec/pull/28
branch head 7b1a76c734e186e50858de52675c50468bd8306a

[...] and note anything left for the ticket / other tickets.

I'm going to file another ticket (or tickets) for anything remaining. Feel free to treat the above PR as the only changes under the scope of this ticket, and close this ticket when the PR merged.

comment:8 Changed 2 years ago by teor

Milestone: Tor: unspecifiedTor: 0.3.5.x-final

comment:9 in reply to:  description Changed 2 years ago by dmr

Description: modified (diff)
Summary: Clarify/determine specification for padding bytes, PADDING cellClarify/determine specification for padding bytes, (formerly also PADDING cell)

Replying to dmr:

I'm going to file another ticket (or tickets) for anything remaining. Feel free to treat the above PR as the only changes under the scope of this ticket, and close this ticket when the PR merged.

I've edited the description with strikethrough to clarify what is under the scope of this ticket.
I've edited the title, too - would've used strikethrough if it supported that.

Those portions of the ticket description are covered instead by ticket #26870. (See that ticket's description for the non-strikethrough version of its scope.)

It's also worth reiterating that the patch here doesn't resolve these - it may actually make things a bit less consistent in the interim.
I tried to follow the feedback in this ticket for the patch, aside from addressing the apparent inconsistency for [V]PADDING/DROP cells.

comment:10 Changed 2 years ago by teor

Hi dmr,

Thanks for this patch. I like your changes.

Please see my branch 26228-padding-bytes on https://github.com/teor2345/torspec.git , which also fixes #26870.

If you're happy with my changes, please flip this ticket to merge_ready.

comment:11 Changed 2 years ago by teor

Parent ID: #26869

comment:12 Changed 2 years ago by teor

Status: needs_reviewneeds_revision

Oops. VERSIONS cells can't have (more than 1 byte of) random padding, because it will be interpreted as an extra version.

All the other variable-length cells can have extra bytes of padding, because their formats contain an internal length (VPADDING is a degenerate case, it has Length bytes of padding). We should explicitly say that these bytes MUST be ignored.

All other fixed-length cells can have extra bytes of padding. If we make the padding random, we won't be able to extend the cell formats as easily. (With zero padding, we can extend a cell format by calling some of the remaining zero bytes a "number of extensions" or "flags that default to zero" field.)

comment:13 Changed 2 years ago by teor

Actually, we should distinguish between padding relay cells, which need randomness because they are relayed, and link cells, which don't need randomness because:
a) they don't have any digests, so randomisation doesn't gain us anything
b) TLS should protect their payloads from modification

comment:14 in reply to:  12 Changed 2 years ago by dmr

Replying to teor:

Oops. VERSIONS cells can't have (more than 1 byte of) random padding, because it will be interpreted as an extra version.

Actually, well-formed VERSIONS cells can't have any (fully) random padding.

The spec says:

Either party MUST close the connection if the versions cell is not well-formed (for example, if it contains an odd number of bytes).

It's unclear in the spec if you can pad VERSIONS cells by repeating (pairs of) version bytes. The algorithms described in the spec make it sound possible, but "not well-formed" is a bit loosely defined.

comment:15 in reply to:  13 ; Changed 2 years ago by teor

Status: needs_revisionneeds_review

Replying to teor:

Actually, we should distinguish between padding relay cells, which need randomness because they are relayed, and link cells, which don't need randomness because:
a) they don't have any digests, so randomisation doesn't gain us anything
b) TLS should protect their payloads from modification

I made this change in the spec, and included the relay cell padding randomisation from #26871.

Replying to dmr:

Replying to teor:

Oops. VERSIONS cells can't have (more than 1 byte of) random padding, because it will be interpreted as an extra version.

Actually, well-formed VERSIONS cells can't have any (fully) random padding.

The spec says:

Either party MUST close the connection if the versions cell is not well-formed (for example, if it contains an odd number of bytes).

Thanks!

It's unclear in the spec if you can pad VERSIONS cells by repeating (pairs of) version bytes. The algorithms described in the spec make it sound possible, but "not well-formed" is a bit loosely defined.

The implementation would interpret padding as extra versions, so let's ban it.

Please see my branch 26228-padding-bytes on ​https://github.com/teor2345/torspec.git , which also fixes #26870 and contains the spec for #26871.

comment:16 in reply to:  15 Changed 2 years ago by dmr

Replying to teor:

Please see my branch 26228-padding-bytes on ​https://github.com/teor2345/torspec.git , which also fixes #26870 and contains the spec for #26871.

Now tracking all of #26228, #26870, #26871 in this pull request:
https://github.com/torproject/torspec/pull/28

(teor, I pushed your branch's changes into that PR)

EDIT: only the tor-spec part of #26871 is tracked here.

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

comment:17 Changed 2 years ago by asn

Reviewer: nickm

comment:18 Changed 2 years ago by teor

Keywords: prop295-assigned-sponsor-v added
Sponsor: SponsorV

I think all prop#295 tickets are sponsor V.

comment:19 Changed 2 years ago by nickm

I've squashed and merged the spec branch; please close this ticket if there is no more to do here.

comment:20 Changed 2 years ago by teor

Resolution: fixed
Status: needs_reviewclosed

Thanks, we'll deal with the implementation in #26871.

Note: See TracTickets for help on using tickets.