Opened 2 months ago

Closed 3 weeks ago

#27112 closed enhancement (user disappeared)

Decouple payload processing from pop/unpack + tune abstraction layers

Reported by: dmr Owned by: dmr
Priority: Medium Milestone:
Component: Core Tor/Stem Version:
Severity: Normal Keywords: client
Cc: teor, atagar Actual Points:
Parent ID: Points:
Reviewer: atagar Sponsor:

Description

A few goals here:

  • allow RELAY cells to be unpacked / popped without error, and passed to another level for decryption
  • put the encryption/decryption logic in cell.py, but require the crypto state be managed in Connection/Circuit/Stream layers

Child Tickets

Change History (13)

comment:1 Changed 2 months ago by dmr

Reviewer: atagar
Status: assignedneeds_review

Here's my WIP changes PR:
https://github.com/torproject/stem/pull/8
branch head e02cf0edb1292f67c87df95c7a406e5f94c1e7a8

I'd say it's mergeable - it's well-tested and I've weeded out a few failures I had in it.

Along with changes to stem.client functional code, you'll see a tiny bit of exception/docstring/etc. cleanup.

This should all be fairly well explained in commit messages, but feel free to ask any questions!

comment:2 Changed 2 months ago by dmr

For the review, I thought it might help to indicate where I plan to go in the near future.

Another method I want to define at the Cell level is check_digest() to be used for decryption, to correspond with the algorithm specified in section 6.1 (spec reference).

I further want to define encrypt() and decrypt() methods at the Cell level, to make everything much more streamlined. While technically misnomers, these would each do the auxiliary functionality, too.

So...
In addition to actual encryption, encrypt() would:

  • apply the digest (see existing apply_digest())
  • return a RawRelayCell

And...
In addition to actual decryption, decrypt() would:

  • check 'recognized'
  • check the digest (via NYI check_digest())
  • return a RawRelayCell if still encrypted, or an unencrypted/unpacked RELAY Cell if fully decrypted/recognized

(The above is an oversimplification, but I hope it helps illustrate my thoughts.)

My commits are also a bit forward-looking for a few other things. You can see some early structure to make it possible to:

  • centralize ORPort reads/sends (demux/mux)
  • implement RelayCell subclasses (e.g. parsing/packing of decrypted body)
  • handle RELAY_EARLY similarly with a lot of code reuse after a mild bit of refactoring

It's all still in a bit of flux, and I don't seem to be able to fully decouple my commits into entirely 1 specific goal - overall they're working toward a collective vision.

Next-steps summary:

  1. implement Cell check_digest()
  2. implement Cell encrypt()
  3. implement Cell decrypt()

4/5(TBD - and in different tickets):

  • centralize ORPort reads/sends (demux/mux)
  • implement RelayCell subclasses (e.g. parsing/packing of decrypted body)

Right now I'm leaning towards RelayCell subclasses for 4.

comment:3 Changed 2 months ago by atagar

Status: needs_reviewneeds_revision

Swapping our ticket status. Dave and I chatted on irc a couple days ago and he's gonna revise this so cells remain immutable.

comment:4 in reply to:  3 Changed 2 months ago by dmr

Status: needs_revisionneeds_review

Replying to atagar:

[...] he's gonna revise this so cells remain immutable.

PR branch updated!
1 commit added, then rebased to current master HEAD and force-pushed. (Everything else the same)

https://github.com/torproject/stem/pull/8
branch head f3f44a2f4572d3535ae6f2ea7f9788450fc61a20

The old revision / base is still available here, in case you want it:
https://github.com/dmr-x/stem/tree/27112-relay-cell-processing-abstraction-old
branch head e02cf0edb1292f67c87df95c7a406e5f94c1e7a8

comment:5 in reply to:  2 Changed 8 weeks ago by dmr

(I'm a few days late in adding a comment for bookkeepings' sake.)

PR branch updated again!
"dropped" the --no-ff merge commit, 9 commits added, then force-pushed. (Everything else the same. This shares a common base of b47ea8edacdff2d4a3644e95af9c40a6c3536a5d, so everything after that is new.)

This adds these from comment 2:

Next-steps summary:

  1. implement Cell check_digest()
  2. implement Cell encrypt()
  3. implement Cell decrypt()

... and a few other things (the commits describe it pretty well)

PR at:
https://github.com/torproject/stem/pull/8
New branch head e8a7599110bd25bd5139c691a634ba1ab2e3449e

Old revs / bases available here:

