[정보보안기사 PART 02] 암호학 - 해시함수와 응용

[정보보안기사 PART 02] 암호학 - 해시함수와 응용

---

Section 05 해시함수와 응용

 

1. 일방향 해시함수

 

(1) 일방향 해시함수의 개요

 

1) 기본 개념

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

- 해시함수 h는 임의의 길이의 문자열을 고정된 길이를 갖는 n비트 문자열로 대응시킨다.

- 정의역을 D, 치역을 R이라 할 때 해시함수 h : D -> R (|D| > |R|)는 다대일 대응 함수이다.

(충돌이 반드시 존재함을 의미)

 

2) 일발향 해시함수의 특징

1. 임의 길이의 메시지로부터 고정 길이의 해시값을 계산

- 어떤 길이의 메시지를 입력으로 주더라도 항상 짧은 해시값을 생성하지 않으면 의미가 없다.

 

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

- 해시값을 구하기 위해 시간이 너무 오래 걸리면 안된다.

 

3. 일방향성을 갖는다.

- 일방향 해시함수는 일발향성(one-way)을 가질 필요가 있다. 이것은 해시값으로부터 메시지를 더 메시지를 역산할 수 없다는 성질이다.

 

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

- 무결성을 확인하기 위해 사용한다. 메시지가 1비트라도 변환하면 해시값은 매우 높은 확률로 다른 값이 되어야 하기 때문이다.

- 2개의 다른 메시지가 같은 해시값을 갖는 것을 충돌이라고 한다. 일방향 해시함수를 무결성 확인에 사용하기 위해서는 충돌이 발견되어서는 안 된다.

- 충돌이 발견하는 것이 어려운 성질을 가리켜 충돌 내성(collision resistance)이라고 부른다. 암호기술에서 사용되는 일방향 해시함수는 충돌내성을 가질 필요가 있다.

 

 

 

(2) 해시함수의 분류와 보안 요구사항

 

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

(가) 개요

암호학적 해시함수는 프리이미지 저항성(preimage resistance), 제2프리이미지 저항성(second preimage resistance), 충돌 저항성(collision resistance)의 3가지 기준을 충족해야 한다.

 

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

- 해시 값 h = H(x)에 대하여, x는 h의 선 이미지(preimage)라 한다.

(x는 함수 H를 사용한 해시함수 결과가 h인 데이터 블록 H가 다대일 대응이므로, 주어진 해시 값 h에 대하여 여러개의 선 이미지가 존재하게 된다.)

- 해시함수 h와 y = h(M)에 대해서 Eve가 y = h(M)를 만족하는 메시지 M를 찾아낸다는 것이 매우 힘들어야 한다는 성질이다. 

(프리 이미지 저항성은 일발향성임)

 

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

- 메시지를 쉽게 위조할 수 없도록 하는 성질이다.

- Eve는 메시지 M가 다이제스트 h(M)을 가로챈다. Eve는 h(M) = h(M)를 만족하는 다른 메시지(M')를 생성한다. Eve는 M'와 h(M)를 Bob에게 보낸다. Eve는 이렇게 해서 메시지를 위조할 수 있는 것이다.

- 이런 충돌이 발생할 확률은 충돌저항성(강한 충돌 내성)보다 상대적으로 낮기 때문에 약한 충돌 내성이라 한다.

 

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

- Eve로 하여금 동일한 다이제스트를 가지는 2개의 메시지를 구하지 못하도록 하는 것이다. 여기서 공격자는 어떤 정보도 없는 상태에서 동일한 다이제스트를 갖는 두 개의 메시지를 생성할 수 있다.

- 충돌이 발생할 확률은 약한 내성의 경우보다 상대적으로 높기 때문에 강한 충돌 내성이라 한다.

 

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

- 해시값을 고속으로 계산할 수 있다.       // 해시함수의 성능조건

- 약 일방향성 (Weak onewayness)         // 해시함수의 안전성에 대한 제약, 해시 함수의 역함수 계산 방지

- 강 일방향성 (Strong onewayness)       // 해시함수의 안전성에 대한 제약, 해시 함수의 역함수 계산 방지

- 충돌 회피성 (collision freeness)          // 해시함수의 성능조건, 내부부정을 방지하는 기능

 

3) 해시함수의 성질들 사이 관계

- 충돌 저항성은 두 번째 역상 저항성을 보장한다.

- 두 번째 역상 저항이 역상 저항을 보장하지 못하며, 역상 저항이 두 번째 역상 저항을 보장하지 못한다.

- 충돌 저항성은 역상 저항성을 보장하지 않는다.

 

 

 

(3) 키가 없는 해시함수와 키를 사용하는 해시함수

 

