Thuật toán PQXDH thiết lập mã khóa chung

PQXDH là giao thức trao đổi khóa hậu lượng tử kế thừa kiến trúc X3DH, được thiết kế để bảo vệ tính bí mật thông tin liên lạc ngay cả trước các đối thủ sở hữu máy tính lượng tử trong tương lai.

Giới thiệu

Bài viết này mô tả giao thức thỏa thuận khóa PQXDH (Post-Quantum Extended Diffie–Hellman – Trao đổi Diffie–Hellman mở rộng hậu lượng tử). PQXDH thiết lập một khóa bí mật chung giữa hai thiết bị, những người xác thực lẫn nhau dựa trên khóa công khai. PQXDH cung cấp tính bảo mật chuyển tiếp hậu lượng tử và một dạng khả năng từ chối mật mã, nhưng vẫn dựa vào độ khó của bài toán logarit rời rạc để xác thực lẫn nhau trong phiên bản giao thức hiện tại.

PQXDH là phiên bản mở rộng của X3DH, được Signal phát triển để đối phó với mối đe dọa từ điện toán lượng tử – cụ thể là chiến lược thu thập ngay bây giờ, giải mã sau (harvest now, decrypt later): kẻ tấn công ghi lại lưu lượng mã hóa hiện tại và chờ đến khi có đủ sức mạnh lượng tử để phá vỡ mã hóa đường cong elliptic. X3DH thuần túy dễ bị tổn thương trước chiến lược này vì toàn bộ bảo mật của nó phụ thuộc vào bài toán logarit rời rạc – bài toán mà thuật toán Shor của máy tính lượng tử có thể giải trong thời gian đa thức. PQXDH bổ sung một cơ chế đóng gói khóa hậu lượng tử (post-quantum KEM) như CRYSTALS-Kyber-1024 vào quá trình tính toán khóa phiên SK, đảm bảo rằng ngay cả khi toàn bộ thành phần Diffie–Hellman bị phá vỡ bởi máy tính lượng tử, kẻ tấn công vẫn cần phá vỡ thêm bài toán Module Learning With Errors (Module-LWE) để tính SK – một bài toán mà chưa có thuật toán lượng tử hiệu quả nào được biết đến.

PQXDH được thiết kế cho môi trường không đồng bộ, trong đó Đan Nguyên có thể ngoại tuyến nhưng đã công bố trước thông tin cần thiết lên máy chủ. Mỹ Anh sử dụng thông tin đó để gửi dữ liệu mã hóa và thiết lập khóa bí mật chung cho các lần liên lạc trong tương lai. Giao thức kế thừa toàn bộ cấu trúc ba giai đoạn của X3DH – công bố khóa, gửi tin nhắn ban đầu, nhận tin nhắn ban đầu – đồng thời bổ sung thêm hai lớp khóa hậu lượng tử song hành với các khóa đường cong elliptic truyền thống. Sự kết hợp này đảm bảo rằng PQXDH duy trì toàn bộ tính chất bảo mật của X3DH trước các đối thủ cổ điển, đồng thời cung cấp bảo vệ bổ sung trước đối thủ lượng tử thụ động.

Kiến thức cơ bản

Phần này trình bày nền tảng kỹ thuật của PQXDH: các tham số cấu hình, hệ thống ký hiệu mật mã, mô hình vai trò, hệ thống khóa đường cong elliptic và hệ thống khóa hậu lượng tử. Hiểu đầy đủ năm thành phần này là điều kiện để theo dõi chính xác đặc tả giao thức trong các phần tiếp theo.

Tham số PQXDH

PQXDH yêu cầu ứng dụng thống nhất trước một bộ tham số cấu hình. Khác với X3DH chỉ cần ba tham số (curve, hash, info), PQXDH bổ sung thêm pqkem và aead để xử lý thành phần hậu lượng tử, cùng với bốn hàm mã hóa/giải mã cho khóa đường cong và khóa KEM.

Ví dụ, một ứng dụng có thể chọn curve là curve25519, hash là SHA512, info là MyProtocol và pqkem là CRYSTALS-Kyber-1024.

Tham số pqkem là điểm khác biệt quan trọng nhất so với X3DH. CRYSTALS-Kyber-1024, được NIST tiêu chuẩn hóa chính thức vào năm 2024, cung cấp khoảng 256 bit bảo mật cổ điển tương đương và khoảng 180 bit bảo mật hậu lượng tử theo tiêu chí NIST Level 5 – mức cao nhất trong bảng phân loại của NIST. Tham số aead cũng phải có tính bảo mật hậu lượng tử: AES-256-GCM là lựa chọn phổ biến vì thuật toán Grover chỉ giảm mức bảo mật của AES-256 từ 256 bit xuống còn 128 bit lượng tử – vẫn đủ an toàn theo tiêu chuẩn NIST. Phạm vi của tất cả các hàm mã hóa phải không trùng nhau để đảm bảo phân tách miền.

Các hàm EncodeEC và DecodeEC xử lý tuần hoàn hóa khóa đường cong. Cách triển khai được khuyến nghị: EncodeEC gồm một byte hằng số đại diện cho đường cong, tiếp theo là mã hóa little-endian của tọa độ u; DecodeEC đọc byte đầu tiên để xác định đường cong và thất bại nếu không nhận dạng được. Tương tự, EncodeKEM gồm một byte hằng số đại diện cho pqkem, tiếp theo là mã hóa khóa công khai pqkem theo định dạng chuẩn của pqkem đó; DecodeKEM đọc byte đầu tiên để xác định cơ chế KEM và thất bại nếu không nhận dạng được. Việc bao gồm byte định danh loại trong cả EncodeEC lẫn EncodeKEM là biện pháp phòng thủ chủ động: nó đảm bảo không bao giờ có sự nhầm lẫn giữa khóa đường cong và khóa KEM, dù cả hai đều được biểu diễn dưới dạng chuỗi byte.

Ký hiệu mật mã

