Shamir का secret sharing कैसे काम करता है

• Shamir secret sharing में किसी secret को कई हिस्सों में बाँटा जाता है, और वह तभी recover होता है जब threshold या उससे ज़्यादा हिस्से इकट्ठा हों; इससे कम हिस्सों से कोई जानकारी सामने नहीं आती
• यह company master key, family account recovery, और team backup जैसे मामलों में उपयोगी है, जहाँ पूरे secret की ज़िम्मेदारी एक व्यक्ति को देना कठिन हो और कुछ हिस्से खो जाने पर भी recovery चाहिए हो
• इसका मुख्य मॉडल secret को polynomial के 0 बिंदु के value के रूप में छिपाता है, और हर share को curve पर मौजूद एक point के रूप में बाँटता है
• threshold k के लिए degree k - 1 का polynomial इस्तेमाल होता है; दो shares एक line, तीन shares एक parabola, और चार shares एक cubic curve के बराबर होते हैं
• Ente Legacy Kit इस तरीके को एक layer के रूप में इस्तेमाल करता है, ताकि card खुद permanent recovery key न बन जाए और जारी किए गए cards को revoke किया जा सके

---

secret को points और polynomials में बाँटने का तरीका

• यह तरीका Adi Shamir ने 1979 में प्रकाशित किया था, और इसकी सबसे अहम बात सिर्फ यह नहीं है कि इसे “तोड़ना मुश्किल” है, बल्कि यह है कि अगर ज़रूरी संख्या में shares न हों तो कोई जानकारी बिल्कुल भी प्रकट नहीं होती
• अलग-अलग दो points मिलकर ठीक एक line तय करते हैं, लेकिन अगर सिर्फ एक point हो तो उस point से गुजरने वाली lines अनंत होती हैं, और हर line vertical axis को अलग जगह पर काटती है
• अगर secret संख्या 7 हो, तो इस value को उस जगह छिपाया जा सकता है जहाँ line vertical axis से मिलती है
• slope secret खुद नहीं होती, बल्कि secret को छिपाने के लिए randomness का काम करती है
• अगर हर व्यक्ति को line पर मौजूद एक point दे दिया जाए, तो किसी एक व्यक्ति के पास मौजूद सिर्फ एक point से अनंत संभव lines बनती हैं, और वे सब अलग-अलग secrets के साथ compatible होती हैं
• दो points को मिलाते ही line तय हो जाती है, और उस line का 0 पर value पढ़कर secret recover किया जा सकता है
• यह संरचना 2-of-n secret sharing scheme है; points जितने चाहें बनाए जा सकते हैं, लेकिन किसी भी दो points से line recover की जा सकती है
• threshold बढ़ने पर higher-degree curves का इस्तेमाल होता है
  • parabola को तय करने के लिए तीन points चाहिए, इसलिए अगर secret को उस जगह छिपाया जाए जहाँ parabola vertical axis से मिलती है, तो किसी भी तीन shares से recovery संभव है और दो shares से नहीं
  • सामान्य रूप से threshold k के लिए degree k - 1 का polynomial इस्तेमाल होता है
  • 2 shares एक line, 3 shares एक parabola, और 4 shares एक cubic curve के बराबर होते हैं
  • असली implementation graph paper की जगह finite field arithmetic का इस्तेमाल करती है, लेकिन संरचना वही रहती है: secret 0 पर value होता है, random coefficients उसे छिपाते हैं, और हर share polynomial पर एक point होता है
  • यह बात महत्वपूर्ण है कि shares कम होने पर secret निकालना सिर्फ कठिन नहीं होता, बल्कि हर संभव secret अब भी equally possible बना रहता है

Ente Legacy Kit और संदर्भ सामग्री

• Ente इस विचार का उपयोग Legacy Kit में करता है
• लक्ष्य सिर्फ secret को बाँटना नहीं है, बल्कि recovery को संभव रखते हुए यह भी सुनिश्चित करना है कि बाँटे गए shares permanent recovery key न बन जाएँ
• Legacy Kit Shamir scheme को एक बड़े flow के भीतर एक layer के रूप में इस्तेमाल करता है
• card में recovery key खुद नहीं होती; पहले एक अलग secret को local रूप से reconstruct किया जाता है, फिर server-mediated recovery में भाग लिया जाता है
• इस संरचना की वजह से जारी किए गए cards को revoke किया जा सकता है, और खोए हुए cards स्थायी बोझ नहीं बनते
• संदर्भ सामग्री
  • Adi Shamir का “How to Share a Secret”
  • Bruce Schneier का “Sharing Secrets Among Friends”
  • Max Levchin की PayPal कहानी
  • Ente source code

[GN⁺]

Hacker News की राय

