정규식을 이용한 공격 - ReDos

redos title

정규식을 이용한 공격 ReDos

ReDOS는 정규표현식을 사용자로부터 입력받았을 때 발생할 수 있는 보안 문제입니다. 특정 정규식 패턴은 입력값을 평가하는데 오래 걸립니다. ReDos는 이를 이용해 정규식 평가에 오랜 시간이 걸리게 하는 알고리즘 복잡성 공격입니다.

타깃이 되는 정규식 로직은 자체적으로 반복되는 그룹이 주원인이며, 이 정규식에 어느 정도 만족하는 대량의 문자 등을 입력하여 가용성이 떨어지게 만듭니다.

 

ReDos 원인은 정규식을 평가하는 엔진이 Backtracking을 사용하는 엔진이라면 발생합니다.

주로 NFA (Nondeterministic Finite Automaton) 엔진이 그 원인입니다.

 

NFA 방식은 JAVA, javascript, .NET, PHP, Perl, Python, Ruby 등 광범위하게 사용되고 있습니다.

Catastrophic Backtracking이 일어나는 모습

Catastrophic Backtracking

정규식에는 두가지 알고리즘이 있습니다.

• Deterministic Finite Automaton (DFA): 문자열의 문자를 한 번만 확인한다.
• Nondeterministic Finite Automaton (NFA): 최적의 일치를 찾을 때까지 여러 번 확인한다. 이런 여러 번 확인하는 NFA의 동작으로 인해 Catastrophic Backtracking이 일어날 수 있다.

 

ReDos에 취약한 곳

Nodejs

ReDos공격을 이용하여 nodejs 서버를 공격할 수 있습니다.

Node.js 런타임 아키텍처는 싱글 스레드 이벤트 루프를 구현합니다. 싱글 스레드 이벤트 루프 아키텍처는 확장성이 매우 높지만, 하나의 함수 실행에 오랜 시간이 걸리면 전체 프로세스를 중단시키기 때문에 문제가 발생합니다.

이것이 Node.js가 ReDoS 취약점에 크게 영향을 받는 이유입니다.

Moment.js

2.15.2이하 버전의 Moment.js는 ReDos 취약성이 있습니다.

https://snyk.io/test/npm/moment/2.15.2

Snyk Vulnerability Database | Snyk

아래는 Moment.js가 날짜 구문을 검사하기 위해 사용했던 취약한 정규식입니다

/D[oD]?(\\[[^\\[\\]]*\\]|\\s+)+MMMM?/

원인은 + 구문을 많이 사용한 것입니다. 보통 그룹 내 + 구문이 있는데 그 그룹 밖에 또 + 구문이 있으면 취약한 정규식이 됩니다.

var moment = require('moment')
moment.locale('be')
moment().format('D                               MMN MMMM')

142843회 스탭을 검사했지만 정규식 매칭에 실패한다.

스택 오버플로우가 멈춘 사례

2016년에 Stack Overflow는 34분 동안 다운되었습니다. 다음과 같은 정규식을 사용했기 때문입니다.

^[\\s\\u200c]+|[\\s\\u200c]+$

위의 정규식은 잘못된 형식의 게시물에서 실행되어 정규식이 웹서버에서 높은 CPU를 소비하도록 했습니다.

Cloudflare가 멈춘 사례

2019년 Cloudflare의 ReDoS 중단으로 인해 27분 동안 많은 서비스가 멈춘 사례가 있습니다.

원인은 ReDos이며 아래 링크에서 그 내용을 볼 수 있습니다.

https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/

 

안전한 정규식 작성하는 방법

1. 안전한 정규식을 작성하는 기본 원칙

주의해야 할 3가지 패턴

나쁜 정규식 패턴을 발견하는 것은 실제로 매우 까다롭습니다. 그러나 주의해야 할 3가지 주요 패턴은 다음과 같습니다.

1. (a+)+ : 중첩 수량자
2. (a|a)+ : 정량화된 중첩 분리
3. \d+\d+ : 정량화된 중첩 인접성

정규식 패턴 입력을 사용자에게 열어두지 말자.

사용자가 정규식 패턴에 입력을 할 수 있도록 서비스를 제공하면 안 됩니다. 당연한 이야기지만, 이는 공격자가 정규식을 수정할 수 있는 경우 위험한 패턴을 구성하여 시스템을 ReDoS에 취약하게 만들 수 있습니다.

정규식 패턴은 단순하게 작성하자

정규식 패턴이 길면 길수록 취약점이 생깁니다. 가능한 단순한 정규식을 만드세요. 당연히 위의 중첩수량자와 같은 취약패턴은 피하시고요.

 

2. 정규식 패턴을 검사해줄 툴을 사용하자

위에 언급하다시피 정규식 패턴을 단순하게 작성하는 것이 좋지만, 패턴을 길게 작성해야 할 경우가 생깁니다. 작성한 정규식이 취약한지 확인할 수 있는 여러 도구들이 있습니다.

validation 라이브러리 사용

• https://github.com/validatorjs/validator.js
• https://express-validator.github.io/docs/

와 같은 라이브러리로 정규식을 한번 검토하고 나갈 필요가 있다.

정규식 analyzer 사용

• https://makenowjust-labs.github.io/recheck/playground/
• https://github.com/2bdenny/ReScue
• https://github.com/davisjam/safe-regex

를 사용하여, 안전한 정규식인지 한번 확인할 필요가 있다.

 

3. Nodejs를 사용한다면, ReDos를 방어하는 정규식 엔진을 사용하자.

NodeJS의 기본 정규식 엔진은 ReDos 공격에 취약합니다. 구글은 이를 파악하고 re2라는 엔진을 만들었습니다. re2 엔진은 **ReDos**를 방어할 수도 있으며, 기존 정규식 엔진과 사용도 거의 동일합니다.

https://github.com/uhop/node-re2

GitHub - uhop/node-re2: node.js bindings for RE2: fast, safe alternative to backtracking regular expression engines.

 

 

참고

ReDoS - Wikipedia

ReDoS - Wikipedia

ReDOS (Regex DOS)

ReDOS (Regex DOS)

자바스크립트에서의 정규식, 이론부터 조심해야 할 것 까지

Home

recheck

recheck