چکیده:
علی¬رغم تحقیقات متعدد و تلاش¬های به¬عمل¬آمده در خصوص تحلیل الگوریتم¬های رمزنگاری با روش مصالحه¬ زمان و حافظه، سطح پوشش جداول هلمن و روش¬های مشابه در عمل کمتر از نصف بوده و احتمال موفقیت آنها به همین میزان و یا کمتر است. زنجیره¬های رمز هلمن در واقع مسیرهایی با رئوس آغازین و پایانی معین روی نمودار گراف تابع هستند. در این مقاله به تحلیل رفتار این زنجیره¬ها از دیدگاه گراف توابع تصادفی پرداخته شده است. در ابتدای مقاله پارامترهای گراف توابع تصادفی تعریف و سپس رفتار زنجیره¬های هلمن بر اساس این پارامترها تحلیل می¬شود. نتیجه تحلیل نشان می¬دهد که به دلایلی مانند وجود درصدی قابل توجه (حدود 37%) از رئوس پایانه¬ای و عدم امکان رخداد آنها روی زنجیره¬ها (مگر در رئوس آغازین)، وجود پارامترهای مناسبی همانند تعداد مولفه¬ها و طول مسیرهای بدون تکرار برای ساخت زنجیره¬ها، عدم توجه به احتمال ساخت یک زنجیره غیردوری برحسب پارامتر طول زنجیره و عدم توجه به احتمال برای ادغام زنجیره¬ها برحسب پارامترهای طول و تعداد آنها، سطح پوشش چنین جداولی نمی¬تواند در حد انتظار باشد. لذا عوامل مذکور باعث می¬شوند که سطح پوشش یک جدول هلمن از نقطه¬ای به بعد به سرعت کاهش یافته و در عمل ساخت آنها بی¬اثر باشد. این روش به طور عملی روی الگوریتم رمز mAES پیاده شده که نتایج آن تاییدکننده نتایج نظری تحقیق می¬باشد.
خلاصه ماشینی:
نتیجه تحلیل نشان می¬دهد که به دلایلی مانند وجود درصدی قابل توجه (حدود 37%) از رئوس پایانه¬ای و عدم امکان رخداد آنها روی زنجیره¬ها (مگر در رئوس آغازین)، وجود پارامترهای مناسبی همانند تعداد مؤلفه¬ها و طول مسیرهای بدون تکرار برای ساخت زنجیره¬ها، عدم توجه به احتمال ساخت یک زنجیره غیردوری برحسب پارامتر طول زنجیره و عدم توجه به احتمال برای ادغام زنجیره¬ها برحسب پارامترهای طول و تعداد آنها، سطح پوشش چنین جداولی نمی¬تواند در حد انتظار باشد.
حداکثر طول مسیر بدون تکرار در این گراف مربوط به نقاط پایانه¬ای 0 و 30 می¬باشد: >رجوع شود به تصویر صفحه> شکل (1): گراف تابع تصادفی >رجوع شود به تصویر صفحه> روشن است که فضای حالات پنهان، در روش هلمن، برای این تابع برابر S={0,1,…,31} خواهد بود.
اکنون با استفاده از تقریب استرلینگ برای محاسبه فاکتوریل اعداد بزرگ و با توجه به تقریبهای بالا داریم: >رجوع شود به تصویر صفحه> حال فرض کنید عدد c به گونهای انتخاب شده باشد که، t=c√N در این صورت داریم: >رجوع شود به تصویر صفحه> این رابطه به ما نشان می¬دهد که اگر از یک نقطه تصادفی شروع به ساخت یک زنجیره رمز نمائیم، مانند آن است که از یک رأس دلخواه روی گراف یک تابع تصادفی شروع به حرکت کنیم و طول مسیر طی شده، قبل از آنکه به اولین تکرار برسیم، با احتمال e^(-t^2/2N) ، بزرگتر یا مساوی عدد طبیعی t خواهد بود.
Paget, "GSM-SRSLY," Congress slides during CCC 2009, retrieved from http:/events.
K. Nohl, "Attacking phone privacy," Convention slides during Black Hat USA 2010, retrieved from https://media.