- Chia sẻ bí mật Shamir chia một bí mật thành nhiều mảnh, chỉ có thể khôi phục khi tập hợp đủ từ ngưỡng trở lên, còn ít hơn thì không làm lộ bất kỳ thông tin nào
- Hữu ích trong các trường hợp như khóa master của công ty, khôi phục tài khoản gia đình, sao lưu nhóm, khi khó giao toàn bộ bí mật cho một người và vẫn cần khôi phục ngay cả khi mất một số mảnh
- Mô hình cốt lõi là ẩn bí mật dưới giá trị tại điểm
0 của một đa thức, rồi chia cho mỗi mảnh dưới dạng một điểm trên đường cong
- Với ngưỡng
k, dùng đa thức bậc k - 1; hai mảnh tương ứng với đường thẳng, ba mảnh là parabol, bốn mảnh là đường cong bậc ba
- Legacy Kit của Ente dùng cách này như một lớp trong hệ thống để thẻ không trở thành khóa khôi phục vĩnh viễn, đồng thời cho phép hủy các thẻ đã phát hành
Cách chia bí mật bằng điểm và đa thức
- Đây là phương pháp do Adi Shamir công bố năm 1979, và điểm cốt lõi không chỉ là “khó phá” mà là nếu thiếu số mảnh cần thiết thì hoàn toàn không lộ ra thông tin nào
- Hai điểm khác nhau xác định chính xác một đường thẳng, nhưng nếu chỉ có một điểm thì có vô số đường thẳng đi qua điểm đó, và mỗi đường sẽ cắt trục dọc tại một vị trí khác nhau
- Nếu bí mật là số
7, có thể giấu giá trị này tại vị trí đường thẳng cắt trục dọc
- Độ dốc không phải là bí mật mà đóng vai trò ngẫu nhiên để che giấu bí mật
- Nếu phát cho mỗi người một điểm trên đường thẳng, thì chỉ với một điểm của một người sẽ có vô số đường thẳng khả dĩ, tất cả đều tương thích với những bí mật khác nhau
- Khi ghép hai điểm lại, đường thẳng được xác định cố định, và có thể khôi phục bí mật bằng cách đọc giá trị mà đường đó có tại
0
- Cấu trúc này là mô hình chia sẻ bí mật 2-of-n; có thể tạo bao nhiêu điểm tùy ý, nhưng chỉ cần bất kỳ hai điểm nào cũng có thể khôi phục đường thẳng
- Khi ngưỡng tăng lên, ta dùng các đường cong bậc cao hơn
- Parabol cần ba điểm mới xác định được, nên nếu giấu bí mật tại vị trí parabol cắt trục dọc thì có thể khôi phục bằng bất kỳ ba mảnh nào, còn hai mảnh thì không thể
- Nói chung, với ngưỡng
k thì dùng đa thức bậc k - 1
2 mảnh là đường thẳng, 3 mảnh là parabol, 4 mảnh là đường cong bậc ba- Trong triển khai thực tế, người ta không dùng giấy kẻ ô để vẽ đồ thị mà dùng số học trường hữu hạn, nhưng cấu trúc vẫn giống nhau: bí mật là giá trị tại
0, các hệ số ngẫu nhiên che giấu nó, và mỗi mảnh là một điểm trên đa thức
- Điều quan trọng là khi không đủ mảnh, vấn đề không chỉ là khó tính ra bí mật, mà là mọi bí mật khả dĩ vẫn đều còn có thể xảy ra
Ente Legacy Kit và tài liệu tham khảo
- Ente sử dụng ý tưởng này trong Legacy Kit
- Mục tiêu cần đạt không chỉ là chia nhỏ bí mật, mà còn phải cho phép khôi phục trong khi các mảnh đã chia không trở thành khóa khôi phục vĩnh viễn
- Legacy Kit sử dụng phương pháp Shamir như một lớp trong một luồng lớn hơn
- Bản thân khóa khôi phục không nằm trên thẻ; thay vào đó, một bí mật riêng được tái tạo cục bộ rồi tham gia vào quá trình khôi phục do máy chủ làm trung gian
- Nhờ cấu trúc này, các thẻ đã phát hành có thể bị hủy, và thẻ bị mất không trở thành gánh nặng vĩnh viễn
- Tài liệu tham khảo
1 bình luận
Ý kiến trên Hacker News
Tôi đã viết luận văn thạc sĩ về chủ đề này. Tôi đã tạo một ứng dụng chia dữ liệu để lưu trên nhiều nhà cung cấp lưu trữ phổ biến như Dropbox, Google Drive, OneDrive, và dùng chia sẻ bí mật để hỗ trợ mã hóa
Ưu điểm là nhà cung cấp không còn có thể đọc dữ liệu, chỉ cần 2 nơi còn hoạt động nên có độ dư thừa bổ sung, và khác với các ứng dụng lưu trữ bảo mật khác nơi quên mật khẩu chủ là hết cách, có thể dùng nguyên quy trình khôi phục tài khoản sẵn có
Tôi tự hỏi liệu có cách nào gộp nhiều cặp khóa/giá trị thành một bản mã duy nhất hay không. Không chỉ đơn giản là nối chuỗi hoặc làm kích thước kết quả bùng nổ, mà là để mọi người đưa thông tin vào hệ này cùng lưu một khối đã mã hóa giống nhau nhưng với khóa riêng của mình lại giải mã ra các giá trị khác nhau
Như vậy mọi người có thể đóng vai trò sao lưu cho nhau mà vẫn có khả năng phủ nhận hợp lý về việc chính xác đang lưu thứ gì
Trong luận văn thạc sĩ, tôi đã áp dụng chia sẻ bí mật Shamir vào mạng mesh. Ý tưởng là ngay cả khi một nút trong mesh bị kẻ tấn công chiếm được và bí mật của nút đó bị thu hồi thì vẫn không thể phá được toàn bộ mã hóa
Nhóm chúng tôi dùng kỹ thuật này để phân phối mật khẩu của kho lưu trữ bí mật phụ theo cách “an toàn một cách dân chủ”. Kho phụ đó chứa cách truy cập vào kho bí mật chính
https://packages.debian.org/trixie/ssss là một triển khai ổn và khá trực quan
Shamir đã từng cứu tôi một bàn thua trông thấy. Tôi phải khôi phục gấp một bản sao lưu gần như đã bị quên lãng, và nhờ đó có thể tái tạo mật khẩu ngẫu nhiên đã dùng khi đó
May mà trước đây tôi đã chia các mảnh phân tán cho người thân “để phòng khi cần”
Đoạn “điểm hữu ích không phải là nếu có quá ít mảnh thì khó tính ra bí mật. Mà là nếu có quá ít mảnh thì hoàn toàn không có thông tin gì về bí mật. Chỉ cần thiếu một mảnh thì mọi bí mật khả dĩ vẫn đều có thể xảy ra” làm tôi nhớ tới việc phân tích số bằng trường bậc hai hay các biến thể của nó
Bạn tìm ra hệ các đồng dư mod n và cuối cùng tính được các thừa số nguyên tố, nhưng trước khi gom đủ thì điều đó là bất khả thi. Mỗi đồng dư chắc hẳn vẫn mang một ít thông tin nào đó, nên tôi luôn thắc mắc rốt cuộc ta đang giảm bậc tự do trong không gian nào
Ở đây cũng vậy, mỗi mảnh đều giới hạn không gian các đa thức, nhưng chưa giới hạn đủ để cho biết điểm nơi khóa cắt trục
Đây thực sự là một kỹ thuật rất hay, đủ đơn giản để có thể dạy ở trường trung học như một ví dụ thú vị về những việc nhà khoa học máy tính có thể làm với đa thức
Trong bài học khôi phục phương trình hàm bậc nhất, tôi giới thiệu Shamir, cho học sinh chọn PIN bí mật làm hệ số góc, rồi tạo hai điểm để đưa cho hai học sinh khác. Hai em đó phải ghép cặp để tìm lại PIN, và học sinh lúc nào cũng rất hào hứng
Bruce Schneier đã giải thích nội dung này trong cuốn sách kinh điển Applied Cryptography, và HashiCorp Vault cũng từng có một triển khai bằng Go. Về mặt thực tế, tôi luôn thắc mắc các mảnh phân tán nên có độ dài bao nhiêu bit
Câu trả lời tôi từng nghe trên nhóm tin là “nhiều hơn độ dài khóa thực tế 1 bit”. Giờ tôi lại tò mò mối đe dọa từ máy tính lượng tử sẽ ảnh hưởng thế nào đến 1) việc chọn kích thước mảnh và 2) các ưu nhược điểm của chia sẻ bí mật nói chung
Nếu bạn tạo các mảnh Shamir ngưỡng “10 trong số” cho một bí mật 1 byte và đưa ra 9 mảnh 1 byte, thì không có máy tính nào trong vũ trụ có thể tìm ra bí mật đó. Trong triển khai thực tế, bạn cần thêm mã xác thực thông điệp hoặc checksum để kiểm tra tính toàn vẹn nên sẽ lớn hơn vài byte
Chia sẻ bí mật Shamir an toàn theo lý thuyết thông tin, nên với bí mật k-out-of-n, nếu không có đủ k điểm thì ngay cả vét cạn cũng thấy mọi bí mật đều hợp lý như nhau. Vì thế số bit của trường có thể chọn tùy ý, nhưng dĩ nhiên phải lớn hơn số bit của bí mật. Bạn không thể giấu 100 bit trong một trường hữu hạn chỉ có 5 phần tử
Thông thường bạn còn phải ngăn kẻ tấn công vét cạn chính bản thân bí mật. Dù phương pháp an toàn theo lý thuyết thông tin, bản thân bí mật thường không như vậy. Ví dụ seed của ví là như thế, nên người ta thêm tính ngẫu nhiên vào bí mật và chọn kích thước trường đủ lớn để chặn kiểu tấn công này
Tùy mô hình đe dọa, trường 80 bit hoặc 128 bit thường đã đủ an toàn, và kích thước mảnh cũng chỉ nhỉnh hơn 80 bit hoặc 128 bit một chút. Với máy tính lượng tử, vì phương pháp này an toàn theo lý thuyết thông tin nên không thể tồn tại kiểu tấn công đó
Vì vậy để tạo cấu hình n-of-k, bạn tạo một đa thức p(x) bậc n-1 rồi lấy k điểm bất kỳ từ đa thức đó. Mảnh thứ i đơn giản là (xi, yi), nên số bit của nó do trường dùng để xây đa thức quyết định
Trường đó phải đủ rộng để chứa toàn bộ bí mật, và vì phải lưu cả hai giá trị (x, y), kích thước mảnh tối thiểu là gấp đôi kích thước bí mật. Tuy vậy vẫn cần kiểm tra tính toàn vẹn để biết mảnh có bị hỏng hay không
Tôi hiểu rằng điện toán lượng tử không làm thay đổi gì ở đây. Chỉ cần thiếu một điểm thì điểm cuối cùng vẫn có thể thay bí mật bằng bất cứ giá trị nào, và không có cách nào để phân biệt
Nếu bạn không dự kiến số lượng mảnh nhiều đến mức vô lý, thì GF(2^8) là một lựa chọn khá tự nhiên, và cũng không cần xử lý số nguyên lớn
Triển khai của Ente ở đây: (https://2of3.ente.com/)
Lý tưởng nhất là có thể tạo các cấu hình như
3 of 4: A B C Dhoặc2 of 3: E F Gvà1 of 1: HCũng sẽ hay nếu có cách gắn tên lên các thẻ để làm rõ chính xác cần gì khi khôi phục. Tất nhiên sự đơn giản trong thiết kế hiện tại cũng có cái hay riêng
https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/
Vài năm trước tôi đã làm một công cụ nhỏ chạy Shamir secret sharing ngay trong trình duyệt. Tải trang xuống là có thể dùng hoàn toàn ngoại tuyến
https://simon-frey.com/s4/
Tôi đưa chúng cho vài người thân trong gia đình và dặn rằng nếu tôi chết thì hãy chuyển cho vợ tôi