filippo.io/mlkem768: Mật mã kháng lượng tử cho hệ sinh thái Go

 (words.filippo.io)
1 điểm bởi GN⁺ 2024-02-02 | 1 bình luận | Chia sẻ qua WhatsApp
  • filippo.io/mlkem768 triển khai ML-KEM-768 bằng Go thuần, tiêu chuẩn đang được NIST chuẩn hóa, giúp hệ sinh thái Go có thể đánh giá trao đổi khóa kháng lượng tử
  • Gồm khoảng 500 dòng mã, 200 dòng chú thích và 650 dòng kiểm thử, không có phụ thuộc nào ngoài golang.org/x/crypto/sha3, nên rất dễ đưa vào dưới dạng gói nội bộ của thư viện chuẩn Go
  • Thay vì port triển khai tham chiếu pq-crystals, dự án được viết trực tiếp theo đặc tả FIPS 203 để kiểm chứng liệu có thể tạo ra một triển khai tương thích chỉ từ đặc tả hay không
  • Phần khó nhất là nén/giải nén và vận hành hằng thời gian; dự án dùng Barrett reduction để tránh rủi ro lệnh DIV thời gian biến thiên có thể xuất hiện trong các triển khai cùng họ với bản tham chiếu
  • Tối ưu hiệu năng không phải mục tiêu số một, nhưng đường đi của Bob có tốc độ tương đương X25519 và P-256 trong Go, còn đường đi của Alice cũng dưới 2 lần, cho thấy một triển khai đơn giản vẫn đủ nhanh cho sử dụng thực tế

Triển khai Go thuần của ML-KEM-768

  • filippo.io/mlkem768 là một triển khai Go thuần của ML-KEM-768, ưu tiên tính đúng đắn và khả năng đọc hiểu
  • ML-KEM trước đây được biết đến với tên Kyber và là một cơ chế trao đổi khóa kháng lượng tử đang trong quá trình chuẩn hóa của NIST
  • Gói này gồm khoảng 500 dòng mã, 200 dòng chú thích và 650 dòng kiểm thử
  • Phụ thuộc duy nhất là golang.org/x/crypto/sha3
  • Mục tiêu là đưa nó upstream vào thư viện chuẩn Go, ban đầu dưới dạng gói nội bộ chỉ dùng cho thử nghiệm crypto/tls theo cơ chế opt-in

Cách triển khai bám sát FIPS 203

  • Triển khai này không port thư viện tham chiếu pq-crystals mà được viết mới hoàn toàn, không đọc sâu các codebase khác trước đó
  • Mục tiêu cốt lõi là kiểm tra xem liệu có thể tạo ra một triển khai tương thích chỉ dựa trên đặc tả hay không
  • Tài liệu FIPS 203 cung cấp mã giả chi tiết, định nghĩa đầy đủ và thông tin kiểu nhất quán, nên rất phù hợp làm hướng dẫn triển khai
  • Tên hàm, tên biến và thứ tự phép toán được giữ gần nhất có thể với đặc tả FIPS để giúp việc review và học tập dễ dàng hơn
  • Nền tảng toán học cần thiết để triển khai ML-KEM được trình bày riêng trong Enough Polynomials and Linear Algebra to Implement Kyber

Nén/giải nén và triển khai hằng thời gian

  • Còn lại ba bài toán triển khai chính
    • triển khai số học modulo với số nguyên tố 3329
    • triển khai hàm nén/giải nén ánh xạ giá trị trong [0, 3329) sang [0, 2ᵈ) rồi ngược lại
    • bảo đảm vận hành hằng thời gian
  • Số học modulo tương đối dễ nhờ kinh nghiệm tích lũy từ triển khai RSA và đường cong elliptic, còn số nguyên tố nhỏ giúp việc hiện thực đơn giản hơn
  • Nén và giải nén là phần khó nhất
    • Đặc tả mô tả trừu tượng bằng phân số và quy tắc làm tròn
    • Triển khai thực tế phải xử lý bằng số học hằng thời gian và phép toán bit
  • Nhiều triển khai tham chiếu và các bản port của chúng dùng phép chia, vốn có thể bị biên dịch thành lệnh DIV thời gian biến thiên tùy tối ưu hóa của compiler và nền tảng
  • Gói này ngay từ đầu đã dùng Barrett reduction nên không bị ảnh hưởng, và BoringSSL cũng dùng cùng cách tiếp cận

