Tại sao cuộc 'đại tu' hậu lượng tử của Signal là một thành tựu kỹ thuật tuyệt vời

Mã hóa bảo vệ thông tin liên lạc chống lại tội phạm và rình mò quốc gia đang bị đe dọa. Khi ngành công nghiệp tư nhân và chính phủ tiến gần hơn đến việc xây dựng các máy tính lượng tử hữu ích, các thuật toán bảo vệ ví Bitcoin, truy cập web được mã hóa và các bí mật nhạy cảm khác sẽ vô dụng. Không ai nghi ngờ ngày đó sẽ đến, nhưng như trò đùa phổ biến hiện nay trong giới mật mã nhận xét, các chuyên gia đã dự báo ngày tận thế mật mã này sẽ đến trong 15 đến 30 năm tới trong 30 năm qua.

Sự không chắc chắn đã tạo ra một vấn đề nan giải hiện sinh: Các kiến trúc sư mạng có nên chi hàng tỷ đô la cần thiết để loại bỏ các thuật toán dễ bị tổn thương lượng tử ngay bây giờ hay họ nên ưu tiên ngân sách bảo mật hạn chế của mình để chống lại các mối đe dọa tức thời hơn như ransomware và các cuộc tấn công gián điệp? Với chi phí và không có thời hạn rõ ràng, nó có chút tự hỏi rằng ít hơn một nửa trong số tất cả các kết nối TLS được thực hiện bên trong mạng Cloudflare và chỉ 18 phần trăm mạng của Fortune 500 hỗ trợ kết nối TLS kháng lượng tử. Tất cả, nhưng chắc chắn rằng nhiều tổ chức ít hơn vẫn đang hỗ trợ mã hóa sẵn sàng lượng tử trong các giao thức ít nổi bật hơn.

Chiến thắng của cypherpunks

Một ngoại lệ đối với sự thờ ơ trong toàn ngành là nhóm kỹ thuật thiết kế Giao thức tín hiệu, công cụ nguồn mở cung cấp năng lượng cho hình thức mã hóa đầu cuối mạnh mẽ và linh hoạt nhất thế giới cho nhiều ứng dụng trò chuyện riêng tư, đáng chú ý nhất là Sứ giả tín hiệu. Mười một ngày trước, tổ chức phi lợi nhuận phát triển giao thức, Signal Messenger LLC, đã xuất bản một bài viết dài 5.900 từ mô tả các bản cập nhật mới nhất của nó mang lại cho Signal một bước quan trọng hướng tới khả năng kháng lượng tử hoàn toàn.

Sự phức tạp và khả năng giải quyết vấn đề cần thiết để làm cho lượng tử Giao thức Tín hiệu trở nên an toàn cũng khó khăn như bất kỳ vấn đề nào trong kỹ thuật hiện đại. Giao thức Tín hiệu ban đầu đã giống với bên trong một chiếc đồng hồ Thụy Sĩ tinh xảo, với vô số bánh răng, bánh xe, lò xo, tay và các bộ phận khác đều tương tác với nhau một cách phức tạp. Trong những bàn tay kém lão luyện hơn, việc sử dụng một thiết bị phức tạp như giao thức Tín hiệu có thể dẫn đến các phím tắt hoặc hậu quả không lường trước được làm ảnh hưởng đến hiệu suất, làm mất đi những gì lẽ ra là một chiếc đồng hồ đang chạy hoàn hảo. Tuy nhiên, bản nâng cấp hậu lượng tử mới nhất này (bản đầu tiên đến vào năm 2023) không khác gì một chiến thắng.

“Đây dường như là một cải tiến vững chắc, chu đáo đối với Giao thức tín hiệu hiện có, ” Brian LaMacchia, một kỹ sư mật mã, người giám sát quá trình chuyển đổi hậu lượng tử của Microsoft từ năm 2015 đến năm 2022 và hiện đang làm việc tại Tập đoàn tư vấn Farcaster cho biết. “Là một phần của công việc này, Signal đã thực hiện một số tối ưu hóa thú vị dưới mui xe để giảm thiểu tác động đến hiệu suất mạng khi thêm tính năng hậu lượng tử.”

