First Fit

Reading time: 8 minutes

First Fit

जब आप glibc का उपयोग करके किसी प्रोग्राम में मेमोरी को फ्री करते हैं, तो मेमोरी के टुकड़ों को प्रबंधित करने के लिए विभिन्न "बिन" का उपयोग किया जाता है। यहाँ दो सामान्य परिदृश्यों का एक सरल स्पष्टीकरण है: अनसॉर्टेड बिन और फास्टबिन।

Unsorted Bins

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

उदाहरण:

• आप 300 बाइट (a) आवंटित करते हैं, फिर 250 बाइट (b), फिर a को फ्री करते हैं और फिर से 250 बाइट (c) मांगते हैं।
• जब आप a को फ्री करते हैं, तो यह अनसॉर्टेड बिन में चला जाता है।
• यदि आप फिर से 250 बाइट मांगते हैं, तो आवंटक a को टेल में पाता है और इसे विभाजित करता है, आपके अनुरोध के अनुसार फिट होने वाला भाग वापस करता है और बाकी को बिन में रखता है।
• c पिछले a की ओर इशारा करेगा और a की सामग्री से भरा होगा।

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

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

Example:

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

🔥 आधुनिक glibc विचार (tcache ≥ 2.26)

glibc 2.26 से हर थ्रेड अपनी tcache रखता है जिसे unsorted bin से पहले क्वेरी किया जाता है। इसलिए एक first-fit परिदृश्य केवल तब प्राप्त होगा यदि:

1. अनुरोधित आकार tcache_max (डिफ़ॉल्ट रूप से 64-बिट पर 0x420) से बड़ा है, या
2. संबंधित tcache बिन पहले से ही भरा हुआ है या मैन्युअल रूप से खाली किया गया है (7 तत्वों को आवंटित करके और उन्हें उपयोग में रखकर)।

वास्तविक हमलों में आप आमतौर पर एक सहायक रूटीन जोड़ेंगे जैसे:

// Drain the tcache for a given size
for(int i = 0; i < 7; i++) pool[i] = malloc(0x100);
for(int i = 0; i < 7; i++) free(pool[i]);

एक बार जब tcache समाप्त हो जाता है, तो बाद में की गई frees अनसॉर्टेड बिन में जाती हैं और क्लासिक फर्स्ट-फिट व्यवहार (टेल सर्च, हेड इंसर्शन) फिर से सक्रिय किया जा सकता है।

🚩 पहले-फिट के साथ ओवरलैपिंग-चंक UAF बनाना

नीचे दिया गया अंश (glibc 2.38 पर परीक्षण किया गया) दिखाता है कि अनसॉर्टेड बिन में स्प्लिटर का दुरुपयोग कैसे किया जा सकता है ताकि 2 ओवरलैपिंग पॉइंटर्स बनाए जा सकें - एक शक्तिशाली प्राइमिटिव जो एकल फ्री को राइट-आफ्टर-फ्री में परिवर्तित करता है।

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
setbuf(stdout, NULL);

/* 1. prepare 2 adjacent chunks and free the first one */
char *A = malloc(0x420);   // big enough to bypass tcache
char *B = malloc(0x420);
strcpy(A, "AAAA\n");
free(A);                   // A → unsorted

/* 2. request a *smaller* size to force a split of A */
char *C = malloc(0x400);   // returns lower half of former A

/* 3. The remainder of A is still in the unsorted bin.
Another 0x400-byte malloc will now return the *same*
region pointed to by B – creating a UAF/overlap. */
char *C2 = malloc(0x400);

printf("B  = %p\nC2 = %p (overlaps B)\n", B, C2);

// Arbitrary write in B is immediately visible via C2
memset(B, 'X', 0x10);
fwrite(C2, 1, 0x10, stdout);  // prints Xs
}

Exploitation recipe (common in recent CTFs):

1. टारगेट आकार के लिए tcache को ड्रेन करें।
2. एक चंक को फ्री करें ताकि यह अनसॉर्टेड बिन में जाए।
3. एक थोड़ा छोटा आकार अलॉट करें - अल्लोकेटर अनसॉर्टेड चंक को विभाजित करता है।
4. फिर से अलॉट करें - बचे हुए भाग का एक मौजूदा उपयोग में चंक के साथ ओवरलैप होता है → UAF।
5. संवेदनशील फ़ील्ड्स (फंक्शन पॉइंटर्स, FILE vtable, आदि) को ओवरराइट करें।