Trong toàn bộ bài viết này, tất cả khóa công khai đều có khóa bí mật tương ứng; để đơn giản hóa, cặp khóa được chỉ định bằng khóa công khai và giả định rằng khóa bí mật có thể truy cập bởi chủ sở hữu.

Phép nối chuỗi byte X và Y được ký hiệu là X || Y. Thứ tự nối có ý nghĩa mật mã và phải được tuân thủ chính xác.

DH(PK1, PK2) là đầu ra của hàm Diffie–Hellman đường cong elliptic, sử dụng cặp khóa biểu diễn bởi PK1 và PK2 – là X25519 hoặc X448 tùy theo tham số curve.

Sig(PK, M, Z) là chữ ký XEdDSA trên chuỗi byte M, được tạo bằng cách ký M với khóa bí mật tương ứng PK và 64 byte ngẫu nhiên Z. Sự bổ sung của Z so với X3DH (dùng Sig(PK, M) không có Z) phản ánh đặc tính ngẫu nhiên của XEdDSA: entropy Z ngăn chặn các cuộc tấn công suy ra khóa riêng từ hai lần ký cùng thông điệp.

KDF(KM) là đầu ra 32 byte từ HKDF với: đầu vào khóa = F || KM (trong đó F là 32 byte 0xFF với curve25519 hoặc 57 byte 0xFF với curve448 – đảm bảo phân tách miền với XEdDSA); muối HKDF là chuỗi toàn số 0 có độ dài bằng đầu ra hàm băm; thông tin HKDF là chuỗi ghép bốn tham số PQXDH ngăn cách bởi dấu gạch dưới, ví dụ MyProtocol_CURVE25519_SHA512_CRYSTALS-KYBER-1024. Chuỗi thông tin HKDF này phục vụ phân tách miền ở tầng ứng dụng: SK do PQXDH tạo ra cho MyProtocol không thể tái sử dụng hay nhầm lẫn với SK của bất kỳ ứng dụng hay cấu hình khác nào.

(CT, SS) = PQKEM–ENC(PK) là bộ đôi gồm bản mã KEM CT và bí mật chung SS được đóng gói bởi CT bằng khóa công khai PK. PQKEM–DEC(PK, CT) là bí mật chung SS được giải mã từ CT bằng khóa bí mật tương ứng với PK. Hai thao tác này là cốt lõi của thành phần hậu lượng tử: chỉ người giữ khóa bí mật KEM mới có thể tính SS từ CT, ngay cả khi kẻ tấn công có máy tính lượng tử mạnh bao nhiêu.

Vai trò

Giao thức PQXDH liên quan đến ba bên với trách nhiệm và mức độ tin cậy khác nhau: Mỹ Anh, Đan Nguyên và một máy chủ.

Mỹ Anh là bên chủ động (initiator): muốn gửi dữ liệu ban đầu cho Đan Nguyên bằng mã hóa, đồng thời thiết lập khóa bí mật chung SK có thể dùng cho liên lạc hai chiều về sau. Mỹ Anh thực hiện toàn bộ các phép tính phía gửi – DH1, DH2, DH3, DH4 và PQKEM–ENC – mà không cần Đan Nguyên trực tuyến, chỉ dựa vào thông tin Đan Nguyên đã công bố trước lên máy chủ. Điều này đặt Mỹ Anh vào vị thế phải tin tưởng tính xác thực của thông tin nhận từ máy chủ – rủi ro được giảm thiểu thông qua cơ chế chữ ký trên tất cả khóa sơ bộ, bao gồm cả khóa KEM hậu lượng tử.

Đan Nguyên là bên bị động (responder): muốn cho phép các bên như Mỹ Anh thiết lập khóa chung và gửi dữ liệu mã hóa, trong khi bản thân có thể ngoại tuyến. Để hỗ trợ điều này, Đan Nguyên tải lên trước một tập khóa tiền đường cong elliptic và khóa tiền KEM hậu lượng tử. So với X3DH, khối lượng quản lý khóa của Đan Nguyên trong PQXDH tăng đáng kể: ngoài IKB, SPKB và OPKB, Đan Nguyên còn phải quản lý PQSPKB (khóa tiền KEM cuối cùng) và các PQOPKB (khóa tiền KEM một lần), tất cả đều cần được ký và tải lên với chữ ký tương ứng.

Máy chủ lưu trữ và cung cấp thông tin khóa tiền, lưu trữ tạm thời tin nhắn và chuyển tiếp chúng đến Đan Nguyên. Mức độ tin cậy đặt vào máy chủ trong PQXDH giống X3DH: máy chủ không thể đọc nội dung tin nhắn hay tính SK, nhưng một máy chủ độc hại có thể từ chối dịch vụ hay thay thế khóa tiền (bị phát hiện qua chữ ký). Trong một số hệ thống, vai trò máy chủ có thể được phân chia giữa nhiều thực thể – ví dụ máy chủ lưu trữ khóa tiền và máy chủ chuyển tiếp tin nhắn hoạt động độc lập nhau để giảm thiểu rủi ro từ điểm thất bại đơn.

Khóa đường cong Elliptic

PQXDH sử dụng cùng bộ khóa đường cong elliptic với X3DH, đóng vai trò nền tảng xác thực và bảo mật chuyển tiếp cho các đối thủ cổ điển.

Tất cả khóa đường cong phải đồng nhất loại: hoặc toàn bộ curve25519, hoặc toàn bộ curve448.

Mỗi bên có khóa định danh dài hạn (IKA cho Mỹ Anh, IKB cho Đan Nguyên). Đây là nền tảng của xác thực lẫn nhau: toàn bộ các phép tính DH1 và DH2 trong PQXDH đều liên quan đến khóa định danh của ít nhất một bên, ràng buộc SK với danh tính đã được xác thực của cả hai. Đan Nguyên cũng có SPKB được thay thế định kỳ và ký mỗi lần bằng IKB – chữ ký này là rào cản chống lại máy chủ độc hại thay thế SPKB bằng khóa giả.

