Section.05 해시함수와 응용

1.일방향 해시함수

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

1)기본개념

• 일방향 해시함수(one-way hash function)에는 입력과 출력이 각각 1개씩 있다. 입력은 메시지라 하고 출력은 해시값(hash value)이라 한다.
• 일방향 해시함수는 어떤 메시지든지 단지 비트열로 취급하며, 그 비트열을 기초로 해시값을 계산한다.

2)일방향 해시함수의 성질

• 임의의 길이 메시지로부터 고정길이의 해시값을 계산한다.
• 어떤 길이의 메시지를 입력으로 주더라도 일방향 해시함수는 짧은 해시값을 생성하지 않으면 의미가 없다.
• 해시값을 고속으로 계산할 수 있다.
• 해시값을 구하기위해 시간이 너무 오래 걸리면 안 된다.
• 일방향성을 갖는다.
• 일방향 해시함수는 일방향성을 가질 필요가 있다. 이것은 해시값으로부터 메시지를 역산링 수 없다는 성질이다.
• 그림...
• 메시지가 다르면 해시값도 다르다.
• 무결성을 확인하기위해 사용한다. 메시지가 1비트라도 변화하면 해시값은 매우 높은 확률로 다른 해시값이 되어야 하기 때문이다.
• 2개의 다른 메시지가 같은 해시값을 갖는 것을 충돌(collision)이라고 한다. 일방향 해시함수를 무결성 확인에 사용하기 위해서는 충돌이 있어서는 안된다.
• 충돌을 발견하기 어려운 성질을 가리켜 충돌내성(collision resistance)이라함. 암호기술에서 새용되는 일방향 해시함수는 충돌내성을 가질 필요가 있다.

(2)메시지 무결성

1)무결성 점검

• 메시지 혹은 문서의 무결성을 점검하기위해 암호학적 해시함수를 사용해야 하고 이렇게 생성된 새로운 메시지 다이제스트와 이전의 메시지 다이제스트를 비교해 보아야 한다.
• 만약 이 두 개가 동일하다면 원래의 메시지가 변경되지 않았다는 것을 확신할 수 있다.

2)암호학적 해시함수 기준

①개요

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

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

• 암호학적 해시함수는 프리이미지 저항성이 있어야한다. 
• 프리이미지
• f(x)=y에서 x는 y의 이전 이미지라고 한다.f가 일대일 대응이 아니면 하나의 y에 여러 이전 이미지가 있을 수 있다.
• 프리이미지 저항성이란 주어진 해시함수 h와 y=h(M)에 대해 Eve가 y=h(M')를 만족하는 다른 메시지 M'를 찾아낸다는 것이 매우 힘들어야 한다는 성질이다.

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

• 메시지를 쉽게 위조할 수 없도록 해야함.
• Eve는 메시지 M과 다이제스트 h(M)을 가로챈다. Eve는 h(M)=h(M')을 만족하는 다른 메시지를 생성한다.

④충돌 저항성(강한 충돌 저항성)

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

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

• 해시값을 고속으로 계산할 수 있다.
• 약 일방향성(weak onewayness)
• 해시값 H로부터 h(M)=H 되는 서명문 M을 찾는것은 계산상 불가능해야 한다.
• 강 일방향성(strong onewayness)
• 어떤 서명문 M과 그 해시값 H=h(M)가 주어졌을 때 h(M')=H되는 서명문 M'!=M을 찾는것이 계산상 불가능 해야 한다.
• 충돌 회피성
• h(M)=h(M')되는 서명문 쌍 (M,M')(M!=M') 을 찾는것이 계산상 불가능해야 한다.

(3)일방향 해시함수의 응용

1)소프트웨어 변경 검출

• 자신이 입수한 소프트웨어가 변경되었는지를 확인하기 위해 사용.
• 사용자는 소프트웨어를 입수한 후 , 자신의 손으로 해시값을 가시 계산해서 그 것을 오리지널 사이트에서 제공하는 해시값과 비교함.

2)패스워드를 기초로 한 암호화 

• 패스워드를 기초로 한 암호화(password based encryption;PBE)에서 사용된다.
• PBE에서는 password와 솔트(의사난수 생성기로 생성한 랜덤값)를 섞는 결과의 해시값을 구해 그것을 암호화키로 사용한다. 이 방법으로 패스워드에 대한 사전공격을 막을 수 있다.
• 사전공격: 사전에 있는 단어를 입력해 암호를 알아내거나 해독하는 컨퓨터 공격법

3)메시지 인증 코드 

• 일방향 해시함수를 사용해서 메시지 인증코드를 구성할 수 있다.
• 메시지 인증코드: 송신자와 수신자만이 공유하고 있는 키 와 메시지를 혼합해서 그 해시값을 계산한 값

4)전자서명

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

