해시 함수 (Hash Functions)
기본 개념:
- 해시 함수 H는 임의 길이의 메시지 M을 받아 고정된 길이의 해시 값 h = H(M)을 반환.
- 주 목적은 데이터 무결성을 보장하는것
암호학적 해시 함수가 만족해야 할 두 가지 조건:
- (a) 일방향성(one-way property):
- 주어진 해시 값 h로부터 원래 데이터 M을 거꾸로 찾는 것이 불가능해야 함.
- (b) 충돌 회피성(collision-free property):
- 서로 다른 두 입력(M1 ≠ M2)이 같은 해시값을 만들어내지 않아야 함.
11.1 – 암호학적 해시 함수
- 데이터를 고기 분쇄기처럼 가공하는 비유.
- 입력: 메시지 M (가변 길이)
- 처리: 해시 함수 H를 통과
- 출력: 고정 길이의 해시값 h
- P, L은 패딩 및 길이 정보를 나타냄
11.2 – 해시 함수에 대한 공격 예시
(a) 정상 통신:
- Alice는 메시지 M을 해시 함수 H에 넣어 해시값 h를 만든다.
- 그리고 M과 h를 Bob에게 함께 전송.
- Bob은 받은 M에 대해 자신도 같은 해시 함수 H를 적용해 해시값 h'를 계산한다.
- 그리고 Alice가 보낸 h와 Bob이 계산한 h'를 비교해서 일치하면 메시지가 변조되지 않았음을 확인.
(b) 중간자 공격(Mitm):
- Darth(공격자)가 메시지를 가로채서 내용을 수정하고 해시값도 다시 계산하여 Bob에게 보냄.
- 암호학적 해시 함수만 사용하면 공격자가 이런 식으로 속일 수 있음 -> MAC이나 디지털 서명이 필요함
메시지 인증 코드 (MAC)
🔸정의
- MAC은 비밀 키를 사용하는 해시 함수(keyed hash function) 다.
- 두 당사자가 공유하는 비밀 키(secret key)와 메시지를 입력으로 받아, 메시지 무결성과 출처를 검증할 수 있는 고정 길이의 인증 코드(MAC 값)를 생성한다.
🔸작동 원리
- 송신자는 메시지 M과 비밀 키 K를 이용해 MAC 값을 생성한다: MAC = MAC(K, M)
- 송신자는 메시지 M과 MAC을 함께 수신자에게 전송한다.
- 수신자는 수신한 메시지 M과 자신이 알고 있는 비밀 키 K로 MAC 값을 다시 계산: MAC' = MAC(K, M)
- 수신된 MAC과 계산된 MAC이 일치하면 메시지 무결성과 송신자의 인증이 확인된다.
🔸특징 및 장점
- 무결성 보장: 메시지가 전송 중 변경되면 MAC 값이 달라져 즉시 검출 가능
- 인증 기능: MAC을 생성하는데 비밀 키를 사용하므로, 키를 모르는 공격자는 정상 MAC 생성 불가
- 키 공유 필요: MAC을 생성하고 검증하려면 송신자와 수신자가 같은 비밀 키를 공유해야 함
- 성능 우수: 일반 해시 함수 기반이어서 빠른 연산 가능
🔸차이점: MAC vs 암호학적 해시 함수
- 암호학적 해시 함수는 그냥 메시지 하나만 해시해서 무결성을 확인하는 데 쓰이고,
- MAC은 거기에 비밀 키를 같이 써서 메시지 무결성뿐 아니라 메시지를 보낸 사람 인증(출처 확인)까지 할 수 있다는 점이 다르다. ⇒ 무결성 + 인증
디지털 서명 (Digital Signature)
특징:
- 메시지 해시값을 개인 키로 암호화해서 서명 생성
- 검증자는 공개 키로 서명을 해독하고, 메시지를 다시 해시한 값과 비교
-> 누구나 송신자의 공개키로 서명을 검증할 수 있음 - 동작 원리는 MAC과 유사
- 공격자가 메시지를 변경하려면 사용자의 개인키를 알아야 한다.
장점:
- 무결성 보장: 메시지 변조 시 서명 검증 실패
- 송신자 인증: 개인키 없이는 서명 생성 불가
- 부인 방지: 송신자가 서명을 부인하기 어려움
11.4 – 디지털 서명 예시
- (a): 간단한 서명 과정
- Source A가 메시지 M의 해시값을 개인키로 암호화 -> M과 함께 전송
- Destination B는 공개키로 해독 후, 직접 계산한 해시와 비교
- (b): 인증 기관(CA)이 포함된 보다 복잡한 과정
- 메시지와 함께 인증서나 토큰 등도 같이 암호화/전송 -> 인증 강화
해시 함수의 기타 활용
3. 패스워드 보호:
- 사용자 비밀번호 -> 해시값 저장 -> 로그인 시 비교
- 원본 비밀번호 자체는 저장하지 않음 -> 보안 강화
4. 악성코드 탐지: 파일 해시값을 저장하고, 훗날 동일한 해시값이 유지되는지 확인 -> 변경 탐지
5. 의사난수 생성(PRF, PRNG): 대칭키 생성 등에서 활용
두 가지 연산을 조합한 해시함수
🔸 두 가지 방식의 차이:
- 기본 XOR 해시 방식
-> 각 블록의 비트를 단순히 XOR하여 해시 값을 생성 - XOR + 회전 방식
-> 입력의 규칙성 제거에 효과적
-> XOR 처리 후 결과를 1비트 회전(보통 왼쪽으로)하여 무작위성을 높임
⇒ 이 방식들은 안전하지 않지만 해시 구조를 이해하는 연습으로 좋음
그림 11.5 – 단순 해시 함수 시각화
- 블록을 순서대로 XOR하며 진행
- 왼쪽으로 비트 순환 -> 규칙성 제거 효과
보안 요건 (Requirements and Security)
Preimage (역상):
- 어떤 해시값 h에 대해 그것을 만들어낸 입력값 x를 찾는 문제
- 해시 함수는 여러 입력이 같은 출력을 가질 수 있음(다대일 함수)
Collision (충돌):
- x ≠ y인데 H(x) = H(y)인 경우 발생
- 충돌은 해시 함수의 무결성을 해치므로 반드시 피해야 함
암호학적 해시 함수의 요구사항
| 요구사항 | 설명 |
| Variable input size | 어떤 길이의 입력에도 적용 가능해야 함. |
| Fixed output size | 항상 고정된 길이의 출력값 생성. |
| Efficiency | 계산이 효율적이어야 하며, 하드웨어/소프트웨어 모두에서 실용적이어야 함. |
| Preimage resistance | 주어진 해시값 h에 대해, 그 값을 만들 수 있는 입력 x를 찾는 것이 계산적으로 불가능해야 함. |
| Second preimage resistance | 주어진 입력 x와 같은 해시값을 가지는 x' ≠ x를 찾는 것이 어려워야 함. |
| Collision resistance | H(x) = H(y)이면서 x ≠ y인 두 입력을 찾는 것이 불가능해야 함. |
| Pseudorandomness | 출력이 충분히 무작위적 특성을 가져야 함. |
헷갈리는 개념 3종 비교 (보완 추가 포함)
| 속성 | 주어진 것 | 목표 | 설명 (공격 시나리오) | 관련된 보안 성질 |
| Preimage resistance | 해시값 h | x such that H(x) = h | 해커가 해시값만 보고 원래 입력을 추정하려는 역방향 공격을 방지 | 일방향성 보장 |
| Second preimage resistance | 입력값 x | x' ≠ x such that H(x') = H(x) | 기존 입력과 해시가 동일한 다른 입력을 만들어 서명 등 인증 정보를 도용하려는 공격 방지 | 위조 방지 (충돌 회피성) |
| Collision resistance | 없음 (해시 함수만 알고 있음) | x ≠ y such that H(x) = H(y) | 해시 함수 구조의 약점을 이용해 충돌 쌍을 만들어 해시 기반 시스템의 신뢰성을 무너뜨리려는 공격 방지 | 해시 함수의 신뢰성 보장 |
💬 추가 설명 메모
- Second preimage의 진짜 의미:→ x′ ≠ x를 만들어 H(x′) = H(x)가 되도록 하면, 서명을 위조문서에도 그대로 재사용 가능.
- 해커는 x를 알고 있고, 그에 대한 서명 S도 갖고 있음.
- 왜 난이도가 다르냐?
- Preimage는 정해진 h에 도달해야 하므로 완전한 역추적
- Collision은 시작점이 자유로워서 생일 역설로 인해 확률적 약점 존재
해시 함수에 대한 공격
🔹 Brute-force Attack
- 알고리즘이 아니라 비트 길이에만 의존.
- 가능한 값을 하나씩 시도하며 충돌(collision)을 찾는 방식.
🔹 Cryptanalysis
- 알고리즘의 구조적 약점을 파고들어 효율적으로 공격.
- 무차별 대입이 아닌, 논리적 취약점 활용.
충돌 저항성 공격
- Brute-force의 일종
- 공격자는 서로 다른 두 입력 x ≠ y에 대해 H(x) = H(y)를 찾으려 함.
- 이 과정을 생일 역설(Birthday Paradox)를 이용해 효율적으로 수행.
🔹공격 시나리오:
- A는 x에 서명할 준비.
- B는 x의 의미가 같은 다양한 변형 x'를 만들어 (x', H(x')) 저장.
- B는 위조 메시지 y 생성.
- y와 비슷한 변형 y'를 만들어 해시값 비교 -> H(y') = H(x') 찾음.
- A의 서명을 훔쳐 Sign(H(x')) -> Sign(H(y'))로 바꿔 사용 가능.
2^38 변형을 가진 편지
- 동일 의미의 편지를 구성할 수 있는 단어 선택의 조합을 보여주는 예시.
- 이처럼 해시 충돌을 일으킬 수 있는 수많은 변형이 존재한다는 점을 강조.
Secure Hash Code 구조
🔹 Secure Hash 구조란?
전통적인 블록 기반 해시 함수의 일반적인 틀이며, 대표적으로 SHA-1, SHA-2, MD5 같은 해시 함수들이 이 구조를 따른다.
- 입력 메시지를 블록 단위로 분할
- 각 블록: Y₀, Y₁, ..., Yₙ
- 각 블록은 b비트
- 초기 값(IV)을 설정하고, 블록마다 이전 출력(CV)을 다음 입력과 함께 압축 함수 f에 넣음
- 마지막 출력이 해시값이 됨
→ 즉, 그림에서 보는 구조는 일반적인 SHA-1, SHA-2 같은 해시 함수에서 사용하는 기본 원리
🔹 개념정리
- 해시 함수(H)
전체 메시지를 받아 고정된 크기의 해시값을 출력하는 함수
예: SHA-1, SHA-256, SHA-3 등 - 압축 함수(f)
해시 함수 내부에서 사용하는 기초 블록 처리 함수 두 입력(보통 이전 해시값 + 메시지 블록)을 받아 고정된 크기의 출력값을 만들어냄
→ 보통: f(CVᵢ, Yᵢ) = CVᵢ₊₁
SHA (Secure Hash Algorithm) 시리즈
🔹 SHA-1:
- 1993년 NIST에서 표준화 (FIPS 180)
- 160비트 해시값 출력
- 2017년, Google이 충돌 시연 -> 보안 취약 판명
🔹 SHA-2:
- 2002년 발표된 개정판
- SHA-256, SHA-384, SHA-512로 나뉨
- 여전히 널리 사용
🔹 SHA-3:
- SHA-2와 다른 구조 (스펀지 구조) 사용
- 2015년 NIST에 의해 표준화 (FIPS PUB 202)
- Keccak 알고리즘에서 파생
SHA-3 매개변수
| 해시 길이 | 블록 크기 r | 용량 c | 라운드 수 | 충돌 저항성 | 2차 프리이미지 저항성 |
| 224 | 1152 | 448 | 24 | 2112 | 2224 |
| 256 | 1088 | 512 | 24 | 2128 | 2256 |
| 384 | 832 | 768 | 24 | 2192 | 2384 |
| 512 | 576 | 1024 | 24 | 2256 | 2512 |
스펀지 구조 (Sponge Construction) – SHA-3 내부 구조
🔸 구조 핵심 요약: Sponge Construction (SHA-3 내부 구조)
- Sponge 구조는 내부 상태 전체를 r 비트(rate) + c 비트(capacity)로 나눔.
- 전체 상태 b = r + c는 f 함수의 입력 및 출력 크기이며, 예: SHA-3에서는 1600비트.
🔹 Absorbing Phase (입력 단계):
-> 위의 Secure Hash 구조와 같다
- 메시지를 패딩한 뒤, r비트씩 잘라 내부 상태의 앞부분과 XOR.
- 이후 전체 상태(r + c)에 대해 f 함수 반복 적용.
- c 영역은 XOR에는 사용되지 않지만, f 함수로 인해 계속 섞이며 보안성 유지에 핵심적인 역할을 함.
[ Internal state ] ← f 함수 입력 (b = r + c)
| r bits | c bits |
|==========|==========|
↑ 입력 블록 XOR됨
🔹 Squeezing Phase (출력 단계):
- 내부 상태(r + c)가 준비되면, f 함수 적용 후
- 출력으로 사용할 앞쪽 r비트만 잘라냄 -> 이게 출력 블록 Z₀
- Z는 내부 상태에서 잘라낸 출력일 뿐, 다시 f 함수에 사용되지는 않는다. 내부 상태 전체가 f 함수의 입력으로 유지되며, 출력이 필요할 때만 앞 r비트를 잘라낸다.
- 이렇게 매번 새로운 상태를 만들어, 다시 앞 r비트를 잘라냄 → Z₁, Z₂, ...
[ Internal state ] ← f 결과 (b = r + c)
| r bits | c bits |
|==========|==========|
↑
│
└── 잘라냄 → Z₀ (출력용, 내부 상태와 독립)
[ Internal state ] ← f(state)
| r bits | c bits |
|==========|==========|
↑
└── 잘라냄 → Z₁
...
📌 Z₀, Z₁ 등은 단지 내부 상태에서 추출한 결과값일 뿐이며, 내부 계산에는 전혀 영향을 주지 않음.
🔸 왜 Sponge 구조는 "출력 확장 가능(XOF)"한가?
- 전통적인 해시 함수 (예: SHA-256) -> 출력 길이가 고정됨 (항상 256비트 등)
- 하지만 Sponge 구조는:
- 내부 상태 크기 b = r + c는 고정되지만,
- 내부 상태에서 r비트씩 잘라내는 방식으로 출력함
- 필요하면 f를 반복 호출하여 출력을 계속 이어붙일 수 있음
- 따라서 출력 길이를 사용자가 원하는 만큼 확장 가능
📌 Z₀, Z₁ 등은 단지 내부 상태에서 추출한 결과값일 뿐이며, 내부 계산에는 전혀 영향을 주지 않음.
대표 예시:
- SHAKE128, SHAKE256→ 출력은 사용자가 원하는 만큼 비트 수를 지정해서 받음 (예: 512비트, 1024비트 등)
-> 입력은 일반 해시처럼 받지만
출력 Z = Z₀ || Z₁ || Z₂ || ... (필요한 만큼 이어붙여 사용)
✅ 요약:
| 구성 요소 | 역할 |
| r 비트 | 출력에 사용되는 부분 (공개 영역) |
| c 비트 | 내부 보안 유지용 (비공개 영역) |
| f 함수 | 전체 상태(r + c)를 섞는 함수 |
| Z₀, Z₁ | f 결과 상태에서 잘라낸 출력 (계산에는 사용되지 않음) |
| XOF | 원하는 길이만큼 출력 생성 가능하게 하는 구조적 장점 |
SHA-3의 스텝 함수
| 함수 | 유형 | 설명 |
| θ (theta) | Substitution | 각 비트는 같은 열의 이전 및 다음 라운드의 값에 따라 변경됨 |
| ρ (rho) | Permutation | 각 워드의 비트를 원형 이동(circular shift) |
| π (pi) | Permutation | 워드들을 5x5 행렬 형태로 재배치 |
| χ (chi) | Substitution | 워드 내에서 특정 규칙으로 비트 변경 |
| ι (iota) | Substitution | W[0][0]을 라운드 상수와 XOR |
'컴퓨터 보안' 카테고리의 다른 글
| 9장-공개키 암호 & RSA (0) | 2025.05.13 |
|---|---|
| 12장-MAC (0) | 2025.05.11 |
| 8장-난수와 스트림암호 (0) | 2025.04.22 |
| 7장-Block Cipher Operation (0) | 2025.04.22 |
| 6장-AES (0) | 2025.04.22 |