• मैंने इस विषय पर मास्टर थीसिस लिखी थी। मैंने एक ऐप बनाया था जो Dropbox, Google Drive, OneDrive जैसे कई सामान्य storage providers में डेटा को बाँटकर स्टोर करता था, और encryption को सपोर्ट करने के लिए secret sharing का उपयोग करता था
  फायदे यह थे कि provider अब डेटा पढ़ नहीं सकते थे, सिर्फ 2 जगहें चालू रहने पर भी काम हो जाता था इसलिए अतिरिक्त redundancy मिलती थी, और दूसरे secure storage apps की तरह master password भूल जाने पर सब खत्म नहीं हो जाता था क्योंकि मौजूदा account recovery प्रक्रिया को वैसे ही इस्तेमाल किया जा सकता था

  • आइडिया अच्छा लगता है, जानना चाहूँगा कि क्या यह बाद में किसी product या open source app तक पहुँचा

• मैं सोच रहा हूँ कि क्या कई key/value pairs को एक ही ciphertext में मिलाने का कोई तरीका है। सिर्फ उन्हें जोड़ देने या output size को बहुत बढ़ा देने के बिना, ऐसा कि इस स्कीम में जानकारी डालने वाले सभी लोग वही encrypted blob स्टोर करें लेकिन अपनी-अपनी key से अलग-अलग value decrypt कर सकें
  इससे लोग एक-दूसरे के backup की तरह काम कर सकते हैं, और साथ ही क्या स्टोर है इस बारे में plausible deniability भी बनी रहे

• मैंने अपनी मास्टर थीसिस में Shamir secret sharing को mesh network पर लागू किया था। विचार यह था कि अगर mesh का कोई एक node attacker के कब्जे में चला जाए और उस node का secret निकाल भी लिया जाए, तब भी पूरी encryption को तोड़ना असंभव रहे

• हमारी टीम इस तकनीक का इस्तेमाल सहायक secret store के passphrase को “लोकतांत्रिक रूप से सुरक्षित” तरीके से बाँटने के लिए करती है। उस सहायक store में primary secret store तक पहुँचने का तरीका रखा होता है
  https://packages.debian.org/trixie/ssss एक ठीक-ठाक और काफी सहज implementation है

• Shamir की वजह से मैं एक बार बड़ी मुसीबत से बच गया था। मुझे लगभग भुला दिया गया backup तुरंत restore करना था, और मैं उस समय इस्तेमाल किया गया random password फिर से बना सका
  अच्छा हुआ कि मैंने “सावधानी के लिए” वितरित हिस्से परिवार में बाँट रखे थे

• “इसकी उपयोगी बात यह नहीं है कि बहुत कम हिस्सों के साथ secret की गणना करना कठिन है। बल्कि यह है कि बहुत कम हिस्सों के साथ secret के बारे में कोई जानकारी मिलती ही नहीं। एक हिस्सा कम हो तो हर संभव secret अब भी उतना ही संभव रहता है” — यह बात quadratic sieve या उसके रूपांतरों के साथ संख्याओं के factorization की याद दिलाती है
  वहाँ mod n congruences की एक प्रणाली खोजी जाती है और अंत में factors निकाले जाते हैं, लेकिन पर्याप्त चीजें इकट्ठी होने से पहले यह संभव नहीं होता। हर congruence में कुछ जानकारी तो होती होगी, इसलिए मैं हमेशा सोचता था कि हम किस space में degrees of freedom कम कर रहे हैं
  यहाँ भी हर हिस्सा polynomial के space को सीमित करता है, लेकिन इतना नहीं कि key जहाँ axis को काटती है वह बिंदु बता सके

• यह सच में बहुत शानदार तकनीक है, और polynomial के साथ computer scientist क्या रोचक काम कर सकते हैं, यह middle school में भी सिखाया जा सकता है

  • मैं middle school का math teacher हूँ, और वास्तव में इसे छात्रों को इसी तरह पढ़ाता हूँ
    linear function का equation फिर से निकालने वाले पाठ में मैं Shamir का परिचय कराता हूँ, और छात्र secret PIN को slope मानकर दो points बनाते हैं और उन्हें दो दूसरे छात्रों को दे देते हैं। वे दोनों मिलकर PIN वापस निकालते हैं, और छात्र हमेशा बहुत उत्साह से जुड़ते हैं

