PKI Token revocation

Co-authored-by: Adam Young <ayoung@redhat.com>

Token revocations are captured in the backends,

During upgrade, all previous tickets are defaulted to valid.

Revocation list returned as a signed document and can be fetched in an admin context via HTTP

Change config values for enable diable PKI

In the auth_token middleware,  the revocation list is fetched prior
to validating tokens. Any tokens that are on the revocation list
will be treated as invalid.

Added in PKI token tests that check the same logic as the UUID tests.
Sample data for the tests is read out of the signing directory.

dropped number on sql scripts to pass tests.

Also fixes 1031373

Bug 1037683

Change-Id: Icef2f173e50fe3cce4273c161f69d41259bf5d23

26 files changed, 626 insertions, 71 deletions

diff --git a/keystone/common/cms.py b/keystone/common/cms.py
index 22dadfcc..e4c0f260 100644
--- a/keystone/common/cms.py
+++ b/keystone/common/cms.py
@@ -76,6 +76,11 @@ def cms_sign_text(text, signing_cert_file_name, signing_key_file_name):
         LOG.error('Signing error: %s' % err)
         raise subprocess.CalledProcessError(retcode,
                                             "openssl", output=output)
+    return output
+
+
+def cms_sign_token(text, signing_cert_file_name, signing_key_file_name):
+    output = cms_sign_text(text, signing_cert_file_name, signing_key_file_name)
     return cms_to_token(output)
 
 
diff --git a/keystone/common/sql/core.py b/keystone/common/sql/core.py
index bf256473..e9b780a4 100644
--- a/keystone/common/sql/core.py
+++ b/keystone/common/sql/core.py
@@ -41,6 +41,7 @@ String = sql.String
 ForeignKey = sql.ForeignKey
 DateTime = sql.DateTime
 IntegrityError = sql.exc.IntegrityError
+Boolean = sql.Boolean
 
 
 # Special Fields
diff --git a/keystone/common/sql/migrate_repo/versions/003_sqlite_downgrade.sql b/keystone/common/sql/migrate_repo/versions/003_sqlite_downgrade.sql
new file mode 100644
index 00000000..c054ef33
--- /dev/null
+++ b/keystone/common/sql/migrate_repo/versions/003_sqlite_downgrade.sql
@@ -0,0 +1 @@
+alter TABLE token  drop column valid;
diff --git a/keystone/common/sql/migrate_repo/versions/003_sqlite_upgrade.sql b/keystone/common/sql/migrate_repo/versions/003_sqlite_upgrade.sql
new file mode 100644
index 00000000..963bfa0a
--- /dev/null
+++ b/keystone/common/sql/migrate_repo/versions/003_sqlite_upgrade.sql
@@ -0,0 +1,3 @@
+alter TABLE token  ADD valid integer;
+update token set valid = 1;
+
diff --git a/keystone/common/sql/migrate_repo/versions/003_token_valid.py b/keystone/common/sql/migrate_repo/versions/003_token_valid.py
new file mode 100644
index 00000000..d45a7a87
--- /dev/null
+++ b/keystone/common/sql/migrate_repo/versions/003_token_valid.py
@@ -0,0 +1,40 @@
+# vim: tabstop=4 shiftwidth=4 softtabstop=4
+
+# Copyright 2012 OpenStack LLC
+#
+# Licensed under the Apache License, Version 2.0 (the "License"); you may
+# not use this file except in compliance with the License. You may obtain
+# a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations
+# under the License.
+
+
+from migrate import *
+from sqlalchemy import *
+
+
+from keystone.common import sql
+
+
+def upgrade(migrate_engine):
+    # Upgrade operations go here. Don't create your own engine; bind
+
+    meta = MetaData()
+    meta.bind = migrate_engine
+    dialect = migrate_engine.url.get_dialect().name
+    token = Table('token', meta, autoload=True)
+    valid = Column("valid", Boolean(), ColumnDefault(True), nullable=False)
+    token.create_column(valid)
+
+
+def downgrade(migrate_engine):
+    meta = MetaData()
+    meta.bind = migrate_engine
+    token = Table('token', meta, autoload=True)
+    token.drop_column('valid')
diff --git a/keystone/common/utils.py b/keystone/common/utils.py
index 19749764..a8e50dfe 100644
--- a/keystone/common/utils.py
+++ b/keystone/common/utils.py
@@ -263,3 +263,9 @@ def auth_str_equal(provided, known):
         b = ord(known[i]) if i < k_len else 0
         result |= a ^ b
     return (p_len == k_len) & (result == 0)
+
+
+def hash_signed_token(signed_text):
+    hash_ = hashlib.md5()
+    hash_.update(signed_text)
+    return hash_.hexdigest()
diff --git a/keystone/config.py b/keystone/config.py
index 04839f13..4a8b2c1a 100644
--- a/keystone/config.py
+++ b/keystone/config.py
@@ -125,8 +125,8 @@ register_str('keyfile', group='ssl', default=None)
 register_str('ca_certs', group='ssl', default=None)
 register_bool('cert_required', group='ssl', default=False)
 #signing options
