해쉬함수를 이용한 MAC의 구성 2006. 12. 21. 윤 아 람 aaram@etri.re.kr.

Presentation on theme: "해쉬함수를 이용한 MAC의 구성 2006. 12. 21. 윤 아 람 aaram@etri.re.kr."— Presentation transcript:

1 해쉬함수를 이용한 MAC의 구성 윤 아 람

2 목 차 1 해쉬함수와 MAC 2 HMAC 3 Merkle-Damgard 4 EMD 5 OMD 6 결론

3 해쉬함수를 이용한 MAC의 구성 1 해쉬함수와 MAC 2 HMAC 3 Merkle-Damgard 4 EMD 5 OMD 6 결론

4 해쉬함수란? 임의 길이의 비트열을 특정 길이의 비트열로 대응시키는 함수 용도 해쉬 값은 원래 메시지의 일종의 ‘지문’ 역할
대표적인 예: MD5, SHA-1, HAS-160 등 일반적인 출력 길이: 160비트, 256비트, 512비트 등 용도 컴퓨터에서 패스워드를 직접 저장하지 않고 그 해쉬값을 저장 패스워드를 비교하지 않고 그 해쉬값을 비교하여 사용자를 인증 공격자가 저장된 패스워드 파일을 훔쳐도 무용지물 긴 메시지를 직접 전자서명하지 않고 해쉬값을 서명함 서명의 계산량이 크기 때문에 짧은 해쉬값을 서명하는 것이 쉬움

5 MAC이란? MAC = Message Authentication Code (메시지 인증 코드)
특정 비밀키를 공유하고 있는 사용자들끼리 주고받는 메시지의 무결성을 확인하기 위한 수단 비밀키와 임의 길이의 메시지  특정 길이의 MAC 즉, 해쉬함수: h = H(m) MAC: x = Mk(m) 용도 메시지 m을 전송할 때 m 뿐만 아니라 t=Mk(m)를 같이 전송: (m, t) 전송  수신자는 m을 받아본 뒤 직접 Mk(m)를 계산하여, 수신된 t와 같은지 확인 즉, 메시지가 중간에 위조된 것인지의 여부를 확인하는 것이 목적 K를 모르는 공격자는 m과 t 간의 올바른 대응관계를 찾을 수 없음

6 MAC이란? MAC MAC = ? MAC MAC K K

7 Forger의 시도 MAC MAC MAC MAC HAM ≠ K K

8 해쉬함수와 MAC의 차이 ‘signature’가 다름 목적이 다름 전혀 다른 안전성 개념에 기초하고 있음
MAC을 ‘keyed hash function’이라고 부르기도 함 즉, 해쉬함수는 비밀키가 필요 없이 누구나 메시지로부터 계산 가능 MAC은 기본적으로 비밀을 공유한 사람들만 계산 가능 목적이 다름 해쉬: 긴 메시지를 대신해서 다양한 암호학적 기능에 이용될 수 있는 ‘지문’을 채취하는 것이 목적 MAC: 긴 메시지가 제대로 된 메시지라는 증명을 제공하는 것이 목적 전혀 다른 안전성 개념에 기초하고 있음

9 해쉬함수의 안전성 암호학적 해쉬함수는 최소한 다음의 세 가지를 만족해야 함
Preimage resistance: h=H(m)이 주어졌을 때 m을 찾기 어려워야 함 2nd preimage resistance: m에 대해, H(m)=H(m’)인 m’을 찾기 어려워야 함 패스워드 저장 방식을 생각하면 필요함 Collision resistance: H(m)=H(m’)인 메시지 쌍 m, m’을 찾기 어려워야 함 서명 방식을 생각하면 필요함

10 해쉬함수의 안전성 해쉬함수의 안전성 정의는 보기보다 단순하지 않음 세 가지가 필요한 전부인가?
참조: P. Rogaway, Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys, Vietcrypt 2006 세 가지가 필요한 전부인가? ‘지문’이 원 메시지를 대체하기 위해 가져야 할 성질은? 응용 따라 다른가? 본질적으로 ‘장볼 목록’같은, 불만족스러운 정의임 타 암호 프리미티브는 이보다 체계적인 안전성 정의를 가지고 있음 시장 가서 사올 것 콩나물 두부 세제 편지 부치는 것 잊지 말기

