개요

정규표현식을 이용한 Dos 공격인 “ReDos 공격” 에 대해 조사해본다.

기본개념

정규식 알고리즘

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

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

백트랙킹?

ReDos 취약점이 있는 곳

Node.js

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

정규식 체크툴

참고

정규 표현식 서비스 거부 공격: https://namu.wiki/w/%EC%A0%95%EA%B7%9C%20%ED%91%9C%ED%98%84%EC%8B%9D%20%EC%84%9C%EB%B9%84%EC%8A%A4%20%EA%B1%B0%EB%B6%80%20%EA%B3%B5%EA%B2%A9
https://www.hahwul.com/cullinan/redos/
https://wooncloud.tistory.com/118
https://ufo.stealien.com/2023-07-03/django-cve-2023-36053