حمله ایکس‌اس‌ال

حل معادلات چندمتغیره با وجود تعداد محدودی از اعداد با کاربردهایی در رمزنویسی در حالت کلی یک مسئله ان‌پی سخت محسوب می‌شود. حمله ایکس اس ال نیازمند یک الگوریم کارامد است. در سال ۱۹۹۹ کیپنیس و شمیر نشان دادند که رمزنگاری کلید عمومی می‌تواند به یک دستگاه مشخص از معادلات درجه دوم کاهش یابد. بک روش برای حل چنین دستگاه‌هایی خطی سازی است که شامل جایگزینی رابطه درجه دوم با یک متغیر مستقل و حل دستگاه خطی به دست آمده با استفاده از الگوریتمی نظیر حذف گاوسی است. برای ادامه، خطی سازی نیاز به معادلاتی دارد که از لحاظ خطی مستقل باشند (تقریباً به تعداد روابط). هرچند برای تحلیل رمز اچ اف ای معادلات بسیار کمی وجود داشتند، بنابراین کیپنیس و شمیر پیشنهاد خطی سازی مجدد را دادند، تکنیکی که معادلات غیرخطی اضافی را بعد از خطی سازی اضافه کرده و دستگاه حاصل به وسیله اعمال دوباره خطی سازی حل می‌شود. ثابت شد که خطی سازی مجدد برای سایر طرح‌ها نیز به صورت کلی قابل اعمال است.

در سال ۲۰۰۰ کورتویز الگوریتم بهبود یافته‌ای را برای معادلات چندمتغیره درجه دوم با نام ایکس ال (خطی سازی توسعه یافته) پیشنهاد داد که تعداد معادلات را از طریق ضرب آن‌ها در همه تک جمله ای‌های یک درجه مشخص افزایش می‌دهد. محاسبات پیچیدگی نشان دادند که حمله ایکس ال در مقابل معادلات به دست آمده از رمزهای بلوکی نظیر استاندارد رمزنگاری پیشرفته عمل نمی‌کند. هرچند دستگاه‌های معادلات تولید شده دارای یک ساختار خاص بودند و الگوریتم ایکس اس ال حالت اصلاح شده ایکس الی بود که می‌توانست از مزایای این ساختار بهره مند شود. در ایکس اس ال معادلات تنها در تک جمله‌ای‌هایی که با دقت انتخاب می‌شوند و چندین متغیر پیشنهادی، ضرب می‌شوند.

تحقیقات در مورد کارایی ایکس ال و الگوریتم‌های اقتباس شده از آن هم چنان ادامه دارد.

کورتویز و پیپرزیک مشاهده کردند که استاندارد رمزنگاری پیشرفته و تا حدی سرپنت می‌توانند به صورت دستگاهی از معادلات درجه دوم بیان شوند. متغیرها نه تنها متن رمزنشده، متن رمزشده و بیت‌های کلید را ارائه می‌دهند، بلکه مقادیر مختلف میانی را نیز برای الگوریتم ارائه می‌دهند. جدول جایگزینی استاندارد رمزنگاری پیشرفته به این نوع تحلیل حساس است، چرا که بر مبنای تابع معکوس جبری است. در ادامه سایر رمزها مورد مطالعه قرار گرفتند تا مشخص شود چه دستگاه معادلاتی می‌تواند تولید شود. برخلاف سایر حالات تحلیل رمز، برای چنین تحلیل رمز تفاضل و خطی ای تنها یک یا دو متن رمزنشده مشخص لازم است.

الگوریتم ایکس اس ال برای حل نوع دستگاه معادلات تولید شده، سازمان دهی می‌شود. کورتویز و پیپرزیک تخمین می‌زنند که "یک ارزیابی خوش بینانه نشان می‌دهد که حمله ایکس اس ال ممکن است قادر به شکستن استاندارد رمزنگاری پیشرفته با کلیدهای ۲۵۶ بیتی و سرپنت با کلیدهای ۱۹۲ تا ۲۵۶ بیتی باشد. " هرچند تحلیل آن‌ها به صورت جهانی پذیرفته نیست. به عنوان مثال:

