حلقه در MD5

[cardano7]

سلام
این سوال را در سایتی معروف پرسیدم و ادمین های وب سایت این سوال را بر نتافته تاپیک را بستند و بعد هم پاکش کردند. اومدم اینجا حداقل هموطنانمون اندیشه های بازتری دارند.
در هر الگوریتم هش این احتمال وجود دارد که هش یکی عبارت خودش بشود:
x = hash(x)
فارق از اینکه الگوریتم چی باشه، احتمال چنین رویدادی 63٪ هست
(1-1/e) = 63%
e=عدد نپر
علتش هم این هست که فضای کلیدها محدودیت داره و نمی شود از این محدودیت فرار کرد.
تا حالا هم کسی در md5 یا sha1 چنین کلیدی را کشف نکرده و پردازش همه ی موارد ممکن ها بیش از میلیاردها میلیارد سال زمان می برد.
این مقدمه را گفتم که به اینجا برسم که درسته که نقطه ی ثابتی تا حالا کشف نشده اما حالت کلی تر آن که یک حلقه می شود چطور؟
وقتی هش های متعدد(هش روی هش) انجام می دهیم و فضای کلید محدود است، حتما باید حلقه هایی در فضای هش وجود داشته باشد. آیا کسی در باره ی این حلقه ها اطلاعی دارد؟ آیا تا کنون موردی از آنها کشف شده است(چه md5 و چه sha1)؟

با سپاس

[newsoft]

سلام من اصلا بخش مقدمشو متوجه نمی شم
چطور

احتمال چنین رویدادی 63٪ هم هست
ولی هنوز تا به حال کسی

در md5 یا sha1 چنین کلیدی را کشف نکرده

یه کم بیشتر توضیح میدین

[cardano7]

