[OSSA 2013-025] PKI tokens are never revoked using memcache token backend (CVE-2013-4294)

Bug #1202952 reported by Kieran Spear
260
This bug affects 1 person
Affects Status Importance Assigned to Milestone
OpenStack Identity (keystone)
Invalid
Undecided
Unassigned
Folsom
Fix Released
High
Unassigned
Grizzly
Fix Released
High
Morgan Fainberg
OpenStack Security Advisory
Fix Released
High
Thierry Carrez

Bug Description

This is a more serious incarnation of: https://bugs.launchpad.net/keystone/+bug/1202050.
Looks to be fixed on master in c238ace30981877e5991874c5b193ea7d5107419 (id hashing happens keystone/token/core.py there).

In the memcache token backend, whole tokens are stored in the revocation list.

In keystone/token/backends.py:
166 def _add_to_revocation_list(self, data):
167 data_json = jsonutils.dumps(data)
168 if not self.client.append(self.revocation_key, ',%s' % data_json):
169 if not self.client.add(self.revocation_key, data_json):
170 if not self.client.append(self.revocation_key,
171 ',%s' % data_json):
172 msg = _('Unable to add token to revocation list.')
173 raise exception.UnexpectedError(msg)
174
175 def delete_token(self, token_id):
176 # Test for existence
177 data = self.get_token(token_id) <----
178 ptk = self._prefix_token_id(token_id)
179 result = self.client.delete(ptk)
180 self._add_to_revocation_list(data) <----
181 return result

And returned from the API when the auth_token middleware asks for the revocation list:

208 def list_revoked_tokens(self):
209 list_json = self.client.get(self.revocation_key)
210 if list_json:
211 return jsonutils.loads('[%s]' % list_json)
212 return []

The auth_token middleware hashes the signed token and searches the revocation list for the hash:

1017 def is_signed_token_revoked(self, signed_text):
1018 """Indicate whether the token appears in the revocation list."""
1019 revocation_list = self.token_revocation_list
1020 revoked_tokens = revocation_list.get('revoked', [])
1021 if not revoked_tokens:
1022 return
1023 revoked_ids = (x['id'] for x in revoked_tokens)
1024 token_id = utils.hash_signed_token(signed_text)
1025 for revoked_id in revoked_ids:
1026 if token_id == revoked_id:
1027 self.LOG.debug('Token %s is marked as having been revoked',
1028 token_id)
1029 return True
1030 return False

Because the memcache backend stores the entire token, the value of x['id'] above is not an md5 hash, but the encoded PKI token. This will never match the value of the hashed untrusted token.

Storing the whole token also means only around 256 tokens can stored before the memcache page is full and errors happen.

Revision history for this message
Thierry Carrez (ttx) wrote :

Adding Keystone PTL for impact confirmation

Changed in ossa:
status: New → Incomplete
Revision history for this message
Adam Young (ayoung) wrote :

Looks legitimate. A quick check of the code shows that we do not test the format of the revocation list for each of the backends, but merely that the ID in is the same as the revoked ID, which would mask this issue.

The memcached backend already has a serious and public failing in that it is not persisted over reboots. As such, using the memcahced backend for tokens is probably a bad choice.

One solution to both problems would be to have the revocation list always stored in SQL.

Revision history for this message
Dolph Mathews (dolph) wrote :

I'm trying to follow along but I'm having to make a few assumptions documented below. Please verify!

First, I assume "keystone/token/backends.py" is intended to refer to "keystone/token/backends/memcache.py".

Second, all the line numbers in the code excerpts appear to refer to the current master branch (not stable/grizzly?).

Those two excerpts on master:

1. https://github.com/openstack/keystone/blob/53ed50ddd0cdebd1b6329f47caac3c8d8b41cd7e/keystone/token/backends/memcache.py#L166-L181

2. https://github.com/openstack/keystone/blob/53ed50ddd0cdebd1b6329f47caac3c8d8b41cd7e/keystone/token/backends/memcache.py#L208-L212

