लेख से पता चलता है कि एक गैर - पुनरावर्ती ज़िप बम कैसे बनाया जाए जो ज़िप कंटेनर के अंदर फाइलों को ओवरलैप करके उच्च स्तर की संपीड़न प्रदान करता है। "गैर-पुनरावर्ती" का मतलब है कि यह ज़िप अभिलेखागार से जुड़ी फाइलों के डिकम्प्रेसरों पर निर्भर नहीं करता है: केवल एक दौर है। आउटपुट आकार इनपुट से चतुष्कोणीय बढ़ता है, ज़िप प्रारूप के भीतर 28 मिलियन (10 एमबी → 281 टीबी) से अधिक के संपीड़न अनुपात तक पहुंच जाता है। 64-बिट एक्सटेंशन के साथ आगे विस्तार संभव है। डिज़ाइन केवल सबसे आम प्रभावी संपीड़न एल्गोरिथ्म का उपयोग करता है और अधिकांश ज़िप पार्सर्स के साथ संगत है।

• zbsm.zip 42 kB → 5.5 GB
  
• zblg.zip 10 एमबी → 281 टीबी
  
• zbxl.zip 46 एमबी → 4.5 पीबी ( ज़िप 64, पार्सर्स के साथ कम संगत)

स्रोत कोड:

  git क्लोन https://www.bamsoftware.com/git/zipbomb.git 

zipbomb-20190702.zip

दृष्टांतों का डेटा और स्रोत:

  git क्लोन https://www.bamsoftware.com/git/zipbomb-paper.git 

<sub>* 42.zip के दो संस्करण हैं: पुराने 42 374 बाइट्स, और नए 42 428 बाइट्स। अंतर यह है कि नए को अनपैक करने से पहले पासवर्ड की आवश्यकता होती है। हम केवल पुराने संस्करण से तुलना करते हैं। यहां फ़ाइल की एक कॉपी है यदि आपको इसकी आवश्यकता है: 42.zip ।

** मैं 42.zip के लेखक को जानना और इंगित करना चाहूंगा, लेकिन यह नहीं मिल सका - यदि आपके पास कोई जानकारी है तो मुझे बताएं।</sub>

जिप बमों को इस तथ्य से उबरना होगा कि पार्सल द्वारा समर्थित अधिकतम संपीड़न एल्गोरिथ्म 1032 से 1 के संपीड़न अनुपात से अधिक नहीं हो सकता है। इस कारण से, ज़िप बम आमतौर पर एक अतिरिक्त अनुपात प्राप्त करने के लिए ज़िप फ़ाइलों में ज़िप फ़ाइलों को सम्मिलित करके पुनरावर्ती विसंपीड़न पर भरोसा करते हैं। प्रत्येक परत के साथ 1032। लेकिन चाल केवल कार्यान्वयन में काम करती है जो पुनरावर्ती रूप से डिकम्प्रेस होती है, और अधिकांश नहीं। सबसे प्रसिद्ध 42.zip बम एक दुर्जेय 4.5 पीबी तक फैलता है यदि सभी छह परतें पुनर्संरचित रूप से अनपैक की जाती हैं, लेकिन शीर्ष परत पर यह 0.6 एमबी से अधिक है। कॉक्स और एलिंगसेन की तरह जिप क्वीन खुद की एक प्रति जारी करती है और इस तरह से पुनर्नवीनीकरण किए जाने पर अनिश्चित काल तक विस्तार करती है। लेकिन वे एक बार अनपैक करते समय पूरी तरह से सुरक्षित भी होते हैं।

यह आलेख बताता है कि गैर-पुनरावर्ती ज़िप बम कैसे बनाया जाए, जिसका संपीड़न अनुपात 1032 की अधिकतम सीमा से अधिक है। यह कई प्रतियों के माध्यम से कई फ़ाइलों में अत्यधिक संकुचित डेटा के "कोर" को संदर्भित करने के लिए ज़िप कंटेनर के अंदर फाइलों को ओवरलैप करके काम करता है। ज़िप बम का आउटपुट आकार इनपुट आकार से चौगुना बढ़ता है; यानी, बम के आकार में वृद्धि के साथ संपीड़न अनुपात में सुधार होता है। डिज़ाइन ज़िप और सुविधाओं की सुविधाओं पर निर्भर करता है: इसे सीधे अन्य फ़ाइल स्वरूपों या संपीड़न एल्गोरिदम में स्थानांतरित नहीं किया जा सकता है। बम अधिकांश ज़िप पार्सर्स के साथ संगत है, "स्ट्रीमिंग" वाले को छोड़कर, जो ज़िप फ़ाइल की केंद्रीय निर्देशिका की जांच किए बिना एक पास में फ़ाइलों का विश्लेषण करते हैं। हम दो परस्पर विरोधी लक्ष्यों को संतुलित करने का प्रयास करते हैं:

• संपीड़न अनुपात बढ़ाएँ। हम संपीड़न अनुपात को ज़िप फ़ाइल के आकार से विभाजित संग्रह में सभी फाइलों के आकार के योग के रूप में परिभाषित करते हैं। यह फ़ाइल नाम या अन्य फ़ाइल सिस्टम मेटाडेटा में नहीं लेता है, लेकिन केवल सामग्री है।
  
• अनुकूलता बनाए रखें। ज़िप एक जटिल प्रारूप है, और पार्सर अलग-अलग होते हैं, खासकर सीमावर्ती स्थितियों और अतिरिक्त कार्यों में। ऐसी तकनीकों का उपयोग न करें जो केवल कुछ निश्चित पार्सर के साथ काम करती हैं। हम संगतता के एक निश्चित नुकसान के साथ जिप बम की दक्षता बढ़ाने के लिए कुछ तरीके नोट करेंगे।

ज़िप फ़ाइल संरचना

ज़िप फ़ाइल में फ़ाइल लिंक की एक केंद्रीय निर्देशिका होती है ।



केंद्रीय निर्देशिका ज़िप फ़ाइल के अंत में है। यह केंद्रीय निर्देशिका शीर्षलेखों की एक सूची है। प्रत्येक केंद्रीय निर्देशिका शीर्षलेख में एक फ़ाइल के लिए मेटाडेटा होता है, जैसे फ़ाइल नाम और सीआरसी -32 चेकसम, साथ ही साथ स्थानीय फ़ाइल हेडर के लिए एक सूचक वापस। केंद्रीय निर्देशिका शीर्षलेख में 46 बाइट्स की लंबाई और फ़ाइल नाम की लंबाई है।

फ़ाइल में स्थानीय फ़ाइल के शीर्षलेख होते हैं, जिसके बाद संपीड़ित फ़ाइल डेटा होता है। स्थानीय फ़ाइल हेडर की लंबाई 30 बाइट्स और फ़ाइल नाम की लंबाई है। इसमें केंद्रीय निर्देशिका के शीर्षलेख से मेटाडेटा की एक अतिरिक्त प्रतिलिपि होती है, साथ ही इसके पीछे संकुचित और असम्पीडित डेटा फ़ाइलों के आकार भी होते हैं। ज़िप एक कंटेनर प्रारूप है, एक संपीड़न एल्गोरिथ्म नहीं। प्रत्येक फ़ाइल का डेटा मेटाडेटा में निर्दिष्ट एल्गोरिथ्म का उपयोग करके संपीड़ित होता है - आमतौर पर DEFLATE ।

ज़िप प्रारूप का यह विवरण कई विवरणों को छोड़ देता है जिन्हें ज़िप बम को समझने की आवश्यकता नहीं है। पूरी जानकारी के लिए, फ्लोरिअन बुचोलज़ द्वारा खंड 4.3 APPNOTE.TXT या PKZip फ़ाइल संरचना देखें, या स्रोत कोड देखें ।

जिप प्रारूप में महत्वपूर्ण अतिरेक और बहुत सी अस्पष्टताएं विभिन्न प्रकार के शरारत के अवसर खोलती हैं। एक ज़िप बम हिमखंड का सिरा है। आगे पढ़ने के लिए लिंक:

• "दस हजार सुरक्षा जाल: एक ज़िप प्रारूप," Ginwael Coldwind द्वारा
  
• अस्पष्ट ज़िप पार्सिंग आपको लिंटर और लोगों से फ़ायरफ़ॉक्स ऐड-ऑन फ़ाइलों को छिपाने की अनुमति देता है : addons.mozilla.org पर मेरी भेद्यता

पहली खोज: अतिव्यापी फाइलें

