filippo.io/mlkem768: Go ecosystem के लिए quantum-resistant cryptography

 (words.filippo.io)
1 पॉइंट द्वारा GN⁺ 2024-02-02 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • filippo.io/mlkem768 NIST standardization process में चल रहे ML-KEM-768 को pure Go में implement करता है, जिससे Go ecosystem में quantum-resistant key exchange का मूल्यांकन किया जा सकता है
  • यह लगभग 500 lines of code, 200 lines of comments, और 650 lines of tests से बना है, और golang.org/x/crypto/sha3 के अलावा कोई dependency नहीं है, इसलिए इसे Go standard library के internal package के रूप में शामिल करना आसान है
  • pq-crystals reference implementation को port करने के बजाय इसे सीधे FIPS 203 specification के अनुसार लिखा गया है, ताकि यह verify किया जा सके कि केवल spec के आधार पर interoperable implementation बनाई जा सकती है या नहीं
  • सबसे कठिन क्षेत्र compression·decompression और constant-time operations हैं, और Barrett reduction का उपयोग करके reference implementation family में हो सकने वाले variable-time DIV instruction के जोखिम से बचा गया है
  • performance optimization प्राथमिक लक्ष्य नहीं है, फिर भी Bob path Go के X25519·P-256 के समान है और Alice path भी 2x से कम है, इसलिए यह simple implementation होने के बावजूद practical speed दिखाता है

ML-KEM-768 का pure Go implementation

  • filippo.io/mlkem768 ML-KEM-768 का pure Go implementation है, जिसमें correctness और readability को प्राथमिकता दी गई है
  • ML-KEM पहले Kyber के नाम से जाना जाता था, और यह NIST standardization process में मौजूद quantum-resistant key exchange mechanism है
  • package लगभग 500 lines of code, 200 lines of comments, और 650 lines of tests से बना है
  • इसकी एकमात्र dependency golang.org/x/crypto/sha3 है
  • लक्ष्य इसे Go standard library में upstream करना है, और शुरुआत में इसे opt-in crypto/tls experiment में इस्तेमाल होने वाले internal-only package के रूप में योजना बनाई गई है

FIPS 203 को ज्यों का त्यों follow करने का implementation approach

  • यह implementation pq-crystals reference library को port नहीं करता, बल्कि किसी दूसरे codebase को विस्तार से पढ़े बिना शुरू से लिखा गया है
  • मुख्य लक्ष्य यह देखना था कि क्या केवल specification के आधार पर interoperable implementation बनाई जा सकती है
  • FIPS 203 document detailed pseudocode, complete definitions, और consistent type information देता है, इसलिए यह implementation guide के रूप में उपयुक्त था
  • function names, variable names, और operation order को review और learning आसान बनाने के लिए FIPS specification के जितना संभव हो उतना करीब रखा गया है
  • ML-KEM implementation के लिए जरूरी mathematical background को Enough Polynomials and Linear Algebra to Implement Kyber में अलग से व्यवस्थित किया गया है

compression·decompression और constant-time implementation

  • तीन core implementation tasks बाकी थे
    • prime 3329 के लिए modular arithmetic implement करना
    • [0, 3329) values को [0, 2ᵈ) में map करके वापस लाने वाले compression·decompression functions implement करना
    • constant-time operations की guarantee देना
  • modular arithmetic अपेक्षाकृत आसान था, क्योंकि RSA और elliptic-curve implementations का अनुभव पहले से था, और छोटे prime ने implementation को सरल बना दिया
  • compression और decompression सबसे कठिन हिस्सा था
    • specification इसे fractions और rounding rules के जरिए abstract तरीके से define करती है
    • actual implementation में इसे constant-time arithmetic और bit operations से handle करना पड़ता है
  • reference implementation और उसके कई ports ऐसी division का उपयोग करते थे जो compiler optimization और platform के अनुसार variable-time DIV instruction बन सकती थी
  • यह package शुरुआत से Barrett reduction का उपयोग करता है, इसलिए यह इस समस्या से प्रभावित नहीं हुआ, और BoringSSL भी यही approach अपनाता है

