HMAC đã nuốt mất autocomplete của tôi: tìm kiếm gợi ý theo từng ký tự trên email đã mã hóa
Chúng tôi mã hóa PII của người dùng khi lưu trữ bằng khóa riêng cho từng tenant, để một bản dump cơ sở dữ liệu bị rò rỉ không để lộ điều gì hữu ích. Cột email là ciphertext. Số điện thoại, tên, thuộc tính tùy chỉnh: tất cả đều là ciphertext. Chúng tôi tự hào về điều này. Nó là một điểm bán hàng.
Và đúng ngày tính năng này đi vào hoạt động, ô tìm kiếm của trang quản trị lặng lẽ ngừng tự động gợi ý.
Không lỗi. Không một dòng log. Gõ ali vào ô tìm kiếm người dùng, và người quản trị tenant vốn từng thấy [email protected] hiện ra sau ba lần gõ phím giờ đây thấy... không gì cả, trừ khi họ gõ toàn bộ địa chỉ email, chính xác từng ký tự. Tìm kiếm không hề hỏng: nó đã âm thầm suy giảm từ "bắt đầu bằng" xuống "bằng đúng", và không thành phần nào trong hệ thống thấy điều đó đáng để lên tiếng.
Đây là câu chuyện về việc lấy lại tính năng gợi ý theo từng ký tự trên dữ liệu mà chúng tôi từ chối lưu ở dạng plaintext, và ba cái bẫy chúng tôi gặp phải trên đường đi. Hóa ra phần mật mã lại là phần dễ.
Vì sao mã hóa nuốt mất autocomplete
Với plaintext, tìm kiếm theo tiền tố chính là thứ cơ sở dữ liệu sinh ra để làm. Giữ một chỉ mục sắp thứ tự theo email và starts with "ali" là một range scan: mọi thứ >= "ali" và < "alj". Rẻ, hiển nhiên, xong.
Mã hóa cột đó và chỉ mục có thứ tự biến mất. Giải pháp thay thế tiêu chuẩn là một blind index (chỉ mục mù): bên cạnh ciphertext, lưu một keyed HMAC của giá trị, và tra cứu người dùng bằng cách tính lại HMAC của từ khóa tìm kiếm. HMAC(key, "[email protected]") mang tính tất định, nên tra cứu khớp chính xác hoạt động hoàn hảo, và chỉ mục không để lộ thứ gì đọc được, bởi vì thiếu khóa riêng của tenant thì không thể tính ra digest để so sánh.
Nhưng hãy để ý HMAC sinh ra để làm gì. Toàn bộ mục tiêu thiết kế của nó là các đầu vào giống nhau tạo ra các đầu ra không liên quan gì đến nhau: lật một bit, nhận về một digest hoàn toàn khác. HMAC("ali") và HMAC("alistair") chẳng dính dáng gì đến nhau. Chính tính chất khiến blind index an toàn khi bị lộ cũng là tính chất khiến nó không thể trả lời câu hỏi "bắt đầu bằng". Thứ tự chính là rò rỉ. Blind index không vô tình làm hỏng tìm kiếm theo tiền tố; nó làm hỏng điều đó một cách có nguyên tắc.
Vậy nên ô tìm kiếm suy giảm xuống khớp chính xác, một cách lặng lẽ, vì khớp chính xác là câu hỏi duy nhất mà chỉ mục còn trả lời được.
Thiết kế: đánh chỉ mục mọi tiền tố như một giá trị riêng
Nếu chỉ mục chỉ trả lời được "bằng đúng", thì hãy biến "bắt đầu bằng" thành "bằng đúng".
Mỗi tiền tố của phần local đã chuẩn hóa của email (phần đứng trước dấu @) nhận một dòng blind-index riêng. Với [email protected], đó là các dòng cho al, ali, alis, alist, và cứ thế tiếp tục: PartitionKey = HMAC(prefix), RowKey = id của người dùng. Giờ đây "bắt đầu bằng ali" là một tra cứu khớp chính xác trên HMAC("ali"): một point query duy nhất, không cần thứ tự. Tìm kiếm theo tên của chúng tôi vốn đã hoạt động theo cách này vì cùng một lý do; email chỉ là gia nhập sau.
Hai hằng số giữ cho mọi thứ trong tầm kiểm soát. Tiền tố bắt đầu từ 2 ký tự (tra cứu một ký tự chưa bao giờ hữu ích mà lại nhân đôi số dòng) và giới hạn ở 16 (chặn trên mức fan-out cho mỗi email; một truy vấn dài hơn chỉ khớp trên 16 ký tự đầu của nó, và nhúm ứng viên còn lại được lọc sau khi giải mã). Vậy mỗi email tốn nhiều nhất 15 dòng chỉ mục: được ghi khi tạo, dời đi khi email thay đổi, xóa khi xóa người dùng.
Đó là sự đánh đổi gói trong một câu: bạn mua lại thứ tự mà bạn đã từ chối để lộ, và trả giá bằng fan-out khi ghi. Lưu trữ và ghi thì rẻ; cấu trúc bị rò rỉ thì không. Đây là một món hời.
Một điểm tinh tế trong đường dời-khi-thay-đổi đã tự giành được một dòng comment riêng trong code: các dòng tiền tố được khóa theo phần local, nên việc ghi lại phải được kích hoạt khi phần local thay đổi, độc lập với domain. Một lần đổi tên trong cùng domain, [email protected] → [email protected], trông giống như "domain không đổi, bỏ qua việc cập nhật chỉ mục" đối với một guard được viết với chỉ mục domain trong đầu, và sẽ để các dòng tiền tố cũ trỏ vào người dùng đã đổi tên mãi mãi.
Và để thành thật về thứ chúng tôi đã xây: chỉ mục này cố ý để lộ sự trùng tiền tố; kẻ tấn công có được bảng có thể thấy hai người dùng dùng chung một tiền tố email 3 ký tự, dù không biết tiền tố đó là gì. Searchable encryption không bao giờ loại bỏ được rò rỉ; nó cho bạn chọn phần rò rỉ, một cách có ý thức, theo từng dạng truy vấn. Trùng khớp và trùng tiền tố là phần rò rỉ chúng tôi đã chọn. Cách nhìn đó (chọn phần rò rỉ của mình, rồi thiết kế mọi thứ còn lại xoay quanh nó) chính là toàn bộ kỷ luật của lĩnh vực này.
Thiết kế hoạt động. Rồi các vấn đề hệ thống bắt đầu.
Bẫy thứ nhất: chiếc khóa không thể tạo ra
Blind index cần một khóa HMAC cho mỗi tenant, được cấp phát trong transit engine của Vault giống như các khóa mã hóa của chúng tôi. Tạo một khóa như vậy trả về lỗi 500: invalid key size for HMAC key.
Vault yêu cầu một key_size tường minh cho khóa kiểu hmac (từ 32 đến 512 byte), trong khi các kiểu có kích thước cố định (aes256-gcm96, ecdsa-p256) lại cấm tham số này. Lệnh tạo khóa của chúng tôi chỉ gửi {"type":"hmac"}. Thiếu đúng một trường.
Đây là lý do nó là một cái bẫy chứ không phải một bug report bình thường: mọi thao tác tokenize đều ném lỗi, mà đường đăng nhập cũng tokenize, bởi vì việc tìm người dùng theo email lúc đăng nhập đi qua đúng blind index mà tìm kiếm của trang quản trị sử dụng. Bật mã hóa không làm hỏng tìm kiếm. Nó làm hỏng đăng nhập. Tính năng có lời chào hàng là "người dùng của bạn an toàn hơn" đã đánh sập việc đăng nhập ngay lần bật đầu tiên trên môi trường dev. Cách sửa là key_size=32 (HMAC-SHA256) cho khóa hmac, bỏ trống với các kiểu kích thước cố định, cùng một quy tắc thường trực: smoke-test đường tokenize với một Vault thật trước khi bật mã hóa ở bất kỳ đâu. Mock không kiểm tra payload tạo khóa.
Bẫy thứ hai: bản cập nhật có thể bỏ rơi người dùng
Đổi email đồng nghĩa với bảo trì chỉ mục: xóa các dòng cũ, ghi các dòng mới. Bản hiện thực đầu tiên của chúng tôi làm đúng theo thứ tự đó: xóa, rồi ghi. Tự nhiên, gọn gàng, sai.
Mỗi lần ghi dòng mới giờ đây đều liên quan đến Vault (để tính các PartitionKey bằng HMAC). Xóa các dòng cũ trước, và một trục trặc của Vault trong lúc ghi sẽ để người dùng ở tình trạng không có dòng tra cứu cũ lẫn dòng mới. Họ vẫn tồn tại, đã mã hóa, trong bảng, mà không gì tìm ra họ được. Kể cả đăng nhập. Đó không phải là tìm kiếm bị suy giảm; đó là một người dùng bị khóa ngoài cửa, cho đến khi một đợt reindex nào đó trong tương lai quét qua.
Cách sửa nằm ở thứ tự, không phải ở xử lý lỗi: ghi trước, xóa sau, ở mọi nơi chỉ mục được bảo trì. Một sự cố giữa hai bước giờ chỉ để lại một dòng cũ thừa (vô hại, được dọn dần về sau) thay vì một dòng bị thiếu. Chế độ hỏng hóc chuyển từ "không thể tìm thấy người dùng" sang "một dòng dư thừa", hoàn toàn miễn phí. Khi một đường ghi có dính đến một phụ thuộc từ xa, hãy chọn thứ tự bước mà trạng thái dang dở của nó là thứ bạn sống chung được.
Bẫy thứ ba: partition nuốt trọn một đợt import
Chúng tôi cũng giữ một blind index theo domain (HMAC(domain) → các thành viên) để "tất cả mọi người ở acme.com" chỉ là một lần tra cứu. Băm tất định có một hệ quả mà chẳng ai tính giá cho đến khi import: mọi người dùng của một domain rơi vào một partition duy nhất. Một partition của Azure Table chịu được khoảng 2.000 thao tác mỗi giây. Một đợt import 50 nghìn người dùng cùng domain từ Auth0 dồn toàn bộ các lần ghi chỉ mục domain vào đúng cái nút thắt cổ chai đó.
Cách sửa là chia bucket: các thành viên được rải trên 16 partition theo một giá trị băm của id người dùng, và các lần đọc theo domain fan-out qua các bucket, có chặn trên, và đủ hiếm để không thành vấn đề. Hai chi tiết mang theo bài học. Hàm băm bucket là một FNV-1a tự viết, bởi vì string.GetHashCode của .NET cố tình không ổn định giữa các process: bucket theo nó thì process của ngày mai sẽ tính ra một bucket khác cho cùng một người dùng và không thể tìm thấy dòng mà nó cần xóa. Và đường đọc vẫn quét các partition không chia bucket kiểu cũ, nên các dòng hiện có vẫn tìm thấy được mà không cần một đợt backfill cưỡng bức nào: các lần ghi mới phân tán ngay lập tức, các dòng cũ di trú mỗi khi người dùng được đụng đến lần kế tiếp.
Bài học
Không có gì trong câu chuyện này là mật mã mới lạ. HMAC đã có hàng chục năm tuổi; "băm giá trị, đánh chỉ mục giá trị băm" gói gọn trong một câu. Mọi thứ thực sự khiến chúng tôi trả giá đều là công việc hệ thống: sản phẩm thực sự cần những dạng truy vấn nào (trùng khớp, tiền tố, domain, mỗi dạng có chỉ mục riêng, vì một blind index trả lời đúng một câu hỏi); khóa được cấp phát ra sao và điều gì xảy ra trên đường đăng nhập khi việc đó thất bại; các lần ghi chỉ mục diễn ra theo thứ tự nào khi một KMS từ xa nằm chính giữa; và nơi băm tất định dồn tải theo cách plaintext chưa bao giờ gây ra.
Searchable encryption được rao bán như một tính năng mật mã. Xây nó rồi bạn sẽ phát hiện nó là một tính năng hệ thống phân tán khoác áo mật mã. Ô tìm kiếm lại tự động gợi ý (ali tìm ra Alistair sau ba lần gõ phím), và một bản dump bị đánh cắp của chính bảng đó chỉ cho thấy các digest HMAC rải trên mười sáu bucket, nghĩa là: không gì cả. Có được cả hai cùng lúc từ đầu vẫn luôn là mục đích.