يوضح المقال كيفية إنشاء قنبلة zip غير متكررة توفر درجة عالية من الضغط عن طريق تداخل الملفات داخل حاوية zip. "غير تكراري" يعني أنه لا يعتمد على برامج إلغاء الضغط التي تقوم بفك ضغط الملفات المرفقة بأرشيفات zip: هناك جولة واحدة فقط. يزداد حجم المخرجات من المدخلات ، حيث يصل معدل الضغط إلى أكثر من 28 مليون (10 ميغابايت → 281 تيرابايت) ضمن تنسيق zip. مزيد من التوسع ممكن مع ملحقات 64 بت. يستخدم التصميم فقط خوارزمية ضغط DEFLATE الأكثر شيوعًا ومتوافق مع معظم موزعي الرمز البريدي.

• zbsm.zip 42 كيلو بايت → 5.5 جيجابايت
  
• zblg.zip 10 ميغابايت → 281 تيرابايت
  
• zbxl.zip 46 ميجابايت → 4.5 PB (Zip64 ، أقل توافقًا مع المحللون)

كود المصدر:

  git clone https://www.bamsoftware.com/git/zipbomb.git 

zipbomb-20190702.zip

البيانات ومصدر الرسوم التوضيحية:

  git clone https://www.bamsoftware.com/git/zipbomb-paper.git 

<sub>* هناك إصداران من 42.zip: 42 424 بايت القديمة ، وأحدث 42 428 بايت. الفرق هو أن الجديد يتطلب كلمة مرور قبل التفريغ. قارنا فقط مع الإصدار القديم. هذه نسخة من الملف إذا كنت في حاجة إليها: 42.zip .

** أود أن أعرف مؤلف كتاب 42.zip وأشير إليه ، لكن لم أتمكن من العثور عليه - أخبرني إذا كان لديك أي معلومات.</sub>

يجب أن تتغلب القنابل المضغوطة على حقيقة مفادها أن خوارزمية ضغط DEFLATE المدعومة غالبًا من قبل المحللون لا يمكن أن تتجاوز نسبة الضغط من 1032 إلى 1. لهذا السبب ، عادة ما تعتمد القنابل المضغوطة على إلغاء الضغط المتكرر عن طريق إدراج ملفات مضغوطة في ملفات مضغوطة للحصول على نسبة إضافية 1032 مع كل طبقة. لكن الحيلة لا تعمل إلا في التطبيقات التي تعمل على إلغاء الضغط بشكل متكرر ، ومعظمها لا يعمل. تتوسع القنبلة 42.zip الأكثر شهرة إلى 4.5 PB هائلة إذا كانت جميع الطبقات الست قد تم تفريغها بشكل متكرر ، ولكن في الطبقة العليا كان بها 0.6 ميغابايت. الرمز البريدي ، مثل تلك الموجودة في Cox و Ellingsen ، تعطي نسخة عن نفسها ، وبالتالي ، تتوسع إلى أجل غير مسمى عند التفريغ المتكرر. لكنها أيضًا آمنة تمامًا عند التفريغ مرة واحدة.

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

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

الرمز البريدي هيكل الملف

يتكون ملف zip من دليل مركزي لروابط الملفات.



الدليل المركزي هو في نهاية ملف مضغوط. هذه قائمة برؤوس الدليل المركزي . يحتوي كل رأس دليل مركزي على بيانات أولية لملف واحد ، مثل اسم الملف واختبار CRC-32 ، بالإضافة إلى مؤشر يعود إلى رأس الملف المحلي. رأس الدليل المركزي بطول 46 بايت بالإضافة إلى طول اسم الملف.

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

يحذف هذا الوصف للتنسيق zip العديد من التفاصيل غير الضرورية لفهم القنبلة zip. للحصول على معلومات كاملة ، راجع القسم 4.3 APPNOTE.TXT أو بنية ملف PKZip بواسطة Florian Buchholz ، أو راجع التعليمات البرمجية المصدر .

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

• "عشرة آلاف مصيدة أمان: تنسيق ZIP" (بالإنجليزية) ، بقلم جينويل كولدويند
  
• يتيح لك تحليل الرمز البريدي الغامض إخفاء ملفات الوظيفة الإضافية لمتصفح فايرفوكس من linter والأشخاص : نقاط الضعف الخاصة بي في addons.mozilla.org

الاكتشاف الأول: تداخل الملفات

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



