replaced nonce handling in wsgitools.digest

1 files changed, 43 insertions, 15 deletions

diff --git a/wsgitools/digest.py b/wsgitools/digest.py
index d846d54..244eb98 100755
--- a/wsgitools/digest.py
+++ b/wsgitools/digest.py
@@ -72,7 +72,8 @@ class AuthDigestMiddleware:
         self.gentoken = gentoken
         self.maxage = maxage
         self.maxuses = maxuses
-        # TODO implement better nonce-lookup (i.e. not O(n))
+        self.server_secret = ("%066X" % sysrand.getrandbits(33*8)
+                              ).decode("hex").encode("base64").strip()
         self.nonces = [] # [(creation_time, nonce_value, useage_count)]
                          # as [(float, str, int)]
 
@@ -125,6 +126,9 @@ class AuthDigestMiddleware:
                         "cnonce" not in credentials)):
                 raise AuthenticationRequired
 
+            if not self.is_nonce(credentials): # riases KeyError, ValueError
+                raise AuthenticationRequired
+
             if not self.check_nonce(credentials): # raises KeyError, ValueError
                 return self.authorization_required(environ, start_response,
                                                    stale=True) # stale nonce!
@@ -175,37 +179,61 @@ class AuthDigestMiddleware:
 
     def cleanup_nonces(self):
         """internal methods cleaning list of valid nonces"""
-        old = time.time() - self.maxage
+        # see new_nonce
+        old = "%13X" % long((time.time() - self.maxage) * 1000000)
         while self.nonces and self.nonces[0][0] < old:
             self.nonces.pop(0)
 
+    def is_nonce(self, credentials):
+        """internal method checking whether a nonce might be from this server"""
+        nonce = credentials["nonce"] # raises KeyError
+        # raises ValueError
+        nonce_time, nonce_value, nonce_hash = nonce.split(':')
+        token = "%s:%s:%s" % (nonce_time, nonce_value, self.server_secret)
+        token = md5.new(token).hexdigest()
+        return nonce_hash == token
+
     def check_nonce(self, credentials):
         """internal method checking nonce validity"""
         nonce = credentials["nonce"]
+        # raises ValueError
+        nonce_time, nonce_value, nonce_hash = nonce.split(':')
         qop = credentials.get("qop", None)
         if qop is None:
             nc = 1
         else:
             nc = long(credentials["nc"], 16) # raises KeyError, ValueError
-        for p, (nt, nv, uses) in enumerate(self.nonces):
-            if nv == nonce:
-                if uses != nc:
-                    del self.nonces[p]
-                    return False
-                if uses >= self.maxuses:
-                    del self.nonces[p]
-                else:
-                    self.nonces[p] = (nt, nv, uses+1)
-                return True
-        return False
+        # searching nonce_time
+        lower, upper = 0, len(self.nonces) - 1
+        while lower < upper:
+            mid = (lower + upper) // 2
+            if nonce_time <= self.nonces[mid][0]:
+                upper = mid
+            else:
+                lower = mid + 1
+
+        (nt, nv, uses) = self.nonces[lower]
+        if nt != nonce_time or nv != nonce_value:
+            return False
+        if nc != uses:
+            del self.nonces[lower]
+            return False
+        if uses >= self.maxuses:
+            del self.nonces[lower]
+        else:
+            self.nonces[lower] = (nt, nv, uses+1)
+        return True
 
     def new_nonce(self):
         """internal method generating a new nonce"""
-        nonce_time = time.time()
+        # 13 = (32 bit + 20 bit) / 4
+        nonce_time = "%13X" % long(time.time() * 1000000)
         randval = sysrand.getrandbits(33*8)
         nonce_value = ("%066X" % randval).decode("hex").encode("base64").strip()
         self.nonces.append((nonce_time, nonce_value, 1))
-        return nonce_value
+        token = "%s:%s:%s" % (nonce_time, nonce_value, self.server_secret)
+        token = md5.new(token).hexdigest()
+        return "%s:%s:%s" % (nonce_time, nonce_value, token)
 
     def authorization_required(self, environ, start_response, stale=False):
         """internal method implementing wsgi interface, serving 401 page"""