fts encrypted
1.0.0
หมายเหตุ: โทเค็น หมายถึง โทเค็นคำศัพท์ ไม่ใช่ โทเค็นการเข้ารหัส ตัวอย่างเช่น tokenizer อาจเปลี่ยน 'เรียนรู้', 'การเรียนรู้', 'เรียนรู้' ทั้งหมดเป็นโทเค็น 'เรียนรู้'
หากคุณไม่ต้องการการเข้ารหัส Tantivy จะดีกว่าในทุก ๆ ด้าน
การสาธิต GUI ขั้นพื้นฐานโดยใช้ไดออกซัสและชุดอีเมล Enron มีอยู่ใน GitHub ของฉันที่นี่ เป็นหลักที่จะแสดงให้เห็นว่าความเร็วในการค้นหานั้นดีสำหรับประเภทของชุดข้อมูลที่เห็นที่เก็บไว้ในแอพพลิเคชั่นฝั่งไคลเอ็นต์
นี่ยังคงเป็นงานที่กำลังดำเนินอยู่ ไม่มีการรับประกันเกี่ยวกับห้องสมุดนี้หรือการพึ่งพาในการดำเนินการตามแนวคิดหรืออย่างอื่น ไม่มีการตรวจสอบความปลอดภัยใด ๆ ใช้ความเสี่ยงของคุณเอง
คำหลักแต่ละคำในการค้นหาหรือดัชนีจะถูกโทเค็น โทเค็นนี้และชื่อตารางที่เกิดขึ้นในนั้นถูกแฮชกับ Blake2B-128 จากนั้นเข้ารหัสด้วย AES-128-ECB ก่อนที่จะถูกเก็บไว้หรือใช้สำหรับการสืบค้น
Encrypt(Hash(token + table_name))
โหมด ECB ใช้สำหรับการเข้ารหัส ECB ทำให้ข้อความธรรมดาเหมือนกันเหมือนกัน แต่นี่ไม่ใช่ความกังวลสำหรับค่าที่ไม่ซ้ำกันเช่นแฮชของโทเค็นและชื่อตาราง ซึ่งหมายความว่าโทเค็นเดียวกันจะมี ciphertext ที่แตกต่างกันหากเกิดขึ้นในตารางแยกต่างหาก
รหัสเอกสารถูกเข้ารหัสด้วย AES-128-ECB สิ่งนี้เกี่ยวข้องกับเคาน์เตอร์ 32 บิต
เนื่องจากรหัสเอกสารปรากฏขึ้นหลายครั้งและจำนวนรหัสเอกสารมีขนาดเล็กกว่าที่สามารถระบุได้ด้วย 128 บิตรหัสเอกสารสามารถบีบอัดได้
สมมติว่ามีโทเค็น / เอกสารที่ไม่ซ้ำกัน 1,000 รายการค่าใช้จ่ายในการจัดเก็บโทเค็นที่เกิดขึ้นในเอกสารคือ:
| เอกสาร | ไม่เหมาะสม | 32 บิต |
|---|---|---|
| 1,000 | 16MB | 4MB |
| 10k | 160MB | 40MB |
| 50k | 800MB | 200MB |
| 100k | 1.6GB | 400MB |
| 250k | 4GB | 1GB |
| ล้าน | 16GB | 4GB |
| พันล้าน | 16TB | 4TB |
ความแตกต่างคือการแสดงค่าในลำดับเป็นความแตกต่างระหว่างพวกเขา สิ่งนี้จะสร้างค่าที่สามารถแสดงได้ด้วยบิตน้อยลงซึ่งช่วยให้ Bitpacking แน่นขึ้น
Bitpacking Crate ใช้สำหรับบล็อกที่แตกต่างและ bitpacking ของจำนวนเต็ม 128
ความแตกต่างทำงานได้ดีที่สุดเมื่อมีการจัดเรียงค่า แต่การรักษาค่าที่เรียงลำดับและ bitpacked จะต้องทำการเข้ารหัสค่าทั้งหมดอีกครั้งเมื่อมีการเพิ่มรายการตามลำดับ การใช้วิธีการตัดจำหน่ายโดยมีการรวบรวมค่าไม่สั่งซื้อสามารถลดค่าใช้จ่ายในการเปลี่ยนแปลงได้โดยการตัดจำหน่าย
| หมายเลขเลเยอร์ | รูปแบบการบรรจุ | การจัดเรียง | การกระจาย |
|---|---|---|---|
| 0 | ไม่มี - 32 บิต (<128 ints) | ไม่มี | เลขที่ |
| 1+ | bitpacker4x (128 ints) | เลเยอร์ amoung ทั่วโลกเหนือ 0 | ใช่ |
อีเมล Enron ที่สั้นกว่า 9,000-10,000 ฉบับถูกบีบอัดและขนาด DB FTS ที่ได้คือ 235MB โดยใช้การเข้ารหัส 32 บิต การใช้ความแตกต่างที่ตัดจำหน่ายและการบรรจุ bitpacking แบบเลเยอร์เปลี่ยนเป็น 21MB
การลบไฟล์คือ ... ราคาแพง ... ค่าตัดจำหน่ายสิ่งที่ต้องทำ
สิ่งที่ต้องทำ บางอย่างเช่น Rocksdb Memtable หรือ Sled จัดเก็บการเปลี่ยนแปลงในหน่วยความจำจากนั้นล้างทุก 500ms หรือเมื่อถึงขีด จำกัด ของหน่วยความจำ
Bucket Sort Words ด้วยอักขระ 3 หรือ 4 ตัวแรก (ไม่ใช่ tokenized), บีบอัด? และเข้ารหัส บล็อกเข้ารหัสด้วยบางสิ่งที่มีการแพร่กระจายเช่น CBC หรือ GCM (การเข้ารหัสที่ผ่านการรับรองความถูกต้อง) นี่จะหมายถึงการเติมข้อความอัตโนมัติจะเตะหลังจาก 3 หรือ 4 อักขระ นี่ยังอยู่ในขั้นตอนแนวคิด
ความสมบูรณ์ของข้อมูลเป็นทางเลือกโดยการแฮชไฟล์ฐานข้อมูลในเวลาใกล้เคียงและจัดเก็บแฮชเวอร์ชันที่เข้ารหัส
ไม่มีการแพร่กระจายของรหัสเอกสารที่เข้ารหัส การเพิ่มการแพร่กระจายจะต้องใช้รหัสเอกสารการเข้ารหัสโดยใช้ IV ที่สร้างขึ้นแบบสุ่ม สิ่งนี้จะทำให้การบีบอัดเป็นไปไม่ได้ การจัดเก็บ IV จะเพิ่ม 128 บิตต่อโทเค็นและคู่เอกสาร (สำหรับ AES CBC)
ผู้โจมตีต่อไปนี้สามารถมองเห็นได้โดยไม่มีกุญแจ:
ในกรณีของดัชนีในรายชื่อผู้ป่วยที่สำนักงานแพทย์ผู้โจมตีที่ไม่มีกุญแจจะเห็นจำนวนผู้ป่วยและการกระจายโทเค็นที่ใช้ภายในเอกสาร พวกเขาไม่สามารถเห็นข้อความธรรมดาใด ๆ เช่นชื่อหรือตัวระบุอื่น ๆ และพวกเขาไม่สามารถเห็นรหัสเอกสารของผู้ป่วยใด ๆ พวกเขาสามารถดูได้ว่าผู้ป่วยสองรายแบ่งปันโทเค็นการค้นหา แต่ไม่มีอะไรเกี่ยวกับผู้ป่วยหรือข้อมูลที่ใช้ร่วมกัน
ตัวอย่างเช่นหากดัชนีการค้นหาถูกสร้างขึ้นจากชื่อในประเทศที่มีนามสกุลทั่วไปเช่นเวียดนามคุณสามารถทำการวิเคราะห์ความถี่และหาจำนวนผู้ป่วยที่มีนามสกุล Nguyen (38% ของประชากรเวียดนาม) สิ่งนี้ขึ้นอยู่กับ (การกระจายนามสกุล) ก่อนหน้านี้ของคุณนั้นถูกต้องสำหรับชุดข้อมูลที่อยู่ในมือ นอกจากนี้ยังจะมีผลบังคับใช้กับชื่อสามัญเท่านั้นซึ่งไม่ได้ระบุและไม่น่าจะแยกแยะเอกสารที่มีความมั่นใจแม้กระทั่งชื่อที่สองจากนามสกุลที่พบบ่อยที่สุดในเวียดนาม (Tran ที่ 11% และ LE ที่ 10%)
มีการเพิ่มข้อมูลเพิ่มเติมลงในดัชนีการค้นหาเช่นอายุบ้านเกิดที่อยู่คำอธิบาย ฯลฯ ความสามารถในการวิเคราะห์ความถี่จะหายไปอย่างแท้จริง
ข้อกังวลประการหนึ่งอาจไม่ใช่การปฏิเสธการจัดเก็บชุดข้อมูลที่ไม่ซ้ำกันซึ่งการวิเคราะห์ความถี่ของชุดข้อมูลธรรมดาขนาดใหญ่ที่รู้จักกันสามารถนำมาใช้เพื่อแสดงให้เห็นว่าปราศจากข้อสงสัยที่สมเหตุสมผลอุปกรณ์ที่กำหนดมีชุดข้อมูลนั้นจัดทำดัชนี สิ่งนี้ดูเหมือนจะส่งผลกระทบต่อผู้คัดค้านในประเทศเผด็จการหรืออาชญากรเท่านั้น สิ่งนี้สามารถบรรเทาได้ด้วยการเข้ารหัสดิสก์เต็มเมื่ออุปกรณ์ปิด
ให้ d1 เป็นเอกสารที่มีโทเค็น t1 ให้ t2 เป็นโทเค็นที่แฮชชนกับ t1 และไม่ใช่โทเค็นของเอกสาร d1
ผลบวกปลอมซึ่งผลลัพธ์ที่ไม่เกี่ยวข้องเพิ่มเติมรวมอยู่ในผลการค้นหาสามารถเกิดขึ้นกับ d1 ได้หากการค้นหามี t2 และไม่ใช่ t1
เชิงลบที่ผิดพลาดซึ่งผลลัพธ์ที่เกี่ยวข้องถูกละเว้นจากผลการค้นหาสามารถเกิดขึ้นได้ก็ต่อเมื่อหนึ่งในโทเค็นการชนถูกลบสำหรับเอกสาร ซึ่งจะส่งผลให้โทเค็นอื่นเป็น "ลบ" เช่นกัน
ผลบวกหรือเชิงลบที่ผิดพลาดจะใช้กับเอกสารที่มีโทเค็นการชนกันอย่างใดอย่างหนึ่งเมื่อโทเค็นชนกันอื่น ๆ อยู่ในข้อความค้นหา สิ่งนี้ทำให้เงินเดิมพันของการชนกันต่ำมาก
ความเสี่ยงที่แท้จริงของการปะทะกันนั้นมีขนาดเล็กอย่างตลกสำหรับแฮช 128 บิต (ดูปัญหาวันเกิดบนวิกิพีเดีย)
การเข้ารหัส 64 บิตส่งผลให้ประหยัดพื้นที่เพียงไม่กี่เมกะไบต์สำหรับดัชนีขนาดใหญ่มาก ภาษาอังกฤษมีประมาณ 1,000,000 คำและโทเค็นน้อยลง 64 ล้านบิตเป็นเพียง 8MB เมื่อพิจารณาจากการแจกแจงประเภทกฎหมายพลังงานที่เห็นในภาษาที่คำชั้นบนร้อยคำหรือมากกว่านั้นอาจประกอบด้วยครึ่งหนึ่งของความถี่การออมจริงจะน้อยกว่ามาก
