เหตุใดการใช้งานจึงเกี่ยวข้องกับการโจมตีแบบกำหนดเวลา

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

การชี้แจง - บริบทคือการเซ็นชื่อแบบเข้ารหัสของข้อความที่ไม่เป็นความลับ

คำตอบเริ่มต้นของ @ poncho ระบุว่าผู้โจมตีไม่ได้มีความหรูหราในการพิจารณาการใช้งาน "ของผู้ใช้" เสมอไป

อันที่จริง ฉันสนใจคำถามนี้ในสถานการณ์จริงที่ผู้โจมตีเป็นผู้ใช้ และมีความสามารถในการเลือกการใช้งานของตนเอง - ในการเซ็นชื่อแบบเข้ารหัสของข้อความที่ไม่เป็นความลับ การอ้างอิงของฉันด้านล่างเกี่ยวกับ NaCl ซึ่งรวมถึงการใช้งาน ed25519 ในกรณีการใช้งานที่ฉันกำลังดำเนินการ คุณสามารถสันนิษฐานได้ว่า "ผู้โจมตี" / ผู้ใช้มีข้อความธรรมดา ลายเซ็น และรหัสสาธารณะ ทั้งสามอย่างนี้จำเป็นสำหรับลายเซ็นที่จะมีประโยชน์ด้วยซ้ำ สิ่งเดียวที่พวกเขาขาดคือคีย์ส่วนตัว

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

เช่น.

• หากอัลกอริทึมไม่สามารถระบุความถูกต้องทางคณิตศาสตร์ของชุดอินพุตได้จนกว่าจะถึงขั้นตอนสุดท้าย ก็จะไม่ถูกโจมตีโดยเวลา ฉันเข้าใจว่าอัลกอริทึม SHA ที่ NIST อนุมัติทั้งหมด ณ วันที่ FIPS-180-4 อยู่ในกลุ่มนี้
• หากอัลกอริทึมสามารถระบุอินพุตที่ไม่ถูกต้องทางคณิตศาสตร์ในทุกๆ ไบต์/คำ/บล็อกที่เพิ่มขึ้นของการประมวลผลสตรีมบางรายการ แสดงว่ามีความอ่อนไหวอย่างมากต่อการถูกโจมตีด้วยจังหวะเวลา
• ในกรณีที่เลวร้ายที่สุด จำนวนการดำเนินการขั้นต่ำที่จำเป็นในการระบุความสำเร็จหรือความล้มเหลวขึ้นอยู่กับแต่ละบิตที่เพิ่มขึ้นในรหัสลับ

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

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

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

ฉันพลาดอะไรไปหรือเปล่า

ข้อมูลอ้างอิง: แดเนียล เบิร์นสไตน์ / NaCl

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

ไม่มีสาขาที่ขึ้นกับข้อมูล

... วรรณกรรมมีตัวอย่างมากมายที่ประสบความสำเร็จ การโจมตีตามเวลา ที่แยกรหัสลับจากส่วนเหล่านี้ของ CPU NaCl หลีกเลี่ยงการไหลของข้อมูลทั้งหมดอย่างเป็นระบบจากข้อมูลลับไปยังตัวชี้คำสั่งและตัวทำนายสาขา

ไม่มีดัชนีอาร์เรย์ที่ขึ้นกับข้อมูล

... วรรณกรรมมีตัวอย่างที่ประสบความสำเร็จมากมาย การโจมตีแคชไทม์ ที่ใช้ข้อมูลลับรั่วไหลไปตามที่อยู่ NaCl หลีกเลี่ยงการไหลของข้อมูลทั้งหมดอย่างเป็นระบบจากข้อมูลลับไปยังที่อยู่ที่ใช้ในคำแนะนำในการโหลดและคำแนะนำในการจัดเก็บ

