Shamir แชร์ความลับอย่างไร
(ente.com)- Shamir Secret Sharing คือการแบ่งความลับออกเป็นหลายชิ้น โดยจะกู้คืนได้ก็ต่อเมื่อมีชิ้นส่วนครบตามค่า threshold ขึ้นไป และถ้ามีน้อยกว่านั้นจะไม่เปิดเผยข้อมูลใดเลย
- มีประโยชน์เมื่อยากจะฝากความลับทั้งหมดไว้กับคนเพียงคนเดียว และยังต้องการให้กู้คืนได้แม้ชิ้นส่วนบางส่วนสูญหาย เช่น master key ของบริษัท การกู้คืนบัญชีครอบครัว หรือแบ็กอัปของทีม
- โมเดลหลักคือซ่อนความลับไว้เป็นค่าที่จุด
0ของพหุนาม แล้วแจกแต่ละชิ้นส่วนเป็น จุด หนึ่งจุดบนเส้นโค้ง - สำหรับ threshold
kจะใช้พหุนามดีกรีk - 1โดยชิ้นส่วน 2 ชิ้นคือเส้นตรง 3 ชิ้นคือพาราโบลา และ 4 ชิ้นคือเส้นโค้งกำลังสาม - Legacy Kit ของ Ente ใช้วิธีนี้เป็นหนึ่งเลเยอร์ เพื่อไม่ให้การ์ดกลายเป็นคีย์กู้คืนถาวร และทำให้สามารถยกเลิกการ์ดที่ออกไปแล้วได้
วิธีแบ่งความลับด้วยจุดและพหุนาม
- วิธีนี้ถูกเผยแพร่โดย Adi Shamir ในปี 1979 และหัวใจสำคัญไม่ใช่แค่ “ถอดได้ยาก” แต่คือถ้าจำนวนชิ้นส่วนที่ต้องการยังไม่ครบ ก็จะไม่เปิดเผยข้อมูลใดเลย
- จุดสองจุดที่ต่างกันจะกำหนดเส้นตรงได้อย่างแน่นอนเพียงเส้นเดียว แต่ถ้ามีแค่จุดเดียว จะมีเส้นตรงที่ผ่านจุดนั้นได้ไม่จำกัด และแต่ละเส้นจะตัดแกนตั้งคนละตำแหน่ง
- ถ้าความลับคือเลข
7ก็สามารถซ่อนค่านี้ไว้ที่ตำแหน่งที่เส้นตรงตัดแกนตั้งได้ - ความชันไม่ใช่ตัวความลับเอง แต่ทำหน้าที่เป็นความสุ่มเพื่อใช้ซ่อนความลับ
- หากแจกให้แต่ละคนคนละหนึ่งจุดบนเส้นตรง เพียงมีจุดของคนเดียวจุดเดียวก็ยังมีเส้นตรงที่เป็นไปได้อยู่ไม่จำกัด และแต่ละเส้นก็สอดคล้องกับความลับที่ต่างกันได้ทั้งหมด
- เมื่อนำสองจุดมารวมกัน เส้นตรงจะถูกกำหนดตายตัว และสามารถอ่านค่าที่เส้นนั้นมีเมื่อ
0เพื่อกู้คืนความลับได้ - โครงสร้างนี้คือการแชร์ความลับแบบ 2-of-n โดยสามารถสร้างจุดได้มากเท่าที่ต้องการ แต่จุดสองจุดใดๆ ก็ใช้กู้เส้นตรงได้
- เมื่อ threshold สูงขึ้น ก็จะใช้เส้นโค้งดีกรีสูงขึ้น
- พาราโบลาต้องใช้สามจุดจึงจะกำหนดได้ ดังนั้นถ้าซ่อนความลับไว้ที่ตำแหน่งที่พาราโบลาตัดแกนตั้ง ก็จะกู้คืนได้ด้วยชิ้นส่วนสามชิ้นใดๆ และกู้คืนด้วยสองชิ้นไม่ได้
- โดยทั่วไป threshold
kจะใช้พหุนามดีกรีk - 1 - ชิ้นส่วน
2ชิ้นคือเส้นตรง ชิ้นส่วน3ชิ้นคือพาราโบลา และชิ้นส่วน4ชิ้นคือเส้นโค้งกำลังสาม - ในการใช้งานจริงไม่ได้ใช้กระดาษกราฟ แต่ใช้เลขคณิตบน finite field อย่างไรก็ตาม โครงสร้างยังเหมือนเดิม คือความลับเป็นค่าที่
0สัมประสิทธิ์แบบสุ่มใช้ซ่อนมันไว้ และแต่ละชิ้นส่วนคือหนึ่งจุดบนพหุนาม - สิ่งสำคัญคือเมื่อชิ้นส่วนไม่พอ ไม่ใช่แค่คำนวณความลับได้ยาก แต่ความลับที่เป็นไปได้ทั้งหมดยังคงเป็นไปได้อยู่ทั้งหมด
Ente Legacy Kit และแหล่งข้อมูลอ้างอิง
- Ente ใช้แนวคิดนี้ใน Legacy Kit
- เป้าหมายที่ต้องการไม่ใช่แค่แบ่งความลับ แต่ต้องทำให้ชิ้นส่วนที่ถูกแบ่งออกมาไม่กลายเป็นคีย์กู้คืนถาวร ขณะเดียวกันก็ยังทำให้กู้คืนได้
- Legacy Kit ใช้วิธีของ Shamir เป็นหนึ่งเลเยอร์ภายในโฟลว์ที่ใหญ่กว่า
- ตัวการ์ดไม่ได้เก็บ recovery key เอง แต่จะนำความลับอีกชุดหนึ่งมาสร้างใหม่บนเครื่อง แล้วให้เซิร์ฟเวอร์ช่วยเป็นตัวกลางในกระบวนการกู้คืน
- ด้วยโครงสร้างนี้ จึงสามารถยกเลิกการ์ดที่ออกไปแล้วได้ และการ์ดที่สูญหายจะไม่กลายเป็นภาระถาวร
- แหล่งข้อมูลอ้างอิง
1 ความคิดเห็น
ความคิดเห็นใน Hacker News
เคยเขียนวิทยานิพนธ์ปริญญาโทเกี่ยวกับเรื่องนี้ ทำแอปที่แบ่งข้อมูลไปเก็บไว้กับผู้ให้บริการสตอเรจทั่วไปหลายเจ้าอย่าง Dropbox, Google Drive, OneDrive และใช้ การแบ่งปันความลับ เพื่อช่วยเรื่องการเข้ารหัส
ข้อดีคือผู้ให้บริการจะอ่านข้อมูลไม่ได้อีกต่อไป, มี ความซ้ำซ้อนเพิ่มเติม เพราะเหลือรอดแค่ 2 แห่งก็ยังพอ, และต่างจากแอป secure storage อื่น ๆ ที่ถ้าลืมรหัสผ่านหลักก็จบเลย อันนี้ยังใช้กระบวนการกู้คืนบัญชีเดิมได้ตามปกติ
สงสัยว่ามีวิธีรวมหลายคู่คีย์/ค่าให้เป็น ciphertext เดียวได้ไหม โดยไม่ใช่แค่เอามาต่อกันตรง ๆ หรือทำให้ขนาดผลลัพธ์พุ่งขึ้นมาก และทำให้ทุกคนที่ใส่ข้อมูลด้วยวิธีนี้เก็บก้อนข้อมูลเข้ารหัสก้อนเดียวกันไว้ แต่ใช้คีย์ของตัวเองถอดรหัสออกมาได้คนละค่า
ถ้าเป็นแบบนั้น ผู้คนก็จะสำรองข้อมูลให้กันและกันได้ ขณะเดียวกันก็ยังมี การปฏิเสธอย่างสมเหตุสมผล เกี่ยวกับสิ่งที่ถูกเก็บไว้อยู่
ในวิทยานิพนธ์ปริญญาโทเคยนำ Shamir secret sharing ไปใช้กับ mesh network ด้วย เป็นวิธีที่แม้โหนดหนึ่งใน mesh จะถูกผู้โจมตียึดไปและดึงความลับของโหนดนั้นออกมาได้ ก็ยังไม่สามารถทำลายการเข้ารหัสทั้งหมดได้
ทีมของเราใช้เทคนิคนี้เพื่อกระจายรหัสผ่านของที่เก็บความลับสำรองในแบบที่ “ปลอดภัยแบบประชาธิปไตย” ที่เก็บสำรองนั้นมีวิธีเข้าถึงที่เก็บความลับหลักอยู่
https://packages.debian.org/trixie/ssss เป็น implementation ที่ใช้ได้ดีและค่อนข้างตรงไปตรงมา
Shamir เคยช่วยชีวิตไว้ครั้งใหญ่ครั้งหนึ่ง ต้องกู้แบ็กอัปเก่าที่แทบถูกลืมไปอย่างเร่งด่วน แล้วก็สามารถประกอบรหัสผ่านสุ่มที่ใช้ตอนนั้นกลับมาได้
ดีที่ตอนนั้นแบ่ง ชิ้นส่วนที่กระจายไว้ ให้คนในครอบครัวเก็บไว้ “เผื่อฉุกเฉิน”
ส่วนที่ว่า “ประโยชน์ของมันไม่ใช่ว่าถ้ามีชิ้นส่วนน้อยเกินไปจะคำนวณความลับได้ยาก แต่คือถ้ามีน้อยเกินไปจะไม่มีข้อมูลเกี่ยวกับความลับเลย ถ้าขาดไปหนึ่งชิ้น ทุกความลับที่เป็นไปได้ก็ยังเป็นไปได้เท่าเดิม” ทำให้นึกถึงกระบวนการแยกตัวประกอบจำนวนด้วย sieve quadratic หรือรูปแบบใกล้เคียง
เราหาระบบสมการที่สอดคล้องกันแบบ mod n แล้วสุดท้ายก็คำนวณตัวประกอบเฉพาะได้ แต่ก่อนจะมีมากพอก็ทำไม่ได้ แต่ละสมการก็น่าจะมีข้อมูลบางอย่างอยู่เสมอ เลยสงสัยมาตลอดว่าเรากำลังลดองศาอิสระในปริภูมิแบบไหน
ที่นี่ก็คล้ายกัน แต่ละชิ้นส่วนจำกัดปริภูมิของพหุนามลง แต่ยังจำกัดไม่พอที่จะบอกตำแหน่งที่คีย์ตัดแกนได้
เป็นเทคนิคที่เจ๋งมาก และเป็นตัวอย่างของสิ่งน่าสนใจที่นักวิทยาการคอมพิวเตอร์ทำได้ด้วยพหุนาม ถึงขั้นเอาไปสอนใน มัธยมศึกษา ได้เลย
ตอนสอนเรื่องการหาสมการเชิงเส้นกลับคืน จะยก Shamir มาด้วย แล้วให้นักเรียนกำหนด PIN ลับเป็นความชัน สร้างจุดสองจุด แล้วแจกให้เพื่อนอีกสองคน เพื่อนคู่นั้นต้องจับคู่กันเพื่อหา PIN กลับมา และนักเรียนมีส่วนร่วมกันมากทุกครั้ง
Bruce Schneier อธิบายเรื่องนี้ไว้ในหนังสือคลาสสิก Applied Cryptography และ HashiCorp Vault ก็เคยมี implementation ภาษา Go ด้วย ในทางปฏิบัติแล้วสงสัยมาตลอดว่าชิ้นส่วนที่กระจายควรมีกี่บิต
คำตอบที่เคยได้ยินในกลุ่มข่าวคือ “มากกว่าความยาวคีย์จริง 1 บิต” ทุกวันนี้ก็สงสัยว่าภัยคุกคามจาก quantum computing จะมีผลต่อ 1) การเลือกขนาดชิ้นส่วน และ 2) ข้อดีข้อเสียของ secret sharing โดยรวมอย่างไร
ถ้าสร้างชิ้นส่วน Shamir แบบ ‘threshold 10 จาก 10’ ให้กับความลับขนาด 1 ไบต์ แล้วให้ชิ้นส่วนขนาด 1 ไบต์ไป 9 ชิ้น ก็ไม่มีคอมพิวเตอร์ไหนในจักรวาลจะหาความลับได้ ใน implementation จริงมักต้องใส่ message authentication code หรือ checksum เพื่อตรวจสอบความถูกต้อง จึงใหญ่ขึ้นอีกไม่กี่ไบต์
Shamir secret sharing ปลอดภัยเชิงทฤษฎีสารสนเทศ ดังนั้นสำหรับความลับแบบ k-out-of-n ถ้ายังไม่มีจุดครบ k จุด ต่อให้ brute force ก็ยังทำให้ทุกความลับดูเป็นไปได้พอ ๆ กัน เพราะแบบนี้ ขนาดบิตของ field จะเลือกเท่าไรก็ได้ แต่แน่นอนว่าต้องใหญ่กว่าขนาดบิตของความลับ จะซ่อน 100 บิตไว้ใน finite field ที่มีแค่ 5 องค์ประกอบไม่ได้
ปกติแล้วต้องกันไม่ให้ผู้โจมตี brute force ตัวความลับเองได้ แม้ว่าวิธีนี้จะปลอดภัยเชิงทฤษฎีสารสนเทศ แต่ตัวความลับมักไม่ใช่ เช่น seed ของกระเป๋าเงิน จึงต้องเพิ่มความสุ่มให้ความลับและเลือกขนาดบิตของ field ให้ใหญ่พอเพื่อกันการโจมตีแบบนี้
แล้วแต่โมเดลภัยคุกคาม field ขนาด 80 บิตหรือ 128 บิตก็มักปลอดภัยพอ และขนาดชิ้นส่วนก็จะใหญ่กว่า 80 บิตหรือ 128 บิตเล็กน้อย สำหรับคอมพิวเตอร์ควอนตัม วิธีนี้ปลอดภัยเชิงทฤษฎีสารสนเทศอยู่แล้ว จึงไม่น่ามีการโจมตีได้
เพราะอย่างนั้น ถ้าจะสร้างแบบ n-of-k ก็สร้างพหุนามดีกรี n-1 ชื่อ p(x) แล้วสุ่มเลือกจุด k จุดจากพหุนามนั้น ชิ้นส่วนลำดับที่ i ก็คือ (xi, yi) เฉย ๆ ดังนั้นจำนวนบิตจึงขึ้นกับ field ที่ใช้สร้างพหุนาม
field ต้องกว้างพอจะบรรจุความลับทั้งหมดได้ และเพราะต้องเก็บทั้งค่า (x, y) ขนาดชิ้นส่วนจึงอย่างน้อยต้องเป็นสองเท่าของขนาดความลับ แต่ก็ยังต้องมีการตรวจสอบความถูกต้องเพื่อดูว่าชิ้นส่วนเสียหายหรือไม่
ความเข้าใจของฉันคือ quantum computing ไม่ได้เปลี่ยนอะไรตรงนี้เลย ถ้าขาดจุดไปแม้แต่จุดเดียว จุดสุดท้ายก็สามารถเปลี่ยนความลับให้เป็นอะไรก็ได้ และไม่มีทางแยกออก
ถ้าไม่ได้คาดว่าจะมีชิ้นส่วนจำนวนมหาศาล GF(2^8) ก็เป็นตัวเลือกที่ค่อนข้างเป็นธรรมชาติ และไม่ต้องยุ่งกับการคำนวณจำนวนเต็มขนาดใหญ่ด้วย
implementation ของ Ente อยู่ที่นี่: (https://2of3.ente.com/)
ตามอุดมคติคืออยากสร้างชุดแบบ
3 of 4: A B C Dหรือ2 of 3: E F Gและ1 of 1: Hได้อยากให้มีวิธีตั้งชื่อบนการ์ดด้วย เพื่อให้ชัดเจนว่าตอนกู้คืนต้องใช้อะไรบ้าง แน่นอนว่าความเรียบง่ายของดีไซน์ปัจจุบันก็มีข้อดีในตัวเอง
https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/
เมื่อหลายปีก่อนเคยทำเครื่องมือเล็ก ๆ สำหรับรัน Shamir secret sharing ในเบราว์เซอร์ ถ้าดาวน์โหลดหน้าเว็บไว้ก็ใช้แบบ ออฟไลน์ ได้เต็มรูปแบบ
https://simon-frey.com/s4/
จากนั้นก็แจกให้สมาชิกครอบครัวบางคนเก็บไว้ และบอกพวกเขาว่าถ้าฉันตายให้ส่งต่อให้ภรรยาของฉัน