I. 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)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

II. 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 NFADFA 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
image

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 26 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.

image

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 26. 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:

image

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:

image

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)

image-20210901103932152

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

image-20210901103959567

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ì ...


Tác giả: Nguyễn Đặng Khải