केवल ML-KEM-768 को target करने का कारण

  • implementation, ML-KEM के तीन security levels -512, -768, -1024 में से केवल ML-KEM-768 को target करता है
  • Kyber team नए cryptanalysis के खिलाफ अधिक conservative security margin के लिए -512 की बजाय -768 उपयोग करने की recommendation देती है
  • -1024 को 256-bit security level जैसे कारणों, यानी compliance और strength matching के लिए एक option के रूप में समझाया गया है
  • क्योंकि अधिकांश experimental या standardizing protocols ML-KEM-768 पर एकत्रित हो चुके हैं, इसलिए एक ही level को target करने से cost लगभग नहीं बढ़ती
  • single-targeting, moving parts को कम करके readability, security, और performance के लिए फायदेमंद है
    • उदाहरण के लिए 1·4·10·12-bit integer serialization को एक generic encoder से handle करने के बजाय dedicated encoder·decoder में बांटा गया है
    • केवल ML-KEM-768 को target करने के कारण 5-bit और 11-bit encoding implement करने की जरूरत नहीं पड़ी

test strategy और public test vectors

  • tests, इस package की security assurance strategy में readability के बाद दूसरा सबसे महत्वपूर्ण स्तंभ हैं
  • basic tests में key generation, encapsulation, decapsulation roundtrip, और 95% से अधिक test coverage शामिल है
  • अतिरिक्त test coverage में यह शामिल है
    • NIST और अन्य implementations से मिले test vectors के साथ interoperability check
    • 3329 modular addition·subtraction·multiplication के सभी input combinations की variable-time तरीके से निकाले गए expected values से तुलना
    • compression·decompression का math/big.Rat baseline के खिलाफ exhaustive testing
    • यह verify करना कि precomputed constants definitions से मेल खाते हैं
    • सभी function inputs पर length बहुत लंबी या बहुत छोटी होने पर सही errors आते हैं या नहीं, इसकी जाँच
    • Sophie Schmieg द्वारा दिए गए और भविष्य में Wycheproof में शामिल होने वाले test vectors चलाना
  • इसके अपने test vectors को अन्य implementations में भी reuse किया जा सके, इसके लिए उन्हें CCTV project के हिस्से के रूप में public किया गया है
  • CCTV vectors में intermediate values शामिल हैं, जिनसे हर intermediate step और partial algorithm को test और debug किया जा सकता है

special test vectors जिन errors को पकड़ते हैं

  • Negative test vectors 3329 से बड़े coefficients वाली invalid encapsulation keys प्रदान करते हैं
    • Kyber और NIST team के vectors सामान्यतः valid inputs पर केंद्रित हैं, इसलिए ऐसे vectors की अक्सर मांग होती है
    • 3329 से 2¹²-1 तक के सभी values और हर coefficient position को अलग-अलग test किया जाता है
    • बाकी coefficients को share करके 1–3MiB data को 12–28KiB तक compress किया गया है
  • “Unlucky” vectors उन cases को test करते हैं जहाँ XOF reads असामान्य रूप से बहुत अधिक चाहिए होते हैं
    • SampleNTT में SHAKE-128 XOF से 575 bytes से अधिक पढ़ना पड़ने वाली public key, जो सामान्यतः probability 2⁻³⁸ से होती है
    • Sophie के vectors को और brute-force करके अधिकतम 591 bytes तक की आवश्यकता वाला बनाया गया है
  • strcmp vectors ML-KEM.Decaps में strcmp() इस्तेमाल करने वाली implementations को fail करा देते हैं
    • decapsulation में ciphertext और K-PKE.Encrypt output की तुलना करते समय यदि 0 byte मौजूद हो तो strcmp() comparison को जल्दी रोक सकता है
  • Accumulated vectors reference pq-crystals implementation से derived हैं
    • 300MB random vector output store करने के बजाय, deterministic RNG के साथ test के दौरान उन्हें regenerate करके hash की expected value से तुलना की जाती है
    • reference implementation के 10k से आगे बढ़कर 10 लाख random test hashes भी बनाए जा सकते हैं
  • completion के बाद जोड़े गए कई अतिरिक्त tests में भी filippo.io/mlkem768 में कोई समस्या नहीं मिली, और negative vectors ने प्रमुख implementations की कमियों को पकड़ा है, ऐसा कम-से-कम 1 reported case है