The same two excerpts on stable/grizzly:

1. https://github.com/openstack/keystone/blob/76a94c68d621c893941a817d36f8ddbe9559dbde/keystone/token/backends/memcache.py#L87-L102

2. https://github.com/openstack/keystone/blob/76a94c68d621c893941a817d36f8ddbe9559dbde/keystone/token/backends/memcache.py#L129-L133

Anyway, attempting to reproduce on each branch results in the following responses from GET /v2.0/tokens/revoked:

https://gist.github.com/dolph/899226d3b774787a2ad5

So, the actual content of the response changes quite radically from the entire signed token in stable/grizzly to just a hash in master. In other words, we've introduced a backwards-incompatible API change between the two branches.

While I would prefer to revise the client to handle both responses, we can't guarantee that keystoneclient is the only consumer of that API. It's not very attractive, but the only viable option I see is to revert the change in master, and publish entire signed tokens in the token revocation list.

I didn't test against folsom, but it's safe to assume that the responses from both folsom and grizzly are the same.

Revision history for this message
Dolph Mathews (dolph) wrote :

In case something happens to the gist above, the verified responses appear as follows...

grizzly:

  {"revoked": [{"expires": "2013-07-20T20:59:39Z", "id": "--signed-token--"}]}

master:

  {"revoked": [{"expires": "2013-07-20T21:10:09Z", "id": "--md5-checksum--"}]}

Changed in keystone:
importance: Undecided → High
status: New → Confirmed
Revision history for this message
Kieran Spear (kspear) wrote :

Thanks Dolph, obviously my delivery could use some work... The code excerpts were taken before I realised the auth_token issue didn't affect master.

Regarding the breaking API change, note that the SQL backend in stable/grizzly has always only stored the md5 checksum in the token id:
https://github.com/openstack/keystone/blob/76a94c68d621c893941a817d36f8ddbe9559dbde/keystone/token/backends/sql.py#L64
https://github.com/openstack/keystone/blob/76a94c68d621c893941a817d36f8ddbe9559dbde/keystone/token/backends/sql.py#L161

So in Grizzly just switching backends also changes the content of the revocation list.

Revision history for this message
Dolph Mathews (dolph) wrote :

Ah, I didn't even think to switch to the memcache driver in either of my tests... I used the default config in both cases. So the above reflects the KVS driver in grizzly, and the SQL driver in master.

This is going to be a mess to clean up... but, I'm now thinking we should handle both variations in auth_token as an immediate security fix, and then work out exactly which drivers in which branches are producing hashes before changing any of them.

Changed in python-keystoneclient:
status: New → Confirmed
importance: Undecided → High
Revision history for this message
Adam Young (ayoung) wrote :

With the applied patch, you can see the revocation list in memcached:

ran devstack, killed keystone server, modified /etc/keystone/keystone.conf with

[token]
driver = keystone.token.backends.memcache.Token
#driver = keystone.token.backends.sql.Token

service start memcached

restarted keystone server

sourced openrc

as demo user, created a bunch of tokens using cli token-get

export OS_USERNAME=admin
export ADMINTOKEN=` keystone token-get | awk '/ id /{print $4}'`

deleted a bunch of tokens using:
curl -X DELETE -H "X-Auth-Token:$ADMINTOKEN" http://localhost:35357/v2.0/tokens/$USERTOKEN

ran the following code in the python interpreter

import memcache
memcache_client = memcache.Client(['localhost'],debug=0)
memcache_client.get(revocation_key)

output looks like this:

'{"id": "83d677322322fc279a6a11c9c7474cb3"},{"id": "089dfcc4e55f96301d3d19beb663435d"},{"id": "36851e53e0027bf55c32b12a898b2950"}'

Revision history for this message
Kieran Spear (kspear) wrote :

I think some of the higher up code expects the 'expires' key in the revocation list dicts when the list is requested. Fix looks good to me otherwise.