Đối với mỗi khóa dự phòng có chữ ký hoặc dùng một lần K mà Đan Nguyên tạo, anh tính thêm một định danh IdEC(K) để xác định duy nhất khóa này trên thiết bị. Định danh này cho phép Đan Nguyên tải đúng khóa riêng khi nhận tin nhắn ban đầu: tin nhắn của Mỹ Anh chứa các định danh của khóa tiền đã dùng, và Đan Nguyên dùng chúng để tra cứu khóa riêng tương ứng. Thiết kế định danh ảnh hưởng đến bảo mật (xem phần Định danh khóa) và nên được quyết định cẩn thận ở cấp độ ứng dụng.

Khóa đóng gói hậu lượng tử (Quantum key)

PQXDH bổ sung hai loại khóa hậu lượng tử mới không có trong X3DH, được ký bằng IKB như các khóa đường cong để đảm bảo tính xác thực.

Tất cả khóa KEM trong một phiên phải dùng cùng tham số pqkem.

Đan Nguyên có một PQSPKB – khóa KEM cuối cùng được dùng khi không còn PQOPKB nào khả dụng. Tên gọi last-resort (cuối cùng) phản ánh chính xác vai trò của nó: đây là lựa chọn dự phòng, không phải lựa chọn ưu tiên. Các PQOPKB được ưu tiên vì tính chất một lần của chúng cung cấp bảo mật chuyển tiếp mạnh hơn. Cả PQSPKB lẫn PQOPKB đều được ký bằng IKB, và Đan Nguyên tính định danh IdKEM(K) cho mỗi khóa để thiết bị nhận có thể tải đúng khóa riêng KEM khi xử lý PQKEM–DEC.

Sự song hành giữa hệ thống khóa đường cong (SPKB/OPKB) và hệ thống khóa KEM (PQSPKB/PQOPKB) là có chủ đích. Trong mỗi phiên PQXDH, Mỹ Anh sử dụng một khóa tiền đường cong (SPKB hoặc OPKB) và một khóa tiền KEM (PQSPKB hoặc PQOPKB). Sự hiện diện hay vắng mặt của OPKB ảnh hưởng đến bảo mật chuyển tiếp cổ điển; sự hiện diện hay vắng mặt của PQOPKB ảnh hưởng đến bảo mật chuyển tiếp hậu lượng tử. Hai chiều bảo mật này độc lập nhau, cho phép phân tích rõ ràng hơn các hệ quả bảo mật của từng tình huống. Khóa PQOPKB bị xóa khi Đan Nguyên nhận và xử lý tin nhắn sử dụng nó – hành vi tương tự OPKB nhưng áp dụng cho thành phần hậu lượng tử.

Giao thức PQXDH

PQXDH triển khai qua ba giai đoạn tuần tự: Đan Nguyên công bố khóa định danh, khóa tiền đường cong elliptic và khóa tiền KEM hậu lượng tử lên máy chủ; Mỹ Anh truy xuất gói khóa tiền và gửi tin nhắn ban đầu; Đan Nguyên nhận và xử lý tin nhắn đó. Ba giai đoạn có thể diễn ra không đồng bộ: giai đoạn một xảy ra trước, giai đoạn hai và ba có thể cách nhau hàng giờ hay hàng ngày tùy thuộc vào trạng thái trực tuyến của Đan Nguyên.

Công khai khóa

Đan Nguyên tạo một chuỗi các giá trị ngẫu nhiên 64 byte ZSPK, ZPQSPK, Z1, Z2… và công bố tập hợp khóa lên máy chủ:

– Khóa định danh IKB. – Khóa sơ bộ đường cong đã ký (SPKB, IdEC(SPKB)) và chữ ký Sig(IKB, EncodeEC(SPKB), ZSPK). – Khóa sơ bộ KEM cuối cùng đã ký (PQSPKB, IdKEM(PQSPKB)) và chữ ký Sig(IKB, EncodeKEM(PQSPKB), ZPQSPK). – Tập hợp khóa sơ bộ đường cong một lần (OPKB1, OPKB2, OPKB3…) cùng định danh (IdEC(OPKB1), IdEC(OPKB2), IdEC(OPKB3)…). – Tập hợp khóa sơ bộ KEM một lần đã ký (PQOPKB1, PQOPKB2, PQOPKB3…) cùng định danh (IdKEM(PQOPKB1), IdKEM(PQOPKB2), IdKEM(PQOPKB3)…) và tập chữ ký tương ứng (Sig(IKB, EncodeKEM(PQOPKB1), Z1), Sig(IKB, EncodeKEM(PQOPKB2), Z2),…).

Điểm quan trọng cần chú ý so với X3DH là PQXDH yêu cầu ký cả các PQOPKB một lần. Trong X3DH, OPKB đường cong không cần chữ ký vì tính xác thực của chúng được đảm bảo gián tiếp qua cơ chế giao thức. Trong PQXDH, các PQOPKB phải có chữ ký IKB riêng vì một máy chủ có quyền truy cập vào máy tính lượng tử có thể tính khóa riêng của IKB và giả mạo chữ ký – việc kiểm tra tính hợp lệ của chữ ký trên mỗi PQOPKB giúp Mỹ Anh phát hiện sự giả mạo trước khi sử dụng.

Đan Nguyên chỉ cần tải IKB lên một lần. SPKB và PQSPKB được thay thế định kỳ (thường mỗi tuần hoặc mỗi tháng) – khóa sơ bộ mới thay thế khóa cũ. Sau khi tải khóa sơ bộ mới, Đan Nguyên giữ lại khóa riêng cũ trong thời gian ngắn để xử lý các tin nhắn trễ sử dụng khóa đó, rồi xóa vĩnh viễn để bảo mật chuyển tiếp. Đối với các OPKB và PQOPKB, Đan Nguyên tải thêm khi kho gần cạn và xóa khóa riêng ngay khi nhận tin nhắn sử dụng chúng. Triển khai nên cung cấp cho Đan Nguyên phương thức để xác định một khóa KEM công khai cụ thể thuộc loại one-time (PQOPKB) hay last-resort (PQSPKB), vì hai loại này có chính sách vòng đời khác nhau.

Gửi tin nhắn ban đầu

