6.해시함수

<해시함수>

개요 : 

h: D→R (|D|>|R|) 다대일함수 *충돌이 반드시 존재

1) 임의의 길이 String → 고정된 n비트의 String

2) 일방향성 (해싱가능하지만 역산은 할 수 없다)

3) 고속

4) 메시지가 다르면 해시값이 다르다 : ex)악성코드 무결성(변조여부가 없고 같을때) 확인되면 정탐처리 → 충돌이 있어서는 안된다. 왜냐하면 있을 경우 오탐인데 정탐처리가 될 가능성이 생기기 때문이다 따라서 Collision resistance (충돌 저항성 혹은 내성)을 가져야만 한다.

<보안 요구사항>

Preimage resistance (일방향성, 약일방향성)	Second Preimage resistance (약한충돌내성,강일방향성)	Collision resistance (강한충돌내성, 충돌회피성)
h= H(x)에서 x는 preimage이다. Eve는 해시함수 H에 대해서 x를 찾아내는것이 매우 어렵다.	Eve는 메세지 M과 다이제스트 h(M)을 가로챈다. Eve는 h(M)=h(M')인 M'을 만들어내지 못한다.	임의의 M과 같은 M'의 쌍을 찾아내지 못한다.

<키가 있는 해시함수와 없는 해시함수>

<해시의 이용>

-무결성 점검 : 소프트웨어 변경, 문서의 위변조 여부

-메시지 인증 코드 MAC , MDC

-전자서명 

주요 해시 함수들 :

 

메시지 인증 코드 :

메시지 인증 코드(Message Authentication Code, 약칭 MAC)는 메시지의 인증에 쓰이는 작은 크기의 정보이다. MAC 알고리즘은 비밀 키를 입력받고, 임의-길이의 메시지를 인증한다. 그리고 출력으로써 MAC을 출력한다. MAC 값은 검증자(비밀 키를 소유한 사람)의 허가에 의해서 메시지의 데이터 인증과 더불어 무결성을 보호한다.

 

전자서명 :

전자서명을 할 때 일방향 해시함수가 사용된다.

전자서명이란 현실 사회의 서명이나 날인에 해당하는 행위를 디지털 세계로 가져온 것이다.

 

<랜덤 오라클 모델 > Bellare Rogaway 1993

해시함수를 기반으로 한 이상적인 수학적 모델.
이미 다이제스트를 가진 메세지가 주어지면 오라클은 저장되어있던 다이제스트를 제공한다.

새로운 메시지가 들어오면 기존 다이제스트들과 독립적으로 선택되어야 하며, 이는 오라클이 다이제스트 생성을 위한 공식이나 알고리즘을 일체 사용해서는 안됨을 뜻한다.

같은 입력에 대해 항상 같은 출력 값을 갖고, 서로 다른 입력들에 대해 생성된 해시들은 연속균등분포의 형태를 갖음.

*연속균등분포는 연속 확률 분포로, 분포가 특정 범위 내에서 균등하게 나타나 있을 경우를 가리킨다. 이 분포는 두 개의 매개변수 를 받으며, 이때 범위에서 균등한 확률을 가진다. 보통 기호로 로 나타낸다. 인 경우를 표준연속균등분포로 부른다.

<해시함수에 대한 공격> 

비둘기집(pigeon-hole)

N개의 비둘기집과 N+1 마리의 비둘기가 있다면 => 적어도 한 집에는 두마리의 비둘기가 존재한다.

N개의 비둘기집과 kN+1마리의 비둘기가 있다면 => 적어도 한 집에는 K+1마리의 비둘기가 존재한다.

생일 문제(Birthday Paradox)

해시함수가 랜덤 오라클 모델일 때, 안전성의 증명을 비둘기집 원리와 같이 증명한다. 같은 해시 값을 생성하는 2개의 메시지를 구한다. =>충돌저항성(강한 충돌 내성)을 깬다.

랜덤으로 N명의 그룹을 선택한다. N명 중 적어도 2명의 생일이 일치할 확률이 50퍼센트 이상이 되도록 하려면 N이 최저 몇명이 되어야 하는가? => (전체 - 모두 생일이 다른경우) = 1- [365 X 364 X 363 X ... X (365-(N-1)) / (365의 N승)] 의 값이 0.5에 근사한 값을 찾으면 N=23일 때 0.507297라는 값을 가진다.

<일방향 해시함수에 대한 공격>

Brute Force :  SHA-1의 경우 해시값이 160비트이므로 2^160회를 시행하면 원하는 메시지가 발견될 것이라 생각하고 공격함. -약한 충돌 내성

일치블록 연쇄 공격 : 새로운 메시지(M')를 여러개 만들어서 공격하고자 하는 메시지 M의 해시함수 값 H(M)과 같은 것을 골라 사용하는 것.

중간자 연쇄공격 : 해시 중간의 결과에 대한 충돌쌍을 찾아 내는 것.

고정점 연쇄공격 : 메시지 블록과 연쇄변수 쌍을 얻으면 연쇄변수가 발생하는 특정점에서 동일블록을 메시지 중간에 삽입해도 전체 해시값이 변하지 않음

차분 연쇄공격 : 해시함수의 경우 압축함수 방법이므로 입출력 차이를 조사해 0의 충돌쌍을 주로 찾아내는 것.
  다중 라운드 블록함수의 경우 입력값과 출력값의 차이를 통계적으로 분석하여 공격하는 방법.

<일방향 해시함수로 해결불가능한 문제>

조작과 변경은 검출 가능하지만, 거짓행세는 검출 불가능하다.

파일 무결성 뿐 아니라 소유자가 앨리스인지 확인을 위해서는 [인증] 절차가 필요하고

MAC이나 전자서명으로 충족시킨다.

<SHA-512>

 

128비트의 부호없는 정수 길이 필드 + 가변길이의 패딩 + 원문 메세지가 필요하고, 이들은 밑의 자료와 같이 해싱이 진행된다.

메시지 길이는 2의 128승보다 작아야 한다.

 

<MDC, Modification Detection Code, 메시지 변경 감지 코드>

메시지의 무결성을 보장하는 메시지 다이제스트로 수신한 메시지의 MDC를 계산하고 송신측이 보내준 MDC와 비교하여 동일한지 비교함.

무결성은 인증 가능하지만 메시지 출원인증이 안되기 때문에 메시지의 위조같은 적극적 공격은 MAC으로 검출해야 한다. 위의 자료를 보면 MDC는 신뢰성있는 채널을 통해 MDC가 전송된다는 가정이 전제조건으로 깔려있다. 따라서 MDC를 사용하기 위해서는 신뢰성있는 채널이 있어야만 한다는 제약이 있으며,

제약조건에 부합하지 않을경우 제 3자가 메시지를 위조해도 알아차리지 못하게 된다. (그저 임의의 송신자가 보낸 파일의 원본인지 아닌지만 판단하는 용도로 전락해버린다.)

<MAC,Message Authentication Code,메시지 인증코드>

MDC에는 없는 두사람 만의 비밀값 (키)가 존재한다.
MAC은 (해시함수,대칭키)로 메시지 무결성을 인증하고 송신자 가장 행위를 검출한다. (메시지 인증의 의의 : 올바른 송신자가 보낸 것임을 인증한다.)

임의 길이의 메시지와 송신자 및 수신자가 공유하는 키. 두 개의 입력으로 고정 비트길이의 출력을 만드는 함수의 출력값을 MAC이라고 정의한다. 적극적 공격인 데이터 위조 같은 것을 방어하는데 사용.

키 K는 오직 송,수신자만 알고 있음.
H(K||M)= MAC

(K,M) 두개의 인풋 MAC이라는 아웃풋

 

  H(M||K||K') 처럼 다른 키가 있어도 된다. (송수신자가 K, K'을 사전에 공유해야 한다.)

<MAC의 안전성>

MAC의 안전성 = 해시함수의 안전성

키 배송 문제가 존재한다.

<MAC의 종류>

MAC의 안전성을 높이기 위한 방법

  두번의 해시함수를 거친다.
  (최종 MAC) = H(K||(H(K||M)))

HMAC(Hash MAC,Nested MAC의 표준)
-키k 는b 비트가 되도록 패딩을 붙인다. (0으로 채움) 그 후 00110110 00110110이 반복되는 b 비트짜리 ipad와 XOR한다. => K1 

-키k 는b 비트가 되도록 패딩을 붙인다. (0으로 채움) 그 후 01011100 01011100이 반복되는 b 비트짜리 opad와 XOR한다. => K2

CMAC(Cipher-based Message Authentication Code, CBMAC, FIPS 113
  대칭키 암호시스템 CBC모드와 동일 아이디어 기반.
  메시지를 N개의 블록으로 나누고 , 각각의 블록은 키와 함께 암호화 알고리즘에 반영됩니다. 암호화 알고리즘의 결과는 final MAC이 생성되기 전까지 다음 블록과 XOR됩니다. 암호화와는 다르게 결과는 단일블록으로 압축됩니다.

마지막 단계는 추가적인 키를 사용하는데(같은 시작을 가진 두개의 메시지에 대한 차분분석법을 피하기 위해서 추가적인 키가 필요하다.), 그 키가 생성되는 원리는 다음과 같다.

0으로 이루어진 m비트의 블록을 비밀키 K로 암호화하여 패딩이 적용되지 않았을 경우 x를 곱하고 패딩이 적용되면 x의 제곱을 곱한다.
 

장점

상용 암호화 알고리즘 사용 가능

암호화 알고리즘 사용으로 역상이미지 저항성과 충돌 회피성을 가진다

단점

해시 알고리즘보다 암호화 알고리즘(특히, 사슬 형태이라면)이 더 느리다.

 

CCM(Counter with CBC Mode) : AES 알고리즘 + CTR 운용모드 + CBC-MAC 인증 알고리즘

GCM(Galois/Counter Mode) : CTR 모드가 암호문을 생성하면서 '위조된 암호문이 아니다'라는 인증정보(인증자)를 만들어낸다.

<MAC 사용의 예>

IPSec, SSL/TLS

<MAC 공격 방법>

재전송 공격(replay 공격): 적극적 공격자 멜로리는 저장해둔 MAC값을 반복해서 송신.

방어법
  순서번호
      송신 메시지에 순서번호를 붙이면서, MAC 값의 계산에서는 순서번호도 메시지에 포함시킨다.
  타임스탬프
      송신 메시지에 현재 시각을 삽입. 이전의 메시지가 오면 MAC값이 같더라도 오류로 판단.
                                                                      단, 송수신자 사이에 시간동기화 필요.
  비표(nonce)
      메시지 수신전, 수신자가 송신자에게 일회용 랜덤 값(비표) 전송. 송신자가 메시지 안에 비표를 넣어 MAC값을 계산.
      매번 비표가 바뀌므로 재전송 공격이 막힘.

<MAC으로 해결 불가능한 문제>

제3자에 대한 증명
  앨리스로부터 메시지를 받은 밥이 메시지가 정말 앨리스가 보낸 것이라는 것을 제 3자인 검증자 빅터에게 증명할 수 없음.
  증명하기 위해선 공유키(앨리스와 밥이 공유하고 있는 키)를 빅터에게 알려줘야만 하고,
  공유키는 앨리스와 밥이 가지므로 둘 중 누가 메시지를 작성했는지 검증할 수 없음.
부인 방지
  밥이 MAC과 함께 메시지를 받고, 메시지가 앨리스로부터 온것이라는 것은 확실히 증명이 가능함.
  하지만 앨리스가 전송 자체를 부정할 경우 제 3자에게 이를 증명할 수 없음.
  즉, 앨리스가 송신자체를 부인(repudiation)하는 것. 따라서 MAC으로는 부인 방지를 할 방법이 없음.
해결방법
  전자서명: 공개키기반이므로 송신자는 자신의 개인키로 메시지에 서명하고, 수신자는 송신자의 공개키로 서명을 검증하여 부인방지를 함.