बार-बार बाइट्स की एक लंबी स्ट्रिंग को संपीड़ित करके, हम अत्यधिक संपीड़ित डेटा का एक कोर बना सकते हैं। कर्नेल का संपीड़न अनुपात स्वयं 1032 की सीमित सीमा से अधिक नहीं हो सकता है, इसलिए हमें प्रत्येक फ़ाइल में इसकी एक अलग प्रतिलिपि बनाए बिना कर्नेल को कई फ़ाइलों में पुन: उपयोग करने का एक तरीका चाहिए। फ़ाइलों को ओवरलैप करके हम ऐसा कर सकते हैं: केंद्रीय निर्देशिका के कई हेडर एकल फ़ाइल को इंगित करते हैं, जिसका डेटा कोर है।



इस उदाहरण पर विचार करें कि यह डिज़ाइन संपीड़न अनुपात को कैसे प्रभावित करता है। मान लीजिए 1 एमबी में 1000 बाइट्स का एक कोर अनपैक किया गया है। फिर आउटपुट की पहली मेगाबाइट इनपुट डेटा की "लागत" 1078 बाइट्स:

• स्थानीय फ़ाइल हेडर के लिए 31 बाइट्स (1 बाइट फ़ाइल नाम सहित)
  
• केंद्रीय निर्देशिका शीर्ष लेख के लिए 47 बाइट्स (1-बाइट फ़ाइल नाम सहित)
  
• प्रति कोर 1000 बाइट्स

लेकिन प्रत्येक 1 एमबी आउटपुट के बाद पहली लागत केवल 47 बाइट्स की होती है - हमें स्थानीय फ़ाइल के किसी अन्य शीर्षलेख या कर्नेल की एक और प्रतिलिपि की आवश्यकता नहीं होती है, केवल केंद्रीय निर्देशिका का एक अतिरिक्त हेडर। इस प्रकार, जबकि कोर के पहले लिंक में 1,000,000 / 1,078, 928 का संपीड़न अनुपात है, प्रत्येक अतिरिक्त लिंक गुणांक को 1,000,000 / 47, 21,277 के करीब ले जाता है, और एक बड़ा कोर छत उठाता है।

इस विचार के साथ समस्या संगतता की कमी है। चूंकि केंद्रीय निर्देशिका के कई हेडर स्थानीय फ़ाइल के एक हेडर को इंगित करते हैं, मेटाडेटा (विशेष रूप से, फ़ाइल का नाम) प्रत्येक फ़ाइल के लिए समान नहीं हो सकता है। कुछ पार्सर्स इस पर शपथ लेते हैं । उदाहरण के लिए, Info-ZIP UnZip (Unix पर मानक unzip प्रोग्राम) फ़ाइलों को पुनर्प्राप्त करता है, लेकिन चेतावनियों के साथ:

  $ अनज़िप ओवरलैप। ज़िप
   फुलाते हुए: ए
 बी: बेमेल "स्थानीय" फ़ाइल नाम (ए),
          "केंद्रीय" फ़ाइल नाम संस्करण के साथ जारी है
   फुलाया: बी
 ... 

अजगर zipfile भी एक अपवाद फेंकता है :

  $ python3 -m zipfile -e ओवरलैप.ज़िप।
 ट्रेसबैक (सबसे हालिया कॉल अंतिम):
 ...
 __main __। BadZipFile: निर्देशिका 'B' में फ़ाइल नाम और हेडर b'A 'भिन्न हैं। 

अगला, हम ओवरलैपिंग फ़ाइलों के अधिकांश लाभों को संरक्षित करते हुए फ़ाइल नाम संगति के लिए नया स्वरूप बनाने के तरीके को देखेंगे।

दूसरी खोज: स्थानीय फ़ाइलों के शीर्षकों को उद्धृत करना

हमें एक-एक कोर का पुन: उपयोग करते हुए प्रत्येक फ़ाइल के लिए स्थानीय फ़ाइलों के हेडर को अलग करना होगा। बस सभी हेडर को संयोजित करने से काम नहीं चलता है, क्योंकि ज़िप पार्सर स्थानीय फ़ाइल के हेडर को ढूंढ लेगा, जहां यह डिफ्ल्ट स्ट्रीम की शुरुआत की उम्मीद करता है। लेकिन विचार मामूली बदलाव के साथ काम करेगा। हम स्थानीय फ़ाइलों के शीर्षकों को "उद्धरण" करने के लिए असम्पीडित ब्लॉक के DEFLATE फ़ंक्शन का उपयोग करेंगे ताकि वे उसी DEFLATE स्ट्रीम का हिस्सा बनें जो कर्नेल में समाप्त होता है। स्थानीय फ़ाइल के प्रत्येक हेडर (पहले को छोड़कर) को दो तरीकों से व्याख्या किया जाएगा: कोड के रूप में (ज़िप फ़ाइल की संरचना का हिस्सा) और डेटा के रूप में (फ़ाइल सामग्री का हिस्सा)।



DEFLATE स्ट्रीम ब्लॉक का एक अनुक्रम है जहां प्रत्येक ब्लॉक को संपीड़ित या असम्पीडित किया जा सकता है। हम आमतौर पर केवल संकुचित ब्लॉकों के बारे में सोचते हैं, उदाहरण के लिए, कर्नेल एक बड़ा संकुचित ब्लॉक है। लेकिन ऐसे असम्पीडित भी हैं जो 5-बाइट हेडर के साथ एक लंबाई क्षेत्र के साथ शुरू करते हैं, जिसका सीधा मतलब है: "अगले एन बाइट्स शब्दशः प्रिंट करें।" एक असम्पीडित ब्लॉक को अनपैक करने का मतलब केवल 5-बाइट हेडर को हटाना है। संकुचित और असम्पीडित ब्लॉक स्वतंत्र रूप से स्ट्रीम में मिश्रित हो सकते हैं। आउटपुट सभी ब्लॉकों को क्रम में अनपैक करने के परिणामों का एक संयोजन है। "असम्पीडित" की अवधारणा केवल DEFLATE स्तर पर मायने रखती है; फ़ाइल डेटा को अभी भी ज़िप स्तर पर "संकुचित" माना जाता है, इसकी परवाह किए बिना कि ब्लॉक का उपयोग किया जाता है।

इस डिजाइन की कल्पना करने का सबसे आसान तरीका एक आंतरिक ओवरलैप है, आखिरी फ़ाइल से पहली तक। हम एक कर्नेल डालकर शुरू करते हैं जो प्रत्येक फ़ाइल के लिए डेटा फ़ाइल के अंत का निर्माण करेगा। स्थानीय LFH _N फ़ाइल के शीर्ष लेख और केंद्रीय CDH _N निर्देशिका के शीर्ष लेख को इसमें जोड़ें। LFH _N और CDH _N में "संपीड़ित आकार" मेटाडेटा फ़ील्ड को संपीड़ित कोर आकार पर सेट करें। अब असम्पीडित ब्लॉक के 5-बाइट हेडर (आरेख पर हरे रंग में) को जोड़ें, जिसकी लंबाई फ़ील्ड के आकार LFH _{N के} बराबर है _। स्थानीय LFH फ़ाइल _N the1 के दूसरे शीर्षलेख और केंद्रीय निर्देशिका CDH _N to1 का शीर्षक जोड़ें, जो इसे इंगित करता है। "संपीड़ित आकार" मेटाडेटा फ़ील्ड को संपीड़ित कर्नेल आकार के लिए नए शीर्षक के रूप में सेट करें और असम्बद्ध ब्लॉक हेडर (5 बाइट्स) के आकार के साथ साथ LFH _N का आकार _।

फिलहाल, ज़िप फ़ाइल में Y और Z नाम वाली दो फाइलें हैं। पार्स करते समय पार्सर क्या देखेगा। मान लीजिए कि संकुचित कर्नेल आकार 1000 बाइट्स है और LFH _N आकार 31 बाइट्स है। हम CDH _N and1 से शुरू करते हैं और LFH _N .1 के लिए साइन इन करते हैं। पहली फ़ाइल का नाम Y है, और इसकी डेटा फ़ाइल का संकुचित आकार 1036 बाइट्स है। अगले 1036 बाइट्स को एक डिफ्लैट स्ट्रीम के रूप में व्याख्या करते हुए, हम पहले एक असम्बद्ध ब्लॉक के 5-बाइट हेडर में आते हैं जो अगले 31 बाइट्स को कॉपी करने के लिए कहता है। हम अगले 31 बाइट्स लिखते हैं, जो LFH _{N हैं} , जिसे हम अनपैक करते हैं और Y फाइल में जोड़ते हैं। DEFLATE स्ट्रीम में आगे बढ़ते हुए, हम कंप्रेस्ड ब्लॉक (कर्नेल) को खोजते हैं जिसे हम Y फाइल में अनपैक करते हैं। अब हम कंप्रेस्ड डेटा के अंत में पहुँच गए हैं और Y फाइल के साथ समाप्त हो गया है।