Để thực hiện thỏa thuận khóa PQXDH với Đan Nguyên, Mỹ Anh liên hệ máy chủ và truy xuất một gói khóa sơ bộ chứa: IKB; (SPKB, IdEC(SPKB)) và Sig(IKB, EncodeEC(SPKB), ZSPK); một trong hai: PQOPKBn (ưu tiên, nếu còn) hoặc PQSPKB (dự phòng, nếu hết PQOPKB); định danh khóa KEM được cấp IdKEM(PQPKB) và chữ ký Sig(IKB, EncodeKEM(PQPKB), ZPQPK); và tùy chọn một OPKBn cùng định danh IdEC(OPKBn).

Mỹ Anh xác minh tất cả chữ ký trên gói khóa sơ bộ. Nếu bất kỳ chữ ký nào không hợp lệ, giao thức bị hủy ngay lập tức. Sau khi xác minh thành công, Mỹ Anh tạo cặp khóa tạm thời đường cong mới EKA và thực hiện đóng gói KEM hậu lượng tử:

(CT, SS) = PQKEM–ENC(PQPKB)

Nếu gói khóa không có OPKB:

DH1 = DH(IKA, SPKB)
DH2 = DH(EKA, IKB)
DH3 = DH(EKA, SPKB)
SK = KDF(DH1 || DH2 || DH3 || SS)

Nếu gói khóa có OPKB:

DH4 = DH(EKA, OPKB)
SK = KDF(DH1 || DH2 || DH3 || DH4 || SS)

Sự hiện diện của SS – bí mật chung từ PQKEM–ENC – là điểm cốt lõi phân biệt PQXDH với X3DH. Trong X3DH, SK = KDF(DH1 || DH2 || DH3 || DH4); trong PQXDH, SS được nối thêm vào trước khi đưa qua KDF. Điều này đảm bảo rằng để tính SK, kẻ tấn công phải giải quyết đồng thời cả bài toán ECDLP (để tính các giá trị DH) lẫn bài toán Module-LWE (để tính SS mà không có khóa riêng KEM). Kết cấu DH1 || DH2 || DH3 || DH4 || SS đảm bảo tính chất xác thực lẫn nhau không bị ảnh hưởng: DH1 và DH2 vẫn cung cấp xác thực, DH3/DH4 vẫn cung cấp bảo mật chuyển tiếp cổ điển, và SS cung cấp bảo mật chuyển tiếp hậu lượng tử.

Sau khi tính SK, Mỹ Anh xóa khóa riêng tạm thời, các giá trị DH và SS. Mỹ Anh tính AD:

AD = EncodeEC(IKA) || EncodeEC(IKB)

Nếu pqkem không tích hợp PQPKB vào bản mã (một số KEM không làm vậy), Mỹ Anh phải thêm EncodeKEM(PQPKB) vào AD để ràng buộc bản mã KEM với giao thức – đây là biện pháp chống tấn công tái mã hóa KEM. Tin nhắn ban đầu gửi cho Đan Nguyên gồm: IKA, EKA, CT, định danh các khóa sơ bộ đã dùng, và bản mã AEAD với AD là dữ liệu liên kết và SK là khóa mã hóa.

Nhận tin nhắn ban đầu

Sau khi nhận tin nhắn ban đầu từ Mỹ Anh, Đan Nguyên trích xuất IKA và EKA từ tiêu đề, tải khóa riêng nhận dạng của mình, và dùng các định danh khóa để tải đúng khóa riêng SPKB, OPKB (nếu có) và PQPKB mà Mỹ Anh đã sử dụng. Bước tra cứu khóa riêng theo định danh là điều kiện tiên quyết để Đan Nguyên có thể thực hiện đúng các phép tính.

Đan Nguyên tính PQKEM–DEC(PQPKB, CT) để thu bí mật chung SS, sau đó thực hiện lại đúng trình tự các phép DH và KDF theo tổ hợp khóa tương ứng (có hoặc không có DH4 tùy theo gói khóa Mỹ Anh đã dùng) để dẫn xuất SK. Tính đúng đắn của bước này dựa trên tính đối xứng của DH và tính đúng đắn của KEM: PQKEM–DEC trả về cùng SS mà PQKEM–ENC đã tạo ra, đảm bảo SK của Đan Nguyên bằng SK của Mỹ Anh. Sau khi tính xong, Đan Nguyên xóa các giá trị DH và SS.

Đan Nguyên xây dựng AD theo cách giống Mỹ Anh và thử giải mã bản mã ban đầu bằng SK và AD. Nếu giải mã thất bại – do xác thực AEAD không thành công hay AD không khớp – Đan Nguyên hủy giao thức và xóa SK. Giải mã thất bại có thể do Mỹ Anh dùng sai tham số, dữ liệu bị hỏng trên đường truyền, hay máy chủ đã can thiệp. Nếu giải mã thành công, Đan Nguyên xóa ngay khóa riêng PQOPKB đã dùng (nếu có) để bảo mật chuyển tiếp hậu lượng tử. Cả hai bên lúc này có SK và có thể chuyển sang giao thức liên lạc sau PQXDH – thường là Double Ratchet với SK làm khóa gốc ban đầu.

Cân nhắc về bảo mật

Bảo mật của PQXDH kết hợp với Double Ratchet đã được phân tích chính thức trong mô hình ký hiệu với ProVerif và mô hình tính toán với CryptoVerif. Với ProVerif, các tác giả chứng minh xác thực và tính bí mật trong mô hình ký hiệu, đồng thời liệt kê các điều kiện cụ thể mà kẻ tấn công có thể phá vỡ các thuộc tính này. PQXDH duy trì mức bảo mật của X3DH trước đối thủ cổ điển, đồng thời yêu cầu giải quyết thêm GapDH và Module-LWE để phá vỡ bắt tay trước đối thủ lượng tử thụ động.

