ฉันต้องการเข้าใจพีชคณิตที่อยู่เบื้องหลังความปลอดภัยของ GCM ก่อนที่ฉันจะถามคำถาม ให้ฉันระบุความเข้าใจของฉันเกี่ยวกับคณิตศาสตร์เบื้องหลัง GCM ถ้าถูกต้อง คำถามของฉันก็จบลงแล้ว ถ้าไม่ถูกต้อง คุณช่วยอธิบายข้อผิดพลาดของฉันได้ไหม
เพื่อความง่าย ให้ถือว่าไซเฟอร์เท็กซ์เพียงบล็อกเดียว $ค$. เราต้องการให้แท็กของเรามีสองคุณสมบัติ:
$tag_k(ค)$ ควรเป็นแฮชเครื่องแบบสากลของ $ค$: นั่นคือสำหรับทุกคน $ค$, ถ้า $k$ เป็นแบบสุ่มอย่างสม่ำเสมอ $P[tag_k(c) = y]$ เป็นชุดเดียวกันสำหรับทุกคน $y$.
$tag_k(ค)$ ไม่ควรเปิดเผยข้อมูลเกี่ยวกับ $k$แม้กระทั่งเมื่อ $ค$ เป็นที่รู้จัก
พร็อพเพอร์ตี้ 1 พึงพอใจอย่างง่ายดายโดยการคูณด้วยค่าที่ไม่ใช่ศูนย์ $k$ ใน $GF(2^n)$ตั้งแต่ใน $GF(2^n)$, $f(x) = ขวาน$ เป็นการเปลี่ยนแปลงที่ไม่เหมือนใครสำหรับทุกคน $a \n 0$, และ $f$ จึงเป็นแฮชเครื่องแบบสากล
อย่างไรก็ตามทรัพย์สิน 2 จะ ไม่ พึงพอใจโดย $tag_k(ค) = kc$เนื่องจากเราสามารถคำนวณ $c{^-1}$ และแก้ปัญหา $k = tag_k(c)c^{-1}$. เพื่อให้ตรงกับคุณสมบัติ 2 เราขอแนะนำ "รหัสลับ" $c_0$และกำหนด $tag_k(c) = kc + c_0$ (นอกจากนี้ยังเป็น XOR ระดับบิตใน $GF(2^n)$). $c_0$ ทำงานได้อย่างมีประสิทธิภาพเป็นแพดแบบใช้ครั้งเดียวเพื่อเข้ารหัสแท็ก "รูท" $kc$.
ถ้าเราต้องการพิสูจน์ตัวตนของไซเฟอร์เท็กซ์สองบล็อกล่ะ เราสามารถทำขั้นตอนนั้นซ้ำได้ โดยต้องแน่ใจว่าใช้อันใหม่ $c_0$ แต่ละครั้ง. ในทางปฏิบัติ AES-GCM ใช้ c_0 = AES_k (เคาน์เตอร์ ++).
อย่างไรก็ตาม เมื่อตรวจสอบสิทธิ์หลายบล็อกพร้อมกัน สิ่งนี้จะไม่มีประสิทธิภาพ แทนที่เราสามารถใช้ หนึ่ง แท็กสำหรับ cipherblocks หลายอัน โดยใช้สูตรนี้:
$$tag_k(c_1, c_2,...c_n) = kc_0 + \sum k^nc_n.$$ (เพื่อความง่าย ฉันจะละเว้นฟิลด์ความยาวและข้อความธรรมดาที่รับรองความถูกต้อง) สิ่งนี้จะรักษาคุณสมบัติทั้งสองไว้
เราอาจถูกล่อลวงให้ลดความซับซ้อนลง $\sum kc_n$แต่สิ่งนี้ล้มเหลวเนื่องจากเราสามารถแทนที่ได้ $c_a, c_b$ กับ $fake_a, fake_b$ ตราบเท่าที $fake_a + fake_b = c_a + c_b$. ตัวอย่างเช่น เราสามารถพลิกบิตในบล็อกรหัสใดๆ ก็ได้ ตราบใดที่เราพลิกบิตที่เกี่ยวข้องในบล็อกอื่น (การโจมตีประเภทนี้ใช้กับ WEP ซึ่งใช้ CRC เป็น "MAC")
ที่สำคัญกว่านั้น เราจะหลีกเลี่ยงโหมดความล้มเหลวที่ชัดเจนต่อไปนี้ได้อย่างไร:
ตัวอย่างเช่น ลองนึกภาพ $k$ มีคำสั่งที่ 2 จากนั้นเราพลิกกลับเล็กน้อย $c_1$ ตราบใดที่เราพลิกบิตเดียวกัน $c_3$, เนื่องจาก $$\begin{จัด} k^2c_1 + k^4c_3 &= k^2(c_1 + c_3) \ &= k^2(c_1 + c_3 + d + d) \ &= k^2(c_1 + d) + k^4(c_3 + d)\end{จัดตำแหน่ง}.$$ GCM หลีกเลี่ยงโหมดความล้มเหลวนี้ได้อย่างไร
ฉันต้องการเข้าใจพีชคณิตที่อยู่เบื้องหลังความปลอดภัยของ GCM
คุณได้เขียนกลไกการทำงานของการตรวจสอบสิทธิ์ของ GCM แล้ว อย่างไรก็ตาม เพื่อทำความเข้าใจว่าเหตุใดกลไกเหล่านั้นจึงทำงานได้ จะเป็นการดีหากใช้วิธีอื่น
GCM ใช้เลขคณิตใน $GF(2^{128})$; มันคือ สนาม; ประเด็นสำคัญก็คือ ในฟิลด์หนึ่งๆ พหุนามของดีกรีที่ไม่ใช่ศูนย์ใดๆ $n$ มีมากที่สุด $n$ ศูนย์; นั่นคือสำหรับสมการใดๆ:
$$a_n x^n + a_{n-1} x^{n-1} + ... + a_0 x^0 = 0$$
มีมากที่สุด $n$ โซลูชั่นสำหรับ $x$ (สมมติว่าอย่างน้อยหนึ่งใน $a_i$ ค่าไม่เป็นศูนย์)
เหตุใดสิ่งนี้จึงสำคัญจะชัดเจนในภายหลัง
ตอนนี้ สิ่งที่ GCM ทำเพื่อตรวจสอบความถูกต้องคือใช้ข้อมูลที่เข้ารหัส (และ AAD) และแปลเป็นพหุนาม จากนั้นจะแปลง nonce เป็นค่าคงที่ของพหุนาม จากนั้นประเมินพหุนามนั้นด้วยค่าลับ $k$และผลลัพธ์ของการประเมินนั้นคือแท็ก นั่นคือ:
$$tag := a_n k^n + a_{n-1} k^{k-1} + ... + a_1 k^1 + \text{hash}(ไม่มี)$$
ตอนนี้ สมมติว่าเรามีคู่ข้อความ/แท็กที่แตกต่างกันสำหรับ nonce เดียวกัน ข้อความ/แท็กนั้นจะผ่านการตรวจสอบความสมบูรณ์ของ GCM หาก:
$$tag' := a'_n k^n + a'_{n-1} k^{k-1} + ... + a'_1 k^1 + \text{hash}(ไม่มี)$$
สิ่งที่เราทำได้คือลบพหุนามสองชื่อออก (อันที่สอดคล้องกับข้อความเข้ารหัสที่ดีที่สร้างโดยตัวเข้ารหัสที่ถูกต้อง และอันที่สอดคล้องกับการเดาโดยผู้โจมตี) เราจะได้ [1]:
$$0 = (a_n-a'_n)k^n + (a_{n-1} - a'_{n-1})k^{n-1} + ... + (a_1 - a'_1) k^1 + (แท็ก - แท็ก')k^0$$
สมการนี้จะคงอยู่ก็ต่อเมื่อคู่ไซเฟอร์เท็กซ์/แท็กที่สองถูกต้องเท่านั้น
ตอนนี้ เรากลับไปที่การสังเกตเดิมของเรา นี่คือพหุนามของดีกรีเป็นส่วนใหญ่ $n$ และมีมากที่สุด $n$ ค่าต่างๆของ $k$ ซึ่งสมการนี้เป็นจริง เรายังทราบด้วยว่าอย่างน้อยหนึ่งค่าสัมประสิทธิ์ของพหุนามนั้นไม่เป็นศูนย์ (พหุนามที่เป็นศูนย์ทั้งหมดจะเป็นจริงหากไซเฟอร์เท็กซ์ที่ 'ปลอมแปลง' นั้นเหมือนกับค่าที่ถูกต้องทุกประการ ซึ่งไม่ถือว่าเป็นการปลอมแปลง) และถ้า $k$ ถูกเลือกอย่างคาดเดาไม่ได้ก็มี $2^{128}$ ค่าที่เป็นไปได้ และความน่าจะเป็นที่จะเป็นหนึ่งในนั้น $n$ ค่าสูงสุด $n2^{-128}$ซึ่งเล็กมากจริงๆ
ตอนนี้ เพื่อเปลี่ยนข้อโต้แย้งนี้ให้เป็นหลักฐานจริง (ซึ่งได้ทำไปแล้ว) เราต้องถือว่า ก) $k$ ถูกเลือกอย่างเท่าเทียมกันโดยการสุ่ม และ b) $\text{hash}(ไม่มี)$ จะถูกเลือกแบบสุ่ม (เพราะหากไม่เป็นเช่นนั้น ผู้โจมตีสามารถอนุมานบางสิ่งเกี่ยวกับค่าของพหุนามได้ ซึ่งจะไม่ดี) ปรากฎว่าเราสามารถเชื่อมโยงทั้งสองอย่างเข้ากับความแข็งแกร่งของการเข้ารหัสของ AES
ตอนนี้เพื่อตอบคำถามของคุณ:
- ข้างต้นถูกต้องหรือไม่?
ปิด; คุณได้รับรายละเอียดผิดไปหนึ่งข้อ เมื่อใช้สัญกรณ์ของคุณ เราจะได้การคำนวณแท็กเป็น $tag_k(c_1, c_2,...c_n) = c_0 + \sum k^nc_n$ (โปรดทราบว่า $c_0$ ไม่ได้คูณด้วย $k$):
- AES-GCM เลือกอย่างไร $k$?
มันเข้ารหัสบล็อกศูนย์ทั้งหมดโดยใช้ AES โดยใช้คีย์ GCM
- ถ้า $k=0$, $tag(\text{any_ciphertext})=0$
ไม่, $c_0$ ไม่ได้รับการคูณด้วย $k$ดังนั้นเราจึงมีในกรณีนี้:
$$แท็ก(\text{any_ciphertext}) = c_0$$
ซึ่งยังคงหมายความว่า ในกรณีนี้ ciphertext สามารถแก้ไขได้ตามอำเภอใจโดยไม่ต้องแก้ไขแท็ก แต่ก็ไม่ชัดเจน
คำถามที่ชัดเจนคือ: "นี่ยังไม่แย่อีกหรือ" ด้วยแท็ก 128 บิต ผู้โจมตีมีโอกาสเสมอ $2^{-128}$ ของการคาดเดาคู่รหัส / แท็กที่ถูกต้อง - $k=0$ มีความน่าจะเป็นที่จะเกิดขึ้นเท่าๆ กัน และด้วยเหตุนี้จึงไม่เพิ่มความน่าจะเป็นของการปลอมแปลง
- ทำ $c_n=0$ ก่อปัญหา?
ไม่; หากคุณทำตามตรรกะข้างต้น $c_n=0$ ไม่ได้เป็นกรณีพิเศษ
- แต่ถ้า $k$ เกิดขึ้นเป็นลำดับต่ำ แผนจะล้มเหลว
สถานการณ์ความล้มเหลวเฉพาะนี้ยังคงอยู่ในความน่าจะเป็น $n2^{-128}$ ดังที่แสดงไว้ข้างต้น ถ้าคุณ (พูด) ทดสอบว่า $k$ มีคำสั่งซื้อเล็กน้อยและปฏิเสธค่าเหล่านั้น คุณจะไม่ลดความน่าจะเป็นของการปลอมแปลง
[1]: ในฟิลด์ลักษณะคู่เช่น $GF(2^{128})$การบวกและการลบเป็นการดำเนินการเดียวกัน ดังนั้นเรามักจะเขียนทั้งสองอย่างเป็น $+$; ผมก็เก็บไว้เป็น $-$ เพื่อให้ชัดเจนขึ้นสำหรับคนที่ไม่คุ้นเคยกับอนุสัญญาดังกล่าว
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