النظر في مثال على كيفية تأثير هذا التصميم على نسبة الضغط. افترض أنه تم تفريغ حزمة أساسية 1000 بايت في 1 ميغابايت. ثم "ميغا بايت" الإخراج الأولى "يكلف" 1078 بايت من بيانات الإدخال:

• 31 بايت لرأس الملف المحلي (بما في ذلك اسم ملف بايت واحد)
  
• 47 بايت لرأس الدليل المركزي (بما في ذلك اسم ملف 1 بايت)
  
• 1000 بايت لكل الأساسية

لكن كل 1 ميغابايت من الإخراج بعد الأول يكلف 47 بايت فقط - لا نحتاج إلى رأس آخر للملف المحلي أو نسخة أخرى من kernel ، فقط رأس إضافي للدليل المركزي. وهكذا ، في حين أن الرابط الأول من القلب يحتوي على نسبة ضغط تبلغ 1،000،000 / 1،078 ≈ 928 ، فإن كل رابط إضافي يحرك المعامل أقرب من 1،000،000 / 47 ≈ 21،277 ، بينما يرفع النواة الكبيرة السقف.

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

  $ unzip overlap.zip
   تضخيم: أ
 B: عدم تطابق اسم الملف "المحلي" (A) ،
          متابعة إصدار ملف "المركزية"
   تضخيم: ب
 ... 

بايثون zipfile يلقي أيضا استثناء :

  $ python3 -m zipfile -e overlap.zip.
 تتبع (آخر مكالمة أخيرة):
 ...
 __main __. BadZipFile: يختلف اسم الملف في الدليل 'B' والرأس b'A '. 

بعد ذلك ، سننظر في كيفية إعادة تصميم تناسق اسم الملف ، مع الحفاظ على معظم فوائد الملفات المتداخلة.

الاكتشاف الثاني: نقلا عن رؤوس الملفات المحلية

نحتاج إلى فصل رؤوس الملفات المحلية لكل ملف ، مع إعادة استخدام نواة واحدة. لا يعمل ببساطة الجمع بين جميع الرؤوس ، لأن المحلل اللغوي zip سيجد رأس الملف المحلي حيث يتوقع بدء دفق DEFLATE. لكن الفكرة ستنجح ، مع تغييرات طفيفة. سوف نستخدم وظيفة DEFLATE للكتل غير المضغوطة "اقتباس" لرؤوس الملفات المحلية بحيث تظهر كجزء من نفس دفق DEFLATE الذي ينتهي في النواة. سيتم تفسير كل رأس للملف المحلي (باستثناء الأول) بطريقتين: كرمز (جزء من بنية ملف مضغوط) وكبيانات (جزء من محتوى الملف).



دفق DEFLATE هو سلسلة من الكتل حيث يمكن ضغط كل كتلة أو ضغطها. عادة ما نفكر فقط في الكتل المضغوطة ، على سبيل المثال ، النواة عبارة عن كتلة كبيرة مضغوطة. ولكن هناك أيضًا تلك غير المضغوطة التي تبدأ برأس 5 بايت مع حقل طول ، وهو ما يعني ببساطة: "طباعة الحرف البايت n التالي." تفريغ كتلة غير مضغوطة يعني حذف رأس 5 بايت فقط. يمكن خلط الكتل المضغوطة وغير المضغوطة بحرية في دفق DEFLATE. الإخراج هو سلسلة من نتائج الضغط من جميع الكتل بالترتيب. مفهوم "غير مضغوط" يهم فقط على مستوى DEFLATE ؛ لا تزال بيانات الملف "مضغوطة" على مستوى الرمز البريدي ، بغض النظر عن الكتل المستخدمة.

أسهل طريقة لتخيل هذا التصميم هي تداخل داخلي ، من الملف الأخير إلى الأول. نبدأ بإدخال kernel الذي سيشكل نهاية ملف البيانات لكل ملف. أضف رأس ملف LFH _N المحلي ورأس دليل CDH _N المركزي الذي يشير إليه. اضبط حقل بيانات التعريف "بالحجم المضغوط" في LFH _N و CDH _N على حجم النواة المضغوطة. أضف الآن العنوان المكون من 5 بايتات للكتلة غير المضغوطة (باللون الأخضر على الرسم التخطيطي) ، حيث يساوي مجال الطول بالحجم LFH _N. أضف العنوان الثاني لملف LFH المحلي _{N − 1} وعنوان الدليل المركزي CDH _{N −1} ، والذي يشير إليه. عيّن حقل بيانات التعريف "بالحجم المضغوط" كرأس جديد لحجم النواة المضغوطة بالإضافة إلى حجم رأس الكتلة غير المضغوطة (5 بايت) بالإضافة إلى حجم LFH _N.