Looks like the KVS backend is fixed on master:
https://github.com/openstack/keystone/commit/efc30beab10faf4720a96322adb135726662b025#L1R46
Date: Wed May 8 10:51:27 2013 +1000

Revision history for this message
Thierry Carrez (ttx) wrote :

Looks like this will need an OSSA in all cases.

If I understand the comments correctly, the issue is that the server in some cases (grizzly/memcache at least, not sure about others... please re-precise) returns full token instead of token id in the check, which breaks Keystone middleware revocation.

If that's correct, I suppose we could fix it directly on the server side because it's a bit unlikely that another client would have relied on that wrong answer.. The alternative is to not fix it in Grizzly, support both forms in the middleware/client side and introduce the fix only in Havana...

Changed in ossa:
status: Incomplete → Confirmed
importance: Undecided → High
Thierry Carrez (ttx)
Changed in ossa:
assignee: nobody → Thierry Carrez (ttx)
Revision history for this message
Thierry Carrez (ttx) wrote :

Dolph, Adam: is only grizzly/memcache affected ?

Revision history for this message
Adam Young (ayoung) wrote :

All memcache token incarnations for PKI tokens are affected. Since that code went in back in Folsom, that means Folsom, Grizzly and Havana.

The fix is a server side fix. We could also fix using the auth_token middleware, but that is probably suboptimal. It will slow down the revocation check, and it would require updating every component in an OS deployment. Server side fix is preferable and proper.

Deploying the fix will dump the revocation list, but since it was not checked before, it will be no worse than it was.

Revision history for this message
Thierry Carrez (ttx) wrote :

Keystone core, please review proposed patch !
Kieran: should we credit a company in addition to your name ?
My understanding is that only the memcache backend is affected in master... but what about Folsom/Grizzly ? Is the KVS backend affected there ? Comments are contradictory :)

Proposed impact description, please review:
=================================
Title: Token revocation failure when using Keystone memcache backend
Reporter: Kieran Spear ($COMPANY)
Products: Keystone
Affects: Folsom and later

Description:
Kieran Spear from $COMPANY reported a vulnerability in Keystone memcache token backend. The memcache token revocation lists stored the entire token instead of the token ID, triggering comparison failures, ultimately resulting in revoked tokens still being considered valid. Only Keystone setups making use of the memcache token backend are affected.
=================================

Changed in ossa:
status: Confirmed → Triaged
Revision history for this message
Dolph Mathews (dolph) wrote :

I'd still like to test each branch & token backend at the API level, but at first glance, it appears that ayoung's fix wouldn't produce the expected API response as Kieran cites (missing the "expires" attribute for each token).

Revision history for this message
Dolph Mathews (dolph) wrote :

Affected:

  master + memcache token driver
  stable/grizzly + kvs token driver
  stable/grizzly + memcache token driver
  stable/folsom + kvs token driver

Not affected (ID attribute is at least a predictable MD5 hex digest):

  master + kvs token driver
  master + sql token driver
  stable/grizzly + sql token driver
  stable/folsom + sql token driver

Untestable / completely broken due to MemcachedKeyLengthError:

  stable/folsom + memcache token driver
    backtrace: https://gist.github.com/dolph/899226d3b774787a2ad5#file-folsom-memcache-500

Revision history for this message
Dolph Mathews (dolph) wrote :

Sample API responses of the above branch/driver combinations: https://gist.github.com/dolph/899226d3b774787a2ad5#file-notes

Revision history for this message
Kieran Spear (kspear) wrote :

COMPANY = '[the] University of Melbourne'

Nice analysis, Dolph. That matches my understanding of the state of things from digging through the code.

Revision history for this message
Thierry Carrez (ttx) wrote :

New proposed impact description, please review:
=================================
Title: Token revocation failure using Keystone memcache/KVS backends
Reporter: Kieran Spear (University of Melbourne)
Products: Keystone
Affects: Folsom and later