-register_bool('disable_pki', group='signing',
-              default=True)
+register_str('token_format', group='signing',
+             default="UUID")
 register_str('certfile', group='signing',
              default="/etc/keystone/ssl/certs/signing_cert.pem")
 register_str('keyfile', group='signing',
diff --git a/keystone/middleware/auth_token.py b/keystone/middleware/auth_token.py
index 75ab67c7..ef449c67 100644
--- a/keystone/middleware/auth_token.py
+++ b/keystone/middleware/auth_token.py
@@ -93,6 +93,7 @@ HTTP_X_ROLE
 
 """
 
+import datetime
 import httplib
 import json
 import logging
@@ -105,6 +106,8 @@ import webob.exc
 
 from keystone.openstack.common import jsonutils
 from keystone.common import cms
+from keystone.common import utils
+from keystone.openstack.common import timeutils
 
 LOG = logging.getLogger(__name__)
 
@@ -172,6 +175,8 @@ class AuthProtocol(object):
         self.signing_cert_file_name = val
         val = '%s/cacert.pem' % self.signing_dirname
         self.ca_file_name = val
+        val = '%s/revoked.pem' % self.signing_dirname
+        self.revoked_file_name = val
 
         # Credentials used to verify this component with the Auth service since
         # validating tokens is a privileged call
@@ -186,6 +191,10 @@ class AuthProtocol(object):
         memcache_servers = conf.get('memcache_servers')
         # By default the token will be cached for 5 minutes
         self.token_cache_time = conf.get('token_cache_time', 300)
+        self._token_revocation_list = None
+        self._token_revocation_list_fetched_time = None
+        self.token_revocation_list_cache_timeout = \
+            datetime.timedelta(seconds=0)
         if memcache_servers:
             try:
                 import memcache
@@ -418,6 +427,7 @@ class AuthProtocol(object):
             self._cache_put(user_token, data)
             return data
         except Exception as e:
+            LOG.debug('Token validation failure.', exc_info=True)
             self._cache_store_invalid(user_token)
             LOG.warn("Authorization failed for token %s", user_token)
             raise InvalidUserToken('Token authorization failed')
@@ -618,19 +628,30 @@ class AuthProtocol(object):
 
             raise InvalidUserToken()
 
-    def verify_signed_token(self, signed_text):
-        """
-            Converts a block of Base64 encoding to strict PEM format
-            and verifies the signature of the contensts IAW CMS syntax
-            If either of the certificate files are missing, fetch them
-            and retry
+    def is_signed_token_revoked(self, signed_text):
+        """Indicate whether the token appears in the revocation list."""
+        revocation_list = self.token_revocation_list
+        revoked_tokens = revocation_list.get('revoked', [])
+        if not revoked_tokens:
+            return
+        revoked_ids = (x['id'] for x in revoked_tokens)
+        token_id = utils.hash_signed_token(signed_text)
+        for revoked_id in revoked_ids:
+            if token_id == revoked_id:
+                LOG.debug('Token %s is marked as having been revoked',
+                          token_id)
+                return True
+        return False
+
+    def cms_verify(self, data):
+        """Verifies the signature of the provided data's IAW CMS syntax.
+
+        If either of the certificate files are missing, fetch them and
+        retry.
         """
-
-        formatted = cms.token_to_cms(signed_text)
-
         while True:
             try:
-                output = cms.cms_verify(formatted, self.signing_cert_file_name,
+                output = cms.cms_verify(data, self.signing_cert_file_name,
                                         self.ca_file_name)
             except subprocess.CalledProcessError as err:
                 if self.cert_file_missing(err, self.signing_cert_file_name):
@@ -642,6 +663,64 @@ class AuthProtocol(object):
                 raise err
             return output
 
+    def verify_signed_token(self, signed_text):
+        """Check that the token is unrevoked and has a valid signature."""
+        if self.is_signed_token_revoked(signed_text):
+            raise InvalidUserToken('Token has been revoked')
+
+        formatted = cms.token_to_cms(signed_text)
+        return self.cms_verify(formatted)
+
+    @property
+    def token_revocation_list_fetched_time(self):
+        if not self._token_revocation_list_fetched_time:
+            # If the fetched list has been written to disk, use its
+            # modification time.
+            if os.path.exists(self.revoked_file_name):
+                mtime = os.path.getmtime(self.revoked_file_name)
+                fetched_time = datetime.datetime.fromtimestamp(mtime)
+            # Otherwise the list will need to be fetched.
+            else:
+                fetched_time = datetime.datetime.min
+            self._token_revocation_list_fetched_time = fetched_time
+        return self._token_revocation_list_fetched_time
+
+    @token_revocation_list_fetched_time.setter
+    def token_revocation_list_fetched_time(self, value):
+        self._token_revocation_list_fetched_time = value
+
+    @property
+    def token_revocation_list(self):
+        timeout = self.token_revocation_list_fetched_time +\
+            self.token_revocation_list_cache_timeout
+        list_is_current = timeutils.utcnow() < timeout
+        if list_is_current:
+            # Load the list from disk if required
+            if not self._token_revocation_list:
+                with open(self.revoked_file_name, 'r') as f:
+                    self._token_revocation_list = jsonutils.loads(f.read())
+        else:
+            self.token_revocation_list = self.fetch_revocation_list()
+        return self._token_revocation_list
+
+    @token_revocation_list.setter
+    def token_revocation_list(self, value):
+        """Save a revocation list to memory and to disk.
+
+        :param value: A json-encoded revocation list
+
+        """
+        self._token_revocation_list = jsonutils.loads(value)
+        self.token_revocation_list_fetched_time = timeutils.utcnow()
+        with open(self.revoked_file_name, 'w') as f:
+            f.write(value)
+
+    def fetch_revocation_list(self):
+        response, data = self._http_request('GET', '/v2.0/tokens/revoked')
+        if response.status != 200:
+            raise ServiceError('Unable to fetch token revocation list.')
+        return self.cms_verify(data)
+
     def fetch_signing_cert(self):
         response, data = self._http_request('GET',
                                             '/v2.0/certificates/signing')
diff --git a/keystone/service.py b/keystone/service.py
index 0ee34e88..91442621 100644
--- a/keystone/service.py
+++ b/keystone/service.py
@@ -48,6 +48,10 @@ class AdminRouter(wsgi.ComposingRouter):
                        controller=auth_controller,
                        action='authenticate',
                        conditions=dict(method=['POST']))
+        mapper.connect('/tokens/revoked',
+                       controller=auth_controller,
+                       action='revocation_list',
+                       conditions=dict(method=['GET']))
         mapper.connect('/tokens/{token_id}',
                        controller=auth_controller,
                        action='validate_token',
@@ -429,13 +433,18 @@ class TokenController(wsgi.Application):
         service_catalog = self._format_catalog(catalog_ref)
         token_data['access']['serviceCatalog'] = service_catalog
 
-        if config.CONF.signing.disable_pki:
+        if config.CONF.signing.token_format == "UUID":
             token_id = uuid.uuid4().hex
-        else:
-            token_id = cms.cms_sign_text(json.dumps(token_data),
-                                         config.CONF.signing.certfile,
-                                         config.CONF.signing.keyfile)
+        elif config.CONF.signing.token_format == "PKI":
 
+            token_id = cms.cms_sign_token(json.dumps(token_data),
+                                          config.CONF.signing.certfile,
+                                          config.CONF.signing.keyfile)
+        else:
+            raise exception.UnexpectedError(
+                "Invalid value for token_format: %s."
+                "  Allowed values are PKI or UUID." %
+                config.CONF.signing.token_format)
         try:
             self.token_api.create_token(
                 context, token_id, dict(key=token_id,
@@ -526,9 +535,24 @@ class TokenController(wsgi.Application):
         """Delete a token, effectively invalidating it for authz."""
         # TODO(termie): this stuff should probably be moved to middleware
         self.assert_admin(context)
-
         self.token_api.delete_token(context=context, token_id=token_id)
 
+    def revocation_list(self, context, auth=None):
+        self.assert_admin(context)
+        tokens = self.token_api.list_revoked_tokens(context)
+
+        for t in tokens:
+            expires = t['expires']
+            if not (expires and isinstance(expires, unicode)):
+                    t['expires'] = timeutils.isotime(expires)
+        data = {'revoked': tokens}
+        json_data = json.dumps(data)
+        signed_text = cms.cms_sign_text(json_data,
+                                        config.CONF.signing.certfile,
+                                        config.CONF.signing.keyfile)
+
+        return signed_text
+
     def endpoints(self, context, token_id):
         """Return a list of endpoints available to the token."""
         raise exception.NotImplemented()
diff --git a/keystone/token/backends/kvs.py b/keystone/token/backends/kvs.py
index 442bd4b8..98d7936e 100644
--- a/keystone/token/backends/kvs.py
+++ b/keystone/token/backends/kvs.py
@@ -23,6 +23,7 @@ from keystone import token
 
 
 class Token(kvs.Base, token.Driver):
+
     # Public interface
     def get_token(self, token_id):
         try:
@@ -30,7 +31,7 @@ class Token(kvs.Base, token.Driver):
         except exception.NotFound:
             raise exception.TokenNotFound(token_id=token_id)
         if token['expires'] is None or token['expires'] > timeutils.utcnow():
-            return token
+            return copy.deepcopy(token)
         else:
             raise exception.TokenNotFound(token_id=token_id)
 
@@ -43,7 +44,9 @@ class Token(kvs.Base, token.Driver):
 
     def delete_token(self, token_id):
         try:
+            token_ref = self.get_token(token_id)
             self.db.delete('token-%s' % token_id)
+            self.db.set('revoked-token-%s' % token_id, token_ref)
         except exception.NotFound:
             raise exception.TokenNotFound(token_id=token_id)
 
@@ -61,3 +64,14 @@ class Token(kvs.Base, token.Driver):
                 continue
             tokens.append(token.split('-', 1)[1])
         return tokens
+
+    def list_revoked_tokens(self):
+        tokens = []
+        for token, token_ref in self.db.items():
+            if not token.startswith('revoked-token-'):
+                continue
+            record = {}
+            record['id'] = token_ref['id']
+            record['expires'] = token_ref['expires']
+            tokens.append(record)
+        return tokens
diff --git a/keystone/token/backends/memcache.py b/keystone/token/backends/memcache.py
index df4dcdc3..b5cae2a0 100644
--- a/keystone/token/backends/memcache.py
+++ b/keystone/token/backends/memcache.py
@@ -22,6 +22,7 @@ import memcache
 from keystone.common import utils
 from keystone import config
 from keystone import exception
+from keystone.openstack.common import jsonutils
 from keystone import token
 
 
@@ -30,6 +31,9 @@ config.register_str('servers', group='memcache', default='localhost:11211')
 
 
 class Token(token.Driver):
+
+    revocation_key = 'revocation-list'
+
     def __init__(self, client=None):
         self._memcache_client = client
 
@@ -65,8 +69,25 @@ class Token(token.Driver):
         self.client.set(ptk, data_copy, **kwargs)
         return copy.deepcopy(data_copy)
 
+    def _add_to_revocation_list(self, data):
+        data_json = jsonutils.dumps(data)
+        if not self.client.append(self.revocation_key, ',%s' % data_json):
+            if not self.client.add(self.revocation_key, data_json):
+                if not self.client.append(self.revocation_key,
+                                          ',%s' % data_json):
+                    msg = _('Unable to add token to revocation list.')
+                    raise exception.UnexpectedError(msg)
+
     def delete_token(self, token_id):
         # Test for existence
-        self.get_token(token_id)
+        data = self.get_token(token_id)
         ptk = self._prefix_token_id(token_id)
-        return self.client.delete(ptk)
+        result = self.client.delete(ptk)
+        self._add_to_revocation_list(data)
+        return result
+
+    def list_revoked_tokens(self):
+        list_json = self.client.get(self.revocation_key)
+        if list_json:
+            return jsonutils.loads('[%s]' % list_json)
+        return []
diff --git a/keystone/token/backends/sql.py b/keystone/token/backends/sql.py
index fa0dbb76..5816162d 100644
--- a/keystone/token/backends/sql.py
+++ b/keystone/token/backends/sql.py
@@ -31,6 +31,7 @@ class TokenModel(sql.ModelBase, sql.DictBase):
     id = sql.Column(sql.String(1024))
     expires = sql.Column(sql.DateTime(), default=None)
     extra = sql.Column(sql.JsonBlob())
+    valid = sql.Column(sql.Boolean(), default=True)
 
     @classmethod
     def from_dict(cls, token_dict):
@@ -55,7 +56,8 @@ class Token(sql.Base, token.Driver):
     def get_token(self, token_id):
         session = self.get_session()
         token_ref = session.query(TokenModel)\
-            .filter_by(id_hash=self.token_to_key(token_id)).first()
+            .filter_by(id_hash=self.token_to_key(token_id),
+                       valid=True).first()
         now = datetime.datetime.utcnow()
         if token_ref and (not token_ref.expires or now < token_ref.expires):
             return token_ref.to_dict()
@@ -77,6 +79,7 @@ class Token(sql.Base, token.Driver):
 
         token_ref = TokenModel.from_dict(data_copy)
         token_ref.id_hash = self.token_to_key(token_id)
+        token_ref.valid = True
         session = self.get_session()
         with session.begin():
             session.add(token_ref)
@@ -85,15 +88,13 @@ class Token(sql.Base, token.Driver):
 
     def delete_token(self, token_id):
         session = self.get_session()
-        token_ref = session.query(TokenModel)\
-                           .filter_by(id_hash=self.token_to_key(token_id))\
-                           .first()
-        if not token_ref:
-            raise exception.TokenNotFound(token_id=token_id)
-
+        key = self.token_to_key(token_id)
         with session.begin():
-            if not session.query(TokenModel).filter_by(id=token_id).delete():
+            token_ref = session.query(TokenModel).filter_by(id=key,
+                                                            valid=True).first()
+            if not token_ref:
                 raise exception.TokenNotFound(token_id=token_id)
+            token_ref.valid = False
             session.flush()
 
     def list_tokens(self, user_id):
@@ -101,7 +102,8 @@ class Token(sql.Base, token.Driver):
         tokens = []
         now = timeutils.utcnow()
         for token_ref in session.query(TokenModel)\
-                                .filter(TokenModel.expires > now):
+                                .filter(TokenModel.expires > now)\
+                                .filter_by(valid=True):
             token_ref_dict = token_ref.to_dict()
             if 'user' not in token_ref_dict:
                 continue
@@ -109,3 +111,18 @@ class Token(sql.Base, token.Driver):
                 continue
             tokens.append(token_ref['id'])
         return tokens
+
+    def list_revoked_tokens(self):
+        session = self.get_session()
+        tokens = []
+        now = timeutils.utcnow()
+        for token_ref in session.query(TokenModel)\
+                                .filter(TokenModel.expires > now)\
+                                .filter_by(valid=False):
+            token_ref_dict = token_ref.to_dict()
+            record = {
+                'id': token_ref['id'],
+                'expires': token_ref['expires'],
+            }
+            tokens.append(record)
+        return tokens
diff --git a/keystone/token/core.py b/keystone/token/core.py
index aff59fba..d6e9d38d 100644
--- a/keystone/token/core.py
+++ b/keystone/token/core.py
@@ -98,6 +98,14 @@ class Driver(object):
         """
         raise exception.NotImplemented()
 
+    def list_revoked_tokens(self):
+        """Returns a list of all revoked tokens
+
+        :returns: list of token_id's
+
+        """
+        raise exception.NotImplemented()
+
     def _get_default_expire_time(self):
         """Determine when a token should expire based on the config.
 
diff --git a/tests/signing/Makefile b/tests/signing/Makefile
new file mode 100644
index 00000000..b56c0008
--- /dev/null
+++ b/tests/signing/Makefile
@@ -0,0 +1,34 @@
+# vim: tabstop=4 shiftwidth=4 softtabstop=4
+
+# Copyright 2012 Red Hat,. Inc
+
+#
+# Licensed under the Apache License, Version 2.0 (the "License"); you may
+# not use this file except in compliance with the License. You may obtain
+# a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations
+# under the License.
+
+
+
+.SUFFIXES:  .json .pem
+
+SOURCES=auth_token_unscoped.json auth_token_scoped.json revocation_list.json
+SIGNED=$(SOURCES:.json=.pem)
+TARGETS=$(SIGNED)
+
+all: $(TARGETS)
+clean:
+	rm -f $(TARGETS) *~
+
+.json.pem :
+	openssl cms  -sign -in $<  -nosmimecap  -signer signing_cert.pem -inkey private_key.pem -outform PEM -nodetach -nocerts  -noattr -out $@
+
+
+
diff --git a/tests/signing/README b/tests/signing/README
index 7fba97df..c8e5eae4 100644
--- a/tests/signing/README
+++ b/tests/signing/README
@@ -1,4 +1,11 @@
-auth_token.pem was constructed using the following command
+The commands to create the various pem files for the signed tokens and
+revocation list were generated by the associated make file.
 
-openssl cms  -sign -in auth_token.json  -nosmimecap  -signer signing_cert.pem -inkey private_key.pem -outform PEM -nodetach -nocerts  -noattr -out auth_token.pem
+The hashed value in the revocation list was generated using the revoked token using
+the following python code
 
+from keystone.common import cms,utils
+f=open("tests/signing/auth_token_revoked.pem","r")
+r=f.read()
+utils.hash_signed_token(cms.cms_to_token(r))
+f.close()
diff --git a/tests/signing/auth_token_revoked.json b/tests/signing/auth_token_revoked.json
new file mode 100644
index 00000000..92c6922c
--- /dev/null
+++ b/tests/signing/auth_token_revoked.json
@@ -0,0 +1 @@
+{"access": {"serviceCatalog": [{"endpoints": [{"adminURL": "http://127.0.0.1:8776/v1/64b6f3fbcc53435e8a60fcf89bb6617a", "region": "regionOne", "internalURL": "http://127.0.0.1:8776/v1/64b6f3fbcc53435e8a60fcf89bb6617a", "publicURL": "http://127.0.0.1:8776/v1/64b6f3fbcc53435e8a60fcf89bb6617a"}], "endpoints_links": [], "type": "volume", "name": "volume"}, {"endpoints": [{"adminURL": "http://127.0.0.1:9292/v1", "region": "regionOne", "internalURL": "http://127.0.0.1:9292/v1", "publicURL": "http://127.0.0.1:9292/v1"}], "endpoints_links": [], "type": "image", "name": "glance"}, {"endpoints": [{"adminURL": "http://127.0.0.1:8774/v1.1/64b6f3fbcc53435e8a60fcf89bb6617a", "region": "regionOne", "internalURL": "http://127.0.0.1:8774/v1.1/64b6f3fbcc53435e8a60fcf89bb6617a", "publicURL": "http://127.0.0.1:8774/v1.1/64b6f3fbcc53435e8a60fcf89bb6617a"}], "endpoints_links": [], "type": "compute", "name": "nova"}, {"endpoints": [{"adminURL": "http://127.0.0.1:35357/v2.0", "region": "RegionOne", "internalURL": "http://127.0.0.1:35357/v2.0", "publicURL": "http://127.0.0.1:5000/v2.0"}], "endpoints_links": [], "type": "identity", "name": "keystone"}],"token": {"expires": "2012-06-02T14:47:34Z", "id": "placeholder", "tenant": {"enabled": true, "description": null, "name": "tenant_name1", "id": "tenant_id1"}}, "user": {"username": "revoked_username1", "roles_links": ["role1","role2"], "id": "revoked_user_id1", "roles": [{"name": "role1"}, {"name": "role2"}], "name": "revoked_username1"}}}
diff --git a/tests/signing/auth_token_revoked.pem b/tests/signing/auth_token_revoked.pem
new file mode 100644
index 00000000..186c0800
--- /dev/null
+++ b/tests/signing/auth_token_revoked.pem
@@ -0,0 +1,40 @@
+-----BEGIN CMS-----
+MIIHAwYJKoZIhvcNAQcCoIIG9DCCBvACAQExCTAHBgUrDgMCGjCCBeQGCSqGSIb3
+DQEHAaCCBdUEggXReyJhY2Nlc3MiOiB7InNlcnZpY2VDYXRhbG9nIjogW3siZW5k
+cG9pbnRzIjogW3siYWRtaW5VUkwiOiAiaHR0cDovLzEyNy4wLjAuMTo4Nzc2L3Yx
+LzY0YjZmM2ZiY2M1MzQzNWU4YTYwZmNmODliYjY2MTdhIiwgInJlZ2lvbiI6ICJy
+ZWdpb25PbmUiLCAiaW50ZXJuYWxVUkwiOiAiaHR0cDovLzEyNy4wLjAuMTo4Nzc2
+L3YxLzY0YjZmM2ZiY2M1MzQzNWU4YTYwZmNmODliYjY2MTdhIiwgInB1YmxpY1VS
+TCI6ICJodHRwOi8vMTI3LjAuMC4xOjg3NzYvdjEvNjRiNmYzZmJjYzUzNDM1ZThh
+NjBmY2Y4OWJiNjYxN2EifV0sICJlbmRwb2ludHNfbGlua3MiOiBbXSwgInR5cGUi
+OiAidm9sdW1lIiwgIm5hbWUiOiAidm9sdW1lIn0sIHsiZW5kcG9pbnRzIjogW3si
+YWRtaW5VUkwiOiAiaHR0cDovLzEyNy4wLjAuMTo5MjkyL3YxIiwgInJlZ2lvbiI6
+ICJyZWdpb25PbmUiLCAiaW50ZXJuYWxVUkwiOiAiaHR0cDovLzEyNy4wLjAuMTo5
+MjkyL3YxIiwgInB1YmxpY1VSTCI6ICJodHRwOi8vMTI3LjAuMC4xOjkyOTIvdjEi
+fV0sICJlbmRwb2ludHNfbGlua3MiOiBbXSwgInR5cGUiOiAiaW1hZ2UiLCAibmFt
+ZSI6ICJnbGFuY2UifSwgeyJlbmRwb2ludHMiOiBbeyJhZG1pblVSTCI6ICJodHRw
+Oi8vMTI3LjAuMC4xOjg3NzQvdjEuMS82NGI2ZjNmYmNjNTM0MzVlOGE2MGZjZjg5
+YmI2NjE3YSIsICJyZWdpb24iOiAicmVnaW9uT25lIiwgImludGVybmFsVVJMIjog
+Imh0dHA6Ly8xMjcuMC4wLjE6ODc3NC92MS4xLzY0YjZmM2ZiY2M1MzQzNWU4YTYw
+ZmNmODliYjY2MTdhIiwgInB1YmxpY1VSTCI6ICJodHRwOi8vMTI3LjAuMC4xOjg3
+NzQvdjEuMS82NGI2ZjNmYmNjNTM0MzVlOGE2MGZjZjg5YmI2NjE3YSJ9XSwgImVu
+ZHBvaW50c19saW5rcyI6IFtdLCAidHlwZSI6ICJjb21wdXRlIiwgIm5hbWUiOiAi
+bm92YSJ9LCB7ImVuZHBvaW50cyI6IFt7ImFkbWluVVJMIjogImh0dHA6Ly8xMjcu
+MC4wLjE6MzUzNTcvdjIuMCIsICJyZWdpb24iOiAiUmVnaW9uT25lIiwgImludGVy
+bmFsVVJMIjogImh0dHA6Ly8xMjcuMC4wLjE6MzUzNTcvdjIuMCIsICJwdWJsaWNV
+UkwiOiAiaHR0cDovLzEyNy4wLjAuMTo1MDAwL3YyLjAifV0sICJlbmRwb2ludHNf
+bGlua3MiOiBbXSwgInR5cGUiOiAiaWRlbnRpdHkiLCAibmFtZSI6ICJrZXlzdG9u
+ZSJ9XSwidG9rZW4iOiB7ImV4cGlyZXMiOiAiMjAxMi0wNi0wMlQxNDo0NzozNFoi
+LCAiaWQiOiAicGxhY2Vob2xkZXIiLCAidGVuYW50IjogeyJlbmFibGVkIjogdHJ1
+ZSwgImRlc2NyaXB0aW9uIjogbnVsbCwgIm5hbWUiOiAidGVuYW50X25hbWUxIiwg
+ImlkIjogInRlbmFudF9pZDEifX0sICJ1c2VyIjogeyJ1c2VybmFtZSI6ICJyZXZv
+a2VkX3VzZXJuYW1lMSIsICJyb2xlc19saW5rcyI6IFsicm9sZTEiLCJyb2xlMiJd
+LCAiaWQiOiAicmV2b2tlZF91c2VyX2lkMSIsICJyb2xlcyI6IFt7Im5hbWUiOiAi
+cm9sZTEifSwgeyJuYW1lIjogInJvbGUyIn1dLCAibmFtZSI6ICJyZXZva2VkX3Vz
+ZXJuYW1lMSJ9fX0NCjGB9zCB9AIBATBUME8xFTATBgNVBAoTDFJlZCBIYXQsIElu
+YzERMA8GA1UEBxMIV2VzdGZvcmQxFjAUBgNVBAgTDU1hc3NhY2h1c2V0dHMxCzAJ
+BgNVBAYTAlVTAgEBMAcGBSsOAwIaMA0GCSqGSIb3DQEBAQUABIGAXstA+yZ5N/cS
++i7Mmlhi585cckvwSVAGj9huPTpqBItpbO44+U3yUojEwcghomtpygI/wzUa8Z40
+UW/L3nGlATlOG833zhGvLKrp76GIitYMgk1e0OEmzGXeAWLnQZFev8ooMPs9rwYW
+MgEdAfDMWWqX+Tb7exdboLpRUiCQx1c=
+-----END CMS-----
diff --git a/tests/signing/auth_token.json b/tests/signing/auth_token_scoped.json
index 16eb644f..16eb644f 100644
--- a/tests/signing/auth_token.json
+++ b/tests/signing/auth_token_scoped.json
diff --git a/tests/signing/auth_token.pem b/tests/signing/auth_token_scoped.pem
index 42146a9a..42146a9a 100644
--- a/tests/signing/auth_token.pem
+++ b/tests/signing/auth_token_scoped.pem
diff --git a/tests/signing/auth_token_unscoped.json b/tests/signing/auth_token_unscoped.json
new file mode 100644
index 00000000..b2340a76
--- /dev/null
+++ b/tests/signing/auth_token_unscoped.json
@@ -0,0 +1 @@
+{"access": {"token": {"expires": "2012-08-17T15:35:34Z", "id": "01e032c996ef4406b144335915a41e79"}, "serviceCatalog": {}, "user": {"username": "user_name1", "roles_links": [], "id": "c9c89e3be3ee453fbf00c7966f6d3fbd", "roles": [{'name': 'role1'},{'name': 'role2'},], "name": "user_name1"}}}
\ No newline at end of file
diff --git a/tests/signing/auth_token_unscoped.pem b/tests/signing/auth_token_unscoped.pem
new file mode 100644
index 00000000..771239b4
--- /dev/null
+++ b/tests/signing/auth_token_unscoped.pem
@@ -0,0 +1,14 @@
+-----BEGIN CMS-----
+MIICLwYJKoZIhvcNAQcCoIICIDCCAhwCAQExCTAHBgUrDgMCGjCCARAGCSqGSIb3
+DQEHAaCCAQEEgf57ImFjY2VzcyI6IHsidG9rZW4iOiB7ImV4cGlyZXMiOiAiMjAx
+Mi0wOC0xN1QxNTozNTozNFoiLCAiaWQiOiAiMDFlMDMyYzk5NmVmNDQwNmIxNDQz
+MzU5MTVhNDFlNzkifSwgInNlcnZpY2VDYXRhbG9nIjoge30sICJ1c2VyIjogeyJ1
+c2VybmFtZSI6ICJ1c2VyX25hbWUxIiwgInJvbGVzX2xpbmtzIjogW10sICJpZCI6
+ICJjOWM4OWUzYmUzZWU0NTNmYmYwMGM3OTY2ZjZkM2ZiZCIsICJyb2xlcyI6IFtd
+LCAibmFtZSI6ICJ1c2VyX25hbWUxIn19fTGB9zCB9AIBATBUME8xFTATBgNVBAoT
+DFJlZCBIYXQsIEluYzERMA8GA1UEBxMIV2VzdGZvcmQxFjAUBgNVBAgTDU1hc3Nh
+Y2h1c2V0dHMxCzAJBgNVBAYTAlVTAgEBMAcGBSsOAwIaMA0GCSqGSIb3DQEBAQUA
+BIGAisEcxeNzNYbZPuWEEL+0SRAHjfaSFuhDHAAZ67P6LkoSN8IAio+2fqH2d1Ix
+qfUYBW/cVEYdEZ3itbR0KdDucemHFpows+eZVUe6nsV7hgMqXBmfrKyEC4PBuIoI
+/nofrwbV/R88v1jAIyrB3IbPUydXDK79lThL47rcGCeOuwI=
+-----END CMS-----
diff --git a/tests/signing/revocation_list.json b/tests/signing/revocation_list.json
new file mode 100644
index 00000000..c3401b0f
--- /dev/null
+++ b/tests/signing/revocation_list.json
@@ -0,0 +1 @@
+{"revoked":[{"id":"7acfcfdaf6a14aebe97c61c5947bc4d3","expires":"2012-08-14T17:58:48Z"}]}
diff --git a/tests/signing/revocation_list.pem b/tests/signing/revocation_list.pem
new file mode 100644
index 00000000..ad7a96f3
--- /dev/null
+++ b/tests/signing/revocation_list.pem
@@ -0,0 +1,11 @@
+-----BEGIN CMS-----
+MIIBhgYJKoZIhvcNAQcCoIIBdzCCAXMCAQExCTAHBgUrDgMCGjBpBgkqhkiG9w0B
+BwGgXARaeyJyZXZva2VkIjpbeyJpZCI6IjdhY2ZjZmRhZjZhMTRhZWJlOTdjNjFj
+NTk0N2JjNGQzIiwiZXhwaXJlcyI6IjIwMTItMDgtMTRUMTc6NTg6NDhaIn1dfQ0K
+MYH3MIH0AgEBMFQwTzEVMBMGA1UEChMMUmVkIEhhdCwgSW5jMREwDwYDVQQHEwhX
+ZXN0Zm9yZDEWMBQGA1UECBMNTWFzc2FjaHVzZXR0czELMAkGA1UEBhMCVVMCAQEw
+BwYFKw4DAhowDQYJKoZIhvcNAQEBBQAEgYCVDgl1puOfsn2BNliKnHNsSucYI3xn
+aJvZ8UM2hg+TGgshMPhNjo1/p1VBqwyIb0+AAUnFj7fikCNE6dypvT+xX/vUgGnv
+4EJ2cqG/0PFB/8B6Tz3FSsFMhXUIRnXKKxLxMCkge1b072BapJ1FJm8sXSem5ecO
+adoOjW3kjFJk/A==
+-----END CMS-----
diff --git a/tests/test_auth_token_middleware.py b/tests/test_auth_token_middleware.py
index dc5760ca..07217dcf 100644
--- a/tests/test_auth_token_middleware.py
+++ b/tests/test_auth_token_middleware.py
@@ -15,25 +15,62 @@
 # under the License.
 
 import datetime
+import hashlib
 import iso8601
+import os
+import string
+import tempfile
+
 import webob
 
+from keystone.common import cms
+from keystone.common import utils
 from keystone.middleware import auth_token
 from keystone.openstack.common import jsonutils
+from keystone.openstack.common import timeutils
 from keystone import config
 from keystone import test
 
 
-# JSON responses keyed by token ID
-TOKEN_RESPONSES = {
-    'valid-token': {
+#The data for these tests are signed using openssl and are stored in files
+# in the signing subdirectory.  IN order to keep the values consistent between
+# the tests and the signed documents, we read them in for use in the tests.
+def setUpModule(self):
+    signing_path = os.path.join(os.path.dirname(__file__), 'signing')
+    with open(os.path.join(signing_path, 'auth_token_scoped.pem')) as f:
+        self.SIGNED_TOKEN_SCOPED = cms.cms_to_token(f.read())
+    with open(os.path.join(signing_path, 'auth_token_unscoped.pem')) as f:
+        self.SIGNED_TOKEN_UNSCOPED = cms.cms_to_token(f.read())
+    with open(os.path.join(signing_path, 'auth_token_revoked.pem')) as f:
+        self.REVOKED_TOKEN = cms.cms_to_token(f.read())
+    self.REVOKED_TOKEN_HASH = utils.hash_signed_token(self.REVOKED_TOKEN)
+    with open(os.path.join(signing_path, 'revocation_list.json')) as f:
+        self.REVOCATION_LIST = jsonutils.loads(f.read())
+    with open(os.path.join(signing_path, 'revocation_list.pem')) as f:
+        self.SIGNED_REVOCATION_LIST = f.read()
+
+    self.TOKEN_RESPONSES[self.SIGNED_TOKEN_SCOPED] = {
         'access': {
             'token': {
-                'id': 'valid-token',
-                'tenant': {
-                    'id': 'tenant_id1',
-                    'name': 'tenant_name1',
-                },
+                'id': SIGNED_TOKEN_SCOPED,
+            },
+            'user': {
+                'id': 'user_id1',
+                'name': 'user_name1',
+                'tenantId': 'tenant_id1',
+                'tenantName': 'tenant_name1',
+                'roles': [
+                    {'name': 'role1'},
+                    {'name': 'role2'},
+                ],
+            },
+        },
+    }
+
+    self.TOKEN_RESPONSES[self.SIGNED_TOKEN_UNSCOPED] = {
+        'access': {
+            'token': {
+                'id': self.SIGNED_TOKEN_UNSCOPED,
             },
             'user': {
                 'id': 'user_id1',
@@ -43,30 +80,65 @@ TOKEN_RESPONSES = {
                     {'name': 'role2'},
                 ],
             },
-            'serviceCatalog': {}
         },
     },
-    'default-tenant-token': {
+
+
+INVALID_SIGNED_TOKEN = string.replace(
+    """AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
+BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
+CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
+DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
+EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+0000000000000000000000000000000000000000000000000000000000000000
+1111111111111111111111111111111111111111111111111111111111111111
+2222222222222222222222222222222222222222222222222222222222222222
+3333333333333333333333333333333333333333333333333333333333333333
+4444444444444444444444444444444444444444444444444444444444444444
+5555555555555555555555555555555555555555555555555555555555555555
+6666666666666666666666666666666666666666666666666666666666666666
+7777777777777777777777777777777777777777777777777777777777777777
+8888888888888888888888888888888888888888888888888888888888888888
+9999999999999999999999999999999999999999999999999999999999999999
+0000000000000000000000000000000000000000000000000000000000000000
+xg==""", "\n", "")
+
+UUID_TOKEN_DEFAULT = "ec6c0710ec2f471498484c1b53ab4f9d"
+
+VALID_DIABLO_TOKEN = 'b0cf19b55dbb4f20a6ee18e6c6cf1726'
+
+UUID_TOKEN_UNSCOPED = '731f903721c14827be7b2dc912af7776'
+
+UUID_TOKEN_NO_SERVICE_CATALOG = '8286720fbe4941e69fa8241723bb02df'
+
+# JSON responses keyed by token ID
+
+TOKEN_RESPONSES = {
+    UUID_TOKEN_DEFAULT: {
         'access': {
             'token': {
-                'id': 'default-tenant-token',
+                'id': UUID_TOKEN_DEFAULT,
+                'tenant': {
+                    'id': 'tenant_id1',
+                    'name': 'tenant_name1',
+                },
             },
             'user': {
                 'id': 'user_id1',
                 'name': 'user_name1',
-                'tenantId': 'tenant_id1',
-                'tenantName': 'tenant_name1',
                 'roles': [
                     {'name': 'role1'},
                     {'name': 'role2'},
                 ],
             },
+            'serviceCatalog': {}
         },
     },
-    'valid-diablo-token': {
+    VALID_DIABLO_TOKEN: {
         'access': {
             'token': {
-                'id': 'valid-diablo-token',
+                'id': VALID_DIABLO_TOKEN,
                 'tenantId': 'tenant_id1',
             },
             'user': {
@@ -79,10 +151,10 @@ TOKEN_RESPONSES = {
             },
         },
     },
-    'unscoped-token': {
+    UUID_TOKEN_UNSCOPED: {
         'access': {
             'token': {
-                'id': 'unscoped-token',
+                'id': UUID_TOKEN_UNSCOPED,
             },
             'user': {
                 'id': 'user_id1',
@@ -94,7 +166,7 @@ TOKEN_RESPONSES = {
             },
         },
     },
-    'valid-token-no-service-catalog': {
+    UUID_TOKEN_NO_SERVICE_CATALOG: {
         'access': {
             'token': {
                 'id': 'valid-token',
@@ -123,7 +195,7 @@ class FakeMemcache(object):
         self.token_expiration = None
 
     def get(self, key):
-        data = TOKEN_RESPONSES['valid-token'].copy()
+        data = TOKEN_RESPONSES[SIGNED_TOKEN_SCOPED].copy()
         if not data or key != "tokens/%s" % (data['access']['token']['id']):
             return
         if not self.token_expiration:
@@ -180,6 +252,9 @@ class FakeHTTPConnection(object):
             if token_id in TOKEN_RESPONSES.keys():
                 status = 200
                 body = jsonutils.dumps(TOKEN_RESPONSES[token_id])
+            elif token_id == "revoked":
+                status = 200
+                body = SIGNED_REVOCATION_LIST
             else:
                 status = 404
                 body = str()
@@ -220,6 +295,7 @@ class FakeApp(object):
 
 
 class BaseAuthTokenMiddlewareTest(test.TestCase):
+
     def setUp(self, expected_env=None):
         expected_env = expected_env or {}
 
@@ -228,6 +304,7 @@ class BaseAuthTokenMiddlewareTest(test.TestCase):
             'auth_host': 'keystone.example.com',
             'auth_port': 1234,
             'auth_admin_prefix': '/testadmin',
+            'signing_dir': 'signing',
         }
 
         self.middleware = auth_token.AuthProtocol(FakeApp(expected_env), conf)
@@ -236,8 +313,21 @@ class BaseAuthTokenMiddlewareTest(test.TestCase):
 
         self.response_status = None
         self.response_headers = None
+        self.middleware.revoked_file_name = tempfile.mkstemp()[1]
+        self.middleware.token_revocation_list_cache_timeout =\
+            datetime.timedelta(days=1)
+        self.middleware.token_revocation_list = jsonutils.dumps(
+            {"revoked": [], "extra": "success"})
+
         super(BaseAuthTokenMiddlewareTest, self).setUp()
 
+    def tearDown(self):
+        super(BaseAuthTokenMiddlewareTest, self).tearDown()
+        try:
+            os.remove(self.middleware.revoked_file_name)
+        except OSError:
+            pass
+
     def start_fake_response(self, status, headers):
         self.response_status = int(status.split(' ', 1)[0])
         self.response_headers = dict(headers)
@@ -250,53 +340,149 @@ class DiabloAuthTokenMiddlewareTest(BaseAuthTokenMiddlewareTest):
         expected_env = {
             'HTTP_X_TENANT_ID': 'tenant_id1',
             'HTTP_X_TENANT_NAME': 'tenant_id1',
-            'HTTP_X_TENANT': 'tenant_id1',  # now deprecated (diablo-compat)
+            # now deprecated (diablo-compat)
+            'HTTP_X_TENANT': 'tenant_id1',
         }
         super(DiabloAuthTokenMiddlewareTest, self).setUp(expected_env)
 
-    def test_diablo_response(self):
+    def test_valid_diablo_response(self):
         req = webob.Request.blank('/')
-        req.headers['X-Auth-Token'] = 'valid-diablo-token'
+        req.headers['X-Auth-Token'] = VALID_DIABLO_TOKEN
         body = self.middleware(req.environ, self.start_fake_response)
         self.assertEqual(self.response_status, 200)
-        self.assertEqual(body, ['SUCCESS'])
 
 
 class AuthTokenMiddlewareTest(BaseAuthTokenMiddlewareTest):
-    def test_valid_request(self):
+
+    def assert_valid_request_200(self, token):
+
         req = webob.Request.blank('/')
-        req.headers['X-Auth-Token'] = 'valid-token'
+        req.headers['X-Auth-Token'] = token
         body = self.middleware(req.environ, self.start_fake_response)
-        self.assertEqual(self.middleware.conf['auth_admin_prefix'],
-                         "/testadmin")
-        self.assertEqual("/testadmin/v2.0/tokens/valid-token",
-                         FakeHTTPConnection.last_requested_url)
         self.assertEqual(self.response_status, 200)
+        catalog = req.headers.get('X-Service-Catalog')
         self.assertTrue(req.headers.get('X-Service-Catalog'))
         self.assertEqual(body, ['SUCCESS'])
 
-    def test_default_tenant_token(self):
+    def test_valid_uuid_request(self):
+        self.assert_valid_request_200(UUID_TOKEN_DEFAULT)
+        self.assertEqual("/testadmin/v2.0/tokens/%s" % UUID_TOKEN_DEFAULT,
+                         FakeHTTPConnection.last_requested_url)
+
+    def test_valid_signed_request(self):
+        FakeHTTPConnection.last_requested_url = ''
+        self.assert_valid_request_200(SIGNED_TOKEN_SCOPED)
+        self.assertEqual(self.middleware.conf['auth_admin_prefix'],
+                         "/testadmin")
+        #ensure that signed requests do not generate HTTP traffic
+        self.assertEqual('', FakeHTTPConnection.last_requested_url)
+
+    def assert_unscoped_default_tenant_auto_scopes(self, token):
         """Unscoped requests with a default tenant should "auto-scope."
 
         The implied scope is the user's tenant ID.
 
         """
         req = webob.Request.blank('/')
-        req.headers['X-Auth-Token'] = 'default-tenant-token'
+        req.headers['X-Auth-Token'] = token
         body = self.middleware(req.environ, self.start_fake_response)
         self.assertEqual(self.response_status, 200)
         self.assertEqual(body, ['SUCCESS'])
 
-    def test_unscoped_token(self):
+    def test_default_tenant_uuid_token(self):
+        self.assert_unscoped_default_tenant_auto_scopes(UUID_TOKEN_SCOPED)
+
+    def test_default_tenant_uuid_token(self):
+        self.assert_unscoped_default_tenant_auto_scopes(SIGNED_TOKEN_SCOPED)
+
+    def assert_unscoped_token_receives_401(self, token):
         """Unscoped requests with no default tenant ID should be rejected."""
         req = webob.Request.blank('/')
-        req.headers['X-Auth-Token'] = 'unscoped-token'
+        req.headers['X-Auth-Token'] = token
         self.middleware(req.environ, self.start_fake_response)
         self.assertEqual(self.response_status, 401)
         self.assertEqual(self.response_headers['WWW-Authenticate'],
                          'Keystone uri=\'https://keystone.example.com:1234\'')
 
-    def test_request_invalid_token(self):
+    def test_unscoped_uuid_token_receives_401(self):
+        self.assert_unscoped_token_receives_401(UUID_TOKEN_UNSCOPED)
+
+    def test_unscoped_pki_token_receives_401(self):
+        self.assert_unscoped_token_receives_401(SIGNED_TOKEN_UNSCOPED)
+
+    def test_revoked_token_receives_401(self):
+        self.middleware.token_revocation_list = self.get_revocation_list_json()
+        req = webob.Request.blank('/')
+        req.headers['X-Auth-Token'] = REVOKED_TOKEN
+        self.middleware(req.environ, self.start_fake_response)
+        self.assertEqual(self.response_status, 401)
+
+    def get_revocation_list_json(self, token_ids=None):
+        if token_ids is None:
+            token_ids = [REVOKED_TOKEN_HASH]
+        revocation_list = {'revoked': [{'id': x, 'expires': timeutils.utcnow()}
+                                       for x in token_ids]}
+        return jsonutils.dumps(revocation_list)
+
+    def test_is_signed_token_revoked_returns_false(self):
+        #explicitly setting an empty revocation list here to document intent
+        self.middleware.token_revocation_list = jsonutils.dumps(
+            {"revoked": [], "extra": "success"})
+        result = self.middleware.is_signed_token_revoked(REVOKED_TOKEN)
+        self.assertFalse(result)
+
+    def test_is_signed_token_revoked_returns_true(self):
+        self.middleware.token_revocation_list = self.get_revocation_list_json()
+        result = self.middleware.is_signed_token_revoked(REVOKED_TOKEN)
+        self.assertTrue(result)
+
+    def test_verify_signed_token_raises_exception_for_revoked_token(self):
+        self.middleware.token_revocation_list = self.get_revocation_list_json()
+        with self.assertRaises(auth_token.InvalidUserToken):
+            self.middleware.verify_signed_token(REVOKED_TOKEN)
+
+    def test_verify_signed_token_succeeds_for_unrevoked_token(self):
+        self.middleware.token_revocation_list = self.get_revocation_list_json()
+        self.middleware.verify_signed_token(SIGNED_TOKEN_SCOPED)
+
+    def test_get_token_revocation_list_fetched_time_returns_min(self):
+        self.middleware.token_revocation_list_fetched_time = None
+        self.middleware.revoked_file_name = ''
+        self.assertEqual(self.middleware.token_revocation_list_fetched_time,
+                         datetime.datetime.min)
+
+    def test_get_token_revocation_list_fetched_time_returns_mtime(self):
+        self.middleware.token_revocation_list_fetched_time = None
+        mtime = os.path.getmtime(self.middleware.revoked_file_name)
+        fetched_time = datetime.datetime.fromtimestamp(mtime)
+        self.assertEqual(self.middleware.token_revocation_list_fetched_time,
+                         fetched_time)
+
+    def test_get_token_revocation_list_fetched_time_returns_value(self):
+        expected = self.middleware._token_revocation_list_fetched_time
+        self.assertEqual(self.middleware.token_revocation_list_fetched_time,
+                         expected)
+
+    def test_get_revocation_list_returns_fetched_list(self):
+        self.middleware.token_revocation_list_fetched_time = None
+        os.remove(self.middleware.revoked_file_name)
+        self.assertEqual(self.middleware.token_revocation_list,
+                         REVOCATION_LIST)
+
+    def test_get_revocation_list_returns_current_list_from_memory(self):
+        self.assertEqual(self.middleware.token_revocation_list,
+                         self.middleware._token_revocation_list)
+
+    def test_get_revocation_list_returns_current_list_from_disk(self):
+        in_memory_list = self.middleware.token_revocation_list
+        self.middleware._token_revocation_list = None
+        self.assertEqual(self.middleware.token_revocation_list, in_memory_list)
+
+    def test_fetch_revocation_list(self):
+        fetched_list = jsonutils.loads(self.middleware.fetch_revocation_list())
+        self.assertEqual(fetched_list, REVOCATION_LIST)
+
+    def test_request_invalid_uuid_token(self):
         req = webob.Request.blank('/')
         req.headers['X-Auth-Token'] = 'invalid-token'
         self.middleware(req.environ, self.start_fake_response)
@@ -304,6 +490,14 @@ class AuthTokenMiddlewareTest(BaseAuthTokenMiddlewareTest):
         self.assertEqual(self.response_headers['WWW-Authenticate'],
                          'Keystone uri=\'https://keystone.example.com:1234\'')
 
+    def test_request_invalid_signed_token(self):
+        req = webob.Request.blank('/')
+        req.headers['X-Auth-Token'] = INVALID_SIGNED_TOKEN
+        self.middleware(req.environ, self.start_fake_response)
+        self.assertEqual(self.response_status, 401)
+        self.assertEqual(self.response_headers['WWW-Authenticate'],
+                         'Keystone uri=\'https://keystone.example.com:1234\'')
+
     def test_request_no_token(self):
         req = webob.Request.blank('/')
         self.middleware(req.environ, self.start_fake_response)
@@ -321,7 +515,7 @@ class AuthTokenMiddlewareTest(BaseAuthTokenMiddlewareTest):
 
     def test_memcache(self):
         req = webob.Request.blank('/')
-        req.headers['X-Auth-Token'] = 'valid-token'
+        req.headers['X-Auth-Token'] = SIGNED_TOKEN_SCOPED
         self.middleware._cache = FakeMemcache()
         self.middleware(req.environ, self.start_fake_response)
         self.assertEqual(self.middleware._cache.set_value, None)
@@ -335,7 +529,7 @@ class AuthTokenMiddlewareTest(BaseAuthTokenMiddlewareTest):
 
     def test_memcache_set_expired(self):
         req = webob.Request.blank('/')
-        req.headers['X-Auth-Token'] = 'valid-token'
+        req.headers['X-Auth-Token'] = SIGNED_TOKEN_SCOPED
         self.middleware._cache = FakeMemcache()
         expired = datetime.datetime.now() - datetime.timedelta(minutes=1)
         self.middleware._cache.token_expiration = float(expired.strftime("%s"))
@@ -357,7 +551,7 @@ class AuthTokenMiddlewareTest(BaseAuthTokenMiddlewareTest):
     def test_request_prevent_service_catalog_injection(self):
         req = webob.Request.blank('/')
         req.headers['X-Service-Catalog'] = '[]'
-        req.headers['X-Auth-Token'] = 'valid-token-no-service-catalog'
+        req.headers['X-Auth-Token'] = UUID_TOKEN_NO_SERVICE_CATALOG
         body = self.middleware(req.environ, self.start_fake_response)
         self.assertEqual(self.response_status, 200)
         self.assertFalse(req.headers.get('X-Service-Catalog'))
diff --git a/tests/test_backend.py b/tests/test_backend.py
index 66d2019f..9f60645c 100644
--- a/tests/test_backend.py
+++ b/tests/test_backend.py
@@ -647,6 +647,29 @@ class TokenTests(object):
         new_data_ref = self.token_api.get_token(token_id)
         self.assertEqual(data_ref, new_data_ref)
 
+    def check_list_revoked_tokens(self, token_ids):
+        revoked_ids = [x['id'] for x in self.token_api.list_revoked_tokens()]
+        for token_id in token_ids:
+            self.assertIn(token_id, revoked_ids)
+
+    def delete_token(self):
+        token_id = uuid.uuid4().hex
+        data = {'id_hash': token_id, 'id': token_id, 'a': 'b'}
+        data_ref = self.token_api.create_token(token_id, data)
+        self.token_api.delete_token(token_id)
+        return token_id
+
+    def test_list_revoked_tokens_returns_empty_list(self):
+        revoked_ids = [x['id'] for x in self.token_api.list_revoked_tokens()]
+        self.assertEqual(revoked_ids, [])
+
+    def test_list_revoked_tokens_for_single_token(self):
+        self.check_list_revoked_tokens([self.delete_token()])
+
+    def test_list_revoked_tokens_for_multiple_tokens(self):
+        self.check_list_revoked_tokens([self.delete_token()
+                                        for x in xrange(2)])
+
 
 class CatalogTests(object):
     def test_service_crud(self):
diff --git a/tests/test_backend_memcache.py b/tests/test_backend_memcache.py
index f18cc9ca..12e953b2 100644
--- a/tests/test_backend_memcache.py
+++ b/tests/test_backend_memcache.py
@@ -34,6 +34,18 @@ class MemcacheClient(object):
         """Ignores the passed in args."""
         self.cache = {}
 
+    def add(self, key, value):
+        if self.get(key):
+            return False
+        self.set(key, value)
+
+    def append(self, key, value):
+        existing_value = self.get(key)
+        if existing_value:
+            self.set(key, existing_value + value)
+            return True
+        return False
+
     def check_key(self, key):
         if not isinstance(key, str):
             raise memcache.Client.MemcachedStringEncodingError()
@@ -45,8 +57,6 @@ class MemcacheClient(object):
         now = utils.unixtime(timeutils.utcnow())
         if obj and (obj[1] == 0 or obj[1] > now):
             return obj[0]
-        else:
-            raise exception.TokenNotFound(token_id=key)
 
     def set(self, key, value, time=0):
         """Sets the value for a key."""