[정보보안기사] 5. 해시 함수와 응용 (출제율: 1.9%)

1. 일방향 해시함수 (= 메시지 다이제스트 함수, 암호학적 해시함수)

임의의 길이를 갖는 메시지 입력으로 고정된 길이의 해시값 또는 해시 코드라 불리는 값을 출력하는 함수이다.

서로 다른 두 개의 메시지가 하나의 해시로 출력되는 충돌 현상을 막기 위해서 충돌 내성을 가져야 한다.

 

1) 일방향 해시함수의 특징

해시값을 고속으로 계산할 수 있다.

해시값 으로부터 메시지를 구할 수 없는 일방향성을 갖는다. 

메시지가 다르면 해시 값도 다르다. 

기본적으로 무결성을 검증, 소프트웨어 변경을 검출할 수있지만 부인방지는 검출하지 못한다.

메시지 인증 코드(MAC), 전자서명에 활용된다. (인증을 수행하기 위한 기술)

기본적으로 키가 존재하지 않는다.

 

2) 해시 함수의 보안 요구사항

프리 이미지 저항성, 제2프리 이미지 저항성, 충돌 저항성의 3가지 기준을  충족해야 한다.

2.1) 프리 이미지 저항성 (역상 저항성)

y = h(M)에 대해서 도청자가 y = h(M')을 만족하는 메시지 M'를 찾아낸다는 것이 매우 어려워야 한다.

해시를 통해 출력된 값을 통해서 입력값을 알아내야 하는 것이 어려워야 한다.

 

2.2) 제 2프리 이미지 저항성 (두 번째 역상 저항성, 약한 충돌 내성)

메시지를 쉽게 위조할 수 없어야 한다.

도청자가 메시지 M과 메시지에 대한 결과 값 h(M)을 가로챈 후 h(M) = h(M')을 만족하는 M'을 찾기가 어려워야 한다.

메시지와 해시된 값을 가지고 같은 해시값을 가지는 다른 메시지를 찾는 것이 불가능해야 함

 

2.3) 충돌 저항성 (충돌 회피성, 강한 충돌 내성)

동일한 결과 값을 가지는 서로 다른 2개의 메시지를 구하기 어려워야 한다. (충돌 저항성)

 

2. 전자서명에 이용되는 해시 함수의 특성

해시 값을 고속으로 계산할 수 있어야 한다.

약 일방향성 (프리 이미지 저항성)을 가지고 있어야 한다.

강 일방향성 (제2 프리 이미지 저항성)을 가지고 있어야 한다.

충돌 회피성을 가지고 있어야 한다.

 

3. 키가 없는 해시 함수

블록 암호를 기초로한 해시 함수, 전용 해시 함수, 모듈 연산을 기초로 한 해시 함수

1) 전용 해시 함수 (처음부터 새로 만듦)

1.1) 메시지 다이제스트 (MD2 → MD4 → MD5)

MD5는 512비트의 블록 크기로 나누고 128비트의 메시지 다이제스트를 출력한다.

생일 공격에 취약하다.

 

1.2) SHA

SHA-1은 512비트 블록 크기로 나누고 160비트의 메시지 다이제스트를 출력한다.(MD5 구조를 따름)

그 이후의 SHA의 해시 값은 각각 256(SHA-256), 384(SHA-384), 512(SHA-512) 비트이다.(SHA-2로 불림)

현재는 안정성 때문에 SHA-3를 사용하고 있다.

 

1.3) SHA-512

각 블록은 16개의 워드로 이루어져있고 MD는 8개의 워드로 이루어져 있다.

SHA-512의 메시지의 길이는 2^128을 넘어선 안된다. (메시지 처리 불가능)

MD를 생성하기 이전에 128비트의 메시지 길이를 표현한 값이 패딩된다. (약한 충돌 내성 저항)

 

1.4) Tiger

64비트 시스템에서 해시 함수를 수행하기 위해 설계되었다.

MD, SHA-1보다 속도가 빠르다

 

1.5) HAS160

한국형 전자서명에서 사용할 목적으로 설계되었다.

512비트 블록 크기로 나누고 160비트의 메시지 다이제스트를 출력한다. (Little endian)

 

	MD5	SHA-1	RIPEMD-160	SHA-512	HAVAL
MD 크기	512	512	512	512	128,160,192,224
블록 크기	128	160	160	1024	1024
라운드 수	80(16*4)	80(20*4)	80	80	3/4/5
Endianness	Little-endian	Big-endian	Little-endian	Big-endian	Little-endian

2) 블록 기반 해시 함수

해시 함수 안에 사용하는 압축 함수 자리에 대칭키 블록 암호를 상용할 수 있다

 

3) 모듈 연산에 기반을 둔 함수

압축 함수의 기반을 모듈 연산의 반복적인 수행에 두고 있는 해시 함수이다.

속도가 빠르지 않고 안전성에 대한 역사가 짧다.

 

4. 키를 사용하는 해시 함수

메시지 인증 기능을 가진 함수이다.

 