Vì sao chỉ nhắm tới ML-KEM-768

  • Triển khai chỉ tập trung vào ML-KEM-768 trong ba mức an toàn -512, -768, -1024 của ML-KEM
  • Nhóm Kyber khuyến nghị dùng -768 thay vì -512 để có biên an toàn bảo thủ hơn trước các kết quả mật mã phân tích mới
  • -1024 được mô tả là lựa chọn cho mức an toàn 256 bit, tức phục vụ tuân thủ quy định và strength matching
  • Vì phần lớn các giao thức đang thử nghiệm hoặc chuẩn hóa đều hội tụ về ML-KEM-768, việc chỉ nhắm một mức gần như không làm tăng chi phí
  • Chỉ nhắm một mức giúp giảm số lượng phần chuyển động, có lợi cho khả năng đọc, bảo mật và hiệu năng
    • Ví dụ, thay vì dùng một bộ mã hóa tổng quát cho tuần tự hóa số nguyên 1, 4, 10, 12 bit, dự án tách thành các bộ mã hóa/giải mã chuyên biệt
    • Vì chỉ hỗ trợ ML-KEM-768 nên không cần triển khai mã hóa 5 bit và 11 bit

Chiến lược kiểm thử và test vector công khai

  • Kiểm thử là trụ cột quan trọng thứ hai trong chiến lược bảo đảm an toàn của gói này, chỉ sau khả năng đọc hiểu
  • Kiểm thử cơ bản gồm vòng lặp key generation, encapsulation, decapsulation và độ bao phủ kiểm thử trên 95%
  • Phạm vi kiểm thử bổ sung gồm
    • xác minh khả năng tương thích với test vector từ NIST và các triển khai khác
    • so sánh mọi tổ hợp đầu vào của phép cộng, trừ, nhân modulo 3329 với giá trị kỳ vọng được tính bằng cách thời gian biến thiên
    • kiểm thử vét cạn nén/giải nén theo chuẩn math/big.Rat
    • xác minh các hằng số tiền tính toán khớp với định nghĩa
    • kiểm tra mọi hàm đều trả lỗi phù hợp khi độ dài đầu vào quá dài hoặc quá ngắn
    • chạy test vector do Sophie Schmieg cung cấp và sẽ được đưa vào Wycheproof trong tương lai
  • Bộ test vector tự tạo cũng được công bố như một phần của dự án CCTV để các triển khai khác có thể tái sử dụng
  • Vector CCTV bao gồm giá trị trung gian để kiểm thử và debug từng bước trung gian cũng như các thuật toán con

Những lỗi mà test vector đặc biệt có thể bắt được

  • Negative test vectors cung cấp khóa encapsulation sai với hệ số lớn hơn 3329
    • Vector của Kyber và nhóm NIST chủ yếu xoay quanh đầu vào hợp lệ nên loại vector này thường xuyên được yêu cầu
    • Mọi giá trị từ 3329 đến 2¹²-1 và mọi vị trí hệ số đều được kiểm thử riêng
    • Các hệ số còn lại được chia sẻ để nén dữ liệu từ 1–3MiB xuống còn 12–28KiB
  • “Unlucky” vectors kiểm thử trường hợp cần số lần đọc XOF bất thường
    • Đây là các khóa công khai khiến SampleNTT phải đọc từ SHAKE-128 XOF ít nhất 575 byte, trong khi thông thường xác suất chỉ là 2⁻³⁸
    • Vector của Sophie còn được brute-force thêm để cần tối đa 591 byte
  • strcmp vectors khiến các triển khai dùng strcmp() trong ML-KEM.Decaps bị lỗi
    • Nếu có byte 0 khi so sánh ciphertext với đầu ra K-PKE.Encrypt trong lúc decapsulation, strcmp() có thể dừng so sánh quá sớm
  • Accumulated vectors được suy ra từ triển khai tham chiếu pq-crystals
    • Thay vì lưu đầu ra vector ngẫu nhiên 300MB, dự án tái tạo chúng trong lúc kiểm thử bằng RNG xác định rồi so sánh hash với giá trị kỳ vọng
    • Có thể tạo cả hash cho 1 triệu kiểm thử ngẫu nhiên, vượt quá 10k của triển khai tham chiếu
  • Trong nhiều kiểm thử được thêm sau đó, không phát hiện vấn đề nào ở filippo.io/mlkem768, còn negative vector đã có ít nhất một trường hợp báo cáo phát hiện lỗi ở một triển khai lớn

