لماذا لا يمكن عكس قيم تجزئة MD5؟

Question

أحد المفاهيم التي طالما تساءلت عنها هو استخدام وظائف وقيم التشفير.أدرك أن هذه الوظائف يمكن أن تولد قيمة تجزئة فريدة ومن المستحيل تقريبًا عكسها، ولكن هذا ما كنت أتساءل عنه دائمًا:

إذا كان على الخادم الخاص بي، في PHP أقوم بإنتاج:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

عندما تقوم بتشغيل نفس السلسلة من خلال وظيفة MD5، فإنك تحصل على نفس النتيجة عند تثبيت PHP الخاص بك.يتم استخدام العملية لإنتاج بعض القيمة، من بعض القيمة الأولية.

ألا يعني هذا أن هناك طريقة ما لتفكيك ما يحدث وعكس قيمة التجزئة؟

ما الذي يجعل هذه الوظائف تجعل من المستحيل تتبع السلاسل الناتجة؟

Answer 1

والمواد المدخلات يمكن أن يكون طول لانهائي، حيث الإخراج هو دائما 128 بت طويلة. وهذا يعني أن عددا لا حصر له من سلاسل الإدخال ستكون على نفس الناتج.

إذا اخترت رقم عشوائي ونقسمه على 2 ولكن الكتابة فقط أسفل الباقي، ستحصل إما 0 أو 1 - أو حتى غريب، على التوالي. هل من الممكن أن تأخذ ذلك 0 أو 1 والحصول على العدد الأصلي؟

Answer 2

إذا كانت وظائف التجزئة مثل MD5 عكسها ثم كان يمكن أن يكون حدثا فاصلا في تاريخ خوارزميات ضغط البيانات! من السهل أن نرى أنه إذا كانت MD5 قطع ثم التعسفية عكسها من البيانات من حجم التعسفي يمكن أن يمثله مجرد 128 بت من دون أي خسارة من المعلومات. وهكذا كنت قد تمكنت من إعادة الرسالة الأصلية من عدد 128 بت بغض النظر عن حجم الرسالة الأصلية.

Answer 3

على عكس ما تؤكده الإجابات الأكثر تأييدًا هنا، فإن عدم الحقن (أي.أن هناك عدة سلاسل مجزأة بنفس القيمة) لوظيفة تجزئة التشفير الناتجة عن الفرق بين حجم الإدخال الكبير (الذي يحتمل أن يكون لا نهائيًا) وحجم الإخراج الثابت ليست النقطة المهمة - في الواقع، نحن نفضل وظائف التجزئة حيث نادرًا ما تحدث هذه التصادمات قدر الإمكان.

خذ بعين الاعتبار هذه الوظيفة (في تدوين PHP، كسؤال):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

يؤدي هذا إلى إلحاق بعض المسافات، إذا كانت السلسلة قصيرة جدًا، ثم يأخذ أول 16 بايت من السلسلة، ثم يقوم بترميزها كنظام سداسي عشري.وله نفس حجم الإخراج مثل تجزئة MD5 (32 حرفًا سداسيًا عشريًا، أو 16 بايت إذا حذفنا الجزء bin2hex).

print simple_hash("stackoverflow.com");

سيؤدي هذا إلى إخراج:

737461636b6f766572666c6f772e636f6d

تحتوي هذه الوظيفة أيضًا على نفس خاصية عدم الحقن كما أبرزتها إجابة Cody لـ MD5:يمكننا تمرير سلاسل من أي حجم (طالما أنها تناسب جهاز الكمبيوتر الخاص بنا)، وستخرج 32 رقمًا سداسيًا فقط.بالطبع لا يمكن أن يكون عن طريق الحقن.

ولكن في هذه الحالة، من السهل العثور على سلسلة يتم تعيينها لنفس التجزئة (فقط تطبيق hex2bin على التجزئة الخاصة بك، وكان لديك).إذا كان طول السلسلة الأصلية 16 (كما هو الحال في مثالنا)، فستحصل على هذه السلسلة الأصلية.لا ينبغي أن يكون أي شيء من هذا النوع ممكنًا بالنسبة إلى MD5، حتى لو كنت تعلم أن طول الإدخال كان قصيرًا جدًا (بخلاف تجربة جميع المدخلات الممكنة حتى نجد واحدًا مطابقًا، على سبيل المثال:هجوم بالقوة الغاشمة).

الافتراضات المهمة لوظيفة التجزئة المشفرة هي:

• من الصعب العثور على أي سلسلة تنتج تجزئة معينة (مقاومة ما قبل الصورة)
• من الصعب العثور على أي سلسلة مختلفة تنتج نفس التجزئة كسلسلة معينة (مقاومة الصورة الثانية)
• من الصعب العثور على أي زوج من السلاسل بنفس التجزئة (مقاومة الاصطدام)