5. 해시 함수에 대한 공격

1) 비둘기집 원리

kn + 1마리의 비둘기가 n개의 비둘기집에 들어가 있다면 적어도 한개의 비둘기집에는 k + 1마리의 비둘기가 들어가 있어야 한다는 원리이다.

 

2) 생일 공격 (Birthday Attack)

일방향 해시 함수의 강한 충돌 내성을 깨고자 하는 공격이다.

해당 공격에 안전한 해시함수 비트는 180bit이다.

 

생일 패러독스: 23명이 같이 있으면 2명의 생일이 일치할 확률은 1/2 이상이다.

 

6. 일방향 해시 함수에 대한 공격

무차별 공격, 일치블록 연쇄공격, 중간자 연쇄공격, 고정점 연쇄공격, 차분 연쇄공격이 있다.

 

1) 무차별 공격

약한 충돌 내성을 깨고자 하는 공격이다. 

SHA-1의 경우 메시지 다이제스트 값이 160비트이므로 2^160회를 실행하면 원하는 메시지가 발견된다.

 

2) 일치블록 연쇄공격

새로운 메시지 M' 사전에 많이 만들어 두어서 대입을 통한 약한 충돌 내성을 깨고자 하는 공격이다.

 

3) 중간자 연쇄공격

해시 중간의 결과에 대한 충돌쌍을 찾는다. (특정 포인트를 공격 대상으로 한다.)

 

4) 고정점 연쇄공격

연쇄변수가 발생하는 특정한 점에서 임의의 수의 동등한 블록을 메시지 중간에 삽입해도 전체 해시값이 변하지 않는 것을 이용한 공격이다.

 

5) 차분 연쇄공격

다중 라운드 블록암호의 공격: 입력값과 그에 대응하는 출력값의 차이의 통계적 특성을 조사한다.

해시함수의 공격: 압축함수의 입출력 차이를 조사하여 0의 충돌쌍을 찾아낸다.

 

7. 변경 감지 코드 (MDC)

메시지이 무결성을 보장하는 메시지 다이제스트이다.

무결성은 보장하지만 인증과 부인방지를 할 수 없다.

 

8. 메시지 인증코드 (MAC)

무결성을 확인하고 메시지에 대한 인증을 하는 기술이다. 

블록 암호나 해시 함수에 기반을 두기 때문에 전자 서명보다 속도가 빠르다.

MDC와의 차이점은 평문을 키를 통해 암호화한 후 암호문을 해시 처리한다는 것이다.

검증하는 방법은 계산된 MAC m'과 수신된 MAC m값이 서로 일치하는지 확인한다.

메시지 인증코드, 암호학적 체크섬, HMAC 기법 등을 사용한다.

대칭키 암호화 동일하게 키 배송 문제가 발생한다.

 

 

1) 축소 MAC

안전성을 높이기 위해서 메시지와 키를 해시 처리한 후 나온 MAC값과 키를 또 해시 처리한다.

 

2) HMAC

SHA-1과 같은 일방향 해시함수를 이용하여 MAC를 구성하는 방법이다.

TLS, IPSec, SET 같은 프로토콜에 사용된다. (메시지 인증, 기밀성, 부인 방지)

 

3) CBC-MAC, CMAC (Cipher-Based MAC)

대칭키 암호를 N번 사용하여 N개의 평문블록에서 하나의 MAC을 생성한다.

둘다 무결성 과 인증이 제공되지만 CBC-MAC보다 CMAC이 더 안전하다.

 

4) CCM (Counter with CBC-MAC)

CTR과 CBC-MAC을 통합하여 동일한 키 사용을 통하여 기밀성과 인증(무결성)을 제공한다.

무선 근거리 통신망의 보안 요구 사항을 지원하기 위해 표준화 되었으나 인증 암호를 요구하는 다양한 네트워크에서 응용하여 사용할 수 있다.

 

5) CGM

CTR 모드에 인증 기능을 추가한 것이다. (기밀성과 무결성, 인증을 제공)

 

9. MAC에 대한 공격

재생 공격(Replay Attack)을 방지 할 수 없다.

순서번호, 타임 스탬프, 비표, 시도/응답 방식을 도입하여 재생 공격을 방어할 수 있다.

제3자에 대한 증명, 부인 방지할 수 없으나 전자서명을 사용하면 방지가 가능하다.

 

10. 랜덤 오라클 모델

오라클은 0 또는 1로 이루어진 고정된 메시지 다이제스트를 생성한다.

이미 해시값이 존재하는 메시지가 주어면 오라클은 저장되어있던 해시값을 이용한다.

새로운 메시지에 대한 해시값은 다른 모든 해시값과 독립적으로 선택되어야하고 충돌 저항성을 갖는다.

 

 

 

 

참조

MAC:https://ko.wikipedia.org/wiki/%EB%A9%94%EC%8B%9C%EC%A7%80_%EC%9D%B8%EC%A6%9D_%EC%BD%94%EB%93%9C