ภัยคุกคามจากการรั่วไหลของรูปแบบการเข้าถึง

การเข้ารหัสข้อมูลช่วยปกป้องเนื้อหาจากฝ่ายที่ไม่ได้รับอนุญาต แต่การเข้ารหัสเพียงอย่างเดียวไม่สามารถซ่อนข้อมูลเมตาเกี่ยวกับวิธีการเข้าถึงข้อมูลได้ รูปแบบการเข้าถึง เช่น ระเบียนใดถูกอ่านหรือเขียน เมื่อใด และบ่อยเพียงใด อาจเปิดเผยข้อมูลที่มีความอ่อนไหวได้ แม้ข้อมูลนั้นจะถูกเข้ารหัสอย่างสมบูรณ์ก็ตาม ช่องว่างระหว่างความเป็นส่วนตัวของเนื้อหากับความเป็นส่วนตัวของการเข้าถึงนี้คือแรงจูงใจหลักของ RAM แบบปกปิดรูปแบบการเข้าถึง

การวิเคราะห์รูปแบบการเข้าถึงอาจเปิดเผยสิ่งต่อไปนี้: ระเบียนฐานข้อมูลที่ผู้ใช้ค้นหา (ทำให้อนุมานภาวะทางการแพทย์ได้จากระเบียนที่ผู้ใช้เข้าถึง) รูปแบบการสื่อสาร (ใครติดต่อใคร แม้เนื้อหาข้อความจะถูกเข้ารหัส) กิจกรรมทางการเงิน (ทำให้อนุมานกลยุทธ์การซื้อขายได้จากราคาที่ผู้ใช้ร้องขอ) และรูปแบบพฤติกรรม (กิจวัตรประจำวันจากเวลาและความถี่ในการเข้าถึง) การอนุมานเหล่านี้อาจมีความอ่อนไหวไม่ต่างจากเนื้อหาของข้อมูลเอง

CryptDB (MIT, 2011) เป็นระบบที่มีอิทธิพลต่อวงการสำหรับค้นหาข้อมูลในฐานข้อมูลที่เข้ารหัส งานวิจัยต่อมาโดย Grubbs, McPherson, Naveed, Ristenpart และ Spooner (2016) แสดงให้เห็นว่า CryptDB และรูปแบบการเข้ารหัสที่รักษาลำดับในลักษณะเดียวกันรั่วไหลรูปแบบการเข้าถึง ซึ่งเปิดทางให้เกิดการโจมตีเพื่ออนุมาน ผู้โจมตีที่มีชุดข้อมูลเสริมเกี่ยวกับการกระจายของการเข้าถึงสามารถอนุมานค่าข้อความต้นฉบับจากความถี่และลำดับการเข้าถึงเพียงอย่างเดียวได้ แม้จะไม่สามารถทำลายการเข้ารหัสได้ก็ตาม

หากบริการที่เก็บข้อมูลคลาวด์แบบเข้ารหัสบันทึกว่ามีการเข้าถึงบล็อกข้อความเข้ารหัสใดบ้าง ผู้โจมตีสามารถทำการวิเคราะห์ความถี่ได้ เนื่องจากผู้ใช้มักเข้าถึงไฟล์ยอดนิยมบ่อยกว่า ฮิสโตแกรมความถี่การเข้าถึงของบล็อกข้อความเข้ารหัสจึงสะท้อนการกระจายการเข้าถึงข้อความธรรมดา การจับคู่ฮิสโตแกรมความถี่เข้ารหัสกับรูปแบบการเข้าถึงที่ทราบอยู่แล้วสามารถระบุได้ว่าไฟล์เข้ารหัสใดสอดคล้องกับหมวดหมู่เนื้อหายอดนิยม