Description:
Kieran Spear from the University of Melbourne reported a vulnerability in Keystone memcache and KVS token backends. The token revocation lists stored the entire token instead of the token ID, triggering comparison failures, ultimately resulting in revoked tokens still being considered valid. Only Keystone setups making use of the memcache token backend (using Grizzly and later) and KVS token backend (using Folsom and Grizzly only, master branch is already fixed) are affected. The SQL token backend is unaffected.
=================================

Revision history for this message
Dolph Mathews (dolph) wrote :

Regarding impact description: deployments using UUID tokens are not affected, only those using PKI tokens (`keystone.conf [signing] token_format = PKI`).

`UUID` is the default format in stable/folsom and `PKI` is the default in stable/grizzly. In master, `token_format` is deprecated in favor of `keystone.conf [token] provider`.

Revision history for this message
Thierry Carrez (ttx) wrote :

How about this ?

=================================
Title: Token revocation failure using Keystone memcache/KVS backends
Reporter: Kieran Spear (University of Melbourne)
Products: Keystone
Affects: Folsom and later

Description:
Kieran Spear from the University of Melbourne reported a vulnerability in Keystone memcache and KVS token backends. The PKI token revocation lists stored the entire token instead of the token ID, triggering comparison failures, ultimately resulting in revoked PKI tokens still being considered valid. Only Keystone setups making use of PKI tokens with the memcache token backend (using Grizzly and later) and KVS token backend (using Folsom and Grizzly only, master branch is already fixed) are affected. Setups using UUID tokens, or using PKI tokens with the SQL token backend, are unaffected.
=================================

Revision history for this message
Jeremy Stanley (fungi) wrote :

Thierry's proposed impact description in comment #19 looks good to me.

Revision history for this message
Thierry Carrez (ttx) wrote :

Keystone core: Could we get a review on Adam's patch ?
Anyone up for the Grizzly and Folsom backports ?

Revision history for this message
Dolph Mathews (dolph) wrote :

impact description looks great

Revision history for this message
Dolph Mathews (dolph) wrote :

Attaching patches that only include automated tests to reproduce. These are my results with these tests, which differ from my analysis done by hand above (differences noted in parens).

Affected:

  stable/grizzly + kvs token driver
  stable/grizzly + sql token driver (previously not affected)
  stable/grizzly + memcache token driver
  stable/folsom + kvs token driver
  stable/folsom + memcache token driver (previously untestable)

Not affected:

  master + kvs token driver
  master + sql token driver
  master + memcache token driver (previously affected)
  stable/grizzly + sql token driver

Revision history for this message
Dolph Mathews (dolph) wrote :
Revision history for this message
Dolph Mathews (dolph) wrote :
Revision history for this message
Thierry Carrez (ttx) wrote :

Dolph: "stable/grizzly + sql token driver" is listed in both the "Affected" and "Not affected" lists ? What about "stable/folsom + sql token driver" ?

Revision history for this message
Dolph Mathews (dolph) wrote :

My mistake!

stable/grizzly + sql token driver IS affected.
stable/folsom + sql token driver is NOT affected.

Revision history for this message
Dolph Mathews (dolph) wrote :

Fix for stable/folsom memcache and kvs is attached, with tests from above.

Revision history for this message
Dolph Mathews (dolph) wrote :

Fix for stable/grizzly memcache and kvs is attached, with a slightly modified version of the tests from above (see inline comment).

With the modified tests, stable/grizzly + sql token driver does NOT appear to be affected.

Revision history for this message
Dolph Mathews (dolph) wrote :

Final list of affected branches / drivers:

  stable/grizzly + kvs token driver
  stable/grizzly + memcache token driver
  stable/folsom + kvs token driver
  stable/folsom + memcache token driver

I originally had marked "master + memcache token driver" as "affected" because it returns a relatively bloated API response (as the other failing implementations do), however the response itself does not present a vulnerability because the "id" values are MD5-hashed as expected.