अगली फ़ाइल पर चलते हुए, हम CDH _N से LFH _N तक पॉइंटर का अनुसरण करते हैं और Z नाम वाली फ़ाइल को 1000 बाइट्स के संकुचित आकार के साथ पाते हैं। इन 1000 बाइट्स को एक डिफ्लैट स्ट्रीम के रूप में व्याख्या करते हुए, हम तुरंत एक संपीड़ित ब्लॉक (कोर फिर से) का सामना करते हैं और इसे एक Z फ़ाइल में अनपैक करते हैं। अब हम अंतिम फ़ाइल के अंत तक पहुँच चुके हैं और समाप्त हो गए हैं। आउटपुट फ़ाइल Z में अनपैक्ड कर्नेल होता है; आउटपुट फ़ाइल Y समान है, लेकिन वैकल्पिक रूप से 31 बाइट्स LFH _{N के} उपसर्ग के साथ है _।

हम उद्धरण प्रक्रिया को दोहराते हुए निर्माण को पूरा करते हैं जब तक कि ज़िप संग्रह में आवश्यक संख्या में फाइलें शामिल न हों। प्रत्येक नई फ़ाइल में एक केंद्रीय निर्देशिका हेडर, एक स्थानीय फ़ाइल हेडर, और अगले स्थानीय फ़ाइल हेडर से सीधे उद्धरण के लिए एक असम्पीडित ब्लॉक जोड़ता है। संपीड़ित फ़ाइल डेटा आमतौर पर एक संपीड़ित कोर के बाद असम्पीडित ब्लॉक (स्थानीय फ़ाइल हेडर उद्धृत) की एक श्रृंखला है। कर्नेल में प्रत्येक बाइट आउटपुट आकार में लगभग 1032 N का योगदान करता है, क्योंकि प्रत्येक बाइट सभी N फ़ाइलों का हिस्सा है। आउटपुट फाइलें भी विभिन्न आकारों की होती हैं: पहले वाले बाद वाले की तुलना में बड़े होते हैं क्योंकि वे स्थानीय फाइलों के हेडर को अधिक उद्धृत करते हैं। आउटपुट फ़ाइलों की सामग्री बहुत मायने नहीं रखती है, लेकिन किसी ने भी यह नहीं कहा कि इसका अर्थ होना चाहिए।

इस ओवरलैप उद्धरण डिजाइन में पिछले अनुभाग से पूर्ण ओवरलैप डिजाइन की तुलना में बेहतर संगतता है, लेकिन संगतता संपीड़न के माध्यम से प्राप्त की जाती है। वहां, प्रत्येक जोड़ी गई फ़ाइल में केवल केंद्रीय निर्देशिका के शीर्षक की लागत होती है, यहां केंद्रीय निर्देशिका के शीर्षक, स्थानीय फ़ाइल के शीर्षक और प्रशस्ति पत्र हेडर के लिए एक और 5 बाइट्स खर्च होते हैं।

अनुकूलन

जिप बम का मूल डिजाइन प्राप्त करने के बाद, हम इसे यथासंभव कुशल बनाने की कोशिश करेंगे। हम दो सवालों के जवाब देना चाहते हैं:

• किसी दिए गए ज़िप फ़ाइल आकार के लिए अधिकतम संपीड़न अनुपात क्या है?
  
• ज़िप प्रारूप की सीमाओं को देखते हुए अधिकतम संपीड़न अनुपात क्या है?

कर्नेल संपीड़न

जितना संभव हो उतना कर्नेल को संपीड़ित करना हमारे लिए फायदेमंद है, क्योंकि प्रत्येक अनपैक बाइट को एन द्वारा गुणा किया जाता है । इस उद्देश्य के लिए, हम एक कस्टम DEFLATE कंप्रेसर का उपयोग करते हैं, जिसे बल्क_डफलेट कहा जाता है, जो बार-बार बाइट्स की एक स्ट्रिंग को संपीड़ित करने में विशेष है।

सभी सभ्य DEFLATE आर्काइव बार-बार बाइट्स के एक अंतहीन स्ट्रीम पर 1032 के संपीड़न अनुपात के करीब आते हैं, लेकिन हम विशिष्ट आकार के बारे में चिंतित हैं। हमारे संग्रह आकार में, बल्क_डेफलेट सामान्य-उद्देश्य वाले अभिलेखागार की तुलना में अधिक डेटा रखता है: ज़ालिब और इन्फो-ज़िप से लगभग 26 केबी, और ज़ोफ़ली से लगभग 15 केबी अधिक, जो संपीड़न गुणवत्ता की खातिर गति प्रदान करता है।



एक उच्च संपीड़न अनुपात की कीमत बल्क_डेफलेट - बहुमुखी प्रतिभा की कमी। यह बाइट्स दोहराने की केवल पंक्तियों को संकुचित कर सकता है और केवल एक निश्चित लंबाई, अर्थात् पूर्णांक k good 0. के लिए 517 + 258 k । अच्छा संपीड़न के अलावा, बल्क_डेफलेट जल्दी से काम करता है, इनपुट डेटा के आकार की परवाह किए बिना लगभग एक ही समय में काम करता है, वास्तव में एक संकुचित स्ट्रिंग लिखने के काम की गिनती।

फ़ाइल नाम

हमारे उद्देश्यों के लिए, फ़ाइल नाम लगभग मृत वजन हैं। हालाँकि वे स्थानीय फ़ाइलों के उद्धृत शीर्षकों का हिस्सा बनकर आउटपुट आकार में योगदान करते हैं, फ़ाइल नाम में बाइट्स कर्नेल में बाइट्स की तुलना में बहुत कम योगदान करते हैं। हम चाहते हैं कि संगतता के बारे में भूलने के बिना, फ़ाइल नाम यथासंभव छोटा हो।

फ़ाइल नाम पर खर्च किए गए प्रत्येक बाइट का अर्थ है दो बाइट्स कर्नेल पर खर्च नहीं किए गए हैं (दो क्योंकि प्रत्येक फ़ाइल का नाम दो बार दिखाई देता है: केंद्रीय निर्देशिका के हेडर में और स्थानीय फ़ाइल के हेडर में)। एक फ़ाइल नाम बाइट के परिणामस्वरूप औसतन केवल ( N + 1) / 4 बाइट्स का आउटपुट होता है, जबकि कर्नेल में एक बाइट 1032 N के रूप में गिना जाता है । उदाहरण: 1 , 2 , 3 ।

पहला संगतता विचार एन्कोडिंग है। ज़िप प्रारूप विनिर्देश में कहा गया है कि यदि विशिष्ट ध्वज बिट सेट है ( APPNOTE.TXT, परिशिष्ट D ) , तो फ़ाइल नाम की व्याख्या CP 437 या UTF-8 के रूप में की जानी चाहिए। यह जिप पार्सर्स के बीच असंगति का मुख्य बिंदु है, जो कुछ निश्चित या स्थानीय-विशिष्ट एन्कोडिंग में फ़ाइल नामों की व्याख्या कर सकता है। इसलिए, संगतता के लिए, अपने आप को सीपी 437 और यूटीएफ -8 दोनों में समान एन्कोडिंग वाले पात्रों तक सीमित करना बेहतर है। अर्थात्, ये 95 प्रिंट करने योग्य US-ASCII वर्ण हैं।

हम फ़ाइल सिस्टम नामकरण प्रतिबंधों से भी बंधे हैं। कुछ फ़ाइल सिस्टम केस असंवेदनशील होते हैं, इसलिए 'a' और 'A' को अलग-अलग नाम नहीं माना जाता है। सामान्य फ़ाइल सिस्टम, जैसे कि FAT32, कुछ वर्णों को प्रतिबंधित करता है , जैसे '*' और '?'।

एक सुरक्षित, लेकिन आवश्यक रूप से इष्टतम समझौता नहीं होने के कारण, हमारा ज़िप बम 36-वर्ण वर्णमाला के फ़ाइल नामों का उपयोग करेगा, जिसमें विशेष वर्ण और विभिन्न मामले के वर्ण शामिल नहीं हैं:

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

फ़ाइल नाम एक स्पष्ट तरीके से उत्पन्न होते हैं, बदले में सभी स्थिति, लूप के अंत में एक स्थिति के अलावा:

  "0", "1", "2", ..., "जेड",
 "00", "01", "02", ..., "0Z",
 ...,
 "Z0", "Z1", "Z2", ..., "ZZ",
 "000", "001", "002", ... 

36 एक-वर्ण फ़ाइल नाम, 36² दो-वर्ण नाम और इतने पर हैं। चार बाइट्स 1,727,604 विभिन्न फ़ाइल नामों के लिए पर्याप्त हैं।

