HMAC ने मेरा autocomplete खा लिया: encrypted emails पर type-ahead search

हम user PII को at rest per-tenant keys से encrypt करते हैं, ताकि leaked database dump से कुछ भी उपयोगी उजागर न हो। Email column ciphertext है। Phone numbers, names, custom attributes: सब ciphertext। हमें इस पर गर्व है। यह एक selling point है।

और जिस दिन यह live हुआ, उसी दिन admin search box ने चुपचाप autocomplete करना बंद कर दिया।

कोई error नहीं। कोई log line नहीं। User search में ali type कीजिए, और जो tenant admin पहले तीन keystrokes के बाद [email protected] को pop up होते देखता था, उसे अब... कुछ नहीं दिखता, जब तक कि वह पूरा email address, बिल्कुल सही, type न कर दे। Search टूटी नहीं थी, वह चुपचाप "starts with" से "equals" तक degrade हो गई थी, और system में किसी को भी यह ज़िक्र करने लायक नहीं लगा।

यह कहानी है उस data पर type-ahead वापस पाने की जिसे हम plaintext में store करने से इनकार करते हैं, और उन तीन traps की जिनसे हम इस दौरान टकराए। Cryptography तो आसान हिस्सा निकली।

Encryption autocomplete को क्यों खा जाता है

Plaintext के साथ, prefix search तो वही है जिसके लिए databases बने हैं। Email के हिसाब से ordered एक index रखिए और starts with "ali" एक range scan बन जाता है: वह सब कुछ जो >= "ali" और < "alj" है। सस्ता, ज़ाहिर, हो गया।

Column को encrypt कीजिए और ordered index गायब हो जाता है। इसका standard replacement है blind index: ciphertext के साथ-साथ value का एक keyed HMAC store कीजिए, और search term का HMAC दोबारा compute करके users को look up कीजिए। HMAC(key, "[email protected]") deterministic है, इसलिए exact-match lookup बिल्कुल ठीक काम करता है, और index से कुछ भी पढ़ने लायक leak नहीं होता, क्योंकि per-tenant key के बिना आप compare करने के लिए कोई digest compute ही नहीं कर सकते।

लेकिन ध्यान दीजिए कि HMAC किसलिए है। इसका पूरा design goal ही यह है कि मिलते-जुलते inputs असंबंधित outputs दें: एक bit पलटिए, बिल्कुल अलग digest पाइए। HMAC("ali") और HMAC("alistair") का आपस में कोई लेना-देना नहीं है। जो property blind index को leak होने पर भी safe बनाती है, ठीक वही property उसे "starts with" का जवाब देने में असमर्थ बनाती है। Ordering ही leakage है। Blind index prefix search को गलती से नहीं तोड़ता; वह उसे उसूलन तोड़ता है।

तो search box चुपचाप exact-match तक degrade हो गया, क्योंकि exact-match ही एकमात्र सवाल था जिसका जवाब index अब भी दे सकता था।

Design: हर prefix को उसकी अपनी value के रूप में index करें

अगर index सिर्फ़ "equals" का जवाब दे सकता है, तो "starts with" को "equals" में बदल दीजिए।

Normalized email local part (यानी @ से पहले का हिस्सा) के हर prefix को उसकी अपनी blind-index row मिलती है। [email protected] के लिए, यानी al, ali, alis, alist, वगैरह के लिए rows: PartitionKey = HMAC(prefix), RowKey = user id। अब "starts with ali" HMAC("ali") पर एक exact-match lookup है: एक point query, किसी ordering की ज़रूरत नहीं। हमारी name search इसी वजह से पहले से इसी तरह काम करती थी; email बस उसमें शामिल हो गया।

दो constants इसे संतुलित रखते हैं। Prefixes 2 characters से शुरू होते हैं (one-character lookups कभी उपयोगी नहीं थे और rows दोगुनी कर देते हैं) और 16 पर cap होते हैं (इससे हर email का fan-out सीमित रहता है; लंबी query बस अपने पहले 16 characters पर match करती है, और मुट्ठी भर candidates decryption के बाद filter हो जाते हैं)। इस तरह हर email की लागत ज़्यादा से ज़्यादा 15 index rows है: create पर लिखी जाती हैं, email बदलने पर move होती हैं, delete पर हटाई जाती हैं।

यही trade एक वाक्य में: जिस ordering को leak करने से आपने इनकार किया था, उसे आप वापस खरीदते हैं, और उसकी कीमत write fan-out में चुकाते हैं। Storage और writes सस्ते हैं; leaked structure नहीं। यह एक अच्छा सौदा है।

Move-on-change path की एक बारीकी ने code में अपनी अलग comment कमाई: prefix rows local part पर keyed हैं, इसलिए rewrite तब trigger होना चाहिए जब local part बदले, domain से स्वतंत्र होकर। एक same-domain rename, [email protected] → [email protected], domain index को ध्यान में रखकर लिखे गए guard को "domain unchanged, index का काम skip करो" जैसा दिखता है, और पुरानी prefix rows को हमेशा के लिए renamed user की ओर इशारा करते छोड़ देता।

और जो हमने बनाया उसके बारे में ईमानदारी से कहें तो: यह index जान-बूझकर prefix-equality leak करता है। Table तक पहुँच रखने वाला attacker देख सकता है कि दो users का 3-character email prefix एक जैसा है, हालाँकि यह नहीं कि वह prefix क्या है। Searchable encryption leakage को कभी खत्म नहीं करता; वह आपको उसे चुनने देता है, सोच-समझकर, हर query shape के हिसाब से। Equality और prefix-equality वह leakage है जो हमने चुनी। यही framing (अपनी leakage चुनिए, फिर बाकी सब कुछ उसके इर्द-गिर्द engineer कीजिए) पूरी discipline है।

