Skip to content

Two people, one account

Level: 301 · deep dive

One line: Any function that decides two different strings are the same person is many-to-one by construction, so it does not remove ambiguity — it creates equivalence classes, and the only real question is who owns each class.

The shape

identity(a) == identity(b)     but     a != b

Every system that lets you log in with Alice@example.com when you registered alice@example.com has one of these. It is not a bug; it is a product decision, and a good one. What makes it a vulnerability is the second half:

...and then the system acts on `a` while believing it acted on `b`

The fold merges. The action does not. Between those two lines sits every account-takeover bug on this page.

Four lines of Python, one CVE

Django, December 2019, CVE-2019-19844 ↗:

  1. Password reset looked the user up case-insensitively, which on several backends means comparing UPPER(a) = UPPER(b).
  2. ı — U+0131 LATIN SMALL LETTER DOTLESS I, an ordinary Turkish letter — uppercases to ASCII I.
  3. So mıke@example.org and mike@example.org are one row to that query.
  4. And the reset mail went to the address that was submitted, not the one on file.

Register the dotless spelling, ask for a reset, receive somebody else's token. No exploit code, no malformed input, no encoding trick — a letter that exists so that Turkish can be written down, and a fold that was doing what folds do.

The patch is the whole lesson: send the mail to the stored address. The fold may decide which account; it must never decide where the secret goes.

The canonicaliser that was the defence

Spotify, 2013. Usernames were canonicalised so that nobody could impersonate somebody else with a look-alike spelling — a defence against exactly the problem confusables and scripts is about. It worked. It also meant that registering ᴮᶦᵍᴮᶦʳᵈ in modifier letters canonicalised down onto an existing account, and the canonicalisation handed it over.

Modifier letters are compatibility-equivalent to the letters they are shrunken copies of, so any fold that includes NFKC pulls them back into the alphabet — the Python example shows NFKC alone reaching BɪgBɪrd, and a canonicaliser stronger than NFKC reaching plain bigbird. The stronger the fold, the bigger the classes, and the more accounts each class contains. There is no setting of that dial that removes the problem; there is only a choice about where it lands.

The locale that changes the alphabet

The dotless ı has a mirror image, and it is the most reliable i18n bug in the industry. In a Turkish locale, "FILE".toLowerCase() is "fıle" and "file".toUpperCase() is "FİLE" — so a comparison against "file" fails on a machine whose regional settings differ from the developer's, and a check for a forbidden filename or a header name silently stops matching.

Java's String.toLowerCase() uses the default locale; the fix is toLowerCase(Locale.ROOT). .NET's ToLower() uses the current culture; the fix is ToLowerInvariant(). Both fixes have existed for twenty years, and both bugs are still shipped, because the wrong call is the shorter one and it passes every test on the machine that wrote it.

The security reading is worth stating plainly: a fold that depends on ambient configuration is a fold an attacker may be able to change, and even where they cannot, it means two nodes of the same system can disagree about who a user is.

Truncation is a fold too

One more many-to-one map, and it is the one that does not look like one. MySQL's three-byte utf8 cannot store a four-byte character, and in a non-strict configuration the insert did not fail — it truncated at the bad byte and kept going. So admin@example.com😀.attacker.com is stored as admin@example.com, and a registration that a validator saw as a domain the attacker controls becomes, in the database, somebody else's address.

Anything that shortens a string maps many inputs to one: a column width, a VARCHAR(255), bcrypt's 72-byte input limit, a UI field that cuts a display name to fit. Each one merges identities somewhere. The rule is the same as everywhere else on this page — validate the stored form, because the stored form is the one that will be compared.

In Python

Verified output of collisions_by_design_py.py — regenerated by tools/run_examples.py, never hand-typed.

1. TWO ADDRESSES, ONE UPPERCASE
   victim     'mike@example.org'
              U+006D U+0069 U+006B U+0065 ...
   attacker   'mıke@example.org'
              U+006D U+0131 U+006B U+0065 ...
   equal?     False
   uppercased 'MIKE@EXAMPLE.ORG'
              'MIKE@EXAMPLE.ORG'
   equal now? True
   Register the second address; ask for a password reset; the lookup is
   case-insensitive, so it finds the first account -- and the mail goes
   to whichever address the code decided to send to. If that is the one
   that was submitted rather than the one that was stored, the token
   leaves the building. That is CVE-2019-19844, in four lines.

2. THE FOLD IS NOT A ROUND TRIP
   char     upper    lower(upper)   back to start?
   ß        SS       ss             False
   ı        I        i              False
   İ        İ        i̇             False
   fi        FI       fi             False
   ẞ        ẞ        ß              False
   Not one of them survives the journey. Case mapping is not a bijection
   -- it merges characters on the way up and cannot un-merge them coming
   back -- so it cannot be an identity function. It can only be a way of
   choosing which distinct strings you are willing to call the same.

