Summary
Hash flooding làm máy chủ chậm đi vì nó buộc hash table phải hoạt động trong trường hợp xấu nhất - thời gian tra cứu tuyến tính (linear lookup time). Cách hoạt động của nó như sau:
- Hoạt động bình thường của Hash Table:
- Một hash table ánh xạ các key tới các value bằng cách sử dụng một hash function.
- Lý tưởng nhất, các key được phân phối đều trên các hash bucket khác nhau, dẫn đến việc tra cứu hiệu quả với độ phức tạp O(1).
- Khai thác xung đột (Collisions):
- Kẻ tấn công tạo ra nhiều input có cùng giá trị hash (xung đột).
- Những input này sau đó được gửi đến máy chủ, làm đầy một hash bucket duy nhất.
- Suy giảm hiệu năng thành tra cứu tuyến tính (Linear Lookup):
- Khi nhiều key rơi vào cùng một bucket, nhiều cách triển khai hash table sẽ lưu trữ chúng trong một danh sách liên kết (linked list) hoặc một cấu trúc dữ liệu phụ khác.
- Thay vì thời gian tra cứu O(1) như mong đợi, máy chủ giờ đây phải duyệt qua một danh sách dài, dẫn đến thời gian tra cứu O(n).
- Tấn công từ chối dịch vụ (Denial of Service):
- Mọi thao tác tra cứu, chèn hoặc xóa trong hash table bị ảnh hưởng đều trở nên chậm hơn đáng kể.
- Nếu hash table được sử dụng cho các hoạt động quan trọng (ví dụ: xử lý yêu cầu HTTP, quản lý phiên), toàn bộ máy chủ sẽ chậm lại hoặc không phản hồi.
Tham khảo: Collision attack - Wikipedia
Summary
Để ngăn chặn hash flooding mà không làm cho hash function trở nên quá phức tạp, các keyed hash functions mới đã được giới thiệu, với mục tiêu bảo mật là khó tìm thấy các xung đột miễn là key không bị lộ. Chúng có thể chậm hơn các hàm hash trước đây, nhưng vẫn dễ tính toán hơn nhiều so với các cryptographic hash.