Nếu các giao thức mật mã ngày nay không thành công, thì sẽ không thể đảm bảo an toàn cho các kết nối trực tuyến - để gửi tin nhắn bí mật, thực hiện các giao dịch tài chính an toàn hoặc xác thực dữ liệu. Bất kỳ ai cũng có thể truy cập bất cứ thứ gì; bất cứ ai có thể giả làm bất cứ ai. Nền kinh tế kỹ thuật số sẽ sụp đổ.
Khi nào (hoặc if) một máy tính lượng tử đầy đủ chức năng trở nên khả dụng, đó chính xác là điều có thể xảy ra. Do đó, vào năm 2017, Viện Tiêu chuẩn và Công nghệ Quốc gia (NIST) của chính phủ Hoa Kỳ đã phát động một cuộc thi quốc tế nhằm tìm ra những cách tốt nhất để đạt được mật mã “hậu lượng tử”.
Tháng trước, cơ quan này đã chọn ra nhóm người chiến thắng đầu tiên: bốn giao thức, với một số sửa đổi, sẽ được triển khai như một lá chắn lượng tử. Nó cũng thông báo bốn ứng cử viên bổ sung vẫn đang được xem xét.
Sau đó, vào ngày 30 tháng XNUMX, một cặp nhà nghiên cứu tiết lộ rằng họ đã đã phá vỡ một trong những ứng cử viên đó trong một giờ trên máy tính xách tay. (Kể từ đó, những người khác đã thực hiện cuộc tấn công nhanh hơn, phá vỡ giao thức chỉ trong vài phút.) “Một cuộc tấn công quá ấn tượng và mạnh mẽ… thực sự là một cú sốc,” nói Steven Galbraith, một nhà toán học và khoa học máy tính tại Đại học Auckland ở New Zealand. Không chỉ toán học làm nền tảng cho cuộc tấn công đáng ngạc nhiên, mà nó còn làm giảm tính đa dạng (rất cần thiết) của mật mã hậu lượng tử - loại bỏ một giao thức mã hóa hoạt động rất khác với phần lớn các kế hoạch trong cuộc thi NIST.
“Đó là một chút ngớ ngẩn,” nói Christopher Peikert, một nhà mật mã học tại Đại học Michigan.
Kết quả đã khiến cộng đồng tiền mã hóa hậu lượng tử bị chấn động và được khuyến khích. Rung động, bởi vì cuộc tấn công này (và một cuộc khác từ vòng trước của cuộc thi) đột nhiên biến thứ trông giống như một cánh cửa thép kỹ thuật số thành tờ báo ướt. “Nó đến từ màu xanh lam,” nói Dustin tâm trạng, một trong những nhà toán học dẫn đầu nỗ lực chuẩn hóa NIST. Nhưng nếu một kế hoạch mật mã sắp bị phá vỡ, tốt nhất là nếu nó xảy ra tốt trước khi nó được sử dụng trong tự nhiên. “Có rất nhiều cảm xúc đi qua bạn,” nói David Jao, một nhà toán học tại Đại học Waterloo ở Canada, cùng với nhà nghiên cứu của IBM Luca De Feo, đề xuất giao thức vào năm 2011. Chắc chắn sự ngạc nhiên và thất vọng nằm trong số đó. "Nhưng cũng có thể," Jao nói thêm, "ít nhất nó đã bị hỏng bây giờ."
Những cuộc đi bộ bí mật giữa những khúc cua
Jao và De Feo đã nhìn thấy cơ hội cho một hệ thống mật mã vừa giống và vừa khác biệt với các giao thức nổi tiếng. Đề án của họ, được gọi là giao thức đẳng cấp siêu đẳng Diffie-Hellman (SIDH), xử lý các đường cong elip - các đối tượng toán học tương tự được sử dụng trong một trong những loại mật mã phổ biến nhất được triển khai ngày nay. Nhưng nó đã sử dụng chúng theo một cách hoàn toàn khác. Đây cũng là kế hoạch nhỏ gọn nhất mà NIST đang xem xét (đánh đổi là nó chậm hơn so với nhiều ứng cử viên khác).
Và “về mặt toán học, nó thực sự rất thanh lịch,” Jao nói. "Vào thời điểm đó, nó có vẻ như là một ý tưởng tuyệt vời."
Giả sử hai bên, Alice và Bob, muốn trao đổi một tin nhắn trong bí mật, ngay cả dưới sự giám sát của kẻ tấn công tiềm năng. Chúng bắt đầu với một tập hợp các điểm được nối với nhau bằng các cạnh được gọi là đồ thị. Mỗi điểm biểu diễn một đường cong elliptic khác nhau. Nếu bạn có thể biến đổi một đường cong này thành một đường cong khác theo một cách cụ thể (thông qua một bản đồ được gọi là đường đẳng giác), hãy vẽ một cạnh giữa cặp điểm. Biểu đồ kết quả rất lớn và dễ bị lạc: Nếu bạn đi bộ tương đối ngắn dọc theo các cạnh của nó, bạn sẽ đến một nơi nào đó trông hoàn toàn ngẫu nhiên.
Đồ thị của Alice và của Bob có tất cả các điểm giống nhau, nhưng các cạnh khác nhau - chúng được xác định bởi các đồng đẳng khác nhau. Alice và Bob bắt đầu tại cùng một điểm, và mỗi người nhảy dọc theo các cạnh ngẫu nhiên trên biểu đồ của riêng mình, theo dõi đường đi của họ từ điểm này đến điểm khác. Sau đó, mỗi người công bố vị trí kết thúc của họ nhưng giữ bí mật về đường đi của họ.
Bây giờ họ đổi chỗ cho nhau: Alice đến điểm cuối cùng của Bob, và Bob đến điểm của Alice. Mỗi người lặp lại bước đi bí mật của họ. Họ làm điều này theo cách mà cả hai sẽ kết thúc ở cùng một điểm.
Vị trí này đã được tìm thấy trong bí mật, vì vậy Alice và Bob có thể sử dụng nó làm khóa bí mật của họ - thông tin cho phép họ mã hóa và giải mã tin nhắn của nhau một cách an toàn. Ngay cả khi kẻ tấn công nhìn thấy các điểm trung gian mà Alice và Bob gửi cho nhau, họ không biết bước đi bí mật của Alice hoặc Bob, vì vậy họ không thể tìm ra điểm cuối cuối cùng đó.
Nhưng để làm cho SIDH hoạt động, Alice và Bob cũng cần trao đổi thêm một số thông tin về các chuyến đi bộ của họ. Thông tin bổ sung đó là nguyên nhân dẫn đến sự sụp đổ của SIDH.
Một bước ngoặt mới về toán học cũ
Thomas Decru đã không đặt ra để phá vỡ SIDH. Anh ấy đang cố gắng xây dựng dựa trên nó - để tổng quát hóa phương pháp nhằm nâng cao một loại mật mã khác. Điều đó không thành công, nhưng nó đã làm nảy sinh một ý tưởng: Cách tiếp cận của anh ta có thể hữu ích để tấn công SIDH. Và vì vậy anh ấy đã tiếp cận Wouter Castryck, đồng nghiệp của ông tại Đại học Công giáo Leuven ở Bỉ và một trong những cố vấn tiến sĩ cũ của ông, và cả hai đã nghiên cứu sâu về tài liệu liên quan.
Họ tình cờ xem được một bài báo được xuất bản bởi nhà toán học Ernst Kani vào năm 1997. Trong đó có một định lý “gần như có thể áp dụng ngay cho SIDH,” Castryck nói. "Tôi nghĩ một khi chúng tôi nhận ra rằng ... cuộc tấn công đến khá nhanh, trong một hoặc hai ngày."
Cuối cùng, để khôi phục bước đi bí mật của Alice (và do đó là khóa chia sẻ), Castryck và Decru đã kiểm tra tích của hai đường cong elliptic - đường cong xuất phát của Alice và đường cong mà cô ấy đã gửi công khai cho Bob. Sự kết hợp đó tạo ra một loại bề mặt được gọi là bề mặt abel. Sau đó, họ sử dụng các bề mặt abelian này, định lý Kani (liên hệ bề mặt abel với đường cong elliptic) và thông tin bổ sung Alice cung cấp cho Bob để khám phá từng bước Alice thực hiện.
“Nó gần giống như một tín hiệu gọi xe cho phép bạn bám vào [một số bề mặt abelian nhất định],” Jao nói. “Và tín hiệu đó cho bạn biết rằng đây là cách bạn nên đi để thực hiện bước tiếp theo để tìm ra [bước đi bí mật] chính xác.” Điều này dẫn họ đến thẳng khóa chung của Alice và Bob.
“Đó là một cách tiếp cận rất bất ngờ, đi đến các đối tượng phức tạp hơn để thu được kết quả về đối tượng đơn giản hơn,” Jao nói.
“Tôi rất vui mừng khi thấy kỹ thuật này được sử dụng,” nói Kristin Lauter, một nhà toán học và mật mã học tại Meta AI Research, người không chỉ giúp phát triển mật mã dựa trên isogeny mà còn làm việc trên các bề mặt abelian. “Thật xấu hổ cho tôi vì đã không nghĩ về nó như một cách để phá vỡ [nó].”
Cuộc tấn công của Castryck và Decru đã phá vỡ phiên bản bảo mật thấp nhất của giao thức SIDH trong 62 phút và mức bảo mật cao nhất chỉ trong vòng chưa đầy một ngày. Sau đó, ngay sau đó, một chuyên gia khác đã điều chỉnh cuộc tấn công để chỉ mất 10 phút để phá vỡ phiên bản bảo mật thấp và vài giờ để phá vỡ phiên bản bảo mật cao. Các cuộc tấn công tổng quát hơn đã đăng trong vài tuần qua làm cho nó không chắc rằng SIDH có thể được trục vớt.
“Đó là một cảm giác đặc biệt,” Castryck nói, mặc dù có một chút buồn vui lẫn lộn. "Chúng tôi đã giết một trong những hệ thống yêu thích của mình."
Khoảnh khắc đầu nguồn
Không thể đảm bảo rằng một hệ thống an toàn vô điều kiện. Thay vào đó, các nhà mật mã học dựa vào đủ thời gian trôi qua và đủ số người cố gắng phá vỡ vấn đề để cảm thấy tự tin. “Điều đó không có nghĩa là ngày mai bạn sẽ không thức dậy và thấy rằng ai đó đã tìm ra một thuật toán mới để làm điều đó,” nói Jeffrey Hoffstein, một nhà toán học tại Đại học Brown.
Vì vậy, tại sao các cuộc thi như NIST lại quan trọng đến vậy. Trong vòng trước của cuộc thi NIST, Ward Beullens, một nhà mật mã học tại IBM, đã nghĩ ra một cuộc tấn công phá vỡ một kế hoạch được gọi là Cầu vồng trong một ngày cuối tuần. Giống như Castryck và Decru, anh ta chỉ có thể thực hiện cuộc tấn công của mình sau khi anh ta nhìn vấn đề toán học cơ bản từ một góc độ khác. Và giống như cuộc tấn công vào SIDH, cuộc tấn công này đã phá vỡ một hệ thống dựa trên toán học khác với hầu hết các giao thức hậu lượng tử được đề xuất.
“Các cuộc tấn công gần đây là một thời điểm đầu nguồn,” nói Thomas Perst, một nhà mật mã học tại công ty khởi nghiệp PQShield. Họ nhấn mạnh mức độ khó của mật mã hậu lượng tử và mức độ phân tích có thể cần thiết để nghiên cứu tính bảo mật của các hệ thống khác nhau. Ông nói: “Một đối tượng toán học có thể không có cấu trúc rõ ràng trong một góc nhìn và có một cấu trúc có thể khai thác ở một góc độ khác. “Phần khó là xác định được quan điểm mới phù hợp.”