11 랜덤 함수로서의 해쉬 함수? “좋은 해쉬함수는 일종의 랜덤함수처럼 행동해야 한다”
즉, 전혀 인위적인 구조가 드러나지 않아야 한다 랜덤함수는 좋은 해쉬함수임은 분명함 preimage resistance, 2nd preimage resistance, collision resistance 모두 만족 하지만, public deterministic function이 랜덤함수처럼 행동해야 한다는 말이 대체 무슨 소리인가? “abc”의 SHA-1 값은 03cfd743661f07975fa2f1220c5194cbaff48451임 (“abc”의 ASCII 값에 해당하는 비트열의 SHA-1 값) F가 랜덤 함수일 때 F(“abc”)=03cfd743661f07975fa2f1220c5194cbaff48451일 확률: 2-160 F가 SHA-1일 때 F(“abc”)=03cfd743661f07975fa2f1220c5194cbaff48451일 확률: 1

12 랜덤 함수란? 랜덤 함수 랜덤 함수를 보는 다른 방법: ‘lazy sampling’ Domain X, Codomain Y
Fun(X, Y): the set of all functions from X to Y A random function from X to Y: an element randomly chosen from Fun(X, Y) With uniform probability on Fun(X, Y) 랜덤 함수를 보는 다른 방법: ‘lazy sampling’ 랜덤 함수 F:X  Y를 구현하는 방법 처음에는 임의의 x에 대해 F(x)=undefined F(x)를 실제로 evaluate할 때, 만일 F(x)=undefined이면 Y의 원소 y를 랜덤하게 골라 (under uniform distribution) F(x)=y로 정의 만일 F(x)가 정의되어 있으면, 이미 정의된 값을 출력 Lazy sampling은 X가 finite domain일 때 위의 정의와 동등 X가 infinite domain일 때에도 엄밀하게 정의 가능: integrability도 필요 없음

13 Random Oracle Model Random oracle = public random function 즉, 적법한 사용자든 공격자든 누구든 질의해볼 수 있는 함수 Random oracle model: random oracle이 주어졌다고 가정하고, random oracle을 이용해서 실제의 해쉬 함수를 모델링함 Random oracle methodology: random oracle을 이용해서 암호 시스템의 안전성을 증명하고, 실제 구현 시에는 random oracle 대신 구체적인 해쉬함수로 대체 종종, random oracle을 가정하지 않은 대신 엄밀한 증명을 제공하는 시스템이 매우 비효율적인데 비해, 이보다 훨씬 가볍고 최소한 random oracle model에서 증명 가능한 암호 시스템들이 있음

14 MAC의 안전성 일차적으로, 위조 공격에 대한 안전성이 기본적인 정의임 공격자의 능력을 과대평가하는, 매우 보수적인 정의임
공격자 A는 randomized algorithm이라고 가정 A는 비밀키 k를 몰라도 q회의 질의를 통해 자신이 원하는 메시지 m1, …, mq에 대한 MAC Mk(m1), …, Mk(mq)를 얻어낼 수 있음 이 과정을 거친 후 A가 어떤 메시지 m과 그 MAC 값 Mk(m)를 얻어낼 수 있으면 A는 MAC 위조에 성공한 것으로 간주 단, m은 A가 query한 m1, …, mq와 달라야 함 Adv(A) = Pr[ A가 위조에 성공] Adv(t, q) = t라는 계산 시간과, q 회의 질의를 하는 모든 공격자 A에 대한 Adv(A)의 최대값 공격자의 능력을 과대평가하는, 매우 보수적인 정의임

