Regular expression Denial of Service (ReDoS) là một cuộc tấn công từ chối dịch vụ, khai thác thực tế là hầu hết các triển khai Biểu thức chính quy có thể gặp các tình huống cực đoan khiến chúng hoạt động rất chậm (liên quan theo cấp số nhân với kích thước đầu vào). Sau đó, kẻ tấn công có thể khiến một chương trình sử dụng Biểu thức chính quy (Regex) đi vào các tình huống khắc nghiệt này và sau đó bị treo trong một thời gian rất dài.
Các bài viết liên quan:
Tổng Quan Regular expression Denial of Service (ReDoS)
Thuật toán Regex naïve algorithm có vấn đề
Thuật toán Regex naïve algorithm xây dựng một tự động hóa hữu hạn không xác định (NFA), là một máy trạng thái hữu hạn trong đó đối với mỗi cặp trạng thái và biểu tượng đầu vào có thể có một số trạng thái tiếp theo. Sau đó, động cơ bắt đầu chuyển đổi cho đến khi kết thúc đầu vào. Vì có thể có một số trạng thái tiếp theo có thể xảy ra, một thuật toán xác định được sử dụng. Thuật toán này thử lần lượt tất cả các đường có thể có (nếu cần) cho đến khi tìm thấy kết quả phù hợp (hoặc tất cả các đường đều được thử và không thành công).
Ví dụ: mẫu Regex hoặc bộ định lượng ^ (a +) + $ được đại diện bởi NFA sau:
Đối với đầu vào aaaaX, có 16 đường dẫn có thể có trong đồ thị trên. Nhưng đối với aaaaaaaaaaaaaaaaX, có 65536 đường dẫn có thể xảy ra, và con số gấp đôi cho mỗi đường bổ sung a. Đây là một trường hợp cực đoan khi thuật toán ngây thơ có vấn đề, vì nó phải vượt qua nhiều đường dẫn để tìm đầu vào không phù hợp.
Nguyên nhân gốc rễ của ví dụ trên là trong một tính năng của công cụ Regex được gọi là backtracking. Đơn giản, nếu đầu vào (mã thông báo) không khớp, công cụ sẽ quay trở lại các vị trí trước đó, nơi nó có thể đi theo một con đường khác. Động cơ thử điều này nhiều lần cho đến khi nó khám phá tất cả các con đường có thể. Trong ví dụ trên, tính năng này tạo ra một vòng lặp chạy dài vì có nhiều đường dẫn để khám phá do mẫu Regex không hiệu quả.
Lưu ý rằng không phải tất cả các thuật toán đều ngây thơ, và thực sự các thuật toán Regex có thể được viết một cách hiệu quả. Thật không may, hầu hết các công cụ Regex ngày nay cố gắng giải quyết không chỉ các Regex “thuần túy” mà còn giải quyết các Regex “mở rộng” với các “bổ sung đặc biệt”, chẳng hạn như tham chiếu ngược mà không phải lúc nào cũng được giải quyết một cách hiệu quả (xem Mẫu cho các ngôn ngữ không thông thường trong Wiki -Regex để biết thêm một số chi tiết). Vì vậy, ngay cả khi Regex không được “mở rộng”, một thuật toán ngây thơ vẫn được sử dụng.
Ác ma Regex
Một mẫu Regex được gọi là Evil Regex nếu nó có thể gặp khó khăn với đầu vào được chế tạo.
Evil Regex chứa:
- Nhóm với sự lặp lại
- Bên trong nhóm lặp lại:
- Sự lặp lại
- Luân phiên với chồng chéo
Ví dụ về Evil Regex:
(a+)+([a-zA-Z]+)*(a|aa)+(a|a?)+(.*a){x} for x \> 10
Tất cả những điều trên đều dễ bị ảnh hưởng bởi đầu vào aaaaaaaaaaaaaaaaaaaaaaaa! (Độ dài đầu vào tối thiểu có thể thay đổi một chút, khi sử dụng máy nhanh hơn hoặc chậm hơn).
Các cuộc tấn công
Kẻ tấn công có thể sử dụng kiến thức trên để tìm kiếm các ứng dụng sử dụng Biểu thức chính quy, có chứa Evil Regex và gửi thông tin đầu vào được chế tạo kỹ lưỡng, điều này sẽ làm treo hệ thống. Ngoài ra, nếu bản thân Regex bị ảnh hưởng bởi đầu vào của người dùng, thì kẻ tấn công có thể đưa Evil Regex vào và làm cho hệ thống dễ bị tấn công.
Các yếu tố rủi ro ReDoS
Web dựa trên Regex:
Trong mỗi lớp của WEB đều có Biểu thức chính quy, có thể chứa Ác ma Regex. Kẻ tấn công có thể làm treo trình duyệt WEB (trên máy tính hoặc cũng có thể là trên thiết bị di động), treo Tường lửa ứng dụng web (WAF), tấn công cơ sở dữ liệu và thậm chí ngăn xếp một máy chủ WEB dễ bị tấn công.
Ví dụ: nếu một lập trình viên sử dụng Regex để xác thực phía máy khách của hệ thống và Regex chứa Evil Regex, kẻ tấn công có thể cho rằng Regex có lỗ hổng tương tự được sử dụng ở phía máy chủ và gửi một đầu vào được chế tạo kỹ lưỡng, ngăn xếp máy chủ WEB.
Các ví dụ về ReDoS
Regex dễ bị tổn thương trong kho lưu trữ trực tuyến
ReGexLib,id=1757 (email validation) – xem phần in đậm, đó là Evil Regex
^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$Đầu vào:
aaaaaaaaaaaaaaaaaaaaaaaaaa!
OWASP Validation Regex Repository, Java Classname – xem phần in đậm, đó là Evil Regex
^ (([a-z]) +.)^(([a-z])+.)+[A-Z]([a-z])+$
Đầu vào:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!
Tấn công ứng dụng web
- Mở một JavaScript
- Tìm Ác ma Regex
- Tạo một đầu vào độc hại cho Regex được tìm thấy
- Gửi giá trị hợp lệ qua proxy chặn
- Thay đổi yêu cầu chứa đầu vào độc hại
ReDoS thông qua Regex Injection
Ví dụ sau kiểm tra xem tên người dùng có phải là một phần của mật khẩu do người dùng nhập hay không.
String userName = textBox1.Text;
String password = textBox2.Text;
Regex testPassword = new Regex(userName);
Match match = testPassword.Match(password);
if (match.Success)
{
MessageBox.Show("Do not include name in password.");
}
else
{
MessageBox.Show("Good password.");
}Nếu kẻ tấn công nhập ^ (([a-z]) +.) + [A-Z] ([a-z]) + $ làm username và aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! làm mật khẩu, chương trình sẽ bị treo.