As far as I can tell, this API has never been previously documented or tested at all, hence the inconsistencies in implementation.

Revision history for this message
Thierry Carrez (ttx) wrote :

New revision:

=================================
Title: Token revocation failure using Keystone memcache/KVS backends
Reporter: Kieran Spear (University of Melbourne)
Products: Keystone
Affects: Folsom, Grizzly

Description:
Kieran Spear from the University of Melbourne reported a vulnerability in Keystone memcache and KVS token backends. The PKI token revocation lists stored the entire token instead of the token ID, triggering comparison failures, ultimately resulting in revoked PKI tokens still being considered valid. Only Folsom and Grizzly Keystone setups making use of PKI tokens with the memcache or KVS token backends are affected. Havana setups, setups using UUID tokens, or setups using PKI tokens with the SQL token backend are all unaffected.
=================================

Revision history for this message
Dolph Mathews (dolph) wrote :

+1 for impact; definitely easier to understand which branches are affected.

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

Running through the folsom patch from #29, it looks like memcache fix was not adding in the "expired" field, which would cause list_revoked_tokens to fail.

Attached is a fix based upon patch from #29 with added functionality to handle adding 'expires' into the revocation-list (per token) in the memcache token driver. Updated new tests to verify token_id and expires both are in each element of the revocation_list. Updated TokenTests.test_token_crud to avoid stripping "expired" fields from tokens in fake-memcache server, ensuring tests will now complete.

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

