Opened 6 years ago

Closed 4 years ago

#8961 closed enhancement (implemented)

src/or/replaycache.c hashes entries with SHA-1

Reported by: rransom Owned by:
Priority: Medium Milestone: Tor: 0.2.8.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-hs, easy
Cc: Actual Points:
Parent ID: Points: small
Reviewer: Sponsor:

Description

Tor is supposed to be moving away from SHA-1, and the replay-detection cache can be migrated and protected against hash flooding at the same time (see also #4900) without a protocol change. Just add and use a crypto_digest_local function which prepends a random bytestring (either 16 bytes or a full hash block), then applies either SHA-256 (if Tor was compiled for a 32-bit architecture) or SHA-512 (if Tor was compiled for a 64-bit architecture), then returns the first 160 bits.

Child Tickets

Change History (9)

comment:1 Changed 6 years ago by nickm

Keywords: tor-hs added
Milestone: Tor: 0.2.5.x-final
Priority: minornormal

comment:2 Changed 6 years ago by nickm

Milestone: Tor: 0.2.5.x-finalTor: 0.2.???

comment:3 Changed 4 years ago by dgoulet

Keywords: easy added
Points: small
Type: defectenhancement

comment:4 Changed 4 years ago by gtank

Severity: Normal
Status: newneeds_review

Tried writing this in two ways; one less invasive and the other more so. The small one (https://github.com/gtank/tor/tree/8961-small) just calls openssl SHA512. The big one (https://github.com/gtank/tor/tree/8961-big) adds SHA512 support throughout src/common/crypto.c.

Neither prepends random bytes- I'm unclear if the attacks discussed in #4900 apply to cryptographic hashes. If they do, either of these could be easily modified to take advantage of the existing siphash key.

comment:5 Changed 4 years ago by nickm

Milestone: Tor: 0.2.???Tor: 0.2.8.x-final

should look at this in 0.2.8

comment:6 in reply to:  4 ; Changed 4 years ago by teor

Replying to gtank:

Tried writing this in two ways; one less invasive and the other more so. The small one (https://github.com/gtank/tor/tree/8961-small) just calls openssl SHA512. The big one (https://github.com/gtank/tor/tree/8961-big) adds SHA512 support throughout src/common/crypto.c.

Thanks for the patch, it looks good, but I'm not sure about the original approach suggested in the ticket:
(I am sorry, I don't want you to feel like you wasted your time.)

  • why do 32-bit platforms get less protection?
  • why not switch to using digest256map_t? (I think it's new since this ticket was created)

Then there's no truncation, no need to prepend a random value, and the patch is nice and small. (digestmaps already uses a random-keyed siphash internally, so an attacker would have to get an exact SHA256 match.)

I'd also take a patch for SHA512 support throughout src/common/crypto.c as a feature in another ticket. I've created #17663 to track adding SHA512 support. And I'll add some feedback there.

Do you think you could write unit tests?

Neither prepends random bytes- I'm unclear if the attacks discussed in #4900 apply to cryptographic hashes. If they do, either of these could be easily modified to take advantage of the existing siphash key.

Yes, the attacks do apply to cryptographic hashes, but I'm not sure if they're feasible at 160 bits:

  • the attacker knows the hash (SHA256 or SHA512)
  • they know that we only use the first 160 bits
  • they choose a 160-bit value to target for O(N) performance
  • they keep hashing random values, sending each one that truncates to that 160-bit value to the victim

Prepending a large enough random secret prevents this attack, because the attacker no longer knows the hashed output value.

comment:7 in reply to:  6 Changed 4 years ago by teor

Replying to teor:

Do you think you could write unit tests?

Oops, there are unit tests.

comment:8 Changed 4 years ago by teor

Please see my branch feature8961-replaycache-sha256 at https://github.com/teor2345/tor.git

It switches the replaycache to digest256map_t, and adds unit tests which check that two different buffers don't have the same hash.

comment:9 Changed 4 years ago by nickm

Resolution: implemented
Status: needs_reviewclosed

lgtm ; merged!

Note: See TracTickets for help on using tickets.