في الوقت الحالي ، يحتوي ملف zip على ملفين يحملان الاسمين Y و Z. دعنا نذهب إلى ما سيراه المحلل اللغوي عند التحليل. افترض أن حجم kernel المضغوط هو 1000 بايت وأن حجم LFH _N هو 31 بايت. نبدأ مع CDH _{N −1} ونتبع علامة LFH _{N −1} . اسم الملف الأول هو Y ، والحجم المضغوط لملف البيانات الخاص به هو 1036 بايت. ترجمة البايتات 1036 التالية على أنها دفق DEFLATE ، وصلنا أولاً إلى رأس مكون من 5 بايتات من كتلة غير مضغوطة تقول لنسخ البايتات الـ 31 التالية. نكتب الـ 31 بايت التالية ، وهي LFH _N ، التي نفرغها ونضيفها إلى الملف Y. مع التقدم في دفق DEFLATE ، نجد الكتلة المضغوطة (kernel) التي نفرغها في الملف Y. لقد وصلنا الآن إلى نهاية البيانات المضغوطة وانتهينا من ملف Y.

بالانتقال إلى الملف التالي ، نتبع المؤشر من CDH _N إلى LFH _N ونجد ملفًا اسمه Z بحجم مضغوط يبلغ 1000 بايت. عند تفسير هذه البايتات 1000 على أنها دفق DEFLATE ، نواجه على الفور كتلة مضغوطة (نواة مرة أخرى) ونفككها في ملف Z. لقد وصلنا الآن إلى نهاية الملف النهائي وانتهينا. يحتوي ملف الإخراج Z على kernel unpacked؛ ملف الإخراج Y هو نفسه ، ولكن اختيارياً مع بادئة 31 بايت LFH _N.

نكمل الإنشاء من خلال تكرار إجراء الاقتباس حتى يتضمن أرشيف الرمز البريدي العدد المطلوب من الملفات. يضيف كل ملف جديد رأس دليل مركزي ، ورأس ملف محلي ، وكتلة غير مضغوطة للاقتباس مباشرة من رأس الملف المحلي التالي. عادةً ما تكون بيانات الملفات المضغوطة سلسلة من كتل DEFLATE غير المضغوطة (رؤوس الملفات المحلية المقتبسة) متبوعة بنواة مضغوطة. تساهم كل بايت في kernel بحوالي 1032 N في حجم الإخراج ، لأن كل بايت جزء من جميع ملفات N. تكون ملفات الإخراج أيضًا بأحجام مختلفة: الأقدم منها أكبر من الأحدث لأنها تستشهد برؤوس الملفات المحلية أكثر. محتويات ملفات الإخراج لا معنى لها ، لكن لا أحد قال إنه ينبغي أن يكون له معنى.

يحتوي تصميم الاستشهاد المتداخل على توافق أفضل من تصميم التداخل الكامل من القسم السابق ، ولكن يتم تحقيق التوافق من خلال الضغط. هناك ، يكلف كل ملف مضاف فقط عنوان الدليل المركزي ، وهنا يكلف عنوان الدليل المركزي ، ورأس الملف المحلي وخمس بايتات أخرى لرأس الاستشهاد.

الأمثل

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

• ما هي أقصى نسبة ضغط لحجم ملف مضغوط معين؟
  
• ما هو الحد الأقصى لنسبة الضغط بالنظر إلى قيود تنسيق الرمز البريدي؟

ضغط النواة

من المفيد لنا أن نضغط النواة قدر الإمكان ، لأن كل بايت مفرغ يتم ضربه بـ N. لهذا الغرض ، نستخدم ضاغط DEFLATE مخصص يسمى bulk_deflate ، متخصص في ضغط سلسلة من البايتات المتكررة.

تقترب جميع أرشيفات DEFLATE اللائقة من نسبة الضغط البالغة 1032 على دفق لا نهاية له من وحدات البايت المتكررة ، لكننا نشعر بالقلق إزاء الحجم المحدد. في حجم الأرشيف لدينا ، يحتفظ bulk_deflate ببيانات أكثر من أرشيفات الأغراض العامة: حوالي 26 كيلوبايت أكثر من zlib و Info-ZIP ، وحوالي 15 كيلوبايت أكثر من Zopfli ، الذي يضحّي بالسرعة من أجل جودة الضغط.



