رمزگذاری تفاضلی

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

تاریخ

کشف رمزنگاری تفاضلی به‌طور کلی به الی بیهام و ادی شامیر در اواخر سال ۱۹۸۰ نسبت داده می‌شود، آن‌ها به بلاک سیفرها و توابع درهم ساز که شامل ضعف تئور در استاندارد رمزنگاری داده‌ها (DES) بودند حمله کردند بیهام و شمیر عنوان کردند که استاندارد رمزنگاری داده‌ها به‌طور شوکه کننده ای در برابر رمزنگاری دیفرانسیلی (تفاضلی) مقاوم بوده‌اند اما با اصلاحات کوچکی در الگوریتم می‌توانند آن را بسیار حساس تر کنند.

در سال ۱۹۹۴ یکی از اعضای اصلی گروه IBM DES دن کوپر اسمیت، در یک مقاله ای بیان کرد که رمزنگاری دیفرانسیلی از سال ۱۹۷۴ برای این گروه شناخته شده بود و اینکه دفاع از این نوع رمزنگاری از اهداف طرح آنان بوده‌است. طبق گفته‌های استیون لوی (نویسنده) IBM رمزنگاری دیفرانسیلی را کشف کرد. NSA هم ظاهراً از این تکنیک به‌طور کامل باخبر بوده‌است.IBM بعضی از رمزها را فاش نکرد و در گروه حفظ کرد، اینگونه که کوپر اسمیت توضیح می‌دهد، بعد از گفتگوهایی با سازمان NSA نتیجه‌گیری شد که از نکات طرح و از تکنیک‌های رمزگذاری دیفرانسیلی پرده برداری شود. تکنیکی قدرتمند که می‌توان از آن برای بسیاری از کدها بهره برد، البته این به نوبه خود آمریکا را از منظر رقابتی با سایر کشور ضعیف تر می‌ساخت. در IBM، رمزنگاری دیفرانسیلی با عنوان "حمله T" یا "حمله Tickle" شناخته می‌شد.

DES در مقابل رمزگشایی دیفرانسیلی مقاومت بالایی از خود نشان دادند، در حالیکه سایر کدهای هم دورهٔ آن‌ها ثابت کردند که در مقابل آن آسیب‌پذیر می‌باشند و مقاومت کمی دارند. هرگونه هدف برای حمله یک نوع بلاک سیفر FEAl محسوب می‌شود. نسخه اصلی پیشنهاد شده با ۴ راند (FEAL-4) می‌تواند تنها با هشت متن اصلی منتخب شکسته شود و حتی یک نسخهٔ ۳۱ دوری FESL نیز نسبت به حمله حساس است. در مقابل آن این طرح می‌تواند DES را با یک تلاش به مقیاس ۲^۴۷ پلین تکست رمرنگاری کند.

حمله مکانیکی