Trong số nhiều rào cản cần vượt qua, thách thức lớn nhất là tính đến kích thước khóa lớn hơn nhiều mà các thuật toán kháng lượng tử yêu cầu. Việc đại tu ở đây bổ sung thêm các biện pháp bảo vệ dựa trên ML-KEM-768, một triển khai thuật toán CRYSTALS-Kyber được chọn vào năm 2022 và chính thức năm ngoái bởi Viện Tiêu chuẩn và Công nghệ Quốc gia. ML-KEM là viết tắt của Module-Lattice-Based Key-Encapsulation Mechanism, nhưng hầu hết thời gian, các nhà mật mã học gọi nó đơn giản là KEM.

Ratchets, bóng bàn và không đồng bộ

Giống như giao thức Elliptic curve Diffie-Hellman (ECDH) mà Signal đã sử dụng kể từ khi bắt đầu, KEM là một cơ chế đóng gói chính. Còn được gọi là cơ chế thỏa thuận quan trọng, nó cung cấp phương tiện để hai bên chưa từng gặp nhau thỏa thuận một cách an toàn về một hoặc nhiều bí mật được chia sẻ trước sự chứng kiến của đối thủ đang theo dõi mối liên hệ giữa các bên. RSA, ECDH và các thuật toán đóng gói khác từ lâu đã được sử dụng để đàm phán các khóa đối xứng (hầu như luôn là khóa AES) trong các giao thức bao gồm TLS, SSH và IKE. Tuy nhiên, không giống như ECDH và RSA, KEM mới hơn nhiều là an toàn lượng tử.

Thỏa thuận chính trong một giao thức như TLS tương đối đơn giản. Đó là bởi vì các thiết bị kết nối qua TLS đàm phán một chìa khóa qua một cái bắt tay duy nhất xảy ra vào đầu phiên. Khóa AES đã được thống nhất sau đó sẽ được sử dụng trong suốt phiên. Signal Protocol thì khác. Không giống như các phiên TLS, các phiên Signal được bảo vệ bởi chuyển tiếp bí mật, một thuộc tính mật mã đảm bảo sự thỏa hiệp của một khóa được sử dụng để mã hóa một tập hợp tin nhắn gần đây không thể được sử dụng để giải mã một tập hợp tin nhắn trước đó. Giao thức này cũng cung cấp Bảo mật sau thỏa hiệp, giúp bảo vệ các tin nhắn trong tương lai khỏi các thỏa hiệp chính trong quá khứ. Trong khi TLS sử dụng cùng một khóa trong suốt phiên, các khóa trong phiên Tín hiệu sẽ liên tục phát triển.

Để cung cấp các đảm bảo bảo mật này, Giao thức Tín hiệu cập nhật tài liệu khóa bí mật mỗi khi một bên tin nhắn nhấn nút gửi hoặc nhận tin nhắn và tại các điểm khác, chẳng hạn như trong các chỉ báo đồ họa mà một bên hiện đang nhập và trong việc gửi biên lai đã đọc. Cơ chế giúp cho sự phát triển quan trọng liên tục này có thể thực hiện được trong thập kỷ qua là cái mà các nhà phát triển giao thức gọi là “bánh cóc đôi.” Giống như bánh cóc truyền thống cho phép bánh răng quay theo một hướng nhưng không quay theo hướng khác, bánh cóc Tín hiệu cho phép các bên nhắn tin tạo các phím mới dựa trên sự kết hợp giữa bí mật trước đó và bí mật mới được thống nhất. Bánh cóc hoạt động theo một hướng duy nhất, gửi và nhận các tin nhắn trong tương lai. Ngay cả khi kẻ thù xâm phạm một bí mật mới được tạo ra, các tin nhắn được mã hóa bằng các bí mật cũ hơn cũng không thể được giải mã.

Điểm khởi đầu là một cái bắt tay thực hiện ba hoặc bốn thỏa thuận ECDH kết hợp các bí mật dài hạn và ngắn hạn để thiết lập một bí mật chung. Việc tạo ra “root key” này cho phép Double Ratchet bắt đầu. Cho đến năm 2023, thỏa thuận quan trọng đã sử dụng X3DH. Cái bắt tay hiện sử dụng PQXDH để làm cho cái bắt tay có khả năng kháng lượng tử.