سعر نسبة ضغط عالية bulk_deflate - عدم وجود تنوع. يمكنه ضغط أسطر وحدات البايت المكررة وطول معين فقط ، أي 517 + 258 ك للحصول على عدد صحيح k ≥ 0. بالإضافة إلى الضغط الجيد ، يعمل الجزء الأكبر بسرعة كبيرة ، ويعمل في نفس الوقت تقريبًا بغض النظر عن حجم بيانات الإدخال ، عد العمل في الواقع كتابة سلسلة مضغوط.

أسماء الملفات

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

تعني كل بايت يتم إنفاقه على اسم الملف وحدتي بايت لا يتم إنفاقهما على kernel (اثنين لأن كل اسم ملف يظهر مرتين: في رأس الدليل المركزي وفي رأس الملف المحلي). ينتج عن بايت اسم الملف في المتوسط ​​فقط ( N + 1) / 4 بايت من الإخراج ، في حين أن بايت في النواة يبلغ 1032 نون. أمثلة: 1 ، 2 ، 3 .

أول توافق التوافق هو الترميز. تنص مواصفات تنسيق zip على ضرورة تفسير أسماء الملفات على أنها CP 437 أو UTF-8 إذا تم تعيين بت إشارة محددة ( APPNOTE.TXT ، الملحق D ). هذه هي النقطة الرئيسية لعدم التوافق بين موزعي الرمز البريدي ، والتي يمكن أن تفسر أسماء الملفات في بعض الترميز الثابت أو الخاص بالإعدادات المحلية. لذلك ، من أجل التوافق ، من الأفضل أن تقصر نفسك على الأحرف بنفس الترميز في كل من CP 437 و UTF-8. وهي ، 95 حرفًا من أحرف US-ASCII قابلة للطباعة.

نحن ملزمون أيضًا بقيود تسمية نظام الملفات. بعض أنظمة الملفات غير حساسة لحالة الأحرف ، لذلك لا تعتبر "أ" و "أ" أسماء مختلفة. تحظر أنظمة الملفات الشائعة ، مثل FAT32 ، أحرفًا معينة ، مثل "*" و "؟".

كحل وسط آمن ، ولكن ليس بالضرورة الأمثل ، ستستخدم قنبلة الرمز البريدي الخاصة بنا أسماء الملفات من الأبجدية المكونة من 36 حرفًا ، والتي لا تتضمن أحرفًا خاصةً وشخصيات مختلفة الحالة:

  0 1 2 3 4 5 6 7 8 9 ABCDEFGHIJKLMNOPQRSTU VWXYZ 

يتم إنشاء أسماء الملفات بطريقة واضحة ، وجميع المواضع بدورها ، مع إضافة موضع في نهاية الحلقة:

  "0" ، "1" ، "2" ، ... ، "Z" ،
 "00" ، "01" ، "02" ، ... ، "0Z" ،
 ...،
 "Z0" ، "Z1" ، "Z2" ، ... ، "ZZ" ،
 "000" ، "001" ، "002" ، ... 

هناك 36 اسمًا للملف من حرف واحد ، وأسماء ذات حرفين 36 مترًا وما إلى ذلك. البايتات الأربعة كافية لأسماء الملفات المختلفة 1727604.

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

حجم الأساسية

يتيح لك التصميم المتداخل للاقتباس وضع نواة بيانات مضغوطة ، ثم نسخها عدة مرات بثمن بخس. بالنسبة لحجم محدد لملف zip X ، ما المساحة التي يمكن تخصيصها لتخزين النواة ، وكم مساحة النسخ؟

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

تطبيق إجراء التحسين على X = 42،374 لـ 42.zip يعثر على الحد الأقصى عند N = 250. تتطلب هذه الملفات 250 21،195 بايت من الحمل ، وترك 21،179 بايت للنواة. يتم تفريغ نواة بهذا الحجم إلى 21،841،249 بايت (نسبة 1031.3 إلى 1). 250 نسخة من النواة التي تم فك حزمتها بالإضافة إلى عدد قليل من رؤوس الملفات المحلية التي تم الاستشهاد بها تعطي ناتجًا إجماليًا غير محزوم يبلغ 5،461،307،620 بايت ونسبة ضغط تبلغ 129،000.

