1. 일방향 해시함수
임의 길이 메시지를 입력으로 고정된 길이의 해시값을 출력하는 다대일 대응 함수
1-1. 특징
- 고속으로 고정 길이 해시값 계산
- 일방향성을 가져 역산 불가
- 메시지가 다르면 해시값도 다름 (충돌 내성)
1-2. 보안 요구사항
| 해시함수 | 전자서명 | 설명 |
| 프리이미지 저항성 (역상 저항성) |
약 일방향성 | $y$가 주어졌을 때, $y = h(x)$를 만족하는 $x$를 찾는 건 불가능해야 함 |
| 제2프리이미지 저항성 (두 번째 역상 저항성, 약한 충돌 내성) |
강 일방향성 | $x$가 주어졌을 때 $h(x) = h(x^{'})$를 만족하는 $x^{'}$를 찾는 건 불가능해야 함 |
| 충돌 저항성 (충돌 회피성, 강한 충돌 내성) |
충돌 회피성 | $h(x) = h(x^{'})$를 만족하는 $x, x^{'}$를 찾는 건 불가능해야 함 충돌 저항성은 두 번째 역상 저항성을 보장함 |
1-3. 해시함수의 분류
- 반복 해시함수
- 고정 길이 입력을 받는 함수를 반복함
- Merkle-Damgard 구조는 압축함수가 충돌 내성을 갖는 해시함수
- 키가 없는 해시함수
- 블록 암호 기반: 압축함수 자리에 대칭키 블록암호
- 모듈 연산 기반: 속도가 빠르지 않아 많이 사용되지 않음
- 전용 해시함수 (SHA-1, RIPEMD, LSH, Tiger, HAVAL)
- MD (MD2, MD4, MD5): MD5는 입력을 512-bit 블록으로 나누고 128-bit MD를 출력하지만 너무 짧고 약점이 발견됨
- SHA: NIST에 의해 배포되어 가장 널리 사용됨. 현재는 SHA-3(Keccak) 표준화
- RIPEMD-160: 160-bit Hash를 생성, 비트코인에서 사용
- HAVAL: 가변 길이 해시함수
- 키를 사용하는 해시함수
- 메시지 인증 기능을 가짐
- 블록 암호 기반: CBC-MAC이 대표적, DES를 CBC 모드에서 사용
1-4. 암호학적 응용
- 메시지 무결성 점검, 소프트웨어 변경 검출
- 메시지 인증 코드 (MAC): 키가 있는 해시함수로부터 얻어짐 (비밀키 공유해야 함)
- 전자서명
1-5. 랜덤 오라클 모델과 공격
- 랜덤 오라클 모델
- 해시함수의 이상적 수학 모델 (난수 스트링, 공식으로부터 독립적인 다이제스트)
- 비둘기집 원리
- 적어도 한 비둘기집에는 두 마리 비둘기가 있음, 즉 충돌은 필연적
- 생일 문제
- 해시값은 뭐든지 괜찮으며, 같은 해시값을 생성하는 2개의 메시지를 구함 (강한 충돌 내성을 공격)
- 생일 패러독스: 23명만 있으면 적어도 2명의 생일이 50% 이상의 확률로 일치함
- 랜덤 오라클 모델 공격
- 프리이미지, 제2프리이미지 저항성 강도: $2^{n}$
- 충돌 저항성: $2^{n/2}$
- 일방향 해시함수 공격
- 무차별 공격: 약한 충돌 내성을 깨는 공격
- 일치블록 연쇄공격: 새로운 메시지를 사전에 다양하게 생성
- 중간자 연쇄공격: 해시 중간 결과에 대한 충돌쌍을 찾음
- 고정점 연쇄공격: 연쇄변수 발생점은 중간에 삽입해도 해시값 변화 없음
- 차분 연쇄공격: 입출력 차이를 조사
1-6. 해결 불가능한 문제
- 조작과 변경(무결성)은 검출 가능
- 거짓행세(인증)은 검출 불가
- 인증코드와 전자서명 필요
2. 해시함수의 예
2-1. SHA-512
- 1024-bit의 다중 블록 메시지로부터 512-bit의 Hash 생성
- 메시지 길이 제한: $2^{128}$
- 길이 필드와 패딩
- 정수 길이 필드에는 패딩 전 원래 메시지 길이를 나타내며, 보안 요소로 작용
- 안전성: 이전 SHA들과 동일한 MD 기반 구조를 가지고 있어 우려가 있음 (지적된 약점은 없음)
2-2. SHA-3
- SHA-3의 최종후보로 KECCAK이 경쟁방식에 의해 표준화됨
- 공격 방법이 밝혀진 SHA-1의 대체
- 스펀지, 듀플렉스 구조 기반
3. 메시지 인증 코드 (MAC, Message Authentication Code)
3-1. 특징
- 무결성을 확인하고 거짓행세를 검출(인증)하는 기술
- 전자서명보다 빠름
- MDC vs MAC
- MDC (Modfication Detection Code): 단순 무결성을 보장하는 메시지 다이제스트
- MAC: 송수신자 사이의 비밀값이 포함되어 데이터 출원지를 인증
- 키를 공유해야 하므로 키 배송 문제가 발생
3-2. 구현 사례
- 축소 MAC (Nested MAC)
- 두 단계의 해시 과정을 거침 (첫 번째는 키+메시지, 두 번째는 키+해시)
- HMAC (Hash MAC)
- 일방향 해시함수로 MAC 구성
- TLS, IPSec, SET 등에 사용
- CBC-MAC, CMAC
- 대칭키 암호를 N번 사용해 하나의 MAC을 생성
- CBC-MAC에서 논점이 발견되어 수학적으로 더 안전한 CMAC이 만들어짐
- CCM (Counter with CBC-MAC)
- CTR과 CBC-MAC을 통합함
- AES 암호를 사용함
- 무선 보안에 사용
- GCM (Galois Counter Mode)
- CTR 모드에 인증 기능을 추가함
- CTR 모드가 암호문을 생성함과 동시에, 올바른 암호화를 거쳤다는 인증자를 만들어냄
3-3. MAC에 대한 공격
- MAC은 재전송 공격에 취약함
- 재전송 공격을 막는 방법
- 순서 번호: 마지막 순서번호를 기록해야 함
- 타임스탬프: 송수신자의 시계 동기화 요구됨
- 비표: 통신 때마다 변경되므로 통신량이 약간 증가
- 시도/응답 (Challenge/Response)
3-4. 해결할 수 없는 문제
- 제3자에 대한 증명: MAC을 계산한 건 자신이 아닌 상대방이라고 제3자에게 증명 불가
- 부인 방지: 송신자와 수신자 중 누구의 주장이 맞는지 판단 불가, 전자서명을 사용해야 함