นี่ควรเป็นความคิดเห็น (ยาว) แต่ฉันไม่มีที่ว่าง มีไว้เพื่ออธิบายว่าทำไมแนวคิดในการปล่อยให้ผู้โจมตีเลือกการใช้งานพื้นฐานนั้นแข็งแกร่งเกินไป --- มัน "เล็กน้อย" ทำลายสิ่งดั้งเดิมใดๆ

สำหรับการเข้ารหัสแบบดั้งเดิม หากผู้โจมตีต้องการแยกคีย์ $k\in \{0,1\}^n$ สำหรับบางคน $n$และสามารถ:

1. เลือกข้อความโดยพลการ (อย่างน้อยข้อความที่อยู่ใน $\{0,\จุด,n-1\}$) ในสิ่งที่ดั้งเดิมอยู่ภายใต้การพิจารณา

2. แก้ไขโดยพลการ การนำไปใช้งาน ของอัลกอริทึม (แต่ไม่ใช่พฤติกรรมอินพุต-เอาต์พุตของฟังก์ชันทางคณิตศาสตร์ที่อัลกอริทึมนำไปใช้)

3. สามารถเข้าถึงวิธีการวัดคุณภาพใด ๆ เพื่อวัดเวลาได้เลย

มันค่อนข้างง่ายที่จะแก้ไขการใช้งานอัลกอริทึมเพื่อรั่วไหลของรหัสลับทั้งหมด $n$ แบบสอบถาม ถ้า $\mathcal{O}(k, m)$ เป็นดั้งเดิม "เก่า" กำหนดดั้งเดิม "ใหม่" ผ่าน:

O'(k, เมตร)
    ถ้า m ใน {0,...,n-1} และ k[m] == 1:
        รอ (T)
    กลับ O(k, m)

ในที่นี้ T คือค่าคงที่ที่ไม่ระบุซึ่ง "ใหญ่พอ" เพื่อให้ผู้โจมตีสามารถวัดความแตกต่างระหว่างอัลกอริทึมที่รับได้อย่างน่าเชื่อถือ $\ll T$ เวลา หรือ $\ประมาณ T$ เวลาดำเนินการ $\mathcal{O}'$ มีพฤติกรรมอินพุต - เอาท์พุตเหมือนกันอย่างชัดเจน $\mathcal{O}$.

ตัวอย่างข้างต้นควรแสดงให้เห็นว่าการปล่อยให้ผู้โจมตีเลือกการดำเนินการคือ มโหฬาร ปัญหาด้านความปลอดภัย แม้ว่าจะมีการจำกัดการใช้งานให้มีพฤติกรรมอินพุต/เอาต์พุตเหมือนกันทุกประการกับฟังก์ชันที่ต้องการ ด้วยเหตุนี้ คำว่า "ไวต่อการโจมตีทางคณิตศาสตร์ในทางคณิตศาสตร์" จึงไม่ได้รับการนิยามที่ชัดเจน เนื่องจาก ใดๆ อัลกอริทึมที่อาศัยข้อมูล "ลับ" นั้นไวต่อการโจมตีข้างต้น

นี่ไม่ใช่ปัญหาจริงๆ เนื่องจากการปล่อยให้ผู้โจมตีเลือกอัลกอริทึมที่ใช้จะไม่ถือเป็นปัญหาใหญ่ในทางปฏิบัติ (ครั้งเดียวที่อาจเกิดขึ้นจริงๆ คือในการโจมตีประเภท "backdooring Standard Committee" พูดว่าเกิดอะไรขึ้นกับ DUEL_EC_DRBG แต่ไทม์มิ่งแบ็คดอร์ดูแย่กว่าแบ็คดอร์ "ฉันรู้กุญแจลับ" เนื่องจากคนอื่นอาจสังเกตไทม์มิ่งแบ็คดอร์ได้ง่ายกว่า)

