كيف سيكون بوابة التعامل مع SHA-1 تصادم على blob ؟

Question

هذا ربما لم يحدث في العالم الحقيقي بعد و قد لا يحدث ، ولكن دعونا النظر في هذا:نقول لديك git ، وجعل ارتكاب والحصول جدا جدا سيئ الحظ:واحدة من النقط ينتهي وجود نفس SHA-1 آخر الذي هو بالفعل في المستودع الخاص بك.السؤال هو كيف سيكون بوابة التعامل مع هذا ؟ ببساطة تفشل ؟ إيجاد طريقة لربط اثنين من النقط و تحقق واحد الذي هو حسب السياق ؟

المزيد من الدماغ دعابة من مشكلة فعلية ، ولكن وجدت مسألة مثيرة للاهتمام.

Answer 1

أجريت تجربة لمعرفة كيف سيتصرف Git بالضبط في هذه الحالة. هذا مع الإصدار 2.7.9 ~ rc0 + next.20151210 (إصدار دبيان). لقد قللت للتو حجم التجزئة من 160 بت إلى 4 بت من خلال تطبيق الفرق التالي وإعادة بناء git: Genacodicetagpre

ثم قمت ببعض الالتزامات ولاحظت ما يلي

1. في حالة وجود blob بالفعل بنفس التجزئة ، فلن تتلقى أي تحذيرات على الإطلاق. يبدو أن كل شيء على ما يرام ، ولكن عندما تدفع ، أو يستنسخ شخص ما ، أو تعود ، ستفقد أحدث إصدار (بما يتماشى مع ما تم شرحه أعلاه).
2. إذا كان كائن الشجرة موجودًا بالفعل وقمت بإنشاء فقاعة بنفس التجزئة: سيبدو كل شيء طبيعيًا ، حتى تحاول الدفع أو يستنسخ شخص ما مستودعك. عندها سترى أن الريبو فاسد.
3. إذا كان كائن التنفيذ موجودًا بالفعل وقمت بإنشاء blob بنفس التجزئة: مثل # 2 - فاسد
4. إذا كان blob موجودًا بالفعل وقمت بإنشاء كائن تنفيذ بنفس التجزئة ، فسوف يفشل عند تحديث "المرجع".
5. إذا كانت النقطة موجودة بالفعل وقمت بإنشاء كائن شجرة بنفس التجزئة. سوف تفشل عند إنشاء الالتزام.
6. إذا كان كائن الشجرة موجودًا بالفعل وقمت بإنشاء كائن تنفيذ بنفس التجزئة ، فسوف يفشل عند تحديث "المرجع".
7. إذا كان كائن الشجرة موجودًا بالفعل وقمت بإنشاء كائن شجرة به نفس التجزئة ، فسيبدو كل شيء على ما يرام. ولكن عندما تلتزم ، سيرجع كل المستودع إلى الشجرة الخطأ.
8. إذا كان كائن الالتزام موجودًا بالفعل وقمت بإنشاء كائن تنفيذ بنفس التجزئة ، فسيبدو كل شيء على ما يرام. ولكن عند الالتزام ، لن يتم إنشاء الالتزام أبدًا ، وسيتم نقل مؤشر HEAD إلى التزام قديم.
9. إذا كان كائن الالتزام موجودًا بالفعل وقمت بإنشاء كائن شجرة بنفس التجزئة ، فسوف يفشل عند إنشاء الالتزام.

بالنسبة للخطأ الثاني ، ستحصل عادةً على خطأ مثل هذا عند تشغيل "git push":

Genacodicetagpre

أو: Genacodicetagpre

إذا حذفت الملف ثم شغلت "git checkout file.txt".

بالنسبة للرقمين 4 و 6 ، ستحصل عادةً على خطأ مثل هذا: Genacodicetagpre

عند تشغيل "git الالتزام". في هذه الحالة ، يمكنك عادةً كتابة "git الالتزام" مرة أخرى لأن هذا سيؤدي إلى إنشاء تجزئة جديدة (بسبب الطابع الزمني المتغير)

بالنسبة للرقمين 5 و 9 ، ستحصل عادةً على خطأ مثل هذا: Genacodicetagpre

عند تشغيل "git الالتزام"

إذا حاول شخص ما استنساخ مستودعك التالف ، فسيرى عادةً شيئًا مثل: Genacodicetagpre