यह देखते हुए कि संग्रह में फ़ाइल नामों में आमतौर पर अलग-अलग लंबाई होगी, मैं उन्हें कैसे बेहतर कर सकता हूं: सबसे छोटी से सबसे लंबी या इसके विपरीत? यदि आप थोड़ा सोचते हैं, तो सबसे लंबे नामों को अंतिम रूप देना बेहतर है। यह छँटाई 900 एमबी से अधिक आउटपुट को zblg.zip में जोड़ता है , जो सबसे कम समय तक ऑर्डर करने के लिए है। हालांकि, यह एक मामूली अनुकूलन है, क्योंकि 900 एमबी इश्यू के कुल आकार का केवल 0,0003% है।

मुख्य आकार

ओवरलैपिंग कोटिंग डिज़ाइन आपको एक संपीड़ित डेटा कोर रखने की अनुमति देता है, और फिर इसे कई बार सस्ते में कॉपी करता है। ज़िप फ़ाइल X के एक विशिष्ट आकार के लिए, कर्नेल के भंडारण के लिए आवंटित करने के लिए कितना स्थान इष्टतम है, और प्रतियां बनाने के लिए कितना?

इष्टतम संतुलन खोजने के लिए, आपको ज़िप संग्रह में केवल एक चर एन , फ़ाइलों की संख्या को अनुकूलित करने की आवश्यकता है। प्रत्येक N मान को केंद्रीय निर्देशिका के हेडर, स्थानीय फ़ाइलों के हेडर, उद्धरण ब्लॉक के हेडर और फ़ाइल नाम के लिए एक निश्चित राशि की आवश्यकता होती है। शेष स्थान कोर द्वारा कब्जा कर लिया जाएगा। चूँकि N एक पूर्णांक होना चाहिए, और कर्नेल का आकार शून्य होने से पहले आप केवल एक निश्चित संख्या में फ़ाइलें रख सकते हैं, यह 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 kB → 5.5 GB

  zipbomb --mode = quoted_overlap --num-files = 250-compressed-size = 21179> zbsm.zip 

अनुकूलन कर्नेल और फ़ाइल हेडर के बीच अंतरिक्ष के लगभग समान वितरण का कारण बना है। यह संयोग नहीं है। ओवरलैप के साथ एक प्रशस्ति पत्र निर्माण के सरलीकृत मॉडल पर विचार करें। एक सरलीकृत मॉडल में, हम फ़ाइल नामों की उपेक्षा करते हैं, साथ ही साथ स्थानीय फ़ाइलों के शीर्षकों को उद्धृत करने के कारण आउटपुट फ़ाइल के आकार में मामूली वृद्धि भी करते हैं। सरलीकृत मॉडल के विश्लेषण से पता चलेगा कि कर्नेल और फ़ाइल हेडर के बीच इष्टतम वितरण लगभग समान है, और इष्टतम वितरण के साथ आउटपुट आकार इनपुट के आकार के आधार पर चौगुनी बढ़ता है।

कुछ स्थिरांक और चर की परिभाषा:


बता दें कि H (N) N फाइलों के हेडर के लिए ओवरहेड का वॉल्यूम है। सूत्र का सार समझने के लिए चार्ट देखें।

$$

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

कर्नेल के लिए, X - H (N) स्थान बने हुए हैं। कुल अनपैक्ड साइज S _X (N) , C के अनपैक किए गए कर्नेल की N प्रतियों के आकार के बराबर है (इस सरलीकृत मॉडल में, हम उल्लिखित स्थानीय फ़ाइल हेडर से थोड़े अतिरिक्त विस्तार की उपेक्षा करते हैं)।

$$$ $ $ $ $ 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_ {OPT}) = CD2 (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 $ $ $ $ प्रदर्शित

एच (एन _ऑप्ट ) फ़ाइल हेडर रखने के लिए अधिकतम मात्रा में जगह देता है। यह CDH, LFH और C से स्वतंत्र है और X / 2 के करीब है।

$$$ $ प्रदर्शन $ $ H (N_ {OPT}) = N_ {OPT} CD (CDH + LFH) + (N_ {OPT} - 1) \ Q \\ = (X - Q) / 2 $ $ प्रदर्शन $ $

एस _एक्स (एन _ऑप्ट ) - इष्टतम वितरण में कुल अनपैक्ड आकार। इससे हम देखते हैं कि इनपुट डेटा बढ़ने के साथ आउटपुट का आकार चौगुना बढ़ जाता है।

$$

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

ज़िप फ़ाइल का आकार बढ़ाना, अंत में हम ज़िप प्रारूप की सीमाओं का सामना करेंगे: संग्रह में 2 ¹⁶ files1 फ़ाइलों की संख्या नहीं हो सकती है, जिनका आकार 2 ³² by1 बाइट्स से अधिक नहीं होगा। इससे भी बदतर, कुछ कार्यान्वयन 64-बिट एक्सटेंशन की उपस्थिति के संकेतक के रूप में अधिकतम मान लेते हैं, इसलिए हमारी सीमाएं वास्तव में 2 ¹⁶ −2 और 2 ³² .2 हैं। ऐसा होता है कि पहली बार हम एक असम्पीडित फ़ाइल के आकार पर एक सीमा का सामना करते हैं। 8 319 377 बाइट्स के ज़िप फ़ाइल आकार के साथ, भोले अनुकूलन हमें 47 837 फ़ाइलों की संख्या और 2 ³² +311 बाइट्स की अधिकतम फ़ाइल देगा।

(वास्तव में, सब कुछ थोड़ा और अधिक जटिल है, क्योंकि सटीक सीमाएं कार्यान्वयन पर निर्भर हैं। पायथन जिपफाइल गो में फाइलों की संख्या, संग्रह / ज़िप को अनदेखा करता है । फाइलों की संख्या बढ़ाने की अनुमति देता है जब तक कि वे निचले 16 बिट्स से मेल नहीं खाते। लेकिन सामान्य संगतता के लिए, हमें पालन करना होगा। स्थापित सीमा)।

यदि हम एन या कर्नेल आकार को असीम रूप से नहीं बढ़ा सकते हैं, तो हम ज़िप प्रारूप के भीतर अधिकतम संपीड़न अनुपात खोजना चाहेंगे। आपको फ़ाइलों की अधिकतम संख्या के साथ कर्नेल को यथासंभव बड़ा करने की आवश्यकता है। इस तथ्य के बावजूद कि हम कर्नेल और फ़ाइल हेडर के बीच लगभग एक समान पृथक्करण नहीं रख सकते हैं, प्रत्येक जोड़ी गई फ़ाइल अभी भी संपीड़न अनुपात को बढ़ाती है - बस के रूप में उपवास के रूप में यदि हम कर्नेल को बढ़ाना जारी रख सकते हैं। वास्तव में, जैसे ही फाइलें जोड़ी जाती हैं, हमें अधिकतम फ़ाइल आकार के लिए स्थान खाली करने के लिए कर्नेल के आकार को कम करना होगा, जो प्रत्येक फ़ाइल के साथ थोड़ा बढ़ता है।

योजना 2 ¹⁶ and2 फ़ाइलों और एक कर्नेल के साथ एक ज़िप संग्रह की ओर ले जाती है, जिसे 2 ³² by2 178 825 बाइट में अनपैक किया गया है। फाइलें जिप संग्रह की शुरुआत की ओर बड़ी होंगी - पहली और सबसे बड़ी फाइल 2 ³² .56 बाइट्स में अनपैक्ड है। यह उतना ही करीब है जितना कि हम बल्क_डेफलेट के रफ आउटपुट मापदंडों का उपयोग कर सकते हैं - अंतिम 54 बाइट्स को एन्कोडिंग करना उनके आकार से अधिक खर्च होगा (ज़िप फ़ाइल में पूरे 28 मिलियन का संपीड़न अनुपात है, और अंतिम 54 बाइट्स को अधिकतम 54 ⋅ 10 ³² ⋅ प्राप्त होगा। 2 ¹⁶ - 2)? 36; 5 मिलियन बाइट्स, इसलिए यह केवल मदद करता है यदि 54 बाइट्स को एक बाइट में एन्कोड किया जा सकता है - और मैं दो से कम कोड नहीं कर सकता। इसलिए, यदि आप 1 बाइट में 54 बाइट्स को एनकोड नहीं कर सकते हैं, यह केवल संपीड़न अनुपात को कम करता है)। इस जिप बम का आउटपुट साइज़ 281,395,456,244,934 बाइट्स है, 99.97% सैद्धांतिक अधिकतम (2 ³² - 1) × (2 ¹⁶ - 1)। संपीड़न अनुपात में कोई भी महत्वपूर्ण सुधार केवल इनपुट सिग्नल के आकार को कम करके प्राप्त किया जा सकता है, न कि आउटपुट को बढ़ाकर।

