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 | 08/03/2024
Chiều 07/3, tại Hà Nội, Ban Cơ yếu Chính phủ tổ chức Hội thảo xây dựng tiêu chuẩn Việt Nam (TCVN) cho thuật toán mã khối ViEncrypt trong lĩnh vực mật mã dân sự. Đồng chí Vũ Ngọc Thiềm, Trưởng ban Ban Cơ yếu Chính phủ chủ trì Hội thảo. Tham dự Hội thảo còn có đại diện lãnh đạo các hệ Cơ yếu, các cơ quan, đơn vị thuộc Ban Cơ yếu Chính phủ, các chuyên gia, nguyên cán bộ cấp cao của Viện Khoa học Công nghệ mật mã, Cục Chứng thực số và Bảo mật thông tin..., Ban Cơ yếu Chính phủ.
12:00 | 23/09/2022
Sự kiện Trường hè mật mã do Hiệp hội Quốc tế về Nghiên cứu mật mã (International Association for Cryptographic Research - IACR) phối hợp cùng Viện Nghiên cứu cao cấp về Toán (International Association for Cryptographic Research - VIASM) tổ chức thành công vào cuối tháng 8 vừa qua đã đem lại một môi trường học thuật đa dạng để khơi dậy việc đào tạo nguồn nhân lực chất lượng cao trong lĩnh vực mật mã. Từ đó góp phần xây dựng nền tảng kiến thức cho nhiều bạn trẻ đi theo các hướng nghiên cứu chủ chốt và hiện đại về mật mã của thế giới.
13:00 | 24/03/2022
Nhân dịp đầu Xuân Nhâm Dần, phóng viên Tạp chí An toàn thông tin đã có buổi phỏng vấn đồng chí Đại tá, TS. Hồ Văn Hương, Cục trưởng Cục Quản lý mật mã dân sự và Kiểm định sản phẩm mật mã (MMDS&KĐSPMM), Ban Cơ yếu Chính phủ nhằm hiểu rõ hơn thông tin, định hướng và triển khai công tác quản lý mật mã dân sự và kiểm định sản phẩm mật mã trong thời gian tới.
10:00 | 29/10/2021
Các hệ thống công nghiệp phụ thuộc vào công nghệ vận hành luôn coi trọng vấn đề về an toàn mạng. Tiêu chuẩn IEC 62443 được phát triển để bảo đảm an toàn cho các mạng truyền thông công nghiệp và các hệ thống điều khiển và tự động hóa công nghiệp (Industrial Automation and Control Systems - IACS) thông qua phương pháp tiếp cận có hệ thống.