메시지 무결성과 메시지 인증

메시지 무결성과 메시지 인증  Objectives Chapter 11 Chapter 11 □메시지 무결성 □메시지 인증 □암호학적 해시함수의 기준 □암호학적 해시함수의 안전성 평가를 위한 랜덤 오라클 모델과 역할 □MDC와 MAC의 차이점 □일반 MAC  11-1 MESSAGE INTEGRITY 11-1 MESSAGE INTEGRITY 지금까지 우리가 배운 암호시스템은 적어도 비밀성 혹은 기밀성을 제공한다 . 하지만 무결성은 제공하지 못했다. 그러나 메시지 전송에 있어서 때로는 기밀성 보다는 무결성이 더 중요한 경우가 있다 . Topics discussed in this section: 11.1 문서와 핑거프린트 (Document and Fingerprint) 11.2 메시지와 메시지 다이제스트 (Message and Message Digest) 11.3 차이점 (Difference) 11.4 무결성 점검 (Checking Integrity) 11.5 암호학적 해시함수 기준 (Cryptographic Hash Function Criteria)  11.1.1 문서와핑거프린트(Document and Fingerprint) 11.1.1 문서와핑거프린트(Document and Fingerprint) 문서의 무결성을 보존하는 한 가지 방법은 핑거프린트 (fingerprint) 를 이용하는 것이다. 만약 앨리스가 자신의 문서 내용이 변경되지 않기를 바란다면 문서의 끝부분에 문서의 핑거프린트를 첨부하는 것이다 ..  11.1.2 메시지와메시지다이제스트(Message and Message Digest) 11.1.2 메시지와메시지다이제스트(Message and Message Digest) 문서와 핑거프린트에 해당되는 전자적인 의미에 해당되는 용어는 각각 메시지와 다이제스트이다 . Figure 11.1 메시지와 다이제스트  11.1.3 차이점(Difference) 이 두 개의 쌍인 (문서/핑거프린트)와 (메시지/메시지 다이제스트 )는 아주 유사한 개념이지만 차이점이 있다 . 문서와 핑거프린트는 물리적으로 묶여있다 . 하지만 메시지와 메시지 다이제스트는 물리적으로 볼 때 묶여있지 않으며 따로 보낼 수도 있다 . 더 중요한 것은 메시지 다이제스트는 변경되어서는 안 된다는 것이다 . Note 메시지 다이제스트는 변경되어서는 안 된다 .  11.1.4 무결성 점검 (Checking Integrity) Figure 11.2 무결성 점검  11.1.5 암호학적해시함수기준(Cryptographic Hash Function Criteria) 11.1.5 암호학적해시함수기준(Cryptographic Hash Function Criteria) 암호학적 해시함수는 3 가지 기준을 충족해야 한다 . 이 3 가지는 그림 11.3 에 나타내었듯이 . 프리이미지 저항성 (preimage resistance), . 제 2 프리이미지 저항성 (second preimage resistance), . 충돌 저항성 (collision resistance) 이다. Figure 11.3 암호학적 해시함수의 기준  11.1.5 Continued 프리이미지 저항성 (Preimage Resistance) Figure 11.4 프리이미지  11.1.5 Continued Example 11.1 StuffIt 같은 전통적인 유실이 없는 압축방법을 암호학적 해시함수로 사용할 수 있는가 ? Solution 사용할 수 없다 . 유실이 없는 압축방법은 복구가 가능한 압축 메시지를 생성하는 것이다 . 압축된 메시지를 풀어서 원래의 메시지를 구할 수 있다 . Example 11.2 검사 합 함수를 암호학적 해시함수로 사용할 수 있는가 ? Solution 사용할 수 없다 . 검사 합 함수는 프리이미지 저항성이 없다 . 이브는 주어진 데이터의 검사 합과 동일한 검사 합값을 갖는 여러 개의 다른 메시지를 만들 수 있다 .  제2 프리이미지저항성(Second Preimage Resistance) 11.1.5 Continued 제2 프리이미지저항성(Second Preimage Resistance) 11.1.5 Continued Figure 11.5 두 번째 프리이미지  11.1.5 Continued 충돌 저항성 (Collision Resistance) Figure 11.6 충돌 내성  11-2 RANDOM ORACLE MODEL Bellare 와Rogaway 가1993 년에소개한랜덤오라클모델은해시함수에대한이상적인수학적인모델이다. 11-2 RANDOM ORACLE MODEL Bellare 와Rogaway 가1993 년에소개한랜덤오라클모델은해시함수에대한이상적인수학적인모델이다. Topics discussed in this section: 11.2.1 비둘기집 원리 (Pigeonhole Principle) 11.2.2 생일 문제 (Birthday Problems) 11.2.3 랜덤 오라클 모델에 대한 공격 (Attacks on Random Oracle Model) 11.2.4 구조에 대한 공격 (Attacks on the Structure)  Example 11.3 Example 11.3 오라클이 하나의 표과 동전 한 개로 이루어졌다고 가정해보자 . 이 표는 두 개의 열로 이루어져있다 . 11-2 Continued a. 메시지 AB1234CD8765BDAD 를 가지고 다이제스트를 생성한다고 하자 . 오라클은 일단 표를 점검한다 .  11-2 Continued Example 11.3 Continued 11-2 Continued Example 11.3 Continued a. 메시지 4523AB1352CDER45126 가 다이제스트 생성을 위해 주어졌다고 해보자 . 오라클은 표를 점검하고 이 메시지에 대한 다이제스트가 이미 표에 존재한다는 것을 알아챈다 . 이 오라클은 단순히 대응되는 다이제스트 값인 13AB 를 제공한다 .  11-2 Continued 11-2 Continued Example 11.4 예 11.3 의 오라클에서는 주어진 메시지로부터 다이제스트 생성하는 것을 공식이나 알고리즘을 사용해서 표현할 수 없다 . 예를 들면 , 공식h(M) = M mod n 을 사용하는 오라클이라고 해보자. 오라클은 이미 h(M1) and h(M2) 을 생성해놓았다고 가정해보자. 만약 새로운 메시지가 M3=M1 +M2 라고 해보자 . 오라클은 h(M3) 를 계산할 필요가 없다 . 새로운 다이제스트는 바로 [h(M1) + h(M2)] mod n 이 된다 . 왜냐하면 이기 때문이다. 이것은 각 다이제스트는 오라클에 입력되는 메시지에 대해 랜덤하게 선택되어야 한다는 세 번째 요구조건을 위배하는 것이 된다 .  11.2.1 비둘기 집 원리 (Pigeonhole Principle) 만약에 n+1 마리의 비둘기가 n 개의 비둘기 집에 들어가 있다면 적어도 한 비둘기 집에는 두 마리의 비둘기가 들어있다는 뜻이다 . 일반화된 비둘기 집 원리 버전은 만약 kn + 1 마리의 비둘기가 n 개의 비둘기 집에 들어가 있다면 적어도 한 개의 비둘기 집에는 k+1 마리의 비둘기가 들어가 있어야 한다는 원리이다 .  11.2.1 Continued Example 11.5 해시함수에 적용되는 메시지 길이가 6 비트이고, 다이제스트 길이는 오직 4 비트이다. 그러면 가능한 다이제스트 (비둘기 집 )의 총 개수는 24 = 16 이고, 가능한 메시지 (비둘기)의 총 개수는 26 = 64개다. 이것이 의미하는 것은 n = 16 이고 kn + 1 = 64 이다. 그래서 k 는 3보다 크다 . 결론적으로 하나의 다이제스트는 k + 1=4 개의 메시지와 대응한다 .  11.2.2 Birthday Problems Figure 11.7 4 개의생일문제11.2.2 Birthday Problems Figure 11.7 4 개의생일문제  문제에대한요약된해답(Summary of Solutions) 이런문제에대한해답은흥미를가진독자를위해부록E 에첨부하였다. 그결과에대해서만표11.3 에요약해놓았다. 11.2.2 Continued 문제에대한요약된해답(Summary of Solutions) 이런문제에대한해답은흥미를가진독자를위해부록E 에첨부하였다. 그결과에대해서만표11.3 에요약해놓았다. 11.2.2 Continued  11.2.2 Continued 비교(Comparison) Figure 11.8 4 개의 생일 문제 그래프  11.2.3 Attacks on Random Oracle Model 프리이미지공격(Preimage Attack) Note 11.2.3 Attacks on Random Oracle Model 프리이미지공격(Preimage Attack) Note 프리이미지 공격의 어려움 정도는 2n 에 비례한다 .  11.2.3 Continued Example 11.6 암호학적 해시함수는 64 비트 다이제스트를 사용한다 . 이브는 원래의 메시지를 찾을 확률이 0.5 이상이 되도록 하려면 얼마나 많은 다이제스트를 생성해야 하는가 ? Solution 생성해야 할 다이제스트의수는 k . 0.69 × 2n . 0.69 × 264 이다. 이 수는 매우 큰 수이다 . 비록 이브가 초당 230 (거의 10억)개의 메시지를 생성한다고 하더라도 , 이 수만큼 만들려면 0.69 × 234 초가 걸린다 . 이것은 500년 이상 되는 기간이다 . 이 말이 의미하는 것은 길이가 64비트인 메시지 다이제스트는 프리이미지 공격에 대해 안전하다는 뜻이다 . 하지만 바로 뒤에 보겠지만 충돌 공격에 대해서는 안전하지 않다 .  제2 프리이미지공격(Second Preimage Attack.) 11.2.3 Continued Note 제2 프리이미지공격(Second Preimage Attack.) 11.2.3 Continued Note 제2 프리이미지 공격의 어려움 정도는 2n 에 비례한다.  11.2.3 Continued 충돌공격(Collision Attack)  11.2.3 Continued Note 충돌 공격의 어려움 정도는 2n/2 에 비례한다 .  11.2.3 Continued Example 11.7 한 암호학적 해시함수가 64비트 다이제스트를 사용한다고 하자 . 이브가 동일한 다이제스트를 갖는 서로 다른 두 개의 메시지를 만들 수 있는 확률이 0.5 이상이 되려면 얼마나 많은 다이제스트가 필요한가 ? Solution 생성해야 할 다이제스트의 수는 k . 1.18 × 2n/2 . 1.18 × 232 이다. 만약 이브가 초당 220 의 메시지를 점검할 수 있다면 , 1.18 × 212 초 혹은 2 시간 이내로 끝낼 수 있다는 뜻이다 . 다시 말해서 길이가 64비트인 메시지 다이제스트는 충돌 공격에 안전하지 못하다는 뜻이다 .  또다른충돌공격(Alternate Collision Attack) 11.2.3 Continued Note 또다른충돌공격(Alternate Collision Attack) 11.2.3 Continued Note 또 다른 충돌 공격의 어려움 정도는 2n/2 에 비례한다.  11.2.3 Continued 공격에 대한 요약 (Summary of Attacks) 표 11.4 에 다이제스트의 길이가 비트일 경우에 각 공격에 대한 어려움 정도를 요약해놓았다 .  11.2.3 Continued Example 11.8 64 비트 다이제스트를 가지는 원래의 해시함수 충돌 공격에 저항성을 가지고 있다고 해보자 . 하지만 컴퓨터의 처리 속도가 현격히 증가되고 있기 때문에 많은 사람들이 이런 해시함수가 더 이상 안전하지 않을 거라고 생각하고 있다 . 이브는 확률 1/2 이상을 가지고 공격을 시행할 경우 오직 264/2 = 232 번의 점검만 하면 된다 . 이브가 초당220 번의 점검을 할 능력을 가지고 있다고 하면 232/220 = 212 초 만에 공격을 할 수 있게 된다는 의미이다 . 이 시간은 겨우 한 시간 정도에 해당되는 기간이다 .  11.2.3 Continued Example 11.9 매우 오래 동안 해시함수의 표준으로 사용되고 있는 MD5( 제 12장 참조)는 128 비트 다이제스트를 생성한다 . 충돌 공격을 수행하려면 공격자는 충돌 알고리즘에서 264 (2128/2) 번의 점검을 해야만 한다 . 비록 공격자가 초당 230 번의 점검을 할 수 있다고 하더라도 이것을 수행하려면 234 초(500 년 이상 )가 걸린다 . 이런 공격유형은 랜덤 오라클 모델에 기초하고 있다 . MD5 는 알고리즘의 구조 때문에 264 번의 적은 수의 점검으로 공격이 가능하다는 것이 증명되어있다 .  11.2.3 Continued Example 11.10 NIST가 개발한 표준 해시함수인 SHA-1( 제 12장 참조 )는 160 비트 다이제스트를 생성한다 . 충돌 공격을 수행하려면 공격자는 충돌 알고리즘에서 2160/2 = 280 번의 점검을 해야만 한다 . 비록 공격자가 초당 230 번의 점검을 할 수 있다고 하더라도 이것을 수행하려면 250 초(만년 이상 )가 걸린다 . 그러나 암호학자들은 이 함수의 약점을 발견해냈고 그 결과로 실제 공격에는 위에 계산된 시간보다 짧은 시간에 공격을 할 수 있다는 것을 알아내었다 .  11.2.3 Continued Example 11.11 NIST 표준이 될 새로운 해시함수인 SHA-512( 제 12장 참조 )은 512 비트 다이제스트를 생성한다 . 이 함수는 랜덤 오라클 모델에 기초한 충돌 공경에 저항성을 가지고 있는 것이 분명하다 . 이에 대한 공격은 성공할 확률이 1/2 이상이 되기 위해서 2512/2 = 2256 번의 점검이 필요하다 .  11.2.4 구조에대한공격(Attacks on the Structure) 11.2.4 구조에대한공격(Attacks on the Structure) 공격자가 해시함수를 공격하는 다른 도구를 가지고 있을 수도 있다 . 이러한 도구 중의 하나로서 예를 들자면 우리가 제 6장에서 배운 이중 DES에 대한 중간자 공격(man-in-the middle attack) 이 있다 .  11-3 메시지인증(MESSAGE AUTHENTICATION) 메시지다이제스트는메시지의송신자를인증해주지는못한다. 앨리스가밥에게메시지를보낸다고할때, 밥은메시지가정말로앨리스로부터송신된것인지알고싶을것이다. 암호학적해시함수로생성한다이제스트를일반적으로변경감지코드(modification detection code: MDC) 라고부른다. 메시지인증(데이터출원인증)을위해필요한것은메시지인증코드(message authentication code: MAC) 이다. Topics discussed in this section: 11-3 메시지인증(MESSAGE AUTHENTICATION) 메시지다이제스트는메시지의송신자를인증해주지는못한다. 앨리스가밥에게메시지를보낸다고할때, 밥은메시지가정말로앨리스로부터송신된것인지알고싶을것이다. 암호학적해시함수로생성한다이제스트를일반적으로변경감지코드(modification detection code: MDC) 라고부른다. 메시지인증(데이터출원인증)을위해필요한것은메시지인증코드(message authentication code: MAC) 이다. Topics discussed in this section: 11.3.1 변경 감지 코드 (Modification Detection Code (MDC)) 11.3.2 메시지 인증 코드 (Message Authentication Code (MAC))  11.3.1 Modification Detection Code (MDC) 변경 감지 코드 (modification detection code: MDC)는 메시지의 무결성을 보장하는 메시지 다이제스트이다 . 즉, 해당 메시지가 변경되지 않았다는 것을 보장해준다 . 만약 앨리스가 밥에게 메시지를 보낼때 메시지가 전송 도중에 변경되지 않는다는 것을 확신하려면 앨리스는 메시지 다이제스트인 MDC를 생성하여 메시지와 MDC를 모두 밥에게 보낸다 . 밥은 수신한 메시지로부터 새로운 MDC 를 생성하여 앨리스로부터 수신된 MDC와 비교를 한다 . 만약이두값이 동일하면해당메시지는 변경되지 않았다는 뜻이 된다 .  11.3.1 Continued Figure 11.9 변경 감지 코드 (MDC)  11.3.2 Message Authentication Code (MAC) Figure 11.10 메시지 인증 코드  11.3.2 Continued Note MAC의 안전성은 사용하는 해시 알고리즘의 안전성에 종속된다 .  11.3.2 Continued 축소 MAC(Nested MAC) Figure 11.11 축소 MAC  11.3.2 Continued HMAC Figure 11.12 HMAC 의 자세한 내용  11.3.2 Continued Figure 11.13 CMAC