Thuật toán là một cơ chế mật mã để xác thực các thông điệp và thực thể bằng kỹ thuật số. Chúng được sử dụng rộng rãi bởi các ứng dụng nhắn tin an toàn, trình duyệt Internet, thương mại điện tử và nhiều ứng dụng khác. Thật không may, tất cả các thuật toán chữ ký số đang được sử dụng ngày nay (ví dụ như RSA và ECDSA) đều dựa trên độ khó của bài toán phân tích số hoặc bài toán tính logarit rời rạc.
Tuy nhiên, những vấn đề này rất dễ dàng đối với , điều này có nghĩa là khi một máy tính lượng tử đủ mạnh được xây dựng, nó có thể được sử dụng để mạo danh người dùng trên WhatsApp, cung cấp cho người dùng các trang web giả mạo và gửi cho bạn các bản cập nhật phần mềm độc hại. Để tránh thảm họa này, các nhà mật mã đã làm việc không ngừng nghỉ để thiết kế các thuật toán chữ ký số mới an toàn trước những kẻ tấn công bằng máy tính lượng tử.
Năm 2016, do những tiến bộ liên tục trong tính toán lượng tử và mối đe dọa rằng máy tính lượng tử cuối cùng sẽ phá vỡ tất cả các thuật toán mật mã hiện đang được sử dụng, Viện Tiêu chuẩn và Công nghệ Quốc gia Mỹ (National Institute of Standards and Technology - NIST) đã bắt đầu một dự án kéo dài nhiều năm với mục tiêu là chuẩn hóa một hoặc nhiều thuật toán mật mã khóa công khai kháng lượng tử cho mã hóa khóa công khai, thiết lập khóa và thuật toán chữ ký số.
Các nhóm nghiên cứu từ khắp nơi trên thế giới đã phản hồi với hơn 70 lần đệ trình các lược đồ mật mã, cùng với các tham số để đáp ứng ba cấp độ bảo mật (security level) ngày càng tăng là SL1, SL3 và SL5. Sau đó, NIST và cộng đồng mật mã bắt đầu với việc phân tích mật mã. Trong số 19 thuật toán chữ ký điện tử được chấp nhận cho vòng 1, có 9 thuật toán tiến vào vòng 2 (01/2019), trong đó 3 thuật toán đã được công bố lọt vào vòng chung kết thứ 3 (7/2020) là Dilithium, Falcon và Rainbow. Sau 2 năm, vào đầu tháng 7/2022, NIST đã công bố 3 thuật toán chữ ký số sẽ được chuẩn hóa là Dilithium, Falcon và SPHINCS+ [1]. Như vậy Rainbow đã bị loại. Về quá trình tuyển chọn của NIST, bạn đọc có thể tham khảo thêm [2] để biết thêm chi tiết.
Rainbow, dựa trên lược đồ Unbalanced Oil and Vinegar (UOV), là một lược đồ chữ ký đa biến, với tính bảo mật của nó dựa vào độ khó của bài toán giải một hệ lớn các phương trình bậc hai đa biến trên một trường hữu hạn. Cũng giống như lược đồ chữ ký RSA, Rainbow sử dụng một hàm cửa sập.
Trong khi RSA sử dụng phép tính lũy thừa modulo, Rainbow sử dụng việc tính một hệ các đa thức bậc hai nhiều biến. Đặc tính quan trọng của hàm cửa sập là nó có thể tính được rất hiệu quả nhưng rất khó để đảo ngược, ngoại trừ việc biết một thông tin (bí mật) cửa sập nào đó, và sẽ dễ dàng tính được đầu vào của hàm cửa sập khi được cho đầu ra của nó. Điều này có thể được sử dụng để tạo một lược đồ chữ ký số: Để ký một tin nhắn, người ta băm thông điệp và đặt giá trị băm đó làm đầu ra của hàm cửa sập; chữ ký khi đó là đầu vào mà dẫn đến kết quả đầu ra của hàm.
Trong trường hợp của Rainbow, chữ ký của một thông báo là một phép gán cho các biến mà được tính thành giá trị băm của thông báo đó. Ví dụ, đối với mức bảo mật thấp nhất của NIST vòng 3, đề xuất là sử dụng m = 64 đa thức có n = 100 biến trên trường hữu hạn có q = 16 phần tử. Trong lõi của cửa sập là một không gian con tuyến tính của không gian đầu vào, trong đó tất cả m đa thức bậc hai đều trở nên bằng 0; với sự hiểu biết về không gian con này, người ta có thể giải hệ phương trình một cách hiệu quả và giả mạo chữ ký điện tử.
Trái ngược với lược đồ chữ ký RSA, Rainbow được cho là có thể chống lại sức mạnh của các máy tính lượng tử quy mô lớn.
Các lược đồ chữ ký đa biến đã tồn tại hơn 20 năm. Bài toán giải các phương trình đa biến cũng nảy sinh một cách tự nhiên trong các lĩnh vực khác của toán học và khoa học máy tính, nhìn chung đã được nghiên cứu kỹ lưỡng. Tuy nhiên, việc phân tích bài toán cụ thể nhằm tìm kiếm không gian con tuyến tính bí mật trong lõi của cửa sập chỉ xảy ra trong những năm sau khi các lược đồ chữ ký đa biến được đề xuất.
Sự tiến sâu của Rainbow trong quá trình tiêu chuẩn hóa NIST trong vài năm qua dẫn đến sự quan tâm mới đáng kể và yêu cầu phân tích mật mã được cải thiện, tăng các tham số của Rainbow cho vòng 3 của NIST. Vào tháng 10/2020, trong bài báo “Cải tiến thám mã UOV và Rainbow” [3], Beullens đã đưa ra hai tấn công mới, đó là Tấn công giao nhau (intersection attack) và tấn công MinRank hình chữ nhật (Rectangular MinRank attack), chúng làm giảm đáng kể tính bảo mật về mặt lý thuyết của Rainbow.
Ngày 25/02/2022, trên website của Hiệp hội Nghiên cứu Mật mã Quốc tế đã xuất hiện bài báo “Phá Rainbow mất một dịp nghỉ cuối tuần trên máy tính xách tay” [4] của Ward Beullens, một nghiên cứu viên cao cấp (PostDoc) tại IBM Research. Sau đây là tóm tắt của bài báo này:
Công trình này giới thiệu các cuộc tấn công khôi phục khóa mới chống lại lược đồ chữ ký Rainbow, là một trong ba lược đồ chữ ký cuối cùng vẫn nằm trong Dự án Chuẩn hóa Mật mã Hậu lượng tử của NIST. Các cuộc tấn công mới vượt trội hơn các cuộc tấn công đã biết trước đây đối với tất cả các bộ tham số được gửi cho NIST và làm cho việc khôi phục khóa trở nên thực tế đối với bộ tham số SL1. Cụ thể, khi được cung cấp khóa công khai Rainbow cho các tham số SL1 của lần đệ trình vòng thứ hai, tấn công của chúng tôi trả về khóa bí mật tương ứng sau thời gian tính toán trung bình 53 giờ (2 ngày cuối tuần) trên máy tính xách tay tiêu chuẩn.
Bài báo này đã giúp Ward Beullens được tặng giải thưởng “Best Early Career Researcher Paper - Bài báo nghiên cứu tốt nhất lúc bắt đầu sự nghiệp” tại Hội nghị Crypto 2022.
Cuối tháng 3/2022, Edlyn Teske đã có bài viết "NIST PQC Finalists Update: It's Over For The Rainbow” [5], có thể dịch là: Cập nhật các thuật toán chung kết cuộc tuyển chọn mật mã hậu lượng tử của NIST: Raindow đã dừng lại.
Tháng 4/2022, Ward Beullens đã công bố mã nguồn của chương trình thám mã này trên Github [6].
Tháng 8/2022, Ward Beullens đã giới thiệu về công trình của mình trên trang web của IBM Reseach [7] như sau:
Chúng tôi đã tìm thấy một tấn công mới chống lại lược đồ chữ ký Rainbow. Tấn công của chúng tôi khai thác các điểm khác biệt để khôi phục khóa bí mật hiệu quả hơn. Ở cấp độ bảo mật thấp nhất, người ta tin rằng để phá vỡ Rainbow sẽ cần chạy một thuật toán thực hiện ít nhất 2128 phép toán. Ngay cả khi một tỷ máy tính đã hoạt động cùng nhau, mỗi máy tính thực hiện một tỷ phép tính mỗi giây kể từ khi vũ trụ bắt đầu hình thành cách đây 14 tỷ năm thì ngày hôm nay chúng vẫn chưa kết thúc cuộc tấn công.
Tấn công mới của chúng tôi hiệu quả hơn nhiều và chỉ chạy trong 53 giờ (một dịp nghỉ cuối tuần) trên một máy tính xách tay bình thường, điều này cho thấy Rainbow kém an toàn hơn nhiều so với dự đoán và không nên được NIST chuẩn hóa.
Ngoài việc công bố 4 thuật toán sẽ được chuẩn hóa (1 thuật toán mã hóa và 3 thuật toán chữ ký số), NIST còn chọn 4 thuật toán mã hóa nữa vào vòng tuyển chọn thứ 4. SIKE là một trong số 4 thuật toán đó. Tuy nhiên, ngày 30/7/2022, Wouter Castryck và Thomas Decru đã công bố một tấn công hiệu quả lên SIKE [8], nó cũng kéo theo một số công trình khác [9, 10]. Về kết quả này bạn đọc có thể tham khảo [11] để biết thêm chi tiết.
Bất kỳ thuật toán nào mà NIST sẽ chọn, chúng vẫn có thể bị phá vỡ trong tương lai. Như Cơ quan An ninh Hệ thống Thông tin Quốc gia của Pháp (ANSSI) đã cảnh báo: “Không nên đánh giá quá cao mức độ trưởng thành của các thuật toán hậu lượng tử được đệ trình cho việc tuyển chọn của NIST”.
|
TÀI LIỆU THAM KHẢO 1. PQC Standardization Process: Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates, . 2. Trần Duy Lai, //qvikly.com/mat-ma-dan-su/nist-cong-bo-4-thuat-toan-se-duoc-chuan-hoa-cua-mat-ma-hau-luong-tu-va-cac-ung-cu-vien-cho-vong-tuye-108288 . 3. Ward Beullens, Improved cryptanalysis of UOV and Rainbow, (26/10/2020). 4. Ward Beullens, Breaking Rainbow Takes a Weekend on a Laptop, (25/2/2022). 5. Edlyn Teske, NIST PQC Finalists Update: It's Over For The Rainbow, 24,March 2022. 6. (13/4/2022). 7. Ward Beullens, 13/8/2022. 8. Wouter Castryck and Thomas Decru, An efficient key recovery attack on SIDH, 9. Luciano Maino and Chloe Martindale, An attack on SIDH with arbitrary starting curve (draft), 10. Damien Robert, Breaking SIDH in polynomial time, . 11. Trần Duy Lai, //qvikly.com/mat-ma-dan-su/mat-ma-sike-duoc-gia-thiet-an-toan-luong-tu-vua-bi-pha-vo-boi-may-tinh-pc-108286 |
Trần Duy Lai
10:00 | 17/02/2023
12:00 | 12/08/2022
14:00 | 04/03/2022
09:00 | 17/07/2023
10:00 | 17/11/2020
14:00 | 05/07/2023
09:00 | 01/08/2023
15:00 | 28/06/2023
14:00 | 24/08/2023
Các chuyên gia nghiên cứu bảo mật thuộc Đại học Cornell (Vương quốc Anh) đã phát triển một hình thức lấy cắp mật khẩu đăng nhập tài khoản của người dùng theo cách ít ai ngờ đến.
15:00 | 14/12/2022
Kiểm thử xâm nhập còn được gọi là ethical hacking, là hành động xâm nhập hệ thống thông tin một cách hợp pháp. Kiểm thử xâm nhập giúp phát hiện ra các lỗ hổng và điểm yếu trong hệ thống phòng thủ bảo mật của tổ chức trước khi để kẻ xấu phát hiện ra. Đây là hành động hỗ trợ đắc lực cho tổ chức trong việc đưa ra các giải pháp để khắc phục các lỗ hổng bảo mật đã được phát hiện trước đó.
16:00 | 30/11/2022
Ngày 23/4/2021, trên trang web của Hiệp hội mật mã thế giới xuất hiện bài báo “On One-way Functions from NP-Complete Problems” của Yanyi Liu và Rafael Pass [1]. Liu và Pass đã chứng minh rằng sự tồn tại của tất cả các hệ mật khóa công khai phụ thuộc vào một trong những câu hỏi lâu đời nhất của lý thuyết độ phức tạp tính toán. Trong bài báo này, tác giả sẽ giới thiệu nội dung bài viết của Erica Klarreich [2] bình luận về kết quả trong nghiên cứu [1] của Liu và Pass.
15:00 | 24/02/2022
Zodiac-340 là một bản mã dựa trên các mã pháp cổ điển là thay thế và hoán vị, nhưng việc phá nó không hề dễ. Trong [1] cũng đã trích dẫn nhiều bài viết về lời giải của Zodiac-340. Trên trang web của Hiệp hội quốc tế về nghiên cứu mật mã, ngày 12/12/2021 đã xuất bản bài viết của Joachim von zur Gathen với nhan đề “Unicity distance of the Zodiac-340 cipher”. Bài viết này sẽ trình bày lại kết quả của nghiên cứu này.
08:00 | 11/01/2024 | Chính sách - Chiến lược
09:00 | 10/01/2024 | Giải pháp khác
09:00 | 05/01/2024|Chính sách - Chiến lược
09:00 | 05/01/2024|An ninh – Quốc Phòng