Lớp đầu tiên của Double Ratchet, Symmetric Ratchet, lấy khóa AES từ khóa gốc và nâng cao nó cho mọi tin nhắn được gửi. Điều này cho phép mọi tin nhắn được mã hóa bằng một khóa bí mật mới. Do đó, nếu những kẻ tấn công xâm phạm thiết bị của một bên, họ sẽ không thể tìm hiểu bất cứ điều gì về các khóa đến trước đó. Tuy nhiên, ngay cả khi đó, những kẻ tấn công vẫn có thể tính toán các khóa được sử dụng trong các tin nhắn trong tương lai. Đó là nơi “Ratchet” Diffie-Hellman thứ hai xuất hiện.

Bánh cóc Diffie-Hellman kết hợp khóa chung ECDH mới vào mỗi tin nhắn được gửi. Sử dụng Alice và Bob, những nhân vật hư cấu thường được nhắc đến khi giải thích về mã hóa bất đối xứng, khi Alice gửi cho Bob một tin nhắn, cô ấy sẽ tạo một cặp khóa bánh cóc mới và tính toán thỏa thuận ECDH giữa khóa này và khóa chung bánh cóc cuối cùng mà Bob gửi. Điều này mang lại cho cô một bí mật mới và cô biết rằng một khi Bob nhận được khóa công khai mới của cô, anh ấy cũng sẽ biết bí mật này (bởi vì, như đã đề cập trước đó, Bob trước đó đã gửi khóa khác đó). Với điều đó, Alice có thể trộn bí mật mới với khóa gốc cũ của mình để có được khóa gốc mới và bắt đầu mới. Kết quả: Những kẻ tấn công tìm hiểu bí mật cũ của cô ấy sẽ không thể phân biệt được sự khác biệt giữa các phím ratchet mới của cô ấy và tiếng ồn ngẫu nhiên.

Kết quả là những gì các nhà phát triển Signal mô tả là hành vi “ping-pong”, khi các bên tham gia thảo luận thay phiên nhau thay thế từng cặp phím bánh cóc. Hiệu ứng: Kẻ nghe trộm xâm phạm một trong các bên có thể khôi phục khóa riêng bánh cóc hiện tại, nhưng chẳng bao lâu nữa, khóa riêng đó sẽ được thay thế bằng khóa mới, không bị xâm phạm và theo cách giúp nó không bị lọt vào mắt xanh tò mò của kẻ tấn công.

Mục tiêu của các khóa mới được tạo là giới hạn số lượng tin nhắn có thể được giải mã nếu kẻ thù khôi phục tài liệu chính tại một thời điểm nào đó trong cuộc trò chuyện đang diễn ra. Tin nhắn được gửi trước và sau khi thỏa hiệp sẽ vẫn nằm ngoài giới hạn.

Một thách thức lớn mà các nhà thiết kế Giao thức Tín hiệu phải đối mặt là nhu cầu làm cho bánh cóc hoạt động trong môi trường không đồng bộ. Tin nhắn không đồng bộ xảy ra khi các bên gửi hoặc nhận chúng vào các thời điểm khác nhau—, chẳng hạn như khi một bên ngoại tuyến và bên kia đang hoạt động hoặc ngược lại—mà không cần phải có mặt hoặc phản hồi ngay lập tức. Toàn bộ Giao thức Tín hiệu phải hoạt động trong môi trường không đồng bộ này. Hơn nữa, nó phải hoạt động đáng tin cậy trên các mạng không ổn định và các mạng do đối thủ kiểm soát, chẳng hạn như chính phủ buộc dịch vụ viễn thông hoặc đám mây phải theo dõi lưu lượng truy cập.

Thuật toán của Shor ẩn nấp

Theo tất cả các tài khoản, thiết kế bánh cóc đôi của Signal là nhà nước của nghệ thuật. Điều đó nói rằng, nó mở rộng cho một mối đe dọa không thể tránh khỏi nếu không muốn nói là ngay lập tức: điện toán lượng t. Điều đó là do đối thủ có khả năng giám sát lưu lượng truy cập đi qua từ hai hoặc nhiều người dùng trình nhắn tin có thể thu thập dữ liệu đó và đưa nó vào máy tính lượng tử. Một khi một trong những nguồn năng lượng đủ khả thi— và tính toán các khóa phù du được tạo trong bánh cóc thứ hai.