5)전자입찰 시스템

• 입찰 공고를 한 다수의 공급자가 응찰하여 오면 이중에서 가장 싼 가격을 제시, 계약을 맺는 입찰 방식을 인터넷을 이용해 구현한 것.
• 요구사항
• 독립성: 전자입찰 시스템의 각 구성요소들은 자신들의 독자적인 자율성을 보장받아야 한다.
• 비밀성: 네트워크상에서 각 구성요소 간에 개별정보는 누구에게도 노출되어서는 안된다.
• 무결성: 입찰시 입찰자 자신의 정보를 확인 가능하게 함으로써 누락 및 변조 여부를 확인할 수 있어야 한다.
• 공평성: 입찰이 수행될 때 모든 정보는 공개되어야 한다. 
• 안전성: 각 입찰 참여자간의 공모는 방지되어야 하고 입찰 공고자와 서버의 독단이 발생해서는 안된다.

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

1)랜덤 오라클 모델

①개요

• 해시함수에 대한 이상적인 수학적 모델

②비둘기집 원리

• 만약 n+1마리의 비둘기가 n개의 비둘기집에 들어가 있다면 적어도 한 비둘기 집에는 두 마리의 비둘기가 들어가 있다는 뜻.
• 일반화된 버전은, 만약 kn+1마리의 비둘기가 n개의 비둘기집에 들어가 있다면 적어도 한 개의 비둘기집에는 k+1마리의 비둘기가 들어가 있어야 한다는 원리이다.

③생일문제(생일공격)

• 특정의 해시값을 생성하는 메시지를 구하는 것이 아니라, 해시값은 뭐든지 괜찮고, 어쨌든 같은 해시값을 생성하는 2개의 메시지를 구하는 것이다.
• 생일공격(birthday attack)은 일방향 해시함수의 강한 충돌내성을 깨고자 하는 공격
• 생일 패러독스
• 생일퀴즈: 랜덤으로 N명의 그룹을 생각한다. N명중 적어도 2명의 생일이 일치랑 확률이 1/2이상이 되도록 하기위해서는 N의 최소 숫자는?
• 답: N=23이다. 이떄 확률이 0.507297로 1/2이상임.

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

①무차별 공격

• 암호에 대해 무차별 공격이 가능했던 것처럼 일방향 해시함수에 대해서도 가능함.
• 일방향 해시함수의 약한 충돌내성을 깨기위한 공격이다. SHA-1의 경우 해시값이 160비트이므로 2^160회의 시행횟수를 행하면 목적하는 메시지가 발견될 것이라고 기대할 수 있다.

②기타 해시함수 공격의 종류 및 특성

• 일치 블록 연쇄공격
• 새로운 메시지 M'를 사전에 다양하게 만들어 놓았다가 공격하고자 하는 메시지 M의 해시함수값 h(M)과 같은 해시함수값을 갖는 것을 골라 사용하는 공격.
• 중간자 연쇄공격 
• 전체 해시값이 아니라 해시 중간의 결과에 대한 충돌쌍을 찾는다. 특정 포인트를 공격대상으로 삼는다.
• 고정점 연쇄공격
• 압축함수에서 고정점이란  압축 함수에서 고정점이란 을 만족하는 쌍 를 말한다. 
• 그러한 메시지 블록과 연쇄변수 쌍을 얻게 되면 연쇄변수가 발생하는 특정한 점에서 임의의 수의 동등한 블록들  를 메시지의 중간에 삽입해도 전체 해시값이 변하지 않는다.
• 차분 연쇄공격 
• 다중 라운드 블록암호의 공격: 다중 라운드 블록암호를 사용하는 해시함수에서 입력값과 그에 대응하는 출력값 차이의 통계적 특성을 조사하는 기법사용.
• 해시함수의 공격: 압축함수의 입출력 차이를 조사해 0의 충돌쌍을 주로 찾아내는 방법사용.

(5)일방향 해시함수를 이용해 해결할 수 없는 문제

• 일방향 해시함수는 조작과 변경을 검출할 수 있지만 거짓행세를 검출하지는 못함.
• 파일의 무결성을 조사하는 것뿐만 아니라 이 파일이 정말 Alice의 것인가를 확인하고 싶은 경우에는 무결성 외에 인증이라는 절차가 필요하다.
• 인증을 수행하기 위한 기술이 메시지 인증코드와 전자서명이다.

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

