[SISS/암호학 스터디] 여름 8주차 스터디

[SISS/암호학 스터디] 여름 8주차 스터디 - 해시

24-여름 SISS/암호학 2024. 8. 19. 20:30

: 8주차 08/19 ~ 08/25 해시

해시

해시 함수 → 임의 크기의 입력으로 고정된 크기의 데이터(해시값)를 반환하는 함수
- 암호학적 해시 함수
  - 성질
    1. 제 1 역상 저항성(Preimage resistance) → H(x) = y를 만족하는 x를 찾는 것이 어려움(일방향 함수)
    2. 제 2 역상 저항성(Second preimage resistance) → ”x가 주어졌을 때” x ≠ x′이면서 H(x) = H(x′)을 만족하는 x′을 찾는 것이 어려움
    3. 충돌 저항성(Collision resistance) → x ≠ x′이면서 H(x) = H(x′)을 만족하는 x′을 찾는 것이 어려움
    - 눈사태 효과 또한 중요해지고 있음 (입력의 작은 변화가 해시값을 크게 바꾸는 것)
  - 생일 역설 → 한 반에 생일이 같은 학생이 있을 확률이 높음(비둘기집 원리) → 공역의 크기가 작으면 해시값 충돌이 발생할 확률이 높음
  - 암호학적 해시 함수의 사용 → 통신의 무결성 증명

해시함수의 종류 → 파이썬의 hashlib 모듈에 다양한 해시 함수가 구현되어있음
- MD5 → (Ronald Lorin Rivest) 입력을 512비트 단위로 쪼개 128비트의 해시값을 생성
- SHA-2 → (미국 국립표준기술연구소) Merkle-Damgård 구조로 구현됨 → SHA-256은 SHA2 중 하나로 256비트의 해시값을 생성
- SHA-3 → (공모) Keccak 알고리즘 기반(스펀지 구조)

# MD5

import hashlib

print(hashlib.md5(b'dreamhack').hexdigest()) # 298d75fe864c08e3a68dd1da1483654d print(hashlib.md5(b'dreamhacc').hexdigest()) # 02ac31c7f653161b28554a383ba36bae

# MD5 hash of file

with open('/path/to/file', 'rb') as f:

print(hashlib.md5(f.read()).hexdigest())

# SHA-2

import hashlib

print(hashlib.sha256(b'theori').hexdigest()) # 51a8e7115164399085a3650f3d6e9c00cbb59afea7689918a27c8294abcb8d57

print(hashlib.sha256(b'theorr').hexdigest()) # acd88112d4c87351e193cfd425cf7f01925ea15b9c03b7be03ad1343c8f13f70

# SHA256 hash of file

with open('/path/to/file', 'rb') as f:

print(hashlib.sha256(f.read()).hexdigest())

# SHA-3

from Crypto.Hash import keccak

def keccak256(msg):

k = keccak.new(digest_bits=256)

k.update(msg)

return k.digest()

print(keccak256(b'theori').hex()) # 3222d0f9a6e666a31aabe1d33572ed466e0786336e9a6de1955f86da3ffceaef print(keccak256(b'theorr').hex()) # 97e6def96cb732d9a8fa68078ff9da1f359500d56de6488dd0d96fee23e16ea7

# Keccak256 hash of file

with open('/path/to/file', 'rb') as f:

print(keccak256(f.read()).hex())

메시지 인증 코드(MAC)

MAC
- 데이터와 함께 보내 무결성과 통신 상대 확인을 위해 사용 (메시지 위조 시 MAC도 함께 변경해야하므로)
- 메시지와 키를 통해 계산한 MAC 값을 메시지 전송 시 함께 송신

HMAC

해시 함수를 기반으로 한 MAC
키의 길이, 블록의 길이를 인자로 하여 복잡함

#!/usr/bin/env python3
# Name: hmac.py

import hashlib, hmac

# key : b'secret', msg : b'hello world'
h = hmac.new(b'secret', b'hello world', hashlib.sha256).hexdigest() 
print(h) # 734cc62f32841568f45715aeb9f4d7891324e6d948e4c6c60c0621cdac48623a

공격 방법

Merkle–Damgård 구조
- 해시 생성 단계
  1. 각 해시 함수에 따라 블록 사이즈의 배수가 되도록 메시지를 패딩
  2. 메시지를 블록으로 나눔
  3. 초기 벡터를 state로 하여 순차적으로 state를 업데이트(각 해시 별 고유 초기 벡터가 있음)
  4. 마지막 state에서 해시값 추출Merkle–Damgård 구조

해시 함수 별 특징

해시 종류	state의 비트 수	해시값의 비트 수	손실된 비트
MD5	128	128	0 (취약)
SHA-224 (SHA-2)	256	224	32 (취약)
SHA-256 (SHA-2)	256	256	0 (취약)
SHA-384 (SHA-2)	512	384	128
SHA-512 (SHA-2)	512	512	0 (취약)

Length extension attack → Merkle–Damgård 구조를 사용하는 HMAC을 공격
- H(K || *M_*1)의 연산값을 알 경우 K || *M_*1으로 해시를 생성하였을 때의 최종 state 복구 가능
- 복구한 state를 IV로 설정하여 X에 대한 해시값을 구하면 H(K || *M_*1 || X)를 알 수 있음
- 따라서 *M_*2가 *M_*1 || X의 꼴(*M_*1의 뒤에 값이 이어짐)일 경우 K를 몰라도 H(K || *M_*2)의 값을 구해 올바른 HMAC을 생성할 수 있음

