[Django] #37209: `UserAttributeSimilarityValidator` uses unordered string comparison

[Django]

#37209: `UserAttributeSimilarityValidator` uses unordered string comparison
------------------------------------------+--------------------------------
Reporter: Terence Honles | Owner: Terence Honles
Type: Bug | Status: assigned
Component: contrib.auth | Version:
Severity: Normal | Keywords:
Triage Stage: Unreviewed | Has patch: 1
Needs documentation: 0 | Needs tests: 0
Patch needs improvement: 0 | Easy pickings: 0
UI/UX: 0 |
------------------------------------------+--------------------------------
`UserAttributeSimilarityValidator` only uses the
`SequenceMatcher.quick_ratio` method (which uses an unordered comparison
of two strings and is only intended to be used as an upper bound)

This causes what I would consider "false positives" for strings that are
not actually similar (any anagram will produce a ratio of 1 (exactly
equal)).

I discovered this because we had a flaky test in our CI (with a user
having attributes generated using Faker) and I finally spent some time to
investigate the flaky test. The two strings (lowercased) were "andrews"
and "new-password", which lead me to wonder how those could be considered
70% similar.

I have added a test with the anagrams: "enumerations" & "mountaineers"
--
Ticket URL: <https://code.djangoproject.com/ticket/37209>
Django <https://code.djangoproject.com/>
The Web framework for perfectionists with deadlines.

[Django]

#37209: `UserAttributeSimilarityValidator` uses unordered string comparison

--------------------------------+------------------------------------------

Reporter: Terence Honles | Owner: Terence Honles
Type: Bug | Status: assigned
Component: contrib.auth | Version:

Severity: Normal | Resolution:

Keywords: | Triage Stage: Unreviewed
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0

--------------------------------+------------------------------------------
Changes (by Terence Honles):

* Attachment "patch.diff" added.

[Django]

#37209: `UserAttributeSimilarityValidator` uses unordered string comparison
--------------------------------+------------------------------------------
Reporter: Terence Honles | Owner: Terence Honles
Type: Bug | Status: assigned
Component: contrib.auth | Version:
Severity: Normal | Resolution:
Keywords: | Triage Stage: Unreviewed
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
--------------------------------+------------------------------------------

Comment (by Terence Honles):

The `SequenceMatcher`'s `quick_ratio` method has been used since the
validators were added to Django in v1.9
(1daae25bdcd735151de394a5578c22257e3e5dc7), and since my PR was
automatically closed, here's the same patch
--
Ticket URL: <https://code.djangoproject.com/ticket/37209#comment:1>

[Django]

#37209: `UserAttributeSimilarityValidator` uses unordered string comparison
--------------------------------+------------------------------------------
Reporter: Terence Honles | Owner: Terence Honles
Type: Bug | Status: assigned
Component: contrib.auth | Version:
Severity: Normal | Resolution:
Keywords: | Triage Stage: Unreviewed
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
--------------------------------+------------------------------------------

Comment (by SofianeB):

Can I work on this issue ?
--
Ticket URL: <https://code.djangoproject.com/ticket/37209#comment:2>

[Django]

#37209: `UserAttributeSimilarityValidator` uses unordered string comparison
--------------------------------+------------------------------------------
Reporter: Terence Honles | Owner: Terence Honles
Type: Bug | Status: assigned
Component: contrib.auth | Version:
Severity: Normal | Resolution:
Keywords: | Triage Stage: Unreviewed
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
--------------------------------+------------------------------------------

Comment (by Mike Edmunds):

SofianeB the ticket has not yet been accepted, and the original reporter
has already claimed the ticket and created a PR for if it is accepted.
(Please see Django's
[https://docs.djangoproject.com/en/dev/internals/contributing/writing-code
/submitting-patches/ guide to submitting contributions].)
--
Ticket URL: <https://code.djangoproject.com/ticket/37209#comment:3>

[Django]

#37209: `UserAttributeSimilarityValidator` uses unordered string comparison
--------------------------------+------------------------------------------
Reporter: Terence Honles | Owner: Terence Honles
Type: Bug | Status: assigned
Component: contrib.auth | Version:
Severity: Normal | Resolution:

Keywords: | Triage Stage: Accepted

Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
--------------------------------+------------------------------------------

Changes (by Mike Edmunds):

* stage: Unreviewed => Accepted

Comment:

Terence thanks for the report and PR (and for tracking down the history of
the implementation).

I'm tentatively accepting this, but there may be some additional
discussion needed about whether it constitutes a breaking change (vs. a
bug fix), whether the default `max_similarity` needs to be adjusted (was
it tuned for `quick_ratio()`?), etc.

Checking the actual `ratio()` (not just `quick_ratio()`) seems correct to
me. False positives in password validators ''decrease'' security by
frustrating users attempting to set complex passwords. (That's not my
opinion, it's
[https://pages.nist.gov/800-63-4/sp800-63b/passwords/#complexity NIST's
position].)
--
Ticket URL: <https://code.djangoproject.com/ticket/37209#comment:4>

[Django]

#37209: `UserAttributeSimilarityValidator` uses unordered string comparison
--------------------------------+------------------------------------------
Reporter: Terence Honles | Owner: Terence Honles
Type: Bug | Status: assigned
Component: contrib.auth | Version:
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
--------------------------------+------------------------------------------

Comment (by Terence Honles):

Thanks Mike, yeah I understand that this might be considered a breaking
change.

I doubt this was tuned on any significant dataset, otherwise this likely
would have been caught, but it's possible the default threshold should be
adjusted regardless.

I haven't tested it, but my assumption is the default ratio was attempting
to target 70% similarity. If that's the case I think leaving it is fine,
but if someone is not using the default then they might have a different
expectation and it may need to at least be called out in the release
notes. If there's anything else that needs to be added I can adjust my
changeset.
--
Ticket URL: <https://code.djangoproject.com/ticket/37209#comment:5>