Sử dụng CryptoVerif, các tác giả chứng minh bảo mật tính toán và xác thực theo giả định GapDH cho X25519, UF-CMA trên XEdDSA, mô hình hóa hàm băm như oracle ngẫu nhiên và IND-CPA+INT-CTXT cho AEAD. Bảo mật chuyển tiếp hậu lượng tử được chứng minh thêm khi giả định bảo mật IND-CCA hậu lượng tử cho KEM, mô hình hóa hàm băm như PRF và IND-CPA+INT-CTXT cho AEAD. Tuy nhiên, một bằng chứng đầy đủ về bảo mật dưới giả định chung của GapDH và UF-CMA cho cả X25519 và XEdDSA vẫn còn cần thiết.

Xác thực

Xác thực trong PQXDH, giống X3DH, được thực hiện thông qua các phép tính DH liên quan đến khóa định danh dài hạn, không phải qua chữ ký trực tiếp lên thông điệp. DH1 = DH(IKA, SPKB) cung cấp tính xác thực phía gửi: chỉ người giữ khóa riêng IKA mới có thể tính đúng giá trị này. DH2 = DH(EKA, IKB) cung cấp tính xác thực phía nhận: chỉ người giữ khóa riêng IKB mới có thể tính đúng giá trị này từ phía của Đan Nguyên. Cấu trúc xác thực dựa trên DH này – thay vì chữ ký trực tiếp – là nguồn gốc của khả năng phủ nhận mà PQXDH cung cấp.

Quan trọng cần nhấn mạnh: xác thực trong PQXDH không đảm bảo an toàn trước đối thủ lượng tử chủ động. Một kẻ tấn công có máy tính lượng tử đủ mạnh có thể tính logarit rời rạc trên đường cong elliptic và do đó tính khóa riêng từ khóa công khai của bất kỳ bên nào, giả mạo toàn bộ thành phần xác thực Diffie–Hellman. PQXDH bảo vệ tính bí mật của SK trước đối thủ lượng tử thụ động (qua thành phần KEM hậu lượng tử), nhưng không bảo vệ tính xác thực trước đối thủ lượng tử chủ động (vì thành phần xác thực vẫn dựa trên ECDLP). Đây là giới hạn thiết kế được thừa nhận công khai trong phiên bản hiện tại, và Signal hy vọng giải quyết trong phiên bản tương lai. Các bên có thể xác minh khóa định danh qua kênh ngoài băng (quét mã QR, so sánh số an toàn) để tăng cường bảo vệ. Xác thực lẫn nhau có thể phủ nhận và an toàn hậu lượng tử vẫn là vấn đề nghiên cứu mở.

Phát lại giao thức

Nếu tin nhắn ban đầu của Mỹ Anh không sử dụng PQOPKB một lần (vì kho đã cạn và chỉ có PQSPKB), tin nhắn đó có thể bị phát lại nhiều lần đến Đan Nguyên và anh sẽ chấp nhận mỗi lần. Lý do là PQSPKB không bị xóa sau khi dùng – không giống PQOPKB. Kẻ tấn công có được bản sao tin nhắn ban đầu có thể gửi lại nhiều lần, buộc Đan Nguyên tạo nhiều phiên riêng biệt với cùng SK. Đây là cùng vấn đề phát lại như trong X3DH, nhưng có thêm chiều hậu lượng tử: phát lại thành công cũng tái tạo lại thành phần SS từ bản mã KEM CT, vì CT được mang nguyên vẹn trong tin nhắn ban đầu.

Để giảm thiểu, giao thức sau PQXDH cần nhanh chóng đàm phán khóa mã hóa mới dựa trên đầu vào ngẫu nhiên mới từ Đan Nguyên – hành vi điển hình của các giao thức ratcheting như Double Ratchet. Ngay khi Đan Nguyên gửi phản hồi qua Double Ratchet với khóa Ratchet mới, SK ban đầu được thay thế bởi một chuỗi khóa mới phụ thuộc vào cả khóa Ratchet của Đan Nguyên – thông tin mà kẻ phát lại không thể biết. Đan Nguyên cũng có thể thực hiện các biện pháp bổ sung như duy trì danh sách đen các CT đã quan sát trong khoảng thời gian giới hạn, hay thay thế PQSPKB thường xuyên hơn để thu hẹp cửa sổ phát lại.

Phát lại và tái sử dụng khóa

Hệ quả trực tiếp của phát lại thành công: Đan Nguyên có thể tạo ra cùng một SK trong các lần thực thi giao thức khác nhau. Nếu giao thức sau PQXDH dùng SK trực tiếp để mã hóa, việc tái sử dụng SK là thảm họa bảo mật: cùng khóa mã hóa hai bản mã khác nhau cho phép kẻ tấn công khôi phục nội dung qua phân tích XOR với nhiều sơ đồ mã hóa đối xứng.

Vì lý do này, bất kỳ giao thức sau PQXDH nào cũng phải bắt buộc ngẫu nhiên hóa khóa mã hóa trước khi Đan Nguyên gửi dữ liệu mã hóa. Double Ratchet thực hiện điều này một cách tự nhiên: ngay trong tin nhắn đầu tiên Đan Nguyên gửi cho Mỹ Anh, một bước tăng DH mới được thực hiện đưa entropy hoàn toàn mới vào chuỗi khóa, tạo ra khóa chuỗi mới không phụ thuộc vào SK ban đầu theo bất kỳ cách nào có thể đoán trước. Sau bước này, kể cả kẻ tấn công biết SK ban đầu cũng không thể tính được các khóa tin nhắn Double Ratchet. Việc không thực hiện bước ngẫu nhiên hóa – dùng SK như một khóa mã hóa tĩnh – là lỗi triển khai nghiêm trọng tạo ra lỗ hổng cơ bản phá vỡ hoàn toàn tính bảo mật tiến về phía trước.

Khả năng phủ nhận

Khả năng phủ nhận trong PQXDH có nghĩa là giao thức không cung cấp cho những người tham gia bằng chứng mật mã có thể công bố về nội dung giao tiếp hay bằng chứng về việc họ đã giao tiếp. Đây là tính chất quan trọng bảo vệ người dùng trong các ngữ cảnh pháp lý hay chính trị nhạy cảm.