Attaching correct patch file (for #33). This one should work for python2.6 as well.

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

Correction on post #33/#34, the patch is based upon the Folsom patch in post #28.

Revision history for this message
Dolph Mathews (dolph) wrote :

+1 for revisions on folsom patch

Revision history for this message
Thierry Carrez (ttx) wrote :

So, to summarize... our patches for this are posted at:
master (havana): comment 7
grizzly: comment 29
folsom: comment 34

keystone-core please confirm and +2 proposed patches !

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

I am performing the same changes for the grizzly patch (and should be done shortly) to correct the same bugs in folsom.

Grizzly patch will not succeed gate because of https://bugs.launchpad.net/keystone/+bug/1212939. In regards to bug 1212939, the quickest solution would be to include netaddr in the test-requirements with the grizzly patch, but it doesn't resolve the bug the "right" way.

Revision history for this message
Brant Knudson (blk-u) wrote :

Grizzly - bug-1202952-grizzly-v1.patch from comment #29
- unit tests worked - Ran 1306 tests in 2467.505s
- visual inspection looks good
= +2

Folsom bug-1202952-folsom-v2.patch from comment #34
- run unit tests - Ran 709 tests in 411.905s - a couple of s3token tests failed but I don't know why, they also fail without the patch
- visual inspection looks good
= +2

The master patch from comment #7 didn't apply.
error: patch failed: keystone/token/backends/memcache.py:174
error: keystone/token/backends/memcache.py: patch does not apply

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

Fixed grizzly patch attached, same functional issues corrected as in patch from #34.

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

Folsom - bug-1202952-folsom-v2.patch from comment #34
- unit tests worked - Ran 709 tests in 44.883s
- visual inspection looks good
- verified functionally in devstack
= abstain since I provided updated patch (+2 if this doesn't matter)

Grizzly - bug-1202952-grizzly-v1.patch from comment #29
- unit tests worked - Ran 1306 tests in 191.340s
- visual inspection - missing expires field in revocation list in memcache driver
- fails functionally in devstack (memcache driver causes exception in building revocation_list due to missing 'expires' key/element in the elements in the revocation_list)
= -2 (do not merge)

Updated grizzly bug-1202952-grizzly-v2.patch from comment #41
- Units test pass with the addition of netaddr in vnenv - Ran 1306 tests in 192.625s
- visual inspection looks good
- verified functionally in devstack (no exceptions)
= abstain since I provided updated patch (+2 if this doesn't matter)

Master patch from #7 does not apply.
error: patch failed: keystone/token/backends/memcache.py:174
error: keystone/token/backends/memcache.py: patch does not apply
- Patch from #7, while beneficial is not required for this bug. Master is not affected by the security bug.

Revision history for this message
Dolph Mathews (dolph) wrote :

+1 for revisions on grizzly patch in comment #41

tests for master can be corrected in gerrit publicly after folsom & grizzly patches are released

Revision history for this message
Brant Knudson (blk-u) wrote :

Question on the grizzly patch v2 from comment #41 --

in token/backends/memcache.py, at line 99 do
 token_id = token.unique_id(token_id)
then at line 101
 ptk = self._prefix_token_id(token.unique_id(token_id))

so now token_id has had token.unique_id() applied twice when passed to self._prefix_token_id(). Seems strange would need to double-apply an operation, so wondering if this is intentional.

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

Brant: It appears to be un-intentional, but shouldn't hurt anything as the cms.hash_token function does validation before rehashing. This is a flaw in both versions of both patches (grizzly and folsom). It can be removed if it's a big concern and I'll run through the tests and post 'v3's of each with the modification if needed.

Revision history for this message
Brant Knudson (blk-u) wrote :

Morgan - please fix it since it looks incorrect, and I'd be worried about somebody changing the unique_id function expecting nobody's applying it twice.

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

No problem, I'll roll the changes and get them posted here shortly.

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

Folsom update covering Brant's concern.

Revision history for this message
Morgan Fainberg (mdrnstm) wrote :

Grizzly update covering Brant's concern.

Revision history for this message
Brant Knudson (blk-u) wrote :

Grizzly - bug-1202952-grizzly-v3.patch from comment #49
- unit tests worked - Ran 1306 tests in 2366.276s
- visual inspection looks good, my comment was addressed
= +2

Revision history for this message
Brant Knudson (blk-u) wrote :

Folsom - bug-1202952-folsom-v3.patch in comment #48
- unit tests worked - Ran 709 tests in 412.283s
- visual inspection looks good, my comment was addressed
= +2

Revision history for this message
Dolph Mathews (dolph) wrote :

+2 for revised patches in comments #48 and #49

Revision history for this message
Thierry Carrez (ttx) wrote :

This should be good to go with the patches in comments #48 and #49.
Requesting CVE.

Changed in ossa:
status: Triaged → In Progress
Revision history for this message
Thierry Carrez (ttx) wrote :

CVE: CVE-2013-4294

Proposed public disclosure date/time: Wednesday, September 11, 1500UTC.

Changed in ossa:
status: In Progress → Fix Committed
no longer affects: keystone/havana
Changed in keystone:
status: Confirmed → Invalid
no longer affects: python-keystoneclient
Changed in keystone:
importance: High → Undecided
Thierry Carrez (ttx)
information type: Private Security → Public Security
Revision history for this message
Thierry Carrez (ttx) wrote :
Revision history for this message
Thierry Carrez (ttx) wrote :

[OSSA 2013-025]

summary: - PKI tokens are never revoked using memcache token backend
+ [OSSA 2013-025] PKI tokens are never revoked using memcache token
+ backend (CVE-2013-4294)
Revision history for this message
Dolph Mathews (dolph) wrote :

Opening against master to forward port tests.

Changed in keystone:
status: Invalid → Triaged
importance: Undecided → Wishlist
Revision history for this message
Thierry Carrez (ttx) wrote :

@Dolph: This bug is about the vulnerability, I don't want to create confusion whether master is affected by keeping a master task on this. I created bug 1224320 to cover for the forward-porting of tests.

Changed in ossa:
status: Fix Committed → Fix Released
Changed in keystone:
importance: Wishlist → Undecided
status: Triaged → Invalid
To post a comment you must log in.
This report contains Public Security information  
Everyone can see this security related information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.