Trong điện toán cổ điển, nó không khả thi, nếu không nói là không thể, đối với một đối thủ như vậy để tính toán khóa. Giống như tất cả các thuật toán mã hóa bất đối xứng, ECDH dựa trên hàm toán học một chiều. Còn được gọi là hàm cửa sập, những vấn đề này rất nhỏ khi tính toán theo một hướng và khó tính toán ngược lại hơn đáng kể. Trong mật mã đường cong elip, hàm một chiều này dựa trên bài toán Logarit rời rạc trong toán học. Các tham số chính dựa trên các điểm cụ thể trong đường cong elip trên trường số nguyên modulo một số nguyên tố P.

Trung bình, một đối thủ chỉ được trang bị một máy tính cổ điển sẽ dành hàng tỷ năm để đoán các số nguyên trước khi đến đúng số nguyên. Ngược lại, một máy tính lượng tử sẽ có thể tính toán các số nguyên chính xác chỉ trong vài giờ hoặc vài ngày. Một công thức được gọi là thuật toán Shor's— chỉ chạy trên máy tính lượng tử— đảo ngược phương trình logarit rời rạc một chiều này thành phương trình hai chiều. Tương tự, thuật toán Shor có thể thực hiện công việc nhanh chóng để giải hàm một chiều mà Lừa làm cơ sở cho thuật toán RSA.

Như đã lưu ý trước đó, Giao thức Tín hiệu đã nhận được giao thức đầu tiên thay đổi sau lượng tử vào năm 2023. Bản cập nhật này đã thêm PQXDH—triển khai dành riêng cho Tín hiệu kết hợp các thỏa thuận chính từ các đường cong elip được sử dụng trong X3DH (cụ thể là X25519) và KEM— an toàn lượng tử trong giao thức bắt tay ban đầu. (X3DH sau đó đã được đưa ra đồng cỏ như một thực hiện độc lập.)

Động thái này đã loại bỏ khả năng một cuộc tấn công lượng tử có thể khôi phục phím đối xứng được sử dụng để khởi động bánh cóc, nhưng các phím phù du được thiết lập trong bánh cóc thứ hai chơi bóng bàn vẫn dễ bị tấn công lượng tử. Bản cập nhật mới nhất của Signal bổ sung khả năng chống lượng tử cho các khóa này, đảm bảo rằng bí mật chuyển tiếp và bảo mật sau thỏa hiệp cũng an toàn khỏi thuật toán của Shor.

Mặc dù các phím bóng bàn dễ bị tấn công lượng tử trong tương lai, nhưng chúng được cho là an toàn trước các cuộc tấn công ngày nay từ máy tính cổ điển. Các nhà phát triển Giao thức Tín hiệu đã không muốn loại bỏ chúng hoặc mã đã được thử nghiệm trong trận chiến tạo ra chúng. Điều đó dẫn đến quyết định của họ để thêm sức đề kháng lượng tử bằng cách thêm một bánh cóc thứ ba. Loại này sử dụng KEM an toàn lượng tử để tạo ra những bí mật mới giống như bánh cóc Diffie-Hellman đã làm trước đây, đảm bảo an ninh an toàn lượng tử sau thỏa hiệp.

Những thách thức kỹ thuật không hề dễ dàng. Các khóa đường cong elip được tạo trong quá trình triển khai X25519 dài khoảng 32 byte, đủ nhỏ để thêm vào mỗi tin nhắn mà không tạo gánh nặng cho băng thông hoặc tài nguyên máy tính vốn đã bị hạn chế. Ngược lại, khóa ML-KEM 768 là 1.000 byte. Ngoài ra, thiết kế của Signal yêu cầu gửi cả khóa mã hóa và văn bản mã hóa, làm cho tổng kích thước là 2.272 byte.

Và sau đó có ba

