Score:1

เหตุใดจึงไม่สามารถโจมตี AES โดยสร้างฟังก์ชันเพื่อจำลองการแทนที่ที่เกิดขึ้นใน s-box

ธง ru

ฉันรู้ว่ากล่อง s สามารถทำการแปลงใน AES ที่ไม่ใช่เชิงเส้นได้ อย่างไรก็ตาม ฉันไม่แน่ใจว่าสิ่งนี้ทำให้ AES ปลอดภัยได้อย่างไร ตัวอย่างเช่น ถ้าเราไม่มี s box ก็เป็นไปได้ที่จะคำนวณคีย์จากชุดสมการเชิงเส้น:

$C^1=ขวาน+k$

$C^2=AC^1+k$

...

$y=AC^n+k$

โดยที่ A คือการแปลงเชิงเส้น, k คือคีย์, C เป็นไซเฟอร์เท็กซ์ระดับกลาง, n เป็นจำนวนรอบของการเข้ารหัส, x เป็นอินพุตและ y เป็นเอาต์พุตสุดท้ายอย่างไรก็ตาม หากเราเพิ่มกล่อง S ลงไป มันจะเป็นไปไม่ได้เลยที่จะแสดงการแทนที่ที่มันทำหน้าที่เป็นฟังก์ชันของ x, f(x) ดังนั้นตอนนี้เรามี:

$C^1=Af(x)+k$

$C^2=อัฟ(C^1)+k$

...

$y=Af(C^n)+k$

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

kelalaka avatar
in flag
คุณต้องจัดการกับโมโนเมียลระดับ 128 (โดยเฉลี่ย 127) และโมโนเมียลจำนวนมากที่ต้องจัดการ Courtois อ้างว่าทำลาย AES (หมายถึงความซับซ้อนน้อยกว่าการค้นหา 128 บิต) แต่นั่นเป็นการเก็งกำไรอย่างมาก นี้มีการแก้ชื่อ SAT เรียบร้อยแล้ว ดู [ตัวอย่างหนังสือของกวี](https://www.amazon.com/Algebraic-Cryptanalysis-Gregory-Bard-ebook/dp/B00FB36BZO/)
Fractalice avatar
in flag
@kelalaka การแก้ปัญหา SAT เป็นเพียงวิธีหนึ่งในการแก้ปัญหาระบบดังกล่าว สิ่งที่ Ahmed แนะนำก็คือการทำให้เป็นเส้นตรงแบบง่ายๆ (ซึ่งเป็นองค์ประกอบพื้นฐานของวิธีการขั้นสูงที่อิงตามพื้นฐานของ Gröbner, การทำให้เป็นเส้นตรงแบบขยาย, ElimLin เป็นต้น)
kelalaka avatar
in flag
@Fractalice ฉันใช้ SAT เป็นคำหลัก (ตอนนี้ฉันเห็นว่าการใช้ SAT แก้ปัญหาทำให้พลาดทิศทาง) GB,XL,XLS, RL, EL เป็นวิธีการแก้ปัญหา SAT ของเราโดยเฉพาะในการเข้ารหัส Bard ครอบคลุมเนื้อหาส่วนใหญ่ในหนังสือของพวกเขาแล้ว คำตอบของคำถามนี้เป็นเพียงเอกสารบางส่วนเท่านั้น
kelalaka avatar
in flag
ในปี 2003 Murphy และ Robshaw ค้นพบคำอธิบายทางเลือกของ AES โดยฝังไว้ในรหัสขนาดใหญ่ที่เรียกว่า "BES" ใช้การดำเนินการที่ง่ายมากในฟิลด์เดียว GF(28) การโจมตี XSL ให้ชุดสมการที่ง่ายกว่าซึ่งจะทำลาย AES ด้วย ~2^100 comp. ถ้า Courtois et การวิเคราะห์อัลถูกต้อง ในปี พ.ศ. 2548 et al ให้หลักฐานว่าในรูปแบบที่เสนอ อัลกอริทึม XSL ไม่ได้ให้วิธีการที่มีประสิทธิภาพสำหรับการแก้ระบบสมการ AES; อย่างไรก็ตาม Courtois โต้แย้งการค้นพบของพวกเขา ที่ FSE 2007 Chu-Wee Lim และ Khoongming Khoo แสดงให้เห็นว่าไม่สามารถทำงานได้ตามที่นำเสนอ
Score:2
ธง in

ถ้าฉันเข้าใจถูกต้อง คุณแนะนำให้รักษาค่ากลาง $C^i$ เป็นตัวแปร

ปัญหาก็คือว่า $f(C^i)$ ไม่เป็นเชิงเส้นและมี monomials มากกว่า 128 ตัวแปร (เนื่องจาก nonlinearity มาจาก S-box จำนวน monomials จึงมากที่สุด $256\times16$). ดังนั้นจึงไม่สามารถกำจัดโดยใช้สมการได้ $C^i = ...$, และ $C^i$ ไม่ได้ใช้ที่อื่น โปรดทราบว่าหากคุณเพิ่มค่าข้อความธรรมดา/ข้อความเข้ารหัส ตัวแปร $C^i$ ไม่เหมือนกัน ดังนั้นคุณจึงไม่สามารถใช้คู่อื่นเพื่อกำจัดโมโนเมียมพิเศษเหล่านั้นได้ มีการเพิ่มตัวแปรมากขึ้นแทน

โปรดทราบว่า S-box มีจุดอ่อนตรงที่มีอยู่ กำลังสอง สมการ (มากกว่า $GF(2)$) เชื่อมต่ออินพุตและเอาต์พุต (แทนที่จะเป็นสมการองศา -7 โดยตรงของ S-box) ซึ่งทำให้ระบบง่ายขึ้นมาก อย่างไรก็ตาม ถึงกระนั้นก็ไม่มีใครสามารถแสดงวิธีแก้ปัญหาระบบดังกล่าวหรือที่คล้ายกันได้เร็วกว่า AES key bruteforce

สำหรับบันทึก แหล่งที่มาของสมการกำลังสองคือ S-box เทียบเท่ากับ $GF(256)$ ฟังก์ชันผกผัน $y=x^{254}$. เรามี $yx^2=x^{256}=x$ และอื่น ๆ $yx^2-x=0$ซึ่งเป็นกำลังสองส่วน $GF(2)$ (แบ่งออกเป็น 8 สมการ)

โพสต์คำตอบ

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