एक व्यावहारिक अनुप्रयोग 2024 HITCON Quals Setjmp चुनौती में पाया जा सकता है जहाँ इस सटीक प्राइमिटिव का उपयोग UAF से __free_hook के पूर्ण नियंत्रण में जाने के लिए किया जाता है।

🛡️ Mitigations & Hardening

• सेफ-लिंकिंग (glibc ≥ 2.32) केवल सिंगली-लिंक्ड tcache/fastbin सूचियों की रक्षा करता है। अनसॉर्टेड/छोटे/बड़े बिन अभी भी कच्चे पॉइंटर्स को स्टोर करते हैं, इसलिए पहले-फिट आधारित ओवरलैप तब भी संभव हैं यदि आप एक हीप लीक प्राप्त कर सकते हैं।
• हीप पॉइंटर एन्क्रिप्शन & MTE (ARM64) अभी तक x86-64 glibc को प्रभावित नहीं करते हैं, लेकिन वितरण हार्डनिंग फ्लैग जैसे GLIBC_TUNABLES=glibc.malloc.check=3 असंगत मेटाडेटा पर abort करेंगे और सरल PoCs को तोड़ सकते हैं।
• फ्री पर tcache भरना (2024 में glibc 2.41 के लिए प्रस्तावित) अनसॉर्टेड उपयोग को और कम करेगा; सामान्य एक्सप्लॉइट विकसित करते समय भविष्य के रिलीज़ की निगरानी करें।

Other References & Examples

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Use after free: एक उपयोगकर्ता ऑब्जेक्ट उत्पन्न करें, इसे फ्री करें, एक ऑब्जेक्ट उत्पन्न करें जो फ्री किए गए चंक को प्राप्त करता है और इसे लिखने की अनुमति देता है, पिछले वाले से user->password की स्थिति को ओवरराइट करना। उपयोगकर्ता को फिर से उपयोग करें ताकि पासवर्ड चेक को बायपास किया जा सके।
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• प्रोग्राम नोट्स बनाने की अनुमति देता है। एक नोट में नोट की जानकारी एक malloc(8) में होगी (जिसमें एक फ़ंक्शन का पॉइंटर होगा जिसे कॉल किया जा सकता है) और एक अन्य malloc() का पॉइंटर होगा जिसमें नोट की सामग्री होगी।
• हमला 2 नोट्स (note0 और note1) बनाने का होगा जिनकी malloc सामग्री नोट की जानकारी के आकार से बड़ी होगी और फिर उन्हें फ्री करें ताकि वे फास्ट बिन (या tcache) में जाएं।
• फिर, एक और नोट (note2) बनाएं जिसकी सामग्री का आकार 8 हो। सामग्री note1 में होगी क्योंकि चंक को फिर से उपयोग किया जाएगा, जहाँ हम फ़ंक्शन पॉइंटर को win फ़ंक्शन की ओर इंगित करने के लिए संशोधित कर सकते हैं और फिर नोट1 को Use-After-Free करके नए फ़ंक्शन पॉइंटर को कॉल कर सकते हैं।
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• कुछ मेमोरी आवंटित करना, वांछित मान लिखना, इसे फ्री करना, फिर से आवंटित करना संभव है और चूंकि पिछले डेटा अभी भी वहां है, इसे चंक में नए अपेक्षित संरचना के अनुसार माना जाएगा जिससे मान सेट करना या फ्लैग प्राप्त करना संभव हो जाएगा।
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• इस मामले में एक विशिष्ट चंक के अंदर 4 लिखना आवश्यक है जो पहले आवंटित किया गया है (यहां तक कि सभी को बलपूर्वक फ्री करने के बाद भी)। प्रत्येक नए आवंटित चंक में इसका नंबर एरे इंडेक्स में स्टोर किया जाता है। फिर, 4 चंक्स (+ प्रारंभ में आवंटित) आवंटित करें, अंतिम में 4 होगा, उन्हें फ्री करें और पहले वाले के पुनः आवंटन को बल दें, जो अंतिम फ्री किए गए चंक का उपयोग करेगा जिसमें 4 होगा।
• 2024 HITCON Quals Setjmp write-up (Quarkslab) – व्यावहारिक पहले-फिट / अनसॉर्टेड-स्प्लिट ओवरलैप हमला: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify write-up – अनसॉर्टेड-बिन विभाजन का दुरुपयोग करके libc लीक करना और ओवरलैप प्राप्त करना: https://hackmd.io/@aneii11/H1S2snV40