ในขณะที่ "ไวต่อการถูกโจมตีด้วยจังหวะเวลา" นั้นไม่ได้กำหนดไว้อย่างชัดเจน แต่ก็มีสิ่งดั้งเดิมที่ยากกว่าที่จะนำไปใช้ในวิธีคงที่ของเวลา โดยทั่วไปหมายถึงหนึ่งในสองสิ่ง:

1. ค่าใช้จ่ายในการเปลี่ยนจากเวลาไม่คงที่เป็นเวลาคงที่นั้นมีมาก
2. มันง่ายที่จะผิดพลาดในการเปลี่ยนแปลงจากเวลาที่ไม่คงที่เป็นเวลาคงที่

สิ่งเหล่านี้ไม่ใช่คุณสมบัติของปัญหาที่เป็นทางการ แต่เป็นการสังเกตเชิงประจักษ์ของผู้ปฏิบัติงานแทน ปัญหาแรกอาจสามารถทำให้เป็นทางการได้ (โดยเฉพาะในช่องว่างขนาดใหญ่ระหว่างวงจรขนาดต่ำสุดที่คำนวณบางสิ่งและ TM ขนาดต่ำสุดในโมเดล RAM ที่คำนวณบางอย่าง) แต่ปกติแล้วฉันไม่เห็นคนพยายามทำสิ่งนี้ (ดูเหมือนว่าจะไม่น่าสนใจสำหรับผู้ดำเนินการ)

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

การดำเนินการมีความเกี่ยวข้องค่อนข้างมาก อัลกอริทึมใด ๆ ที่เสร็จสิ้นในเวลาที่มีขอบเขตสามารถนำไปใช้ในลักษณะการเข้าถึงเวลาคงที่ / หน่วยความจำคงที่ ดังนั้นอัลกอริธึมใดๆ ดังกล่าวจึงสามารถนำไปใช้ได้อย่างปลอดภัยต่อการโจมตีช่องทางด้านข้างเหล่านี้ แน่นอนว่าอัลกอริธึมบางอย่างทำให้การใช้งานนั้นง่าย และบางอัลกอริธึมทำให้มีค่าใช้จ่ายค่อนข้างสูง

หากอัลกอริทึมไม่สามารถระบุความถูกต้องทางคณิตศาสตร์ของชุดอินพุตได้จนกว่าจะถึงขั้นตอนสุดท้าย ก็จะไม่ถูกโจมตีโดยเวลา

จริงๆ แล้ว การดำเนินการอาจใช้เวลาขึ้นอยู่กับคีย์ลับหรือค่ากลางของความลับ

หากอัลกอริทึมสามารถระบุอินพุตที่ไม่ถูกต้องทางคณิตศาสตร์ในทุกๆ ไบต์/คำ/บล็อกที่เพิ่มขึ้นของการประมวลผลสตรีมบางรายการ แสดงว่ามีความอ่อนไหวอย่างมากต่อการถูกโจมตีด้วยจังหวะเวลา

ไม่; การดำเนินการอาจตัดสินใจยกเลิกก่อนกำหนด หรืออาจตั้งค่าสถานะ 'ล้มเหลว' ภายในและดำเนินการต่อ (และในตอนท้าย ให้สังเกตว่ามีการตั้งค่าสถานะล้มเหลว และจัดการกับความล้มเหลว ณ จุดนั้น) และใช่ การตั้งค่าของ การตั้งค่าสถานะที่ล้มเหลวสามารถทำได้ในเวลาคงที่ การใช้แฟล็กที่ล้มเหลวซึ่งมีการตรวจสอบในตอนท้ายเป็นเรื่องปกติธรรมดาสำหรับการใช้งานแบบคงที่ตลอดเวลา

ผู้โจมตีที่มีเหตุผลจะเลือกใช้การดำเนินการที่จงใจไวต่อการโจมตีตามเวลา

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

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

ไม่ มันไม่จริง; คุณสามารถแนะนำรูปแบบเวลาที่ไม่เกี่ยวข้องกับความถูกต้องหรือไม่ถูกต้องได้อย่างง่ายดาย

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

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