Kết quả hiệu năng

  • Hiệu năng không phải mục tiêu hàng đầu của gói này hay của các gói mật mã Go, nhưng vẫn phải đủ nhanh để hữu ích
  • ML-KEM đủ nhanh, và ngay cả triển khai đơn giản này cũng ở mức cạnh tranh với các triển khai P-256 và X25519 của Go đã được tối ưu bằng assembly
  • Việc so sánh nên dựa trên toàn bộ công việc mỗi bên phải làm trong quá trình thiết lập khóa
    • ECDH thực hiện 2 phép nhân vô hướng, trong đó có 1 lần với fixed basepoint
    • KEM yêu cầu một bên làm key generation và decapsulation, còn bên kia làm encapsulation
    • ECDH là đối xứng, còn thiết lập khóa ML-KEM là bất đối xứng
  • Trong benchmark, “Alice” thực hiện key generation và decapsulation, còn “Bob” thực hiện encapsulation
    • Decapsulation bao gồm cả một lần mã hóa đầy đủ để kiểm tra ciphertext đầu vào có khớp với kết quả hay không
    • Alice thực hiện mã hóa, giải mã và tạo khóa nên chậm hơn Bob
  • Kết quả là Bob nhanh ngang X25519 hoặc P-256, còn Alice chậm hơn chưa tới 2 lần
  • So với các triển khai ML-KEM nhanh như BoringSSL và libcrux, gói này mất khoảng gấp đôi thời gian

Số liệu benchmark và dư địa tối ưu

  • Các số liệu đo được như sau
    • trên macOS arm64, ECDH/P256-8 là 49.43µs, ECDH/X25519-8 là 77.46µs
    • trong cùng môi trường, RoundTrip/Alice-8 là 109.4µs, RoundTrip/Bob-8 là 56.19µs
    • trên Linux amd64, ECDH/P256-4 là 78.88µs, ECDH/X25519-4 là 115.6µs
    • trong cùng môi trường, RoundTrip/Alice-4 là 223.8µs, RoundTrip/Bob-4 là 114.7µs
  • Triển khai tuân theo các mẫu Go hiệu năng cao như giảm cấp phát heap
  • x/crypto/sha3 đã được làm lại để có thể dùng mà không cấp phát heap, nhưng hiện chưa được merge vì gây tác động tiêu cực trên Apple M2, và cũng chưa được tính vào benchmark ở trên
  • Dư địa tối ưu còn khá rõ ràng
    • Vì key generation và decapsulation lấy mẫu cùng một ma trận từ cùng giá trị, phía Alice có thể tiết kiệm khoảng 10% thời gian nếu lưu lại ma trận khi hai tác vụ diễn ra liên tiếp
    • Có thể tiếp tục giảm số lần copy ở đường đọc sha3
    • Sau đó sẽ cần tối ưu phần triển khai trường

