QUÁ TRÌNH CHUẨN HÓA MẬT MÃ HẬU LƯỢNG TỬ CỦA NIST

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

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.

PHÂN TÍCH MẬT MÃ

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.

VỀ CÁC THUẬT TOÁN MẬT MÃ HẬU LƯỢNG TỬ KHÁC

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”.