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

در رمزنویسی حمله ایکس اس ال روشی برای تحلیل رمز رمزهای بلوکی است. این حمله اولین بار در سال ۲۰۰۲ توسط محققان نیکلا کورتوا و جوزف پیپرزیک به چاپ رسید. از زمان معرفی آن جدال‌هایی مطرح بوده مبنی بر اینکه این حمله نمی‌تواند پتانسیل شکستن رمز استاندارد رمزنگاری پیشرفته را با سرعت بیشتری نسبت به حمله جستجوی فراگیر داشته باشد. از آنجایی که استاندارد رمزنگاری پیشرفته در حال حاضر به شدت در تجارت و کارهای دولتی برای انتقال اطلاعات سری به کار می‌رود، پیدا کردن تکنیکی که بتواند زمان لازم برای بازیابی پیام سری را بدون داشتن کلید کاهش دهد می‌تواند پیامدهای گسترده‌ای داشته باشد.
این روش تلاش لازم برای شکستن استاندارد رمزنگاری پیشرفته را در مقایسه با جستجوی فراگیر کاهش نمی‌دهد. بنابراین امنیت واقعی رمزهای بلوکی را در آینده نزدیک تحت تاثیر قرار نمی‌دهد. با این حال این حمله باعث شده چند تن از متخصصان سختی بیشتری را برای ساده سازی جبری استاندارد رمزنگاری پیشرفته کنونی اعلام کنند.
حمله ایکس اس ال به اولین تحلیل یک رمز و استخراج یک دستگاه معادلات شبیه ساز درجه دوم بستگی دارد. این دستگاه‌ها اغلب بسیار بزرگ هستند، به عنوان مثال دستگاهی با ۸۰۰۰ معادله و ۱۶۰۰ متغیر برای استاندارد رمزنگاری پیشرفته ۱۲۸ بیتی. چندین روش برای حل چنین دستگاهی شناخته شده. در حمله ایکس اس ال یک الگوریتم خاص با همان نام (ایکس اس ال) برای حل این معادلات و بازیابی کلید، استفاده می‌شود.
این حمله به خاطر نیاز به تنها تعداد محدودی متن رمزنشده مشخص قابل توجه است؛ روش‌های قبلی تحلیل رمز مانند روش خطی و تحلیل تفاضلی، اغلب نیاز به تعداد زیادی متن رمزنشده مشخص یا انتخابی دارند.
حل معادلات چندمتغیره درجه دوم
حل معادلات چندمتغیره با وجود تعداد محدودی از اعداد با کاربردهایی در رمزنویسی در حالت کلی یک مسئله ان‌پی سخت محسوب می‌شود. حمله ایکس اس ال نیازمند یک الگوریم کارامد است. در سال ۱۹۹۹ کیپنیس و شمیر نشان دادند که رمزنگاری کلید عمومی می‌تواند به یک دستگاه مشخص از معادلات درجه دوم کاهش یابد. بک روش برای حل چنین دستگاه‌هایی خطی سازی است که شامل جایگزینی رابطه درجه دوم با یک متغیر مستقل و حل دستگاه خطی به دست آمده با استفاده از الگوریتمی نظیر حذف گاوسی است. برای ادامه، خطی سازی نیاز به معادلاتی دارد که از لحاظ خطی مستقل باشند (تقریبا به تعداد روابط). هرچند برای تحلیل رمز اچ اف ای معادلات بسیار کمی وجود داشتند، بنابراین کیپنیس و شمیر پیشنهاد خطی سازی مجدد را دادند، تکنیکی که معادلات غیرخطی اضافی را بعد از خطی سازی اضافه کرده و دستگاه حاصل به وسیله اعمال دوباره خطی سازی حل می‌شود. ثابت شد که خطی سازی مجدد برای سایر طرح‌ها نیز به صورت کلی قابل اعمال است.
در سال ۲۰۰۰ کورتویز الگوریتم بهبود یافته‌ای را برای معادلات چندمتغیره درجه دوم با نام ایکس ال (خطی سازی توسعه یافته) پیشنهاد داد که تعداد معادلات را از طریق ضرب آنها در همه تک جمله ای‌های یک درجه مشخص افزایش می‌دهد. محاسبات پیچیدگی نشان دادند که حمله ایکس ال در مقابل معادلات به دست آمده از رمزهای بلوکی نظیر استاندارد رمزنگاری پیشرفته عمل نمی‌کند. هرچند دستگاه‌های معادلات تولید شده دارای یک ساختار خاص بودند و الگوریتم ایکس اس ال حالت اصلاح شده ایکس الی بود که می‌توانست از مزایای این ساختار بهره مند شود. در ایکس اس ال معادلات تنها در تک جمله‌ای‌هایی که با دقت انتخاب می‌شوند و چندین متغیر پیشنهادی، ضرب می‌شوند.
تحقیقات در مورد کارایی ایکس ال و الگوریتم‌های اقتباس شده از آن هم چنان ادامه دارد.
کاربرد برای رمزهای بلوکی
کورتویز و پیپرزیک مشاهده کردند که استاندارد رمزنگاری پیشرفته و تا حدی سرپنت می‌توانند به صورت دستگاهی از معادلات درجه دوم بیان شوند. متغیرها نه تنها متن رمزنشده، متن رمزشده و بیت‌های کلید را ارائه می‌دهند، بلکه مقادیر مختلف میانی را نیز برای الگوریتم ارائه می‌دهند. جدول جایگزینی استاندارد رمزنگاری پیشرفته به این نوع تحلیل حساس است، چرا که بر مبنای تابع معکوس جبری است. در ادامه سایر رمزها مورد مطالعه قرار گرفتند تا مشخص شود چه دستگاه معادلاتی می‌تواند تولید شود. برخلاف سایر حالات تحلیل رمز، برای چنین تحلیل رمز تفاضل و خطی‌ای تنها یک یا دو متن رمزنشده مشخص لازم است.
الگوریتم ایکس اس ال برای حل نوع دستگاه معادلات تولید شده، سازمان دهی می‌شود. کورتویز و پیپرزیک تخمین می‌زنند که "یک ارزیابی خوش بینانه نشان می‌دهد که حمله ایکس اس ال ممکن است قادر به شکستن استاندارد رمزنگاری پیشرفته با کلیدهای ۲۵۶ بیتی و سرپنت با کلیدهای ۱۹۲ تا ۲۵۶ بیتی باشد. " هرچند تحلیل آنها به صورت جهانی پذیرفته نیست. به عنوان مثال:
"من اعتقاد دارم کار کورتویز و پیپرزیک دارای عیب است. آنها تعداد معادلات مستقل به صورت غیرخطی را حساب می‌کنند. نتیجه این است که آنها در واقعیت معادلات خطی کافی برای حل دستگاه دارند و این روش استاندارد رمزنگاری پیشرفته را نمی‌شکند، هرچند مزایایی هم دارد. "
در چهارمین کنفرانس استاندارد رمزنگاری پیشرفته یکی از مخترعان استاندارد رمزنگاری پیشرفته به نام وینسنت ریجمن اظهار داشت که حمله ایکس اس ال یک حمله محسوب نمی‌شود و تنها یک رویاست. بلافاصله کورتویز پاسخ داد که کابوس تو خواهد شد. هرچند هیچ مقاله‌ای از این حرف کورتویز حمایت نکرد.
در سال ۲۰۰۳ مورفی و رابشو توصیف جایگزینی برای استاندارد رمزنگاری پیشرفته کشف کردند و آن را در یک رمز بزرگتر به نام بی‌ای اس جا دادند که می‌تواند با استفاده از عملگرهای بسیار ساده در یک میدان واحد (GF(2 ۸ توصیف شود. یک حمله ایکس اس ال بر روی این سیستم، مجموعه معادلات ساده‌تری را ایجاد می‌کند که می‌تواند استاندارد رمزنگاری پیشرفته را با پیچیدگی حدود ۲ ۱۰۰ بشکند، اگر تحلیل کورتویز و پیپرزیک درست باشد. در سال ۲۰۰۵ سید و لئورنت برای این مسئله که الگوریتم ایکس اس ال روش کارایی را برای حل دستگاه معادلات استاندارد رمزنگاری پیشرفته فراهم نمی‌کند، مدرک ارائه دادند. هرچند کورتویز یافته‌های آها را انکار کرد. در مقاله‌ای مربوط به چهارمین کنفرانس استاندارد رمزنگاری پیشرفته تولی و زانونی اثبات کردند که کار مورفی و رابشو ایراد داشت.
حتی اگر ایکس اس ال در مقابل تعدادی از الگوریتم‌های مدرن عمل کند، این حمله در حال حاضر خطر کمی را در عمل به وجود می‌آورد. همچون بسیاری از نتایج تحلیل رمز مدرن، می‌توان آن را ضعف تصدیقی نامید. در حالی که از حمله جستجوی فراگیر سریع‌تر است، منابع لازم همچنان زیاد هستند و احتمال اینکه سیستم‌های دنیای واقعی با استفاده از آن به خطر بیافتند، بسیار کم است، هرچند پیشرفت‌های آینده می‌تواند عملی بودن یک حمله را افزایش دهد. از آنجایی که این نوع حمله جدید است، چند رمزنویس، سختی ساده سازی جبری رمزهایی مانند استاندارد رمزنگاری پیشرفته را اعلام کرده‌اند. بروس اسچنیر و نیلز فرگوسن می‌نویسند: "ما انتقادی از استاندارد رمزنگاری پیشرفته داریم: ما از اعتماد به امنیت دست برنمی داریم… مهم‌ترین چیزی که ما را در مورد استاندارد رمزنگاری پیشرفته نگران می‌کند، ساختار جبری ساده آن است… هیچ رمز بلوکی دیگری که ما می‌شناسیم چنین معرفی جبری ساده‌ای ندارد. ما هیچ ایده‌ای در مورد اینکه آیا این مسئله منجر به حمله می‌شود یا نه نداریم، اما ندانستن، دلیل کافی‌ای برای مشکوک بودن در مورد کاربرد استاندارد رمزنگاری پیشرفته‌است. "