Design काम कर गया। फिर systems problems शुरू हुईं।

Trap एक: वह key जो बन ही नहीं पाई

Blind indexes को हर tenant के लिए एक HMAC key चाहिए, जो हमारी encryption keys की तरह Vault के transit engine में provision होती है। एक बनाने पर 500 मिला: invalid key size for HMAC key।

Vault hmac-type keys के लिए एक explicit key_size मांगता है, 32 से 512 bytes, जबकि fixed-size types (aes256-gcm96, ecdsa-p256) इसे मना करते हैं। हमारी key-creation call सिर्फ़ {"type":"hmac"} भेजती थी। एक missing field।

यह trap क्यों था, महज़ bug report क्यों नहीं, इसकी वजह: हर tokenize operation throw करने लगा, और login path tokenize करता है, क्योंकि sign-in पर email से user ढूँढना उसी blind index से गुज़रता है जिससे admin search। Encryption enable करने से search नहीं टूटी। Login टूट गया। जिस feature की sales pitch है "आपके users ज़्यादा सुरक्षित हैं", उसने dev में पहली बार enable होते ही sign-in गिरा दिया। Fix है hmac keys के लिए key_size=32 (HMAC-SHA256), और fixed-size types के लिए इसे omit करना, साथ ही एक standing rule: encryption कहीं भी on करने से पहले tokenize path को एक असली Vault के खिलाफ smoke-test कीजिए। Mocks key-creation payloads validate नहीं करते।

Trap दो: वह update जो user को अधर में छोड़ सकता था

Email बदलने का मतलब है index maintenance: पुरानी rows हटाइए, नई लिखिए। हमारे पहले implementation ने इसे इसी क्रम में किया: delete, फिर write। स्वाभाविक, सुथरा, गलत।

हर new-row write में अब Vault शामिल है (HMAC PartitionKeys compute करने के लिए)। पहले पुरानी rows delete कीजिए, और write के दौरान Vault की एक hiccup user को ऐसी स्थिति में छोड़ देती है जहाँ उसके पास न पुरानी lookup rows हैं न नई। वे table में मौजूद हैं, encrypted, और कोई उन्हें ढूँढ नहीं सकता। Login भी नहीं। यह degraded search नहीं है; यह locked-out user है, जब तक कोई भावी reindex वहाँ से न गुज़र जाए।

Fix ordering है, error handling नहीं: write before delete, हर उस जगह जहाँ index maintain होता है। दोनों steps के बीच crash अब एक फ़ालतू stale row छोड़ता है (हानिरहित, आराम से lazily साफ़ हो जाती है), न कि एक missing row। Failure mode "user unreachable" से "एक redundant row" पर आ गया, मुफ़्त में। जब किसी write path में remote dependency शामिल हो, तो वही step order चुनिए जिसकी आधी-अधूरी state के साथ आप जी सकते हों।

Trap तीन: वह partition जो एक import को खा गया

हम एक domain blind index भी रखते हैं, HMAC(domain) → members, ताकि "everyone at acme.com" एक lookup हो। Deterministic hashing का एक नतीजा है जिसकी कीमत कोई import आने तक नहीं आँकता: एक domain के सारे users एक ही partition में गिरते हैं। एक Azure Table partition लगभग 2,000 operations प्रति second संभालता है। Auth0 से 50k-user का single-domain import हर domain-index write को ठीक उसी bottleneck में झोंक रहा था।

Fix है bucketing: members user id के hash से 16 partitions में फैलते हैं, और domain reads buckets पर fan out करती हैं (bounded, और इतनी rare कि फ़र्क नहीं पड़ता)। दो details में सबक छिपा था। Bucket hash एक hand-rolled FNV-1a है, क्योंकि .NET का string.GetHashCode जान-बूझकर processes के बीच unstable है: उससे bucket कीजिए और कल का process उसी user के लिए अलग bucket compute करेगा और वह row नहीं ढूँढ पाएगा जिसे उसे delete करना है। और read path अब भी legacy unbucketed partitions को sweep करता है, इसलिए मौजूदा rows बिना किसी forced backfill के findable रहीं: नई writes तुरंत distribute होती हैं, पुरानी rows तब migrate होती हैं जब user को अगली बार छुआ जाए।

सबक

इस कहानी में कुछ भी novel cryptography नहीं है। HMAC दशकों पुराना है; "hash the value, index the hash" एक वाक्य में समा जाता है। जो कुछ भी हमें वास्तव में महंगा पड़ा, वह systems का काम था: product को असल में कौन-सी query shapes चाहिए (equality, prefix, domain, हर एक को अपना index मिला, क्योंकि blind index ठीक एक सवाल का जवाब देता है); keys कैसे provision होती हैं और जब नहीं होतीं तो login path पर क्या होता है; बीच में remote KMS बैठा हो तो index writes किस क्रम में होती हैं; और deterministic hashing load को वहाँ कैसे केंद्रित कर देता है जहाँ plaintext ने कभी नहीं किया।

Searchable encryption एक crypto feature के तौर पर बेचा जाता है। इसे बनाइए और आप पाएँगे कि यह crypto की पोशाक पहने एक distributed-systems feature है। Search box फिर से autocomplete करता है (ali तीन keystrokes के बाद Alistair को ढूँढ लेता है) और उसी table का चुराया हुआ dump सोलह buckets में फैले HMAC digests दिखाता है, यानी: कुछ भी नहीं। दोनों एक साथ, यही तो हमेशा से मकसद था।