[OSSA 2013-017] Memcache encryption middleware improperly implemented (CVE-2013-2166)

This patch is untested, but I believe it to be a mostly complete implementation of the fix.

The unittests obviously need to be updated to match this.

Adding keystone core

I think it makes sense to fix both issues you reported in embargo mode, even if their exploitation is a bit unlikely... after all, those features were added to mitigate a risk, and they don't really mitigate it.

Here is my attempt to summarize impact (for both)

Title: Issues in Keystone middleware memcache signing/encryption feature
Reporter: Paul McMillan (Nebula)
Products: python-keystoneclient
Affects: [? any idea when in client history that was introduced]

Description:
Paul McMillan from Nebula reported multiple issues in the implementation of memcache signing/encryption feature in Keystone client middleware. An attacker with direct write access to the memcache backend could insert malicious data and potentially bypass the signing/encryption security strategy that was specified. Only setups that make use of memcache caching in the Keystone middleware (specify memcache_servers) and using ENCRYPT or MAC as their memcache_security_strategy are affected.

Memcache security was introduced in Grizzly. Its an optional feature.

Yes, we should get absolutely get rid of the marker checking logic. Error out if we can't verify or decrypt data.

An attacker have access to memcache can corrupt data. I don't think adding signature before encryption can prevent that.

If attacker managed to get a hold of the encryption key, signing key is likely compromised as well.

I would think the benefit of adding signature prior to encryption is to guard against brute force attack on the decryption.

You're right about embargoing the fix. The security notice looks good other than that it may be worth noting that a mitm attacker can also carry out the same attacks.

> An attacker have access to memcache can corrupt data. I don't think adding signature before encryption can prevent that.

The difference is that adding a signature before encryption means we reject the corrupted data as invalid, rather than accepting it
and potentially serving attack data to the user. Remember that an attacker can modify the output of the decryption even if they can't read the encrypted data. As currently written, the client will trust that modified data.

> If attacker managed to get a hold of the encryption key, signing key is likely compromised as well.

That may be true, but recommended practice is to make them different keys as I did in my patch, so that you don't end up with subtle related-key attacks. In particular, it is pretty common to have a key re-used in multiple parts of a program result in attacks where signed or encrypted data from one part of a program can be used to attack a different part even if the attacker doesn't actually know the key. The NIST document I reference in the bug report includes more details.

> I would think the benefit of adding signature prior to encryption is to guard against brute force attack on the decryption.

Nope, it's about integrity of the decrypted data, and choosing to not attempt to decrypt the data unless the integrity is verified. For a practical example of the types of attacks this prevents, you can read about the BEAST and CRIME attacks against SSL.

> The difference is that adding a signature before encryption means we reject the corrupted data as invalid, rather than accepting it
and potentially serving attack data to the user. Remember that an attacker can modify the output of the decryption even if they can't read the encrypted data. As currently written, the client will trust that modified data.

Can you please elaborate? How does attacker "modify the output of the decryption"? If attacker don't have to right decryption key, the decrypted output will be garbage and won't be interpreted as token data.

Here's a slightly updated patch. I haven't fixed the unittests yet.

> Can you please elaborate? How does attacker "modify the output of the decryption"? If attacker don't have to right decryption key, the decrypted output will be garbage and won't be interpreted as token data.

An attacker modifies the output of the decryption by changing bytes in the ciphertext. The encryption algorithm does not, by itself, reject this, and as you noted, this muddles some of the output. It is not true that it muddles all the output, however. Specifically, in the cipher mode currently used, modified bytes in the ciphertext will affect one block of output. If any significant amount of data is stored in the cache, this can allow strategic corruption of only a portion of the encrypted message, leaking information about the encrypted data or compromising client functionality.

For some examples of attacks on similar systems, I recommend reading these papers:
http://www.iacr.org/cryptodb/archive/2002/EUROCRYPT/2850/2850.pdf (the Vaudenay paper - a really good introduction)
http://eprint.iacr.org/2005/033.pdf (an attack on PGP's particular use of CFB)
http://static.usenix.org/event/woot10/tech/full_papers/Rizzo.pdf (the SSL oracle paper I mentioned above)

For further reading, I recommend Cryptography Engineering, by Ferguson, Schneier and Kohno.
http://www.amazon.com/dp/0470474246/

