Opened 21 months ago

Last modified 4 months ago

#22948 assigned defect

Padding, Keepalive and Drop cells should have random payloads

Reported by: teor Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-spec, 034-triage-20180328, 034-removed-20180328
Cc: mikeperry, isis, nickm Actual Points:
Parent ID: Points: 0.5
Reviewer: Sponsor:

Description

tor-spec says:

   Link padding can be created by sending PADDING or VPADDING cells
   along the connection; relay cells of type "DROP" can be used for
   long-range padding.  The contents of a PADDING, VPADDING, or DROP
   cell SHOULD be chosen randomly, and MUST be ignored.

https://gitweb.torproject.org/torspec.git/tree/tor-spec.txt#n1534

But padding cells sent by channelpadding_send_padding_cell_for_callback() and keepalive cells sent by run_connection_housekeeping() have a payload of all zero bytes.

I don't know if this is a security issue or not. It is probably ok, unless Tor has compression enabled on its TLS connections. If compression is enabled, all the padding data size calculations will be wrong.

Child Tickets

TicketStatusOwnerSummaryComponent
#22962acceptednickmClarify the security severity of issues that make denial of service easierCore Tor/Tor
#22963newMake relay integrity digests harder to guess by padding cells with random bytesCore Tor/Tor

Change History (20)

comment:1 Changed 21 months ago by teor

Cc: mikeperry added

comment:2 Changed 21 months ago by teor

Summary: Padding and Keepalive cells should have random payloadsPadding, Keepalive and Drop cells should have random payloads

This issue also affects RELAY_COMMAND_DROP cells.

comment:3 Changed 21 months ago by nickm

FWIW, we always disable TLS compression, since CRIME was discovered.

comment:4 Changed 21 months ago by teor

Milestone: Tor: 0.3.1.x-finalTor: 0.3.2.x-final
Version: Tor: 0.3.1.1-alpha

Then this is probably ok in 0.3.1.

Is there any reason for padding cells to have random payloads?
Does it make it harder for adversaries to decrypt them?
(If so, should we fill every cell with random data rather than zeroes?
Or does that make it harder to add extra fields to cells?)

On the other hand, are we worried that implementations with low quality PRNGs will leak state by doing this?

I suggest we update the spec to say that padding cells should be filled with zero bytes, just like other cells, unless there is some compelling reason to use random bytes.

comment:5 in reply to:  4 Changed 21 months ago by cypherpunks

Replying to teor:

Then this is probably ok in 0.3.1.

Is there any reason for padding cells to have random payloads?
Does it make it harder for adversaries to decrypt them?
(If so, should we fill every cell with random data rather than zeroes?
Or does that make it harder to add extra fields to cells?)

On the other hand, are we worried that implementations with low quality PRNGs will leak state by doing this?

I suggest we update the spec to say that padding cells should be filled with zero bytes, just like other cells, unless there is some compelling reason to use random bytes.

This is not something to decide, permanently, in a rush.

Intuitively, thinking about what (very far future attacks) could happen, rather than what is known to already be possible, random or at least pseudo-random data seems better. And there are simple ways of generating pseudorandom data that is at least better against imaginable future cryptanalysis than all zeroes, which consume very little entropy, like a stream cipher with a random key, repeated hashing, etc.

Last edited 21 months ago by cypherpunks (previous) (diff)

comment:6 in reply to:  4 Changed 21 months ago by arma

Replying to teor:

Is there any reason for padding cells to have random payloads?

Yes, the end-to-end circuit digest includes the payloads of all the cells received, and random payloads are not easy to predict. For example, it would reduce vulnerability to attacks where one side produces a valid digest without actually receiving the cells that it is acknowledging.

comment:7 Changed 21 months ago by teor

Keywords: security added; security-maybe removed
Milestone: Tor: 0.3.2.x-finalTor: 0.3.1.x-final

I don't know how to classify this security issue.
https://trac.torproject.org/projects/tor/wiki/org/teams/NetworkTeam/SecurityPolicy

