Score:1

ทำความเข้าใจเกี่ยวกับพีชคณิตที่อยู่เบื้องหลังความปลอดภัยของ GCM

ธง ru

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

เพื่อความง่าย ให้ถือว่าไซเฟอร์เท็กซ์เพียงบล็อกเดียว $ค$. เราต้องการให้แท็กของเรามีสองคุณสมบัติ:

  1. $tag_k(ค)$ ควรเป็นแฮชเครื่องแบบสากลของ $ค$: นั่นคือสำหรับทุกคน $ค$, ถ้า $k$ เป็นแบบสุ่มอย่างสม่ำเสมอ $P[tag_k(c) = y]$ เป็นชุดเดียวกันสำหรับทุกคน $y$.

  2. $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")

  1. ข้างต้นถูกต้องหรือไม่?
  2. AES-GCM เลือกอย่างไร $k$?

ที่สำคัญกว่านั้น เราจะหลีกเลี่ยงโหมดความล้มเหลวที่ชัดเจนต่อไปนี้ได้อย่างไร:

  1. ถ้า $k = 0$, $tag(ใดๆ\_ciphertext) = 0$
  2. ทำ $c_n = 0$ ก่อปัญหา? ดูเหมือนจะไม่ทำลายคุณสมบัติใด ๆ แต่ก็ยังน่าเป็นห่วง (โปรดทราบว่าเราไม่สามารถต่อท้ายบล็อกศูนย์ได้ เนื่องจากการดำเนินการนี้จะเปลี่ยนฟิลด์ความยาว)
  3. สำหรับฉันแล้ว ดูเหมือนว่าอัลกอริทึมหลายบล็อกจะถูกต้อง ถ้า ทั้งหมด $k$ เป็นเครื่องกำเนิดของ $GF(2^n)$ หรืออย่างน้อยในลำดับที่สูงมาก แต่ถ้า $k$ เกิดขึ้นเป็นลำดับต่ำ แผนจะล้มเหลว

ตัวอย่างเช่น ลองนึกภาพ $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 หลีกเลี่ยงโหมดความล้มเหลวนี้ได้อย่างไร