15 MAC의 안전성 구별 공격에 대한 안전성 주장: MAC은 단순히 위조가 잘 안되는 것으로는 부족하다. 랜덤 함수처럼 행동해야 한다. 즉, 공격자는 위조를 시도하는 Mk(m)의 어떤 비트에 대해서도 어떤 아이디어도 얻을 수 없어야 한다. 고작 찍는 것이 최선이어야 한다. 예: Mk(m)이 위조 공격에 대해 안전한 MAC이면, M’k(m) = Mk(m) || 0으로 정의 M’k(m)도 위조 공격에 대해 안전  M’k(m) 는 좋은 MAC임 M’k(m)는 구별 공격에 대해 안전하지 않음: 공격자는 M’k(m)의 마지막 비트가 0임을 알고 있음. 랜덤 함수라면 마지막 비트는 단지 ½의 확률로 0. 즉, 랜덤 함수r(m)과 M’k(m)의 구별이 가능

16 Pseudorandom Function
PRF = Pseudorandom function 비밀키 k를 가지고 있는 사용자는 쉽게 계산할 수 있지만, 비밀키가 없는 사용자의 관점에서는 랜덤 함수와 구별되지 않는 함수 F: K x X  Y가 PRF이고 A가 F에 대한 공격자이면, A의 목표는 자신에게 주어진 어떤 함수 g(x)가 F(k, x)인지 아니면 랜덤 함수 $(x)인지 맞추는 것임 Adv(A) = Pr[A(F(k,·))=1] – Pr[A($)=1] Adv(t, q) = t라는 계산 시간 내에 q 회의 질의를 하는 공격자 A에 대한 Adv(A)들의 최대값 좋은 MAC은 단순히 위조 공격이 아니라 구별 공격에 대해서도 강해야 한다는 의미는, 좋은 MAC은 PRF여야 한다는 의미임 실제로, PRF 정의는 MAC 정의보다 더 강함: 좋은 PRF는 좋은 MAC임을 쉽게 증명할 수 있음

17 Why PRF than MAC? PRF를 사용할 때 좋은 예: truncation
가지고 있는 MAC이 512비트 출력 MAC이나, 전송 효율성 고려하여 128비트만 사용하고 싶음 512비트 출력 random function의 상위 128비트는 여전히 random function 따라서, 512비트 출력 PRF의 상위 128비트는 여전히 PRF 하지만, 512비트 출력 MAC의 상위 128비트는 위조 공격에 취약할 수 있음 즉, 처음에 주어진 함수가 PRF이면 truncation에 자유로우나, MAC이면 그렇지 않음 다양한 응용 환경을 고려하면 MAC보다는 PRF를 염두에 두고 설계한 함수를 사용하는 것이 바람직함 PRF is more robust than MAC

18 해쉬함수를 이용한 MAC의 구성 1 해쉬함수와 MAC 2 HMAC 3 Merkle-Damgard 4 EMD 5 OMD 6 결론

19 해쉬함수 기반 MAC 많은 차이점에도 불구하고, 해쉬함수를 이용하여 MAC을 구성하려는 시도들이 있었음 가장 효율적인 방식?
일단, 어쨌든 형태가 비슷하다고도 할 수 있음 ‘keyed hash function’ 대 ‘unkeyed hash function’ 해쉬함수도 일종의 메시지 무결성 보장을 위해 쓰이기도 함 예: 오픈 소스 소프트웨어 다운로드 및 배포 가장 효율적인 방식? H()가 해쉬함수일 때, Mk(x) = H(k || x)로 정의 (k || x는 비트열 k와 비트열 x의 연접) H가 random oracle이면 위와 같이 정의된 Mk(x)는 PRF임. 아니, 아예 random function임 What’s wrong with this approach?

20 Merkle-Damgard hash function
긴 메시지를 짧은 메시지 블록으로 분해 한 번에 하나씩의 메시지 블록을 순차적으로 처리 이를 위해 ‘압축 함수’를 설계 즉, 압축 함수의 직렬 연결이 Merkle-Damgard 해쉬함수 m1 IV m2 m3 m4 m5 output

