1. Regex
정규식은 특정한 규칙(전화번호, 이메일)을 갖는 문자열의 집합을 다루는 데 사용하는 언어입니다. 다양한 언어에서 형식, 검증, 검색 치환을 위해서 지원하고 있습니다.
2. 정규식 사용법
2-1. 매칭 패턴
대문자 영어는 아닌 것을 뜻합니다.
| 패턴 | 의미 |
|---|---|
| a-zA-Z, 0-9, ㄱ-ㅎ | -으로 범위를 지정한다. |
| \d, \D | 숫자 |
| \w, \W | 알파벳, 숫자, 언더스코어 |
| \s, \S | 스페이스 공백 |
| \특수문자 | 특수기호 |
2-2. 검색 패턴
| 패턴 | 의미 |
|---|---|
| | | OR |
| [ ] | 괄호안의 문자 중 하나 |
| [^문자 ] | 괄호안의 문자를 제외한 것 |
| ^문자열 | 특정 문자열로 시작 |
| 문자열$ | 특정 문자열로 끝남 |
| () | 그룹화 |
| (?:패턴) | 그룹 검색 |
| \b, \B | 단어의 처음, 끝 |
2-3. 수량 표현
| 패턴 | 의미 |
|---|---|
| ? | 최대 1개 |
| * | 있거나 없거나 |
| + | 최소 1개 |
| {min, max} | 최소 ~ 최대 |
전화번호 정규식을 예시로 들면
^\d{3}-?\d{3,4}-?\d{4}$이정도로 정규표현식을 작성할 수 있습니다.
3. 정규표현식의 작동 원리
정규표현식은 개발자가 작성한 패턴과 문자열을 일치시키는 역할을 해야 합니다.
대부분의 정규 표현식 엔진은 2가지 방식으로 작동합니다.
3-1. NFA
현대의 대부분의 프로그래밍 언어에서 사용되고 있습니다.
작동 방식은 그리디 알고리즘과 백트래킹 방식을 사용해서 패턴을 찾으며 가능한 모든 경로를 탐색하며 패턴을 매칭합니다.
\d{3}-?\d{3,4}-?\d{4}해당 표현식을 나눠서 보면
| 패턴 | 설명 |
|---|---|
| \d{3} | 숫자 3자리 |
| -? | - 이 있거나 없음 |
| \d{3, 4} | 숫자 3~4자리 |
| -? | - 이 있거나 없음 |
| \d{4} | 숫자 4자리 |
해당 표현식은
000-0000-0000, 000-000-0000, 0000000000 등등의 숫자를 허용합니다.
해당 표현식은 이런 과정으로 패턴을 해석합니다.
3-2. DFA
주로 컴파일러나 grep 명령어를 사용하는 데 사용됩니다.
백트래킹이 없어서 항상 (O) n의 시간을 보장합니다.
4. ReDos Attack
4-1. ReDos란
ReDos 공격은 서비스 거부 공격의 종류 중에 하나로 정규 표현식의 취약점을 사용하는 공격 방법입니다.
ReDos는 정규식 계산 시 시간복잡도를 의도적으로 증가시켜 서버의 자원을 소모하는 식으로 공격합니다. 서버 자원을 많이 소모시키는 건 다른 서비스 거부 공격과 똑같이 진행되기 때문에 ReDos Attack은 시간복잡도를 증가시키는 게 중요합니다.
일반적으로 정규식이 문자열을 매칭할 땐 정상적으로 작동하지만 비정상적인 문자열을 입력해서 정규 표현식이 작동하는 시간을 비정상적으로 늘립니다. 서버의 자원들이 정규식을 계산하는 데에 사용하기 때문에 서버는 뻗는 것과 마찬가지인 상태가 됩니다.
ReDos Attack은 보통 NFA 엔진에서 발생합니다. 그 이유는 NFA는 탐욕적 알고리즘과 백트래킹을 통해서 문자열을 매치하기 때문에 시간 복잡도가 매우 높아질 가능성이 높기 때문입니다.
4-2. PoC
^(a+)+$해당 정규식은 a가 최소 1개 이상의 그룹이 1개 이상 있다는 의미를 갖습니다.
해당 정규식으로 예시를 들어보겠습니다.
해당 정규식에 aaaaX라는 값을 넣는다고 가정하고 총 몇 번의 path가 발생하는지 계산해 보겠습니다.
입력된 문자열은 a가 4번, X가 문자열 제일 마지막에 있습니다.
NFA엔진은 정규식이 패턴 매칭에 실패하게 되면 백트래킹하여 다시 시도하며 조합을 다시 맞춰봅니다.
1. (a+)로 aaaa를 그룹화합니다. 하지만 마지막에 X 가 있기 때문에 실패합니다.
2. aaaa 가 실패했기 때문에 aaa로 다시 시도합니다. aaa + a를 다시 시도하지만 X 때문에 실패합니다.
3. aaa가 실패해서 다시 aa + aa로 매칭을 해보지만 X때문에 실패합니다.
4. a + aaaa, a + aa + a, a + a + aa, a + a + a + a 과정을 거치며 백트래킹과 path가 발생합니다
aaaaX라는 5글자의 문자열을 매치하기 위해서 총 16번의 path가 발생합니다.
만약의 입력값이 a*16 + X 문자열이 들어오면 총 65,536번의 path가 발생합니다.
4-3. 실제 서비스 공격
교내 서비스인 도토리 서비스의 유튜브 검증 정규식을 분석해 보았습니다
^((?:https?:)?\/\/)?((?:www|m)\.)?((?:youtube(-nocookie)?\.com|youtu\.be))(\/(?:[\w\-]+\?v=|embed\/|live\/|v\/)?)([\w\-]+)(\S+)?$| 정규식 | 설명 |
| ((?:https?:)?\/\/)? | 프로토콜 지정 |
| ((?:www|m)\.)? | www. or m. |
| ((?:youtube(-nocookie)?\.com|youtu\.be)) | youtube(-nocookie).com or youtu.be |
| (\/(?:[\w\-]+\?v=|embed\/|live\/|v\/)?) | watch?v=, /embed/ /live/ /v/ |
| ([\w\-]+), (\S+)? | 이후 추가적인 문자열 허용 |
'youtu.be/y' + 'a'. repeat(~~) + 'X\t'
^((?:https?:)?\/\/)?((?:www|m)\.)?((?:youtube(-nocookie)?\.com|youtu\.be))(\/(?:[\w\-]+\?v=|embed\/|live\/|v\/)?)([\w\-]+)(\S+)?$
일단 백트래킹이 발생하려면 매칭에 실패해야 합니다. 마지막 정규식인 (\S+)? 공백이 없는 하나 이상의 문자열에서 무시되고 $에서 문자열이 남아있어 실패하기 위해 페이로드 마지막에 \t를 넣어줘서 매칭 실패를 의도합니다
해당 정규식의 시간복잡도가 높아지는 원인에는 백트래킹시 ([\w\-]+)가 2번 매칭된다는 게 있습니다.
([\w\-]+)는 모든 문자와 - 문자가 1개 이상이라는 의미를 갖고 있는데, 만약 매칭 실패하고 백트래킹시에 문제가 발생합니다.
처음엔 ([\w\-]+) 이 모든 문자를 매칭하고 (\S+)? 에서 매칭 시에 정규식 매칭에 실패하고 백트래킹 발생해서 다른 경우를 찾게 됩니다.
이때 두 번째의 ([\w\-]+)에서도 문자열을 매 칭하기 때문에 시간복잡도가 증가합니다.
또한 유튜브 링크에 대한 url의 길이에 제한이 없기 때문에 매우 긴 문자열을 보낼 수 있습니다.
실제 로컬에서 테스트를 해보면 2시간이 넘게 걸리는 걸 확인할 수 있습니다.
4-4. 막기
ReDos Attack은 상대적으로 대쳐 하기 쉬운 편에 속합니다. DDoS 공격은 아무리 막으려고 노력해도 새로운 방식으로 계속 공격이 가능하지만 ReDos는 위험한 정규식만 패치하면 취약점이 없어지기 때문에 그나마 낫다고 볼 수 있습니다. 오히려 그런 부분 때문에 위험성에 비해서 잘 알려지지 않는 부분도 있습니다.
실제로 ReDos 때문에 스택오버플로우가 30분 동안 멈추고, 클라우드플레어의 DNS서버가 멈추는 사건도 있었습니다.
실제로 정규식을 사용하게 된다면 취약점을 테스트해 보고 사용하면 안전할 것 같습니다.