해시함수 (Hash Function)

■ 해시함수

 - 임의의 입력 비트열에 대하여 일정한 길이의 안전한 출력 비트열을 내는 것, 즉 입력 데이터의 길이가 길든 짧은 해시 알고리즘을 사용하면 고정길이의 해시값을 출력한다

 - 정보통신 보호의 여러 메커니즘에서 활발히 이용되는 요소 기술

 - 비트코인 채굴 알고리즘에 사용되고 있음

 - 고정길이 해시값을 메시지 다이제스트(MD), 해시코드, Hash Value, File Finger Print라고도 함

 

 

■ 해시함수의 대표적 특징

 

 ① 압축 및 고정길이

   - 임의 크기의 메시지에 적용될 수 있어야 함

   - 어떤 길이의 메시지를 입력으로 주더라도 항상 짧은 고정길이의 해시값을 생성해야 함 

 ② 계산용이성 및 확장성

   - 다양한 응용에 적용하기 위해서는 해시값을 계산하는 데 너무 오랜 시간이 걸려서는 안 됨

   - 하드웨어 및 소프트웨어에 모두 실용적이어야 함

 ③ 일방향성 (one-wayness)

   - 일방향 해시함수(h())는 일방향성(one-way)을 가져야 함

   - 이것은 해시값(H)으로부터 메시지(M)를 역산할 수 없다는 성질

   - h(M)=H에서 해시값(H)을 이용하여 메시지(M)를 찾는 것이 계산적으로 어려워야 함

 ④ 메시지가 다르면 해시값도 다르다 (충돌저항성)

   - 무결성을 확인하기 위해 사용되며, 메시지(M)가 1비트라도 변하면 해시값(H)은 매우 높은 확률로 다른 값이 되어야 함

 

 

 

★ 해시함수의 보안 요구사항

 

1) 역상 저항성(프리 이미지 저항성, 약 일방향성(Weak onewayness)) : 역상 추측에 저항하는 성질

 - h(M)=H일 때 해시값(H)을 이용해 입력값(메시지(M))을 구하는 것은 어려움

 - 해시값(H)이 확인된 상태에서 입력값(메시지(M))을 구하는 것은 계산적으로 불가능하다는 성질

 - 프리 이미지 저항성은 일방향성임

 