ما يقلقني هو أنه في حالتين (2،3) يصبح المستودع فاسدًا دون أي تحذيرات ، وفي 3 حالات (1،7،8) ، يبدو كل شيء على ما يرام ، لكن محتوى المستودع مختلف عما تتوقعه. سيكون لدى الأشخاص الذين يقومون بالاستنساخ أو السحب محتوى مختلف عما لديك. الحالات 4،5،6 و 9 على ما يرام ، لأنها ستتوقف مع وجود خطأ. أفترض أنه سيكون من الأفضل إذا فشلت بخطأ على الأقل في جميع الحالات.

Answer 2

الجواب الأصلية (2012) (انظر shattered.io 2017 SHA1 الاصطدام أدناه)

أن القديم (2006) الجواب من لينوس قد تكون لا تزال ذات الصلة:

لا.إذا كان لديه نفس SHA1, هذا يعني أننا عندما تتلقى هدفا من الآخر ، وسوف لا الكتابة كائن لدينا بالفعل.

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

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

بحيث يكون لديك اثنين من حالات الاصطدام:

• على غير مقصود نوع, حيث كنت بطريقة أو بأخرى جدا جدا سيئ الحظ ، ملفين في نهاية المطاف وجود نفس SHA1.
  عند هذه النقطة, ما يحدث هو أنه عند ارتكاب هذا الملف (أو تفعل "git-update-index"لنقلها إلى المؤشر ، ولكن لم ترتكب حتى الآن) ، SHA1 من محتويات جديدة سيتم حسابها ، ولكن لأنه يطابق القديم الكائن كائن جديد لن يكون خلق و ارتكاب أو مؤشر ينتهي لافتا إلى القديمة وجوه.
  أنك لن تلاحظ على الفور (منذ مؤشر مباراة القديم الكائن SHA1 و هذا يعني شيء من هذا القبيل "git diff"سوف تستخدم فحص-نسخة), ولكن إذا كنت من أي وقت مضى القيام به شجرة مستوى مهرجان دبي السينمائي الدولي (أو استنساخ أو سحب أو القوة الخروج) عليك فجأة لاحظ أن هذا الملف قد تغير إلى شيء تماما مختلفة عن ما هو متوقع.
  لذلك كنت عموما لاحظت هذا النوع من الاصطدام بسرعة إلى حد ما.
  وفي أنباء ذات صلة ، فإن السؤال هو ماذا عن تصادم غير مقصود..
  أولا اسمحوا لي أن أذكر الناس أنه غير مقصود نوع من التصادم هو حقا حقا حقا لعنة المرجح ، لذلك سوف من المحتمل جدا لا ترى أي وقت مضى في تاريخ الكون.
  ولكن إذا يحدث ذلك, انها ليست نهاية العالم: ما كنت على الأرجح إلى القيام به هو مجرد تغيير الملف الذي اصطدمت قليلا فقط قوة جديدة ارتكاب مع تغيير محتويات (إضافة تعليق يقول "/* This line added to avoid collision */") ثم بوابة تعليم عن السحر SHA1 التي ثبت أن تكون خطرة.
  حتى خلال بضعة ملايين من السنين, ربما علينا أن إضافة واحد أو اثنين من "تسمم" SHA1 القيم إلى بوابة.انه من غير المحتمل جدا أن تكون مشكلة صيانة ;)

• على المهاجم نوع من التصادم لأن أحدهم كسر (أو الغاشمة القسري) SHA1.
  هذا هو الواضح الكثير أكثر عرضة من غير قصد النوع ، ولكن بحكم التعريف هو دائما "عن بعد" مستودع.إذا كان المهاجم من الوصول إلى مستودع لكان أسهل طرق المسمار لك.
  حتى في هذه الحالة ، التصادم هو تماما مسألة غير:سوف تحصل على "سيئة" مستودع مختلف عن ما المهاجم المقصود ، ولكن منذ كنت لن تستخدم في الواقع له الاصطدام كائن انها حرفيا لا يختلف عن المهاجم ليس فقط بعد أن تبين اصطدام على الإطلاق, ولكن فقط باستخدام كائن كان لديك بالفعل (أي انها 100% ما يعادل "تافهة" اصطدام متطابقة ملف توليد نفس SHA1).

على مسألة استخدام SHA-256 بانتظام المذكورة ، ولكن لا تعمل عليها الآن (2012).
ملاحظة: ابتداء من عام 2018 و بوابة 2.19, مدونة يجري ريفاكتوريد استخدام SHA-256.

---

ملاحظة (الفكاهة):يمكنك فرض الالتزام معين SHA1 بادئة, مع المشروع gitbrute من براد فيتزباتريك (bradfitz).