1) 키가 없는 해시함수

(가) 기본 개념

- 블록 암호를 기초로 한 해시함수

- 전용 해시함수(처음부터 새로 만드는 것)

- 모듈 연산을 기초로 한 해시함수

 

(나) 전용 해시함수

항목	MD5	SHA-1	RIPEMD-160
다이제스트 길이	128비트	160비트	160비트
처리 단위	512비트	512비트	512비트
단계수	64(16번의 4라운드)	80(20번의 4라운드)	160(16번의 5병행 라운드)
최대 메시지 크기	무한	2^64 - 1 비트	2^64 - 1 비트
앤디언	Little-endian	Big-endian	Little-endian

 

(다) 블록암호 기반 해시함수

- 반복 암호학적 해시함수 안에 사용되는 압축함수 자리에 대칭키 블록암호를 사용할 수도 있다.

 

(라) 모듈 연산에 기반을 둔 해시함수

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

- SW 자체에 내장된 모듈 연산을 사용할 수 있다는 장점,

- 속도 빠르지 않고, 안전성 연구에 대한 역사 짧음.

 

2) 키를 사용하는 해시함수

(가) 기본 개념

- 메시지 인증 기능을 가진 함수

- 함수 자체의 안전성과 키의 비밀성에 안전성을 두고 있다.

 

(나) 블록 암호에 기반을 둔 메시지 인증 알고리즘

- CBC(Cipher Block Chaining) 모드를 이용하는 방법

 

 

 

(4) 암호학적 해시함수의 응용

 

1) 무결성 점검

- 생성된 새로운 메시지 다이제스트와 이전의 메시지 다이제스트를 비교

 

2) 소프트웨어 변경 검출

 

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

- 상호 간에 교환되는 정보를 인증하기 위해, 비밀키를 공유하는 두 통신 상대자 간에 사용된다.

- SSL/TLS 이용

 

4) 전자서명

 

 

 

(5) 랜덤 오라클 모델과 해시함수에 대한 공격

 

1) 랜덤 오라클 모델

(가) 개요

- 임의의 길이를 갖는 메시지에 오라클은 0과 1로 이루어진 난수 스트링인 고저오딘 길이의 메시지 다이제스틀르 생성해서 제공

- 이미 다이제스트가 존재하는 메시지가 주어지면 오라클은 저장되어 있는 다이제스트를 제공

- 새로운 메시지에 대한 다이제스트는 다른 모든 다이제스트와는 독립적으로 선택될 필요가 있다.

 

(나) 비둘기집 원리

(다) 생일 문제 (생일 공격)

 

2) 일방향 해시함수에 대한 공격

(가) 무차별 공격

(나) 기타 해시함수 공격의 종류 및 특성

- 일치블록 연쇄공격

- 중간자 연쇄공격

- 고정점 연쇄공격

- 차분 연쇄공격

 

 

 

(6) 일방향 해시함수로 해결할 수 없는 문제

 

1) 개요

- 「조작과 변경」 검출 가능

- 「거짓행세」 검출 불가능

- 메시지 인증코드, 전자서명

 

 

 

 

2. 암호화적 해시함수의 예

 

(1) SHA-512

(2) SHA-3

 

 

 

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

(1) 개요

 

1) 기본 개념

- 무결성 확인하고, 메시지에 대한 인증하는 기술

(변경과 거짓행세 검출 가능)

- 임의 길이의 메시지와 송신자 및 수신자가 공유하는 키라는 2개의 입력을 기초로 해서 고정 비트 길이의 출력을 계산하는 함수

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

 

2) 변경 감지 코드 (MDC, Modification Detection Code)

- 무결성 보장

- 수신한 메시지로부터 새로운 MDC 생성 후 받은 MDC와 비교

 

3) 메시지 인증 코드 (MAC)

- 송신자와 수신자가 공유하는 키 사용

- 키에 의존하는 일방향 해시함수

- 사용하는 해시 알고리즘의 안전성에 의해 안전성이 좌우된다.

 

4) MAC의 키 배송 문제

- 송신자와 수신자 키 공유할 필요 있다.

- 키 배송 문제 발생

 

(2) MAC의 구현 사례

 

1) 축소 MAC

2) HMAC

3) CBC-MAC, CMAC

4) CCM(Counter with CBC-MAC)

5) GCM 모드

 

(3) MAC에 대한 공격

1) 재전송 공격

 

(4) MAC으로 해결할 수 없는 문제

1) 제 3자에 대한 증명

2) 부인 방지

 

 

 

 

 

*출처:[알기사] 2019 정보보안기사&산업기사

*해당 블로그는 개인적인 공부와 정보 공유를 위해 만들었습니다.