Repository navigation
O(n²) insertion sort in unicodedata.normalize("NFC") canonical ordering #149079
Description
Bug report
Bug description:
From @ch4n3-yoon:
CPython's unicodedata.normalize("NFC") implementation uses an insertion sort for the canonical ordering step of combining characters, which exhibits O(n²) time complexity on crafted inputs. An attacker can cause denial of service by supplying a string with many consecutive combining characters whose Canonical Combining Class (CCC) values are arranged in alternating order, leading to excessive CPU consumption. A 0.5MB payload can consume over 30 seconds of CPU time.
CPython versions tested on:
CPython main branch
Operating systems tested on:
No response
Linked PRs
- gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() #149080
- [3.14] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) #150775
- [3.15] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) #150776
- [3.13] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) #150780
- [3.13] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) #150781
- gh-149079: Optimize sorting in unicodedata.normalize() #150782
- [3.12] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) #150843
- [3.11] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) #151570
- [3.10] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) #151571
- [3.11] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) (GH-150843) #155158
- [3.10] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) (GH-150843) #155159
Activity
pythongh-149079: Fix O(n^2) canonical ordering in unicodedata.normali…
gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (G…
[3.15] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normal…
[3.14] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normal…
pythongh-149079: Speed up find_nfc_index in unicodedata composition
[3.13] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normal…
pythongh-149079: Speed up find_nfc_index in unicodedata composition
pythongh-149079: Speed up find_nfc_index in unicodedata composition
pythongh-149079: Speed up find_nfc_index in unicodedata composition
gh-149079: Optimize sorting in unicodedata.normalize() (GH-150782)
pythongh-149079: Optimize sorting in unicodedata.normalize() (pythonG…
Update python312 to version 3.12.13 / rev 51 via SR 1368858
Update python311 to version 3.11.15 / rev 71 via SR 1368927
Update python310 to version 3.10.20 / rev 79 via SR 1368874
[3.12] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normal…
[3.11] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normal…
[3.10] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normal…
[CVE-2026-3276] Fix O(n^2) canonical ordering in unicodedata.normalize()
[CVE-2026-3276] Fix O(n^2) canonical ordering in unicodedata.normalize()
[CVE-2026-3276] Fix O(n^2) canonical ordering in unicodedata.normalize()
[CVE-2026-3276] Fix O(n^2) canonical ordering in unicodedata.normalize()
[CVE-2026-3276] Fix O(n^2) canonical ordering in unicodedata.normalize()
[CVE-2026-3276] Fix O(n^2) canonical ordering in unicodedata.normalize()
[CVE-2026-3276] Fix O(n^2) canonical ordering in unicodedata.normalize()