당신의 Java Regex가 악용될 수 있습니다 (그리고 이를 방지하는 방법)

Source: Dev.to

대부분의 개발자는 입력 검증이 곧 발생할 서비스 거부(DoS) 취약점이라는 사실을 깨닫지 못합니다. 무슨 말인지 보여드리겠습니다.

String regex = "^([a-zA-Z0-9]+)+@[a-zA-Z0-9]+\\.[a-zA-Z]{2,}$";
Pattern.compile(regex).matcher(input).matches();

괜찮아 보이죠? 이제 다음 입력을 넣어보세요:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

CPU 사용량이 100 %에 고정됩니다. 이것을 ReDoS(Regular Expression Denial of Service)라고 하며, Java의 정규식 엔진이 백트래킹을 사용하기 때문에 발생합니다. 특정 패턴은 매칭이 실패할 때 지수 시간 복잡도를 초래합니다.

공격자들은 이를 알고 있습니다. 그들은 정교하게 만든 입력을 검증 엔드포인트에 보내고 서버가 과열되는 모습을 지켜봅니다.

백트래킹 문제

Java의 java.util.regex는 백트래킹을 사용하는 NFA(비결정적 유한 자동자)를 사용합니다. 매칭이 중간에 실패하면 엔진은 뒤로 돌아가 다른 경로를 시도합니다. ([a-zA-Z0-9]+)+와 같은 중첩된 수량자는 경로 수가 지수적으로 폭발합니다.

입력 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!는 33자를 가지고 있습니다. 정규식 엔진은 포기하기 전까지 약 2³³개의 조합을 시도하게 되며, 이는 단일 검증 호출당 약 80억 번의 연산에 해당합니다.

해결 방법

Google이 만든 RE2라는 다른 종류의 정규식 엔진이 있습니다. 이는 DFA(결정적 유한 자동자)를 사용해 선형 시간 매칭을 보장합니다. 패턴이나 입력이 얼마나 악의적이든 O(n) 시간(여기서 n은 입력 길이) 안에 끝납니다.

저는 Rules 라는 Java 검증 라이브러리를 개발했으며, 여기에는 RE2J(RE2의 Java 포트)의 패치된 포크가 포함되어 있습니다. 이 포크는 원본 구현에서 발견된 몇몇 취약점을 수정했습니다.

Rule email = StringRules.matches(
    "^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}$"
);

ValidationResult result = email.validate(userInput);
if (result.isValid()) {
    // safe to use
}

같은 패턴이지만 이제는 무기로 사용할 수 없습니다. RE2J 엔진은 백트래킹을 전혀 하지 않기 때문에 재앙적인 백트래킹이 발생하지 않습니다.

또 어떤 문제가 발생할 수 있을까

HashDoS

공격자는 모든 해시가 같은 버킷에 매핑되도록 키를 조작해 O(1)인 HashMap 조회를 O(n)으로 만들 수 있습니다. 이 라이브러리는 무작위 키를 사용하는 SipHash‑2‑4 기반 SecureHashMap을 제공해 이를 방지합니다.

타이밍 공격

equals()로 비밀을 비교하면 타이밍 차이를 통해 정보가 유출됩니다. 문자별 비교는 불일치 시 조기에 종료되므로 공격자는 비밀번호를 한 글자씩 추측할 수 있습니다. 라이브러리는 상수 시간 비교 함수를 제공합니다.

재귀에 의한 스택 오버플로우

자기 참조 구조는 검증 중에 스택을 초과하게 만들 수 있습니다. 라이브러리는 깊이를 추적하고 사이클을 감지합니다.

간단한 예시

여러 규칙을 조합해 사용자 등록을 검증하는 예시:

Rule username = Rules.all(
    StringRules.notBlank(),
    StringRules.lengthBetween(3, 20),
    StringRules.matches("^[a-zA-Z0-9_]+$")
);

Rule password = Rules.all(
    StringRules.minLength(12),
    StringRules.matches("[A-Z]"),
    StringRules.matches("[a-z]"),
    StringRules.matches("[0-9]")
);

username.validate("user_dev").isValid();   // true
password.validate("SecurePass123").isValid(); // true

가져오기

Maven

io.github.xoifaii
rules
1.0.0

또는 GitHub 저장소에서 클론하여 살펴볼 수 있습니다. 전체 API 문서는 위키에 있습니다. RE2J 포크가 번들되어 있으며 외부 의존성이 전혀 없습니다.

공개적으로 서비스되는 Java 애플리케이션에서 정규식을 사용해 입력을 검증한다면, 패턴이 취약한지 확인해 볼 가치가 있습니다. recheck 같은 도구는 ReDoS 취약성을 분석해 주어 매우 유용합니다.

아니면 처음부터 문제 자체를 불가능하게 만드는 엔진을 사용하면 됩니다.