Updated impact description:

Title: Issues in Keystone middleware memcache signing/encryption feature
Reporter: Paul McMillan (Nebula)
Products: python-keystoneclient
Affects: Grizzly

Description:
Paul McMillan from Nebula reported multiple issues in the implementation of memcache signing/encryption feature in Keystone client middleware. An attacker with direct write access to the memcache backend (or in a man-in-the-middle position) could insert malicious data and potentially bypass the signing/encryption security strategy that was specified. Only setups that make use of memcache caching in the Keystone middleware (specify memcache_servers) and using ENCRYPT or MAC as their memcache_security_strategy are affected.

Please review this patch, I believe it to be correct and complete.

I have reviewed this patch and it looks good to me.

@Keystone core please review proposed patch.

Code looks good.

just an update- I haven't grokked all the details yet, but I have yet to see anything I object to.

Comments on fix_memcache_crypt3.patch:

Mostly suggestions, but do have a couple questions.

file keystoneclient/middleware/auth_token.py:
line 848: suggest use "not ..." rather than "is None"
line 860: Not sure what "This" is referring to, is it the memcache_crypt.unprotect_data function or the _cache_get function?
line 864: no need to include exception string because LOG.exception will print it out.
line 870: suggest use "not serialized rather than "is None"
line 875: comment doesn't make sense since would have returned at 871 if serialized is None.
line 895: suggest use "not ..." rather than "is None"

file keystoneclient/middleware/memcache_crypt.py:
line 146: Should be "except Exception:", see HACKING.rst

tests/test_memcache_crypt.py:
line 17: would like to see a test for 2 empty strings and 1 empty one not.
line 23: looks like the error message is the length of the MAC? Was the intent to check all 3 are equal?
line 63: should use assertIsNone

Patch looks quite good, similar code to what I am implementing in oslo-incubator, with some minor differences.
I wonder if we want to make it possible to interchange it so that we can consolidate later ?

Some observations:

- I would use HKDF (exapand) from RFC 5869 for the key derivation, insted of just a plain HMAC, as that function has properties that are desirable (I have an implementation available if we want that I have implemented for message signing and can contribute it).

- On the ciphers/hash sides, I think SHA256 would be sufficient, also I would find AES 128 in CBC (as we do not need a stream cipher here) mode wiith random IV prefereable, given AES-128 is faster and also seem has (relatively) less weaknesses than AES-256

- Returning a CACHE_KEY as derivation from the secret is not necessary, you could as well just return the random IV as the kay as it is already exposed in the data anyway. There is no reason to use a piece of a HMAC output signature as a key that I can see, and I rather not publish any key material, derived or not.

None of these remarks are critical, I think all security properties that we want from this change are fullfilled with the current approach as well.

Some responses to Simo:

- HKDF is fine, but I believe that the approach taken in this patch is also fine. This approach has the benefit of being easier to implement / understand.

- This patch uses AES-128-CBC already. It uses SHA-384 per NIST's recommendation on key derivation. This is needed to produce 3 128 bit keys.

- I'm a little confused on your concerns about returning the cache key. Reusing the IV for a different purpose seems like a bad idea.

Some remarks:

- HKDF would allow you to use SHA256 and obtain up to 10 blocks of material good for keys. Plus it allows key derivation with arbitrary salt (if you use extraction which is not needed) and arbitrary additional info if you need to make the key derivation unique (equivalent to using a serialzied tokena s you do here I guess).
But the reason I suggest it is that it is a true and tested Key Derivation Function while HMAC technically is not, and taking shortcuts tend to have undesirable consequences in the long run. Although I am not concerned in this case.

- AES 128 true, the original code mentioned AES256 and it stuck, however both the old and the new code use MODE_CFB not MODE_CBC

- Ignore the IV part you can't look it up so it is not suitable as a memcahce key indeed, pity that, could have saved some space too :) I am still somewhat uncomfortable using a key derived from a secret as a public handle, but it is probably ok.

- If you would like to update the patch to include HKDF, I wouldn't object.

- This patch does use AES-128-CBC. I promise! Go check again :-) I worked with Paul on creating a padding scheme to make CBC possible here. Note the line: AES.new(key, AES.MODE_CBC, iv)

- If you have an alternate suggestion here, I'm open to it. As it is, I can't think of an attack vector with the current code.