• zbsm.zip 42 كيلو بايت → 5.5 جيجابايت

  zipbomb --mode = ونقلت_overlap - عدد الملفات = 250 - مضغوط الحجم = 21179> zbsm.zip 

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

تعريف بعض الثوابت والمتغيرات:


دع H (N) هو حجم الحمل للرؤوس لملفات N. انظر الرسم البياني لفهم جوهر الصيغة.

$$

$$H (N) = N ⋅ (CDH + LFH) + (N - 1) ⋅ Q$$

بالنسبة للنواة ، تبقى أماكن X - H (N) . إجمالي الحجم الذي تم فك حزمه S _X (N) مساوٍ لحجم نسخ N من النواة التي تم فك حزمتها بنسبة C (في هذا النموذج المبسط ، نتجاهل الامتداد الإضافي الطفيف من رؤوس الملفات المحلية المذكورة).

$$عرض $$ $ S_X (N) = (X - H (N)) CN \\ = (X - (N ⋅ (CDH + LFH) + (N - 1) ⋅ Q)) CN \\ = - (CDH + LFH + Q) CN ^ 2 + (X + Q) CN $$ عرض $$

S _X (N) متعدد الحدود في الجزء N ، لذلك ، يجب أن يكون الحد الأقصى عندما يكون المشتق S ' _X (N) يساوي الصفر. أخذ المشتق والعثور على الصفر يعطينا N _OPT ، العدد الأمثل من الملفات.

$$عرض $$ $ S′X (N_ {OPT}) = −2 (CDH + LFH + Q) C N_ {OPT} + (X + Q) C \\ 0 = −2 (CDH + LFH + Q) C N_ {OPT} + (X + Q) C \\ N_ {OPT} = (X + Q) / (CDH + LFH + Q) / 2 $$ عرض $$

يعطي H (N _OPT ) مقدار المساحة الأمثل لوضع رؤوس الملفات. إنه مستقل عن CDH و LFH و C وهو قريب من X / 2 .

$$عرض $$ $$ H (N_ {OPT}) = N_ {OPT} ⋅ (CDH + LFH) + (N_ {OPT} - 1) \\ Q \\ = (X - Q) / 2 عرض $$ $$

S _X (N _OPT ) - إجمالي حجم التفريغ عند التوزيع الأمثل. من هذا نرى أن حجم المخرجات يزداد من الناحية التربيعية مع زيادة إدخال البيانات.

$$

$$S_X (N_ {OPT}) = (X + Q) ^ 2C / (CDH + LFH + Q) / 4$$

بزيادة حجم ملف zip ، في النهاية سنواجه حدود تنسيق zip: لا يمكن أن يحتوي الأرشيف على أكثر من 2 ¹⁶ −1 ملف بحجم لا يزيد عن 2 ^{32 −} 1 بايت لكل منهما. الأسوأ من ذلك ، تأخذ بعض التطبيقات الحد الأقصى للقيم كمؤشر على وجود امتدادات 64 بت ، لذلك فإن حدودنا هي في الواقع 2 ¹⁶ −2 و 2 ³² −2. يحدث أنه في المرة الأولى التي نواجه فيها حدًا لحجم ملف غير مضغوط. بحجم ملف مضغوط قدره 8319 377 بايت ، سيعطينا التحسين الساذج عدد الملفات 47 837 والحد الأقصى للملف 2 ³² +311 بايت.

(في الواقع ، كل شيء أكثر تعقيدًا بعض الشيء ، لأن الحدود الدقيقة تعتمد على التنفيذ. يتجاهل Python zipfile عدد الملفات ، يسمح الأرشيف / zip في Go بزيادة عدد الملفات حتى تتطابق مع 16 بت أقل. ولكن من أجل التوافق العام ، يجب علينا الالتزام الحدود الموضوعة).

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