(1)개요

1)압축함수의 두 가지 유형

• 기본개념
• 아무런 기초없이 처음보터 새로 만드는 것, 목적에 맞게 특별하게 설계
• 압축함수 자리에 대칭키 블록암호를 사용
• 새로 만드는 해시함수
• 메시지 다이제스트(Message Digest)(MD2-MD4-MD5)
• 최종버전인 MD5는 MD4의 강화버전으로 메시지를 512비트로 된 블록들로 나누고 128비트로 다이제스트 출력.
• 현재 128비트 메시지 다이제스트는 충돌 공격에 내성을 갖기에는 길이가 너무 짧다고 알려짐.
• SHA(Secure Hash Algorithm)
• 최근에 가장 널리 사용되는 해시함수는 안전 해시알고리즘(SHA)임.
• SHA는 MD4 해시함수에 기초애서 만들어졌고 설계도 MD4를 모델로함. SHA-1은 해시값으로 160비트를 출력한다.
• 이외 설명이 있는데 사실 귀찮음 ...........필요시 추가.

• 구분	SHA-1	SHA-224	SHA-256	SHA-384	SHA-512
  MD길이	160	224	256	384	512
  최대 메시지 길이	2⁶⁴-1	2⁶⁴-1	2⁶⁴-1	2¹²⁸-1	2¹²⁸-1
  블록길이	512	512	512	1024	1024
  워드길이	32	32	32	64	64
  단계 수	80	64	64	80	80

• 기타 알고리즘
• RIPEMD(Race Integrity Primitives Evaluation Message Digest)
• HAVAL
• 주요 해시 알고리즘 비교

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

• 블록암호기반 해시함수
• 반복 암호학적 해시함수 안에 사용되는 압축함수 자리에 대칭키 블록암호를 써서 사용할 수 있다.
• DES,AES처럼 검증된 여러개의 대칭키 알고리즘이 있어 새로 압축함수를 만들 필요 없이 이 것들을 일방향 함수로 사용할 수 있기 때문이다. 이 경우 블록암호의 암호화 기능만 사용하는 것이다.

(2)SHA-512

1)개요

• 기본개념
• SHA-512는 다중블록메시지로부터 512비트 다이제스트를 생성한다. 각 블록은 1024비트 길이를 가진다. 
• 
• 길이 필드와 패딩
• 메시지 다이제스트를 생성하기 전에 SHA-512에서는 메시지에 추가적으로 덧붙이는 128비트의 부호 없는 정수길이 필드가 필요하다.
• 이 필드에서는 메시지의 길이가 비트수로 표현된 값이 저장된다. 이 길이는 패딩을 하기 전에 원해 메시지의 길이를 나타낸다.
• 

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

(1)MAC의 개요

1)개본개념 

• 메시지 인증을 위해 필요한 것은 메시지 인증코드(MAC: Message Authentication Code)이다. 
• 무결성을 확인하고 메시지에 대한 인증을 하는 기술이다. 거짓변경과 거짓행세 검출 가능. 
• 메시지 인증코드는 임의 길이의 메시지와 송신자 및 수신자가 공유하는 키라는 2개의 입력을 기초로 해서 고정비트길이의 출력을 계산하는 함수이다. 이 출력을 MAC값이라한다.
• 

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

• 변경 감지 코드는 메시지의 무결성을 보장하는 메시지 다이제스트이다. 즉, 해당 메시지가 변경되지 않았다는것을 보장함. 
• Bob는 수신한 메시지로부터 새로운 MDC를 생성하여 Alice로부터 수신된 MDC와 비교한다. 만약 이 두 값이 동일하다면 해당 메시지는 변경되지 않았다는 뜻이 된다.
• 

3)메시지 인증 코드

• 미세지의 무결성은 물론 Alice가 메시지의 원래 전송자이며 다른 사람이 Alice인척 하는 것이 아니라는 것을 말해주는 데이터 출원지 인증을 보장하기 위해 변경 감지 코드를 메시지 인증코드(MAC: Message Authentication Code)로 바꿀 필요가 있다.
• MDC와 MAC의 차이를 살펴보면 MAC에는 Alice 와 Bob사이에 비밀값이 포함된다는 것이다. 예를들어 Eve는 가지고 있지 않은 비밀키가 두 사람 사이의 비밀 값이 될 수 있다. 
• 

4) MAC키의 배송 문제 

• MAC에서는 송신자와 수신자가 키를 공유할 필요가 있다.
• 송신자와 수신자가 키를 공유할 필요가 있다는 것은 대칭키 암호 때의 '키 배송 문제'와 같은 문제가 메시지 인증코드에서도 일어남을 의미한다.