3. 'CASE-INSENSITIVE' IS NOT ONE RELATION
   pair                        lower      upper   casefold  NFKC+fold
   ß  vs  ss                       -       SAME       SAME       SAME
   ı  vs  i                        -       SAME          -          -
   İ  vs  i                        -          -          -          -
   fi  vs  fi                       -       SAME       SAME       SAME
   K  vs  k                     SAME          -       SAME       SAME
   Read the rows, not the columns. Every row is one pair of strings, and
   four systems that all describe themselves as case-insensitive give
   four different answers about whether it is one user or two.
   The dotless i is the sharpest: only the uppercase fold merges it,
   which is why the bug in section 1 needed a system that uppercases.

4. A STRONGER FOLD MAKES BIGGER CLASSES
   registered   'ᴮᶦᵍᴮᶦʳᵈ'
                U+1D2E U+1DA6 U+1D4D U+1D2E U+1DA6 U+02B3 U+1D48
   NFKC         'BɪgBɪrd'
   NFKC+fold    'bɪgbɪrd'
   Modifier letters are compatibility-equivalent to the letters they are
   shrunken copies of, so a fold that includes NFKC pulls them back into
   the alphabet. Spotify hit this in 2013 with a canonicaliser stronger
   than NFKC -- strong enough to reach plain 'bigbird' -- and the
   canonicalisation was the DEFENCE against impersonation. It worked; it
   just also merged an account nobody meant to merge.

5. SO THE FIX IS NOT A BETTER FOLD
   There is no injective fold. Every one of them defines equivalence
   classes, and the only question is which classes you want.
   What actually works is to treat the class as the thing being
   registered:
     canonical = fold(input)          # one fold, named, everywhere
     if taken(canonical): reject      # the CLASS is unique, not the string
     store(canonical, display=input)  # keep the original only to show
     mail_to(stored_address)          # never to the address just typed
   The last line is the one that turns a collision into a takeover.

Section 3 is the table to keep. Read the rows: each is one pair of strings, and four systems that all call themselves case-insensitive give different answers about whether it is one user or two. ß and ss are the same user under an uppercase fold and different users under a lowercase one. ı and i are the same under uppercase only — which is exactly why the Django bug needed a backend that uppercases.

Section 2 is the reason none of this can be engineered away. Case mapping is not a bijection: it merges on the way up and cannot un-merge coming back, and not one of the five characters survives a round trip. A function like that can never be an identity; it can only be a declaration of which distinct strings you are willing to call the same.

In Rust

Verified output of collisions_by_design_rs.rs — regenerated by tools/run_examples.py, never hand-typed.

1. String EQUALITY IS BYTE EQUALITY, ALWAYS
   composed    "café"  5 bytes  U+0063 U+0061 U+0066 U+00E9
   decomposed  "cafe\u{301}"  6 bytes  U+0063 U+0061 U+0066 U+0065 U+0301
   ==          false
   Same word on screen, different bytes, and Rust says no. There is
   no locale, no collation and no hidden normalisation anywhere in
   std -- which means Rust will never merge two users for you, and
   never split two rows a database has already merged.

2. SO THE FOLD IS A DECISION, AND THERE IS MORE THAN ONE
   registry keyed by to_lowercase  2 record(s): ["ss", "ß"]
   registry keyed by to_uppercase  1 record(s): ["SS"]
   The three names are "ss", "\u{df}" and "SS". Lowercasing keeps the
   sharp s apart from the double s; uppercasing folds all three into
   one. Both registries are case-insensitive. They disagree about how
   many people signed up.

3. AND THE ONE THAT LOSES A USER SAYS NOTHING
   "ss" was replaced by "ß" under key "SS"
   "ß" was replaced by "SS" under key "SS"
   HashMap::insert returns the value it displaced. That Option is the
   only notice you will ever get, and `map.insert(k, v);` -- with the
   semicolon and no binding -- throws it away without a warning.
   #[must_use] is not on it, because overwriting is usually the point.

4. WHAT TO DO INSTEAD
   let key = fold(input);                       // one fold, chosen once
   match registry.entry(key) {                   // ask before writing
       Occupied(_) => return Err(NameTaken),
       Vacant(slot) => slot.insert(record),
   }
   `entry` is the difference between 'this name is taken' and
   'this name is now yours', and it is the same one line of code.

Rust's contribution here is refusal. String equality is byte equality, full stop — no locale, no collation, no normalisation anywhere in std — so Rust will never merge two users behind your back, and never split two rows that a database has already merged. That is the property the previous section says is missing everywhere else, and it means the fold in a Rust program is always a visible function call somebody wrote.

Section 3 is the sharp end. HashMap::insert returns the value it displaced, and that Option is the only notice you will ever get that two users collided. map.insert(k, v); — semicolon, no binding — discards it silently, and there is no #[must_use] to stop you, because overwriting is usually the point. entry() is the same one line of code and turns "this name is now yours" into "this name is taken".

If you are coming from Python or ABAP

