รับ${\displaystyle 2^{d}}$^{[ 7 ]}สถานะกลาง ^{[ 8 ]}และ${\displaystyle 2^{d}}$เข้ารหัสข้อความ^{[ 9 ]}จากนั้นคำนวณคีย์ที่แมปจากค่ากลางเดียวไปยัง เข้ารหัสข้อความ ทั้งหมดดำเนินกระบวนการแมปคีย์แบบ "หนึ่งต่อหลาย" ต่อไปโดยทำซ้ำสำหรับค่ากลาง ทั้งหมด

กระบวนการทำแผนที่นี้จำเป็นต้องใช้${\displaystyle (2^{d})_{\text{จำนวนสถานะกลาง}}\cdot (2^{d})_{\text{จำนวนข้อความเข้ารหัสต่อสถานะกลาง}}=2^{d+d}=2^{2d}}$การกู้คืนคีย์ เนื่องจาก สถานะกลาง แต่ละสถานะจำเป็นต้องเชื่อมโยงกับ ข้อความเข้ารหัส ทั้งหมด (ไม่ใช่แค่ข้อความเข้ารหัสเดียว) ^{[ 10 ]}

(วิธีการนี้ได้รับการแนะนำโดย Bogdanov, Khovratovich และ Rechberger ในบทความของพวกเขา: การวิเคราะห์การเข้ารหัส Biclique ของ AES เต็มรูปแบบ^{[ 2 ]} )

เบื้องต้น: โปรดจำไว้ว่าหน้าที่ของไบคลิกคือการแมปค่าระดับกลาง${\displaystyle S}$สำหรับค่าของข้อความที่เข้ารหัสแล้ว${\displaystyle C}$โดยอิงจากกุญแจสำคัญ${\displaystyle K[i,j]}$โดยที่: ${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

ขั้นตอน: ขั้นตอนที่หนึ่ง:สถานะระหว่างกลาง(${\displaystyle S_{0}}$), ข้อความเข้ารหัส(${\displaystyle C_{0}}$) และกุญแจ(${\displaystyle K[0,0]}$) ถูกเลือกโดยมีคุณสมบัติดังนี้:${\displaystyle S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}}$, ที่ไหน${\displaystyle f}$คือฟังก์ชันที่แปลงสถานะกลางไปเป็นข้อความเข้ารหัสโดยใช้กุญแจที่กำหนด ซึ่งเรียกว่าการคำนวณพื้นฐาน

ขั้นตอนที่สอง:ชุดคีย์ที่เกี่ยวข้องสองชุดที่มีขนาดเท่ากัน${\displaystyle 2^{d}}$ได้รับการเลือกแล้ว โดยเลือกคีย์ดังนี้:

• ชุดกุญแจชุดแรกคือกุญแจที่ตรงตามข้อกำหนดความแตกต่างต่อไปนี้${\displaystyle f}$โดยคำนึงถึงการคำนวณพื้นฐาน:${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}}$
• ชุดกุญแจชุดที่สองคือกุญแจที่ตรงตามข้อกำหนดความแตกต่างต่อไปนี้${\displaystyle f}$โดยคำนึงถึงการคำนวณพื้นฐาน:${\displaystyle \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0}$
• มีการเลือกกุญแจเพื่อให้เส้นทางของ${\displaystyle \Delta _{i}}$- และ${\displaystyle \nabla _{j}}$- อนุพันธ์เหล่านี้เป็นอิสระต่อกัน กล่าวคือ พวกมันไม่มีส่วนประกอบที่ไม่เป็นเชิงเส้น ที่ใช้งานอยู่ร่วมกัน

กล่าวอีกนัยหนึ่งคือ: ผลต่างของอินพุตเป็น 0 ควรจะสอดคล้องกับผลต่างของเอาต์พุตเป็น${\displaystyle \Delta _{i}}$ภายใต้ความแตกต่างที่สำคัญประการหนึ่ง${\displaystyle \เดลต้า _{i}^{K}}$ความแตกต่างทั้งหมดนั้นเกี่ยวข้องกับการคำนวณพื้นฐาน ความแตกต่างของข้อมูลนำเข้าคือ${\displaystyle \nabla _{j}}$ควรแมปไปยังความแตกต่างของเอาต์พุตเป็น 0 ภายใต้ความแตกต่างของคีย์${\displaystyle \nabla _{J}^{K}}$ความแตกต่างทั้งหมดนั้นอ้างอิงจากการคำนวณพื้นฐาน