performance results

  • performance इस package या Go crypto packages का प्राथमिक लक्ष्य नहीं है, लेकिन यह इतना तेज होना चाहिए कि उपयोगी रहे
  • ML-KEM पर्याप्त रूप से तेज है, और यह simple implementation भी assembly-optimized Go P-256 और X25519 implementations के साथ प्रतिस्पर्धा करने लायक है
  • comparison key setup में हर side द्वारा किए जाने वाले total work के आधार पर होना चाहिए
    • ECDH, fixed basepoint सहित scalar multiplication 2 बार करता है
    • KEM में एक side key generation और decapsulation करती है, और दूसरी side encapsulation करती है
    • ECDH symmetric है, लेकिन ML-KEM key setup asymmetric है
  • benchmark में “Alice” key generation और decapsulation करती है, जबकि “Bob” encapsulation करता है
    • decapsulation में input ciphertext और result के मेल की जाँच के लिए पूरा encryption शामिल होता है
    • Alice encryption, decryption, और key generation करती है, इसलिए Bob से अधिक समय लेती है
  • परिणामस्वरूप Bob, X25519 या P-256 जितना तेज है, और Alice उससे 2x से कम है
  • BoringSSL और libcrux जैसी तेज ML-KEM implementations की तुलना में यह package लगभग 2x समय लेता है

benchmark numbers और optimization की गुंजाइश

  • measured numbers इस प्रकार हैं
    • macOS arm64 पर ECDH/P256-8 49.43µs है, ECDH/X25519-8 77.46µs है
    • उसी environment में RoundTrip/Alice-8 109.4µs है, RoundTrip/Bob-8 56.19µs है
    • Linux amd64 पर ECDH/P256-4 78.88µs है, ECDH/X25519-4 115.6µs है
    • उसी environment में RoundTrip/Alice-4 223.8µs है, RoundTrip/Bob-4 114.7µs है
  • implementation, heap allocations कम करने जैसे high-performance Go patterns को follow करता है
  • x/crypto/sha3 को heap allocation के बिना इस्तेमाल किया जा सके, इसके लिए rework किया गया था, लेकिन Apple M2 पर इसका नकारात्मक असर पड़ा, इसलिए इसे अभी merge नहीं किया गया है और ऊपर दिए benchmarks में भी शामिल नहीं किया गया है
  • optimization की बची हुई गुंजाइश स्पष्ट है
    • key generation और decapsulation दोनों एक ही value से matrix sample करते हैं, इसलिए Alice side पर जब ये दोनों operations लगातार हों तो matrix को store करके लगभग 10% time saving की जा सकती है
    • sha3 read path में copies घटाने की संभावना है
    • उसके बाद field implementation optimization की जरूरत होगी

