[tor-bugs] #22948 [Core Tor/Tor]: Padding, Keepalive and Drop cells should have random payloads

[Tor Bug Tracker & Wiki]

#22948: Padding, Keepalive and Drop cells should have random payloads
--------------------------+------------------------------------
 Reporter:  teor          |          Owner:
     Type:  defect        |         Status:  new
 Priority:  Medium        |      Milestone:  Tor: 0.3.2.x-final
Component:  Core Tor/Tor  |        Version:
 Severity:  Normal        |     Resolution:
 Keywords:  tor-spec      |  Actual Points:
Parent ID:  #18856        |         Points:  0.5
 Reviewer:                |        Sponsor:
--------------------------+------------------------------------
Changes (by isis):

 * keywords:  tor-spec, security => tor-spec
 * milestone:  Tor: 0.3.1.x-final => Tor: 0.3.2.x-final


Comment:

 Replying to [comment:7 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 [https://xkcd.com/221/ 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.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/22948#comment:8>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online