Regular Expression Denial of Service Attack

September 11th, 2021

0x00 Một số thứ liên quan tới tiêu đề bài viết

Thi thoảng mình vẫn hay lướt Security Lab để đọc những bài nghiên cứu, thì có dạo mình đọc qua GHSL-2021-098: ReDoS in OpenProject - CVE-2021-32763 . Lỗi này mô tả chi tiết sản phầm OpenProject bị khai thác DoS,thông qua việc so khớp chuỗi với patern regex không chặt chẽ hay còn gọi là evil regex. Từ khoá ReDoS mình cũng thấy vài lần nhưng tự vã vào mặt mình mà nói thì mình đơn thuần chỉ nghĩ nó là Bypass DoS của một lỗi nào trước đây mà thôi. Nhưng sự thật thì ReDoS là cách viết ngắn gọn Regular-expression-Denial-of-Service.

Trước khi nói chi tiết vào cách mà ReDoS hoạt động thì mình sẽ nói lại một chút về NFA(Nondeterministic finite automaton) và DFA(Deterministic_finite_automaton).

NFA/DFA là 2 hàm chuyển đổi trạng thái nhận vào Q tập hợp hữu hạn các trạng thái,∑ là bảng chữ - tập các ký tự vào, q0 là trạng thái bắt đầu và cho ra tập F trạng thái kết thúc(trạng thái thành công).

Mình sẽ không giải thích nhiều về phần này, các bạn có thể tham khảo thêm tại bài giảng này. Ngoài ra nếu muốn tìm hiểu sâu hơn thì có thể xem qua what-is-the-enlightenment-im-supposed-to-attain-after-studying-finite-automata. Tiêu đề khá hài nhưng mình rất thích đọc các bài viết hỏi đáp và tranh luận như này. Hai đặc điểm chính của NFA/DFA có liên quan đến phần tiếp theo:

NFA:

Hàm chuyển ánh xạ: Q x ∑ ➙ 2^Q. Tức ứng với một trạng thái và một kí tự nhập, có thể có không, một hoặc nhiều phép chuyển trạng thái

Chấp nhận ε (kí hiệu rỗng)

Trả lời cho câu hỏi ε là gì tại đây : What-is-ε-NFA hoặc Epsilon NFA

ε(epsilon) giúp chuyển đổi trạng thái mà không cần kí tự đầu vào, chuyển tiếp từ trạng thái q(a) sang trạng thái q(b) như một chuỗi rỗng.

DFA:

Hàm chuyển ánh xạ: Q x ∑ ➙ Q. Tức ứng với một trạng thái và một kí tự nhập, chỉ có thể có một phép chuyển trạng thái.

Không chấp nhận ε (kí hiệu rỗng)

Trạng thái trong DFA là tập hợp con của các trạng thái trong NFA

0x01 Cách ReDoS hoạt động

Hiện nay, hầu hết các bộ máy regular expression trong các ngôn ngữ lập trình đều tuân theo thuật toán của Ken Thompson’s để xây dựng NFA từ một regular expression. Kết quả trả về từ bộ máy này là trạng thái thành công với chuỗi kí tự khớp, hoặc một trạng thái rỗng khi NFA đã duyệt qua hết tất cả những trạng thái có thể xảy ra trong tập hợp các trạng thái mà không có có một chuỗi khớp nào.

*Ví dụ 1: *Một ví dụ về các đường đi trạng thái từ cùng một mẫu regular expression a(b|c)e và chuỗi đầu vào abe giữa NFA và DFA bởi fsm_simulator:

dfa

Ví dụ 1:DFA Transition graph

nfa

Ví dụ 1:NFA Transition graph

Biểu đồ duyệt trạng thái NFA trên vẫn còn quá đơn giản đối với khả năng xử lý của máy tính. Ví dụ tiếp theo đây mình sẽ giải thích về backtracking, quay lùi cho đến khi tìm trạng thái được chấp nhận hoặc đã duyệt qua tất cả những thái có thể xảy ra.

*Ví dụ 2:* Tập trạng thái đầu vào gồm {acgf,acdf}. Trạng thái kết thúc thành công là acdf, bộ máy sẽ xử lý như thế nào?

Tóm tắt:

Gồm 2 đường đi trạng thái
Nút bắt đầu là nút 0 ứng với kí tự bắt đầu a
Nút kết thúc là 4 ứng với kí tự kết thúc là f

Ví dụ 2: Đường đi không khớp mẫu

Đầu tiên cả 2 đường đi trạng thái này đều đi đến nút 2 và 6 với các trạng thái của 2 đường đi này đều giống nhau.Sau đó đường trạng thái bên trên bắt đầu duyệt qua nút 3 với kí tự g. Kí tự g không nằm trong trạng thái cho phép acdf.

❌Kết thúc đường trạng thái tại nút này và xem như trạng thái thất bại là acgf.

Ví dụ 2: Đường đi khớp mẫu

