> For the complete documentation index, see [llms.txt](https://docs.cooku222.kr/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-textbook-hmac.md).

# \[DreamHack] Textbook-HMAC

#### WriteUp

```
#chall.py
import hashlib
import os

K = os.urandom(500)
flag = open("flag.txt", "r").read()

def HMAC(M):
    return hashlib.md5(K + M).digest()

m1 = b"Dreamhack"
h1 = HMAC(m1)

print(f"HMAC(\"Dreamhack\") = {bytes.hex(h1)}")

m2 = bytes.fromhex(input("Your message: "))
h2 = bytes.fromhex(input("Your hash: "))

if m2 != m1 and h2 == HMAC(m2):
    print(flag)
```

-> MD5 해시 함수를 이용해 구현된 HMAC 함수가 존재함. 500바이트의 미지 랜덤 상수 K에 대해 K+M의 해시값을 리턴

-> M = b"Dreamhack"인 경우의 HMAC 리턴값이 주어지고, 이를 이용해 b"Dreamhack"이 아닌 다른 메시지의 HMAC 리턴값을 구하면 문제 해결 가능

-> Merkie-Damgard 구조 + MD5 해시 함수의 구현 -> Length extension attack

 

\* 보통은 MD5가 hashlib에 내장이 되어있으나 여기선 Length extension attack이기 때문에 따로 MD5 용 파이선 파일을 만들어야 한다.

```
#MD5 Pseudocode
// : All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
var int s[64], K[64]
var int i

// s specifies the per-round shift amounts
s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }

// Use binary integer part of the sines of integers (Radians) as constants:
for i from 0 to 63 do
    K[i] := floor(2^32 × abs(sin(i + 1)))
end for
// (Or just use the following precomputed table):
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
...생략...
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

// Initialize variables:
var int a0 := 0x67452301   // A
var int b0 := 0xefcdab89   // B
var int c0 := 0x98badcfe   // C
var int d0 := 0x10325476   // D

// Pre-processing: adding a single 1 bit
append "1" bit to message<    
 // Notice: the input bytes are considered as bit strings,
 //  where the first bit is the most significant bit of the byte.[53]

// Pre-processing: padding with zeros
append "0" bit until message length in bits ≡ 448 (mod 512)

// Notice: the two padding steps above are implemented in a simpler way
 //  in implementations that only work with complete bytes: append 0x80
 //  and pad with 0x00 bytes so that the message length in bytes ≡ 56 (mod 64).

append original length in bits mod 2^64 to message

// Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message do
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
    // Initialize hash value for this chunk:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
    // Main loop:
    for i from 0 to 63 do
        var int F, g
        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31 then
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47 then
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63 then
            F := C xor (B or (not D))
            g := (7×i) mod 16
        // Be wary of the below definitions of a,b,c,d
        F := F + A + K[i] + M[g]  // M[g] must be a 32-bit block
        A := D
        D := C
        C := B
        B := B + leftrotate(F, s[i])
    end for
    // Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 // (Output is in little-endian)
```

<figure><img src="https://blog.kakaocdn.net/dna/dcWCnR/btsNggoIjs5/AAAAAAAAAAAAAAAAAAAAAEXV5Si4qPwmrSUeqZyeCDAojGctyg373s6yAWVX34M_/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&#x26;expires=1782831599&#x26;allow_ip=&#x26;allow_referer=&#x26;signature=CRG7ODR8fOjtDGIH%2BeQ5kaTXiYU%3D" alt="" height="282" width="592"><figcaption></figcaption></figure>

상수 값 세팅

```
// : All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
var int s[64], K[64]
var int i

// s specifies the per-round shift amounts
s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }

// Use binary integer part of the sines of integers (Radians) as constants:
for i from 0 to 63 do
    K[i] := floor(2^32 × abs(sin(i + 1)))
end for
// (Or just use the following precomputed table):
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
...생략...
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

// Initialize variables:
var int a0 := 0x67452301   // A
var int b0 := 0xefcdab89   // B
var int c0 := 0x98badcfe   // C
var int d0 := 0x10325476   // D
```

-> MD5 해시 과정에서 필요한 상수 값 세팅

-> s, k는 추후에 state의 블록과의 연산 과정에서 사용되고, a0\~d0은 IV, 즉 초기 state를 세팅할 때 사용

-> Merkie-Damgard 구조 그림의 맨 앞에 있는 IV에 a0\~d0의 값들이 들어간다.(막판에 보면 정수로 할당된 16진수 값 있음)

패딩

```
// Pre-processing: adding a single 1 bit
append "1" bit to message<    
 // Notice: the input bytes are considered as bit strings,
 //  where the first bit is the most significant bit of the byte.[53]

// Pre-processing: padding with zeros
append "0" bit until message length in bits ≡ 448 (mod 512)

// Notice: the two padding steps above are implemented in a simpler way
 //  in implementations that only work with complete bytes: append 0x80
 //  and pad with 0x00 bytes so that the message length in bytes ≡ 56 (mod 64).

append original length in bits mod 2^64 to message
```

-> 패딩 과정은 블록 암호의 패딩 과정과 비슷

-> 메시지의 길이가 블록 단위의 배수가 되게 설정

-> MD5의 경우, 64바이트(512비트)의 배수가 되게 패딩을 진행

\- 패딩 시 추가되는 비트 혹은 바이트들은 기존 메시지의 길이에만 따라 달라지고, 기존 메시지의 내용과는 전혀 무관

&#x20;

프로세스

```
// Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message do
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
    // Initialize hash value for this chunk:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
    // Main loop:
    for i from 0 to 63 do
        var int F, g
        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31 then
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47 then
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63 then
            F := C xor (B or (not D))
            g := (7×i) mod 16
        // Be wary of the below definitions of a,b,c,d
        F := F + A + K[i] + M[g]  // M[g] must be a 32-bit block
        A := D
        D := C
        C := B
        B := B + leftrotate(F, s[i])
    end for
    // Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for
```

-> 이 과정은 Merkie-Damgard 구조 그림에서의 f에 해당

-> 총 128비트의 state, 512비트의 block을 이용해서 새로운 128비트의 state를 생성하고, 그 과정을 모든 512비트의 block에 대해 반복함

&#x20;

해시값 생성

```
var char digest[16] := a0 append b0 append c0 append d0 // (Output is in little-endian)
```

-> state를 구성하는 4개의 32비트 값으로부터 해시값 생성

-> 살펴보면 state로부터 해시값이 생성되는 과정에서 비트 손실이 하나도 없으므로, Length Extension Attack에 적합함

\+ 4개의 값을 little-endian으로 이어붙이기 때문에 역연산 또한 간단함

&#x20;

```
#md5.py
import math

rotate_by = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
             5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20,
             4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
             6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]


constants = [int(abs(math.sin(i+1)) * 4294967296) & 0xFFFFFFFF for i in range(64)]

initial_state = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]


def pad(msg):
    msg_len_in_bits = (8*len(msg)) & 0xffffffffffffffff
    msg += bytes([0x80])

    while len(msg)%64 != 56:
        msg += bytes([0])

    msg += msg_len_in_bits.to_bytes(8, byteorder='little')
    
    return msg


def process(state, block):
    A, B, C, D = state

    for i in range(64):
        if i < 16:
            func = lambda b, c, d: (b & c) | (~b & d)
            index_func = lambda i: i

        elif i >= 16 and i < 32:
            func = lambda b, c, d: (d & b) | (~d & c)
            index_func = lambda i: (5*i + 1)%16

        elif i >= 32 and i < 48:
            func = lambda b, c, d: b ^ c ^ d
            index_func = lambda i: (3*i + 5)%16
        
        elif i >= 48 and i < 64:
            func = lambda b, c, d: c ^ (b | ~d)
            index_func = lambda i: (7*i)%16

        F = func(B, C, D)
        G = index_func(i)

        to_rotate = (A + F + constants[i] + int.from_bytes(block[4*G : 4*G + 4], byteorder='little')) & 0xFFFFFFFF
        newB = (B + (to_rotate << rotate_by[i] | to_rotate >> (32-rotate_by[i]))) & 0xFFFFFFFF
            
        A, B, C, D = D, newB, B, C

    for i, val in enumerate([A, B, C, D]):
        state[i] += val
        state[i] &= 0xFFFFFFFF

    return state


def state2digest(state):
    digest = b""

    for i in range(4):
        digest += state[i].to_bytes(4, byteorder='little')

    return digest


def md5(msg):
    # 1. Padding
    msg = pad(msg)
    assert len(msg) % 64 == 0


    # 2. Process
    state = initial_state[:]
    blocks = [msg[i:i + 64] for i in range(0, len(msg), 64)]

    for block in blocks:
        state = process(state, block)


    # 3. Finalization
    return state2digest(state)


if __name__ == '__main__':
    import os
    import hashlib

    for _ in range(100):
        msg = os.urandom(1337)
        assert hashlib.md5(msg).digest() == md5(msg)
```

&#x20;

익스플로잇

Length extension attack

from md5 import \* 으로 앞서 작성한 md5.py를 임포트함.

```
def digest2state(digest):
    return [int.from_bytes(digest[i:i + 4], byteorder='little') for i in range(0, 16, 4)]

def split_block(msg):
    assert len(msg) % 64 == 0
    return [msg[i:i + 64] for i in range(0, len(msg), 64)]
```

-> digest2state 함수는 16바이트 해시값으로부터 state 복구

-> split\_block 함수는 패딩이 완료되어 길이가 64 바이트의 배수인 바이트 나열을 64 바이트 크기의 블록으로 나누어주는 함수

&#x20;

b"Dreamhack"과 Padding 1을 합친 문자열을 M2로 설정

<figure><img src="https://blog.kakaocdn.net/dna/NKUmb/btsNi57PNsl/AAAAAAAAAAAAAAAAAAAAAN_RSTZ934JqMf4xUe-DB8HucHB87BsxgmrgzfMvgzEu/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&#x26;expires=1782831599&#x26;allow_ip=&#x26;allow_referer=&#x26;signature=OfLkb063WDTJvcGGIepQGc2cA2Y%3D" alt="" height="176" width="541"><figcaption></figcaption></figure>

-> Padding 2에 해당하는 한 64바이트 블록만을 기존 해시로부터 복구된 state에 업데이트해준 후, 해시를 생성하면 원하는 해시값을 구함

```
from pwn import *
from md5 import *

def digest2state(digest):
    return [int.from_bytes(digest[i:i + 4], byteorder='little') for i in range(0, 16, 4)]

def split_block(msg):
    assert len(msg) % 64 == 0
    return [msg[i:i + 64] for i in range(0, len(msg), 64)]

io = remote("host3.dreamhack.games", 23854)

m1 = b"Dreamhack"
io.recvuntil(b"= ")
h1 = bytes.fromhex(io.recvline()[:-1].decode())

msg1 = bytes(500) + m1
padding1 = pad(msg1)[len(msg1):]
# M      = m1                             : 9 bytes
# msg1   = K + m1                         : 509 bytes
# blocks = split_block(K + m1 + padding1) : 576 = 64 * 9 bytes
# padding1                                : 67 bytes

msg2 = pad(msg1)
padding2 = pad(msg2)[len(msg2):]
# M      = m1 + padding1                             : 76 bytes
# msg2   = K + m1 + padding1                         : 576 bytes
# blocks = split_block(K + m1 + padding1 + padding2) : 640 = 64 * 10 bytes
# padding2                                           : 64 = 64 * 1 bytes

blocks = split_block(padding2)

state = digest2state(h1)
for block in blocks:
    state = process(state, block)

h2 = state2digest(state)

io.sendlineafter(b": ", (m1 + padding1).hex().encode())
io.sendlineafter(b": ", h2.hex().encode())

io.interactive()
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-textbook-hmac.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.