Symmetric Key Encryption - MACs

지금까지 앞에서 살펴본 OTP, CBC, CTR, DES, AES는

Confidentiality를 만족시키는 Symmetic key 기반의 암호화 기법이었다.

 

이번에 알아볼 MAC은 Symmetric key Encryption에 해당하지만 Confidentiality가 아닌

Integrity & Authenticity을 만족시키는 기법에 해당한다. 

 

즉 MAC은 confidentiality는 보장할 수 없는 암호화 기법이라는 뜻!

---

What is Hash Function

MAC이 무엇인지 알기 위해서는 우선 HASH 함수에 대해서 알아야 한다. 

 

Hash 함수는 말 그대로 함수이다.

그렇다 보니 M 길이의 메시지를 받으면 n 길이의 고정된 결과를 반환한다. 

 

다른 말로 하면 가변 길이의 메세지를 모두 동일한 길이의 output으로 만드는 함수이다.

 

 

WHY

쉽게 말해 Hash 함수는 데이터를 있는 그대로 알아볼 수 없게 만들기 위해서 사용한다.

"hello, I am D"라는 문구를 비밀스럽게 전달하고 싶다면 아마 자기들만 아는 규칙을 사용해 암호문을 만들 것이다.

 

이때 암호문을 만들기 위해 사용할 수 있는 게 바로 hash function인 셈이다. 

hello I am D -> ae5eba77bacd3e95a3d54b5e5819f447

hello I am D를 md5 hash 해보면 오른쪽과 같이 알아볼 수 없는 형태의 결과가 나온다.

 

이처럼 hash 함수는 내용을 알아볼 수 없도록 만들기 위해서 쓰이며 

hash 함수 종류에 따라서 그 결과의 길이가 다르다. (ex. MD5 = 128 bits)

 

 

HOW

사실 위에서 예시로 든 MD5 같은 경우, 현재로서는 완전히 뚫려버린(?) hash 함수이다.

 

메시지를 그 누구도 알아보지 못하게 만들기 위해서 hash function을 개발한다면 

어떤 조건을 고려해서, 어떻게 만드는 게 좋을까? 

 

Hash function에 input x를 넣은 경우를 H(x) = y라고 표현할 때

1. One Way function

: y를 안다고 할 때, x를 알아낼 수 없어야 한다. (or 알아내기 어려워야 한다.)

 

예를 들어 상수 함수 C(x) = 1이 있다고 가정해 보자.

어떤 값을 넣든 동일한 값이 나오게 되면

"실제로 넣은 값이 무엇인지 알기 어렵기 때문에 one way function이야!"라고 생각할 수 있지만

 

one way function의 정의를 잘 생각해 봤을 때, "어떤 값을 넣었더니 1이 나왔을까?"에 대해

어떤 값을 고르든지 정답이 되기 때문에 상수 함수는 one way function이라 할 수 없다. 

 

 

2. Second Preimage resistance

: x와 H(x)가 주어질 때, H(x)와 동일한 결과를 갖는 x'을 알아낼 수 없어야 한다. (x != x')

 

3. Collision resistance

: 동일한 hash 함수 결과가 나오는 x & x'을 찾을 수 없어야 한다. (x != x')

 

얼핏 보면 2 & 3이 동일한 조건처럼 보일 수 있지만 아니다.

2번보다는 3번을 만족시키는 경우를 찾는 게 조금 더 쉬울 수 있다.

 

2번 같은 경우는 x와 H(x)가 주어진 상황이다.

주어진 H(x)를 만족시키는 x가 아닌 x'을 찾아야 하는 반면 

 

3번의 경우는 H(x) & H(x')가 동일하게 나오는 서로 다른 x & x'을 찾기만 하면 된다. 

일치해야 하는 함숫값이 정해져 있지 않은 상황이다. 

 

 

4. Random & deterministic

input x에 대해 output이 어떻게 나올지 예측 불가능함을 random이라고 표현한다면 

 

hash function의 결과는 random 해야 하며

동일한 input에 대해서는 항상 동일한 output이 나와야 한다. (= deterministic)

 

 

위의 4가지 조건을 주로 고려하여 hash function을 만든다면 

남들은 모르는 비밀 메시지를 만들 수 있을 것이다. 

---

Integrity & Hash function

이젠 hash function이 integrity를 만족하는지에 대해 생각해보려고 한다.

 

Senario 1 ) A가 google에서 program binary를 다운로드한다고 할 때 