Lúc này, backtracking hoạt động, bắt đầu lùi lại nút nơi cuối cùng khi 2 nút có trạng thái tương đồng trên cả 2 đường đi tức 2 và 6. Nút 2 đã bị loại ở bước trên, nên thực hiện duyệt tiếp từ nút 6. Duyệt đến nút 7 là kí tự d khớp với trạng thái cho phép và đi tới nút 4 để kết thúc.

✔️ Kết thúc đường trạng thái tại nút này và xem như trạng thái thành công là acdf.

Hãy thử nghĩ rằng nếu trường hợp tập các trạng thái đầu vào không bao gồm trạng thái kết thúc thành công, tập các trạng thái có khoảng 2^n trạng thái thì CPU sẽ cần bao nhiêu tài nguyên và thời gian để duyệt hết tập trạng thái này?

*Ví dụ 3:* Một tiện ích javascript sử dụng mẫu regular expression (^Author:|^Co-authored-by:)\s+(?<author>[^<]+)\s+(?<email><[^>]+>) với chức năng lấy ra lấy ra các chuỗi khớp với tên, địa chỉ email của người người dùng. Liệu nó có an toàn không?

Sử dụng chức năng debugger regex101.com để có thể xem các bước duyệt chuỗi khớp mẫu.

Trường hợp thứ nhất, chuỗi nhập vào trả về trạng thái cho phép (khớp): Author: dangkhai0x21 <dangkhai0x21@gmail.com>

match

Ví dụ 3: chuỗi so khớp mẫu

Với trường hợp này, cần 23 bước để tìm được chuỗi khớp với mẫu. Với lần duyệt đầu tiên đã tìm được chuỗi khớp.

Trường hợp thứ hai, chuỗi nhập vào không khớp với mẫu: Author: dangkhai0x21 <dangkhai0x21@gmail.com

notmatch

Ví dụ 3: chuỗi không so khớp mẫu

Trường hợp này cần đến 204 bước để xử lý đầu vào này. Kết quả trả về không tìm được chuỗi khớp nào.

So sánh 2 đầu vào:

Lí do:

\s+ cho phép có 1 hoặc nhiều kí tự space.
Nhóm group bắt các kí tự không chặt chẽ
Chuỗi đầu vào không bao gồm trạng thái kết thúc thành công vì thiếu kí tự >.

🔁 Vì nguyên nhân này mà CPU cần xử lý 1 vòng lặp hữu hạn bởi kẻ tấn công có thể tuỳ biến bằng việc thêm hoặc bớt kí tự space ở chuỗi đầu vào.

Hãy xem biểu đồ xử lý để dễ hình dung hơn:

Ví dụ 3: Biểu đồ duyệt đường khi chuỗi không khớp

Biểu diễn [space] bằng kí tự [s] trên biểu đồ. evil space là kí tự space và kẻ tấn công có thể tuỳ chỉnh. Các kí tự space sẽ được chia làm 2 phần:

Phần thứ nhất sẽ khớp với nhóm (?<author>[^<]+)
Phần thứ hai sẽ khớp với \s+

Hậu quả của việc cho bộ máy regular expression chạy một vòng lặp với n đường đi sẽ như thế nào. Sử dụng trình biên dịch javascript để chạy đoạn mã dưới đây:

let regex = /(^Author:|^Co-authored-by:)\s+(?<author>[^<]+)\s+(?<email><[^>]+>)/
t = performance.now()
regex.test('Author: dangkhai0x21' + ' '.repeat(9999) + '<dangkhai0x21@gmail.com')
console.log(performance.now() - t)

Ví dụ 3: Thời gian trả về khi nhập vào một chuỗi không an toàn sấp xỉ 103 ms

Ví dụ 3: Thời gian trả về khi nhập vào một chuỗi an toàn là 0 ms

Nếu bạn thử repeat(999999999) thì …

0X01.1 Phân tích CVE-2020-5243

Dưới đây là chức năng session history ở một số ứng dụng, chức năng này có nhiệm vụ lưu lại các phiên đăng nhập trên các thiết bị, địa điểm khác nhau.

Hình mô tả chức năng session history

Chức năng này đa phần sử dụng regular expression để lọc ra các thiết bị định danh cho người dùng. Đầu vào mà máy chủ thường dùng để xử lý cho chức năng này là trường User-Agent được đính kèm trong header gửi đến máy chủ.

Hình mô tả trường User-Agent

Và phần xử lý này của ứng dụng cũng thường dễ bị tấn công bởi ReDoS. Cụ thể có thể xem qua mã lỗi CVE-2020-5243 mô tả rằng chức năng phân tích trường User-Agent của thư viện ua-parser có thể bị khai thác ReDoS do bắt các nhóm chồng chéo nhau không chặt chẽ.

Đây mẫu regular expression gây lỗi: ; *([^;/]+) Build[/ ]Huawei(MT1-U06|[A-Z]+\d+[^\);]+)[^\);]*\)

Điểm gây lỗi chính là nơi bắt ra 2 nhóm \d+[^\);]+) và [^\);]* trong cú pháp, như ví dụ 3 nói trên thì evil character từ kẻ tấn công truyền vào có thể trùng khớp với cả 2 nhóm trên.