"من اعتقاد دارم کار کورتویز و پیپرزیک دارای عیب است. آنها تعداد معادلات مستقل به صورت غیرخطی را حساب می‌کنند. نتیجه این است که آنها در واقعیت معادلات خطی کافی برای حل دستگاه دارند و این روش استاندارد رمزنگاری پیشرفته را نمی‌شکند، هرچند مزایایی هم دارد. "

در چهارمین کنفرانس استاندارد رمزنگاری پیشرفته یکی از مخترعان استاندارد رمزنگاری پیشرفته به نام وینسنت ریجمن اظهار داشت که حمله ایکس اس ال یک حمله محسوب نمی‌شود و تنها یک رویاست. بلافاصله کورتویز پاسخ داد که کابوس تو خواهد شد. هرچند هیچ مقاله‌ای از این حرف کورتویز حمایت نکرد.

در سال ۲۰۰۳ مورفی و رابشو توصیف جایگزینی برای استاندارد رمزنگاری پیشرفته کشف کردند و آن را در یک رمز بزرگتر به نام بی ای اس جا دادند که می‌تواند با استفاده از عملگرهای بسیار ساده در یک میدان واحد (GF(2 توصیف شود. یک حمله ایکس اس ال بر روی این سیستم، مجموعه معادلات ساده تری را ایجاد می‌کند که می‌تواند استاندارد رمزنگاری پیشرفته را با پیچیدگی حدود ۲ بشکند، اگر تحلیل کورتویز و پیپرزیک درست باشد. در سال ۲۰۰۵ سید و لئورنت برای این مسئله که الگوریتم ایکس اس ال روش کارایی را برای حل دستگاه معادلات استاندارد رمزنگاری پیشرفته فراهم نمی‌کند، مدرک ارائه دادند. هرچند کورتویز یافته‌های آها را انکار کرد. در مقاله‌ای مربوط به چهارمین کنفرانس استاندارد رمزنگاری پیشرفته تولی و زانونی اثبات کردند که کار مورفی و رابشو ایراد داشت.

حتی اگر ایکس اس ال در مقابل تعدادی از الگوریتم‌های مدرن عمل کند، این حمله در حال حاضر خطر کمی را در عمل به وجود می‌آورد. همچون بسیاری از نتایج تحلیل رمز مدرن، می‌توان آن را ضعف تصدیقی نامید. در حالی که از حمله جستجوی فراگیر سریع تر است، منابع لازم همچنان زیاد هستند و احتمال اینکه سیستم‌های دنیای واقعی با استفاده از آن به خطر بیافتند، بسیار کم است، هرچند پیشرفت‌های آینده می‌تواند عملی بودن یک حمله را افزایش دهد. از آنجایی که این نوع حمله جدید است، چند رمزنویس، سختی ساده سازی جبری رمزهایی مانند استاندارد رمزنگاری پیشرفته را اعلام کرده‌اند. بروس اسچنیر و نیلز فرگوسن می‌نویسند: "ما انتقادی از استاندارد رمزنگاری پیشرفته داریم: ما از اعتماد به امنیت دست برنمی داریم... مهم ترین چیزی که ما را در مورد استاندارد رمزنگاری پیشرفته نگران می‌کند، ساختار جبری ساده آن است... هیچ رمز بلوکی دیگری که ما می‌شناسیم چنین معرفی جبری ساده‌ای ندارد. ما هیچ ایده‌ای در مورد اینکه آیا این مسئله منجر به حمله می‌شود یا نه نداریم، اما ندانستن، دلیل کافی ای برای مشکوک بودن در مورد کاربرد استاندارد رمزنگاری پیشرفته‌است. "

• XSL attack