ในแบบจำลองภัยคุกคามแบบซื่อสัตย์แต่ใฝ่รู้ (กึ่งซื่อสัตย์) ผู้ให้บริการคลาวด์จะปฏิบัติตามโพรโทคอลอย่างถูกต้อง แต่สังเกตรูปแบบการเข้าถึงข้อมูลของไคลเอนต์ทั้งหมด ผู้ให้บริการคลาวด์หลายรายบันทึกรูปแบบการเข้าถึงอย่างถูกต้องตามวัตถุประสงค์ เพื่อเรียกเก็บเงิน แก้จุดบกพร่อง และเพิ่มประสิทธิภาพการทำงาน แม้ไม่มีเจตนาร้าย บันทึกเหล่านี้ก็สร้างความเสี่ยงขึ้นมาได้ กล่าวคือ ผู้ให้บริการคลาวด์ที่ถูกเจาะระบบ พนักงานที่ทุจริต หรือหมายเรียกจากรัฐบาลอาจทำให้รูปแบบการเข้าถึงที่ละเอียดอ่อนถูกเปิดเผย

RAM แบบไม่เปิดเผย (ORAM) ซึ่ง Goldreich และ Ostrovsky นำเสนอในปี 1996 เป็นพื้นฐานทางวิทยาการเข้ารหัสลับที่ซ่อนรูปแบบการเข้าถึงจากเซิร์ฟเวอร์ ในรูปแบบ ORAM การเข้าถึงทุกครั้ง ไม่ว่าจะเป็นการอ่านหรือการเขียนไปยังตำแหน่งหน่วยความจำใด ๆ จะก่อให้เกิดการกระจายของการดำเนินการที่เซิร์ฟเวอร์มองเห็นได้เหมือนกัน โดยไม่ขึ้นอยู่กับว่ากำลังเข้าถึงตำแหน่งใดอยู่จริง ผู้โจมตีที่สังเกตเซิร์ฟเวอร์จะเห็นเพียงรูปแบบการเข้าถึงที่สุ่มอย่างสม่ำเสมอ

ORAM มีการประยุกต์ใช้ในวงกว้างทุกกรณีที่ต้องการความเป็นส่วนตัวของรูปแบบการเข้าถึง ได้แก่ ที่เก็บข้อมูลคลาวด์แบบปลอดภัย (ซ่อนว่าเข้าถึงไฟล์ใด) คำค้นฐานข้อมูลแบบไม่เปิดเผย (ซ่อนว่าแถวใดถูกส่งกลับจากคำค้น) เอนเคลฟ SGX (ป้องกันช่องทางข้างเคียงของรูปแบบการเข้าถึงหน่วยความจำในเอนเคลฟ) การดึงข้อมูลแบบรักษาความเป็นส่วนตัว (ซ่อนว่าผู้ใช้ดึงรายการใดจากฐานข้อมูล) และการคำนวณหลายฝ่ายแบบปลอดภัย (ซ่อนรูปแบบการเข้าถึงสถานะระหว่างการคำนวณ)

วิธีแก้ปัญหา ORAM ที่ง่ายที่สุดตรงไปตรงมาอย่างเห็นได้ชัด นั่นคือ เมื่อจะเข้าถึงบล็อกใดบล็อกหนึ่ง ให้อ่านและเขียนกลับใหม่ทุกบล็อกในพื้นที่จัดเก็บทั้งหมด วิธีนี้ซ่อนว่ามีการเข้าถึงบล็อกใด (เพราะการเข้าถึงทุกครั้งดูเหมือนกัน) แต่มีค่าใช้จ่ายด้านการสื่อสาร O(n) ต่อการเข้าถึงเชิงตรรกะหนึ่งครั้ง จึงไม่สามารถใช้งานได้จริงกับชุดข้อมูลขนาดใหญ่โดยสิ้นเชิง รูปแบบ ORAM จริงจึงมุ่งลดค่าใช้จ่ายนี้ลงเหลือ O(polylog n) ขณะที่ยังคงความไม่เปิดเผยอย่างสมบูรณ์แบบหรือเชิงสถิติ

