[3.2.x] Fixed CVE-2021-45115 -- Prevented DoS vector in UserAttributeSimilarityValidator.

Thanks Chris Bailey for the report.

Co-authored-by: Adam Johnson <me@adamj.eu>

5 files changed, 78 insertions, 15 deletions

diff --git a/django/contrib/auth/password_validation.py b/django/contrib/auth/password_validation.py
index 845f4d86d5..7beb4bdc0f 100644
--- a/django/contrib/auth/password_validation.py
+++ b/django/contrib/auth/password_validation.py
@@ -115,6 +115,36 @@ class MinimumLengthValidator:
         ) % {'min_length': self.min_length}
 
 
+def exceeds_maximum_length_ratio(password, max_similarity, value):
+    """
+    Test that value is within a reasonable range of password.
+
+    The following ratio calculations are based on testing SequenceMatcher like
+    this:
+
+    for i in range(0,6):
+      print(10**i, SequenceMatcher(a='A', b='A'*(10**i)).quick_ratio())
+
+    which yields:
+
+    1 1.0
+    10 0.18181818181818182
+    100 0.019801980198019802
+    1000 0.001998001998001998
+    10000 0.00019998000199980003
+    100000 1.999980000199998e-05
+
+    This means a length_ratio of 10 should never yield a similarity higher than
+    0.2, for 100 this is down to 0.02 and for 1000 it is 0.002. This can be
+    calculated via 2 / length_ratio. As a result we avoid the potentially
+    expensive sequence matching.
+    """
+    pwd_len = len(password)
+    length_bound_similarity = max_similarity / 2 * pwd_len
+    value_len = len(value)
+    return pwd_len >= 10 * value_len and value_len < length_bound_similarity
+
+
 class UserAttributeSimilarityValidator:
     """
     Validate whether the password is sufficiently different from the user's
@@ -130,19 +160,25 @@ class UserAttributeSimilarityValidator:
 
     def __init__(self, user_attributes=DEFAULT_USER_ATTRIBUTES, max_similarity=0.7):
         self.user_attributes = user_attributes
+        if max_similarity < 0.1:
+            raise ValueError('max_similarity must be at least 0.1')
         self.max_similarity = max_similarity
 
     def validate(self, password, user=None):
         if not user:
             return
 
+        password = password.lower()
         for attribute_name in self.user_attributes:
             value = getattr(user, attribute_name, None)
             if not value or not isinstance(value, str):
                 continue
-            value_parts = re.split(r'\W+', value) + [value]
+            value_lower = value.lower()
+            value_parts = re.split(r'\W+', value_lower) + [value_lower]
             for value_part in value_parts:
-                if SequenceMatcher(a=password.lower(), b=value_part.lower()).quick_ratio() >= self.max_similarity:
+                if exceeds_maximum_length_ratio(password, self.max_similarity, value_part):
+                    continue
+                if SequenceMatcher(a=password, b=value_part).quick_ratio() >= self.max_similarity:
                     try:
                         verbose_name = str(user._meta.get_field(attribute_name).verbose_name)
                     except FieldDoesNotExist:
diff --git a/docs/releases/2.2.26.txt b/docs/releases/2.2.26.txt
index 12e9923a19..3444c491db 100644
--- a/docs/releases/2.2.26.txt
+++ b/docs/releases/2.2.26.txt
@@ -7,4 +7,16 @@ Django 2.2.26 release notes
 Django 2.2.26 fixes one security issue with severity "medium" and two security
 issues with severity "low" in 2.2.25.
 
-...
+CVE-2021-45115: Denial-of-service possibility in ``UserAttributeSimilarityValidator``
+=====================================================================================
+
+:class:`.UserAttributeSimilarityValidator` incurred significant overhead
+evaluating submitted password that were artificially large in relative to the
+comparison values. On the assumption that access to user registration was
+unrestricted this provided a potential vector for a denial-of-service attack.
+
+In order to mitigate this issue, relatively long values are now ignored by
+``UserAttributeSimilarityValidator``.
+
+This issue has severity "medium" according to the :ref:`Django security policy
+<security-disclosure>`.
diff --git a/docs/releases/3.2.11.txt b/docs/releases/3.2.11.txt
index b88f0f79ff..621139033c 100644
--- a/docs/releases/3.2.11.txt
+++ b/docs/releases/3.2.11.txt
@@ -7,4 +7,16 @@ Django 3.2.11 release notes
 Django 3.2.11 fixes one security issue with severity "medium" and two security
 issues with severity "low" in 3.2.10.
 
-...
+CVE-2021-45115: Denial-of-service possibility in ``UserAttributeSimilarityValidator``
+=====================================================================================
+
+:class:`.UserAttributeSimilarityValidator` incurred significant overhead
+evaluating submitted password that were artificially large in relative to the
+comparison values. On the assumption that access to user registration was
+unrestricted this provided a potential vector for a denial-of-service attack.
+
+In order to mitigate this issue, relatively long values are now ignored by
+``UserAttributeSimilarityValidator``.
+
+This issue has severity "medium" according to the :ref:`Django security policy
+<security-disclosure>`.
diff --git a/docs/topics/auth/passwords.txt b/docs/topics/auth/passwords.txt
index 52c90d574b..8fc4ba6ed4 100644
--- a/docs/topics/auth/passwords.txt
+++ b/docs/topics/auth/passwords.txt
@@ -539,10 +539,16 @@ Django includes four validators:
     is used: ``'username', 'first_name', 'last_name', 'email'``.
     Attributes that don't exist are ignored.
 
-    The minimum similarity of a rejected password can be set on a scale of 0 to
-    1 with the ``max_similarity`` parameter. A setting of 0 rejects all
-    passwords, whereas a setting of 1 rejects only passwords that are identical
-    to an attribute's value.
+    The maximum allowed similarity of passwords can be set on a scale of 0.1
+    to 1.0 with the ``max_similarity`` parameter. This is compared to the
+    result of :meth:`difflib.SequenceMatcher.quick_ratio`. A value of 0.1
+    rejects passwords unless they are substantially different from the
+    ``user_attributes``, whereas a value of 1.0 rejects only passwords that are
+    identical to an attribute's value.
+
+    .. versionchanged:: 2.2.26
+
+        The ``max_similarity`` parameter was limited to a minimum value of 0.1.
 
 .. class:: CommonPasswordValidator(password_list_path=DEFAULT_PASSWORD_LIST_PATH)
 
diff --git a/tests/auth_tests/test_validators.py b/tests/auth_tests/test_validators.py
index 393fbdd39c..f4aaf33052 100644
--- a/tests/auth_tests/test_validators.py
+++ b/tests/auth_tests/test_validators.py
@@ -150,13 +150,10 @@ class UserAttributeSimilarityValidatorTest(TestCase):
                 max_similarity=1,
             ).validate(user.first_name, user=user)
         self.assertEqual(cm.exception.messages, [expected_error % "first name"])
-        # max_similarity=0 rejects all passwords.
-        with self.assertRaises(ValidationError) as cm:
-            UserAttributeSimilarityValidator(
-                user_attributes=['first_name'],
-                max_similarity=0,
-            ).validate('XXX', user=user)
-        self.assertEqual(cm.exception.messages, [expected_error % "first name"])
+        # Very low max_similarity is rejected.
+        msg = 'max_similarity must be at least 0.1'
+        with self.assertRaisesMessage(ValueError, msg):
+            UserAttributeSimilarityValidator(max_similarity=0.09)
         # Passes validation.
         self.assertIsNone(
             UserAttributeSimilarityValidator(user_attributes=['first_name']).validate('testclient', user=user)