google이 program binary를 hash 한 값을 웹 사이트에 공개하면 A는 자신이 다운로드한 program binary를

hash 해봄으로써 누군가에 의해 조작되었는지 확인할 수 있다. 

 

Senario 2) A가 B와 insecure 한 채널로 통신한다고 할 때

A가 B에게 어떤 메시지를 hash 해서 보낸다고 하더라도 중간에서 누군가가 그 값을 아무렇게나 바꾼다고 하면

B는 이를 확인할 방도가 없다!!

 

따라서 Hash를 이용한 Integrity는 상황에 따라 다르다고 할 수 있다.

그러면.. 어떻게 해야 hash를 이용해 항상 Integrity를 만족시킬 수 있을까?

---

MAC (message authentication codes)

우리는 앞선 글에서 key를 암호화하는 데 사용할 수 있음을 확인했다. 

hash function과 key를 같이 사용한다면 어떤 효과를 얻을 수 있을지 생각해 보자. 

 

 

Alice가 Bob에서 메시지를 보내고 싶은 데 이 메시지가 중간에 누군가에 의해 조작되지 않기를 원한다.

그래서 Alice는 자신이 보낼 메시지에 추가적으로 Tag를 만들어 Bob에게 보내기로 한다.

 

이때 Tag는 MAC의 결괏값으로 MAC은 

MAC(K, m) = T

 

Alice와 Bob이 이미 공유하고 있는 key를 이용해 메시지 m을 hash 한다. 

즉 hash의 결과가 Tag인 것이다. 

 

그렇게 Alice로부터 메시지와 Tag를 전달받은 Bob.

Bob은 Alice가 보낸 메시지가 조작되지 않았나 확인하고자 한다. 

 

이때 Bob은 Alice와 동일한 key를 갖고 있기 때문에 자신이 받은 메시지로 직접 Tag를 만들어본다.

자신이 생성한 Tag가 Alice가 보낸 Tag와 일치한다면 누군가가 메시지를 조작하지 않았다는 걸 확인할 수 있다.

---

Integrity & MAC

그렇다면 MAC은 Integrity(& authenticity)를 보장한다고 할 수 있을까?

대답은 Yes!

 

다만 Alice와 Bob이 사용한 key가 서로만 알고 있다는 보장 하에 그렇다.

1) message를 조작한 경우

Bob이 조작된 message와 key로 Tag를 생성하여 Alice가 보낸 Tag와 비교해 보면 

Tag가 일치하지 않기 때문에 조작됨을 알 수 있다.

 

2) Tag를 조작한 경우

Bob이 Tag를 생성하여 Alice가 보낸 Tag와 비교할 때 

Alice의 Tag가 조작되었기 때문에 Bob이 생성한 Tag와 일치하지 않는다. 

 

3) message & Tag 모두 조작한 경우

Alice가 보낸 message & Tag가 모두 조작된 경우

Bob이 조작된 message로 Tag를 생성하더라도 이 Tag는 조작된 Tag와 값이 일치하지 않는다.

---

Result

공격자가 Alice & Bob이 공유하고 있는 secret key를 모른다면 어떤 값을 조작하든지 

유효한 Tag값을 생성해 낼 수 없기 때문에 무언가가 조작되었다는 걸 확인할 수 있다.

 

따라서 MAC으로 메시지를 주고받는 경우에는 Integrity를 보장할 수 있는 것이다.

더불어 key는 Alice와 Bob만 알고 있는 정보이기 때문에 Tag가 유효하다면 해당 message를

Alice or Bob이 보냈다는 걸 알 수 있다. (= Authenticity)