comment head branch tree url
1 e02cf0edb1292f67c87df95c7a406e5f94c1e7a8 https://github.com/dmr-x/stem/tree/27112-relay-cell-processing-abstraction-old
4 f3f44a2f4572d3535ae6f2ea7f9788450fc61a20 https://github.com/dmr-x/stem/tree/27112-relay-cell-processing-abstraction-old-2

comment:6 Changed 7 weeks ago by atagar

Hi Dave, sorry about the delay! Merged a hybrid of our approaches that does the parts I think we agree on (move cell encryption/decryption into the cell class, and general fixups) - mind taking a peek?

https://gitweb.torproject.org/stem.git/commit/?id=8a1239e

I'd be happy to discuss integration of other parts of your pull request, but honestly I found it made our code pretty tough for me to follow.

comment:7 Changed 7 weeks ago by atagar

Good morning Dave. You dropped off irc so responding to ya here.

01:21 < dmr> hey atagar: w.r.t. 486a8d2e5c4724146d6647b7f69ffbd10adbfc1d
             / 8e83553e578aa0f8819eead434ca7ca26d57d5d9 (combined
             encryption and packing), this probably needs to be undone
             for multi-hop circuits
01:22 < dmr> atagar: and w.r.t. 7d8f1f151d8e2c815e68e0197513f0449a12edd0,
             clients *do* need to check the digest when fully decrypted,
             for 2 reasons: (1) to confirm that we didn't get unlucky
             with 'recognized' == 0; (2) to work against various
             corruption / attacks that would affect the integrity of
             our payload
01:24 < dmr> atagar: finally, I think the new decrypt() will probably
             need to be tweaked back to not trying to construct a
             RelayCell until it is known that the cell is fully
             decrypted (to support multi-hop circuits)
01:27 < dmr> atagar: I'll have to look harder at the changes, but I
             fear that (as you noted in
             8e83553e578aa0f8819eead434ca7ca26d57d5d9), some of the 
             design was done intentionally in a future-looking sense
             for multi-hop circuits and more centralized ORPort
             reads/sends
01:27 < dmr> atagar: so now it seems like ground was lost there
01:28 < dmr> atagar: I do agree, however, that _too much_ was
             factored out (e.g. some of the @staticmethod junk),
             but I was pretty solid with the encrypt() and
             decrypt() interface / methods
01:30 < dmr> atagar: if you glance at my
             5baa2e37728ab50a5132d81225070e097e6bd058, in the
             commit message you'll see an example use of
             decrypt() that I believe suits multi-hop circuits
             very well, as well as centralized ORPort reads
01:34 < dmr> uh, so, I think moving forward I'll try to write
             up a hierarchy / method interface layout (as
             discussed last week) and propose that before any
             further code changes

I think we might be misunderstanding each other, and it boils down to one simple question: When you say 'for multi-hop circuits' which of the following do you mean?

  1. So we can relay. That is to say, be in the middle of the circuit.
  2. So we can make circuits. That is to say, we're the originator of a multi-hop circuit.

If you mean 'a' then yes, much of this is necessary, but that is not our task at present. If the later then I'm unsure why much of this is necessary but quite possible I'm missing something.

(1) to confirm that we didn't get unlucky with 'recognized' == 0;

If we're a client then all cells we receive are decryptable. The 'recognized' field is nothing more than a poor man's 'is this cell still encrypted?' check. This is only relevant if we implement relaying.

(2) to work against various corruption / attacks that would affect the integrity of our payload

As for this part, yup. I'd actually be delighted to merge a targeted, simple patch that implements decryption digests (with tests). I stared at your branch for hours this weekend hoping to integrate that, but honestly I couldn't make heads or tails of this code. The myriad of helpers (especially with names like 'coerce' and 'interpret') made my head spin.

but I was pretty solid with the encrypt() and decrypt() interface / methods

I kept the encrypt/decrypt interfaces the same. The only thing I dropped was...

  1. Implementation of decryption digests. This would be nice to have.
  1. Rearchitecture of our RelayCell class, splitting this up into dozens of helpers. I wasn't a fan of this.

Sorry! I know it sucks to get this kind of pushback on a branch you've worked so hard on.