ขั้นตอนที่สาม:เนื่องจากเส้นทางเหล่านี้ไม่มีส่วนประกอบที่ไม่เป็นเชิงเส้นร่วมกัน (เช่น เส้นทางที่ไม่มีกล่อง S ร่วมกัน ) จึงสามารถรวมเส้นทางเหล่านี้เข้าด้วยกันเพื่อให้ได้: ${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}}$ซึ่ง สอดคล้องกับคำจำกัดความของอนุพันธ์ทั้งสองจากขั้นตอนที่ 2 เห็น ได้ชัด ว่า ทูเปิล^{[ 11 ]}${\displaystyle (S_{0},C_{0},K[0,0])}$จากการคำนวณพื้นฐาน ยังสอดคล้องกับอนุพันธ์ทั้งสองตามคำนิยามด้วย เนื่องจากอนุพันธ์นั้นสัมพันธ์กับการคำนวณพื้นฐาน การแทนที่${\displaystyle S_{0},C_{0}}$${\displaystyle K[0,0]}$เมื่อนำไปใส่ในคำจำกัดความใดคำหนึ่งในสองคำนี้ จะได้ผลลัพธ์ดังนี้${\displaystyle 0{\xrightarrow[{f}]{0}}0}$เนื่องจาก${\displaystyle \Delta _{0}=0,\nabla _{0}=0}$และ${\displaystyle \Delta _{0}^{K}=0}$ นั่นหมายความว่าทูเปิลของการคำนวณพื้นฐาน สามารถ นำไป XORกับเส้นทางที่รวมกัน ได้ :${\displaystyle S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}}$