21 메시지 확장 공격 Mk(x)=H(k || x)는 사용된 H가 Merkle-Damgard이면 메시지 확장 공격을 당할 수 있음
랜덤 메시지 x를 골라, Mk(x) 값을 질의 이제 공격자는 k는 모르지만 H(k || x)는 알고 있음 임의의 한 블록 b를 선택하고, x’=x || b로 정의 H가 Merkle-Damgard이면, H(k || x’) = H(k || x || b) = h(H(k || x), b) 여기서 h(s, b)는 H의 압축함수 공격자는 이제 x’과 h(H(k || x), b)를 출력하여 위조를 성공시킴 즉, 1회 질의와 대략 압축 함수 1회 계산량으로 확률 1로 위조 가능

22 HMAC 해쉬함수 기반 MAC으로, Bellare 등에 의해 제안됨 해쉬함수 기반 MAC의 사실상 표준
Merkle-Damgard 해쉬함수의 확장 공격을 막을 수 있도록 설계됨 IV 대신 키 사용 (K0이라는 1개의 키로 두 개의 키 유도하여 사용) 해쉬값을 그냥 출력하지 않고, 한번 다시 압축함수를 통과시켜 출력  연결을 끊어서 확장 공격 봉쇄 M 1 M t IV K0 ipad F F F KI Hash IV K0 opad F F KO MAC

23 Why HMAC? HMAC의 설계 원칙 (제가 이해하는 한에서) HMAC의 아쉬운 점
기존에 이미 사용되어온 MD5, SHA-1 등의 Merkle-Damgard 해쉬함수를 blackbox로 이용하여 구현 가능 (즉, 기존 소스 코드 수정 불필요) Merkle-Damgard 해쉬함수의 메시지 확장 성질을 MAC 레벨에서 봉쇄 안전성 증명 가능 압축 함수가 PRF이고, 그 외에 사소한 성질을 더 만족하면 HMAC 역시 PRF 이러한 한에서 최선의 효율성 유지 HMAC의 아쉬운 점 해쉬함수의 문제를 해쉬함수에서 해결 않고 상위 layer에서 처리 하지만, ‘기존에 이미 사용되어온’ 해쉬함수이므로 선택의 여지는 없었음 그 결과 효율성이 최선은 아님 짧은 메시지에 대해서는 H(k || x) 방식보다 2배까지도 느려짐

24 해쉬함수를 이용한 MAC의 구성 1 해쉬함수와 MAC 2 HMAC 3 Merkle-Damgard 4 EMD 5 OMD 6 결론

25 Merkle-Damgard Composition Scheme
IV m2 m3 m4 m5 output 해쉬함수의 디자인을 개념적으로 두 부분으로 분리 메시지 1블록을 처리하는 압축함수(compression function)의 설계 압축함수를 결합하는 결합 방식(composition scheme)의 설계 유사한 분업화가 암호화에도 적용됨: 블록 암호 + 운영모드 사실상 여태까지 Merkle-Damgard는 거의 유일한 결합 방식이었음 몇 가지 변종들이 있음. 예를 들어: MD strengthening: 마지막 블록에 전체 메시지 길이를 encoding하여 입력 Message as IV: 고정된 IV 대신 메시지의 첫 블록을 이용 Truncation: 최종 출력 시 일부 비트를 누락하기도 함

26 Merkle-Damgard의 장단점 장점 단점
개념적 단순성 효율성 On-line 처리 가능: 모든 메시지 블록을 다 받은 뒤에야 처리를 시작할 수 있는 것이 아니라, 데이터가 전송되는 대로 처리 가능 Collision resistance 증명 가능: 공격자가 전체 해쉬함수의 충돌쌍을 찾아낼 수 있으면, 이를 이용해서 압축함수의 충돌쌍을 찾을 수 있음을 증명 가능 즉, 압축함수의 충돌쌍을 찾기 어려우면, 전체 해쉬함수의 충돌쌍도 찾기 어려움 단점 메시지 확장 성질 ? 질문: ‘메시지 확장 성질’등의 구조적인 결함 여부를 특정 결합 방식에 대해 평가하는 방법은?