من الواضح أن بلدي simple_hash الوظيفة لا تستوفي أيًا من هذه الشروط.(في الواقع، إذا قمنا بتقييد مساحة الإدخال بـ "سلاسل ذات 16 بايت"، فإن وظيفتي تصبح قابلة للحقن، وبالتالي تكون مقاومة للصورة الأولية الثانية ومقاومة للتصادم.)

توجد الآن هجمات تصادمية ضد MD5 (على سبيل المثال.من الممكن إنتاج زوج من السلاسل، حتى مع نفس البادئة المعطاة، والتي لها نفس التجزئة، مع بعض العمل، ولكن ليس الكثير من العمل المستحيل)، لذلك يجب ألا تستخدم MD5 لأي شيء مهم.لا يوجد حتى الآن هجوم Preimage، ولكن الهجمات سوف تتحسن.

للإجابة على السؤال الفعلي:

ما هو حول هذه الوظائف التي تجعل السلاسل الناتجة مستحيلة الاستعادة؟

ما تفعله MD5 (ووظائف التجزئة الأخرى المبنية على بنية Merkle-Damgard) بشكل فعال هو تطبيق خوارزمية تشفير مع الرسالة كمفتاح وبعض القيمة الثابتة مثل "النص العادي"، باستخدام النص المشفر الناتج كتجزئة.(قبل ذلك، يتم تعبئة المدخلات وتقسيمها إلى كتل، ويتم استخدام كل كتلة من هذه الكتل لتشفير مخرجات الكتلة السابقة، ويتم استخدام XORed مع مدخلاتها لمنع الحسابات العكسية.)

تم تصميم خوارزميات التشفير الحديثة (بما في ذلك تلك المستخدمة في وظائف التجزئة) بطريقة تجعل من الصعب استعادة المفتاح، حتى مع توفر النص العادي والنص المشفر (أو حتى عندما يختار الخصم أحدهما).يفعلون ذلك عمومًا عن طريق إجراء الكثير من عمليات خلط البتات بطريقة يتم من خلالها تحديد كل بتة إخراج بواسطة كل بتة مفتاح (عدة مرات) وأيضًا كل بتة إدخال.وبهذه الطريقة، لا يمكنك بسهولة تتبع ما يحدث بالداخل إلا إذا كنت تعرف المفتاح الكامل والإدخال أو الإخراج.

بالنسبة لوظائف التجزئة المشابهة لـ MD5 وهجوم preimage (مع سلسلة مجزأة ذات كتلة واحدة، لتسهيل الأمور)، لديك فقط إدخال وإخراج وظيفة التشفير الخاصة بك، ولكن ليس المفتاح (هذا هو ما تبحث عنه).

Answer 4

والجواب كودي بروسيوس هو حق واحد. بالمعنى الدقيق للكلمة، لا يمكن "عكس" وظيفة تجزئة ليتم تعيين العديد من السلاسل إلى نفس التجزئة. لاحظ، مع ذلك، أنه إما إيجاد <م> واحدة السلسلة التي يحصل تعيينها إلى تجزئة معين، أو تجد <م> اثنين السلاسل التي يحصل تعيينها إلى نفس التجزئة (أي الاصطدام )، سيكون اختراقات كبرى لcryptanalyst. صعوبة كبيرة في كل هذه المشاكل هو السبب في وظائف التجزئة جيدة مفيدة في التشفير.

Answer 5

وMD5 لا يخلق قيمة تجزئة فريدة من نوعها، هدف MD5 هو إنتاج بسرعة قيمة التغييرات استنادا إلى حد كبير على تغيير طفيف على حد تعبيره.

ومنها مثلا.

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

و(من الواضح أن هذا ليس التشفير MD5 الفعلي)

ومعظم التجزئة (إن لم يكن كلها) هي أيضا غير فريد. بدلا من ذلك، انهم فريدة من نوعها <م> بما فيه الكفاية ، لذلك كان الاصطدام واردا للغاية، ولكن لا يزال ممكنا.

Answer 6

وهناك طريقة جيدة للتفكير في خوارزمية البعثرة هي التفكير في تغيير حجم صورة في فوتوشوب ... نقول لديك الصورة التي هي 5000x5000 بكسل وكنت ثم حجمه لمجرد 32x32. ما لديك لا يزال تمثيل الصورة الأصلية لكنه أصغر بكثير من ذلك بكثير، وعلى نحو فعال "هدره" أجزاء معينة من بيانات الصورة لجعله مناسبا في حجم أصغر. حتى لو كنت لتغيير تلك الصورة 32x32 ما يصل الى 5000x5000 كل كنت أحصل في حالة من الفوضى ضبابية. ومع ذلك لأن صورة 32x32 ليست كبيرة سيكون تصور نظريا أن صورة أخرى يمكن تقليص حجم لإنتاج نفس بكسل بالضبط!