gitbrute الغاشمة القوات زوج من المؤلف+committer الطوابع مثل أن الناتج بوابة ارتكاب لديه المطلوب البادئة.

على سبيل المثال: https://github.com/bradfitz/deadbeef

---

دانيال Dinnyes يشير في التعليقات إلى 7.1 أدوات بوابة - مراجعة اختيار, والتي تشمل:

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

---

حتى في الآونة الأخيرة (فبراير 2017) shattered.io أثبتت إمكانية تزوير SHA1 الاصطدام:
(انظر من ذلك بكثير في بلدي الإجابة المنفصلة, ، بما في ذلك لينوس تورفالدس'+ Google)

• أ/ لا يزال يتطلب أكثر من 9,223,372,036,854,775,808 SHA1 الحسابية.هذا أخذ ما يعادل قوة المعالجة من 6500 سنة واحدة وحدة المعالجة المركزية الحسابية و 110 سنوات من واحد GPU الحسابية.
• ب/ أن إقامة واحد الملف (مع نفس SHA1) ولكن مع إضافة القيد محتواه و حجم إنتاج متطابقة SHA1 (تصادم على محتوى وحده لا يكفي):انظر "كيف هو بوابة تجزئة حسابها ؟ "):a النقطة SHA1 يتم حسابها على أساس المحتوى و حجم.

انظر "عمر من الوظائف تجزئة التشفير"من فاليري أنيتا أورورا لمزيد من.
في هذه الصفحة أنها تلاحظ:

جوجل تنفق 6500 وحدة المعالجة المركزية سنوات و 110 GPU سنوات لإقناع الجميع نحن بحاجة إلى التوقف عن استخدام SHA-1 الأمن التطبيقات الهامة.
أيضا لأنه كان بارد

انظر المزيد في بلدي الإجابة المنفصلة أدناه.

Answer 3

وفقا ل Pro Git :

إذا حدثت في ارتكاب كائن يمتص بنفس قيمة SHA-1 ككائن سابق في مستودعك، سترى GIT الكائن السابق بالفعل في قاعدة بيانات GIT الخاصة بك وافترض أنه مكتوب بالفعل. إذا حاولت التحقق من هذا الكائن مرة أخرى في مرحلة ما، فستحصل دائما على بيانات الكائن الأول.

لذلك لن تفشل، ولكن لن ينقذ كائنك الجديد أيضا.
لا أعرف كيف ستبحث عن سطر الأوامر، لكن هذا بالتأكيد سيكون مربكا.

أكثر قليلا من أسفل، فإن نفس المحاولات المرجعية لتوضيح NESS المحتمل لهذا التصادم:

إليك مثال تعطيك فكرة عما سيأخذه للحصول على تصادم شا - 1. إذا كانت كل 6.5 مليار البشر على الأرض كانت برمجة، وكل ثانية، فإن كل واحد، كان كل واحد، كان يعادل تاريخ نواة لينكس بأكمله (1 مليون كائنات جيت) ودفعه إلى مستودع جيت هائل، وسوف يستغرق 5 سنوات حتى يحتوي هذا المستودع على كائنات كافية للحصول على احتمال 50٪ من تصادم كائن SHA-1 واحد. يوجد احتمال أعلى من أن كل عضو في فريق البرمجة الخاص بك ستهاجم وقتله الذئاب في حوادث غير ذات صلة في نفس الليلة.

Answer 4

إضافة إلى إجابتي السابقة من عام 2012, هناك الآن (Feb.2017, بعد خمس سنوات) ، مثال الفعلية SHA-1 تصادم مع المحطمة.io, حيث يمكن صياغة اثنين من الاصطدام ملفات PDF:هذا هو الحصول على SHA-1 التوقيع الرقمي على أول ملف PDF التي يمكن أيضا أن يساء استخدامها صالح التوقيع على الثاني ملف PDF.
انظر أيضا "في باب الموت لسنوات ، تستخدم على نطاق واسع SHA1 وظيفة هو الآن ميت"، هذا التوضيح.

تحديث 26 من شباط / فبراير:لينوس أكد النقاط التالية في+ Google:

(1) أولا - السماء لا يسقط.هناك فرق كبير بين استخدام تجزئة التشفير لأشياء مثل الأمن توقيع باستخدام واحدة لتوليد المحتوى "معرف" عن محتوى تم تركيب نظام مثل git.