27 Indifferentiability Coron, Dodis, Malinaud and Puniya, Merkle-Damgard Revisited: How to Construct a Hash Function, CRYPTO 2005 Coron 등은 결합 방식의 구조적 성질을 연구하기 위해 indifferentiability framework 사용을 제안 압축 함수가 고정 길이 입력의 random oracle일 때, 해당 결합 방식으로 이를 결합한 해쉬함수가 random oracle과 ‘indifferentiable’한가? 직관: 해쉬함수는 궁극적으로 random oracle처럼 동작해야 함 Random oracle에는 어떤 구조도 없음 즉, random oracle과 구분 불가능하다는 것은 ‘메시지 확장 성질’과 같은 구조적 성질을 발견할 수 없음을 의미함 예: Merkle-Damgard 방식은 random oracle과 indifferentiable하지 않음 이유: 메시지 확장 공격이 가능하기 때문에

28 This guy is C and I’m actually G! Believe me!
Indifferentiability This guy is C and I’m actually G! Believe me! C G F S D A Turing machine C with oracle access to an ideal primitive G is said to be (tD, tS, q, ε)-indifferentiable from an ideal primitive F, if there exists a simulator S, such that for any distinguisher D it holds that: | PR[DC,G=1]-PR[DF,S=1] | < ε

29 Indifferentiability for hash functions
G: 고정 길이 입력의 random oracle C: G를 압축 함수로 하여, 특정 결합 방식을 적용하여 만든 해쉬 F: 임의 길이 입력의 random oracle S: F가 C라고 우기기 위해 자신이 그에 대응되는 고정 길이 입력 random oracle이라고 주장하는, 시뮬레이터 Merkle-Damgard는 random oracle과 indifferentiable하지 않음 메시지 확장 공격을 통해, 임의의 시뮬레이터 S의 거짓말도 밝혀낼 수 있음 결합 방식의 구조적 안전성 증명 결합 방식의 설계 적절한 시뮬레이터 S 정의 S에 대한 임의의 ‘differentiator’의 advantage도 크지 않음을 증명

30 새로운 결합 방식의 개발 환경 구조적 특성을 갖는 Merkle-Damgard 결합 방식에 의한 해쉬함수의 경우, HMAC을 사용해야 안전한 MAC을 구성할 수 있으나, HMAC의 효율성은 최선이 아님 해쉬함수의 구조적 안전성에 대한 엄밀한 분석 기법이 Coron 등에 의해 2005년에 제시됨 기존에는 Merkle-Damgard 방식이 사실상 유일한 결합 방식으로 자연스레 받아들여졌으며 이 부분에 대한 연구가 활발하지 않았으나, 최근 이에 대한 분석 및, 새로운 결합 방식의 개발에 대한 학계의 관심이 있음 예 Lucks의 wide pipe 방식 Gauravaram 등의 3C, 3C+ Bellare, Ristenpart의 EMD (Enveloped Merkle-Damgard) Wang의 해쉬함수 공격 이후 새로운 해쉬함수 개발에 대한 관심이 있음 NIST는 AES와 유사하게 AHS(Advanced Hash Standard) 공모사업 추진 예정

31 MAC 기능을 제공하는 새로운 결합 방식? 현재의 환경은, 더 이상 기존의 Merkle-Damgard 결합 방식을 당연시할 필요가 없게 되었음 따라서, Merkle-Damgard의 약점을 보완하기 위해 설계된 HMAC보다 더 효율적인 해쉬함수 기반 MAC의 구성이 가능해짐 결합 방식에 대한 바람직한 특성 자체의 효율성 Collision resistance 증명 가능 Preimage, 2nd preimage resistance의 경우 여태까지는 이것을 증명 가능하게 하는 스킴이 없음 구조적 결함 없음(random oracle과 indifferentiable) HMAC보다 효율적인 MAC 기능 제공 가능

32 해쉬함수를 이용한 MAC의 구성 1 해쉬함수와 MAC 2 HMAC 3 Merkle-Damgard 4 EMD 5 OMD 6 결론