• zblg.zip 10 एमबी → 281 टीबी

  zipbomb --mode = quoted_overlap --num-files = 65534 - max-असंपीड़ित-आकार = 4292788525> zblg.zip 

कुशल सीआरसी -32 कम्प्यूटिंग

केंद्रीय निर्देशिका के शीर्ष लेख में मेटाडेटा और स्थानीय फ़ाइल के शीर्षलेख के बीच असम्पीडित फ़ाइल डेटा का एक चेकसम है - CRC-32 । यह एक समस्या है क्योंकि प्रत्येक फ़ाइल के लिए CRC-32 गणना की मात्रा इसके आकार के समानुपाती है, जो डिफ़ॉल्ट रूप से बहुत बड़ी है (आखिरकार, यह एक ज़िप बम है)। हम ऐसे काम करना पसंद करेंगे जो संग्रह के आकार के कम से कम आनुपातिक हों। दो कारक हमारे पक्ष में काम करते हैं: सभी फ़ाइलों में एक सामान्य कोर है, और एक असम्पीडित कर्नेल बार-बार बाइट्स का एक स्ट्रिंग है। एक मैट्रिक्स उत्पाद के रूप में सीआरसी -32 की कल्पना करें - यह हमें न केवल कर्नेल के चेकसम की गणना करने की अनुमति देगा, बल्कि फाइलों के बीच गणना का पुन: उपयोग करने की भी अनुमति देगा। इस खंड में वर्णित विधि zlib में crc32_combine फ़ंक्शन का एक छोटा विस्तार है, जिसे मार्क एडलर यहाँ बताते हैं ।

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-बाइनरी वेक्टर के रूप में राज्य रजिस्टर का प्रतिनिधित्व करते हैं और इसके अलावा और गुणा के लिए XOR का उपयोग करते हैं, तो crc32_update_0 एक रैखिक मानचित्रण है ; यानी, यह एक बाइनरी 32 × 32 संक्रमण मैट्रिक्स द्वारा गुणा के रूप में दर्शाया जा सकता है। यह समझने के लिए कि क्यों, वेक्टर द्वारा मैट्रिक्स को गुणा करना वेक्टर के संगत तत्व द्वारा प्रत्येक कॉलम को गुणा करने के बाद मैट्रिक्स के कॉलम को जोड़ना है। शिफ्ट ऑपरेशन state >> 1 बस स्टेट वेक्टर के प्रत्येक बिट i को लेता है और इसे एक वेक्टर द्वारा गुणा करता है जो बिट i - 1 को छोड़कर हर जगह शून्य है (बिट्स को दाएं से बाएं)। अपेक्षाकृत बोल, अंतिम XOR state ^ 0xedb88320 केवल तब होता है जब बिट b एक के बराबर होता है। यह 0xedb88320 द्वारा ख के पहले गुणन के रूप में दर्शाया जा सकता है, और फिर इस राज्य में XORing।

इसके अलावा, crc32_update_1 केवल crc32_update_0 प्लस (XOR) स्थिर है।यह crc32_update_1 एक अनुगामी परिवर्तन करता है : मैट्रिक्स गुणन इसके बाद मैपिंग (यानी, वेक्टर जोड़) होता है। हम एक चरण में मैट्रिक्स गुणन और मानचित्रण की कल्पना कर सकते हैं, यदि हम परिवर्तन मैट्रिक्स के आकार को 33 × 33 तक बढ़ाते हैं और राज्य वेक्टर में एक अतिरिक्त तत्व जोड़ते हैं, जो हमेशा 1 होता है (यह प्रतिनिधित्व सजातीय निर्देशांक कहा जाता है )।


परिवर्तन मैट्रिक्स 33 × 33 एम ₀ और एम _{1 हैं} , जो क्रमशः बिट्स 0 और 1 द्वारा किए गए सीआरसी -32 राज्य परिवर्तन की गणना करते हैं। कॉलम वैक्टर नीचे सबसे महत्वपूर्ण बिट के साथ संग्रहीत हैं: नीचे से ऊपर तक पहला कॉलम पढ़ते हुए, आप बहुपद स्थिरांक CRC-32 edb8832016 = 111 0 11 0 11 देखें0 111 000 1 00000 11 00 1 00000 ₂ । ये दोनों मैट्रीस केवल अंतिम कॉलम में भिन्न होते हैं, जो सजातीय निर्देशांक में अनुवाद वेक्टर का प्रतिनिधित्व करते हैं। M _{0 में,} अनुवाद शून्य है, और M _{1 में यह} edb88320 _{16 है} , बहुपद स्थिरांक CRC-32 है। इकाइयों आपरेशन के विकर्ण स्थिति ऊपर तुरंत कर रहे हैंstate >> 1

दोनों के संचालनcrc32_update_0औरcrc32_update_133 × 33 के संक्रमण मैट्रिक्स द्वारा दर्शाया जा सकता। Matrices M ₀ और M ₁ दिखाए जाते हैं।। मैट्रिक्स प्रतिनिधित्व का लाभ यह है कि मैट्रिक्स को कई गुना किया जा सकता है। मान लीजिए कि हम ASCII चरित्र 'a' को संसाधित करके एक राज्य परिवर्तन देखना चाहते हैं, जिसका द्विआधारी प्रतिनिधित्व 01100001 _{2 है} । हम एक परिवर्तन मैट्रिक्स में इन आठ बिट्स के सीआरसी -32 की स्थिति में संचयी परिवर्तन की कल्पना कर सकते हैं:

$$

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

और हम स्थिति पट्टी एम के कई प्रतियां गुणा करके 'एक' दोहरा में परिवर्तन कल्पना कर सकते हैं _और एक बिजली मैट्रिक्स के निर्माण -। हम इस जल्दी से उपयोग कर सकते हैं तेजी से घातांक एल्गोरिथ्म , जो एम गणना करने के लिए अनुमति देता है ⁿ सिर्फ लोग इन ₂ ⁿ चरणों। उदाहरण के लिए, यहां 9 अक्षरों 'a' की स्ट्रिंग की स्थिति बदलने के लिए एक मैट्रिक्स है:

$$