(2) ثانيا: طبيعة SHA1 الهجوم يعني أنه في الواقع من السهل جدا أن التخفيف ، هناك مجموعتين من بقع نشر هذا التخفيف.

(3) وأخيرا, في الواقع هناك صريح المعقول الانتقال إلى تجزئة التي لن كسر مستوى العالم أو حتى القديمة مخازن git.

بخصوص هذا الانتقال ، انظر Q1 2018 بوابة 2.16 إضافة هيكل يمثل خوارزمية التجزئة.تنفيذ هذا التحول قد بدأ.

بدءا من بوابة 2.19 (Q3 2018), جيت اختار SHA-256 كما NewHash, و هو في عملية دمج إلى رمز (معنى SHA1 لا يزال الافتراضي (Q2 2019, بوابة 2.21) ، ولكن SHA2 سوف يكون خليفة)

---

الجواب الأصلية (25 فبراير) ولكن:

• هذا يسمح لتشكيل فقاعة, ومع ذلك SHA-1 من شجرة لا يزال يتغير منذ حجم مزورة النقطة قد لا تكون نفس الأصلي:انظر "كيف هو بوابة تجزئة حسابها ؟ ";a النقطة SHA1 يتم حسابها على أساس المحتوى والحجم.
  فإنه لا يكون بعض المسألة git-svn على الرغم من.أو بالأحرى مع svn نفسها, ، ينظر هنا.
• كما ذكرت في بلدي الأصلي الإجابة, تكلفة مثل هذه المحاولة لا تزال باهظة الآن (من 6500 وحدة المعالجة المركزية سنوات و 100 GPU سنوات) انظر أيضا فاليري أنيتا أورورا في "عمر من الوظائف تجزئة التشفير".
• كما علق قبل ، لا حول الأمن أو الثقة ، ولكن سلامة البيانات (دي-الازدواجية اكتشاف الخطأ) التي يمكن الكشف عنها بسهولة من قبل git fsck, ، ذكرت من قبل لينوس تورفالدس اليوم. git fsck تحذير عن ارتكاب رسالة مع بيانات مبهمة خفية بعد NUL (على الرغم من أن NUL ليست دائما موجودة في الاحتيالية الملف).
  الجميع لا يتحول transfer.fsck, لكن جيثب لا:أي دفع سيكون من شأنها إحباط في حالة تالف كائن أو وصلة مكسورة.على الرغم من أن...هناك السبب في هذا هو عدم تفعيلها بشكل افتراضي.
• ملف pdf يمكن أن يكون تعسفيا البيانات الثنائية التي يمكنك تغيير لتوليد الاصطدام SHA-1, بدلا كما مزورة شفرة المصدر.
  المشكلة الفعلية في إنشاء اثنين من مخازن Git مع نفس رئيس ارتكاب تجزئة محتويات مختلفة.وحتى ذلك الحين ، الهجوم لا تزال معقدة.
• لينوس يضيف:

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

جوي هيس يحاول هؤلاء pdf في Git الريبو و وجد:

الذي يضم اثنين من الملفات مع نفس شا الحجم التي لا تحصل مختلف النقط بفضل الطريقة بوابة بإلحاق الأحرف الأولى إلى رأس محتوى.

joey@darkstar:~/tmp/supercollider>sha1sum  bad.pdf good.pdf 
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  bad.pdf
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  good.pdf
joey@darkstar:~/tmp/supercollider>git ls-tree HEAD
100644 blob ca44e9913faf08d625346205e228e2265dd12b65    bad.pdf
100644 blob 5f90b67523865ad5b1391cb4a1c010d541c816c1    good.pdf

بينما إلحاق بيانات متطابقة إلى هذه الاصطدام الملفات لا تولد غيرها من الاصطدامات ، يتبع البيانات لا.

لذلك الرئيسية ناقلات الهجوم (تزوير لارتكاب) سيكون:

• توليد العادية ارتكاب الكائن ؛
• استخدام كامل ارتكاب كائن + NUL المختار البادئة ،
• استخدام متطابقة-بادئة الاصطدام الهجوم لتوليد الاصطدام جيدة/سيئة الكائنات.
• ...و هذا لا طائل منه لأن الخير والشر ارتكاب الكائنات لا تزال تشير إلى نفس الشجرة!

بالإضافة إلى أنك بالفعل يمكن الكشف عن cryptanalytic الاصطدام الهجمات ضد SHA-1 الموجودة في كل ملف cr-marcstevens/sha1collisiondetection

مضيفا مماثل تحقق في بوابة نفسها بعض حساب التكلفة.