33 EMD Composition Scheme
EMD (Enveloped Merkle-Damgard) M. Bellare and T. Ristenpart, Multi-Property-Preserving Hash Domain Extension and the EMD Transform, Asiacrypt 2006 앞에서 제시한 성질들을 모두 만족하는 결합 방식을 처음으로(?) 제시 EMD(M)=F(IV2, F+(IV1,m1…mk-1) || mk ) F+는 단순한 Merkle-Damgard iteration m1 IV1 m2 mk-1 mk output IV2 n d d-n

34 EMD Composition Scheme
Merkle-Damgard의 메시지 확장 성질을 깨기 위해, 출력 직전에서 또 하나의 IV를 가지고 압축 함수를 1회 추가 적용 마지막에 이전과 이질적인 조작을 해서 연쇄를 깨는 것은 암호학적 구성에서 많이 쓰이는 트릭임 하지만 이를 위해 별도로 압축 함수를 1회 더 적용하지는 않음 일반적으로 메시지 블록 길이 d > 내부 상태 크기 n임을 이용하여, 메시지 길이를 encoding하는 마지막 블록 단계에서 새로운 IV로 압축 함수 동작 결과적으로, Merkle-Damgard에 근접하는 효율성 MAC으로 사용하기 위해서는 IV1, IV2 대신에 비밀키를 이용 PRF로서의 안전성 증명 제공 Indifferentiability 증명 제공 질문: EMD보다 더 효율적일 수 있나?

35 해쉬함수를 이용한 MAC의 구성 1 해쉬함수와 MAC 2 HMAC 3 Merkle-Damgard 4 EMD 5 OMD 6 결론

36 OMD Composition Scheme
OMD (Offset Merkle-Damgard) A. Yun and J.H. Park, A Variant of the Merkle-Damgard Scheme with a Fixed Offset, Manuscript OMD(M)=F(C  F+(IV1,m1…mk-1), mk ) C는 고정된 0이 아닌 상수 m1 IV m2 mk-1 C output n d mk

37 배경 J. Kelsey, in Public Comments on the Draft Federal Information Processing Standard (FIPS) Draft FIPS 180-2, Secure Hash Standard (SHS), 2001, available at John Kelsey는 SHA-2에 대한 public comment에서, SHA-1 등에 쓰인 Merkle-Damgard 방식의 메시지 확장 성질을 막기 위한 한 가지 방법으로 마지막 블록의 처리 직전에 0이 아닌 상수를 XOR하는 것을 제안 (2001년) Kelsey에 의하면 이는 Niels Ferguson에 의해 처음 제안되었다고 함 하지만 여태까지 이 방식의 안전성에 대한 증명이나 기타 분석 결과는 전무 한 일: 이 방식에 대해 OMD(Offset Merkle-Damgard)라 명명하고, 안전성을 증명함

38 OMD의 안전성 OMD의 안전성 압축함수가 collision resistant  OMD도 collision resistant 압축함수가 고정 길이 입력 random oracle  OMD는 임의 길이 입력 random oracle 압축함수가, 비밀키 k를 IV로 사용했을 때 매우 약한 연관키 공격(related-key attack)에 안전한 PRF  비밀키 k를 IV로 사용했을 때 OMD도 PRF 압축함수가, 앞의 가정 이외에, 비밀키를 메시지 블록에 넣을 때에 PRF  Mk(x) := OMD( k || x )가 PRF 참고 압축함수 F(s, x)에 대해 비밀키 k를 IV로 사용: 함수족 kF(k, · )를 고려 비밀키를 메시지 블록에 넣기: 함수족 kF(· , k)를 고려 약한 연관키 공격 PRF F에 대해 공격자가 질의할 때, 비밀키 k에 대해 Fk(·), 또는 FCk(·) 양쪽에 질의 가능. 공격자는 최종적으로 자신이 함수 쌍 Fk(·), FCk(·)를 상대하는지 아니면 두 개의 독립적인 랜덤함수 쌍 r1(·), r2(·)를 상대하는지를 맞혀야 함