TL;DR I think is...

  1. I really liked your branche's simplification of Circuit by moving encryption/decryption down into the RelayCell class. That part is now merged.
  1. I also really liked a myriad of small fixes you made (docs and such). Those are also now merged.
  1. I want to merge your decryption digest implementation (there's now a TODO comment in decrypt() about it) but I couldn't make sense of this code.
  1. I do not want to split RelayCell or excessively complicate this class unless there's a very good reason.

Hope that helps!

comment:8 Changed 7 weeks ago by dmr

Status: needs_reviewneeds_revision

Swapping status

comment:9 in reply to:  7 Changed 7 weeks ago by dmr

Sorry again for the delay in my response, and for the verbosity...

I think it's probably best that I step back a bit to explain a bit more of the broader picture as I see it.
The changes in that branch were indeed messy, but I think they did push towards the vision I have. While I don't have the "end design" quite figured out (hence most of the messiness), I think it would help if I clarify at least an intermediate part of my vision. Thereafter, I can respond a bit more specifically to your comments.

I see the following current limitations in stem.client's design:

  1. dropping multiplexed cells or (worse) throwing exceptions when they occur
  2. having unpack()/pop() methods that effectively won't work on the stream of data received from a guard, if there's any RELAY/RELAY_EARLY cells in there
  3. allowing only a single layer of decryption, instead of an arbitrary number of layers
  4. being limited to only a single "actor" that may send/process Cells (related to 1.)

There are more, but the above are the main ones that I was trying to address with this ticket.
I felt my changes took a pretty big step forward towards these (not completed), but I feel the current master has not - mostly taking only some abstraction-layer tuning and small fixes.

I'm not dead-set on any given design, but I hope the following helps explain why I was trending the way I was.

Limitation 1: dropping multiplexed cells or (worse) throwing exceptions when they occur

By this I mean: Tor is multiplexed by nature. Most cell sequences on the wire can be interleaved with others (the spec calls out just a few exceptions).
This should be fairly self-evident by the ability to have multiple circuits and streams open concurrently, but I wanted to call it out explicitly.

This is related to 4. but goes beyond it - any hop on any of our circuits may send a Cell to us - it does not have to be a response in part of a sequence.

The client needs some way to handle this - i.e. to demultiplex.

My proposed solution to this for stem is to centralize ORPort reads - separating that from more specific handlers. A central point (probably a dedicated thread) should be the only thing reading from the ORport socket. Sorting and handling of incoming cells probably will be facilitated by queues (not there yet).
(This ticket doesn't aim to centralize that, but rather take a step towards making that possible.)

Limitation 2: having unpack()/pop() methods that effectively won't work on the stream of data received from a guard, if there's any RELAY/RELAY_EARLY cells in there

Because our Cell.unpack()/Cell.pop() methods will directly create an interpreted RelayCell, from the payload sent over the wire (which, per the spec, is always encrypted), these methods effectively can't be used on incoming bytes that may have a RELAY/RELAY_EARLY cell.
(Said a different way, interpreting an encrypted payload as if it were unencrypted doesn't get us the data we want, and has plenty of potential to throw an exception.)

Since most of a tor client's useful operation involves relayed Cells, these methods in their current form don't quite make sense to me.

The Cell.by_value() lookup method seemed like a natural place to adjust the returned class, but I'm not tied to changing that if you'd suggest another method.

To make these methods more universally useful (e.g. to use Cell.unpack() in whatever solution fixes 1.), my proposed solution for this is to unpack RELAY cells into some intermediate form that allows parsing the payload but not interpreting it. This was the basis for the RawRelayCell.

I'm not tied to RawRelayCell, but I did see it as an interim way to solve this. (I'm still trying to figure out the best hierarchy for RELAY/RELAY_EARLY Cell classes.)

Limitation 3: allowing only a single layer of decryption, instead of an arbitrary number of layers

Right now, the Cell.decrypt() method creates a RelayCell, meaning that it suffers from the same problems as unpack()/pop() does, for use in multi-hop circuits.

We need a way to arbitrarily decrypt the payload without creating a "Exception hazard" (here: RelayCell) automatically. When decrypting, we at least need to parse and look at 'recognized', and per the spec only consider a cell decrypted if we properly also confirm the digest:

If the digest is correct, the cell is considered "recognized" for the purposes of decryption (see section 5.5 above).

Maybe something unclear here is this: any relay in our circuit may send us a Cell, so we can't just assume an encrypted cell is from the final hop - we need to iteratively decrypt until we can tell it is decrypted. Only at that point do we know which relay sent it to us.

RawRelayCell also served that purpose - it was just a Cell container for the payload.
Using this intermediary allowed a fairly nice API for multi-hop decryption, without the consumer needing to know specifics. I just want to point out the example code that I had in a commit message. Here's the main snippet:

      # relay_1 := nearest relay in circuit
      decryption_states = [
        (relay_1, digest_1, decryptor_1),
        (relay_2, digest_2, decryptor_2),
        (relay_3, digest_3, decryptor_3),
      ]
      new_decryption_states = copy.deepcopy(decryption_states)

      from_relay = None
      for i in range(len(new_decryption_states)):
        relay, digest, decryptor = new_decryption_states[i]

        cell, fully_decrypted, digest, decryptor = cell.decrypt(digest, decryptor)
        new_decryption_states[i] = (relay, digest, decryptor)

        if fully_decrypted:
          from_relay = relay
          break

      if from_relay:
        decryption_states = new_decryption_states
      else:
        # handle this, since the cell couldn't be decrypted
        # probably raise Something()
        pass

I don't think we want the Cell.decrypt() method to handle anything more than a layer of decryption. I believe the Circuit should maintain the crypto state, be told whether the cell is fully decrypted, and know what to do if fully decrypted or not.

So if decrypt() doesn't return cell, fully_decrypted, digest, decryptor (where cell is typically a raw cell), I think it should at least return payload, fully_decrypted, digest, decryptor. These are practically the same except the latter is lower-level (arguably leaky abstraction) with an added need to create a Cell from that payload - a step that could be reduced - and likely a static method instead of an instance method. (An instance method, to me, seems more natural.)

In other words, my proposed solution for this is to have decrypt():

  • callable for an abitrary number of encryption layers
  • not cause Exceptions
  • not return an interpreted Cell by default

Limitation 4: being limited to only a single "actor" that may send/process Cells (related to 1.)

All of the stem.client code currently locks the ORPort, sends cells, and receives cells, and releases the lock.
This is related to 1., but different (hopefully I can explain this ok).

Given limitation 1., it's not that bad if only a single actor makes use of stem.client.

But this limitation means that stem.client only allows a single synchronous message stream, and doesn't have good ways to support longer-term streams.

Again, my proposed solution for this is for stem is to centralize ORPort reads, as well as writes.
(This ticket doesn't aim to centralize that, but rather take a step towards making that possible.)

Summary

I'm not tied to any specific solutions, and definitely open to suggestion.
I hope the above at least explains what I'm trying to solve in this ticket.

comment:10 in reply to:  7 Changed 7 weeks ago by dmr

Ok, now onto specific points in your comment.

Replying to atagar:

I think we might be misunderstanding each other, and it boils down to one simple question: When you say 'for multi-hop circuits' which of the following do you mean?

  1. So we can relay. That is to say, be in the middle of the circuit.
  2. So we can make circuits. That is to say, we're the originator of a multi-hop circuit.

If you mean 'a' then yes, much of this is necessary, but that is not our task at present. If the later then I'm unsure why much of this is necessary but quite possible I'm missing something.

I mean 'b', but I do think that the stem.client.cell shouldn't have any limitations in it that prevents 'a'. Any logic that differentiates relay from client should be at another code layer. So I think with the proposed solutions, there isn't a difference here.

(1) to confirm that we didn't get unlucky with 'recognized' == 0;

If we're a client then all cells we receive are decryptable. The 'recognized' field is nothing more than a poor man's 'is this cell still encrypted?' check. This is only relevant if we implement relaying.

(2) to work against various corruption / attacks that would affect the integrity of our payload

As for this part, yup. I'd actually be delighted to merge a targeted, simple patch that implements decryption digests (with tests). I stared at your branch for hours this weekend hoping to integrate that, but honestly I couldn't make heads or tails of this code. The myriad of helpers (especially with names like 'coerce' and 'interpret') made my head spin.

Agreed, it was messy and had a lot of helpers (and naming is hard). I'll try to take a look at adjusting decrypt(). Right now it also don't check 'recognized', which I believe it should do before attempting to create a RelayCell (and per my proposed solutions, not attempt to create a RelayCell).

but I was pretty solid with the encrypt() and decrypt() interface / methods

I kept the encrypt/decrypt interfaces the same. The only thing I dropped was...

I guess I meant the interface holistically.

Hopefully this illustrates some of the differences.

decrypt()

Where Returns Raises Params
branch(RawRelayCell, fully_decrypted bool, CipherContext, HASH)nothing, I believeself (BaseRelayCell), CipherContext, HASH
master(RelayCell, CipherContext, HASH)stem.ProtocolError and anything the RelayCell unpacking or constructor may raise(staticmethod) link_protocol, bytes from ORPort, CipherContext, HASH

For brevity, I won't do the same for encrypt(), but it's similar. (It also only has a single layer of encryption implemented in the branch, although it's fairly easily refactored to BaseRelayCell)

Again, I'm not tied to the specifics here. I do especially think returning fully_decrypted is necessary, and it makes sense to me that this method operate on the same types that it returns a superset of.

  1. Rearchitecture of our RelayCell class, splitting this up into dozens of helpers. I wasn't a fan of this.

Sorry, that was messy and overdone. Some of it I believe helped and was necessary, but other parts arguably didn't add much value, or were placed at the wrong level. (I'm still rethinking how to have a hierarchy for RELAY/RELAY_EARLY Cells.)

Sorry! I know it sucks to get this kind of pushback on a branch you've worked so hard on.

You raise fair points. Mostly I'm just trying to communicate where I'm coming from, and it looks like neither the code nor the commit messages did a good job of this.

  1. I want to merge your decryption digest implementation (there's now a TODO comment in decrypt() about it) but I couldn't make sense of this code.

Good TODO comment - it helps keep track of things.

For posterity's sake: it's a bit more complicated than the example in the comment.

  • the digest is computed using the payload (not the whole packed cell) with 0 in the digest field (hence the pack_payload helper method)
  • self.digest is an int per unpacking (and otherwise would've been coerced by the constructor), but new_digest is still a HASH, so we need to coerce the latter to int to compare (hence the coerce_digest helper method)
  1. I do not want to split RelayCell or excessively complicate this class unless there's a very good reason.

Yep, this was excessive. I hope that my comments help explain at least a bit of what I consider necessary complexity.

Hope that helps!

Likewise, I hope these help!

comment:11 Changed 7 weeks ago by atagar

Limitation 1: dropping multiplexed cells or (worse) throwing exceptions when they occur
...
My proposed solution to this for stem is to centralize ORPort reads - separating that from more specific handlers.

Hi Dave. Gotcha, Tor's control socket is multiplexed to some extent too. General controller interactions are serialized, but asynchronous events can be interweaved with content we receive.

Stem handles this via its stem.control.BaseController class, which wraps our socket and provides thread safe communication through its msg() method.

My plan for ORPorts is to do the same. Like BaseController, our stem.client.Relay class wraps the socket. It, and the Circuit class it's collocated with, is the spot where we'll be implementing all IO. Multiplexing included.

By contrast our Cells are IO agnostic parsers. We'll likely adjust them a bit when we add multiplexing, but I'd expect the bulk of such a patch to be there.

Limitation 2: having unpack()/pop() methods that effectively won't work on the stream of data received from a guard, if there's any RELAY/RELAY_EARLY cells in there

Sorry, read this a few times and still unsure what you mean by 'interpreting' cells. That said, the next bullet is probably more important.

Limitation 3: allowing only a single layer of decryption, instead of an arbitrary number of layers

Ahh! Gotcha. That's definitely something we need to address, though I suspect it won't be overly challenging. First thought is maybe we can extend our new encrypt/decrypt methods to take a series of key/digests. Side stepping digests for simplicity, that is to say...

def encrypt(self, keys):
  if isinstance(keys, list):
    # Encrypt for each relay, last to first...
    #
    #   Circuit: Us => Relay #1 (Guard) => Relay #2 (Middle) => Relay #3 (Exit) => Endpoint
    #     Cell to send:   [Header for relay #1][Encrypted payload for relay #1]
    #     Payload for #1: [Header for relay #2][Encrypted payload for relay #2]
    #     Payload for #2: [Header for relay #3][Encrypted payload for relay #3]
    #     Payload for #3: [Payload for endpoint]

    cell_to_send = self

    for relay_key in reversed(keys):
      cell_to_send = cell_to_send.encrypt(relay_key)

    return cell_to_send
  else:
    # Encrypting for a single hop.

    [ something similar to our present encryption method ]

def decrypt(self, content, keys):
  if isinstance(keys, list):
    decrypted_cell = self

    for relay_key in reversed(keys):
      decrypted_cell.decrypt(relay_key)

      if decrypted_cell.recognized == 0 and [digest check thingy]:
        return decrypted_cell  # cell is now fully decrypted

    raise stem.ProtocolError('Cell received from X couldn't be fully decrypted')
  else:
    # Decrypt for a single hop.

    [ something similar to our present decryption method ]

Just pulling from my ass. No doubt naively ignoring complications, but I'm sure with a little work we can come up with an elegant and functional solution that makes us both happy.

What I'd like from you isn't anticipatory refactoring, but rather a functional prototype that makes multi-hop circuits. Once we have something that works we can iterate on the code, but until then we're both just guessing.

Cheers! -Damian

comment:12 Changed 6 weeks ago by atagar

Hi Dave, just another cross-channel reply since ya dropped off irc again.

what do you think of making a datatype that abstracts away the running key/digest combo?

Yup, it crossed my mind last week that in the end we'd probably end up combining them as a datatype class (similar to protocol versions and such).

comment:13 Changed 3 weeks ago by atagar

Resolution: user disappeared
Status: needs_revisionclosed

Resolving our SoP tickets. If you return and would care to push this forward feel free to reopen.

Note: See TracTickets for help on using tickets.