kelalaka avatar
in flag
คำถามยาวมากและ 5 Qs ในครั้งเดียว! GCM เปราะบางมากเช่นนี้ [การทำความเข้าใจผลกระทบของการแบ่งพาร์ติชันของการโจมตีของออราเคิลบนสตรีม ciphers](https://crypto.stackexchange.com/q/88716/18298) และ [การใช้ IV เดียวกันสองครั้งกับ AES/ แย่แค่ไหน GCM?](https://crypto.stackexchange.com/a/68525/18298) และ [อะไรคือข้อจำกัดในการใช้ GCM ที่มีขนาดแท็ก 96 และ 128 บิต](https://crypto.stackexchange.com /q/27374/18298)
kelalaka avatar
in flag
ดู [รายงานของ Joux](https://csrc.nist.gov/csrc/media/projects/block-cipher-techniques/documents/bcm/comments/800-38-series-drafts/gcm/joux_comments.pdf)
Score:2
ธง my

ฉันต้องการเข้าใจพีชคณิตที่อยู่เบื้องหลังความปลอดภัยของ 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

ตอนนี้เพื่อตอบคำถามของคุณ:

  1. ข้างต้นถูกต้องหรือไม่?

ปิด; คุณได้รับรายละเอียดผิดไปหนึ่งข้อ เมื่อใช้สัญกรณ์ของคุณ เราจะได้การคำนวณแท็กเป็น $tag_k(c_1, c_2,...c_n) = c_0 + \sum k^nc_n$ (โปรดทราบว่า $c_0$ ไม่ได้คูณด้วย $k$):

  1. AES-GCM เลือกอย่างไร $k$?

มันเข้ารหัสบล็อกศูนย์ทั้งหมดโดยใช้ AES โดยใช้คีย์ GCM

  1. ถ้า $k=0$, $tag(\text{any_ciphertext})=0$

ไม่, $c_0$ ไม่ได้รับการคูณด้วย $k$ดังนั้นเราจึงมีในกรณีนี้:

$$แท็ก(\text{any_ciphertext}) = c_0$$

ซึ่งยังคงหมายความว่า ในกรณีนี้ ciphertext สามารถแก้ไขได้ตามอำเภอใจโดยไม่ต้องแก้ไขแท็ก แต่ก็ไม่ชัดเจน

คำถามที่ชัดเจนคือ: "นี่ยังไม่แย่อีกหรือ" ด้วยแท็ก 128 บิต ผู้โจมตีมีโอกาสเสมอ $2^{-128}$ ของการคาดเดาคู่รหัส / แท็กที่ถูกต้อง - $k=0$ มีความน่าจะเป็นที่จะเกิดขึ้นเท่าๆ กัน และด้วยเหตุนี้จึงไม่เพิ่มความน่าจะเป็นของการปลอมแปลง

  1. ทำ $c_n=0$ ก่อปัญหา?

ไม่; หากคุณทำตามตรรกะข้างต้น $c_n=0$ ไม่ได้เป็นกรณีพิเศษ

  1. แต่ถ้า $k$ เกิดขึ้นเป็นลำดับต่ำ แผนจะล้มเหลว

สถานการณ์ความล้มเหลวเฉพาะนี้ยังคงอยู่ในความน่าจะเป็น $n2^{-128}$ ดังที่แสดงไว้ข้างต้น ถ้าคุณ (พูด) ทดสอบว่า $k$ มีคำสั่งซื้อเล็กน้อยและปฏิเสธค่าเหล่านั้น คุณจะไม่ลดความน่าจะเป็นของการปลอมแปลง


[1]: ในฟิลด์ลักษณะคู่เช่น $GF(2^{128})$การบวกและการลบเป็นการดำเนินการเดียวกัน ดังนั้นเรามักจะเขียนทั้งสองอย่างเป็น $+$; ผมก็เก็บไว้เป็น $-$ เพื่อให้ชัดเจนขึ้นสำหรับคนที่ไม่คุ้นเคยกับอนุสัญญาดังกล่าว

ru flag
คำตอบเด็ด! ถ้าฉันเข้าใจถูกต้อง คุณกำลังพูดว่า: ใช่ มีบางกรณีที่ $tag_{forgery}$ มีความสัมพันธ์ที่เรียบง่ายมากกับ $tag_{real}$: เมื่อ $k = 0$ จะเหมือนกัน และเมื่อ $ k$ คือคำสั่ง 2 พวกเขาทำตามแผนการพลิกบิตที่ฉันแสดง แต่แล้วไงล่ะ? นั่นไม่ได้ทำให้ความปลอดภัยลดลง ตราบใดที่เรายังรั่วไหล _ไม่มีอะไร_ เกี่ยวกับ $k$ ความจริงก็ยังคงมีอยู่ว่าสำหรับการปลอมแปลงทุกครั้ง จะมีแท็ก $n$ มากที่สุด (จาก $2^{128}$) ที่ตรงกัน สำหรับ $k$ บางแท็กที่แก้ไขเหล่านี้คำนวณได้ง่ายจาก $tag_{real}$ และสำหรับ $k$ บางแท็กจะไม่ใช่ ถูกต้องหรือไม่?
poncho avatar
my flag
@SRobertJames: ที่จริงสำหรับฟิลด์นี้ ไม่มี $k$ กับคำสั่ง 2; ในทางกลับกัน มีค่า $k$ สองค่าที่มีลำดับที่ 3 ดังนั้นคะแนนของคุณจึงยังคงใช้ได้
ru flag
คุณได้แสดงให้เห็นว่า $c'$ และ $k$ มี $n$ $tag'$s มากที่สุดที่รับรองความถูกต้องของ $c'$ เราจะรู้ได้อย่างไรว่า $tag'$s เหล่านั้นเป็นฟังก์ชันสุ่มของ $k$ บางที $tag'$s บางตัวใช้ได้กับ $k$ จำนวนมาก และบางตัวใช้ได้กับ $k$ น้อยหรือไม่มีเลย สำหรับฟังก์ชันเชิงเส้น $ax + b$ นี่ไม่ใช่ปัญหา เนื่องจากฟังก์ชันเชิงเส้นในเขตข้อมูลจำกัดเป็นการเรียงสับเปลี่ยน แต่สำหรับฟังก์ชันพหุนาม ไม่เป็นความจริง เช่น. $x^2 ​​+ x$ ส่งครึ่งหนึ่งของ $GF(2^2)$ ถึง $0$
poncho avatar
my flag
@SRobertJames: สอดคล้องกับสิ่งที่คุณถามจริงๆ จริงๆ แล้วค่อนข้างง่ายที่จะกำหนดค่า $n$ สำหรับ $k$ และสร้างของปลอมที่จะจับคู่ค่านั้นหากค่า $k$ ใดค่าหนึ่งถูกต้อง การคำนวณเป็นมากกว่า 'การพลิกสองบิต' เล็กน้อย แต่ก็ยังค่อนข้างเป็นไปได้
poncho avatar
my flag
@SRobertJames: มีไว้สำหรับ 'การแมประหว่างข้อความและแท็กมีการแจกจ่ายเท่ากันหรือไม่' จำ $hash(\text{nonce})$ ที่เรารวมไว้ในการคำนวณแท็กได้ไหม ตราบใดที่สิ่งนี้มีการกระจายอย่างเท่าเทียมกันและเป็นอิสระจากการคำนวณแท็กที่เหลือ (และเนื่องจากอิงตาม AES ซึ่งดูเป็นไปได้) แท็กเองก็จะถูกกระจายอย่างเท่าเทียมกัน

โพสต์คำตอบ

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