2) 제2 역상 저항성(제2 프리 이미지 저항성(Second Pre-image Resistance), 약한 충돌내성, 강 일방향성(Strong onewayness)) : 역상추측에 저항하는 성질

 - h(M)=H일 때 h(M)=H' 이러한 현상이 발생하지 말아야 함

 - 동일한 입력값(메시지)에 대해 서로 다른 해시값이 나와서는 안됨

 - 최초, 입력값(M)이 확인된 상태에서 동일한 해시값(H)이 나오는 다른 입력값(M')을 찾는 것은 계산적으로 불가능해야 함

 

3) 충돌 저항성(강한 충돌내성, 충돌 회피성) : 서로 다른 입력값 추측에 저항하는 성질

 - 주어진 값이 없음

 - h(M)=H일 때 h(M') 이러한 현상이 발생하지 말아야 함

 - 같은 해시값(H)을 생성하는 임의의 서로 다른 두 개의 입력값(M, M')을 찾는 것이 어려워야 함

 - 최초 확인된 정보가 없는 상태에서 동일한 해시값(H)의 서로 다른 입력값(M, M')을 찾는 것은 계산적으로 불가능해야 함

 

 

□ 용어정리

 - 일방향 해시함수 = 메시지 다이제스트 함수 = 메시지 요약 함수 = 암호학적 해시함수

 - 입력되는 메시지 = 프리 이미지 (pre-image)

 - 출력되는 해시값 = 메시지 다이제스트 = 핑거프린트

 - 무결성 = 완전성 = 보전성

 - 제2 역상 저항성은 오늘 해시 돌린 것과 내일 해시 돌린 것이 차이가 나면 안 됨

 

□ 해시함수 테스트 사이트

www.convertstring.com/ko/Hash/SHA256

SHA256 해시 - 온라인 SHA256 해시 생성기

 

■ 해시함수의 종류

	MD5	SHA-1	RIPEMD-160	SHA-256	SHA-512	HAVAL
처리단위 (입력단위, bit)	512	512	512	512	1024	1024
단계수 (라운드, R)	64 (4R x16)	80 (4R x20)	160	80	80	3/4/5
출력길이 (다이제스트 길이, bit)	128	160	160	256	512	128, 160, 192, 224, 256
특징	취약점 발견	취약점 발견		SHA-2

* SHA (Secure Hash Algorithm) - SHA-1 (ver 1) / SHA-2 (ver 2) / SHA-3 (Ver 3)

 - 2005년에 SHA-1 (SHA ver 1)의 강한 충돌 저항성이 깨졌다는 것을 접수하고 NIST는 SHA-1 (Ver 1)을 대체하는 차세대 일방향 해시함수 SHA-3 (ver 3)을 제정하기로 하였음

 - SHA-3(Keccak)은 경쟁 방식으로 표준화 됨

 

* HAS-160 : MD5와 SHA-1의 장점을 결합한 한국 표준 해시함수, 입력단위 : 152 bit, 출력길이 : 160 bit

 

 

■ 해시함수 특징

 - 다양한 가변 길이의 입력에 적용될 수 있어야 함

 - 입력값의 길이가 가변이더라도 고정된 길이의 해시값을 출력함 (고정된 길이의 출력을 만든다)

 - 해시 결과값으로 입력값을 계산하는 것이 불가능

 - 동일한 해시값을 갖는 서로 다른 입력값을 찾는 것은 계산상 불가능

 - 주어진 해시값에 대응하는 입력값을 구하는 것이 계산적으로 어려움

 - 무결성을 제공하는 메시지인증코드(MCA) 및 전자서명에 사용됨

 - 해시값의 충돌은 입력공간이 출력공간보다 크기 때문에 발생한다 (즉, 충돌은 출력공간이 지나치게 작으면 발생할 수 있음)

 

 

■ 해시함수 공격법

 

1) 생일 공격

  ① 생일 역설 (Birthday Paradox)

    - 생일 문제란 사람들이 모였을 때 생일이 같은 두 명이 나타날 확률을 구하는 문제

    - 만약 366명 이상의 사람이 모이면 생일이 같은 두 명이 반드시 존재

    - 여기서 생일 역설이란 생일이 같은 사람이 나타날 확률이 1/2이 되려면 단 23명이 모이면 된다는 것을 의미

 

  ② 생일 공격 (Birthday Attack)

    - 생일 역설(Birthday Paradox)에 근거하여 해시함수를 공격하는 방법

    - 해시값이 같은 두 개의 서로 다른 메시지를 찾는 것도 생일이 같은 두 사람을 찾는 것과 비슷한 문제로 높은 확률로 해시함수의 충돌 메시지 쌍을 찾아내는 데 사용

    - 0부터 N-1까지의 균일 분포를 갖는 수 중에서 임의로 한 개의 수를 선택한다면, (N)*1/2 번의 시도 후에 동일한 수가 반복해서 선택될 확률은 0.5를 넘는다는 이론과 부합

    - 생일 공격은 일방향 해시함수의 강한 충돌 내성을 깨고자 하는 공격

    - 이러한 생일 공격을 막기 위해서는 해시값의 길이를 일정한 길이로 늘려야 함

 

 

2) 재전송 공격(Reply Attack) = 재연 (Reply) 공격

 - 재연(Replay) 공격(재전송 공격)은 공격자가 네트워크상에 흐르는 메시지 스트림을 복사해두었다가, 나중에 재전송하여 정당한 사용자로 가장하는 공격

 - ID와 PW를 암호화해서 보내는 Client/Server 환경에서 암호화되어 있는 ID와 PW를 스니핑해 저장해 두었다가, 공격하고 싶을 때 보관되어 있는 암호화 된 ID와 PW를 전송해주면 로그인이 된다. 즉 실제 ID, PW가 무엇인지 알 필요가 없다

 - 재전송 공격을 막을 수 있는 방법은 순서 번호, 타임스탬프, 비표, 시도응답 등이 있음

 

 ★ 재전송 공격 방지 방법

   ① 순서 번호 (Sequence Number) : 송신 메시지에 일정하게 증가하는 순서 번호를 붙이기로 약속하고 MAC 값의 계산에 순서 번호를 포함시켜 계산하면 재전송 공격을 예방할 수 있음

   ② 타임 스탬프 (Time Stamp) : 송신 메시지에 현재 시간을 넣기로 약속하고 계산. 송ㆍ수신자 사이에 동기화 필요

   ③ 비표 (Nonce) : 수신자는 송신자에게 일회용 랜덤 값(Nonce) 전송, 송신자는 메시지에 비표를 포함하여 MAC 값을 계산한다. 이 비표의 값은 매번 바뀌기 때문에 재전송 공격을 예방할 수 있다

   ④ 시도응답 (Challenge/Response) : 송신자는 수신자에게 난수를 송신한다. 그리고 수신자로부터 응답받는 난수가 사전에 약속했던 값과 일치하는지 확인하는 방식

 

 

★ 전자서명만으로는 재전송 공격을 방어하기 어렵다!

 - 메시지에 송신자의 개인키로 서명한 전자서명(Digital Signature)을 포함하여 전송하는 것으로는 재전송 공격을 막기 힘들다

 - 전자서명의 대표적 기능은 부인방지로, 패스워드를 그대로 복사했다가 로그인하는 재전송 공격을 구분할 수 없기 때문

 - 재전송 공격은 해커가 암호를 알 필요가 없음. Salt가 포함된 암호문을 그대로 복사했다가 재사용하기 때문

 

 

 

■ 해시함수의 응용

종류	MDC	MAC	전자서명	PKI
방법	Hash만 이용	Hash와 대칭키(비밀키) 이용	Hash와 공개키 이용	제3의 신뢰된 기관
기능	무결성	무결성 발신자 인증	무결성 발신자 인증 부인방지	무결성 발신자 인증 부인방지 기밀성
단점	제공서비스 제한	부인방지 기능 제공 안함, 사용이 저조(비밀키 사용의 불편)	복잡, 기밀성 서비스를 제공하지 않음	복잡, 고비용, 저속
종류	MD5, SHA-1, 256, 512 등	축소MAC, HMAC, CMAC, CCM

 

* HMAC (Hash MAC)-SHA1 : RFC 2104 인터넷 표준에서 정의한 메시지 인증 코드를 생성하는 알고리즘

* CMAC : Cipher based Message Authentication Code

* CCM : Counter with Cipher Block Chaining - Message Authentication Code (카운터 암호 블록 체인)

 

* 인증 : 망을 경유해서 컴퓨터에 접속해 오는 사용자가 등록된(허가받은) 사용자인지를 확인하는 것.

           보통 ID/PW로 인증을 수행.

          MAC와 전자서명이 인증기능을 제공하는 것은 메시지의 출처를 키를 통해 확인할 수 있기 때문

 

 

1) MDC (Modification Detection Code : 변경감지코드)

 - 메시지의 무결성을 보장하는 코드

 - MDC는 역상 저항성, 제2 역상 저항성, 충돌 저항성의 성질을 가진다

 - 일방향 해시함수와 충돌 저항 해시함수로 나뉜다

 

