해시 함수, 공격, 응용, MAC

데이터(입력)를 비교적 작은 크기의 스트링(출력)으로 만드는 방법

- 해시 함수의 출력값은 입력 데이터의 디지털 지문(digital fingerprint)

 

성질

- 고정 길이의 출력

- 빠른 계산 속도

- 메시지 1비트만 달라도 해시 값이 완전히 다름

 

왜 쓰나?

- 메시지 무결성 제공 .. 원본 메시지가 변조되지 않음을 보장

 

메시지 변조 감지 코드 (MDC, Modification Detection Code)

- 암호학적으로 원본 메시지에 대응하는 메시지 변조 감지 코드를 생성하기 위한 방법으로 해시 함수 사용

- 클라우드 스토리지 예시 .. 클라우드에 저장된 자신의 데이터에 대한 무결성 검증을 위해 사용 가능

 

암호학적 해시 함수 (cryptographic hash function)

특정한 보안 성질들을 추가적으로 제공하는 해시함수

- 역상 저항성 (preimage resistance)

- 제 2 역상 저항성 (Second preimage resistance)

- 충돌 저항성 (Collision resistance)

 

역상 저항성

- 해시값 y가 주어졌을 때, h(M) = y를 만족하는 M을 찾는 것이 계산적으로 불가능하다는 성질 (일방향성)

 

제 2 역상 저항성

- 해시함수 h와 메시지 M이 주어졌을 때, h(M) = h(M')을 만족하는 M'(=/=M)를 찾는 것이 계산적으로 불가능하다는 성질

 

총돌 저항성

- 해시함수 h가 주어졌을 때, h(M) = h(M')을 만족하는 서로 다른 M과 M' 쌍을 찾는 것이 계산적으로 불가능하다는 성질

* (M, M')을 충돌쌍(collision pair)라고 함

---

SHA (Secure Hash Algorithm)

	출력 길이	메시지 길이 상한
SHA-1	160 bit	2^64 bit
SHA-256	256 bit	2^64 bit
SHA-384	384 bit	2^128 bit
SHA-512	512 bit	2^128 bit

...

사실상 SHA-256과 SHA-512만 존재

224는 256에서 32비트 버리고

384는 512에서 128비트 버리고 이런 식임

..

국내/외에서도 SHA 많이 표준으로 권고

---

해시 함수 공격

 

제 2 역상 저항성에 대한 공격

- 반드시 M에 대해 h(M) = h(M')을 만족하는 M' 존재

- 전수조사 공격(brute force attack)

현재 컴퓨팅 능력에서는 출력 길이가 n bit 이면 공격자는 2^n번 정도의 계산을 수행해야 함

.. n은 224 이상 권장

 

동일한 의미의 다양한 문장을 생성

=> 오리지널 해시 값과 동일한 값이 나올때까지 해야 함

 

충돌 저항성에 대한 공격

- h(x) = h(x')를 만족하는 서로 다른 x, x'을 찾는 것

- 제 2 역상 저항성과 달리 한쪽이 고정이 아님

- 생일문제와 동일 (23명 이상 모이면 같은 생일 나올 가능성 1/2 이상)

 

해시 함수도 2^(n/2)번의 입력값을 무작위로 뽑아서 해시값을 계산하면 충돌쌍을 찾을 수 있음

SHA-1: 해시값 길이 160비트.. => 2^80 연산 필요

---

해시 함수 응용

* 온라인 입찰

각 입찰자가 상호 입찰금이 비밀로 지켜지길 원함

=> 해시값을 온라인에 공개하고 이후 실제 입찰금 공개

- 해시값을 통해 입찰금을 알아낼 수 없음 -> 단방향성

- 해시값 공개 후 입찰금을 변경할 수 없음 -> 충돌 저항성

 

* 소프트웨어의 변경 검출

미러사이트에서 오리지널 사이트의 패치를 잘 업데이트 하고 있는지 확인하기 위해

오리지널 사이트에서 해시만 받아서 확인 가능함

---

메시지 인증 코드 (Message Authentication Code)

 

Vs. MDC (Modification Detection Code) .. 

- 해시 함수를 이용한 메시지 변조 감지 코드 -> 메시지 무결성

- MDC는 안전한(변조 불가능한) 채널로 전송해야 함

- 메시지가 누구로부터 전송된 것인지 확인 불가 .. 위장 공격(Impersonation attack) 가능

 

메시지 인증 코드

- 송신자와 수신자가 공유한 키를 사용 -> 메시지 인증

- MAC 전송을 위해 안전한 채널을 사용하지 않아도 됨

	변조 감지 코드 (MDC)	메시지 인증 코드 (MAC)
사전 키 공유	X	O
안전한 채널 사용	O	X
메시지 무결성	O	O
데이터 출원 인증	X	O
부인 방지	X	X

 

해시 함수 기반

- NMAC .. Nested MAC

- HMAC .. Hashed MAC

 

블록 암호 기반

- CBC-MAC .. Cipher  Block Chaining MAC

- CMAC .. Cipher-based MAC

 

메시지 인증 코드에 대한 공격

- 재전송 공격 (Replay Attack)

저장해둔 정당한 MAC 값을 반복해서 전송하는 방법

 

재전송 공격 방어 방법

- 순서 번호 (sequence number)

> 송신 메시지에 매회 1씩 증가하는 번호 붙이기

> 마지막 통신 시 순서 번호를 저장

 

- 타임스탬프 (timestamp)

> 송신 메시지에 현재 시각 넣기

> 송수신자 사이의 동기화 필요

 

- 비표 (nonce)

> 송신자에게 일회용의 랜덤한 값을 전송

> 메시지와 비표를 합해 MAC값 계산

> 비표 값은 통신 때마다 교체

 

 

MAC으로 해결할 수 없는 문제

제 3자에 대한 메시지 인증

- 키를 공유한 사람들만 메시지를 인증할 수 있으며, 제 3자는 검증 불가

 

부인 방지

- 송, 수신자 간 부인 방지는 막을 수 없음