fa معرفی حمله بده‌بستان زمان-حافظه (TMTO) بر توابع چکیده‌‌ساز رمز و امنیت اطلاعات Cryptology and Information Security مروری Review Article <strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">در این مقاله به معرفی حمله </span></span></strong><strong><span dir="LTR"><span style="font-family:times new roman bold,serif;"><span style="font-size:8.0pt;">TMTO</span></span></span></strong><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;"> و نحوه پیدا‌کردن نزدیک- برخوردها در یک تابع چکیده‌ساز پرداخته شده است. با در‌نظر‌گرفتن محاسبات چکیده‌ساز، محاسبه یک حد پایین برای پیچیدگی الگوریتم‌های نزدیک - برخورد و ساخت یک الگوریتم مطابق با آن آسان است؛ با این حال، این الگوریتم نیاز به</span> مقدار زیادی حافظه دارد و موجب استفاده از </span></strong><span style="position:relative;top:2.5pt;"><span style="font-family:calibri,sans-serif;"><span style="font-size:11.0pt;"> </span></span></span>&nbsp;<strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">حافظه می‌شود. </span>به‌تازگی، چند الگوریتم بدون نیاز به این مقدار حافظه ارائه شده‌اند.</span></strong> <strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">این الگوریتم‌ها نیاز به مقدار بیشتری از محاسبات چکیده‌ساز دارند؛ اما این حمله در واقعیت عملی‌تر است. این دسته از الگوریتم‌ها را به دو دسته اصلی می‌‌‌‌‌توان تقسیم کرد:</span></span></strong> <strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">گروهی مبتنی بر کوتاه‌سازی و گروهی دیگر مبتنی بر کد‌های پوششی هستند.</span></span></strong> <strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">در این کار، بده</span></span></strong><strong><span dir="LTR"><span style="font-family:times new roman bold,serif;"><span style="font-size:8.0pt;">‌</span></span></span></strong><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">بستان زمان‌-‌حافظه برای الگوریتم‌های مبتنی بر کوتاه‌سازی در نظر گرفته شد. برای پیاده‌سازی عملی، می‌توان فرض کرد مقداری از حافظه موجود است و نشان داد که با استفاده از این حافظه قابل‌توجه پیچیدگی را می‌توان کاهش داد؛ در مرحله بعد، با استفاده از</span></span></strong> <strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">&nbsp;برخورد</span></span></strong><strong><span dir="LTR"><span style="font-family:times new roman bold,serif;"><span style="font-size:8.0pt;">‌</span></span></span></strong><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">های متعدد براساس جدول هلمن، بهبود شناخته‌شده‌ترین بده‌بستان زمان حافظه، برای </span></span></strong>&nbsp;<strong><span dir="LTR"><span style="font-family:times new roman bold,serif;"><span style="font-size:8.0pt;">K</span></span></span></strong><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">درخت ارائه شد. در‌نتیجه، منحنی بده‌بستان جدید </span></span></strong><span style="position:relative;top:2.5pt;"><span style="font-family:calibri,sans-serif;"><span style="font-size:11.0pt;"> </span></span></span><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">&nbsp;به‌دست آورده شد، با در‌نظرگرفتن </span></span></strong><strong><span dir="LTR"><span style="font-family:times new roman bold,serif;"><span style="font-size:8.0pt;">k = 4</span></span></span></strong><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;"> منحنی بده‌بستان به شکل&nbsp; </span></span></strong>&nbsp;<span style="position:relative;top:2.5pt;"><span style="font-family:calibri,sans-serif;"><span style="font-size:11.0pt;"> </span></span></span><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">خواهد بود. در این مقاله،</span></span></strong> <strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">ابتدا روش‌های </span></span></strong><strong><span dir="LTR"><span style="font-family:times new roman bold,serif;"><span style="font-size:8.0pt;">TMTO</span></span></span></strong><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;"> و سپس نحوه پیدا‌کردن نزدیک-برخورد با استفاده از </span></span></strong><strong><span dir="LTR"><span style="font-family:times new roman bold,serif;"><span style="font-size:8.0pt;">TMTO</span></span></span></strong><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;"> شرح داده می</span></span></strong><strong><span dir="LTR"><span style="font-family:times new roman bold,serif;"><span style="font-size:8.0pt;">‌</span></span></span></strong><strong><span style="font-family:b nazanin;"><span style="font-size:10.0pt;">شود.</span></span></strong> <strong>In this article, we introduce Time Memory Trade Off attack and a method for finding near collisions in a hash function. By considering hash computations, it is easy to compute a lower bound for the complexity of near-collision algorithms, and to construct matching algorithm. However, this algorithm needs a lot of memory, and uses </strong> <strong>&nbsp;memory accesses. Recently, some algorithms have been proposed that do not require this amount of memory<span dir="RTL">.</span> They need more hash evaluation, but this attack is actually more practical. These algorithms can be divided in two main group: the first group is based on truncation and the second group is based on covering codes. In this paper, we consider the first group that is based on truncation. For practical implementation, it can be assumed that some memory is available, </strong><strong>Leurent</strong> <strong>[</strong><a href="file://tsclient/D/monadi.1396.11.28/2.zolfaghari/zolfaghari.Edited.docx#_ENREF_10" title="Leurent, 2013 #7"><strong>10</strong></a><strong>]</strong> <strong>showed that it is possible to reduce the complexity significantly by using this memory. In the next step, Sasaki et al. </strong><strong>[</strong><a href="file://tsclient/D/monadi.1396.11.28/2.zolfaghari/zolfaghari.Edited.docx#_ENREF_9" title="Nikolić, 2014 #16"><strong>9</strong></a><strong>]</strong><strong> proposed improvement of most popular Time Memory Trade off for K-tree algorithm by using multi-collision based on Helman&rsquo;s table. As a result, they obtained new trade off curve </strong> <strong>&nbsp;that for k=4 the tradeoff curve will be </strong> <strong><em>. </em></strong><strong>In this article, at the first the methods of TMTO</strong><strong>, and then the method of finding near-collision by using TMTO are explained.</strong> تابع چکیده‌ساز, نزدیک-برخورد, بده‌بستان زمان–حافظه Hash function, Near-collision, Time Memory Trade Off 15 26 http://monadi.isc.org.ir/browse.php?a_code=A-10-209-2&slc_lang=fa&sid=1 Zahra Zolfaghari زهرا ذوالفقاری . z.zolfaghari71@gmail.com 1003194753284600601 1003194753284600601 Yes دانشکده برق دانشگاه تربیت دبیر شهید رجایی Nasour Bagheri نصور باقری NBagheri@srttu.edu 1003194753284600600 1003194753284600600 No دانشکده برق دانشگاه تربیت دبیر شهید رجایی