I am sorry Bryan,
apparently when I re-checked about the mode I looked at the first patch in this bug, which used MODE_CFB.
I just checked the last patch does use MODE_CBC, so all fine there.

For HKDF here is my current WIP implementation:
https://review.openstack.org/#/c/28471/
Look into openstack/common/cryptoutils.py there is a class called HKDF, it can be very easily extracted and reused for this bug.

I do not see attack vectors with the current code either. I checked that signed/encrypted blobs could not be swapped for example, but if I understand correctly the full token is used to derive the keys so there should be no way to swap blobs and have authentication pass.
In theory there is a 1 in a 2^64 chance (I think, probably lower) that 2 tokens will generate the same cache_key, but I do not see how that could be practically used in any way.

In response to Brant Knudson:

> file keystoneclient/middleware/auth_token.py:
> line 848: suggest use "not ..." rather than "is None"
> line 895: suggest use "not ..." rather than "is None"

I'm deliberately using None rather than accepting 0, [], '', etc. because the documentation specifies the way to skip the security strategy is to omit the key. I don't think that an empty string is an acceptable way to specify "no security", and I want this code to fail loudly if it is improperly configured.

> line 860: Not sure what "This" is referring to, is it the memcache_crypt.unprotect_data function or the _cache_get function?
Good point, I'll clarify the point that this is a reminder to the reader that unprotect_data can return None and is not always a json value.

> line 864: no need to include exception string because LOG.exception will print it out.
Good point, I'll fix that.

> line 870: suggest use "not serialized rather than "is None"
This was an abundance of caution about parsing unexpected data. There should be no paths where serialized is not one of None or a valid parsable json, and I'd prefered to have a json decode failure (which makes it obvious that data like 0, '', (), etc. is unexpected) rather than silently returning None. That said, I'm not particularly tied to this use, if you don't buy the argument.

> line 875: comment doesn't make sense since would have returned at 871 if serialized is None.
On the contrary, this is entirely the point. At this point in the code, we have returned if serialized was None (indicating a cache miss or other error), and we know we should be holding a json decodable string. What we know is that the string is NOT the value 'null' which deserializes to None. This comment is asserting that we have not made the common cache/serialization mistake of not differentiating between a stored serialized value of None and a cache miss. This is why we can safely do the "data, expires = cached" expansion a couple lines down.

(note that I'm not wild about the way this works, but I'm fixing the crypto here, not rewriting the caching middleware)

> file keystoneclient/middleware/memcache_crypt.py:
> line 146: Should be "except Exception:", see HACKING.rst
Yep, that was a holdover from the original code. I'll fix it.

> tests/test_memcache_crypt.py:
> line 17: would like to see a test for 2 empty strings and 1 empty one not.
Added.

> line 23: looks like the error message is the length of the MAC? Was the intent to check all 3 are equal?
Good catch, fixed that.

I've attached an updated patch.

In response to Simo Sorce:

A few notes about this:

We do need to obscure the key as well as the value here. The cache key is usable as an authentication token in other parts of the stack. Because we are doing this, it is inappropriate to talk about salting it, since if we did that we would be unable to look up any values. Furthermore, because this is a caching layer, we don't want to be doing extra work if we can avoid it, which is why I didn't use more than one round of hashing in the KDF.

I do not believe HKDF is appropriate here. Unlike many other uses of KDFs, the input keying material is expected to be of good quality to begin with. People should not be using a password or similar for generating this secret key, and this key is not derived from some other source an attacker may know something about. Furthermore, we do not need 10 blocks of key material, we need exactly 3. Additionally, it is inappropriate to salt these values because that would make it impossible to look up cached material. If you read the SP800-108 document closely, you'll notice that we're basically using one round of the approved KDF (we could prepend a 1 to the hashed value if you want to be pedantic).

However, as you've observed, if the secret material doesn't have enough entropy, this construction breaks down. I've conservatively added a requirement that the secret be at least 48 bytes long, which should reinforce the security of the construct.