Mô tả 2 nhóm bắt kí tự chồng chéo lên nhau

Vì truyền lên một chuỗi đầu vào không khớp mẫu, kèm theo là hữu hạn các evil character dẫn đến bộ máy này cần xử lí hữu hạn các đường đi trạng thái để kết thúc. Từ đó khiến cho các máy chủ trở nên quá tải và gây tắc nghẽn.

Sau khi nhận được báo cáo, thư viện đã cung cấp bản vá khắc phục như bên dưới.

Trong bản vá này loại đi nhóm [^\);]* khỏi cú pháp đã giải quyết được vấn đề các nhóm bắt kí tự chồng chéo lên nhau.

0X02 ReDoS trong Whitebox

Tìm kiếm nơi có thể xảy ra ReDoS phổ biến hơn trong Whitebox, vì cách thức phát hiện loại tấn công này chủ yếu phân tích các mẫu regular expression từ ứng dụng. Từ đó tìm ra các kí tự potential có thể dẫn đến backtracking.

Đã có nhiều nhà nghiên cứu đóng góp các công cụ phân tích mẫu regular expression độc hại có thể phát hiện ra hầu hết các mẫu có khả năng bị khai thác. Ví dụ như:

regexploit phát triển bở @doyensec hỗ trợ khá nhiều ngôn ngữ như java,javascript,python.c-sharp
saferegex phát triển bởi @jkutner
…

Các công cụ này đã làm tốt công việc của nó là tìm được các mẫu có khả năng gây lỗi đến 80%. Tuy nhiên vẫn bỏ qua một số mẫu phức tạp.

0x03 ReDoS trong Blackbox

Khai thác ReDoS trong Blackbox ít khả hơn so với WhiteBox, vì nó như một kiểu khai thác mù. Cách khai thác vẫn chỉ có thể suy đoán các tham số dễ bị tấn công như các trường email, phone number, session history.... Các trường mà ứng dụng yêu cầu sự phân biệt rõ ràng bởi kí tự thường, in hoa, số, kí tự đặc biệt.

Sau khi tìm được các điểm vào có thể khai thác thì lại có 2 cách tấn công có thể dùng:

Tự động 100%:
- Bao gồm 2 bước chính sau khi tìm được đầu vào có khả năng khai thác là đưa ra tập n giả định mẫu regular expression từ server. Bước tiếp là đưa ra tập m chuỗi đầu độc hại để lần lượt khai thác các mẫu giả định kia. Có thể xem là mất n^m bước khai thác.
Semi(thủ công 50%, tự động 50%):
- Bỏ qua bước đưa ra n giả định mẫu mà người khai thác sẽ tự gợi ý mẫu regular expression. Sau đó sẽ tự động thực hiện vét cạn m chuỗi vào độc hại.

Đối với cách tự động 100% kia mình sợ rằng chưa kịp tấn công máy chủ thì máy mình đã tự crash rồi. Vì vậy mà hiện tại vẫn chưa có công cụ nào khả quan để kiểm tra blackbox.

0x04 Ngăn chặn ReDoS

Làm thế nào để tạo ra mẫu regular expression vừa linh hoạt và an toàn?

Với người một số bạn chưa có kiến thức bảo mật về phần này đang cố gắng tạo ra một mẫu regular expression dài ngoẵn. Nhằm mục đích bắt được nhiều nhóm, nhiều mục tiêu, bắt nó như một mẫu đa dụng. Nhưng đôi khi sẽ biến tính năng thành lỗ hỏng.

Vậy làm sao để giải quyết câu hỏi ở trên? Mình sẽ liệt kê một số cách để hạn chế khả năng bị khai thác thông qua mẫu như sau:

Sử dụng DFA -> An toàn nhưng sẽ không linh hoạt vì hạn chế các trạng thái kết thúc.
Trở thành một người viết mẫu chuẩn 4.0:
- Đừng cố gắng tạo ra một mẫu regular expression quá đa nhiệm. Đôi khi sẽ biến tính năng thành lỗ hỏng. Cố quá sẽ thành quá cố >.<
- Nên ràng buộc chiều dài với các kí tự tự do:
  
  Ví dụ như không sử dụng \s+ hoặc \w+ \d+ mà nên ràng buộc chiều dài \s{1,3} \w{1,3}
- Có thể sử dụng backreferences để kiểm tra số lần lặp lại của kí tự để loại bỏ các kí tự trùng.
- Hãy xét thời gian thực hiện cho các lần sử dụng máy regex, nếu trường hợp việc xử lý đầu vào quá lâu thì có thể dừng tiến trình và thông báo chuỗi phức tạp.
- Sử dụng * và + đúng lúc đúng chỗ.
- Bắt chính xác các chuỗi thuộc group.
- Sử dụng các thư viện khác như strip(),trim(),replace(),... để làm sạch các đầu vào trước khi dùng đến regular expression.
- …