Hỗ trợ Kyber v3 bằng triển khai ML-KEM

  • NIST đã thực hiện một vài thay đổi nhỏ so với bản nộp Kyber Round 3, được tóm tắt ở mục 1.3 của bản nháp FIPS
  • Có một số giao thức thử nghiệm dựa trên Kyber v3 hoặc “draft00”, bao gồm cả trao đổi khóa PQ TLS đang được triển khai rộng rãi
  • Có thể hỗ trợ Kyber v3 bằng triển khai ML-KEM mà không cần gói riêng
  • Một trong các thay đổi là thêm bước kiểm tra với trường hợp ngoại lệ mã hóa hệ số không chính quy trong khóa công khai
    • Triển khai đúng chuẩn sẽ không tạo ra các khóa như vậy, nên có thể từ chối theo đúng bản nháp FIPS
    • Hành vi này làm cho triển khai Kyber-on-ML-KEM có thể bị nhận diện, nhưng ngoài ra không gây hại
  • Một thay đổi khác là bỏ bước băm từng áp dụng cho đầu vào CSPRNG
    • Vì các byte đầu vào vốn đã ngẫu nhiên nên không bên nào có thể phân biệt khác biệt này
  • Thay đổi lớn nhất là việc băm ciphertext vào shared secret
    • Khác biệt này có thể cản trở khả năng tương thích
    • Có thể tạo shared secret Kyber bằng cách lấy shared secret K từ ML-KEM rồi áp dụng SHAKE-256(K || SHA3-256(c))[:32]
    • Không cần phá vỡ trừu tượng ML-KEM
  • Cả Kyber và ML-KEM đều băm secret và ciphertext để thực hiện implicit rejection trong decapsulation
    • Nếu áp dụng dẫn xuất khóa ở trên đè lên ML-KEM, ciphertext sẽ bị băm hai lần trong implicit rejection
    • Điều này không thành vấn đề vì đầu ra implicit rejection theo thiết kế là không thể dự đoán và không nhằm mục tiêu tương thích

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-02-02
Ý kiến trên Hacker News

  • Xin chào từ Kudelski Security. Việc này rất đúng lúc, vì gần đây chúng tôi đã phải ngừng một trong số rất ít thư viện mật mã kháng lượng tử khác dành cho Go
    Toàn bộ câu chuyện có tại https://research.kudelskisecurity.com/2024/02/01/the-kybersl...

    • Chẳng phải Kyber-512 đã bị các thành viên phía NSA của NIST cố ý làm yếu đi sao?

  • Tôi tò mò điện toán lượng tử thực sự đã tiến tới mức nào để những thứ như thế này trở nên cần thiết
    Có phải tình hình đã thành kiểu, thay vì thực sự có thứ gì đó xuất hiện như AI, người ta chỉ thay đổi định nghĩa để tung ra sản phẩm mới dưới một cái tên cũ?

    • Cách ngành mật mã xử lý mối đe dọa từ máy tính lượng tử khá đặc biệt. Lý do là một số dữ liệu và kết nối được mã hóa hôm nay không được phép có khả năng bị giải mã sau 30 năm, 50 năm nữa
      Vì vậy câu hỏi không phải là “máy tính lượng tử sắp xuất hiện chưa”, mà là “liệu trong nửa thế kỷ tới máy tính lượng tử có khả năng xuất hiện một cách hợp lý không”. Không có đồng thuận chính xác, nhưng câu trả lời không phải là “không”, nên hiện nay mới có xu hướng này
      Vì thế ta thấy nhiều tiến triển hơn ở trao đổi khóa PQC so với chữ ký. Việc xác minh chữ ký hôm nay sẽ không bị máy tính lượng tử sau 50 năm ảnh hưởng, nhưng mã hóa thì có
    • Đây không phải là chuyện ngăn chặn máy tính lượng tử hiện nay
      Rủi ro là kẻ tấn công có thể lưu bản mã của hôm nay rồi giải mã trong tương lai. Càng chuyển sớm sang mật mã an toàn trước lượng tử, ta càng để lại ít “bản mã tồn đọng” dễ bị tấn công trong tương lai
    • Nếu câu trả lời là “NSA đã chạy phân tích mật mã lượng tử trong production rồi và ECDH nên được xem là đã bị phá hoàn toàn”, thì người biết điều đó mà nói ra sẽ gặp rắc rối cực lớn
      Trên thực tế khả năng đó có vẻ thấp, nhưng câu hỏi này ở một mức độ nào đó rất khó trả lời. Hiện tại đây không phải là mối đe dọa đã biết, nhưng việc nên nhìn nhận tiềm năng của nó với mức độ hoang tưởng ra sao là chuyện chủ quan
    • Khoảng 2 năm gần đây, NIST đã chọn một số thuật toán mật mã hậu lượng tử, và sau đó các triển khai cũng ngày càng nhiều hơn. Điện toán lượng tử vẫn còn xa, nhưng có vẻ thái độ là “bắt đầu từ bây giờ thì có hại gì?”
      Tôi không chắc, nhưng tôi đoán mật mã đường cong elliptic cũng đã có khá nhiều triển khai từ rất lâu trước khi được dùng phổ biến. Ai đã trải qua thời đó nếu thấy tôi sai thì xin sửa giúp
    • Để máy tính lượng tử phá RSA-2048, chất lượng của qubit vật lý hiện nay cần tăng khoảng 10 lần, còn số lượng cần tăng 10.000 lần. Đây là các con số rất ước chừng
      Cột mốc chính tiếp theo cần theo dõi là qubit logic có độ trung thực tốt hơn 1000 lần so với các qubit vật lý cấu thành nó. Khi điều đó xuất hiện, đó sẽ là tín hiệu rằng chất lượng qubit vật lý đã đủ và giờ chỉ cần bắt đầu mở rộng số lượng

  • Với thảo luận liên quan, sách nhập môn triển khai hệ thống mật mã dựa trên phiên bản Go mới nhất của John Arundel có thể hữu ích. Phần cuối có nhắc thoáng qua về mật mã hậu lượng tử, và khi NIST PQ được chuẩn hóa, có thể sau này John sẽ cập nhật sách để đưa thư viện này vào
    Explore Go: Cryptography (ấn bản Go 1.22):
    https://bitfieldconsulting.com/books/crypto

  • Xin sửa nếu tôi sai, nhưng nếu được viết bằng Go thuần thì chẳng phải nó sẽ dễ bị tấn công kênh kề về thời gian/điện năng sao?

    • Khó có thể nói Go dễ bị hơn C, thậm chí có thể là ít hơn. Khác biệt là Go có một compiler chính và thường không tối ưu hóa quá đà, trong khi với C bạn phải dùng các mẹo ngày càng phức tạp để ngăn compiler nhận ra ý đồ rồi biến thành các nhánh thời gian biến thiên hiệu quả hơn
      Triển khai này được viết để tránh các đường đi mã phụ thuộc vào giá trị bí mật. Kênh kề điện năng cần truy cập vật lý nằm ngoài mô hình đe dọa của Go
    • Có ghi rằng “mọi phép toán cốt lõi đều được thực hiện trong thời gian hằng định”
      Lẽ ra tôi nên bấm theo liên kết tới tài liệu dự án; có vẻ họ đã cân nhắc phần này
    • Có ngôn ngữ nào miễn nhiễm với tấn công kênh kề điện năng không? Bản thân ý tưởng đó nghe đã không hợp lý
      Còn về tấn công timing, tôi không rõ vì sao Go lại khiến kênh kề thời gian dễ bị khai thác hơn các ngôn ngữ khác

  • Có ai biết triển khai cho các ngôn ngữ khác như Java, C# không?

  • Việc nó cũng có thể hoạt động với draft00/kyber v3 thật hay
    Để hỗ trợ chế độ Kyber 90’s nhanh không dùng SHA-3 thì sẽ khó đến mức nào? Có lẽ trong trường hợp đó sẽ phải phá vỡ tầng trừu tượng

    • Muốn đổi hàm băm thì cần fork. Triển khai này chỉ dùng khoảng 20% thời gian CPU cho SHA-3, nên lợi ích không lớn
      Nếu tối ưu triển khai trường thì tỷ lệ đó sẽ tăng, nhưng có lẽ vẫn khó đủ để đáng dùng một chế độ chưa được chuẩn hóa và ít được kiểm thử hơn

  • Không liên quan lắm, nhưng Filo này, bảng syscall 32-bit vẫn còn ghi ‘coming soon’ đấy :')

    • Haha, công nhận. Mỗi lần tôi định sửa trang đó, phạm vi lại cứ phình to ra, kiểu như phải làm sao để tự động sinh nó từ mã nguồn kernel bằng CI ấy :)

  • Tôi không có khả năng đánh giá chất lượng của thuật toán hay phần triển khai này, nhưng tôi rất thích việc dùng Unicode trong tên biến
    ρ, σ := G[:32], G[32:]
    Không hiểu sao trông tốt hơn hẳn so với "rho", "sigma"

    • Khó mà đồng ý. Nhìn thì ngầu, nhưng trong code thực tế tôi không muốn thấy lắm
      Trước hết, tôi không biết phải nhập chúng bằng bàn phím thế nào. Và đa số mọi người có lẽ cũng không biết tên của các ký hiệu này. Tất nhiên những người đọc đoạn code đó có khả năng biết cao hơn, nhưng tôi không cho rằng đó là code thân thiện
      Tính rõ ràng là cốt lõi, và "rho" hay "sigma" khá rõ ràng. Hơn nữa, nếu có cả hằng số "n" và hằng số "η" thì rất dễ gây nhầm lẫn
    • Hoàn toàn không thích. Những ký tự không có trên bàn phím của tôi tạo thêm bước nhập liệu, gây quá nhiều ma sát. Tôi còn có cảm giác sẽ đọc nhầm ρ thành p rồi gặp lỗi biên dịch kỳ lạ
      Thế còn gắn dấu trọng âm hay cedilla vào chữ cái thì sao? Chỉ làm tăng độ phức tạp. Tốt hơn là nên bám vào mẫu số chung thấp nhất
    • Go có cho phép chỉ số dưới Unicode trong tên biến không?
      Trong các ngôn ngữ tôi thử kiểm tra, Perl, Python, JavaScript không cho phép trên Chrome và Firefox, còn PHP thì cho phép

  • Người làm ra cái này cũng chính là người đã làm https://github.com/FiloSottile/age
    Tôi thật sự thích công cụ này

    • Tiếc là nó không tích hợp sẵn khả năng phủ nhận hợp lý. Ý là phải mã hóa ít nhất hai tệp, và tùy vào khóa nào được cung cấp mà có thể giải mã một trong số đó
      Điều này có vẻ là điểm yếu bảo mật của hầu hết các công cụ kiểu này. Nếu chỉ có một khóa khả dĩ, người cầm búa có thể buộc bạn khai khóa đó ra. Nhưng nếu không biết có bao nhiêu khóa, bạn có thể đưa ra vài khóa và hy vọng kẻ tấn công bỏ đi trong khi tệp thực sự cần bảo vệ vẫn được giấu
    • Tôi muốn thích công cụ này, nhưng nó thiếu tài liệu hướng dẫn hoặc tutorial giải thích cách dùng điển hình. Tôi không nói về cách dùng dòng lệnh, mà muốn biết nên quản lý và phân phối khóa thế nào, cần cẩn trọng điều gì
      Toàn bộ tầng xã hội nằm trên lớp kỹ thuật này đối với tôi vẫn chưa rõ ràng. Giá mà có một câu chuyện ví dụ với Alice và Bob
    • Age ổn, nhưng có vẻ đã chững lại. Bản phát hành cuối cùng là năm 2022, và không dùng hàm dẫn xuất khóa dựa trên mật khẩu hiện đại hơn như argon
      Nếu bạn đang tìm thứ được thiết kế để lưu trữ/chia sẻ bí mật, có thể xem rot: https://github.com/candiddev/rot

  • Đặc tả: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf cũng được liên kết trong bài viết