실습 - 생일 역설

공역의 제곱근만큼의 연산을 통해 충돌 쌍을 찾을 수 있음
chall.py → 서로 다른 두 메시지 입력으로 같은 해시값을 구하면 플래그 획득 → (birthday_hash) SHA-256의 중간 5바이트를 해시값으로 리턴

import hashlib

def birthday_hash(msg):
    return hashlib.sha256(msg).digest()[12:17]

msg1 = bytes.fromhex(input("Input message 1 in hex: "))
msg2 = bytes.fromhex(input("Input message 2 in hex: "))

if msg1 == msg2:
    print("Those two messages are the same! >:(")

elif birthday_hash(msg1) != birthday_hash(msg2):
    print("Those two messages don't have the same birthday! T.T")

else:
    print("Finally! They have the same birthday ^o^")
    print(open("flag.txt").read())

exploit.py
- 생일 역설과 충돌 → 공역의 원소 수가 N일 때 K개의 서로 다른 메시지의 해시값이 전부 다를 확률은 {N×(N−1)×⋯×(N−K+1)} / {N×N×⋯×N} → K가 N보다 작고 N의이 매우 크면 1 / e^(K^2/2N)로 수렴 → ∴ K개의 표본에 충돌쌍이 존재할 확률은 1− 1 / e^(K^2/2N)
  - 충돌쌍 확인 코드는 아래 참고
- set → 파이썬의 set은 해시 테이블을 이용하여 삽입 및 탐색에 드는 시간이 짧음(O(n))

# 충돌쌍 확인 코드

import math

def prob(N, K):
    res = 1
    for i in range(K):
        res *= (N - i) / N
    return 1 - res

N_candidates = [25, 100, 10000, 1000000, 100000000]

for N in N_candidates:
    print(f"K = sqrt(N): Collision ={prob(N, math.isqrt(N)) * 100 : .3f}% for {N = }")
print()
for N in N_candidates:
    print(f"K = 2 * sqrt(N): Collision ={prob(N, 2 * math.isqrt(N)) * 100 : .3f}% for {N = }")

import hashlib
from tqdm import trange

def birthday_hash(msg):
    return hashlib.sha256(msg).digest()[12:17]

hash_list = []
hash_set = set()

for i in trange(2**21):
    msg = str(i).encode()
    result = birthday_hash(msg)

    if result in hash_set:
        msg1 = msg
        msg2 = str(hash_list.index(result)).encode()

        break

    hash_list.append(result)
    hash_set.add(result)

assert birthday_hash(msg1) == birthday_hash(msg2)

from pwn import *

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

io.sendlineafter(b": ", bytes.hex(msg1).encode())
io.sendlineafter(b": ", bytes.hex(msg2).encode())

io.interactive()

실습 - Length Extention Attack

chall.py → (HMAC) MD5 해시 함시를 이용해 (K(랜덤 상수) + M)을 반환 → M = b”Dreamhack”의 HMAC을 통해 다른 입력의 HMAC을 구하면 문제 해결

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 수도코드(위키피디아 / 아래 코드 참조)
  1. 상수 설정
  2. 패딩
  3. 반복하여 모든 블록에 대해 state 생성 및 갱신
  4. 해시값 생성
- 새로운 해시값을 구하는 과정 → HMAC(K + b"Dreamhack")의 해시값을 state로 변환한 것은 K + b"Dreamhack" + 패딩 의 state → b"Dreamhack" + 패딩 (+ 기타 내용)을 메시지로 사용할 경우, (state를 아는 블록 + 추가 블록)이 되므로 K를 몰라도 새로운 해시값을 구할 수 있음
- MD5 파이썬(아래 코드 참조)

# MD5 수도코드
// : 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(232 × 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 264 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)

# MD5 파이썬
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)

exploit.py → md5.py를 임포트
- (digest2state) 해시값으로부터 state 복구
- (split_block) 패딩 추가된 입력을 블록으로 나눔(64바이트)
- (M2) b"Dreamhack"과 Padding 1을 합친 문자열

# exploit.py

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", 13667)

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

Length Extention Attack 실습 풀이 과정 및 출력 화면

저작자표시

'24-여름 SISS > 암호학' 카테고리의 다른 글

[SISS/암호학 스터디] 여름 9주차 스터디 - 전자 서명 (0)	2024.08.24
[SISS/암호학 스터디] 여름 7주차 스터디 - 디피헬만 키 교환 (0)	2024.08.16
[SISS/암호학 스터디] 여름 6주차 스터디 - RSA (0)	2024.08.08

ABOUT ME

블로그 블로그

해시

메시지 인증 코드(MAC)

공격 방법

실습 - 생일 역설

실습 - Length Extention Attack

'24-여름 SISS > 암호학' 카테고리의 다른 글

티스토리툴바

ABOUT ME

해시

메시지 인증 코드(MAC)

공격 방법

실습 - 생일 역설

실습 - Length Extention Attack

'24-여름 SISS > 암호학' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바