(2)MAC의 구현 사례

1)축소 MAC

• MAC의 안전성을 높이기 위해 축소 MAC(nested MAC)이 설계되었는데 이 안에서는 해싱이 두 단계로 이루어져 있다.
• 첫 번쨰 단계에서 키는 메시지와 이어 붙이고 해시하여 중간 단계의 다이제스트를 생성한다. 2번째 단계에서 키는 중간단계 다이제스트에 이어 붙이고 최종적인 다이제스트를 생성한다.
• 

2)HMAC

• HMAC의 구현절차는 단순화된 축소 MAC보다 훨씬 복잡하다. HMAC에는 패딩같은 추가적인 조치가 더 들어가 있다.
• 
• HMAC은 일방향 해시함수를 이용하여 메시지 인증코드를 구성하는 방법이다. HMAC의 H는 Hashed를 의미한다.

3)CMAC(Cipher-based Message Authentication Code)

• 대칭키 암호 시스템에 대한 암호 블록체인(CBC)모드와 유사한 방법이다. 하지만 여기에서 사용한 아이디어는 N개의 평문블록으로부터 N개의 암호문 블록을 만드는 것이 아니다.
• 

(3)MAC의 이용 예 

1)IPsec

• IP(Internet Protocol)에 보안 기능을 추가한 것임.
• IPsec에서는 통신 인증과 무결성을 확인하기 위해 MAC를 이용 가능.

2)SSL/TLS

• SSL/TLS는 웹에서 온라인 쇼핑을 할 때 사용되는 통신 프로토콜 이다.
• SSL/TLS는 통신 내용의 인증과 무결성 확인을 위해 메시지 인증코드를 이용한다.

(4)MAC에 대한 공격

1)재전송공격 

• 개요 
• 적극적 공격자 멜로리는 자신이 보존해 두었던 MAC값을 반복해서 송신하는 공격을 감행한다. 이와 같은 공격을 재전송 공격(replay attack), 혹은 리플레이 공격이라고 한다.
• 재전송 공격을 막을 수 있는 방법에는 몇 가지가 있다.
• 
• 순서번호
• 송신 메시지에 매회 1회씩 증가하는 번호 (순서번호, sequence number)를 붙이기로 약속하고 , MAC값의 계산에서는 순서번호도 메시지에 포함시키도록 한다.
• 이렇게 해두면 멜로리는 순서본호를 늘렸을 떄의 MAC값을 계산할 수 없기 때문에 재전송 공격을 막을 수 있다. 이 방법은 유효하지만 통신 상대마다 마지막 순서 번호를 기록해 두어야 하는 번거로움이 있다.
• 타임스템프
• 송신 메시지에 현재 시각을 넣기로 약속해두고 그 이전의 메시지가 왔을 경우에는 MAC값이 바르더라도 오류라고 판단한다.
• 송/수신자 사이에 시계를 일치시켜 두는 동기화를 하지 않으면 안된다. 
• 비표(nonce)
• 메시지를 수신하기에 앞서 수신자를 송신자에게 일회용의 랜덤한 값을 전달한다. 이 값을 일반적으로 nonce(비표)라고 한다.
• 송신자는 메시지 안에 비표를 포함해서 MAC값을 계산한다. 비표의 값은 통신때마다 바뀌기 때문에 재전송 공격을 할 수 없다. 이 방법은 유효하지만 통신 데이터의 양은 약간 증가하게 된다. 

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

1) 제 3자에 대한 증명 

• MAC은 공유키를 사용하기에 MAC값을 계산할 수 있는 것은 엘리스 또는 밥이다.두 사람이 서로 통신하고 있는 동안은 '그 MAC값을 계산한 것은 상대' 라고 말할 수 있다. 공유키를 알고 있는 두 사람 중 한 사람은 자신이기 때문이다. 
• 그러나 제 3자 빅터에게 '이 MAC값을 계산한 것은 자신이 아니라 상대'라고 증명할 방법은 없다. 전자서명을 사용하면 제 3자에 대한 증명이 가능해진다. 

2)부인방지

• 송신자 엘리스는 '나는 밥에게 메시지를 보내지 않았다.' 라고 빅터에게 주장 할 수 있다.
• MAC에서를 엘리스와 밥 중 어느 쪽 주장이 맞는지를 판단할 수 없기 때문에 부인방지를 할 방법이 없다. 
• 전자서명을 사용하면 부인방지가 가능해진다.