Để xử lý mức tăng 71x, các nhà phát triển Signal đã xem xét nhiều lựa chọn khác nhau. Một là gửi khóa KEM 2.272 byte ít thường xuyên hơn—say mỗi tin nhắn thứ 50 hoặc mỗi tuần một lần—chứ không phải mỗi tin nhắn. Ý tưởng đó đã bị hủy bỏ vì nó không hoạt động tốt trong môi trường nhắn tin không đồng bộ hoặc đối nghịch. Các nhà phát triển Giao thức Tín hiệu Graeme Connell và Rolfe Schmidt giải thích:

Hãy xem xét trường hợp “gửi khóa nếu bạn chưa gửi khóa trong một tuần”. Nếu Bob đã offline được 2 tuần, Alice sẽ làm gì khi muốn gửi tin nhắn? Điều gì xảy ra nếu chúng ta có thể mất tin nhắn và mất một trong năm mươi tin nhắn có chứa khóa mới? Hoặc, điều gì sẽ xảy ra nếu có một kẻ tấn công ở giữa muốn ngăn chúng ta tạo ra những bí mật mới và có thể tìm kiếm các tin nhắn lớn hơn [nhiều] byte so với những tin nhắn khác và thả chúng, chỉ cho phép các tin nhắn không cần chìa khóa đi qua?

Một lựa chọn khác mà các kỹ sư Tín hiệu cân nhắc là chia khóa 2.272 byte thành các phần nhỏ hơn, chẳng hạn như 71 trong số đó, mỗi phần có 32 byte. Việc chia khóa KEM thành các phần nhỏ hơn và đặt một khóa vào mỗi tin nhắn ban đầu nghe có vẻ là một cách tiếp cận khả thi, nhưng một lần nữa, môi trường nhắn tin không đồng bộ khiến nó không thể hoạt động được. Điều gì xảy ra, ví dụ, khi mất dữ liệu gây ra một trong những khối bị loại bỏ? Giao thức có thể giải quyết tình huống này bằng cách chỉ gửi lại các đoạn sau khi gửi tất cả 71 đoạn trước đó. Nhưng sau đó, kẻ thù giám sát lưu lượng truy cập có thể chỉ khiến gói 3 bị loại bỏ mỗi lần, ngăn cản Alice và Bob hoàn thành việc trao đổi khóa.

Các nhà phát triển tín hiệu cuối cùng đã đi với một giải pháp sử dụng phương pháp tiếp cận nhiều khối này.

Lén lút một con voi qua cửa mèo

Để quản lý các thách thức không đồng bộ, các nhà phát triển đã chuyển sang “mã xóa,” một phương pháp chia dữ liệu lớn hơn thành các phần nhỏ hơn để bản gốc có thể được xây dựng lại bằng cách sử dụng bất kỳ tập hợp con khối có kích thước đủ nào.

Charlie Jacomme, nhà nghiên cứu tại INRIA Nancy thuộc nhóm Pesto, người tập trung vào xác minh chính thức và nhắn tin an toàn, cho biết thiết kế này giải thích cho việc mất gói bằng cách xây dựng phần dư thừa vào vật liệu được phân đoạn. Thay vì tất cả x số khối phải được nhận thành công để xây dựng lại khóa, mô hình chỉ yêu cầu xy khối được nhận, trong đó y là số lượng gói tin bị mất có thể chấp nhận được. Miễn là ngưỡng đó được đáp ứng, khóa mới có thể được thiết lập ngay cả khi xảy ra mất gói.

Phần còn lại của thiết kế là chia các tính toán KEM thành các bước nhỏ hơn. Những tính toán KEM này khác với tài liệu chính KEM.

Như Jacomme đã giải thích:

Về cơ bản, một phần nhỏ của khóa chung là đủ để bắt đầu tính toán và gửi phần lớn hơn của bản mã, do đó bạn có thể nhanh chóng gửi song song phần còn lại của khóa chung và phần đầu của bản mã. Về cơ bản, các tính toán cuối cùng đều bằng tiêu chuẩn, nhưng một số nội dung đã được song song hóa.