على تغيير التجزئة ، لينكس تعليقات:

حجم تجزئة اختيار خوارزمية التجزئة مستقلة القضايا.
ما كنت ربما القيام به هو التبديل إلى 256 بت تجزئة استخدام هذا داخليا في الأم بوابة قاعدة البيانات ثم افتراضيا فقط تظهر التجزئة باعتباره 40 حرف hex string (مثل ما نحن بالفعل اختصار الأشياء في كثير من الحالات).
بهذه الطريقة الأدوات حول جيت حتى لا نرى التغيير إلا إذا مرت في خاصة "--full-hash"الحجة (أو "--abbrev=64"أو أيا كان - كونها الافتراضي أننا اختصار إلى 40).

لا يزال ، الخطة الانتقالية (من SHA1 إلى آخر وظيفة تجزئة) سوف لا يزال تكون معقدة, لكن درس بنشاط.
A convert-to-object_id الحملة هو في التقدم:

---

تحديث 20 مارس: جيثب تفاصيل هجوم محتمل وحمايتها:

SHA-1 يمكن تعيين أسماء الثقة من خلال آليات مختلفة.على سبيل المثال, بوابة يسمح لك مشفر التوقيع على ارتكاب أو العلامة.ذلك علامات فقط في ارتكاب أو الوسم هدف في حد ذاته ، والذي يشير بدوره إلى الكائنات الأخرى التي تحتوي على الملف الفعلي البيانات باستخدام SHA-1 أسماء.تصادم في هذه الكائنات يمكن أن تنتج التوقيع الذي يظهر صالحة ، ولكن الذي يشير إلى بيانات مختلفة من الموقع المقصود.في مثل هذا الهجوم الموقع لا يرى إلا نصف واحد من الاصطدام ، والضحية يرى النصف الآخر.

الحماية:

الهجوم الأخير يستخدم تقنيات خاصة إلى استغلال نقاط الضعف في SHA-1 الخوارزمية التي تجد تصادم في وقت أقل بكثير.هذه التقنيات ترك نمط في وحدات البايت التي يمكن الكشف عنها عندما الحوسبة SHA-1 إما نصف الاصطدام الزوج.

GitHub.com الآن ينفذ هذا الكشف لكل SHA-1 يحسب و إحباط العملية إذا كان هناك دليل على أن الكائن هو نصف الاصطدام الزوج.يمنع المهاجمين من استخدام جيثب لإقناع المشروع إلى قبول "الأبرياء" نصف الاصطدام ، وكذلك منعهم من استضافة الخبيثة النصف.

انظر "sha1collisiondetection"من قبل مارك ستيفنز

---

مرة أخرى ، Q1 2018 بوابة 2.16 إضافة هيكل يمثل خوارزمية التجزئة ، وتنفيذ الانتقال إلى تجزئة جديدة قد بدأت.
كما ذكر أعلاه, جديدة تدعم تجزئة سوف يكون SHA-256.

Answer 5

أعتقد أن مصممي التشفير سيحتفلون.

اقتباس من مقالة Wikipedia عن SHA-1 :

في فبراير 2005 ، تم الإعلان عن هجوم شنه Xiaoyun Wang و Yiqun Lisa Yin و Hongbo Yu. يمكن للهجمات العثور على تصادمات في الإصدار الكامل من SHA-1 ، والتي تتطلب أقل من 2 ^ 69 عملية.(قد يتطلب البحث باستخدام القوة الغاشمة 2 ^ 80 عملية.)

Answer 6

هناك العديد من نماذج الهجوم المختلفة للتجزئة مثل SHA-1 ، ولكن النموذج الذي تتم مناقشته عادةً هو بحث التصادم ، بما في ذلك Marc Stevens ' أداة HashClash .

"اعتبارًا من 2012 ، يعتبر الهجوم الأكثر فاعلية ضد SHA-1 أن يكون من تأليف مارك ستيفنز [34] بتكلفة تقديرية تبلغ 2.77 مليون دولار كسر قيمة تجزئة واحدة عن طريق استئجار طاقة وحدة المعالجة المركزية من الخوادم السحابية. "

كما أوضح الأشخاص ، يمكنك إجبار تضارب علامة التجزئة مع git ، ولكن القيام بذلك لن يؤدي إلى استبدال الكائنات الموجودة في مستودع آخر. أتخيل أنه حتى الكود العام لن يقوم بالكتابة فوق الكائنات الموجودة ، ولكن ليس متأكدًا بنسبة 100٪.

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

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