تؤدي الخطة إلى أرشيف مضغوط يحتوي على 2 ¹⁶ 162 ملفًا ونواة ، والتي يتم فك حزمتها في 2 ³² −2 178 825 بايت. ستكون الملفات أكبر في بداية أرشيف zip - يتم فك ضغط الملف الأول والأكبر في 2 - ^{32 -} 56 بايت. هذا أقرب ما يمكن إلى استخدام معلمات الإخراج التقريبية لـ bulk_deflate - سيكلف ترميز 54 بايت النهائي أكثر من حجمها (يحتوي ملف zip ككل على نسبة ضغط تبلغ 28 مليونًا وسيحصل 54 بايت النهائي على 54 54 × 10 كحد أقصى) 2 ¹⁶ - 2)؟ 36 - 5 ملايين بايت ، وهذا يساعد فقط إذا كان يمكن ترميز 54 بايت في بايت واحد - ولم أتمكن من الرمز أقل من اثنين ، لذلك ، إذا لم تتمكن من تشفير 54 بايت في 1 بايت ، أنه يقلل فقط من نسبة الضغط). حجم الإخراج من هذه القنبلة البريدي هو 2813954562443434 بايت ، 99.97 ٪ من الحد الأقصى النظري (2 ³² - 1) × (2 ¹⁶ - 1). لا يمكن تحقيق أي تحسن كبير في نسبة الضغط إلا عن طريق تقليل حجم إشارة الدخل ، وليس عن طريق زيادة الإخراج.

• zblg.zip 10 ميغابايت → 281 تيرابايت

  zipbomb --mode = ونقلت_overlap - عدد الملفات = 65534 - الحجم غير المضغوط = 4292788525> zblg.zip 

كفاءة الحوسبة CRC-32

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