Is it low severity: "A defense-in-depth mechanism provides less defense-in-depth than it should"?
Or is it high severity: A potential denial of service attack that affects clients and hidden services?
(I split the security policy clarification off into #22962.)

Should we fix it in 0.3.1?
Should we fill all cells with random bytes? (Split off into #22963.)

comment:8 in reply to:  7 ; Changed 20 months ago by isis

Keywords: security removed
Milestone: Tor: 0.3.1.x-finalTor: 0.3.2.x-final

Replying to teor:

I don't know how to classify this security issue.
https://trac.torproject.org/projects/tor/wiki/org/teams/NetworkTeam/SecurityPolicy

Is it low severity: "A defense-in-depth mechanism provides less defense-in-depth than it should"?
Or is it high severity: A potential denial of service attack that affects clients and hidden services?
(I split the security policy clarification off into #22962.)

Should we fix it in 0.3.1?
Should we fill all cells with random bytes? (Split off into #22963.)


If anything, I would say very-low-severity for the "defense-in-depth provides less defense-in-depth than it should", for the reason that arma mentions where it could theoretically be easier to forge the end-to-end MAC on data seen on a circuit.

Wait. Let me think how we use this.

So the defense-in-depth in this case has a lot of assumptions like: if we believe that AES-128 is not breakable in close-to-real-time (we do), and we believe that neither endpoint is victim to any kleptographic attack (we can't defend against that), and we don't believe that an adversary is capable of a SHA-256 second-preimage in any reasonable amount of time (we don't), then the fact that some subset of cells on a circuit have known plaintexts probably doesn't really give you that much of an advantage in terms of forging a MAC that is cumulative over all data seen so far (i.e. H(a || b || c || …) not "chained" like H(… || H(c || H(b || H(a))))). You'd need a second-preimage on SHA-256, so finding x' where H(x) == H(x'). And in either case it's the same thing, so #1

x  = [UNKNOWN_BYTES] || [0x00, …]
x' = [BYTES_YOU_CAN_TWIDDLE_TO_GET_THE_PREIMAGE] || [0x00, …]

versus #2

x  = [UNKNOWN_BYTES] || [RANDOM_BYTES]
x' = [BYTES_YOU_CAN_TWIDDLE] || [THE_SAME_RANDOM_BYTES_OR_SOMETHING_WITH_A_SECOND_PREIMAGE]

So effectively this attack is just as hard (it's still a second-preimage) even if you know some of the bytes. That is, there's no realistic adversary who's going to look at #1 and #2 and be like "Aha, well, I can do #1 because that only requires one preimage, but two preimages, that's impossible!"

Also consider that, for many protocols, the plaintext of some cells to the exit node are potentially something guessable like GET / HTTP/1.1\r\nHost: twitter.com\r\n\r\n (ignoring TLS in that case, but you get the idea), and we've never really assumed there's any significant advantage there. Also technically, all zeroes is random, in the same way that int get_random_number() { return 4; } is a valid PRNG, it's just not really how any sane person would interpret the spec. 😉🤓

All joking aside, there are two ways I could imagine the "I can do one preimage but not two" adversary could be a problem: first, if they can do one preimage, but it takes enough time (let's say a couple minutes for the case of tor's circuits) that they couldn't reasonably do two (and assuming they don't have resources to parallelise). This adversary doesn't make sense to me, because if unbeknownst to the entire world they can do one preimage, I don't see how they're going to have trouble explaining to their boss why they need a second set of the same hardware. The second issue would be a if a client somehow created a circuit which was entirely padding, that is "find a preimage for all zeroes" which, if you know the number of payload bytes sent/received would be trivial and isn't even preimage or cryptographic attack at all: simply hash the same number of zeroes. This, I'd argue is not an issue because you can't have a circuit with all zeroes (that would mean that all kinds of stuff in the handshake would need to be all zeroes, like keys and fingerprints and such). Also what is an adversary going to do with a circuit made entirely of padding for which they've forged a MAC for, if everything in the payload is ignored? "Oh no! I made you ignore some unauthenticated stuff!"

I think I've convinced myself this is not a security issue.

Probably we should do a torspec fix that says something like "SHOULD be chosen randomly, but MAY be all zeroes, and MUST be ignored"?

For the patch, it probably doesn't hurt to use random padding. We should make sure that whatever we do, we're doing the same thing for VPADDING, PADDING, and DROP cells. I'd also want to hear what Nick thinks about future-compatibility w.r.t. adding extra fields if we have random padding.

comment:9 in reply to:  8 Changed 20 months ago by teor

Replying to isis:

...

So the defense-in-depth in this case has a lot of assumptions like: if we believe that AES-128 is not breakable in close-to-real-time (we do), and we believe that neither endpoint is victim to any kleptographic attack (we can't defend against that), and we don't believe that an adversary is capable of a SHA-256 second-preimage in any reasonable amount of time (we don't), then the fact that some subset of cells on a circuit have known plaintexts probably doesn't really give you that much of an advantage in terms of forging a MAC that is cumulative over all data seen so far (i.e. H(a || b || c || …) not "chained" like H(… || H(c || H(b || H(a))))). You'd need a second-preimage on SHA-256, so finding x' where H(x) == H(x').

Unfortunately, Tor still uses SHA1 for its relay cell digests, except for onion service v3 client to service cells, which use SHA3-256.

But I think your reasoning still applies, at least for the next few years.

comment:10 Changed 19 months ago by isis

Cc: isis added

comment:11 in reply to:  8 ; Changed 19 months ago by isis

Cc: nickm added
Owner: set to isis
Status: newaccepted

Replying to isis:

I think I've convinced myself this is not a security issue.

Probably we should do a torspec fix that says something like "SHOULD be chosen randomly, but MAY be all zeroes, and MUST be ignored"?

For the patch, it probably doesn't hurt to use random padding. We should make sure that whatever we do, we're doing the same thing for VPADDING, PADDING, and DROP cells. I'd also want to hear what Nick thinks about future-compatibility w.r.t. adding extra fields if we have random padding.


Any opinions on whether we should go with 1) actually randomise padding, or 2) patch torspec as above? I'm happy to do either.

comment:12 in reply to:  11 Changed 19 months ago by teor

Replying to isis:

Replying to isis:

I think I've convinced myself this is not a security issue.

Probably we should do a torspec fix that says something like "SHOULD be chosen randomly, but MAY be all zeroes, and MUST be ignored"?

For the patch, it probably doesn't hurt to use random padding. We should make sure that whatever we do, we're doing the same thing for VPADDING, PADDING, and DROP cells. I'd also want to hear what Nick thinks about future-compatibility w.r.t. adding extra fields if we have random padding.


Any opinions on whether we should go with 1) actually randomise padding, or 2) patch torspec as above? I'm happy to do either.

1) Randomise padding in cells that will always be empty (VPADDING, PADDING, and DROP)
2) Leave it as zeroes, otherwise, so we can do field upgrades and assume zero values (like the IPv6 RELAY_BEGIN upgrade, where zeroes mean AcceptIPv4, RejectIPv6, PreferIPv4).

comment:13 Changed 19 months ago by nickm

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

comment:14 Changed 14 months ago by nickm

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

Mark a lot of assigned/needs_revision tickets as 0.3.4. If you think this should happen in 0.3.3 instead, just let me know?

comment:15 Changed 12 months ago by nickm

Keywords: 034-triage-20180328 added

comment:16 Changed 12 months ago by nickm

Keywords: 034-removed-20180328 added

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

comment:17 Changed 12 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:18 Changed 11 months ago by atagar

Parent ID: #18856

Dropping parent so I can resolve stem's ticket.

comment:19 in reply to:  4 Changed 10 months ago by cypherpunks

Replying to teor:

Does it make it harder for adversaries to decrypt them?
(If so, should we fill every cell with random data rather than zeroes?

If AES is a perfect PRP, then padding adds no additional protections.

Theoretically, yes. Tor uses AES in CTR mode, which means that known plaintext allows an adversary to discover the keystream. While this alone is not an issue, the fact that Tor initializes CTR with a zero nonce (something I find a little silly) means that the diffusion from the key is reduced. This could, in theory, make a hypothetical future key-recovery attack against AES a little easier to mount against Tor connections.

Assuming the padding is generated with the same CSPRNG as the keystream for link encryption, there will not be a huge benefit. The padding would be something along the lines of:

C_i = E_k(i + 1) ⊕ E_k(i)

Whereas padding with zeros is equivalent to:

C_i = E_k(i)

And regular encryption of plaintext P is:

C_i = P_i ⊕ E_k(i)

For ciphertext C, plaintext P, block cipher E, key k, and counter i.

On the other hand, are we worried that implementations with low quality PRNGs will leak state by doing this?

You would need a really bad PRNG for that to be an issue. As in, one that is so bad that statistical analysis of the ciphertext could lead to key recovery (after all, CTR mode is nothing more than PRNG output being XORed with the plaintext). If we are using something that bad, we have far worse problems.

My personal opinion is that the cells should use random padding, as long as it's cheap.

comment:20 Changed 4 months ago by gaba

Owner: isis deleted
Status: acceptedassigned
Note: See TracTickets for help on using tickets.