Goldreich และ Ostrovsky พิสูจน์ขอบเขตล่างไว้ว่า ORAM ใด ๆ ที่มีค่าใช้จ่ายด้านพื้นที่จัดเก็บบนเซิร์ฟเวอร์ O(1) จะต้องมีค่าใช้จ่ายด้านการสื่อสารอย่างน้อย Omega(log n) ต่อการเข้าถึงหนึ่งครั้ง ขอบเขตล่างแบบลอการิทึมนี้ใช้กับ ORAM แบบกำหนดแน่นอน การสร้างที่ใช้งานได้จริงมุ่งให้มีค่าใช้จ่าย O(log^2 n) หรือ O(log n) ซึ่งใกล้เคียงกับค่าต่ำสุดเชิงทฤษฎีนี้ ขอบเขตล่างดังกล่าวแสดงให้เห็นว่าการซ่อนรูปแบบการเข้าถึงอย่างสมบูรณ์ย่อมมีต้นทุนที่หลีกเลี่ยงไม่ได้

การเข้ารหัสสมมาตรที่ค้นหาได้ (SSE) ช่วยให้ค้นหาข้อมูลที่เข้ารหัสได้ รูปแบบ SSE พื้นฐานเปิดเผยรูปแบบการค้นหา (มีการค้นหาคำสำคัญใด) และรูปแบบการเข้าถึง (มีการส่งเอกสารใดกลับมา) SSE แบบรักษาความเป็นส่วนตัวไปข้างหน้าจะซ่อนรูปแบบการค้นหาสำหรับเอกสารใหม่ แต่ต้องใช้ ORAM เพื่อซ่อนเพิ่มเติมว่าเอกสารใดถูกเข้าถึง การผสาน SSE เข้ากับ ORAM ให้หลักประกันด้านความเป็นส่วนตัวที่แข็งแกร่งที่สุด แต่ต้องแลกด้วยต้นทุนด้านประสิทธิภาพที่สูงมาก

ORAM ไม่จำเป็นต้องใช้เสมอไป การตัดสินใจขึ้นอยู่กับแบบจำลองภัยคุกคาม กล่าวคือ ผู้โจมตีสังเกตรูปแบบการเข้าถึงได้หรือไม่ สำหรับพื้นที่จัดเก็บข้อมูลภายในเครื่องที่ใช้การเข้ารหัสดิสก์ทั้งชุดและมีผู้โจมตีระยะไกล อาจไม่จำเป็นต้องใช้ ORAM แต่สำหรับที่เก็บข้อมูลคลาวด์ซึ่งผู้ให้บริการคลาวด์ไม่ได้รับความไว้วางใจ ORAM เป็นทางเลือกที่เหมาะสม ค่าใช้จ่ายด้านแบนด์วิดท์ (โดยทั่วไปอยู่ที่ 20-50 เท่า) คุ้มค่าเมื่อการรั่วไหลของรูปแบบการเข้าถึงเป็นภัยคุกคามที่มีอยู่จริง และความละเอียดอ่อนของข้อมูลทำให้ต้นทุนดังกล่าวสมเหตุสมผล

การเข้ารหัสเนื้อหาข้อมูลไม่ได้ซ่อนรูปแบบการเข้าถึง ซึ่งอาจเปิดเผยข้อมูลละเอียดอ่อนผ่านการวิเคราะห์ความถี่และเวลา ผู้ให้บริการคลาวด์ในแบบจำลองแบบซื่อสัตย์แต่ใฝ่รู้จะสังเกตได้ว่าไคลเอนต์เข้าถึงบล็อกข้อความเข้ารหัสใด การโจมตี CryptDB แสดงให้เห็นว่าสามารถอนุมานข้อมูลจากรูปแบบการเข้าถึงในฐานข้อมูลเข้ารหัสได้จริง ORAM แก้ปัญหานี้ด้วยการทำให้การเข้าถึงทุกครั้งดูเหมือนกันสำหรับเซิร์ฟเวอร์ วิธีแก้ปัญหาแบบง่ายตรงไปตรงมา (อ่านทุกอย่างในการเข้าถึงแต่ละครั้ง) มีค่าใช้จ่าย O(n) จนไม่สามารถใช้งานได้จริง ส่วน ORAM จริงทำได้ที่ค่าใช้จ่าย O(log^2 n)