Thuật toán chữ ký số 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 máy tính lượng tử, đ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ã khóa công khai 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”.
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
09:00 | 05/08/2024
Khung An ninh mạng của NIST (Cybersecurity Framework - CSF) được biết đến là một công cụ linh hoạt và toàn diện giúp các tổ chức nắm bắt, quản lý các mối đe dọa an ninh mạng một cách hiệu quả, từ việc xác định rủi ro, triển khai các biện pháp bảo vệ cho đến phản ứng khi xảy ra sự cố. CSF 2.0 được thiết kế phù hợp với nhiều mô hình, quy mô khác nhau của các tổ chức và những điều chỉnh, cập nhật bổ sung nhằm phản ánh sự phát triển nhanh chóng của công nghệ trí tuệ nhân tạo và blockchain. Bài báo sẽ thông tin tới độc giả Khung An ninh mạng phiên bản 2.0 của NIST và những cập nhật quan trọng trong phiên bản mới này.
15:00 | 03/09/2023
Ngày 21/8, Cơ quan An ninh Cơ sở hạ tầng và An ninh mạng (CISA ), Cơ quan An ninh Quốc gia (NSA) và Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (NIST) đã công bố thông cáo về tác động của năng lực lượng tử. Ba cơ quan này kêu gọi tất cả các tổ chức, đặc biệt là những tổ chức hỗ trợ cơ sở hạ tầng quan trọng cần sớm lập kế hoạch cho việc chuyển đổi sang các tiêu chuẩn mật mã hậu lượng tử (PQC) bằng cách phát triển lộ trình sẵn sàng lượng tử.
09:00 | 01/08/2023
Mọi người đều biết rằng nên chuẩn bị cho một “tương lai lượng tử”, nhưng nó được cho là sẽ xảy ra sau 10 - 20 năm nữa. Thế nhưng vào những ngày cuối cùng của năm 2022, cộng đồng công nghệ thông tin (CNTT) khá xôn xao trước một nghiên cứu do một nhóm các nhà khoa học Trung Quốc trình bày. Kết quả nghiên cứu này tuyên bố rằng trong tương lai gần nhất, có thể bẻ khóa thuật toán mã hóa RSA với độ dài khóa là 2048 bit, đây vốn là nền tảng cho hoạt động của các giao thức internet bằng cách kết hợp khéo léo tính toán cổ điển và tính toán lượng tử. Vậy thực hư mối đe dọa này như thế nào? Liệu có một sự đột phá trong năm nay?
14:00 | 12/07/2023
Ngày 20/7 tới đây, tại Thành phố Hồ Chí Minh, Cục Quản lý mật mã dân sự và Kiểm định sản phẩm mật mã, Ban Cơ yếu Chính phủ sẽ tổ chức Hội nghị tập huấn về mật mã dân sự năm 2023 và triển khai Nghị định số 32/2023/NĐ-CP ngày 09/6/2023 của Chính phủ.