أدوات المطورين · SHA حاسبة التجزئة
شرح Merkle–Damgård: البناء وراء SHA-1 وSHA-2
· خلفية
شا-256 التشفير متصفح API
لا يمكن لوظيفة الضغط ذات الحجم الثابت تجزئة الإدخال التعسفي من تلقاء نفسها. تقوم Merkle – Damgård بربطها كتلة تلو الأخرى. يشرح هذا المنشور البناء وفكرة إثباته ونقاط الضعف التي يحملها.
الإدخال التعسفي والإخراج الثابت — المشكلة التي يجب على كل دالة تجزئة حلها أولاً
يجب أن تقوم دالة التجزئة بتعيين الإدخال التعسفي إلى الإخراج الثابت. يجب أن تنتج رسالة بحجم ثلاثة بايت ورسالة بحجم ثلاثة ميغا بايت بالضبط 256 bits من الإخراج لـ SHA-256. يجب أن تكون التجزئة حتمية، وبالتالي فإن نفس المدخلات تنتج دائمًا نفس المخرجات. يجب أن يبدو الإخراج عشوائيًا؛ إن تغيير بت واحد من الإدخال يجب أن يغير ما يقرب من نصف بتات الإخراج.
تبدو هذه المتطلبات متناقضة للوهلة الأولى، لأن خوارزمية واحدة سريعة لا يمكنها التعامل مع الرسائل ذات الطول العشوائي وإنتاج مخرجات موحدة ذات عرض ثابت. يحل بناء Merkle – Damgård هذه المشكلة عن طريق استخدام وظيفة ضغط ذات حجم ثابت بشكل متكرر، مما يؤدي إلى تغذية مخرجات كل تطبيق في مدخلات التطبيق التالي. يتم استخدام هذا البناء بواسطة SHA-1 وكل SHA-2 (SHA-256، SHA-384 وSHA-512).
وظيفة الضغط - خلاط ذو حجم ثابت يأخذ حالة وكتلة ويعيد حالة جديدة
وظيفة الضغط هي وظيفة التشفير الأساسية التي تعمل على تشغيل تجزئة Merkle-Damgård. يستغرق الأمر حالة ذات حجم ثابت، عادةً 256 bits لـ SHA-256 أو 512 bits لـ SHA-512، وكتلة إدخال ذات حجم ثابت، عادةً 512 bits لـ SHA-256 أو 1024 bits لـ SHA-512. تقوم وظيفة الضغط بمزجها معًا باستخدام عمليات البت والتدوير وعمليات البحث في الجدول، مما يؤدي إلى إنتاج حالة جديدة بنفس الحجم. يجب أن تكون هذه الوظيفة مقاومة للتصادم: يجب أن يكون من الصعب العثور على زوجين مختلفين (الحالة، الكتلة) ينتجان نفس المخرجات.
وظيفة الضغط نفسها ليست وظيفة تجزئة كاملة، فهي لا تتعامل مع طول الإدخال التعسفي، ولا تتعامل حتى مع الإدخال الأول، الذي ليس له حالة سابقة. وبدلا من ذلك، فهو لبنة البناء التي يتم بناء بناء أكبر حولها. وظيفة الضغط هي عملية التشفير الوحيدة التي يتم تشغيلها بشكل متكرر؛ كل شيء آخر هو مسك الدفاتر الذي يربط هذه الوظيفة بتجزئة كاملة.
التسلسل ومتجه التهيئة – كيف تتغذى الكتل على بعضها البعض من حالة بداية ثابتة
متجه التهيئة هو حالة البداية الثابتة، ويتم اختياره بعناية لتجنب التماثلات أو نقاط الضعف. بالنسبة إلى SHA-256، فإن IV عبارة عن ثماني كلمات ذات 32 بت مشتقة من الأجزاء الكسرية للجذور التربيعية للأعداد الأولية الثمانية الأولى. هذه القيم اعتباطية ولكنها حتمية، لذا فإن كل تطبيق يؤدي إلى نفس النتيجة. يتم خلط كتلة الرسالة الأولى مع IV باستخدام وظيفة الضغط، مما ينتج عنه حالة جديدة. يتم خلط كتلة الرسالة الثانية مع تلك الحالة، مما ينتج حالة جديدة أخرى، وهكذا من خلال كل كتلة من الرسالة.
هذا التسلسل هو الجزء الحاسم: يعتمد إخراج كتلة واحدة على جميع الكتل السابقة، لذا فإن تغيير أي جزء من أي كتلة سابقة يؤدي إلى تغيير جميع الكتل اللاحقة. بحلول الوقت الذي تتم فيه معالجة الكتلة النهائية، تحتوي الحالة على معلومات حول كل جزء من الإدخال. الحشو هو الحيلة التي تجعل هذا البناء سليمًا. لا يتم دائمًا تقسيم الرسالة بالتساوي إلى كتل. يستخدم بناء Merkle – Damgård تعزيز MD: إلحاق بت واحد واحد بالرسالة، ثم إلحاق الأصفار حتى تبقى كتلة كاملة تقريبًا، ثم إلحاق طول الرسالة الأصلية.
الحشو بطول الرسالة - لماذا تقوية MD هي ما يجعل البناء سليمًا
تقول الحجة الأمنية لـ Merkle – Damgård أنه إذا كانت وظيفة الضغط مقاومة للتصادم، فإن التجزئة بأكملها مقاومة للتصادم. والدليل هو التخفيض: إذا تمكنت من العثور على تصادم في التجزئة، فيمكنك استخراج تصادم في وظيفة الضغط، وهو ما يتعارض مع الافتراض بأن وظيفة الضغط من الصعب الاصطدام بها. البديهي هو أن أي تصادم في التجزئة يجب أن يؤدي في النهاية إلى حدوث تصادم في إحدى استدعاءات دالة الضغط، لأن الحالة يتم ترحيلها بالكامل.
تم اكتشاف نقاط الضعف في Merkle – Damgård مع مرور الوقت، على الرغم من أن البناء الأساسي سليم. امتداد الطول هو واحد: يمكن للمهاجم الذي يرى ملخص الرسالة توسيع الرسالة وحساب ملخص صالح للرسالة الأطول دون معرفة أي شيء عن الإدخال. تعتبر هجمات ما قبل الصورة الثانية أمرًا آخر: نظرًا لوجود رسالة، يكون العثور على رسالة مختلفة بنفس التجزئة أسهل مما ينبغي بالنسبة لبعض أنواع الرسائل. حفزت نقاط الضعف هذه على تصميم SHA-3، والذي يستخدم أسلوبًا مختلفًا يسمى البناء الإسفنجي.
حشوة ترميز الطول تفصل الرسائل المبطنة؛ دليل الأمان الكامل موجود خارج دليل المستودع
تأخذ وظيفة الضغط لـ SHA-256 حالة 256 بت (ثماني كلمات 32 بت) وكتلة 512 بت. تستخدم العملية 64 جولات، كل منها يمزج الحالة مع ثابت وكلمة من الكتلة. يستخدم الخلط عمليات البت: XOR، AND، NOT. ويستخدم عمليات التدوير والتحولات التي تحرك البتات دون تغيير البتات التي تم تعيينها. ويستخدم عمليات بحث الجدول التي توفر خلطًا غير خطي لا يمكن لـ XOR تحقيقه بمفرده.
يستخدم SHA-512 نفس البنية مثل SHA-256 ولكن مع عمليات 64 بت بدلاً من عمليات 32 بت. الحالة هي 512 bits (ثماني كلمات 64 بت)، وحجم الكتلة هو 1024 bits. تحتوي وظيفة الضغط على 80 جولات بدلاً من 64، كما أن الثوابت وعمليات البحث في الجدول مختلفة. بالنسبة إلى SHA-384، تكون وظيفة الحالة والضغط هي نفسها SHA-512، ولكن يتم إخراج 384 bits الأولى فقط من الحالة النهائية. تم تجاهل آخر 128 bits. هذا الاقتطاع هو سبب مقاومة SHA-384 لتمديد الطول.
امتداد الطول هو حدود البناء التي تم التحقق منها؛ تم حذف ادعاءات التصادم المتعدد وSHA-3
يعتمد أمان تجزئة Merkle – Damgård على العديد من الخصائص التي تمتلكها. يجب أن تكون وظيفة الضغط مقاومة للتصادم، لذا فإن مهاجمتها بشكل مباشر غير ممكنة. يجب أن يضمن نظام الحشو أن الرسائل المختلفة تنتج أشكالًا مبطنة مختلفة، لذلك يجب أن يتضمن كل تصادم في التجزئة تصادمًا لوظيفة الضغط. يجب أن يكون حجم الكتلة وحجم الحالة كبيرًا بما يكفي بحيث تكون القوة الغاشمة غير ممكنة. تعمل الحالة الأوسع على توسيع مساحة البحث العامة، لكن هذه المقالة لا ترفق عدد العمليات أو تاريخ الجدوى بدون اشتقاق مضمّن ومصدر تمت مراجعته.
إذا وجد المهاجم نقطة ضعف في وظيفة الضغط، أو إذا أصبحت أجهزة الكمبيوتر الكمومية عملية ويمكنها البحث في مساحة غير منظمة في وقت sqrt(2^n) بدلاً من 2^n من الوقت، فإن هوامش الأمان تتآكل. لم تكن نقطة الضعف التي حفزت SHA-3 انقطاعًا في وظيفة الضغط، بل كانت مشكلة تمديد الطول ونقاط الضعف الهيكلية الأخرى. يتجنب البناء الإسفنجي ذلك من خلال عدم نشر حالته الداخلية الكاملة أبدًا.
ما لا يغطيه هذا - الوظائف الدائرية المحددة لـ SHA-256، تمت تغطيتها في منشور منفصل
إن الطريقة التي يتعامل بها بناء Merkle – Damgård مع كل حجم المدخلات هي النتيجة العملية لتصميمه. قم بتقسيم الرسالة إلى كتل 512 بت، وقم بتضمين الكتلة الأخيرة، ومعالجة كل كتلة من خلال وظيفة الضغط بالتسلسل، وإخراج الحالة النهائية. بالنسبة للإدخال أحادي البايت، تنتج الحشوة كتلة 512 بت (بايت واحد من الرسالة، وبت واحد من الحشو، و447 bits من الأصفار، و64 bits للطول). عدد الضغطات هو عدد الكتل 512 بت، وهو ما يتناسب مع طول الرسالة.
كل ملخص تنتجه حاسبة التجزئة ToolAcre SHA يأتي من هذا البناء. ملخص 64 المكون من حرف SHA-256 هو الحالة النهائية 256 بت المطبوعة بالنظام الست عشري. ملخص 128 المكون من أحرف SHA-512 هو الحالة النهائية 512 بت المطبوعة بالنظام الست عشري. ملخص 96 المكون من أحرف SHA-384 هو أول 384 bits من الحالة النهائية 512 بت. تضمن المساحة المتروكة خلف الكواليس أن كل رسالة محتملة تنتج العدد الصحيح من الكتل وعرض الملخص الصحيح. هذا هو بناء Merkle – Damgård القياسي الذي يتم تشغيله في المتصفح.
الوجبات الجاهزة: نفس الهيكل وراء أربع خوارزميات - كل ملخص تنتجه حاسبة التجزئة ToolAcre SHA يأتي من هذا البناء
يعد فهم البناء مفيدًا لمعرفة سبب كون الملخصات دائمًا بنفس العرض ولماذا يؤدي تغيير جزء واحد من المدخلات إلى تغيير الملخص بأكمله. تعني خاصية التسلسل أن كل جزء من المدخلات يؤثر على كل جزء من المخرجات من خلال سلسلة من عمليات الخلط. سيتم نشر تغيير بمقدار بت واحد في وقت مبكر من الرسالة من خلال جميع عمليات الضغط اللاحقة، وبالتالي فإن الملخص النهائي مختلف تمامًا. تسمى هذه الخاصية بتأثير الانهيار الجليدي وهي بمثابة توقيع لوظيفة تجزئة الصوت.
لقد تم استخدام بناء Merkle – Damgård منذ عقود ويشكل الأساس لوظائف التجزئة الأكثر انتشارًا. تم إنشاء SHA-1 وSHA-2 على هذا البناء، وتعتمد العديد من الأنظمة المنشورة على مخرجاتها. إن البناء مؤسس وليس تجريبيًا، لكن هذا التاريخ لا يجعل كل استخدام آمنًا؛ تمديد الطول هو أحد الحدود الموثقة. يساعد فهم هذا البناء المطورين على فهم سبب بقاء بعض خصائص الأمان وسبب وجود نواقل هجوم معينة.