• Bruce Schneier ने अपनी क्लासिक किताब Applied Cryptography में इसे समझाया था, और HashiCorp Vault में इसका Go implementation भी था। व्यावहारिक रूप से मैं हमेशा सोचता था कि distributed shares कितने bits के होने चाहिए
  newsgroup में जो जवाब सुना था वह था, “असल key length से 1 bit ज़्यादा।” आजकल मैं सोचता हूँ कि quantum computing का खतरा 1) share size के चुनाव और 2) secret sharing के कुल फायदे-नुकसान पर क्या असर डालेगा

  • बुनियादी Shamir स्कीम information-theoretically secure है, और quantum computers से बिल्कुल प्रभावित नहीं होती
    अगर आप 1-byte secret के लिए ‘10 में threshold’ Shamir shares बनाते हैं और उनमें से 9 एक-byte shares दे देते हैं, तब भी ब्रह्मांड का कोई भी computer secret नहीं निकाल सकता। असली implementations में integrity check के लिए message authentication code या checksum जोड़ना पड़ता है, इसलिए कुछ bytes और बढ़ जाते हैं
  • आम तौर पर secret sharing finite field में की जाती है क्योंकि computers गलतियाँ करना पसंद नहीं करते। Share का आकार एक point (x, y) होता है, जहाँ x छोटा हो सकता है और आमतौर पर n participants होने पर log n के आसपास होता है, और y field का एक random point होता है
    Shamir secret sharing information-theoretically secure है, इसलिए k-out-of-n secret में k points इकट्ठे न हों तो brute force करने पर भी हर secret समान रूप से plausible रहता है। इसलिए field का bit size आप जैसा चाहें चुन सकते हैं, लेकिन जाहिर है वह secret के bit size से बड़ा होना चाहिए। 5 elements वाले finite field में आप 100 bits नहीं छिपा सकते
    आम तौर पर यह भी ज़रूरी होता है कि attacker secret को खुद brute force न कर सके। क्योंकि स्कीम information-theoretically secure हो सकती है, लेकिन secret खुद आमतौर पर ऐसा नहीं होता। उदाहरण के लिए wallet seed ऐसा ही होता है, इसलिए secret में randomness जोड़ते हैं और field bit size को काफी बड़ा रखते हैं ताकि ऐसे हमले रोके जा सकें
    attack model के हिसाब से 80-bit या 128-bit field काफी सुरक्षित हो सकता है, और share size भी 80-bit या 128-bit से थोड़ा ही बड़ा होगा। Quantum computers के मामले में, यह स्कीम information-theoretically secure है इसलिए इस पर कोई हमला मौजूद नहीं हो सकता
  • मेरी जानकारी में HashiCorp के पास अभी भी Vault की seal/unseal प्रक्रिया के लिए इसका implementation है। बशर्ते कि कुछ बदला न हो
  • Shamir स्कीम fundamental theorem of algebra पर आधारित है। n-degree polynomial को uniquely define करने के लिए n+1 points चाहिए होते हैं
    इसलिए n-of-k configuration बनाने के लिए n-1 degree polynomial p(x) बनाते हैं, और उस polynomial से k random points लेते हैं। i-th share बस (xi, yi) होता है, इसलिए bit count उस field से तय होता है जिसमें polynomial बनाया गया है
    Field इतनी बड़ी होनी चाहिए कि पूरा secret समा सके, और क्योंकि (x, y) दोनों values स्टोर करनी पड़ती हैं, share size कम-से-कम secret size का दोगुना होता है। हालाँकि यह जाँचने के लिए integrity checks भी चाहिए कि share खराब तो नहीं हुआ
    मेरी समझ से quantum computing यहाँ कुछ भी नहीं बदलती। एक point भी कम पड़ जाए तो आखिरी point secret को कुछ भी बना सकता है, और इसे अलग पहचानने का कोई तरीका नहीं होता
  • पूरा secret जरूरी नहीं कि underlying field का सिर्फ एक element हो। यह छोटे field elements के n-tuple के रूप में भी हो सकता है
    अगर आप बेहिसाब shares की उम्मीद नहीं कर रहे हैं, तो GF(2^8) एक काफी स्वाभाविक विकल्प है, और तब बड़े integer operations सँभालने की जरूरत भी नहीं पड़ती

• Ente का implementation यहाँ है: (https://2of3.ente.com/)

  • अब तक जो देखा उनमें यह मुझे सबसे ज़्यादा पसंद आया, और यह बहुत user-friendly है। बस अच्छा होता अगर इसमें थोड़ा और configuration संभव होता
    आदर्श रूप से, 3 of 4: A B C D या 2 of 3: E F G और 1 of 1: H जैसी configurations बनाई जा सकतीं
    recovery के समय ठीक-ठीक क्या चाहिए, यह स्पष्ट करने के लिए cards पर नाम लिखने का तरीका भी अच्छा होता। हालाँकि मौजूदा design की simplicity भी अपनी जगह एक फायदा है
  • ज़्यादातर Linux distributions में packaged implementation भी है: http://point-at-infinity.org/ssss
  • इसके कई browser-based versions हैं, जिन्हें online इस्तेमाल किया जा सकता है या download करके offline भी चलाया जा सकता है
    https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

• मैंने कुछ साल पहले browser में Shamir secret sharing चलाने वाला एक छोटा tool बनाया था। पेज को download कर लें तो इसे पूरी तरह offline भी इस्तेमाल किया जा सकता है
  https://simon-frey.com/s4/

  • मैंने कुछ साल पहले वह पेज download करके कुछ USB disks में सेव कर लिया था, और साथ में KeePass database और password shares भी रख दिए थे
    उन्हें परिवार के कुछ लोगों में बाँट दिया, और कहा कि अगर मेरी मौत हो जाए तो उन्हें मेरी पत्नी तक पहुँचा दें