$$(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$$

मैट्रिक्स त्वरित गुणा एल्गोरिथ्म एम _{कर्नेल की} गणना के लिए उपयोगी है , एक असम्पीडित कर्नेल के लिए एक मैट्रिक्स, चूंकि कर्नेल दोहराया बाइट्स का एक स्ट्रिंग है। मैट्रिक्स से CRC-32 चेकसम प्राप्त करने के लिए, शून्य वेक्टर द्वारा मैट्रिक्स को गुणा करें (शून्य वेक्टर एक समान निर्देशांक में है, जो कि 32 शून्य है, और फिर इकाई है; यहां हम अनुपालन की जांच करने के लिए चेक के पूर्व और बाद के प्रसंस्करण की थोड़ी जटिलता को छोड़ देते हैं)। प्रत्येक फ़ाइल के लिए चेकसम की गणना करने के लिए, हम विपरीत दिशा में काम करते हैं। हम M: = M _{कर्नेल को} प्रारंभ करके शुरू करते हैं । कर्नेल चेकसम अंतिम फ़ाइल N का चेकसम भी है , इसलिए हम M को गुणा करते हैंएक शून्य वेक्टर और दुकानों CDH में प्राप्त चेकसम _एन और LFH _एन । फ़ाइल N - 1 का डेटा फ़ाइल N के फ़ाइल डेटा के समान है , लेकिन उपसर्ग LFH _{N के साथ} जोड़ा गया है । इसलिए, हम गणना करते हैं$$एम एल एफ एच एन , एलएफएच_एनऔर अपडेट केलिए राज्य परिवर्तन मैट्रिक्स$M_{L{FH_N}}$$$$M := M M_{L{FH_N}}$ ।अब M नाभिक के पीछे LFH _{N के} प्रसंस्करण से राज्य में संचयी परिवर्तन का प्रतिनिधित्व करता है । हम फ़ाइल N - 1 के लिए चेकसम की गणना करते हैं , फिर से शून्य वेक्टर द्वारा एम को गुणा करते हैं। जब तक सभी फाइलें संसाधित नहीं हो जाती हैं, तब तक हम एम में राज्य परिवर्तन मैट्रिक्स जमा करके प्रक्रिया जारी रखते हैं।

एक्सटेंशन: ज़िप 64

इससे पहले, हमने ज़िप प्रारूप की सीमाओं के कारण विस्तार की समस्या का सामना किया था - 281 टीबी से अधिक जारी करना असंभव था, भले ही स्मार्ट तरीके से ज़िप फ़ाइल को पैक किया गया हो। आप Zip64 का उपयोग करके इन सीमाओं को पार कर सकते हैं, एक ज़िप प्रारूप विस्तार जो कुछ हेडर फ़ील्ड के आकार को 64 बिट तक बढ़ाता है। Zip64 के लिए समर्थन किसी भी तरह से सार्वभौमिक नहीं है, लेकिन यह सबसे अधिक लागू किए गए एक्सटेंशनों में से एक है। संपीड़न अनुपात के लिए, ज़िप 64 का प्रभाव केंद्रीय निर्देशिका के हेडर के आकार को 46 से 58 बाइट्स तक और स्थानीय निर्देशिका के हेडर के आकार को 30 से 50 बाइट्स तक बढ़ाना है। सरलीकृत मॉडल में इष्टतम विस्तार गुणांक सूत्र को देखते हुए, हम देखते हैं कि ज़िप 64 प्रारूप में ज़िप बम अभी भी द्विघात रूप से बढ़ता है, लेकिन बड़े हर के कारण धीमा होता है - यह नीचे आरेख में देखा जा सकता है। संगतता और विकास मंदता के नुकसान के कारण, हम फ़ाइल आकार पर लगभग किसी भी प्रतिबंध को हटा देते हैं।

मान लीजिए कि हमें एक ज़िप बम की आवश्यकता है, जो 42.zip की तरह 4.5 PB तक फैलता है। पुरालेख कितना बड़ा होना चाहिए? बाइनरी खोज का उपयोग करते हुए, हम पाते हैं कि ऐसी फ़ाइल का न्यूनतम आकार 46 एमबी है।

• zbxl.zip 46 एमबी → 4.5 पीबी ( ज़िप 64, कम संगत)

 zipbomb --mode = quoted_overlap --num-files = 190023 - संगृहीत-आकार = 22982788 --zip64> zbxl.zip 

4.5 पेटाबाइट्स - इवेंट होरिजन टेलीस्कोप द्वारा डेटा की एक ही मात्रा को ब्लैक होल की पहली छवि के लिए रिकॉर्ड किया गया था : डेटा सेंटर में हार्ड ड्राइव के साथ रैक और रैक।

ज़िप 64 के साथ, अधिकतम संपीड़न अनुपात पर विचार करना लगभग दिलचस्प नहीं है, क्योंकि हम बस ज़िप फ़ाइल के आकार और इसके साथ संपीड़न अनुपात को बढ़ा सकते हैं, जब तक कि संपीड़ित ज़िप फ़ाइल निषेधात्मक न हो जाए। एक दिलचस्प सीमा, हालांकि, 2 ⁶⁴ बाइट्स (18 ईबी या 16 ईआईबी) है - इतना डेटा अधिकांश फ़ाइल सिस्टम पर फिट नहीं होगा। बाइनरी सर्च में सबसे छोटा ज़िप बम मिलता है जो कम से कम अधिक उत्पादन करता है: इसमें 12 मिलियन फाइलें और 1.5 जीबी का एक संपीड़ित कोर होता है। कुल ज़िप फ़ाइल का आकार 2.9 जीबी है और यह 2 ⁶⁴ में पैक किया गया है+11 727 895 877 बाइट्स 6.2 बिलियन से अधिक के संपीड़न अनुपात के साथ। मैंने इस फ़ाइल को डाउनलोड के लिए अपलोड नहीं किया है, लेकिन आप इसे स्रोत कोड का उपयोग करके स्वयं उत्पन्न कर सकते हैं । उसके पास इतने आकार की फाइलें हैं कि Info-ZIP UnZip 6.0 में भी एक बग सामने आया था ।

 zipbomb --mode = quoted_overlap --num-files = 12056313 - संगृहीत-आकार = 1482284040 --zip64> zbxxl.zip 

एक्सटेंशन: bzip2

ज़िप प्रारूप के लिए DEFLATE सबसे आम संपीड़न एल्गोरिदम है, लेकिन यह केवल कई विकल्पों में से एक है। संभवतः दूसरा सबसे आम एल्गोरिथ्म bzip2 है । हालाँकि यह DEFLATE की तरह संगत नहीं है। सैद्धांतिक रूप से, bzip2 में, अधिकतम संपीड़न अनुपात लगभग 1.4 मिलियन से एक है, जो कोर की एक सघन पैकिंग की अनुमति देता है।

bzip2 पहले "रन-लेंथ एन्कोडिंग" को एन्कोड करता है, बाइट्स को दोहराने की स्ट्रिंग लंबाई को 51 गुना कम करता है। फिर डेटा को 900 केबी ब्लॉक में विभाजित किया गया है और प्रत्येक ब्लॉक को अलग से संपीड़ित किया गया है। सैद्धांतिक रूप से, एक ब्लॉक 32 बाइट्स तक संपीड़ित कर सकता है। 900 000 × 51/32 = 1 434 375.

संगतता के नुकसान को अनदेखा करना, क्या bzip2 एक अधिक प्रभावी बम बनाता है?

हां - लेकिन केवल छोटी फाइलों के लिए। समस्या यह है कि bzip2 में असम्पीडित DEFLATE ब्लॉक जैसा कुछ भी नहीं है जिसका उपयोग हम स्थानीय फाइलों के हेडर को उद्धृत करने के लिए करते थे। इस प्रकार, फ़ाइलों को ओवरलैप करना और कर्नेल का पुन: उपयोग करना असंभव है - प्रत्येक फ़ाइल के लिए आपको अपनी कॉपी लिखने की आवश्यकता है, इसलिए समग्र संपीड़न अनुपात किसी भी एकल फ़ाइल के लिए अनुपात से बेहतर नहीं होगा। नीचे दिए गए ग्राफ़ में, हम देखते हैं कि ओवरलैपिंग के बिना, bzip2 आकार में मेगाबाइट के बारे में फ़ाइलों के लिए केवल DEFLATE से बेहतर है।

Bzip2 में हेडर को उद्धृत करने के एक वैकल्पिक साधन के लिए केवल आशा है, जिसकी चर्चा अगले भाग में की गई है। इसके अलावा, यदि आप जानते हैं कि एक विशेष ज़िप पार्सर bzip2 और का समर्थन करता हैबेमेल फ़ाइल नामों की अनुमति देता है, आप पूर्ण ओवरलैप निर्माण का उपयोग कर सकते हैं, जिसे उद्धृत करने की आवश्यकता नहीं है।


विभिन्न ज़िप बमों के संपीड़न अनुपात की तुलना। लॉगरिदमिक अक्ष पर ध्यान दें। प्रत्येक डिज़ाइन को Zip64 के साथ और उसके बिना दिखाया गया है। ओवरलैप के बिना संरचनाओं में एक रैखिक विकास दर होती है, जिसे कुल्हाड़ियों के निरंतर अनुपात से देखा जा सकता है। Bzip2 ग्राफ के ऊर्ध्वाधर ऑफसेट का मतलब है कि bzip2 का संपीड़न अनुपात DEFLATE से लगभग एक हजार गुना अधिक है। उल्लिखित निर्माणों में एक द्विघात विकास दर है, जैसा कि 2: 1 कुल्हाड़ियों के झुकाव के कारण होता है। ज़िप 64 वैरिएंट थोड़ा कम प्रभावी है, लेकिन 281 टीबी से अधिक की अनुमति देता है। एक अतिरिक्त क्षेत्र के माध्यम से bzip2 के लिए रेखांकन द्विघात से रैखिक में जाते हैं जब या तो अधिकतम फ़ाइल आकार पहुंच जाता है (2 ³²⁾ −2 बाइट्स), या फ़ाइलों की अधिकतम अनुमत संख्या

विस्तार: एक अतिरिक्त क्षेत्र के माध्यम से उद्धृत करना

अब तक, हमने स्थानीय फ़ाइलों के हेडर को उद्धृत करने के लिए DEFLATE फ़ंक्शन का उपयोग किया है, और हमने अभी देखा कि यह ट्रिक bzip2 में काम नहीं करती है। हालांकि, एक वैकल्पिक उद्धरण पद्धति है, कुछ हद तक सीमित है, जो केवल ज़िप प्रारूप कार्यों का उपयोग करती है और संपीड़न एल्गोरिदम से स्वतंत्र है।

स्थानीय फ़ाइल के हेडर संरचना के अंत में, स्टोर करने की जानकारी के लिए चर लंबाई का एक अतिरिक्त क्षेत्र है जो सामान्य हेडर फ़ील्ड ( APPNOTE.TXT, खंड 4.3.7) में फिट नहीं होता है)। अतिरिक्त जानकारी में उदाहरण के लिए, यूनिक्स से एक टाइमस्टैम्प या यूआईडी / जीआईडी ​​शामिल हो सकता है। Zip64 जानकारी को एक अतिरिक्त फ़ील्ड में भी संग्रहीत किया जाता है। एक अतिरिक्त फ़ील्ड को लंबाई-मूल्य संरचना के रूप में दर्शाया गया है; यदि आप मान को जोड़े बिना लंबाई बढ़ाते हैं, तो अतिरिक्त फ़ील्ड में वह होगा जो ज़िप फ़ाइल में पीछे है, अर्थात् स्थानीय फ़ाइल का अगला शीर्षलेख। इस पद्धति का उपयोग करते हुए, स्थानीय फ़ाइल के प्रत्येक हेडर निम्नलिखित हेडर को "उद्धरण" कर सकते हैं, उन्हें अपने स्वयं के अतिरिक्त क्षेत्र में संलग्न कर सकते हैं। DEFLATE की तुलना में, तीन फायदे हैं:

1. अतिरिक्त फ़ील्ड के माध्यम से उद्धृत करने के लिए कर्नेल के लिए अधिक स्थान छोड़कर केवल 4 बाइट्स की आवश्यकता होती है, 5 नहीं।
   
2. यह फ़ाइल आकार में वृद्धि नहीं करता है, जिसका अर्थ है एक बड़ा कर्नेल, जिसे ज़िप प्रारूप की सीमाएं दी गई हैं।
   
3. यह bzip2 में उद्धरण प्रदान करता है।

इन लाभों के बावजूद, अतिरिक्त क्षेत्रों के माध्यम से उद्धृत करना कम लचीला है। यह एक श्रृंखला नहीं है, जैसा कि DEFLATE में: स्थानीय फ़ाइल के प्रत्येक शीर्षक में न केवल तुरंत निम्नलिखित शीर्षक शामिल होने चाहिए, बल्कि सभी शीर्ष शीर्षक भी होने चाहिए । जैसे ही आप ज़िप फ़ाइल की शुरुआत के लिए अतिरिक्त फ़ील्ड बढ़ाते हैं। चूंकि अधिकतम क्षेत्र की लंबाई 2 ¹⁶ by1 बाइट्स है, केवल 1808 स्थानीय फ़ाइल हेडर (या ज़िप 64 में 1170) को उद्धृत किया जा सकता है, यह मानते हुए कि नामों को अपेक्षित रूप से सौंपा गया है।(DEFLATE के मामले में, आप स्थानीय फ़ाइलों के पहले (सबसे छोटे) हेडर को उद्धृत करने के लिए एक अतिरिक्त फ़ील्ड का उपयोग कर सकते हैं, और फिर बाकी के लिए DEFLATE को उद्धृत करने के लिए स्विच कर सकते हैं)। एक अन्य समस्या: अतिरिक्त क्षेत्र की आंतरिक डेटा संरचना के अनुरूप होने के लिए, यह ( APPNOTE.TXT, खंड 4.5.2 ) प्रकार के लिए 16-बिट टैग का चयन करना आवश्यक है , जो कि उद्धरण डेटा से पहले है। हम एक प्रकार का टैग चुनना चाहते हैं जो पार्सर्स को उद्धरण चिह्नों में डेटा को अनदेखा करने के बजाय, उन्हें सार्थक मेटाडेटा के रूप में व्याख्या करने का प्रयास करेगा। जिप पार्सर्स को अज्ञात प्रकार के टैग को अनदेखा करना चाहिए, इसलिए हम यादृच्छिक पर टैग का चयन कर सकते हैं, लेकिन एक जोखिम है कि भविष्य में कुछ टैग डिजाइन की संगतता का उल्लंघन करेंगे।

पिछला आरेख bzip2, c और बिना ZIP64 के अतिरिक्त क्षेत्रों का उपयोग करने की संभावना को दर्शाता है। दोनों ग्राफ़ में एक मोड़ होता है, जब विकास द्विघात से रैखिक में चला जाता है। बिना ZIP64 के, यह होता है जहाँ असम्पीडित फ़ाइल का अधिकतम आकार (2 ³²⁾ तक पहुँच जाता है−2 बाइट्स); तब आप केवल फ़ाइलों की संख्या बढ़ा सकते हैं, लेकिन उनका आकार नहीं। ग्राफ़ पूरी तरह से समाप्त हो जाता है जब फ़ाइलों की संख्या 1809 तक पहुंच जाती है, तो हम अतिरिक्त हेडर के हवाले से एक अतिरिक्त क्षेत्र में अंतरिक्ष से बाहर भागते हैं। ज़िप 64 के साथ, 1171 फ़ाइलों पर एक फ्रैक्चर होता है, जिसके बाद केवल फ़ाइल का आकार बढ़ाया जा सकता है, लेकिन उनकी संख्या नहीं। अतिरिक्त क्षेत्र DEFLATE के मामले में मदद करता है, लेकिन यह अंतर इतना छोटा है कि यह दृष्टिगत नहीं है। यह zbsm.zip के संपीड़न अनुपात को 1.2% बढ़ाता है; zblg.zip 0.019% द्वारा; और zbxl.zip 0.0025% द्वारा।

चर्चा

इस विषय पर अपने काम में, Pletz और सहकर्मियों ने लगभग ओवर-प्रतिकृति ज़िप संग्रह बनाने के लिए फ़ाइल ओवरलैप का उपयोग किया है। फ़ाइल ओवरलैप को पहले सुझाव दिया गया था (स्लाइड 47) गिनावेल कोल्डविंड द्वारा।

हमने ज़िप बम का एक डिज़ाइन विकसित किया है जिसमें एक उद्धरण ओवरलैप है, जो खाते की संगतता पर निर्भर करता है - कार्यान्वयन में कई अंतर, जिनमें से कुछ नीचे दी गई तालिका में दिखाए गए हैं। परिणामी डिज़ाइन ज़िप पार्सर के साथ संगत है जो सामान्य तरीके से काम करता है, अर्थात, पहले केंद्रीय निर्देशिका की जांच करना और इसे फ़ाइलों के सूचकांक के रूप में उपयोग करना। उनमें से, कील से एक अद्वितीय ज़िप पार्सरजो औपचारिक व्याकरण से स्वतः उत्पन्न होता है। हालांकि, डिजाइन "स्ट्रीमिंग" पार्सर्स के साथ असंगत है, जो केंद्रीय निर्देशिका को पहले पढ़े बिना एक पास में शुरू से अंत तक ज़िप फ़ाइल का विश्लेषण करता है। उनकी प्रकृति से, स्ट्रीमिंग पार्सर किसी भी तरह से फ़ाइलों को ओवरलैप करने की अनुमति नहीं देते हैं। सबसे अधिक संभावना है, वे केवल पहली फ़ाइल निकालेंगे। इसके अलावा, वे एक त्रुटि भी फेंक सकते हैं, जैसा कि सनज़िप के साथ होता है , जो अंत में केंद्रीय निर्देशिका को पार्स करता है और स्थानीय फ़ाइलों के हेडर के साथ स्थिरता के लिए जांच करता है जो पहले ही देख चुका है।

यदि आप निकाली गई फ़ाइलों को एक विशिष्ट उपसर्ग के साथ शुरू करना चाहते हैं, जो स्थानीय फ़ाइल के हेडर बाइट्स से अलग है, तो आप असम्बद्ध ब्लॉक से पहले एक डीफ्लैट ब्लॉक को सम्मिलित कर सकते हैं जो निम्न हेडर कोट्स में होता है। ज़िप संग्रह में प्रत्येक फ़ाइल को बम के निर्माण में भाग नहीं लेना चाहिए: यदि आवश्यक हो, तो आप कुछ विशेष प्रारूप के अनुरूप करने के लिए संग्रह में साधारण फ़ाइलों को भी शामिल कर सकते हैं ( --templateइस उपयोग के मामले के लिए स्रोत कोड में एक पैरामीटर है )। कई प्रारूप ज़िप को एक कंटेनर के रूप में उपयोग करते हैं, जैसे कि जावा जार दस्तावेज़, एंड्रॉइड एपीके और लिब्रे ऑफिस।

पीडीएफकई तरह से जिप के समान। इसमें फ़ाइल के अंत में एक क्रॉस-रेफरेंस टेबल है जो पिछली वस्तुओं की ओर इशारा करता है, और यह FlateDecode फ़िल्टर के माध्यम से वस्तुओं के संपीड़न का समर्थन करता है। मैंने कोशिश नहीं की है, लेकिन आप पीडीएफ बम बनाने के लिए ओवरलैप के साथ उद्धृत करने के विचार का उपयोग कर सकते हैं। शायद आपको यहां कड़ी मेहनत करने की ज़रूरत नहीं है: बाइनरीहेक्स0आर एक ब्लॉग पोस्ट में लिखते हैं कि आप बस एक ऑब्जेक्ट पर कई फ्लेडेटडॉब परतों को निर्दिष्ट कर सकते हैं, जिसके बाद एक पीडीएफ बम बनाना तुच्छ हो जाता है।

