ReDOS (Regex DOS)

πŸ” Introduction

ReDOSλŠ” μ •κ·œν‘œν˜„μ‹μ„ μ‚¬μš©μžλ‘œλΆ€ν„° μž…λ ₯받을 λ•Œ λ°œμƒν•  수 μžˆλŠ” λ³΄μ•ˆ λ¬Έμ œμž…λ‹ˆλ‹€. 일반적으둜 ReDOS, Regex DOS λ“±μœΌλ‘œ 뢈리며 자체적으둜 λ°˜λ³΅λ˜λŠ” κ·Έλ£Ήν™” μ •κ·œμ‹κ³Ό μ •κ·œμ‹ 검증 λ‘œμ§μ„ λ§Œμ‘±ν•˜λŠ” λŒ€λŸ‰μ˜ 문자 등을 μ΄μš©ν•΄μ„œ ν•œλ²ˆμ˜ μ›Ή μš”μ²­μœΌλ‘œ μ„œλΉ„μŠ€μ˜ κ°€μš©μ„±μ„ λ–¨μ–΄λœ¨λ¦¬λŠ” λ°©λ²•μž…λ‹ˆλ‹€.

μ΄λŸ¬ν•œ ReDOSλŠ” Regexp 엔진이 Backtracking κΈ°λŠ₯을 μ‚¬μš©ν•  λ•Œ λ°œμƒν•˜λ©° 이 κΈ°λŠ₯은 μ •κ·œν‘œν˜„μ‹ 처리 μ‹œ κ°€λŠ₯ν•œ λͺ¨λ“  경둜λ₯Ό νƒμƒ‰ν•˜κΈ° μœ„ν•΄ λΉ„ 효율적인 μž‘μ—…μ„ μ—¬λŸ¬λ²ˆ μ‹œλ„ν•˜κ²Œ λ©λ‹ˆλ‹€. μ΄λ‘œμΈν•΄ μ‹œμŠ€ν…œμ˜ μžμ›μ„ κ³ κ°ˆμ‹œν‚€λ©° DOSλ₯Ό μˆ˜ν–‰ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

원인은 Regex의 μ•Œκ³ λ¦¬μ¦˜μ΄ NFA(Nondeterministic Finite Automaton)을 κ΅¬μ„±ν•˜κ³  이λ₯Ό 기반으둜 μ²˜λ¦¬ν•˜κΈ° λ•Œλ¬Έμž…λ‹ˆλ‹€.

πŸ—‘ Offensive techniques

Detect

μ™ΈλΆ€μ—μ„œμ˜ μΈμžκ°’ λ“±μœΌλ‘œ μ •κ·œν‘œν˜„μ‹μ„ ν†΅μ œν•  수 μ—†λ‹€λ©΄ ν•΄λ‹Ή μ •κ·œν‘œν˜„μ‹μ˜ μ²˜λ¦¬μ—μ„œ λΆ€ν•˜κ°€ λ λ§Œν•œ 뢀뢄을 μ°Ύμ•„μ•Όν•©λ‹ˆλ‹€. λ§Œμ•½ μ •κ·œν‘œν˜„μ‹μ΄ ^(a+)+$ 같은 ꡬ문을 μ‚¬μš©ν•  λ•Œ aaaaX λž€ 값이 μž…λ ₯되면 μ•„λž˜μ™€ 같은 처리λ₯Ό ν†΅ν•΄μ„œ 총 16번의 Pathκ°€ λ°œμƒν•˜κ²Œ λ©λ‹ˆλ‹€.

NFA

이 λ•Œ λ§Œμ•½ μ™ΈλΆ€ μž…λ ₯ 값이 aaaaaaaaaaaaaaaaX 둜 듀어왔을 경우 65536번의 Pathκ°€ λ°œμƒν•˜κ³  λ¬ΈμžλŠ” λͺ‡κ°œ μ•ˆλŠ˜μ—ˆμ§€λ§Œ, μ •κ·œν‘œν˜„μ‹ 처리λ₯Ό μœ„ν•΄ λ°˜λ³΅λ˜λŠ” λ™μž‘μ΄ 크게 λŠ˜μ–΄λ‚¬μŠ΅λ‹ˆλ‹€. κ·Έλž˜μ„œ μ΄λŸ¬ν•œ 경우 훨씬 큰 a 값이 듀어갔을 경우 Backtracking으둜 인해 큰 루프가 λ°œμƒν•©λ‹ˆλ‹€.

Exploitation

Regexp νŒ¨ν„΄μ„ λ°”κΏ€ 수 μ—†λ‹€λ©΄ regexp νŒ¨ν„΄μ— λ”°λΌμ„œ 큰 μ²˜λ¦¬κ°€ λ°œμƒν•˜λ„λ‘ μœ λ„ν•΄μ•Όν•©λ‹ˆλ‹€. 예λ₯Όλ“€μ–΄ μ•„λž˜μ™€ 같이 email 검증 regexpκ°€ μžˆλ‹€κ³  κ°€μ •ν•©μ‹œλ‹€.

1
^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$

일반적인 email 검증 regexp둜 λ³΄μ΄μ§€λ§Œ, μ΄λŸ¬ν•œ 경우 aaaaaaaaaaaaaaaaaaaaaaaa! 값이 input으둜 λ“€μ–΄κ°€λ©΄ 큰 μ˜€λ²„ν—€λ“œκ°€ λ°œμƒν•©λ‹ˆλ‹€.

πŸ›‘ Defensive techniques

Regexp νŒ¨ν„΄μ„ 체크해보고 반볡적인 μž‘μ—…μ΄ λ°œμƒν•  수 μžˆλŠ”μ§€ ν…ŒμŠ€νŠΈν•˜κ³  λ³΄μ™„ν•©λ‹ˆλ‹€. μ΄λŸ¬ν•œ 과정은 test codeλ₯Ό 톡해 μ²˜λ¦¬ν•˜λ©΄ regexpκ°€ λ³€κ²½λ˜μ–΄λ„ μœ μ—°ν•˜κ²Œ λŒ€μ²˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€. λ˜ν•œ ReScue, SafeRegex 같은 ReDOS 탐지 도ꡬλ₯Ό ν†΅ν•΄μ„œ ReDOS의 κ°€λŠ₯성을 체크해볼 수 μžˆμŠ΅λ‹ˆλ‹€.

1
2
3
4
5
6
7
java -jar saferegex.jar "(a|aa)+"

Testing: (a|aa)+
More than 10000 samples found.
***
This expression is vulnerable.
Sample input: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

πŸ•Ή Tools

πŸ“Œ References

Licensed under CC BY-NC-SA 4.0
Last updated on Apr 05, 2022 23:19 +0900