وهذا مجرد تشابه ولكنه يساعد على فهم ما يقوم به تجزئة.

Answer 7

وجود تضارب التجزئة هو أكثر احتمالا بكثير مما كنت اعتقد. نلقي نظرة على للحصول على فهم أكبر لماذا هذا هو.

Answer 8

نظرًا لأن عدد ملفات الإدخال المحتملة أكبر من عدد مخرجات 128 بت، فمن المستحيل تعيين تجزئة MD5 بشكل فريد لكل منها.

تُستخدم وظائف تجزئة التشفير للتحقق من سلامة البيانات أو التوقيعات الرقمية (يتم توقيع التجزئة من أجل الكفاءة).وبالتالي فإن تغيير المستند الأصلي يعني أن التجزئة الأصلية لا تتطابق مع المستند الذي تم تعديله.

تستخدم هذه المعايير أحيانًا:

1. مقاومة ما قبل الصورة:بالنسبة لوظيفة تجزئة معينة وتجزئة معينة، يجب أن يكون من الصعب العثور على مُدخل يحتوي على التجزئة المحددة لهذه الوظيفة.
2. المقاومة الأولية للصورة الثانية:بالنسبة لوظيفة ومدخلات تجزئة معينة، يجب أن يكون من الصعب العثور على إدخال ثانٍ مختلف بنفس التجزئة.
3. مقاومة الاصطدام:بالنسبة لوظيفة معينة، يجب أن يكون من الصعب العثور على مدخلين مختلفين بنفس التجزئة.

تم اختيار هذه المعايير لتجعل من الصعب العثور على مستند يطابق تجزئة معينة، وإلا سيكون من الممكن تزوير المستندات عن طريق استبدال المستند الأصلي بآخر مطابق للتجزئة.(حتى لو كان الاستبدال غير مفهوم، فإن مجرد استبدال النسخة الأصلية قد يتسبب في حدوث خلل.)

الرقم 3 يعني الرقم 2

أما بالنسبة لـ MD5 على وجه الخصوص، فقد ثبت أنه معيب:كيفية كسر MD5 ووظائف التجزئة الأخرى.

Answer 9

ولكن هذا هو المكان الذي تأتي الجداول قوس قزح في اللعب. أساسا انها مجرد كمية كبيرة من القيم تجزئته separetely ثم يتم حفظ النتيجة إلى القرص. ثم بت عكس هو "فقط" للقيام بحث في جدول كبير جدا.

ومن الواضح أن هذا أمر ممكن فقط لمجموعة فرعية من كل قيم المدخلات الممكنة ولكن إذا كنت تعرف حدود قيمة المدخلات قد يكون من الممكن لحساب ذلك.

Answer 10

وعالم صينى وجدت طريقة تسمى "الاصطدامات اختيار بادئة" لجعل الصراع بين سلسلتين مختلفة.

وهنا مثال: http://www.win .tue.nl / hashclash / fastcoll_v1.0.0.5.exe.zip
شفرة المصدر: http://www.win.tue.nl/hashclash /fastcoll_v1.0.0.5_source.zip

Answer 11

ونظرا لأن معظم سبق أن ذكرت صمم MD5 للتيارات البيانات طول متغير يتم تجزئته إلى قطعة طول محددة من البيانات، لذلك هو مشترك تجزئة واحدة من قبل العديد من تيارات إدخال البيانات.

ولكن إذا كنت من أي وقت مضى لم بحاجة لمعرفة البيانات الأصلية من الاختباري، على سبيل المثال إذا كان لديك تجزئة كلمة مرور وتحتاج إلى معرفة كلمة المرور الأصلية، فإنه غالبا ما يكون أسرع لمجرد جوجل (أو أيا كان الباحث كنت تفضل ) التجزئة للحصول على الجواب من القوة الغاشمة ذلك. لقد وجدت بنجاح بضعة كلمات المرور باستخدام هذا الأسلوب.

Answer 12

أفضل طريقة لفهم ما تعنيه جميع الإجابات الأكثر تصويتًا هي محاولة التراجع عن خوارزمية MD5.أتذكر أنني حاولت العودة MD5crypt منذ عدة سنوات، لم تكن هذه الخوارزمية لاستعادة الرسالة الأصلية لأنه من الواضح أن ذلك مستحيل، ولكن فقط لإنشاء رسالة من شأنها أن تنتج نفس التجزئة مثل التجزئة الأصلية.سيوفر لي هذا، من الناحية النظرية على الأقل، طريقة لتسجيل الدخول إلى جهاز Linux الذي قام بتخزين كلمة مرور المستخدم: في ملف /etc/passwd باستخدام الرسالة التي تم إنشاؤها (كلمة المرور) بدلاً من استخدام الرسالة الأصلية.نظرًا لأن كلا الرسالتين سيكون لهما نفس التجزئة الناتجة، فسيتعرف النظام على كلمة المرور الخاصة بي (التي تم إنشاؤها من التجزئة الأصلية) على أنها صالحة.هذا لم ينجح على الإطلاق.وبعد عدة أسابيع، إذا كنت أتذكر بشكل صحيح، تم استخدام ملح في الرسالة الأولى قتلني.كان عليّ أن أكتب ليس فقط رسالة أولية صالحة، بل رسالة أولية صالحة ومملحة، وهو ما لم أتمكن من القيام به على الإطلاق.لكن المعرفة التي حصلت عليها من هذه التجربة كانت لطيفة.