ขั้นตอนที่สี่:เป็นเรื่องง่ายดายที่จะเห็นว่า: ${\displaystyle S_{j}=S_{0}\oplus \nabla _{j}}$${\displaystyle K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}$${\displaystyle C_{i}=C_{0}\oplus \Delta _{i}}$ หากนำค่านี้ไปแทนในผลรวมของค่าความแตกต่างข้างต้น ผลลัพธ์ที่ได้จะเป็นดังนี้: ${\displaystyle S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$ซึ่งก็เหมือนกับคำจำกัดความที่ได้กล่าวไว้ข้างต้นสำหรับ biclique:${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

ดังนั้นจึงสามารถสร้างบิลิคที่มีขนาดได้${\displaystyle 2^{2d}}$(${\displaystyle 2^{2d}}$เนื่องจากทั้งหมด${\displaystyle 2^{d}}$ปุ่มของชุดปุ่มแรก สามารถนำมาผสมผสานกับปุ่มอื่นๆ ได้${\displaystyle 2^{d}}$กุญแจจากชุดกุญแจที่สอง) ซึ่งหมายถึงบิลิคที่มีขนาด${\displaystyle 2^{2d}}$สามารถสร้างได้โดยใช้เพียง${\displaystyle 2*2^{d}}$การคำนวณอนุพันธ์${\displaystyle \Delta _{i}}$และ${\displaystyle \nabla _{j}}$เกิน${\displaystyle f}$. ถ้า${\displaystyle \Delta _{i}\neq \nabla _{j}}$สำหรับ${\displaystyle i+j>0}$จากนั้นกุญแจทั้งหมด${\displaystyle K[i,j]}$ในกลุ่มคนสองพี่น้องก็จะมีความแตกต่างกันด้วยเช่นกัน

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

Bogdanov, Khovratovich และ Rechberger ยังอธิบายวิธีการสร้าง biclique อีกวิธีหนึ่งที่เรียกว่า 'Interleaving Related-Key Differential Trails' ในบทความ: "Biclique Cryptanalysis of the Full AES ^{[ 2 ]} "

พื้นที่คีย์ถูกแบ่งออกเป็น${\displaystyle 2^{112}}$กลุ่มของกุญแจ โดยแต่ละกลุ่มประกอบด้วย${\displaystyle 2^{16}}$ สำหรับแต่ละปุ่ม${\displaystyle 2^{112}}$กลุ่มต่างๆ ซึ่งเป็นคีย์พื้นฐานที่ไม่ซ้ำกัน${\displaystyle K[0,0]}$สำหรับการคำนวณพื้นฐานจะถูกเลือก คีย์พื้นฐานจะมีไบต์เฉพาะสองไบต์ที่ตั้งค่าเป็นศูนย์ ดังแสดงในตารางด้านล่าง (ซึ่งแสดงคีย์ในลักษณะเดียวกับที่ AES ใช้ในเมทริกซ์ 4x4 สำหรับ AES128):

${\displaystyle {\begin{bmatrix}-&-&-&0\\0&-&-&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

จากนั้นจึงทำการแจงนับไบต์ที่เหลืออีก 14 ไบต์ (112 บิต) ของคีย์ ซึ่งจะได้ผลลัพธ์ดังนี้${\displaystyle 2^{112}}$คีย์พื้นฐานที่ไม่ซ้ำกัน หนึ่งคีย์สำหรับแต่ละกลุ่มของคีย์ ทั่วไป${\displaystyle 2^{16}}$จากนั้นจึงเลือกคีย์ในแต่ละกลุ่มโดยอ้างอิงจากคีย์พื้นฐาน โดยเลือกให้คีย์เหล่านั้นเกือบจะเหมือนกับคีย์พื้นฐาน แตกต่างกันเพียง 2 ไบต์เท่านั้น (ไม่ว่าจะเป็น${\displaystyle i}$ของ หรือ${\displaystyle j}$ของข้อมูล 4 ไบต์ที่แสดงด้านล่าง:

${\displaystyle {\begin{bmatrix}-&-&i&i\\j&-&j&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

สิ่งนี้ให้${\displaystyle 2^{8}K[i,0]}$และ${\displaystyle 2^{8}K[0,j]}$ซึ่งเมื่อรวมกันแล้วจะได้${\displaystyle 2^{16}}$กุญแจที่แตกต่างกัน${\displaystyle K[i,j]}$. เหล่านี้${\displaystyle 2^{16}}$คีย์เหล่านี้ประกอบด้วยคีย์ต่างๆ ในกลุ่มสำหรับคีย์พื้นฐานแต่ละตัว

${\displaystyle 2^{112}}$bicliques ถูกสร้างขึ้นโดยใช้เทคนิค "ความแตกต่างของคีย์ที่เกี่ยวข้องแบบอิสระ" ดังที่อธิบายไว้ในส่วน "วิธีการสร้าง biclique" ข้อกำหนดสำหรับการใช้เทคนิคนี้คือ เส้นทางความแตกต่างไปข้างหน้าและย้อนกลับที่ต้องรวมเข้าด้วยกันจะต้องไม่มีองค์ประกอบที่ไม่เป็นเชิงเส้นที่ใช้งานอยู่ร่วมกัน เรารู้ได้อย่างไรว่านี่เป็นเช่นนั้น? เนื่องจากวิธีการเลือกคีย์ในขั้นตอนที่ 1 ที่สัมพันธ์กับคีย์พื้นฐาน เส้นทางความแตกต่างจึง...${\displaystyle \Delta _{i}}$โดยใช้ปุ่มต่างๆ${\displaystyle K[i,0]}$ห้ามแชร์ S-box ที่ใช้งานอยู่ (ซึ่งเป็นส่วนประกอบที่ไม่เป็นเชิงเส้นเพียงอย่างเดียวใน AES) กับเส้นทางความแตกต่าง (differential trails)${\displaystyle \nabla _{j}}$โดยใช้กุญแจ${\displaystyle K[0,j]}$ดังนั้นจึงสามารถนำค่า XOR ของเส้นทางที่แตกต่างกันมาสร้างเป็นบิคลิกได้

เมื่อสร้าง bicliques แล้ว การโจมตี MITM ก็แทบจะเริ่มต้นขึ้นได้ ก่อนที่จะทำการโจมตี MITM นั้น...${\displaystyle 2^{d}}$ค่ากลางจากข้อความต้นฉบับ: ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$, ​${\displaystyle 2^{d}}$ค่ากลางจากข้อความที่เข้ารหัส: ${\displaystyle {\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}}$และ สถานะระดับกลางและคีย์ย่อยที่เกี่ยวข้อง${\displaystyle K[i,0]}$หรือ${\displaystyle K[0,j]}$อย่างไรก็ตาม ค่าเหล่านี้ได้รับการคำนวณและจัดเก็บไว้ล่วงหน้าแล้ว

ตอนนี้สามารถทำการโจมตีแบบ MITM ได้แล้ว เพื่อทดสอบกุญแจ${\displaystyle K[i,j]}$จำเป็นต้องคำนวณส่วนต่าง ๆ ของรหัสลับใหม่เท่านั้น ซึ่งทราบกันดีอยู่แล้วว่าจะแตกต่างกันไปในแต่ละกรณี${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$และ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}}$สำหรับการคำนวณย้อนกลับจาก${\displaystyle S_{j}}$ถึง${\displaystyle {\xleftarrow[{v_{j}}]{}}}$นี่คือ S-box 4 ตัวที่ต้องคำนวณใหม่ สำหรับการคำนวณไปข้างหน้าจาก${\displaystyle P_{i}}$ถึง${\displaystyle {\xrightarrow[{v_{i}}]{}}}$ซึ่งก็คือ 3 เท่านั้น (คำอธิบายเชิงลึกเกี่ยวกับปริมาณการคำนวณใหม่ที่จำเป็นสามารถพบได้ในเอกสาร "Biclique Cryptanalysis of the full AES ^{[ 2 ]} " ซึ่งตัวอย่างนี้มาจากเอกสารดังกล่าว)

เมื่อค่ากลางตรงกัน ผู้สมัครหลักก็จะได้รับการพิจารณา${\displaystyle K[i,j]}$ระหว่าง${\displaystyle P_{i}}$และ${\displaystyle S_{j}}$พบรหัสลับที่เหมาะสมแล้ว จากนั้นจึงนำรหัสลับนั้นไปทดสอบกับข้อความต้นฉบับและข้อความเข้ารหัสอีกคู่หนึ่ง

การโจมตีนี้ทำให้ความซับซ้อนในการคำนวณของ AES128 ลดลงเหลือ${\displaystyle 2^{126.18}}$ซึ่งเร็วกว่าวิธีการเดาแบบสุ่ม 3-5 เท่า ความซับซ้อนของข้อมูลในการโจมตีคือ${\displaystyle 2^{88}}$และความซับซ้อนของหน่วยความจำคือ${\displaystyle 2^{8}}$.