رمزگشایی دیفرانسیلی معمولاً یک حمله با متن اصلی منتخب می‌باشد به این معنی که حمله کننده باید بتواند متون رمزی را برای چندین متن اصلی انتخاب شدهٔ خود بدست آورد. اگرچه تمدیدهایی وجود دارد که به یک متن اصلی یا حتی یک متن رمزی اجازهٔ حمله دهد. روش پایه از چندین جفت پلین تکست استفاده می‌کند که آن‌ها از طریق یک تفاوت ثابتی به هم مرتبط می‌شوند. این تفاوت می‌تواند به شکل‌های متفاوتی تعریف می‌شود اما (Exclusive Or(XOR سیستم رایج آن می‌باشد. مهاجم سپس تفاوت‌های متون کد گذاری شدهٔ مطابق هم را محاسبه می‌کند، به این امید که الگوهای آماری این بخش را پیدا کند. جفت تفاوت‌های نتیجه‌گیری شده تفاضلی (دیفرانسیلی) نامیده می‌شوند. ویژگی آماری آن‌ها به اس باکس‌های استفاده شده در آن برای کدگذاری بستگی دارد، بنابراین مهاجم مشتقات (ΔX, ΔY) که (ΔY= S(X ⊕ ΔX) ⊕ S(X (و ⊕ Exclusive OR را مشخص می‌کند) را برای هرکدام از این اس باکس‌ها آنالیز می‌کند. در حمله اساسی انتظار می‌رود که یک اختلاف متن کدگذاری شده مشخص، لزوماً تصادفی باشد. در این حالت کد می‌تواند از سایر متون تشخیص داده شود. تغییرات پیچیده بیشتر به کلید اجازه می‌دهد تا سریع تر از طریق جستجوی فراگیر بازیابی شود.

در اکثر شکل‌های بنیادی از کلید بازیابی شده از طریق کدنویسی دیفرانسیلی، یک مهاجم متن کدنویسی شده را برای تعداد زیادی از جفت‌های پلین تکست درخواست می‌کند، سپس فرض می‌کند که این تفاضل حداقل برای r - 1 دور باقی می‌ماند، که r اینجا تعداد کل راندها می‌باشد، مهاجم سپس استنباط می‌کند که کدام راند کی‌ها (کلید دوره‌ها) برای دور آخر ممکن می‌باشند. با فرض اینکه تفاوت بین بلوک‌ها قبل از دور آخر تعیین شده‌است، زمانی که کلید دوره‌ها کوتاه باشند، می‌توانند به سادگی توسط رمزگشایی جامع از جفت متن‌های کد نویسی شدهٔ یک راند با همهٔ راند کی‌های ممکن بدست آورده شوند. زمانی که یک راند کی در مقایسه با سایرکلیدهای موجود با پتانسیل بالا تلقی شود می‌توان نتیجه گرفت که آن دور کلید همان دور کلید مناسب می‌باشد.

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

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

حمله در جزییات

حمله در ابتدا بر این حقیقت تکیه می‌کند که تفاوت الگوی یک ورودی/خروجی داده شده تنها برای ورودی‌های مشخصی اتفاق می‌افتد. معمولاً حمله برای مولفه‌های غیر خطی اتفاق می‌افتد بگونه ای که انگار آن‌ها یک مولفه سالید (سخت) می‌باشند. (معمولا آن‌ها جدول‌های جستجو یا اس باکس هستند) مشاهدهٔ تفاوت خروجی‌های مطلوب (که بین دو پلین تکست معروف یا انتخاب شده هستند) تعدادی کلید محتمل را پیشنهاد می‌کند.

برای مثال اگر یک مشتق از ۱ <= ۱ (بیان می‌کند که یک تفاوت در بیت کم ارزش (LSB) ورودی منجر به یک خروجی با LSB متفاوت می‌شود) با احتمال ۶۵۲/۴ اتفاق بیافتد (برای مثال برای توابع غیر خطی در رمز AES ممکن است) در آن صورت برای تنها ۴ مقدار (یا دو جفت) از ورودی‌های آن مشتق ممکن است. فرض کنید ما یک تابع غیر خطی داریم که کلید آن XORed قبل از ارزیابی است و اعداد ی که مشتق را می‌پذیرند {۳ و ۲} و {۵ و ۴} هستند، اگر مهاجم اعداد {۷ و ۶} را بفرستد اختلاف خروجی صحیح را مشاهده می‌کند به این معنا که کلید یا ۲ = k ⊕ ۶ یا ۴ = k ⊕ ۶ است و این یعنی کلید ۲ یا ۴ است.

در اصل برای یک n بیت تابع غیر خطی در حالت ایده‌آل تا حد ممکن نزدیک‌ترین تابع به $2^{1-n}$ جستجو می‌شود تا به مشتق یکنواختی برسد. زمانیکه این اتفاق می‌افتد حمله دیفرانسیلی (مشتقی) نیازمند کار بسیاری می‌باشد که بتواند کلید را بسادگی بروت فورس کردن آن مشخص نماید.

تابع غیر خطی AES حداکثر یک مشتق با احتمال ۴/۲۵۶ دارد (اکثر ورودی‌ها ۲ یا ۰ اند) به این معنی که در تئوری می‌توان با نصف کارکرد بروت فورس (فشار زیاد) کلید را مشخص کرد. اگرچه شاخهٔ بلند AES هرگونه مسئله ای را که احتمال قوی وجود بیش از چند راند را مطرح می‌کند جلوگیری می‌کند. در حقیقت کد AES با یک تابع غیر خطی ضعیف می‌تواند در مقابل حملات دیفرانسیلی و خطی مصون بماند. شاخهٔ بلند به‌طور باور نکردنی (اس باکس فعال نیز جزو آن محسوب می‌شود) از ۲۵ بر 4r می‌باشد. به این معنی که در ۸ راند هیچ حمله ای کمتر از ۵۰ تغییر شکل (دگرگونی) غیر خطی ندارد، یعنی احتمال موفقیت از (بهترین حمله بر اس باکس)Pr $\leq$ (حمله)Pr تجاوز نمی‌کند. برای مثال با مشتق کنونی هیچ احتمالی بیشتر از ⁵⁰(4/256) یا^300-2 خارج نمی‌شود، که از آستانه مورد نیاز که ^128-2 می‌باشد برای یک بلاک سیفر (رمز مسدود) ۱۲۸ بیتی بسیار کمتر است. این برای یک اس باکس بهینه جای بیشتری می‌توانست باز کند و حتی اگر 16-UNIFORM باشد باز هم احتمال حمله به ^200-2 می‌رسد.

هیچ بایجکشنی برای حتی ورودی/خروجی‌های اندازه‌گیری شده با 2-UNIFORMITY (یعنی ۲ یکنواختی) وجود ندارد. آن‌ها در زمینه‌های جالبی - مانند (GF(2⁷ - وجود دارند، از معکوس به توان سوم رساندن استفاده می‌کنند. (البته محاسباتی دیگری نیز برای آن وجود دارد) برای مثال S(X)=X³ در هر زمینهٔ مضاعفی (باینری فیلد) در برابر کد نویسی خطی و دیفرانسیلی مصون است. این بخشی است که توضیح می‌دهد چرا طرح میستی (MISTY) از توابع ۷- و ۹- بیتی در تابع غیر خطی ۱۶ بیتی استفاده کرد. چیزهایی که این توابع در مصون ماندن از حملات خطی و دیفرانسیلی بدست می‌آورند را در الگوریتم حملات از دست می‌دهند. به این معنی که ممکن است آن‌ها توسط مسئله صدق پذیری دودویی توضیح و حل شوند. این در قسمتی است که بیان می‌کند چرا AES (برای مثال) بعد از معکوس شدن یک نگاشت آفین دارد.

انواع تخصصی

• رمزنگاری دیفرانسیل مرتبه بالاتر
• رمزنگاری دیفرانسیل کوتاه شده
• رمزنگاری دیفرانسیل غیرممکن
• حمله بومرنگ

جستارهای وابسته

• رمزنگاری
• رمزنگاری خطی

منابع

• Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. شابک ‎۰−۳۸۷−۹۷۹۳۰−۱, شابک ‎۳−۵۴۰−۹۷۹۳۰−۱.
• Biham, E. and A. Shamir. (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology — CRYPTO '90. Springer-Verlag. 2–21.
• Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES," CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991. (Postscript)