PQXDH, giống X3DH, nhằm mục đích cung cấp cho cả Mỹ Anh và Đan Nguyên khả năng phủ nhận trong bối cảnh một thẩm phán có quyền truy cập vào khóa bí mật của một hoặc nhiều bên phán xét một bản ghi được cho là do Mỹ Anh và Đan Nguyên tạo ra. Signal tập trung vào khả năng phủ nhận ngoại tuyến: nếu một trong hai bên hợp tác với bên thứ ba trong quá trình thực thi giao thức, họ có thể cung cấp bằng chứng về cuộc giao tiếp. Hạn chế đối với khả năng phủ nhận trực tuyến này dường như là đặc điểm cố hữu của môi trường không đồng bộ.

PQXDH có một số dạng khả năng phủ nhận mật mã. Vì Mỹ Anh hoặc Đan Nguyên có thể tạo bản ghi giả bằng cách chỉ dùng khóa bí mật của riêng họ, PQXDH có thuộc tính phủ nhận 1-trong-2 theo nghĩa của Brendel et al. PQXDH cũng có thể phủ nhận theo nghĩa của Vatandas et al. đối với Mỹ Anh, và Signal giả thuyết rằng nó cũng phủ nhận được đối với Đan Nguyên nếu có thêm giả định Nhận Thức Văn Bản Thô (Plaintext Awareness – PA) đối với pqkem. Signal lưu ý rằng Kyber sử dụng biến thể Fujisaki–Okamoto với cơ chế từ chối ngầm và do đó không có thuộc tính PA; tuy nhiên, việc bản mã AEAD luôn được gửi kèm bản mã Kyber trong PQXDH có thể mang lại đảm bảo tương đương PA. Tất cả các khẳng định này áp dụng cho môi trường cổ điển; khả năng phủ nhận trước đối thủ lượng tử độc hại vẫn cần nghiên cứu thêm.

Chữ ký

Có thể nảy sinh suy nghĩ rằng chữ ký trên các khóa sơ bộ là không cần thiết vì xác thực lẫn nhau đã được đảm bảo qua các phép DH. Tuy nhiên, đây là lập luận sai dẫn đến một cuộc tấn công nghiêm trọng: máy chủ độc hại có thể cung cấp cho Mỹ Anh gói khóa sơ bộ có chứa các khóa giả mạo – SPKB và PQPKB do máy chủ tạo ra – và giữ khóa riêng tương ứng. Khi đó máy chủ có thể tính DH1, DH2, DH3 và PQKEM–DEC bằng khóa riêng giả mạo, thu được cùng SK như Mỹ Anh. Chữ ký Sig(IKB, EncodeEC(SPKB)) và Sig(IKB, EncodeKEM(PQPKB)) ràng buộc các khóa sơ bộ với IKB: để giả mạo, máy chủ phải có khóa riêng IKB – điều đó đòi hỏi phải xâm phạm khóa định danh của Đan Nguyên, không chỉ thay thế khóa sơ bộ.

Ngoài ra, cũng có thể muốn thay thế xác thực dựa trên DH (DH1 và DH2) bằng chữ ký từ khóa định danh trực tiếp lên thông điệp. Điều này có ba hệ quả tiêu cực: giảm khả năng phủ nhận (chữ ký trực tiếp tạo ra bằng chứng mật mã không thể chối bỏ); tăng kích thước tin nhắn ban đầu (thêm hai chữ ký 64 byte mỗi cái); và gia tăng thiệt hại nếu sơ đồ chữ ký bị phá vỡ trong tương lai – với xác thực dựa trên DH, việc phá vỡ chữ ký không ảnh hưởng đến tính bí mật của SK đã thỏa thuận, trong khi với chữ ký trực tiếp, nó ảnh hưởng đến cả xác thực lẫn toàn vẹn thông điệp.

Xâm phạm khóa (Key compromise)

Hệ quả của xâm phạm khóa trong PQXDH phức tạp hơn X3DH do có thêm chiều hậu lượng tử. Cần phân tích riêng biệt từng kịch bản để đánh giá đúng mức độ thiệt hại.

Xâm phạm khóa riêng định danh IKB cho phép kẻ tấn công giả mạo Đan Nguyên trong tất cả các phiên tương lai, vì IKB tham gia vào xác thực (DH2) và ký tất cả khóa sơ bộ. Đây là kịch bản nghiêm trọng nhất và không có biện pháp nào trong phạm vi giao thức PQXDH có thể ngăn chặn – hệ thống phải thu hồi và thay thế IKB cùng toàn bộ khóa sơ bộ.

Nếu PQOPKB một lần được sử dụng trong phiên và đã bị xóa đúng quy định, việc sau đó xâm phạm IKB, SPKB và PQSPKB vẫn không đủ để tính lại SK cũ – vì thiếu khóa riêng PQOPKB đã xóa. Đây là mức bảo mật chuyển tiếp hậu lượng tử mạnh nhất PQXDH có thể cung cấp: không chỉ bảo vệ trước đối thủ cổ điển mà còn trước đối thủ lượng tử tấn công sau khi phiên kết thúc.

Nếu không có PQOPKB, xâm phạm IKB, SPKB và PQSPKB từ cùng phiên giao thức sẽ tiết lộ SK: kẻ tấn công có thể tính lại DH1, DH2, DH3 và PQKEM–DEC. Việc thay thế thường xuyên SPKB và PQSPKB giới hạn cửa sổ phơi bày; giao thức ratcheting sau PQXDH giúp thay thế SK nhanh chóng bằng khóa mới. Xâm phạm khóa sơ bộ còn có thể tạo điều kiện cho tấn công giả mạo danh tính (key-compromise impersonation) kéo dài cho đến khi bên bị xâm phạm tải lên khóa sơ bộ mới.

Đối thủ lượng tử thụ động (Passive quantum adversaries)

