Skip to content

Instantly share code, notes, and snippets.

@b-c-ds
Created March 16, 2021 19:28
Show Gist options
  • Save b-c-ds/b1a2cc0c68a35c57188575eb496de5ce to your computer and use it in GitHub Desktop.
Save b-c-ds/b1a2cc0c68a35c57188575eb496de5ce to your computer and use it in GitHub Desktop.
cve-2021-27291
Doyensec Vulnerability Advisory
CVE-2021-27291
=======================================================================
* Regular Expression Denial of Service (REDoS) in pygments
* Affected Product: pygments v1.1+, fixed in 2.7.4
* Vendor: https://github.com/pygments
* Severity: Medium
* Vulnerability Class: Denial of Service
* Status: Fixed
* Author(s): Ben Caller (Doyensec)
=======================================================================
=== SUMMARY ===
In pygments, the lexers used to parse programming languages rely heavily on regular expressions.
Some of the regular expressions have exponential or cubic worst-case complexity and are vulnerable to Regular Expression Denial of Service (ReDoS).
By crafting malicious input, an attacker can cause Denial of Service.
=== TECHNICAL DESCRIPTION ===
The vulnerable regular expressions are below. Line numbers refer to pygments version 2.7.3.
pygments/lexers/archetype.py #61
Pattern: [+-]?(\d+)*\.\d+%?
Complexity: exponential
Example: '0' * 3456
Repeated character: \d
Languages: ODIN, CADL, ADL
The above shows that the python code
re.match(r"[+-]?(\d+)*\.\d+%?", "0" * 123)
will run approximately forever.
pygments/lexers/factor.py #268
Pattern: """\s+(?:.|\n)*?\s+"""
Complexity: cubic
Repeated character: \s
Example: '"""' + ' ' * 3456
Languages: Factor
pygments/lexers/factor.py #325
Pattern: (\{\s+)(\S+)(\s+[^}]+\s+\}\s)
Complexity: cubic
Repeated character: \s
Example: '{ 0' + ' ' * 3456
Languages: Factor
pygments/lexers/jvm.py #984
Pattern: ".*``.*``.*"
Complexity: cubic
Repeated character: \x60 (`)
Example: '"' + '`' * 3456
Languages: Ceylon
pygments/lexers/matlab.py #140
pygments/lexers/matlab.py #641
pygments/lexers/matlab.py #713
Pattern: (\s*)(?:(.+)(\s*)(=)(\s*))?(.+)(\()(.*)(\))(\s*)
Complexity: cubic
Repeated character: \s
Example: ' ' * 3456
Languages: Matlab, Octave, Scilab
pygments/lexers/objective.py #264
Pattern: (%config)(\s*\(\s*)(\w+)(\s*=\s*)(.*?)(\s*\)\s*)
Complexity: cubic
Repeated character: \s
Example: '%config(a=' + ' ' * 3456
Languages: Logos
pygments/lexers/objective.py #268
Pattern: (%new)(\s*)(\()(\s*.*?\s*)(\))
Complexity: cubic
Repeated character: \s
Example: '%new(' + ' ' * 3456
Languages: Logos
pygments/lexers/templates.py #1408
Pattern: (\$)(evoque|overlay)(\{(%)?)(\s*[#\w\-"\'.]+[^=,%}]+?)?(.*?)((?(4)%)\})
Complexity: cubic
Repeated character: [22:",23:#,27:',aa,2d:-,2e:.,b5,ba,[f8-ff],[a-z],[A-Z],[c0-d6],[d8-f6]]
Example: '$evoque{' + 'a' * 3456
Languages: Evoque
pygments/lexers/varnish.py #64
Pattern: (\.\w+\b)(\s*=\s*)([^;]*)(\s*;)
Complexity: cubic
Repeated character: \s
Example: '.a=' + ' ' * 3456
=== REPRODUCTION STEPS ===
In some cases, the lexer will only use the vulnerable regex when a prefix is added to the input.
As an example, causing REDoS via the ODIN / CADL lexer requires a '<' before the long string of digits.
Create a file redos.odin containing:
<000000000000000000000000000000
Run `pygmentize redos.odin`. It will run for a very long time.
As the complexity is exponential, adding one extra digit will double the processing time.
For cubic complexity REDoS, doubling the length of the repeating section makes processing take 8 times as long.
Below are recipes for creating source code files which cause REDoS:
ADL: 'language\n <' + '0' * 30
CADL / ODIN: '<' + '0' * 30
Ceylon: '"' + '`' * 3456
Evoque: '$evoque{' + 'a' * 3456
Factor: '"""'+ " " * 3456
Logos: '%new(' + ' ' * 3456
Matlab: 'function' + ' ' * 3456
Varnish VCL: 'backend x{.a=' + ' ' * 3456
=== REMEDIATION ===
Fix the regular expressions to avoid overlapping capture groups.
=== DISCLOSURE TIMELINE ===
2020-12-29: Vulnerability disclosed via email to maintainer
2021-01-11: Fixed in https://github.com/pygments/pygments/commit/2e7e8c4a7b318f4032493773732754e418279a14
2021-01-12: Patched version 2.7.4 released
=======================================================================
Doyensec (www.doyensec.com) is an independent security research
and development company focused on vulnerability discovery and
remediation. We work at the intersection of software development
and offensive engineering to help companies craft secure code.
Copyright 2020 by Doyensec LLC. All rights reserved.
Permission is hereby granted for the redistribution of this
advisory, provided that it is not altered except by reformatting
it, and that due credit is given. Permission is explicitly given
for insertion in vulnerability databases and similar, provided
that due credit is given. The information in the advisory is
believed to be accurate at the time of publishing based on
currently available information, and it is provided as-is,
as a free service to the community by Doyensec LLC. There are
no warranties with regard to this information, and Doyensec LLC
does not accept any liability for any direct, indirect, or
consequential loss or damage arising from use of, or reliance
on, this information.
@b-c-ds
Copy link
Author

b-c-ds commented May 11, 2021

Discovered with regexploit.
Blog

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment