ReDos Attack + Blind Regular Expression Injection Attack

webhacking.kr 리뉴얼된 문제들을 풀어보면서, 새로운 해킹 기법과 지식을 습득할 수 있었다ㅎㅎ
가장 대표적으로 이 문제가 있었는데, blind regex injection attack 과 ReDos에 대한 새로운 내용을 배울 수 있었던 문제라 해당 문제에 대한 간략한 writeup, 그리고 ReDos attack이 무엇인지 적어보고자 한다!

---

webhacking.kr regex master 문제

우선 이 문제의 경우, GET 방식으로 pattern 파라미터에 특정 내용을 보내주면 그대로 preg_match 함수의 인자로 사용되게 된다. 이 외에는 전혀 다른 힌트가 없다.

PHP manual을 참고해 preg_match함수에 대해 살펴본다면, pattern 파라미터는 regular expression이 들어가게 된다.
관련 공격 기법을 찾아보다가 Time based blind regular expression injection 을 찾아보게 되었다. 특히 파라미터를 통해 들어오는 regex expression의 경우, 해당 regex expression이 flag를 매치 하는지 확인할 방법이 없어보였는데, ReDos를 일으켜 reponse time을 통해 flag를 유추할 수 있었다.

---

Blind Regex injection이란?

Blind SQL injection 처럼, 타겟에 true 또는 false를 반환하는 질의를 하고, reponse에 따라 그 질의에 대한 답이 true 또는 false인지 판단하는 것이다.

참고 사이트: https://portswigger.net/daily-swig/blind-regex-injection-theoretical-exploit-offers-new-way-to-force-web-apps-to-spill-secrets

Blind regex injection: Theoretical exploit offers new means of forcing web apps to spill secrets

보통 Lord of SQL 을 풀때 조건문과 sleep 함수를 사용해서 조건이 참이면 delay를 발생시키고 응답시간을 관찰하면서 Blind SQL injection 공격을 했었는데,
Blind Regex injection도 이처럼 ReDos (Regular expression denial of service) 를 일으키면서 time delay를 발생시키는것 같았다. 특히, Regex 엔진이 'backtracking-based' 라면 ReDos를 야기시킬 수 있다고 한다.


https://diary.shift-js.info/blind-regular-expression-injection/#fn:further_research 에 의하면, ReDos 를 방지하기 위한 방법은 다음과 같다.

타임아웃을 도입하거나, non-backtracking engine을 사용하고, nested quantifier( (.*)*) 와 같은 패턴을 방지하는 방법이다. 이러한 패턴을 사용하면 ReDos를 일으킬 수 있을 것 같았다.


실제로 위 사이트에서는 다음과 같은 Regular expression으로 타임아웃이 도입된 application에 ReDos를 일으킬 수 있다고 한다.

^(?=(some regexp here))((.*)*)*salt$

위의 expression에 대해서 설명을 하자면,
?=R 이라는건 positive lookahead라는 것으로서,
((.*)*)*salt$ 와 일치하지 않는 input string이 주어졌을때,

• input string이 만약 R과 매치된다면 시간이 오래 걸리고 (ReDos 발생 O)
• 그렇지 않는다면 시간이 짧게 걸린다.

(이때, salt$는 random string이라고 한다.)

다음 expression의 경우 글자 길이를 알아낼 수 있다.

^(?=.{1})((.*)*)*salt$

---

문제로 돌아와서,
이렇게 flag에 대한 단서를 얻기 위해선

(flag에 대한 regular expression)(((.*)*)*)string

이런식으로 regular expression을 만들어 pattern 파라미터로 보내주고, 응답 시간에 따라 regular expression이 flag와 매치하는지 확인할 수 있다.


우선 flag 길이부터 알아내보고자 했다.

[\x00-\x7F]{글자길이}(((.*)*)*)!a

를 보내주면서, 네트워크 탭에서 응답 시간을 관찰하고 가장 오래 걸리는 페이로드를 찾을 수 있었다.

글자수는 delay가 가장 큰 28

뒤이어 FLAG{..부분 부터 구해냈는데, FL 로 시작하는 페이로드가 F로 시작하는 페이로드 중에 응답시간이 가장 길다는 것을 알 수 있다.

이렇게 하나씩 구하다가 자동화 스크립트가 있으면 좋을 것 같아서 파이썬으로 request를 보내고 reponse time을 받아오는 코드를 짜봤는데, 이상하게도 응답시간이 정확하지 않고 매번 달라지는 문제가 있었다.
그래서 브라우저 console에서 fetch를 이용해서 코드를 돌린다음 네트워크 탭에서 응답시간을 확인하는 방식으로 문제를 풀었다.

for (var i=0; i<=128; i++){
    fetch("http://regexmaster.webhacking.kr/?pattern="+String.fromCharCode(i)+"(((.%2B)%2B)%2B)!a", {
  "headers": {
    "accept": "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.9",
    "accept-language": "ko-KR,ko;q=0.9,en-US;q=0.8,en;q=0.7,ja;q=0.6",
    "upgrade-insecure-requests": "1"
  },
  "referrerPolicy": "strict-origin-when-cross-origin",
  "body": null,
  "method": "GET",
  "mode": "cors",
  "credentials": "omit"
});}

이외에 또 발생하는 문제가, flag 내용 중에 백 슬래시가 있는 문제였는데, 실제로 regular expression에서는 백슬래시 앞에 escape 문자 (\) 를 넣어줘야한다. request를 보낼때엔 escape 문자를 또 url encoding 해줘야했다.

클리어 했다.