Paul,
just a point, on HKDF, I was recommending to use just expand, and not the extract phase of HKDF, so no salt would be required (and technically you can avoid the salt on the extract phase too, the RFC recommends it but says it is not critical.
I am not sure you really need 384 bits for the secret, but won't hurt.

I did not know the cache key was used as an authentication token elsewhere though, can you elaborate that? It's worrying.

Looks like the patch could still use a few rounds of discussion, so we'll wait a bit more before calling keystone core to formally pre-approve it.

Paul: +1 on explicitly using "is None" rather than "not"

@Keystone core, please have a look at proposed patch.
Maybe we could make a "security release" of the python keystoneclient addressing the two vulnerabilities in progress.

I don't think the 'ignore-expires' parameter makes sense: if the value in the caches is expired, either from a memcache or a reading of the timestamp on the underlying token, it should be considered invalid. Passing a parameter to somehow modify this seems wrong: we can and should be draconian on this. Why was this added?

Note that there is a more serious CVE with a fix already, and I think this one conflicts with that fix. Please rebase this on top of the change for https://bugs.launchpad.net/python-keystoneclient/+bug/1179615 keeping the message signatures in the patch for putting into the cache with the expiration time exposed.

Minor nit: line 192 breaks the pattern of the comment block when splitting over multiple lines, looks like an stray return snuck in.

@ayoung I can't access that bug you referenced. Is it still embargoed?

Bryan: yes, I just added you to the access list.

Could we have a patch rebased on the proposed patch mentioned in comment 27 ?
I'd like to include that fix in a future python-keystoneclient security release.

Yeah, I'll rebase it today.

@Paul: any news ? python-keystoenclient was fixed publicly so you can now rebase on top of master.

Looks like Paul has gone MIA -- any Keystone core member feeling like rebasing his patch on current python-keystoneclient ?

Thierry -- Sorry about that, I'll get a rebased version submitted shortly.

I'm uploading a manual rebase of Paul's patch on top of current master. Verified that this passes all tests. Let me know if there are any questions / concerns.

@Thierry: Sorry about disappearing. Been swamped.

Thank you Bryan for rebasing this, the rebased version looks good to me.

Keystone core please +2 final patch.

I'll get a CVE based on description on comment 10.

CVE requested

I reviewed 0001-manual-rebase-of-memcache-encryption-middleware-patc.patch from comment 35 and it looks good to me. +2.

I'm seeing three test failures when I apply the rebased patch to master:

tests.test_auth_token_middleware.AuthTokenMiddlewareTest.test_encrypt_cache_data
tests.test_auth_token_middleware.AuthTokenMiddlewareTest.test_no_memcache_protection
tests.test_auth_token_middleware.AuthTokenMiddlewareTest.test_sign_cache_data

Full output of run_tests.sh is attached.

Are you sure you patched cleanly against master? Here's what I see when I run the tests (all passing).

https://gist.github.com/bdpayne/3422be8febee7f92e0f1

I hadn't run the unit tests before, but I've run them now and it works for me:

Ran 329 (-2) tests in 1.536s (-0.023s)

(I don't have as many cpus as Bryan.)

Odd, run_tests.sh fails for me but tox succeeds. I suspect that's my fault: https://gist.github.com/dolph/d5a37860a76b1553d770

That snippet looks like bug 1185231 (testrepository) but if tox on its own is succeeding then unit tests on the Jenkins slaves should be similarly fine (they all run under tox).

This is actually affecting python-keystoneclient 0.2.3-0.2.5, will fix impact desc

master: devstack-full, unit/py27, pep8: PASS

Sent downstream. Proposed public disclosure date/time: Wednesday, June 19, 1500UTC.

+2 for latest patch

Fix proposed to branch: master
Review: https://review.openstack.org/33661

Reviewed: https://review.openstack.org/33661
Committed: http://github.com/openstack/python-keystoneclient/commit/eeefb784f24c37d5f56a421e1ccc911cace9385e
Submitter: Jenkins
Branch: master

commit eeefb784f24c37d5f56a421e1ccc911cace9385e
Author: Bryan D. Payne <email address hidden>
Date: Fri Jun 7 09:34:25 2013 -0700

    Fix memcache encryption middleware

    This fixes lp1175367 and lp1175368 by redesigning the memcache crypt
    middleware to not do dangerous things. It is forward compatible, but
    will invalidate any existing ephemeral encrypted or signed memcache
    entries.

    Change-Id: Ice8724949a48bfad3b8b7c41b5f50a18a9ad9f42
    Signed-off-by: Bryan D. Payne <email address hidden>