ML-KEM implementation से Kyber v3 support करना

  • NIST ने Kyber Round 3 submission में कुछ छोटे बदलाव किए, जिनका सार FIPS draft section 1.3 में दिया गया है
  • Kyber v3 या “draft00” पर आधारित कुछ experimental protocols हैं, जिनमें प्रमुख deployed PQ TLS key exchange भी शामिल है
  • अलग package के बिना ML-KEM implementation से Kyber v3 support किया जा सकता है
  • बदलावों में से एक public key में non-canonical coefficient encoding के exception case पर validation जोड़ना है
    • सही implementations ऐसी keys बनाती नहीं हैं, इसलिए FIPS draft के अनुसार उन्हें reject किया जा सकता है
    • यह behavior Kyber-on-ML-KEM implementation को distinguishable बनाता है, लेकिन इसके अलावा हानिकारक नहीं है
  • दूसरा बदलाव CSPRNG input पर लागू होने वाले hashing step को हटाना है
    • क्योंकि input bytes random होते हैं, कोई भी party इस अंतर को पहचान नहीं सकती
  • सबसे बड़ा बदलाव shared secret में ciphertext को hash करने के व्यवहार का है
    • यह अंतर interoperability को रोक सकता है
    • ML-KEM से shared secret K बनाने के बाद SHAKE-256(K || SHA3-256(c))[:32] लागू करके Kyber shared secret बनाया जा सकता है
    • इससे ML-KEM abstraction टूटता नहीं है
  • Kyber और ML-KEM दोनों decapsulation में implicit rejection के लिए secret और ciphertext को hash करते हैं
    • ML-KEM के ऊपर ऊपर वाला key derivation लागू करने पर implicit rejection में ciphertext दो बार hash होता है
    • implicit rejection output design के अनुसार unpredictable होता है और interoperability target नहीं होता, इसलिए यह समस्या नहीं है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-02-02