Answer 13

بحكم التعريف وظيفة التجزئة (تجزئة التشفير): لا ينبغي أن تكون قابلة للعكس؛ لا ينبغي أن يكون لها تصادمات (أقل قدر ممكن).

رج سؤالك :إنها طريقة واحدة للتجزئة.سيؤدي الإدخال (بغض النظر عن الطول) إلى إنشاء مخرجات ذات حجم ثابت. (سيتم حشوها بناءً على algo (حدود 512 بت لـ MD5)).يتم ضغط المعلومات (فقدها) ومن غير الممكن عملياً توليدها من التحويلات العكسية.

معلومات إضافية عن MD5:فهي عرضة للاصطدامات.لقد مررت بهذه المقالة مؤخرًا ،http://www.win.tue.nl/hashclash/Nostradamus/

يمكن العثور على التعليمات البرمجية المصدرية المفتوحة لتطبيقات تجزئة التشفير (MD5 وSHA) على كود Mozilla.(مكتبة فريبل).

Answer 14

والآن أيام MD5 علامات الرقم أو أي تجزئات أخرى لهذه المسألة وقبل محسوب لجميع السلاسل الممكنة وتخزينها ليسهل الوصول إليها. على الرغم من الناحية النظرية MD5 ليس عكسها ولكن باستخدام قواعد البيانات هذه قد معرفة أي نص أسفرت عن قيمة تجزئة معينة.

وعلى سبيل المثال محاولة رمز التجزئة التالية في http://gdataonline.com/seekhash.php لمعرفة ما نص اعتدت أن حساب تجزئة

aea23489ce3aa9b6406ebb28e0cda430

Answer 15

f(x) = 1 لا رجعة فيه.وظائف التجزئة ليست لا رجعة فيها.

هذا في الواقع مطلوب بالنسبة لهم للوفاء بوظيفتهم في تحديد ما إذا كان شخص ما يمتلك نسخة غير تالفة من البيانات المجزأة.يؤدي هذا إلى التعرض لهجمات القوة الغاشمة، والتي تعتبر قوية جدًا هذه الأيام، خاصة ضد MD5.

هناك أيضًا ارتباك هنا وفي أماكن أخرى بين الأشخاص الذين لديهم معرفة رياضية ولكن لديهم معرفة قليلة بفك التشفير.تعمل العديد من الأصفار ببساطة على XOR للبيانات باستخدام تدفق المفاتيح، ولذا يمكنك القول إن النص المشفر يتوافق مع جميع النصوص الواضحة بهذا الطول لأنه كان بإمكانك استخدام أي تدفق مفاتيح.

ومع ذلك، فإن هذا يتجاهل أن النص العادي المعقول ينتج من البذرة password هو أكثر احتمالا بكثير من آخر تنتجه البذور Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o لدرجة أن أي شخص يدعي أن الثاني هو احتمال سوف يضحك عليه.

وبنفس الطريقة، إذا كنت تحاول الاختيار بين كلمتي المرور المحتملتين password و Wsg5Nm^bkI4EgxUO, ، ليس من الصعب القيام بذلك كما يعتقد بعض علماء الرياضيات.

Answer 16

أنا أحب كل الحجج المختلفة.من الواضح أن القيمة الحقيقية للقيم المجزأة هي ببساطة توفير عناصر نائبة غير قابلة للقراءة من قبل الإنسان لسلاسل مثل كلمات المرور.ليس له فائدة أمنية معززة محددة.بافتراض أن أحد المهاجمين تمكن من الوصول إلى جدول يحتوي على كلمات مرور مجزأة، فيمكنه القيام بما يلي:

• قم بتجزئة كلمة مرور من اختياره ووضع النتائج داخل جدول كلمات المرور إذا كان لديه حقوق الكتابة/التحرير في الجدول.
• إنشاء قيم مجزأة لكلمات المرور الشائعة واختبار وجود قيم مجزأة مماثلة في جدول كلمات المرور.

في هذه الحالة، لا يمكن حماية كلمات المرور الضعيفة بمجرد تجزئتها.