39 안전성 증명의 아이디어 메시지 확장 공격은 사실상 Merkle-Damgard의 유일한(?) 구조적 특성임 직관적으로
예: 비밀키를 IV로 사용하는 cascade construction은 Prefix-free PRF (즉, 공격자가 한 메시지가 다른 메시지의 확장인 형태의 질의만 하지 않으면 PRF) 직관적으로 Merkle-Damgard의 chaining 과정을 offset C가 끊을 것이다. 더 구체적으로, F가 복잡하게 생겼다면 F(s, x)가, 이미 질의된 다른 F(s’, x’)에 대해 F(s, x)=s’이거나 혹은 F(s, x)=Cs’일 확률은 낮다. 따라서 이 확률을 무시하면 공격자는 indifferentiability 문제의 경우, 시뮬레이터를 구분하기 위해 유용한 정보를 전혀 얻을 수 없다 시뮬레이터는 F(s, x)를 그냥 랜덤하게 고르는 것이 아니라, 위와 같은 경우가 생기지 않도록 피해서 제공해야 한다.

40 OMD is a PRF Bellare, Canetti, Krawczyk의 96년도 논문 ‘Pseudorandom Functions Revisited’는 비밀키를 IV로 하는 cascade construction이 Prefix-free PRF임을 증명함 OMD가 PRF임은 위 논문의 증명을 연관키 버전으로 바꾸어 증명 Key lemma Fk(x)가 약한 연관키 공격에 강한 PRF이면, 즉 ( Fk(·), FCk(·) )와 랜덤함수 쌍 (r1(·), r2(·) )를 구별할 수 없으면, 다음의 둘도 구별할 수 없음: Fk1(·), FCk1(·), Fk2(·), FCk2(·), … , Fkq(·), FCkq(·) 와 r1(·), r’1(·), r2(·), r’2(·), …, rq(·), r’q(·)

41 OMD 대 EMD 유사 제품 간에 비교 필요함 EMD와 OMD가 둘 다 메시지 확장 공격을 막기 위해 압축함수의 domain을 분리하지만, EMD는 아예 별도의 IV를, OMD는 offset을 통한 확률적 분리를 이용 OMD의 구조가 EMD보다 더 단순함: 이 결과 OMD가 EMD보다 다소 빠름. SHA-1과 같은 파라미터에서 압축함수 동작 횟수가 평균 0.3회 적음 MAC 기능의 경우, EMD는 단지 PRF 가정만 필요로 하지만, OMD는 연관키 공격을 고려한 다소 강한 가정이 필요 반대로, EMD는 IV 두 개에 대응되어, 두 배로 더 긴 비밀키가 필요하지만 키 전수조사 관점에서 divide-and-conquer 공격이 가능하여 OMD만큼의 안전성만을 제공 1개의 비밀키를 이용하고 키 유도 방식을 통해 두 개로 불리면 되지만, 이 경우 OMD와 마찬가지로 연관키 공격에 대한 가정 필요 EMD는 해쉬함수를 블랙박스로 사용하는 H( k || x )와 같은 구성에 대한 PRF 안전성 증명이 되어있지 않음

42 해쉬함수를 이용한 MAC의 구성 1 해쉬함수와 MAC 2 HMAC 3 Merkle-Damgard 4 EMD 5 OMD 6 결론

43 결론 해쉬함수와 MAC은 피상적인 유사함에도 불구, 전혀 다른 대상임
해쉬함수 기반 MAC은 많이 연구되어 왔으며, HMAC이 대표적 이전에는 해쉬함수의 결합 방식에 대한 연구가 미진하였으나, 현재는 분석이 이루어지고 있으며 Merkle-Damgard를 뛰어넘는 결합 방식에 대해 학계의 관심이 있음 또한 기존 표준 해쉬들에 대한 회의론과 더불어, 새로운 해쉬함수의 개발에 대한 실제적인 수요와 관심이 있음 따라서, 안전성을 잃지 않고도 Merkle-Damgard 방식과 HMAC을 동시에 더 효율적인 구성으로 대치할 수 있는 기회가 주어짐 OMD(Offset Merkle-Damgard) 방식이 그러한 구성의 한 예임

44 감사합니다.