PQXDH được thiết kế để ngăn chặn các cuộc tấn công thu thập trước, giải mã sau từ đối thủ có quyền truy cập vào máy tính lượng tử có khả năng tính logarit rời rạc trên đường cong elliptic. Đối thủ thụ động ở đây có nghĩa là họ chỉ quan sát và ghi lại lưu lượng mã hóa, không can thiệp vào giao tiếp đang diễn ra.

Tính bảo mật này phụ thuộc chủ yếu vào pqkem nhưng cũng yêu cầu aead cung cấp bảo mật IND-CPA và INT-CTXT hậu lượng tử. Thuật toán Grover giảm mức bảo mật của AES-256 từ 256 bit xuống còn khoảng 128 bit lượng tử – vẫn đủ an toàn theo tiêu chí NIST Level 1. Việc ước tính chính xác sức mạnh bảo mật hậu lượng tử của AES-GCM là phức tạp, nhưng nhìn chung cộng đồng mật mã đồng thuận rằng AES-256-GCM là lựa chọn đủ an toàn cho aead trong PQXDH.

Signal lưu ý ba đặc tính bảo mật cụ thể: nếu kẻ tấn công chỉ ghi lại thông tin công khai và bản mã, ngay cả với máy tính lượng tử mạnh, họ không thể tính SK vì còn cần khóa riêng KEM của Đan Nguyên; nếu PQOPKB được dùng và xóa đúng quy định, kể cả với máy tính lượng tử trong tương lai, SK của phiên đó vẫn an toàn; nếu không dùng PQOPKB, việc xâm phạm khóa riêng PQSPKB kết hợp với máy tính lượng tử (để tính các giá trị DH cổ điển) đủ để tính SK. Rủi ro cuối cùng nhấn mạnh tầm quan trọng của việc duy trì kho PQOPKB đầy đủ.

Đối thủ lượng tử chủ động (Active quantum adversaries)

PQXDH không được thiết kế để bảo vệ chống lại đối thủ lượng tử chủ động – kẻ tấn công có máy tính lượng tử và đang can thiệp tích cực vào giao tiếp trong thời gian thực.

Một kẻ tấn công chủ động có máy tính lượng tử có thể tính DH(PK1, PK2) cho bất kỳ cặp khóa công khai nào bằng cách đầu tiên tính khóa riêng của một trong hai từ khóa công khai, sau đó thực hiện phép nhân vô hướng thông thường. Điều này cho phép giả mạo Mỹ Anh hoàn toàn: kẻ tấn công tính khóa riêng tương ứng với IKA và thực hiện toàn bộ giao thức giả vờ là Mỹ Anh. Tương tự, máy chủ độc hại có máy tính lượng tử có thể giả mạo Đan Nguyên: tạo cặp khóa KEM mới PQSPK’B và PQOPK’B, tính khóa riêng tương ứng với IKB bằng máy tính lượng tử, ký các khóa KEM giả bằng khóa riêng IKB tính được, rồi cung cấp gói khóa giả này cho Mỹ Anh.

Giải pháp tiềm năng là bổ sung khóa định danh hậu lượng tử để Đan Nguyên ký các khóa sơ bộ hậu lượng tử – điều này ngăn máy chủ lượng tử độc hại giả mạo chữ ký. Tuy nhiên, chưa có cơ chế xác thực lẫn nhau có thể phủ nhận và an toàn hậu lượng tử nào được tiêu chuẩn hóa. Các sơ đồ KEM và chữ ký hậu lượng tử do NIST tiêu chuẩn hóa không tự cung cấp cơ chế này, mặc dù điều này có thể đạt được qua chữ ký vòng hậu lượng tử hoặc chữ ký của trình xác minh được chỉ định. Signal kêu gọi cộng đồng nghiên cứu hướng tới tiêu chuẩn hóa các cơ chế này.

Tin cậy máy chủ

Mức độ tin cậy cần đặt vào máy chủ trong PQXDH tương tự X3DH, nhưng phân tích phức tạp hơn do có thêm thành phần hậu lượng tử.

Một máy chủ đơn thuần không trung thực có thể gây gián đoạn tính khả dụng (từ chối chuyển tiếp tin nhắn), nhưng không thể phá vỡ tính bí mật nội dung hay giả mạo danh tính. Nếu Mỹ Anh và Đan Nguyên đã xác thực lẫn nhau, cuộc tấn công bổ sung duy nhất máy chủ có thể thực hiện là từ chối cung cấp OPKB hay PQOPKB một lần. Điều này buộc tất cả phiên phải dùng SPKB và PQSPKB (last-resort) – giảm mức bảo mật chuyển tiếp cả cổ điển lẫn hậu lượng tử. Kẻ tấn công độc hại cũng có thể cố tình làm cạn kiệt kho PQOPKB bằng cách gửi ồ ạt yêu cầu truy xuất gói khóa tiền; máy chủ nên giới hạn tốc độ truy xuất để ngăn chặn điều này.

Ràng buộc nhận dạng (Identity binding)

Xác thực không nhất thiết ngăn chặn được cuộc tấn công gán nhầm danh tính. Kẻ tấn công Kỳ Lân có thể trình bày sai dấu vân tay khóa nhận dạng của Đan Nguyên cho Mỹ Anh như thể đó là của chính Kỳ Lân. Khi Mỹ Anh xác minh dấu vân tay đó qua kênh ngoài băng, cô thực ra đang xác nhận khóa của Đan Nguyên nhưng tin là khóa của Kỳ Lân. Kết quả là Mỹ Anh nghĩ mình đang giao tiếp với Kỳ Lân trong khi thực tế đang giao tiếp với Đan Nguyên – hoặc ngược lại tùy vào cách Kỳ Lân tổ chức việc chuyển tiếp.

Cuộc tấn công này không đòi hỏi bất kỳ năng lực mật mã nào – nó thuần túy là tấn công xã hội khai thác quá trình xác minh danh tính ngoài băng. Biện pháp giảm thiểu là bổ sung nhiều thông tin nhận dạng hơn vào AD hay dấu vân tay: tên người dùng, số điện thoại, tên thật hay địa chỉ email. Kỳ Lân sẽ buộc phải nói dối về các giá trị bổ sung này, điều này khó hơn khi chúng có thể kiểm tra dễ dàng qua kênh độc lập khác. Tuy nhiên, không có cơ chế mật mã nào đảm bảo hoàn toàn không bị kẻ tấn công nói dối về thông tin nhận dạng tùy ý. Việc đưa thêm thông tin nhận dạng vào giao thức thường dẫn đến đánh đổi liên quan đến quyền riêng tư, tính linh hoạt và trải nghiệm người dùng.