ex) A는 송신할 Message를 해시함수를 이용해 해시값을 만든다. 이때 생성된 해시값을 MDC라 부른다.

    A는 B에게 Message와 MDC를 보낸다

    B는 Message를 해시함수를 이용해 MDC를 만들고 A가 보내준 MDC를 이용해 무결성을 확인한다

 

 

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

 - 해시함수+대칭키(비밀키)로 메시지 무결성을 인증하고 거짓행세를 검출

 - 임의 길이의 메시지와 송신자 및 수신자가 공유하는 키, 두 개를 입력으로 하여 고정 비트길이의 출력을 만드는 함수

 - 송신하려는 메시지와 송/수신자가 공유하는 대칭키(비밀키)를 이용해서 출력(MAC값)을 만든다

 - MAC을 이용한 것이 SSH, SSL, IPSec, TLS, VPN

 - 해시함수와 비슷하지만 key를 미리 교환하는 불편이 있다(안전한 대신 불편, 복제 여부를 판별 할 수 없음)

 

  ★ 특징

   - MAC 검증을 통하여 메시지의 위조 여부를 판별할 수 있음

   - MAC을 이용하여 송신자 인증이 가능

   - MAC 검증을 위해서는 메시지와 비밀키가 필요

   - 해시함수를 이용하여 MAC을 생성할 수 있음

   - MAC 생성자와 검증자는 동일한 키를 사용

 

  ★ 메시지의 무결성 확인

   - 송/수신자 간 사전에 key를 공유

   - 송신자는 Message의 MAC값을 계산해 MAC값과 Message를 수신자에게 보낸다

   - 수신자는 수신한 Message로 MAC 값을 계산한다

   - 수신한 MAC값과 계산한 MAC값이 같으면 인증이 성공한 것이다

 

  ★ 제공 서비스

    - 무결성 검증과 발신자 인증 기능을 제공(사전에 대칭키(비밀키) 미리 교환)한다

 

  ★ 해시함수와 비교

    - MAC은 메시지와 송ㆍ수신자만이 공유하는 비밀키를 입력 받아 생성되는 반면에, 해시는 비밀키 없이 메시지로부터 만들어 짐

 

   ☆ 문제점

     - key배송문제 발생, 비밀키를 이용해 암호화 한다 (그렇기 때문에 HMAC은 해시함수를 이용해 MAC 구성)

     - 부인방지 기능은 제공하지 않는다 (송신자의 개인키로 암호화 하지 않는다)

     - 메시지의 복제 여부를 판별할 수 없다 (원본, 복사본 무의미). 그 이유는 메시지의 내용이 변함이 없다면 제2 역상 저항성에 의해 MAC(Message Detection Code : 메시지인증코드)의 값의 변화가 없기 때문이다

     - MAC은 해시와 비슷한 기능을 가지고 있으나 키교환의 불편으로 사용이 저조하다

 

 