يمكن تصميم نموذج CRC-32 كجهاز دولة ، مع تحديث سجل حالة 32 بت لكل بت إدخال. عمليات التحديث الأساسية للبت 0 و 1 هي:

 uint32 crc32_update_0(uint32 state) { // Shift out the least significant bit. bit b = state & 1; state = state >> 1; // If the shifted-out bit was 1, XOR with the CRC-32 constant. if (b == 1) state = state ^ 0xedb88320; return state; } uint32 crc32_update_1(uint32 state) { // Do as for a 0 bit, then XOR with the CRC-32 constant. return crc32_update_0(state) ^ 0xedb88320; } 

إذا كنت تمثل سجل الحالة كمتجه ثنائي مكون من 32 عنصرًا crc32_update_0 والضرب ، فإن crc32_update_0 هو رسم خطي ؛ أي أنه يمكن تمثيله كضرب بمصفوفة انتقال ثنائية 32 × 32. لفهم السبب ، لاحظ أن ضرب مصفوفة بواسطة متجه يؤدي ببساطة إلى إضافة أعمدة المصفوفة بعد ضرب كل عمود بالعنصر المقابل من المتجه. state >> 1 عملية النقل state >> 1 ببساطة تأخذ كل بت من متجه الحالة وتضربها بواسطة متجه يساوي الصفر في كل مكان باستثناء بت 1 - (ترقيم البتات من اليمين إلى اليسار). وبشكل نسبي ، تحدث state ^ 0xedb88320 XOR النهائية state ^ 0xedb88320 فقط عندما تكون البتة b مساوية لواحدة. يمكن تمثيل هذا كـ الضرب الأول لـ b بواسطة 0xedb88320 ، ثم XORing لهذه الحالة.

أيضًا ، crc32_update_1 هو مجرد crc32_update_0 plus (XOR) ثابت. crc32_update_1 : (. ., ). , 33×33 , 1 ( ).


33×33 M ₀ M ₁ , CRC-32, 0 1, . : , CRC-32 edb8832016 = 111 0 11 0 11 0 111 000 1 00000 11 00 1 00000 ₂ . , . M ₀ , M ₁ — edb88320 ₁₆ , CRC-32. state >> 1

crc32_update_0 crc32_update_1 33×33. M ₀ M ₁ . , . , , ASCII- 'a', 01100001 ₂ . CRC-32 :

$$

$$M_a = M_0 M_1 M_1 M_0 M_0 M_0 M_0 M_1$$

'' — . , , M ⁿ log ₂ ⁿ . , 9 '':

$$

$$(M_a)^9 = M_a M_a M_a M_a M_a M_a M_a M_a M_a\\ = (M_a M_a M_a M_a)^2 M_a\\ = ((M_a M_a)^2)^2 M_a\\ = (((M_a)^2)^2)^2 M_a$$

M _kernel , , . CRC-32 , ( , 32 , ; - ). , . M := M _kernel . N , M CDH _N LFH _N . N−1 , N , LFH _N . $$$M_{L{FH_N}}$ , LFH _N $$$M := M M_{L{FH_N}}$ . M LFH _N . N−1 , M . , M , .

: Zip64

- zip — 281 , , zip-. , Zip64 , zip, 64 . Zip64 , . , Zip64 46 58 , 30 50 . , , zip- Zip64 - , - — . .

, zip-, 4,5 , 42.zip. ? , 46 .

• zbxl.zip 46 MB → 4,5 PB (Zip64, )

 zipbomb --mode=quoted_overlap --num-files=190023 --compressed-size=22982788 --zip64 > zbxl.zip 

4,5 — : -.

Zip64 , zip- , zip- . , , 2 ⁶⁴ (18 EB 16 EiB) — . zip-, : 12 1,5 . zip- 2,9 , 2 ⁶⁴ +11 727 895 877 6,2 . , , . , Info-ZIP UnZip 6.0.

 zipbomb --mode=quoted_overlap --num-files=12056313 --compressed-size=1482284040 --zip64 > zbxxl.zip 

: bzip2

DEFLATE zip, . , bzip2 . , DEFLATE. , bzip2 1,4 , .

bzip2 « » (run-length encoding), 51 . 900 . , 32 . 900 000 × 51 / 32 = 1 434 375.

, bzip2 ?

— . , bzip2 DEFLATE, . , — , , . , bzip2 DEFLATE .

bzip2, . , , zip- bzip2 , , .


zip-. . Zip64. , . bzip2 , bzip2 , DEFLATE. DEFLATE , 2:1. Zip64 , 281 . bzip2 (2 ³² −2 ),

:

DEFLATE , , bzip2. , , zip .

, ( APPNOTE.TXT, 4.3.7 ). , , uid/gid Unix. Zip64 . length-value; , , zip-, . , «» , . DEFLATE :

1. 4 , 5, .
   
2. , , zip.
   
3. bzip2.

, . , DEFLATE: , . zip-. 2 ¹⁶ −1 , 1808 ( 1170 Zip64), , , ( DEFLATE ( ) , DEFLATE ). : , 16- ( APPNOTE.TXT, 4.5.2 ), . , , . Zip- , , , - .

bzip2, c Zip64. , . Zip64 , (2 ³² −2 ); , . , 1809, . Zip64 1171 , , . DEFLATE, , . zbsm.zip 1,2%; zblg.zip 0,019%; zbxl.zip 0,0025%.

zip-. ( 47) .

zip- — , . zip-, , . zip- Nail , . «» , zip- . . , . , , sunzip , , .

, , , DEFLATE , . zip- : , , ( --template ). zip , , Java JAR, Android APK LibreOffice.

PDF zip. , , FlateDecode. , , PDF-. , : binaryhax0r , FlateDecode , PDF- .

zip- : . Info-ZIP UnZip, . , zip-. , zip- , , . « » , ( . « »). zip- , zip- . zip-, , .


zip-, , zip-. DEFLATE Zip64, , CRC 32- 16- .

شكر

, , , , USENIX WOOT 2019 . zip- LibreOffice.

USENIX WOOT 2019 . . zipbomb-woot19.zip .

, ? ? , .

LibreOffice 6.1.5.2

zblg.zip zblg.odt zblg.docx LibreOffice 4 , . , zip- DoS, . .

Mozilla addons-server 2019.06.06

zip- addons-server, addons.mozilla.org. , 110 . Zip- , , , .

UnZip 6.0

UnZip, zip-.

5 2019 : , UnZip CVE-2019-13232 . , / UnZip ( zip-) zip- . , , . — , , zip-. , , , ; , , , , . , . , , , . HTML: — , , .

Twitter @TVqQAAMAAAAEAAA : « McAfee ». , .

, VirusTotal zblg.zip ( 6 2019 ): AhnLab-V3, ClamAV, DrWeb, Endgame, F-Secure, GData, K7AntiVirus, K7GW, MaxSecure, McAfee, McAfee-GW-Edition, Panda, Qihoo-360, Sophos ML, VBA32. zbsm.zip ( 6 2019 ) , , : Baido, Bkav, ClamAV, CMC, DrWeb, Endgame, ESET-NOD32, F-Secure, GData, Kingsoft, McAfee-GW-Edition, NANO-Antivirus, Acronis. , zbxl.zip ( 6 2019 ). , Zip64? « ». , - , ASCII .

Facebook. : , , - . Facebook, . Facebook, .

, .