해시함수
해시함수는 임의의 길이를 갖는 메시지를 입력으로 하여 고정된 길이의 해시값 또는 해시 코드라 불리는 값을 출력하는 함수이다. 해시 함수는 다대일 대응 함수이기 때문에 충돌이 반드시 존재한다.
앞에서의 공개키 암호, 비밀키 암호가 기밀성을 지키기 위해 사용되었다면 이번 해시함수는 무결성을 확인하기 위해 사용된다.
일방향 해시함수의 특징
1. 임의 길이의 메시지로부터 고정 길이의 해시값을 계산한다.
2. 해시값을 고속으로 계산할 수 있다.
3. 일방향성을 갖는다. (역산 불가)
4. 메시지가 다르면 해시값도 다르다.
해시함수의 보안 요구사항
해시함수는 프리이미지 저항성, 제2프리이미지 저항성, 충돌 저항성의 3가지 기준을 충족해야 한다.
- 프리이미지 저항성(역상 저항성)
해시값 h = H(x) 에 대하여 x는 h의 선 이미지(preimage)라 한다. 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로 하여금 동일한 다이제스트를 가지는 2개의 메시지를 구하지 못하도록 하는 것이다. 공격자는 어떠한 정보도 없는 상태에서 단지 동일한 다이제스트를 갖는 두 개의 메시지를 생성할 수 있다.
제2프리이미지와 조금 헷갈릴 수 있는데 제2프리이미지는 주어진 다이제스트 H1에 대해 동일한 다이제스트 값을 갖는 메시지를 찾아내기 어렵게 하는 것이고, 충돌 저항성은 그저 동일한 다이제스트를 갖는 두 개의 메시지만 찾아내기 어렵게끔 하는 것이다.
충돌 저항성은 두 번째 역상 저항성을 보장하지만 역상 저항성을 보장하지 못한다. 두 번째 역상 저항과 역상 저항은 서로를 보장하지 못한다.
반복 해시함수
모든 해시함수는 입력되는 메시지의 크기와 상관없이 항상 일정한 크기의 다이제스트 값을 내놓아야 한다.
이런 함수를 만드는 가장 좋은 방법은 반복을 사용하는 것이다. 입력의 길이가 다양한 해시함수 대신에 고정 길이의 입력을 필요로 하는 함수를 만들고 필요한 만큼 반복해서 사용하는 것이다.
Merkle-Damgard 구조는 현재 사용되는 많은 암호학적 해시함수 구조의 기본 틀이다. 충돌 내성을 갖는 압축함수를 설계해서 이 구조 속에 집어넣기만 하면 된다.
키가 없는 해시함수
- 전용 해시함수
오늘날 사용되고 있는 전용 해시함수인 SHA-1, RIPEMD, RIPEMD-128, RIPEMD-160, HAVAL 등은 모두 MD4를 기초로 디자인 했다.
① 메시지 다이제스트 (Message Digest)
MD 알고리즘에는 MD2, MD4, MD5 이렇게 3가지가 있다.
최종 버전인 MD5는 메시지를 512비트로 된 블록들로 나누고 128비트 다이제스트를 출력한다. 현재 128 다이제스트 값은 충돌 공격에 내성을 갖기에는 너무 짧다고 알려졌다. 또한 MD5 내부 구조에 몇 가지 약점이 발견되고 강한 충돌 내성을 공격하는 Birthday Attack에 노출되어 보안 요구사항이 높은 곳에는 사용이 권장되지 않는다.
② SHA (Secure Hash Algorithm)
가장 널리 사용되는 해시함수 SHA는 DSS에 사용하기 위해 NSA가 설계하였다. NIST는 새 표준인 FIPS 180-2를 내놓았는데 이때 해시값이 256,384,512비트인 3가지 새로운 SHA 버전을 정의했다. 이들을 SHA-2라고 부른다.
SHA-2는 SHA-1과 하부구조가 동일하며 동일한 유형의 모듈러 연산과 논리적 2진 연산을 이용한다.
2005년에 SHA-1의 강한 충돌 내성이 깨져 NIST는 차세대 일방향 해시함수 SHA-3(Keccak)을 제정하였다. AES와 같은 방식으로 표준화 됨
③ RIPEMD-160
RIPEMD도 여러 개의 버전으로 되어 있다. 160비트 메시지 다이제스트를 생성하며 RIPEMD의 강한 충돌 내성은 깨졌지만 RIPEMD-160은 아직 깨지지 않고 비트코인에서 이용 중이다.
④ Tiger
64비트 시스템에서 해시 함수를 수행하기 위해 설계되었고, MD5, SHA-1 보다 속도가 빠르다
⑤ HAVAL
HAVAL은 길이가 128, 160, 192, 224, 256 비트인 메시지 다이제스트를 출력하는 가변 길이 해시 알고리즘이고 사용되는 블록의 크기는 1024비트이다.
- 블록 암호 기반 해시함수
반복 암호학적 해시함수 안에 사용되는 압축함수 자리에 대칭키 블록암호를 사용할 수 있다. 그러면 일부러 새로운 압축함수를 만들 필요 없이 DES나 AES처럼 검증된 여러 개의 대칭키 알고리즘을 일방향 함수로 사용할 수 있기 때문이다. 당연히 복호화할 필요가 없으니 암호화 기능만 사용한다.
- 모듈 연산에 기반을 둔 해시함수
모듈 연산에 기반을 둔 해시함수는 압축 함수의 기반을 모듈 연산의 반복적인 수행에 두고 있는 해시함수를 말한다. 하드웨어나 소프트웨어 자체 내장된 모듈 연산을 사용할 수 있다는 장점이 있으나 속도가 빠르지 않고 안전성 연구에 대한 역사가 짧다.
키를 사용하는 해시함수
키를 사용하는 해시함수는 메시지 인증 기능을 가진 함수이다. 일반적인 해시함수와는 달리 키를 사용하는 해시함수는 함수 자체의 안전성과 키의 비밀성에 그 안전성을 두고 있다.
랜덤 오라클 모델
랜덤 오라클 모델은 해시함수에 대한 이상적인 수학적 모델이다. 이 모델에 근거한 해시함수는 아래의 성질을 갖는다.
·임의의 길이를 갖는 메시지에 오라클은 0과 1로 이루어진 난수 스트링인 고정된 길이의 메시지 다이제스트를 생성해서 제공한다.
·이미 다이제스트가 존재하는 메시지가 주어지면 오라클은 저장되어 있던 다이제스트를 제공한다.
·오라클은 다이제스트를 만들기 위해 공식이나 알고리즘을 사용해서는 안 된다.
- 비둘기집 원리
n+1 마리의 비둘기를 n 개의 비둘기 집에 집어넣는다면 적어도 한 비둘기집에는 두 마리의 비둘기가 들어가 있다. --> 충돌
- 생일 공격(Birthday Attack)
특정한 해시값을 생성하는 메시지를 구하는 것이 아니라 해시값은 뭐든지 괜찮으며 같은 해시값을 생성하는 2개의 메시지를 구하는 것이다. -> 강한 충돌 내성을 깨고자 하는 공격
- 랜덤 오라클 모델에 대한 공격
무차별 공격에 대한 해시함수 강도는 전적으로 알고리즘이 생성하는 해시코드의 길이에 달려있다.
n비트 해시코드에 대한 공격 난이도를 보면
프리이미지,2차 프리이미지 저항성의 공격 난이도 => 2n
충돌 저항성의 공격 난이도 => 2n/2
일방향 해시함수에 대한 공격
- 무차별 공격
일방향 해시함수의 2차 프리이미지 저항성을 깨고자 하는 공격이다.
- 일치블록 연쇄공격
새로운 메시지 M'를 사전에 다양하게 만들어 놓았다가 공격하고자 하는 메시지 M의 해시함수값 h(M)과 같은 해시함수값을 갖는 것을 골라 사용하는 공격이다.
- 중간자 연쇄공격
전체 해시값이 아니라 해시 중간의 결과에 대한 충돌쌍을 찾는다.
- 고정점 연쇄공격
메시지 블록과 연쇄변수 쌍을 얻게 되면 연쇄변수가 발생하는 특정한 점에서 임의의 수의 동등한 블록들을 메시지 중간에 삽입해도 전체 해시값이 변하지 않는다는 점을 이용한 공격
- 차분 연쇄공격
다중 라운드 블록암호를 사용하는 해시 함수에서는 입력값과 그에 대응하는 출력값의 차이의 통계적 특성을 조사한다.
해시함수를 사용하는 경우는 압축함수의 입출력 차이를 조사하여 0의 충돌쌍을 주로 찾아낸다.
SHA-512
SHA-512는 다중 블록 메시지로부터 512비트 다이제스트를 생성한다. 각 블록은 1024비트 길이를 가진다. SHA-512는 워드 단위로 계산된다. 각 블록은 16개의 워드로 이루어지며 다이제스트는 오직 8개의 워드로 이루어진다.
메시지 다이제스트를 생성하기 전에 SHA-512에서는 메시지에 추가적으로 덧붙이는 128비트의 부호 없는 정수 길이 필드가 필요하다. 이 필드에서는 메시지 길이가 비트수로 표현된 값이 저장된다. 메시지 길이 필드는 공격자가 해시값이 같으면서 입력값이 다른 메시지를 찾는 것을 어렵게 만드는 보안 요소이다.
블록이 1024비트를 가지기 때문에 원래의 메시지와 메시지 길이 필드 사이에 패딩값이 포함된다.
SHA-512의 충돌 저항성을 깨기 위한 난이도는 2256번의 연산을 수행해야 하며 약점을 지적한 연구 보고서는 없다고 한다. 하지만 충돌이 깨진 SHA-1의 하부 구조를 동일하게 가지고 있으며 수학적으로도 동일하기 때문에 우려는 나오고 있다.
일방향 해시함수로 해결할 수 없는 문제
일방향 해시함수는 조작과 변경을 검출할 수 있지만 거짓행세를 검출하지는 못한다. 파일의 무결성을 조사하는 것뿐만 아니라 이 파일이 정말로 앨리스 것인가를 확인하고 싶은 경우 무결성 외에 인증이라는 절차가 필요해진다.
인증을 수행하기 위한 기술이 메시지 인증코드와 전자서명이다.
메시지 인증 코드(MAC)
메시지 인증코드란 무결성을 확인하고 메시지에 대한 인증을 하는 기술이다. 메시지 인증코드는 임의 길이의 메시지와 송신자 및 수신자가 공유하는 키라는 2개의 입력을 기초로 고정 비트길이의 출력을 계산하는 함수이다.
MAC의 장점은 블록 암호나 해시 함수에 기반을 두기 때문에 전자 서명보다 훨씬 빠르다.
- 변경 감지 코드 (MDC, Modification Detection Code)
변경 감지 코드는 메시지의 무결성을 보장하는 메시지 다이제스트이다. (평범한 해시 값이라고 보면 됨)
Bob은 수신한 메시지로부터 새로운 MDC를 생성하여 Alice에게 받은 MDC와 비교한다. 이 두 값이 동일하다면 메시지가 변경되지 않았다는 뜻이 된다.
- 메시지 인증 코드 (MAC, Message Authentication Code)
메시지의 무결성은 물론 Alice가 원래 전송자이며 다른 사람이 Alice인 척 하는 것이 아님을 말해주는 인증을 보장해준다.
MDC는 단순히 메시지를 해시 값으로 변환하여 비교하지만 MAC는 비밀키를 이용해 해시 처리 하므로 상대방을 보장해줄 수 있다.
MAC는 대칭키를 사용하는 해시함수이므로 이 역시 키 배송 문제가 발생된다.
MAC 구현 사례
- 축소 MAC (nested MAC)
MAC의 안전성을 높이기 위해 설계된 축소 MAC은 해시를 두 단계 처리 한다.
먼저 키에 메시지를 붙이고 해시 처리하여 생성된 다이제스트 값을 한 번 더 키를 붙이고 해시 처리를 하여 최종적인 다이제스트를 생성한다.
- HMAC
HMAC은 SHA-1과 같은 일방향 해시함수를 이용하여 메시지 인증코드를 구성한다. 일방향 해시함수가 안전하면 뭐든지 사용할 수 있다.
- CBC-MAC, CMAC (해시 알고리즘 사용하지 않음!!)
CBC 모드와 유사한 방법이지만 N개의 평문 블록으로 N개의 암호문 블록을 만들지 않고 대칭키 암호를 N번 사용해서 N개의 평문 블록에서 하나의 MAC을 생성해낸다.
CBC-MAC은 보안 논점이 발견되어 CMAC이 만들어졌다.
- CCM(Counter with CBC-MAC)
CTR과 CBC-MAC을 통합한 CCM 암호 모드는 동일한 키의 사용을 통해 기밀성과 인증, 무결성을 제공한다.
CCM의 핵심적인 알고리즘 구성요소는 AES, CTR 운용모드, CBC-MAC 인증 알고리즘이다.
- GCM
CTR 모드에 인증을 추가한 GCM(Galois/Counter)가 있다.
암호문을 생성함과 동시에 인증 정보를 만들어 내는 구조이다.
MAC에 대한 공격 - 재전송 공격
단순한 메시지 인증코드는 공격자의 Replay 공격을 방지할 수 없다. 공격자는 전송중인 메시지와 메시지 인증코드를 스니핑한 다음 수신자에게 전송해도 수신자는 이를 구별할 수 없다.
재전송 공격을 막기 위해서 순서번호, 타임스탬프, 비표, 시도/응답 등을 사용한다.
- 순서 번호 (Sequence number)
송신 메시지에 매회 1회씩 증가하는 번호를 붙이기로 약속하고 MAC 값의 계산에서도 순서번호를 메시지에 포함시킨다.
Mallory(Malicious / 악의적 공격자)는 순서번호를 늘렸을 때의 MAC 값을 계산할 수 없기 때문에 재전송 공격을 막을 수 있다. 다만 통신상대마다 마지막 순서번호를 기록해두어야 하는 번거로움이 있다.
- 타임스탬프 (timestamp)
송신 메시지에 현재 시각을 넣기로 약속해두고 이전의 메시지가 왔을 경우에는 MAC 값이 바르더라도 오류라고 판단한다.
송·수신자 사이에 동기화를 해야 한다.
- 비표 (nonce)
메시지를 수신하기 전에 수신자는 송신자에게 일회용의 랜덤 값을 건네준다. 이 값을 비표(nonce)라 부른다.
송신자는 메시지 안에 비표를 포함하여 MAC 값을 계산한다. 비표 값은 통신 때마다 바뀌기 때문에 재전송 공격을 할 수 없다.
- 시도/응답 (Challenge/Response)
A가 B에게 우선 난수/시도 를 송신한 다음, B로부터 수신되는 메시지/응답이 정확한 난수 값을 포함할 것을 요구한다.
MAC으로 해결할 수 없는 문제
1. 제3자에 대한 증명
MAC은 공유키를 사용하기에 MAC 값을 계산할 수 있는 것은 Alice 또는 Bob이다. 그러나 제3자 Victor(증명자)에게 이 MAC 값을 계산한 것이 자신이 아닌 상대방이라고 증명할 방법이 없다. 전자서명을 사용하면 제3자에 대한 증명이 가능해진다.
2. 부인 방지
송신자 Alice는 Bob에게 메시지를 보낸 후 Victor에게 Bob에게 메시지를 보내지 않았다고 주장할 수 있다.
MAC에서는 Alice와 Bob 중에서 어느 쪽 주장이 맞는지 판단할 수 없기 때문에 부인방지(nonrepudiation)를 할 방법이 없다. 역시 전자서명을 사용하면 부인방지가 가능하다.