इस आलेख में वर्णित ज़िप बमों के एक विशेष वर्ग को परिभाषित करना आसान है: बस ओवरलैपिंग फ़ाइलों को ढूंढें। मार्क एडलर ने एक पैच लिखाUnzip Info-ZIP के लिए, जो कि बस यही करता है। हालांकि, सामान्य रूप से, ओवरलैपिंग फ़ाइलों को अवरुद्ध करने से सभी प्रकार के ज़िप बमों से रक्षा नहीं होती है। अग्रिम में भविष्यवाणी करना मुश्किल है कि क्या फ़ाइल एक जिप बम है या नहीं अगर आपको पार्सर्स के आंतरिक घटकों के बारे में सटीक ज्ञान नहीं है जो इसका विश्लेषण करने के लिए उपयोग किया जाएगा। हेडर को देखते हुए और सभी फ़ाइलों के "असम्पीडित आकार" फ़ील्ड को समेटने से काम नहीं चलता है , क्योंकि हेडर में मान वास्तविक असम्पीडित आकार (संगतता तालिका में, "लाइन" फ़ाइल बहुत छोटा है "की अनुमति देता है) से मेल नहीं खा सकता है। ज़िप बम के खिलाफ विश्वसनीय सुरक्षा में इसके संचालन के दौरान ज़िप पार्सर में समय, मेमोरी और डिस्क स्थान की सीमाएं शामिल हैं। जिप फ़ाइलों की पार्सिंग करें, बिना किसी डेटा के किसी भी जटिल ऑपरेशन की तरह, सावधानी के साथ।


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

धन्यवाद

इस लेख के मसौदे पर टिप्पणियों के लिए मार्क एडलर , रोस कॉक्स , ब्रैंडन एनर , मारेक मेकोवस्की , जोश वोल्फ और USENIX WOOT 2019 के समीक्षकों का धन्यवाद । Kaolan McNamara ने लिबर ऑफिस की सुरक्षा पर जिप बम के प्रभाव का आकलन किया।

इस लेख का एक संस्करण USENIX WOOT 2019 कार्यशाला के लिए तैयार किया गया है । सोर्स कोड उपलब्ध है। कार्यशाला में प्रस्तुति के लिए कलाकृतियाँ zipbomb-woot19.zip फ़ाइल में हैं ।

क्या आपको एक ऐसी प्रणाली मिली जो किसी एक बम को गिरा देती है? क्या बमों से आपको बग ढूंढने या बग सर्च प्रोग्राम में पैसे कमाने में मदद मिली? मुझे बताएं, मैं यहां इसका उल्लेख करने की कोशिश करूंगा।

लिबरऑफिस 6.1.5.2

Zblg.zip को zblg.odt या zblg.docx के नाम से बदलने के बाद, LibreOffice लगभग 4 जीबी की अस्थायी फ़ाइलों की एक श्रृंखला बनाता है और हटाता है, फ़ाइल प्रारूप को निर्धारित करने की कोशिश करता है। अंततः, वह ऐसा करने के लिए समाप्त हो जाता है और अस्थायी फ़ाइलों को हटा देता है क्योंकि वे आते हैं, इसलिए ज़िप बम केवल डिस्क को भरने के बिना एक अस्थायी DoS का कारण बनता है। Kaolan McNamara ने मेरे त्रुटि संदेश का जवाब दिया।

मोज़िला addons- सर्वर 2019.06.06

मैंने स्थानीय एडोनस-सर्वर इंस्टालेशन के खिलाफ जिप बमों की कोशिश की, जो कि एडनस.मोजिला.ऑल सॉफ्टवेयर का हिस्सा है। फ़ाइलों के निष्कर्षण पर 110 सेकंड की समय सीमा लगाते हुए, सिस्टम इनायत से बम को संभालता है। जिप बम तेजी से फैलता है, जहां तक ​​डिस्क इस समय सीमा तक अनुमति देता है, लेकिन फिर प्रक्रिया को मार दिया जाता है और अनपैक की गई फाइलें अंततः अपने आप साफ हो जाती हैं।

अंजिप 6.0

मार्क एडलर ने ज़िप बम के इस वर्ग का पता लगाने के लिए अनज़िप के लिए एक पैच लिखा।

5 जुलाई, 2019: मैंने देखा कि CVE-2019-13232 को UnZip को सौंपा गया था। व्यक्तिगत रूप से, मैं तर्क दूंगा कि इस तरह के जिप बम को संसाधित करने के लिए अनज़िप (या किसी भी ज़िप पार्सर) की क्षमता / अक्षमता आवश्यक रूप से एक भेद्यता या एक बग है। यह एक प्राकृतिक कार्यान्वयन है जो विनिर्देश का उल्लंघन नहीं करता है, मैं क्या कह सकता हूं। इस लेख में बम प्रकार सिर्फ एक प्रकार है, और कई अन्य तरीके हैं जिनसे आप ज़िप पार्सर की पहेली बना सकते हैं। जैसा कि ऊपर उल्लेख किया गया है, यदि आप संसाधन थकावट के हमलों से खुद को बचाना चाहते हैं, तो आपको हर एक ज्ञात हमले को सूचीबद्ध करने, पता लगाने और अवरुद्ध करने की कोशिश नहीं करनी चाहिए; इसके बजाय, समय और अन्य संसाधनों पर बाहरी प्रतिबंध स्थापित करना आवश्यक है ताकि पार्सर ऐसी स्थिति में न आए, चाहे वह किसी भी तरह के हमले का सामना क्यों न करे। पहले पास के अनुकूलन के रूप में कुछ डिजाइनों का पता लगाने और अस्वीकार करने की कोशिश में कुछ भी गलत नहीं है,लेकिन आप वहाँ नहीं रुक सकते। जब तक आप अविश्वसनीय डेटा के साथ संचालन को अलग और प्रतिबंधित नहीं करते हैं, तब तक आपका सिस्टम संभवतः कमजोर है। HTML में क्रॉस-साइट स्क्रिप्टिंग के साथ समानता पर विचार करें: सही सुरक्षा विशिष्ट बाइट्स को फ़िल्टर करने की कोशिश करना नहीं है जिन्हें कोड के रूप में व्याख्या की जा सकती है, लेकिन सब कुछ सही ढंग से बचने के लिए।

एंटीवायरस इंजन

ट्विटर उपयोगकर्ता @TVqQAAMAAAAEAAA रिपोर्ट करता है : "मेरी परीक्षण मशीन पर McAfee एंटीवायरस बस विस्फोट हो गया।" मैंने खुद इसका परीक्षण नहीं किया है और संस्करण संख्या के रूप में मेरे पास ऐसा कोई विवरण नहीं है।

Tavis Ormandi इंगित करता है कि VirusTotal में zblg.zip ( 6 जून, 2019 से स्क्रीनशॉट) के लिए कई टाइमआउट हैं : AhnLab-V3, ClamAV, DrWeb, Endgame, F-Secure, GData, K7AntiVirus, K7GW, MaxSecure, McAfee, Mcfee। -एडिशन, पांडा, क्यूहु-360, सोफोस एमएल, वीबीए 32। परिणाम zbsm.zip ( 6 जून, 2019 से स्क्रीनशॉट)) समान हैं, लेकिन टाइमआउट इंजन के एक अलग सेट के साथ: बैदो, बीकव, क्लैमाव, सीएमसी, DrWeb, Endgame, ESET-NOD32, F-Secure, GData, Kingsoft, McAee-GW-Edition, NANO-Antivirus, Acronis। दिलचस्प बात यह है कि zbxl.zip ( 6 जून, 2019 से स्क्रीनशॉट ) के परिणामों में कोई टाइमआउट नहीं है । शायद कुछ एंटीवायरस ज़िप 64 का समर्थन नहीं करते हैं? कई इंजन एक तरह के "कम्प्रेशन बम" के रूप में फाइलों का पता लगाते हैं। यह देखना दिलचस्प है कि क्या वे मामूली बदलाव के साथ ऐसा करना जारी रखेंगे, जैसे फ़ाइल नाम बदलना या प्रत्येक फ़ाइल में ASCII उपसर्ग जोड़ना।

अंतिम वक्तव्य

फेसबुक को खत्म करने का समय आ गया है। यह आपके लिए एक तटस्थ काम नहीं है: हर दिन जब आप काम पर आते हैं, तो आप कुछ गलत कर रहे हैं। अगर आपका फेसबुक अकाउंट है, तो उसे डिलीट कर दें। अगर आप फेसबुक पर काम करते हैं, तो बिछुड़ जाइए।

और यह मत भूलो कि राष्ट्रीय सुरक्षा एजेंसी को नष्ट कर दिया जाना चाहिए।