1. 해시함수란
- One-way hash function(메시지 다이제스트 함수, 메시지 요약함수, 암호학적 해시 함수)에는 입력과 출력이 각각 1개씩 존재.
- 입력은 메시지(프리 이미지), 출력은 해시값(메시지 다이제스트, 핑거프린트) 이라고 함.
- 메시지를 비트열로 취급하며, 비트열을 해시값으로 변환.
- 임의 길이의 메시지로부터 고정 길이의 해시값이 만들어짐.
- One-way 라는 의미는 해시값을 이용해서 다시 원래의 메시지를 만들 수 없다는 뜻.
- 메시지가 다르면 해시값도 다름. -> 무결성
- 다른 메시지 2개로 같은 해시값이 나오면 Collision 발생. 이런 경우에 대비해서 해시함수는 충돌내성(collision resistance)를 가져야 함.
- 무결성 점검은 새로운 해시값과 이전의 해시값(보통 서버에 있음)을 비교해봄으로써 확인되어 짐.
2. 암호학적 해시함수가 가져야할 조건
- 해시값을 만드는 해시함수는 프리이미지 저항성, 제2프리이미지 저항성, 충돌저항성을 만족시켜야 함.
- 프리이미지 저항성(역상저항성, 약 일방향성, Weak onewayness)
해시함수 H와 y=H(M)에 대해 Eve가 y=H(M’)을 만족하는 메시지 M’를 찾아내는 것이 어려워야 한다는 성질.
- 제2프리이미지 저항성(약한 충돌 내성, 강 일방향성, Strong onewayness)
메시지를 쉽게 위조할 수 없도록 하는 성질. Eve가 메시지 M과 다이제스트 H(M)을 가로챘을 때, H(M)=H(M’)을 만족하는 다른 메시지를 생성할 수 없어야 함.
즉, 원래의 M는 못찾으니 H(M)과 같은 값을 갖게하는 M'를 찾는 것을 막는 성질.
- 충돌 저항성(강한 충돌 내성, 충돌 회피성, collision freeness)
Eve가 동일한 다이제스트를 갖는 2개의 메시지를 구하지 못하도록 하는 것.
즉, 해시값은 상관안하고 같은 해시값을 갖는 M와 M'를 찾는 것(생일자 공격)을 막는 것.
* 정리
- 역상저항성은 임의의 출력 값 y에 대해 y=H(x)를 만족하는 입력 값 x를 갖는 것이 계산적으로 불가능 해야 한다는 것.
- 약한충돌내성은 입력 값 x에 대해 H(x)=H(x’), x=x’를 만족하는 x’를 찾는 것이 불가능해야 한다는 것,
- 충돌저항성은 H(x)=H(x’)를 만족하는 임의의 두 입력값 x, x’를 찾는 것이 계산적으로 불가능하다는 것.
3. 일방향 해시함수 응용 예
- 소프트웨어 변경 검출 (무결성 검사)
SW를 입수한 후, 해시값을 계산해서, 오리지널 사이트에서 제공하는 해시값과 비교.
- 메시지 인증코드
메시지 인증 코드란 송신자와 수신자만이 공유하는 키와 메시지를 혼합하여 해시값을 계산한 값. SSL/TLS에서도 사용.
- 전자서명
- 전자입찰
전자입찰의 요구사항: 독립성(시스템 구성요소들은 독자적인 자율성을 지님), 비밀성(개별 정보는 노출돼서는 안 됨),
무결성(입찰 시 입찰자 자신의 정보를 확인하게 하여 누락 및 변조 여부 확인 할 수 있어야 함),
공평성(입찰 시 정보는 공개 되어야 함), 안전성(참여자간 공모는 안됨)
4. 랜덤 오라클 모델
- 랜덤 오라클 모델은 이상적인 해시함수를 기반으로 한 수학적 모델.
같은 입력에 대해 항상 같은 출력 값을 갖으며, 서로다른 입력 값들에 대해 생성된 해시값들은 uniform distribution의 형태를 갖음.
- 비둘기집(pigeon-hole) 원리
n+1마리 비둘기가 n개의 비둘기집에 들어가면 적어도 한 비둘기집에는 두 마리 비둘기가 들어간다는 것.
일반화하면 kn+1마리의 비둘기가 n개의 비둘기 집에 들어간다면 한 집에는 K+1마리의 비둘기가 들어간다.
- 생일 문제(생일 공격)
① 생성한 해시함수가 랜덤 오라클 모델이라고 할때, 이것의 안전성을 비둘기집의 원리와 같은 방법으로 증명하는 것.
② 특정 해시값을 생성하는 메시지를 구하는 것이 아닌 해시값은 상관없이 같은 해시 값을 생성하는 2개의 메시지를 구함. → 강한충돌 내성을 깨고자하는 것.
③ "N명의 그룹이 있을 때, 적어도 2명의 생일이 일치할 확률이 1/2가 되게 하려면 N은 최소 몇명이 되어야 하는가?"
== "n 비트인 h = H(x)가 있을 때, 50% 이상의 확률로 x를 찾으려면 몇번의 횟수가 필요한가?" N=23일 때 확률이 0.507297
* 2014년 가을학기 고려대학교 정보보호이론 "8장 해시 함수 및 메시지 인증" 강의자료를 보면 보다 자세하게 나와있음.
5. 일방향 해시함수에 대한 공격
- 무차별 공격
약한 충돌 내성을 깨는 것. SHA-1의 경우 해시값이 160비트이므로 2^160회를 시행하면 원하는 메시지가 발견될 것이라 생각하고 공격함.
- 일치블록 연쇄 공격: 새로운 메시지를 여러개 만들어서 공격하고자 하는 메시지 M의 해시함수 값 H(M)과 같은 것을 골라 사용하는 것.
- 중간자 연쇄공격
해시 중간의 결과에 대한 충돌쌍을 찾아 내는 것.
- 차분 연쇄공격
해시함수의 경우 압축함수 방법이므로 입출력 차이를 조사해 0의 충돌쌍을 주로 찾아내는 것.
다중 라운드 블록함수의 경우 입력값과 출력값의 차이를 통계적으로 분석하여 공격하는 방법.
6. 일방향 해시함수로 해결 못하는 문제
- 조작과 변경(원래의 M이 조금이라도 바뀌면 해시값이 달라짐)은 검출하지만 거짓행세를검출 하지 못함.
- 무결성 뿐만 아니라 이 파일이 정말 앨리스의 것인지를 확인하려는 경우에는 인증 절차가 필요함.
- 인증을 위해서는 메시지 인증코드와 전자서명을 사용해야 함.
7. 암호학적 해시함수의 예
- 해시함수 설계 방법
① 압축함수를 목적에 맞춰 개발.
② 압축함수자리에 대칭키 블록암호 사용
- 압축함수를 목적에 맞춰 개발
① MD(메시지 다이제스트) 방식
MD 2, 4(뚫림), 5가 있으며, 공개키 기반 구조를 만들기 위해 RSA와 함께 개발됨.
MD2는 8비트 4,5는 32비트 컴퓨터에 최적화. MD5는 메시지를 512비트로 된 블록으로 나누고, 128 다이제스트를 출력. 하지만
너무 짧아 충돌 공격에 내성이 약함.
② SHA(Secure Hash Algorithm) (=FIPS PUB 180)
NIST가 개발. SHA-1은 SHA의 약점을 보완한 것. SHA-1는 메시지 길이에 상한 존재.
512비트 블록단위로 처리, 160비트 메시지 다이제스트 출력, MD5 구조 및 유사한 처리 방식을 가짐.
FIPS PUB 180-2는 해시값이 256, 384, 512 비트를 출력함. 각각 SHA-256, SHA-384, SHA-512로 불림.
추후에 FIPS PUB 180-3(해시값이 224비트인 버전)이 추가됨.이들을 SHA-2라고 함.
* SHA-1은 강한 충돌 내성이 깨짐. SHA-3을 만들고 AES와 같은 방식으로 표준화함.
* SHA-512: 다중 블록 메시지로부터 512비트 다이제스트 생성. 각 블록은 1024비트. 다이제스트 생성 전 128비트 정수 필드에
오리지널 메시지 길이를 넣고, 나머지 공간에 패딩을 넣음.
즉, 1024 블록에서 2^128이 오리지날 메시지 비트, 128비트는 오리지널 메시지 길이 정보, 나머지는 패딩.
* 블록체인에 SHA 256 사용됨.
* 참고 할만한 사이트
1. http://m.blog.naver.com/tpinlab/10121517078 (암호학적 해시함수에 대한 블로그. 굿.)
2. http://d2.naver.com/helloworld/318732 (자세한 설명이 부족함)
3. http://d2.naver.com/helloworld/744920 (전자서명 설명하면서 해시 부분이 살짝 나옴.
이글을 읽으면 좋을 듯.)
8. MDC(메시지 변경 감지 코드) - 무결성
- 메시지의 무결성(메시지가 변하지 않았다는 것.) 보장하는 메시지 다이제스트.
- 수신한 메시지의 MDC를 계산하고 송신측이 보내준 MDC와 비교하여 동일한지 비교함.
- 과정
① 메시지의 무결성을 제공하기 위해서 송신자 A는 송신할 메시지를 이용하여 메시지 다이제스트(암호학적 해시함수를 이용한 해시값)를 만듦.
이때 생성된 메시지 다이제스트를 일반적으로 MDC라고 부름.
② 송신자 A가 메시지와 MDC를 수신자 B에게 보냄.
③ 수신자 B는 받은 메시지로 MDC를 만들고, 송신자 A가 보낸 MDC와 비교하여 메시지의 무결성을 확인함.
- 문제: 무결성은 인증가능 하지만 누가 보냈는지에 대한 메시지 출원인증이 안됨. → 즉, 메시지의 위조같은 적극적 공격은 메시지 인증으로 검출해야 함.
위의 그림을 보면 MDC는 신뢰성있는 채널을 통해 MDC가 전송된다는 가정을 한다.
따라서 MDC를 위해서는 신뢰성있는 채널이 있어야 만된다는 제약이 있으며, 그렇지 않으면 제 3자가 메시지를 위조해도 알아차리지 못하게 된다.
- 해결: MAC
9. MAC(메시지 인증코드, Message Authentication Code)의 개념
- MAC은 해시함수 + 대칭키로 메시지 무결성을 인증하고 거짓행세(메시지 인증으로 검출)를 검출.(메시지 인증: 올바른 송신자에게 온것을 인증하는 것)
- 무결성을 확인하고 메시지에 대한 인증을 하는 기술. -> 도청(소극적 공격) 방어, 변경과 거짓행세 검출 가능
- 임의 길이의 메시지와 송신자 및 수신자가 공유하는 키. 두 개를 입력으로 하여 고정 비트길이의 출력을 만드는 함수. 이 출력값을 MAC이라고 함.
- 적극적 공격인 데이터 위조 같은 것을 방어하는데 사용.
- 키 K는 오직 송,수신자만 알고 있음.
- 아래 그림에서 해시 함수 H에는 H(K||M) 처럼 두 개의 값이 입력되고 해시값 MAC이 생성됨.
H(K||M||K') 같이 다른 키를 붙여도 됨. (단, 이 경우에도 송수신자가 K, K'를 알고 있어야함.)
10. MAC의 안전성
- MAC의 안전성은 사용되는 해시함수의 안전성과 같음.
11. MAC 종류
- MAC의 안전성을 높이기 위한 방법들임.
- 축소 MAC(Nested MAC)
① 최종 MAC을 생성하기 위해 두번의 해시함수를 거침.
② -1. H(K||M)을 통해 1차 다이제스트 M1을 생성 함.
-2. H(K||M1)을 통해 2차(최종) 다이제스트를 생성함.
- HMAC(Hash MAC)
Nested MAC의 표준을 만들었는데 그것이 HMAC. 좀더 복잡하며, n 비트의 패딩을 붙이고 두번의 해싱 단계를 거친다.
- CMAC(Cipher-based Message Authentication Code, CBMAC, FIPS 113
대칭키 암호시스템의 암호 블록체인(CBC)모드와 유사한 표준.
메시지를 N개의 블록으로 나누고 키와 블록 1번부터 N번까지 각 블럭과 암호화 기법을 적용한 후 다음번 블록과 XOR를 적용. 이 것을 마지막 N번 블록까지 수행.
* 키 생성: 0으로 이루어진 m비트의 블록을 비밀키 K로 암호화하여 패딩이 적용되지 않았을 경우 x를 곱하고 패딩이 적용되면 x^2을 곱함.
* 참고: http://pds15.egloos.com/pds/201001/19/02/MAC_by_eyestorys.pdf
 |
| <CMAC 동작 방식> |
12. MAC 사용의 예
- IPSec
IP 계층에서 보안 기능을 추가할 때 사용. 통신 내용의 인증, 무결성 제공하기 위해 MAC을 사용.
- SSL/TLS
웹에서 온라인 쇼핑시 사용되는 통신 프로토콜, 인증, 무결성 확인을 위해 MAC을 사용.
13. MAC의 키 배송 문제
- MAC에서는 송신자와 수신자가 키를 공유해야 함. 이를 위해 대칭키 암호화 방식에서 처럼 키 배송 문제가 일어남.
14. MAC 공격 방법 예
- 재전송 공격(replay 공격): 적극적 공격자 멜로리는 저장해둔 MAC값을 반복해서 송신.
- 방어방법
① 순서번호
송신 메시지에 순서번호를 붙이면서, MAC 값의 계산에서는 순서번호도 메시지에 포함시킨다.
② 타임스탬프
송신 메시지에 현재 시각을 넣음. 이전 메시지가 오면 MAC값이 바르더라도 오류로 판단. 단, 송수신자 사이에 타임 동기화 필요.
③ 비표(nonce)
메시지 수신전, 수신자가 송신자에게 일회용 랜덤 값(비표) 전송. 송신자가 메시지 안에 비표를 넣어 MAC값을 계산. 매번 비표가 바뀌므로 재전송 공격이 막힘.
15. MAC으로 해결 못하는 문제
- 제3자에 대한 증명
앨리스로부터 메시지를 받은 밥이 메시지가 정말 앨리스가 보낸 것이라는 것을 제 3자인 검증자 빅터에게 증명할 수 없음.
증명하기 위해선 공유키(앨리스와 밥이 공유하고 있는 키)를 빅터에게 알려줘야만 하고,
공유키는 앨리스와 밥이 가지므로 둘 중 누가 메시지를 작성했는지 검증할 수 없음.
- 부인 방지
밥이 MAC과 함께 메시지를 받고, 메시지가 앨리스로부터 온것이라는 것은 확실히 증명이 가능함.
하지만 앨리스가 전송 자체를 부정할 경우 제 3자에게 이를 증명할 수 없음.
즉, 앨리스가 송신자체를 부인(repudiation)하는 것. 따라서 MAC으로는 부인 방지를 할 방법이 없음.
- 해결방법
전자서명: 공개키기반이므로 송신자는 자신의 개인키로 메시지에 서명하고, 수신자는 송신자의 공개키로 서명을 검증하여 부인방지를 함.
* 참고
- http://cafe.naver.com/algisa/102213
16. 메시지 인증 방법 종류
- 메시지 인증 이란?
수신자가 받은 메시지가 송신자가 보낸 메시지와 동일한 것인지를 확인 하는 것.
메시지 내용 변경, 순서 변경, 삭제 및 불법행위를 탐지 하는 것.
- 관용(대칭키) 암호화 방식
평문을 미리 갖고 있던 비밀키로 암호화 하여 암호문을 수신자에게 전송하면 수신자도 암호문을 비밀키로 복호화하는 것.
복호화한 문장으로 메시지 변경 여부 확인.
- 공개키 암호화 방식
누구나 메시지 인증 검사를 할 수 있지만, 개인키를 아는 송신자만 인증을 생성할 수 있으므로 제 3자가 송신자를 가장하여 메시지 전송이 불가.
- 해시 함수를 이용한 메시지 인증 방식
메시지로부터 해시 함수 결과 값을 계산하고 수신한 해시값과 비교해 무결성 검증 함.
하지만 제 3자의 위조 인증을 인지를 알 수 없는 단점이 있음.
(제 3자가 공개된 해시 함수로 만든 위조된 메시지를 전송했을 때의 문제를 말함.)
따라서 비밀 정보를 해시함수에 추가하여 메시지와 함께 해시함수의 입력으로 사용.
여기서 수신자는 수신한 메시지와 공유한 비밀정보로 해시함수 계산하고 수신한 해시함수 값과 비교하여 메시지 인증 수행.
- MAC을 이용한 메시지 인증 방식
MAC은 관용 암호방식을 이용하여 무결성 검증 코드를 만들어 메시지에 부가하는 방법.
송신자가 인증할 메시지를 비밀키로 암호화 하고 MAC 값을 계산한 후 메시지와 함께
수신하여 메시지를 인증함.
댓글 없음:
댓글 쓰기