Phát hiện tấn công từ chối dịch vụ cho thuật toán Hash của Ruby (CVE-2011-4815)

Đăng bởi Urabe Shyouhei vào 28 Dec 2011

Tác động

Đây là vấn đề liên quan đến độ phức tạp tính toán. Một chuỗi các chuỗi ký tự được tạo thủ công đặc biệt khiến các giá trị hash của chúng va chạm với nhau đã được phát hiện. Với các chuỗi như vậy, kẻ tấn công có thể thực hiện tấn công từ chối dịch vụ bằng cách, ví dụ, đưa chúng làm tham số POST của các yêu cầu HTTP cho ứng dụng Rails của bạn.

Mô tả chi tiết

Tình huống tương tự như trường hợp được phát hiện cho Perl vào năm 2003. Trong dòng 1.8 của Ruby, chúng tôi sử dụng hàm hash xác định để hash một chuỗi. Ở đây “xác định” có nghĩa là không có thông tin nào khác ngoài chính chuỗi đầu vào được sử dụng để tạo giá trị hash. Vì vậy bạn có thể tính trước giá trị hash của một chuỗi. Bằng cách thu thập một loạt các chuỗi có giá trị hash giống nhau, kẻ tấn công có thể khiến ruby xử lý va chạm các bin của bảng hash (bao gồm các instance của lớp Hash). Thuộc tính O(1) amortized của bảng hash phụ thuộc vào tính đồng đều của phân phối giá trị hash. Bằng cách đưa đầu vào được tạo thủ công như vậy, kẻ tấn công có thể khiến bảng hash hoạt động chậm hơn nhiều so với dự kiến (cụ thể là O(n²) để xây dựng bảng n phần tử trong trường hợp này).

Các phiên bản bị ảnh hưởng

• Ruby 1.8.7-p352 và tất cả các phiên bản trước đó.

Tất cả dòng Ruby 1.9 không bị ảnh hưởng bởi loại tấn công này. Chúng không chia sẻ cài đặt hash với dòng Ruby 1.8.

Giải pháp

Giải pháp của chúng tôi là xáo trộn hàm hash chuỗi bằng một số bit ngẫu nhiên được tạo bởi PRNG. Bằng cách này, giá trị hash của một chuỗi không còn mang tính xác định nữa. Nghĩa là, kết quả String#hash chỉ nhất quán trong thời gian sống của tiến trình hiện tại và sẽ tạo ra số khác cho lần khởi động tiếp theo. Để phá vỡ tình huống này, kẻ tấn công phải tạo một tập hợp các chuỗi có khả năng chống lại loại xáo trộn này. Điều này được cho là khá khó khăn.

Vui lòng nâng cấp lên ruby 1.8.7-p357.

Lưu ý

• Hãy nhớ rằng giải pháp này không có nghĩa là thuật toán hash của chúng tôi an toàn về mặt mật mã. Nói đơn giản, chúng tôi đã sửa bảng hash nhưng chưa sửa điểm yếu của String#hash. Kẻ tấn công vẫn có thể khai thác nó một khi họ có được một cặp chuỗi và giá trị hash được trả về từ String#hash. Bạn không được tiết lộ kết quả String#hash. Nếu bạn cần làm những việc như vậy, hãy cân nhắc sử dụng các thuật toán hash an toàn thay thế. Một số trong số đó (như SHA256) được cung cấp trong thư viện chuẩn của Ruby.

• Đối với những ai biết các thuật toán hash thay thế trong code base của chúng tôi: chúng tôi không hỗ trợ chúng (chúng bị tắt theo mặc định). Bằng cách chọn chúng, chúng tôi cho rằng bạn có thể đọc C, và bạn có thể hiểu vấn đề gì với thuật toán mặc định. Hãy đảm bảo rằng lựa chọn của bạn là an toàn theo trách nhiệm của riêng bạn.

Ghi nhận

Ghi nhận Alexander Klink alexander.klink@nruns.com và Julian Waelde jwaelde@cdc.informatik.tu-darmstadt.de vì đã báo cáo vấn đề này.

SỬA một số liên kết liên quan:

• CVE-2011-4815 đã được gán cho vấn đề này.
• oCERT.org đã đăng thông báo về vấn đề này.
• JRuby đã phát hành phiên bản 1.6.5.1 để sửa vấn đề tương tự. Các triển khai ruby thay thế khác cũng có thể bị ảnh hưởng.
• Tài khoản Twitter @hashDoS thu thập thông tin về các cuộc tấn công va chạm hash.