If the strlen() of $full_key is greater than 250, the resultant key send to memcached can contain non-safe characters due to the absence of urlencode wrapping $prefix and $bin in dmemcache.inc on line 456.
See below:
if (strlen($full_key) > 250) {
$full_key = $prefix . $bin . '-' . sha1($key);
}
In addition, this logic does not account for the combined prefix being greater than 210 bytes long, which would cause the length of $full_key to be greater than 250 bytes.
Lastly, there is no watchdog support to help administrators determine that their prefix or bin names are too long.
I have a patch that I am putting the finishing touches on right now and will attach to this issue a bit later this morning.
Comment | File | Size | Author |
---|---|---|---|
#13 | memcache-urlencode-key-1613622-13.patch | 3.33 KB | markpavlitski |
#11 | memcache-urlencode-key-1613622-11.patch | 895 bytes | markpavlitski |
#10 | hash.php_.txt | 833 bytes | Jeremy |
#9 | memcache-urlencode-key-1613622-9.patch | 1.1 KB | markpavlitski |
#8 | memcache-urlencode-key-1613622-8.patch | 3.36 KB | markpavlitski |
Comments
Comment #1
tzakrajs CreditAttribution: tzakrajs commentedI have included the aforementioned patch file based on the latest development version in the git repo.
Let me outline what is included:
1. If the size of the entire urlencoded key is greater than 250 bytes go to 2, else go to 6.
2. If the size of the urlencoded prefix (ex: 'prefix-bin-') is greater than 210 bytes, go to 3, else go to 6
3. If the size of the urlencoded prefix is equal to or greater than 250 bytes, go to 4, else go to 5
4. Invoke watchdog as WATCHDOG_ERROR with "Key prefix and bin are too long to allow unique key" go to 6
5. Invoke watchdog as WATCHDOG_WARNING with "Key prefix and bin are too long to allow full SHA1 key" go to 6
6. Truncate the entire unencoded key character-by-character until the entire encoded key is not greater than 250 go to 7
7. Return the entire encoded key.
Comment #2
tzakrajs CreditAttribution: tzakrajs commentedCross-posted to: https://security.drupal.org/node/74618
Comment #3
BMDan CreditAttribution: BMDan commentedtzakraj's patch should have the following line deleted:
It is just cruft left over from testing. That minor issue notwithstanding, I've reviewed the patch's logic and offer my +r, for whatever it's worth.
Comment #4
SocialNicheGuru CreditAttribution: SocialNicheGuru commentedthe patch fails:
git apply _m*patch
fatal: corrupt patch at line 61
patch -p1 < _m*h
patching file dmemcache.inc
patch unexpectedly ends in middle of line
Hunk #1 FAILED at 439.
1 out of 1 hunk FAILED -- saving rejects to file dmemcache.inc.rej
Comment #5
BMDan CreditAttribution: BMDan commentedHere's an updated patch, fresh against a git clone. Note that this applies against 7.x-1.x, not master. If you'd like me to reroll against master, let me know.
Comment #6
BMDan CreditAttribution: BMDan commentedUnassign; tzakrajs is no longer available.
Patch needs review.
Comment #7
markpavlitski CreditAttribution: markpavlitski commentedThis patch cuts characters off the end of the key until it is 250 bytes or under. As the prefix length increases, the number of unique bytes available for the key decreases, until all keys are just the first 250 bytes of the prefix.
With a key prefix over 210 bytes, you will experience random WSODs where cache collisions are occurring.
I'd suggest trimming characters from the end of the key prefix instead of the key.
I'd also suggest using the register_shutdown_function() method for recording error messages, as watchdog may not yet be functional.
Comment #8
markpavlitski CreditAttribution: markpavlitski commentedAttached patch includes the following changes:
Comment #9
markpavlitski CreditAttribution: markpavlitski commentedThe attached patch takes a much simpler approach.
If the key is over 250 bytes, the fully prefixed key is hashed with sha256 (rather than just the cid).
This will guarantee that the key is always under 250 bytes, while still ensuring there aren't any key collisions.
There is also an update to README.txt to state that the total key length must be under 250 characters.
Comment #10
Jeremy CreditAttribution: Jeremy commentedI like your simpler approach.
However, I don't like your change of hash algorithms. If anything, I'd consider changing to md5 instead of sha1 for performance reasons. Collisions with md5 would be possible, but highly unlikely with cid's imo. That said, in most cases we're probably hashing infrequently enough it doesn't matter which algorithm we use, but still, I see no advantage to sha256 in this use case.
To test, I wrote a quick script that hashes the same text strings 100,000 times with crc32, md5, sha1, sha256 and sha512 for comparison. It does this with increasingly large text strings -- results:
Comment #11
markpavlitski CreditAttribution: markpavlitski commented@Jeremy It looks like leaving as sha1 is the safest option.
Comment #12
Jeremy CreditAttribution: Jeremy commentedI cleaned up the patch by adding documentation, adding a test, and making the hashing algorithm configurable:
http://drupalcode.org/project/memcache.git/commit/1d4cd8b
Needs to be ported to 6.x-1.x.
Comment #13
markpavlitski CreditAttribution: markpavlitski commentedD6 patch.
Comment #14
BMDan CreditAttribution: BMDan commentedIt strikes me that this line:
should be:
Comment #15
Fabianx CreditAttribution: Fabianx commentedI would propose the following both for D6 and D7:
That should ensure the length is correct, but still give visibility to what is being hashed ...
Comment #17
Jeremy CreditAttribution: Jeremy commentedThanks, committed to the 7.x branch after fixing an off-by-one error and improving the documentation. I also exposed memcache_key_max_length so anyone preferring to enforce shorter key lengths to optimize network traffic can do so.
http://cgit.drupalcode.org/memcache/commit/?id=fc5df69
This still needs a backport to 6.x-1.x-dev.
Comment #18
Jeremy CreditAttribution: Jeremy commentedComment #19
Jeremy CreditAttribution: Jeremy at Tag1 Consulting commentedBackported to D6:
http://cgit.drupalcode.org/memcache/commit/?id=05901bf