** MAC을 이용한 무결성 확인 과정

 

ⓐ 첫 번째 방법

 - 메시지 자체는 암호화 하지 않는다

 - A와 B는 사전에 키를 공유

 - A는 Message를 해시함수와 대칭키(비밀키)를 이용해 해시값(MAC)을 만든다. 

 - A는 Message와 MAC을 같이 보냄

 - B는 수신한 Message를 기초로 MAC을 해시함수와 대칭키(비밀키)를 사용해 계산 후 수신한 MAC과 B가 계산한 MAC값이 일치하는지 확인한다

 - 수신된 MAC과 계산된 MAC이 일치하면 무결성이 확인된다

 - MAC(메시지인증코드)는 송신하려는 Message와 송/수신자가 공유하는 대칭키(비밀키)를 이용해서 출력(MAC값)을 만든다

 

ⓑ 두 번째 방법

 - 메시지도 암호화 한다

 - 송/수신자 간 사전에 key를 공유한다(비밀키 공유)

 - 송신자는 Message를 대칭키로 암호화 한 후 해시함수를 이용해 MAC을 생성한 후 암호문과 MAC값을 수신자에게 보낸다

 - 수신자는 수신한 암호문을 대칭키를 이용해 복호화하여 Message를 만들고 다시 해시함수를 이용해 MAC값을 계산한다

 - 수신한 MAC값과 계산한 MAC값이 같으면 인증에 성공한 것이다

 

3) 전자서명 (Digital Signature)

 - 전자서명이란 현실 세계에서 사용하는 도장이나 서명 등을 디지털 세계에 적용하여 서명 효과를 부여하는 전자적 서명 방식을 말함

 - 대부분 공개키 암호 알고리즘을 이용하여 구현하며, 무결성을 확인하고 인증과 부인 방지 기능을 제공하는 암호 기술