Rủi ro từ nguồn ngẫu nhiên yếu (Weak randomness)

Tính bảo mật của SS trong PQXDH phụ thuộc vào chất lượng nguồn ngẫu nhiên trên thiết bị của Mỹ Anh tại thời điểm thực hiện PQKEM–ENC. Đây là điểm song song với Diffie–Hellman: trong DH, chất lượng entropy ảnh hưởng đến khóa tạm thời EKA; trong KEM, nó ảnh hưởng đến bí mật đóng gói SS.

Đối với cả Diffie–Hellman và Kyber, nếu Mỹ Anh có entropy yếu, bí mật chung thu được sẽ có entropy thấp khi được điều kiện hóa trên khóa công khai của Đan Nguyên. Do đó, cả bảo mật cổ điển lẫn hậu lượng tử của SK đều phụ thuộc vào chất lượng nguồn ngẫu nhiên của Mỹ Anh – một điểm thất bại tiềm năng dù có hay không có máy tính lượng tử. Kyber giảm thiểu một phần rủi ro bằng cách băm khóa công khai của Đan Nguyên cùng với các bit ngẫu nhiên của Mỹ Anh để tạo SS, làm cho khóa của Đan Nguyên có tính đóng góp. Điều này hạn chế khả năng của Mỹ Anh kiểm soát hoàn toàn SS, nhưng không giảm sự phụ thuộc vào entropy của Mỹ Anh. Không phải tất cả sơ đồ KEM đều có tính đóng góp của khóa người nhận, và đây là đặc tính quan trọng cần kiểm tra khi lựa chọn pqkem – các sơ đồ không có tính đóng góp mở ra lỗ hổng cho Mỹ Anh (hay kẻ giả mạo Mỹ Anh) kiểm soát SS bằng cách chọn đầu vào ngẫu nhiên đặc biệt.

Ngăn chặn các cuộc tấn công tái mã hóa KEM

Khi dùng KEM dựa trên mã hóa khóa công khai để đóng gói bí mật chung, bí mật chung đó thường không được gắn chặt với khóa công khai đóng gói. Điều này mở ra tấn công tái mã hóa (re-encapsulation attack): bí mật chung tương ứng với việc đóng gói một khóa công khai KEM bị xâm phạm có thể được đóng gói lại đối với khóa công khai KEM khác chưa bị xâm phạm, mà không làm thay đổi bí mật chung. Kẻ tấn công biết khóa riêng KEM cũ có thể giải mã bản mã gốc để lấy SS, rồi đóng gói lại SS cho khóa KEM mới – khiến phiên mới trông hoàn toàn hợp lệ nhưng thực chất bị kiểm soát bởi kẻ tấn công.

Tính bảo mật IND-CCA của KEM không ngăn chặn hành vi này vì IND-CCA chỉ bảo vệ tính bí mật, không bảo vệ tính ràng buộc giữa bản mã và khóa. Cuộc tấn công này đặc biệt phá vỡ tính độc lập phiên: xâm phạm một PQPKB có thể ảnh hưởng đến tính bảo mật của các phiên khác mà lẽ ra phải độc lập hoàn toàn. Kyber ngăn chặn tấn công này bằng cách tích hợp khóa công khai KEM vào quá trình tạo bí mật chung (trong biến thể Fujisaki–Okamoto mà Kyber sử dụng). Đối với KEM IND-CCA tổng quát không có tính chất này, biện pháp đối phó là thêm EncodeKEM(PQPKB) vào AD của tin nhắn ban đầu – điều này ràng buộc bản mã KEM với danh tính khóa công khai thông qua xác thực AEAD, làm cho bất kỳ sự thay thế bản mã nào đều bị phát hiện ngay khi Đan Nguyên cố giải mã.

Định danh khóa

Các định danh IdEC(K) và IdKEM(K) không phải là yếu tố bảo mật cốt lõi – giá trị thực tế của các khóa đã được ký bằng IKB hoặc được đưa vào AD. Tuy nhiên, thiết kế định danh ảnh hưởng đến tính đúng đắn (correctness) của giao thức và có thể gián tiếp ảnh hưởng đến bảo mật.

Nếu định danh trùng lặp giữa hai khóa khác nhau, Đan Nguyên sẽ tải sai khóa riêng khi xử lý tin nhắn và giải mã PQKEM–DEC sẽ thất bại. Điều này gây lỗi giao thức nhưng không phá vỡ bảo mật – Đan Nguyên chỉ hủy giao thức. Rủi ro lớn hơn là định danh có thể dự đoán được, tạo cơ hội cho kẻ tấn công biết trước khóa nào sẽ được dùng trong phiên tiếp theo và chuẩn bị trước.

Ứng dụng có thể chọn dùng chính khóa công khai làm định danh (định danh kích thước lớn, đảm bảo duy nhất tuyệt đối), hay dùng định danh nhỏ hơn để giảm kích thước tin nhắn. Các phương pháp tạo định danh nhỏ bao gồm: băm của khóa công khai (thường lấy 8–16 byte đầu của SHA256 hay SHA512); giá trị ngẫu nhiên được tạo khi tạo khóa; hay giá trị tuần tự bắt đầu từ một độ lệch ngẫu nhiên. Trong cả ba trường hợp, xác suất xung đột cần đủ thấp để không gây lỗi giao thức trong vòng đời thực tế của ứng dụng. Với kho PQOPKB thường không quá vài nghìn khóa, định danh 32 bit ngẫu nhiên đã cung cấp xác suất xung đột rất thấp theo sinh nhật – xác suất tốt hơn nhiều khi dùng định danh tuần tự hay băm ngắn.