Trên thực tế, tất cả những điều này đóng một vai trò trong việc đảm bảo bảo mật cuối cùng, bởi vì bằng cách tối ưu hóa thực tế là việc tính toán KEM được thực hiện nhanh hơn, bạn sẽ giới thiệu trong nguồn gốc chính của mình những bí mật mới thường xuyên hơn.

Bài đăng của Signal 10 ngày trước bao gồm một số hình ảnh minh họa cho thiết kế này:

Mặc dù thiết kế đã giải quyết được vấn đề nhắn tin không đồng bộ, nhưng nó đã tạo ra một sự phức tạp mới của riêng nó: Bánh cóc an toàn lượng tử mới này tiến bộ nhanh đến mức nó không thể được giữ đồng bộ với bánh cóc Diffie-Hellman. Cuối cùng, các kiến trúc sư đã giải quyết một giải pháp sáng tạo. Thay vì bắt vít KEM vào bánh cóc đôi hiện có, họ cho phép nó ít nhiều giữ nguyên như trước đây. Sau đó, họ sử dụng bánh cóc an toàn lượng tử mới để triển khai hệ thống nhắn tin an toàn song song.

Bây giờ, khi giao thức mã hóa một tin nhắn, nó sẽ lấy các khóa mã hóa từ cả Double Ratchet cổ điển và ratchet mới. Sau đó, nó trộn hai khóa với nhau (sử dụng hàm dẫn xuất khóa mật mã) để có được khóa mã hóa mới có tất cả tính bảo mật của Double Ratchet cổ điển nhưng hiện cũng có bảo mật lượng tử.

Các kỹ sư Tín hiệu đã đặt cho bánh cóc thứ ba này cái tên chính thức: Bánh cóc lượng tử hậu thưa thớt, hay gọi tắt là SPQR. Bánh cóc thứ ba được thiết kế với sự cộng tác của PQShield, AIST, và Đại học New York. Các developer trình bày phân đoạn dựa trên mã xóa và thiết kế Triple Ratchet cấp cao tại hội nghị Eurocrypt 2025. Tại hội nghị Usenix 25, họ thảo luận sáu lựa chọn mà họ đã xem xét để bổ sung bí mật chuyển tiếp an toàn lượng tử và bảo mật sau thỏa hiệp cũng như lý do tại sao SPQR và một lựa chọn khác lại nổi bật. Các bài thuyết trình tại Hội nghị Tiêu chuẩn hóa NIST PQC và các Hội thảo ứng dụng mật mã giải thích chi tiết về phân đoạn, những thách thức trong thiết kế và cách điều chỉnh giao thức để sử dụng ML-KEM được tiêu chuẩn hóa.

Jacomme còn quan sát thêm:

Điều thú vị cuối cùng đối với bánh cóc ba bánh là nó kết hợp độc đáo những gì tốt nhất của cả hai thế giới. Giữa hai người dùng, bạn có một bánh cóc dựa trên DH cổ điển ở một bên và hoàn toàn độc lập, một bánh cóc dựa trên KEM đang diễn ra. Sau đó, bất cứ khi nào bạn cần mã hóa thứ gì đó, bạn sẽ nhận được khóa từ cả hai và trộn nó lại để lấy khóa mã hóa thực tế. Vì vậy, ngay cả khi một bánh cóc bị hỏng hoàn toàn, có thể là do hiện nay đã có một máy tính lượng tử, hoặc do ai đó cố gắng phá vỡ các đường cong elip hoặc ML-KEM, hoặc do việc triển khai một bánh cóc có sai sót, hoặc..., Thông báo Tín hiệu sẽ vẫn được bảo vệ bởi bánh cóc thứ hai. Theo một nghĩa nào đó, bản cập nhật này có thể được coi là, tất nhiên là đơn giản hóa, như tăng gấp đôi tính bảo mật của phần bánh cóc của Signal và là một điều thú vị ngay cả đối với những người không quan tâm đến máy tính lượng tử.

Như cả Signal và Jacomme đều lưu ý, người dùng Signal và các trình nhắn tin khác dựa vào Giao thức Tín hiệu không cần phải quan tâm đến bất kỳ thiết kế mới nào trong số này. Để diễn giải một nhà sản xuất thiết bị nhất định, nó chỉ hoạt động.