Nghiên cứu mới tìm ra cách bẻ khóa chữ ký RSA mà không cần phân tích thừa số nguyên tố

Cơ chế giả mạo chữ ký không cần phân tích thừa số nguyên tố

Trong suốt nhiều thập kỷ, nền tảng an toàn của thuật toán mã hóa khóa công khai RSA luôn gắn liền với độ khó của bài toán phân tích một số nguyên cực lớn thành các thừa số nguyên tố (integer factoring). Giới nghiên cứu mật mã mặc định rằng để tạo ra một chữ ký số RSA hợp lệ khi không có khóa riêng (private key), kẻ tấn công bắt buộc phải phân tích số nguyên N bằng thuật toán sàng trường số tổng quát (GNFS). Đây là tác vụ đòi hỏi siêu máy tính với chi phí hàng chục triệu USD đối với khóa 1024-bit và gần như bất khả thi với khóa 2048-bit hay 4096-bit.

Tuy nhiên, nhóm tác giả gồm giáo sư Nadia Heninger tại UC San Diego cùng các đồng nghiệp tại Viện Inria Nancy đã chứng minh một hướng tiếp cận hoàn toàn khác. Dựa trên thuật toán căn bậc e từng được các nhà mật mã học Antoine Joux, David Naccache và Emmanuel Thomé đề xuất năm 2007 nhưng ít được chú ý, nhóm nghiên cứu đã hiện thực hóa cuộc tấn công thực tế nhắm vào biến thể “textbook RSA” (raw RSA). Thay vì cố gắng tìm khóa riêng, kỹ thuật này tương tác trực tiếp với một signing oracle (hệ thống cho phép gửi dữ liệu vào và nhận lại chữ ký số, ví dụ như module bảo mật phần cứng HSM) để trích xuất đủ dữ liệu toán học.

Theo báo cáo mã số 2026/2131 trên kho lưu trữ ePrint IACR, nhóm đã gửi khoảng 2^32 (tương đương 4 tỷ) truy vấn tới một thiết bị phần cứng HSM Thales Luna đóng vai trò oracle. Sau khi hoàn tất giai đoạn sàng lọc số liệu, họ có thể giả mạo chữ ký cho bất kỳ tài liệu tùy ý nào hoàn toàn ngoại tuyến (offline) mà không cần chạm tới thiết bị thêm lần nào nữa.

Khối lượng tính toán sụt giảm hàng trăm lần so với phương pháp cũ

Mức sụt giảm tài nguyên tính toán của phương pháp mới đã khiến các chuyên gia mật mã học bất ngờ. Karsten Nohl, chuyên gia mật mã và giám đốc đổi mới tại Allurity, nhận định với trang Ars Technica rằng nếu kết quả này vượt qua vòng bình duyệt đồng cấp, đây sẽ là một đột phá nền tảng bởi từ trước đến nay ai cũng tin bẻ khóa RSA đồng nghĩa với phân tích số nguyên.

Số liệu từ Tom’s Hardware và Ars Technica cho thấy số phép tính cần thiết đã giảm sâu trên mọi độ dài khóa:

• Khóa RSA 1024-bit: Giảm từ 2^80 phép tính (cần 500.000 đến 1.000.000 CPU core-years) xuống còn 2^65 phép tính (thực tế tốn 1.380 CPU core-years trong 5 tháng trên cụm CPU thông thường). Đáng chú ý, sau 1.200 core-years tiền tính toán, việc tạo chữ ký giả mới chỉ tốn 180 core-years.
• Khóa RSA 2048-bit: Độ phức tạp giảm từ 2^112 xuống 2^90 phép tính.
• Khóa RSA 3072-bit: Độ phức tạp giảm từ 2^128 xuống 2^105 phép tính.
• Khóa RSA 4096-bit: Độ phức tạp giảm từ 2^144 xuống 2^119 phép tính.

Các cơ quan tiêu chuẩn bảo mật quốc tế như Viện Tiêu chuẩn và Kỹ thuật Quốc gia Mỹ (NIST), Cơ quan An ninh Quốc gia Mỹ (NSA) và Cơ quan An ninh Mạng Châu Âu (ENISA) đều đặt ra quy chuẩn: một hệ mật mã an toàn phải đạt độ bảo mật tối thiểu 128-bit (tương đương cần ít nhất 2^128 phép tính để phá). Với việc bị hạ xuống mức 2^119, ngay cả khóa 4096-bit vốn được xem là rất an toàn cũng không còn đáp ứng chuẩn này trong mô hình tấn công qua oracle.

Phạm vi ảnh hưởng thực tế và lộ trình chuyển dịch khỏi RSA

Dù mang tính đột phá về mặt toán học, nguy cơ trên diện rộng đối với người dùng phổ thông hiện vẫn trong tầm kiểm soát. Kỹ thuật này chỉ hoạt động đối với dạng textbook RSA hoặc blind RSA – những hệ thống không áp dụng cơ chế đệm an toàn (padding) như PKCS#1 v1.5 hay RSA-PSS. Các kết nối web thông thường (chứng chỉ HTTPS/TLS, SSH) đều sử dụng padding nên không bị ảnh hưởng trực tiếp bởi phương thức này.

Tuy nhiên, dạng raw RSA và blind RSA vẫn đang được sử dụng ở nhiều vị trí quan trọng trong hạ tầng công nghệ. Tiêu biểu là các giao thức bảo vệ quyền riêng tư như Privacy Pass của Cloudflare, tính năng iCloud Private Relay và Private Cloud Compute của Apple. Ngoài ra, các thiết bị phần cứng tuân thủ chuẩn PKCS #11, smart card, token USB xác thực và chip TPM cũng hỗ trợ các hàm ký số dạng này. Rào cản lớn nhất hiện tại của kẻ tấn công là phải thực hiện được hàng tỷ truy vấn tới máy chủ mục tiêu mà không bị hệ thống tường lửa hay rate-limit phát hiện.

Dẫu vậy, nhóm tác giả lưu ý rằng thuật toán họ áp dụng mới là phiên bản thử nghiệm ban đầu trên CPU, chưa được tối ưu hóa bằng GPU hay các mô hình tính toán tăng tốc. Khi được tinh chỉnh sâu hơn, thời gian bẻ khóa hoàn toàn có thể rút ngắn hơn nữa. Kết quả nghiên cứu này là hồi chuông cảnh báo rõ ràng, thúc đẩy các tổ chức và doanh nghiệp nhanh chóng hoàn tất quá trình chuyển đổi từ RSA sang mật mã đường cong elip (ECC) và các tiêu chuẩn mật mã hậu lượng tử (Post-Quantum Cryptography).