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
13:00 | 23/10/2024
Báo cáo Ransomware Zscaler ThreatLabz 2024 mới đây đã vạch trần nhóm tin tặc Dark Angels với khoản thanh toán tiền chuộc lớn nhất được biết đến trong lịch sử là 75 triệu USD vào đầu năm nay. Bài viết sẽ cùng giải mã, phân tích chi tiết hơn các chiến thuật, kỹ thuật và quy trình của nhóm tin tặc này, dựa trên báo cáo của hãng bảo mật Zscaler (Mỹ).
08:00 | 23/09/2024
Ngày 19/9, cơ quan cảnh sát quốc gia Hàn Quốc cho biết sẽ đầu tư 9,1 tỷ won (6,8 triệu USD) trong 3 năm tới để phát triển công nghệ phát hiện các loại hình tội phạm Deepfake, sao chép giọng nói và các nội dung bịa đặt khác.
14:00 | 26/02/2024
Khi dữ liệu được gửi từ nơi này đến nơi khác thì cần phải bảo vệ dữ liệu trong quá trình đang được gửi. Tương tự như vậy, khi dữ liệu được lưu trữ trong một môi trường mà các bên không được phép cập thì cần thiết phải có các biện pháp bảo vệ dữ liệu đó. Bài báo sẽ giới thiệu tóm tắt nội dung tiêu chuẩn ISO/IEC 19772:2020 về an toàn thông tin – mã hóa có sử dụng xác thực. Xác định các cách thức xử lý một chuỗi dữ liệu theo các mục tiêu an toàn bao gồm 5 cơ chế mã hóa có sử dụng xác thực.
15:00 | 24/10/2023
Mục tiêu chính của các kỹ thuật mã hóa là bảo vệ tính bí mật của dữ liệu được lưu trữ hoặc truyền đi. Thuật toán mã hóa được áp dụng vào dữ liệu (bản rõ), từ đó nhận được dữ liệu được mã hóa (bản mã), quá trình này được gọi là mã hóa. Thuật toán mã hóa cần được thiết kế sao cho bản mã không cung cấp thông tin về bản rõ. Gắn liền với thuật toán mã hóa là thuật toán giải mã, biến đổi ngược bản mã thành bản rõ gốc. Bài viết sẽ giới thiệu tóm tắt nội dung tiêu chuẩn TCVN 11367-1:2016. Nội dung của tiêu chuẩn này xác định các hệ mật nhằm mục đích bảo mật dữ liệu. Việc đưa các hệ mật vào tiêu chuẩn này nhằm đẩy mạnh việc sử dụng chúng với chất lượng tốt nhất hiện nay trong các kỹ thuật mật mã.