Python. Use str.casefold(), not str.lower(), when the question is "are these the same string" — casefold exists for exactly this and folds ß to ss where lower does not. But the more valuable habit is to write the fold once, name it, and let nothing else fold: def identity(s): return unicodedata.normalize("NFKC", s).casefold(). Then the class is computable, greppable, and testable, and you can answer "who else is in this user's class" with a query instead of an argument. Two Python-specific traps worth knowing: dict and set use __eq__ and __hash__, so a dict keyed by raw usernames is case-sensitive while your database may not be — the two disagree about how many users exist; and str.lower() in Python is locale-independent, which saves you from the Turkish bug at the language level and does not save you from it in the database, where the collation decides.

ABAP. The nearest thing to this page in ABAP is the database, not the language. TRANSLATE ... TO UPPER CASE folds by system rules, and a SELECT ... WHERE name = @lv_name compares by the column's own collation — so two systems with different settings can disagree about whether a row matches, and the ABAP code is identical in both. Fold in ABAP, store the folded value in its own field, and index and compare that, rather than relying on the comparison to fold for you; then the equivalence class is a column you can look at. The truncation half of the page applies directly and often: a CHAR(n) field pads and truncates without complaint, and MOVE to a shorter field is silent, so a name that was validated at full length can be compared at a shorter one. Verify collation and code page settings against your own system rather than a document. (Not machine-checked — CI cannot run ABAP.)

Try it

cd 12_Adversarial/collisions_by_design/examples
python3 collisions_by_design_py.py
rustc --edition 2024 collisions_by_design_rs.rs -o /tmp/cb && /tmp/cb

Find your own system's classes. Take the fold your login actually uses and run it over a word list, counting how many distinct inputs land on each output. You are not looking for a big number; you are looking for the classes with more than one member, because those are the accounts that can be reached by more than one spelling.

import collections, unicodedata as ud
fold = lambda s: ud.normalize("NFKC", s).casefold()
names = ["Admin", "admin", "ADMIN", "аdmin", "adᴍin", "ıdmin"]
classes = collections.defaultdict(list)
for n in names:
    classes[fold(n)].append(n)
for key, members in classes.items():
    if len(members) > 1:
        print(f"{key!r:12} <- {members}")

Run it and notice what it does not merge: the Cyrillic а and the small-capital ᴍ stay in classes of their own, because neither is compatibility-equivalent to anything. A fold answers "same person?" and has no opinion at all about "same picture?" — which is the other page's question, and needs the other page's answer.

Then ask the two questions that matter, of anything you own that has accounts: which fold decides that two logins are the same person, and when we send that person a secret, do we send it to the address they typed or the address we stored. The second question is the one that turns a collision into a takeover, and it is usually answerable by reading one function.

Practice

Six signups. Run admin, ADMIN, Admin, ａdmin, ⓐdmin and admın through NFKC + casefold and write down the equivalence classes.

Then the question that actually matters: for each class, who owns it? Give the three policies a system can adopt, say what each costs, and identify the fourth option that is not a policy at all but is what most systems accidentally do. Name three non-text systems with the same shape.

Answers

Verified output of collisions_by_design_kata_py.py — regenerated by tools/run_examples.py, never hand-typed.

SIX SIGNUPS, AND THE CLASSES THEY FALL INTO
   'admin'    <- ['admin', 'ADMIN', 'Admin', 'ａdmin', 'ⓐdmin']
   'admın'    <- ['admın']

   6 distinct strings became 2 identities. That is not a
   failure of the folding function -- it is the definition of one. Any
   function that decides two different strings are the same person is
   many-to-one by construction.

SO THE QUESTION IS NEVER 'DOES IT COLLIDE'
   It is: who gets the class? Three answers, and every system picks one
   whether it knows it or not:
     FIRST COMES, FIRST SERVED   the earliest registration owns the
       class and every later spelling is refused. Simple, and it means
       an attacker who registers first owns YOUR name's class.
     RESERVE THE WHOLE CLASS     registering 'admin' also blocks every
       spelling that folds to it. Safe, and it burns names.
     REFUSE AMBIGUITY            reject any name whose folded form
       differs from itself -- so only the canonical spelling can ever be
       registered. Strictest, and it excludes legitimate scripts.

THE ONE THAT IS NOT AN ANSWER
   Storing the ORIGINAL and comparing the FOLDED. Then two accounts
   exist, both display the same name, and which one a lookup finds
   depends on the index. That is not a policy; it is the absence of one.

THE SAME SHAPE OUTSIDE TEXT
   A hash function, a case-insensitive filesystem, an email provider
   that ignores dots before the @, a phone number normalizer. Each
   creates classes; each has to answer the ownership question; and the
   ones that made news answered it late.

WHAT TO WRITE DOWN
   The folding function, the stored form, and the owner rule -- three
   sentences, in the spec, before the first account is created. They
   cannot be changed afterwards without invalidating identities.

See also