احتمال چنین رویدادی 63٪ هست منظور من احتمال وجود کلیدی است که خودش حاصل md5 خودش باشد:
x=md5(x)
مثلا:
cdd840c6e994e6ccefe8b2b67e810017 = md5(cdd840c6e994e6ccefe8b2b67e810017)
آیا امکان دارد چنین x ی پیدا شود؟ کسی نمی داند و چک کردن آن هم با پردازنده های موجود امکان پذیر نیست. ولی احتمال آن 63% تخمین زده شده است. اگر منظور شما محاسبه ی این عدد هست، اینجا (http://www.redcode.nl/blog/2010/01/md5-fixed-point/)
را ببینید. البته یک لینک خوبی هم داشتم که نمی تونم به راحتی اون را پیدا کنم.

اما من بیشتر به دنبال حلقه می گردم. مثلا فرض کنید هر یک از این عبارت ها حاصل md5 خط بالایی خود باشد:
4b1b41f2d8e1527d45709c6924f2275c
↓ md5
1cf0bdae21c94564f645cbd692f3a23c
↓ md5
8eb4e0d18adfe1352bb0188e908d5095
↓ md5
86e35137ab9541e2559aa24d51d89e74
↓ md5
4b1b41f2d8e1527d45709c6924f2275c

آن زمان عبارت سرخ رنگ حاصل چهار بار md5 کردن خودش می شود. و تشکیل حلقه می دهد. من به دنبال چنین حلقه ای می گردم. این سوال بیشتر ریاضی است تا برنامه نویسی اما امنیت الگوریتم های هش را نشان می دهد.

(البته همه ی کلید های مثال زده شده تنها برای مثال بوده و md5‌ آنها واقعا مقادیر نمایش داده شده در اینجا نیست)

[eshpilen]

سلام
فارق از اینکه الگوریتم چی باشه، احتمال چنین رویدادی 63٪ هست
(1-1/e) = 63%
e=عدد نپر

جان؟
63%؟ :متعجب:
اون فرمول از کجا اومده؟

فکر کنم اشتباهی رخ داده.
احتمالش باید خیلی خیلی کمتر از این حرفا باشه.
اگر 63% احتمال داشت پس با چندتا تست ساده باید همچین اتفاقی مشاهده میشد!

[eshpilen]

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

در پرانتز: «البته بگذریم از اینکه MD5 الان دیگه بعنوان یک هش امن محسوب نمیشه دقیقا بخاطر همینکه چنین ویژگیهای اون مورد خدشه واقع شدن و عملا میشه داده های ورودی رو طوری طراحی کرد که hash collision پیش بیاد (یعنی هش یکسان برای ورودیهای متفاوت). البته hash collision با چیزی که شما میگی فرق میکنه.
بهرحال شما بهتره یک هشی رو که امن بحساب میاد معیار قرار بدید.
البته اگر شما ورودی رو رندوم انتخاب کنی، بنظرم اونوقت MD5 هم طبق همین فرضیه عمل میکنه و در این زمینه مشکلی نداره.
پس بستگی داره که میخوای فقط کار تئوریک بکنی یا امنیت واقعی مد نظرته.»

با فرض داشتن یک الگوریتم هش بی نقص، اینکه بپرسیم احتمال اینکه هش یک چیزی با خودش برابر بشه چقدره، معادل این سواله که بپرسیم احتمال اینکه یه چیزی رو (یک چیزی که رندوم انتخاب میکنیم) هش کنیم و یک مقدار هش خاص (مثلا ac5839f0...) بدست بیاد چقدره.
خب احتمالش روشنه: یک تقسیم بر 2 به توان 128.
چون خروجی یک هش 128 بیتی همین مقدار حالت ممکنه داره.

[cardano7]

فکر کنم اشتباهی رخ داده.تاکید می کنم، احتمال اینکه میان همه ی کلیدهای موجود دست کم یک مورد این چنینی پیدا شود 63٪ هست. و نه اینکه برای هر هش چنین احتمالی وجود داشته باشد.


اینکه هش یک عبارت خودش بشه بنظرم تاجاییکه در حیطهء دانش فعلی است، یک چیزی کاملا رندوم بحساب میاد.شما عبارت hash fixed point probability را جستجو کنید. روابط ریاضی اش موجود هست. این 63٪ بهترین حالت هست.


معادل این سواله که بپرسیم احتمال اینکه یه چیزی رو هش کنیم و ...
یک زمانی من هم همین طوری فکر می کردم ولی متوجه شدم که مسائل مربوط به احتمال را خیلی باید با احتیاط حل کرد. یک مورد اون مسئله مونتی هال (http://en.wikipedia.org/wiki/Monty_Hall_problem) هست. که مردم فورا به طور ذهنی جواب غلط می دهند. حتما راه حل fixed point را بخونید. نظرتون عوض میشه.

[eshpilen]

احتمالا شما دنبال این بودی که از این روش بتونی از روی هش به کلید یا هر اطلاعات اولیه ای که هش شده دست پیدا کنی؛ چون هش ها چیزی هستن که خیلی وقتا در معرض دسترسی پابلیک قرار میدن (یا بهرصورت مجبورن به این کار) و فرض بر اینه که نمیشه با روشی غیر از Brute-force از اون هشها به دیتای اولیه رسید.

باید بگم که در این زمینه کاملا اشتباه کردی و تیرت به سنگ خورد :لبخند:

این چه روش احتمالات محاسبه کردنه!
مرد حسابی اگر احتمالش اینقدر بالا بود که الان نمیشد دنیا روی این هش ها این همه اتکا بکنه!
ضمنا دوتا تست میکردی باید همچین چیزی جلوی چشمت رخ میداد.

[cardano7]

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

[eshpilen]

تاکید می کنم، احتمال اینکه میان همه ی کلیدهای موجود دست کم یک مورد این چنینی پیدا شود 63٪ هست. و نه اینکه برای هر هش چنین احتمالی وجود داشته باشد.

خب الان داستان عوض شد.
اون چیزی که شما اول نوشتی یه معنی دیگه میده.
بیان خودت مشکل داشت.
چیزی که شما قبلا گفتی این بود:

در هر الگوریتم هش این احتمال وجود دارد که هش یک عبارت خودش بشود.
فارق از اینکه الگوریتم چی باشه، احتمال چنین رویدادی 63٪ هست.

[cardano7]

به نظر من مشکل نداره. با هم کلی فرق دارند:

هش هر عبارت خودش بشود
هش یک عبارت خودش بشود


حالا بگذریم. هیچ جوابی نه فارسی نه انگلیسی براش پیدا نکردم

[eshpilen]

این مقدمه را گفتم که به اینجا برسم که درسته که نقطه ی ثابتی تا حالا کشف نشده اما حالت کلی تر آن که یک حلقه می شود چطور؟فکر کنم دشواری کشف یک حلقه برابر دشواری کشف نقطهء ثابت باشه.
چون بهرحال در یک حلقه هم شما داری بجای یک هش چندتا هش میگیری و به همون نسبت پردازش شما زیاد میشه.
بنابراین اگر پیدا کردن نقطهء ثابت صرف نمیکنه/عملی نیست، پیدا کردن حلقه هم دقیقا همونقدر صرف نمیکنه/عملی نیست!

طبیعتا انتظاری هم نمیره که اینها بطور تصادفی کشف بشن؛ چون احتمالش خیلی کمه.
ولی البته اگر در الگوریتم هش خدشه های تئوریک/ریاضی قابل بهره برداری کشف بشه که برای این مورد قابل بهره برداری باشن، مثل اتفاقی که درمورد MD5 در زمینهء collision افتاد، اونوقت ممکنه بشه به حلقه یا نقطهء ثابت هم رسید.
با صرف Brute-force یا اتکا به شانس، بنظرم عملی نیست.

[cardano7]

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