Hacker News टिप्पणियां

  • Kudelski Security की ओर से नमस्कार। हाल ही में Go के लिए मौजूद quantum-resistant cryptography libraries में से लगभग इकलौती दूसरी library को बंद करना पड़ा था, इसलिए यह बहुत सही समय पर आया है
    पूरी कहानी https://research.kudelskisecurity.com/2024/02/01/the-kybersl... पर है

    • क्या Kyber-512 को NIST के NSA-पक्ष के members ने जानबूझकर कमजोर नहीं किया था?

  • जिज्ञासा है कि quantum computing असल में किस स्तर तक पहुंच चुकी है कि ऐसी चीज़ की जरूरत पड़ने लगी
    क्या AI की तरह सच में कुछ सामने आया है, या फिर पुराने नाम के तहत नए products लॉन्च करने के लिए परिभाषा ही बदल दी गई है?

    • Cryptography का quantum computer threat से निपटने का तरीका अलग है। क्योंकि आज encrypted कुछ data और connections ऐसे हैं जिन्हें 30 या 50 साल बाद भी decrypt नहीं हो पाना चाहिए
      इसलिए सवाल “क्या quantum computers जल्द आ रहे हैं” नहीं, बल्कि “क्या अगले आधे शतक में quantum computers का आना plausible है” बन जाता है। सटीक consensus नहीं है, लेकिन जवाब “नहीं” भी नहीं है, इसलिए अभी यह trend दिख रहा है
      इसी वजह से signatures की तुलना में PQC key exchange में ज्यादा प्रगति दिखती है। आज की signature verification पर 50 साल बाद के quantum computer का असर नहीं पड़ेगा, लेकिन encryption पर पड़ेगा
    • बात मौजूदा quantum computers को रोकने की नहीं है
      जोखिम यह है कि attacker आज का ciphertext store करके रखे और भविष्य में उसे decrypt कर सके। जितनी जल्दी quantum-safe cryptography पर switch करेंगे, भविष्य के attacks के लिए vulnerable “backlog ciphertext” उतना ही कम छोड़ा जाएगा
    • अगर जवाब यह हो कि “NSA पहले से production में quantum cryptanalysis चला रहा है और ECDH को पूरी तरह टूटा हुआ मानना चाहिए”, तो जो व्यक्ति यह जानता है, उसके बोलते ही वह भारी मुसीबत में पड़ जाएगा
      असल में इसकी संभावना कम लगती है, लेकिन इस सवाल का जवाब देना कुछ हद तक कठिन है। फिलहाल यह कोई known threat नहीं है, लेकिन इसकी संभावना को लेकर कितना paranoid होना है, यह subjective है
    • पिछले करीब 2 सालों में NIST ने कुछ post-quantum cryptography algorithms तय किए हैं, और उसके बाद implementations भी धीरे-धीरे बढ़ रही हैं। Quantum computing अभी दूर है, लेकिन रवैया ऐसा लगता है: “अभी शुरू करने में नुकसान क्या है?”
      पक्का नहीं कह सकता, लेकिन लगता है कि elliptic-curve cryptography भी व्यापक रूप से इस्तेमाल होने से काफी पहले implement हो चुकी रही होगी। अगर उस दौर से गुजरे किसी व्यक्ति को यह गलत लगे तो सुधार दें
    • Quantum computer को RSA-2048 तोड़ने के लिए मौजूदा physical qubits की quality लगभग 10 गुना और quantity 10,000 गुना बढ़ानी होगी। ये बहुत मोटे आंकड़े हैं
      अगला मुख्य milestone देखने लायक होगा: ऐसा logical qubit जिसकी fidelity उसे बनाने वाले physical qubits से 1000 गुना बेहतर हो। अगर वह आ गया, तो यह संकेत होगा कि physical qubit quality पर्याप्त है और अब बस quantity scale करना शुरू करना है

  • संबंधित चर्चा में John Arundel की latest Go version पर आधारित cryptosystems implementation की introductory book मददगार हो सकती है। आखिरी section में post-quantum cryptography का संक्षिप्त जिक्र है, और NIST PQ standardize होने के बाद John शायद बाद में इस library को जोड़कर book update कर सकते हैं
    Explore Go: Cryptography (Go 1.22 edition):
    https://bitfieldconsulting.com/books/crypto

  • अगर मैं गलत हूं तो सुधारें, लेकिन अगर यह pure Go में लिखा गया है, तो क्या यह timing/power side-channel attacks के लिए vulnerable नहीं हो जाएगा?

    • Go को C से ज्यादा vulnerable मानना मुश्किल है, बल्कि शायद कम हो सकता है। फर्क यह है कि Go में एक major compiler है और वह आम तौर पर बहुत aggressive optimization नहीं करता, जबकि C में compiler आपकी मंशा पहचानकर उसे ज्यादा efficient variable-time branch में न बदल दे, इसके लिए increasingly complex tricks अपनाने पड़ते हैं
      यह implementation secret values पर निर्भर code paths से बचने के लिए लिखा गया है। Physical access की जरूरत वाले power side-channels Go के threat model से बाहर हैं
    • लिखा है कि “सभी core operations constant time में किए जाते हैं”
      मुझे project documentation तक links follow करने चाहिए थे; लगता है वे इस हिस्से पर ध्यान दे रहे हैं
    • क्या कोई ऐसी language है जो power side-channel attacks से immune हो? यह विचार ही बेतुका लगता है
      Timing attacks के मामले में भी, मुझे समझ नहीं आता कि Go दूसरी languages की तुलना में timing side-channels के लिए ज्यादा vulnerable क्यों होगा

  • क्या किसी को Java, C# जैसी दूसरी languages के लिए implementations पता हैं?

    • यह इस पर निर्भर करता है कि आप general implementation की बात कर रहे हैं या “from scratch खुद implement” करने की
      general implementations की list यहां है: https://pq-crystals.org/kyber/software.shtml
    • OpenQuantumSafe का liboqs कैसा है? इसमें अब तक प्रस्तावित अधिकतर PQC primitives की implementations शामिल हैं
      https://github.com/open-quantum-safe/liboqs

  • यह अच्छा है कि यह draft00/kyber v3 के साथ भी काम कर सकता है
    SHA-3 के बिना fast Kyber 90’s mode support करना कितना मुश्किल होगा? शायद उस स्थिति में abstraction तोड़नी पड़ेगी

    • Hash बदलने के लिए fork की जरूरत होगी। यह implementation CPU time का सिर्फ करीब 20% SHA-3 पर खर्च करती है, इसलिए फायदा बहुत बड़ा नहीं होगा
      Field implementation optimize करने पर वह ratio बढ़ेगा, लेकिन शायद इतना नहीं कि non-standardized और कम-tested mode इस्तेमाल करना worthwhile हो

  • संबंधित नहीं है, लेकिन Filo, 32-bit system call table अभी भी ‘coming soon’ ही है न :')

    • हाहा, मानता हूं। हर बार जब उस page को ठीक करने के बारे में सोचता हूं, तो बात इस तरह scope में बढ़ती चली जाती है कि kernel source से CI के जरिए इसे auto-generate कराया जाए :)

  • मेरे पास इस algorithm या implementation की quality को आंकने की क्षमता नहीं है, लेकिन variable names में Unicode का इस्तेमाल मुझे बहुत पसंद है
    ρ, σ := G[:32], G[32:]
    किसी तरह "rho", "sigma" देखने से यह काफी बेहतर लगता है

    • सहमत होना मुश्किल है। देखने में cool है, लेकिन असली code में मैं इसे ज्यादा देखना नहीं चाहूंगा
      सबसे पहले, keyboard से इसे type कैसे करना है, मुझे नहीं पता। और ज्यादातर लोगों को इन symbols के नाम भी नहीं पता होंगे। बेशक, जो लोग वह code देख रहे होंगे उन्हें पता होने की संभावना ज्यादा है, लेकिन मुझे यह friendly code नहीं लगता
      clarity सबसे अहम है और "rho" या "sigma" काफी clear हैं। ऊपर से अगर constant "n" और constant "η" भी साथ में हों, तो confusion पैदा करने के लिए बिल्कुल सही है
    • मुझे बिल्कुल पसंद नहीं। मेरे keyboard पर जो characters नहीं हैं, उन्हें input करने में extra steps लगते हैं और friction बहुत बढ़ जाता है। साथ ही लगता है कि मैं ρ को p समझकर कोई अजीब compile error देख बैठूंगा
      characters पर accent marks या cedilla लगाने के बारे में क्या ख्याल है? इससे बस complexity बढ़ती है। सबसे common denominator के साथ चलना बेहतर है
    • क्या Go variable names में Unicode subscript allow करता है?
      जिन languages में मैंने check किया, उनमें Perl, Python, JavaScript ने Chrome और Firefox में allow नहीं किया, और PHP ने allow किया

  • इसे बनाने वाला वही व्यक्ति है जिसने https://github.com/FiloSottile/age भी बनाया है
    यह tool मुझे सच में बहुत पसंद है

    • अफसोस है कि इसमें plausible deniability built-in नहीं है। मेरा मतलब है कि कम से कम दो files encrypt होनी चाहिए, और आप कौन-सी key देते हैं उसके आधार पर उनमें से एक decrypt हो सके
      इस तरह के ज्यादातर tools की यह security weakness लगती है। अगर possible key सिर्फ एक है, तो हथौड़ा लिए व्यक्ति आपसे वह key उगलवा सकता है। लेकिन अगर keys की संख्या पता न हो, तो आप कुछ keys दे सकते हैं और असली protected file छिपाए रखकर उम्मीद कर सकते हैं कि attacker चला जाए
    • मैं इस tool को पसंद करना चाहता हूं, लेकिन typical usage समझाने वाला manual या tutorial कम है। मैं command-line usage की बात नहीं कर रहा, बल्कि यह जानना चाहता हूं कि keys को कैसे manage और distribute करना चाहिए, किन बातों से सावधान रहना चाहिए
      technology के ऊपर मौजूद पूरी social layer मेरे लिए unclear है। Alice और Bob वाले example story हो तो अच्छा रहेगा
    • Age ठीक है, लेकिन stagnant लगता है। आखिरी release 2022 में था, और यह argon जैसी ज्यादा modern password-based key derivation function का इस्तेमाल नहीं करता
      अगर आप secret storage/sharing के लिए design की गई चीज खोज रहे हैं, तो rot भी देख सकते हैं: https://github.com/candiddev/rot

  • specification: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf article में भी link है