2009/12/05 18:11
이기적인유전자
최근에 블룸필터가 논문 여기저기 등장하다 보니까 마침내는 이런 무책임한 시도들이 일고 있는 것 같습니다. 우선은 블룸필터와 MAC이 무엇인지 모르시는 분들을 위하여 간략히 설명드리겠습니다.
정보보호 분야에서 MAC은 Message Authentication Code를 줄여 부르는 말로 메시지가 전송 도중에 변조되지 않았음을 보장하는 추가적인 코드입니다. 흔히 비밀키가 들어가는 Keyed MAC과 들어가지 않는 MAC으로 나눠볼 수 있는데, 전자의 경우 메시지 뿐만 아니라 비밀키도 같이 넣음으로써, 비밀키를 알고 있는 사람만이 MAC을 생성할 수 있기 때문에, 비밀키를 소유하고 있는 두 노드만이 생성하고 확인하는 것이 가능합니다. 후자의 경우, 메시지만 입력으로 주게 됩니다. 추가적으로 전자서명(Digital Signature)와 이 Keyed MAC의 차이는 전자서명이 공개키 암호화 기법을 활용하여 공개적으로(in public) 확인 가능하다면 Keyed MAC의 경우 개인적으로(in private)만 확인이 가능합니다. 여기서 이야기하는 것은 Keyed MAC으로 HMAC(Hash-based Message Authentication Code)으로도 불리며 그냥 줄여서 MAC으로 부르도록 하겠습니다. RFC 2104에서 HMAC은 다음과 같이 정의하고 있습니다.
HMAC(K,m) = H((K ⊕ opad) ∥ H((K ⊕ ipad) ∥ m))
블룸필터(Bloom filter)는 1970년 Burton Howard Bloom 이 고안한 통계적 특성을 갖는 데이터 구조의 일종으로써, sparse한 데이터를 저장하고 검색하기 좋은 구조로 flase positive를 갖게 되는 것이 특징입니다. 아래 그림을 보시면 바로 이해가 가실 겁니다.
블룸필터(출처, 위키피디아)
정보보호 분야에서는 서로 다른 몇개의 해시 함수(입력에 다양한 패딩을 줌으로써 쉽게 구현할 수있습니다.)를 사용함으로써, 한 메이지에 대해서 필터 위에 몇개의 점을 0에서 1로 바꾸어 전송하면 반대편에서도 동일한 해시 함수를 돌려 해당 위치가 제대로 1로 셋팅되어 있는지 확인함으로써 메시지를 변조되지 않았음을 확신할 수 있습니다.
자. 여기서 문제입니다. MAC의 경우 엔트로피가 높아서 세상에 알려진 어떠한 압축알고리즘으로도 잘 압축이 되지 않는 것으로 알려져 있습니다.(이는 MAC의 출력이 해시 함수의 출력이기 때문이지요.) 여기에 여러 메시지에 대한 MAC이 존재합니다. 이를 블룸필터를 써서 압축할 수 있을까요?
이런 말하기 참 곤란하지만, 몇몇 분들은 이게 가능하다고 생각하는 모양입니다. 사실 단순하게 생각하면 적당히 큰 블룸필터를 잡고 적당히 많은 해시 함수를 돌리고, 적당히 큰 갯수의 MAC이라면 블룸필터가 더 효율적일 수 있을 것만 같습니다.
그럼 지금부터 꼼꼼하게 따져보겠습니다.
여기에 md5 기반의 MAC이 1개 있습니다.(128비트겠네요.) 조합함수를 이용할 경우, 최대 조합 가능한 경우가 등장하는 경우는 꼭 전체의 절반을 선택하는 경우입니다.(예를 들어, 10개 중에 5개를 선택하는 경우가 10개 중에 4개나 6개를 선택하는 경우보다 경우의 수가 더 큽니다.) 따라서 MAC 하나를 블룸필터로 표시하기 위해서는 132개중에 66개를 선택하는 경우(3.77×10^38)에 128비트의 MAC(2^128 = 3.4×10^38)을 온전히 옮겨올 수 있습니다. 즉, 블룸필터가 132비트에 그중 66개의 비트가 1로 셋팅되어 있을 때 128비트 MAC과 유사한 역할을 수행할 수 있다는 것입니다. 만약 이 경우 블룸필터를 쓸 경우, 4비트나 더 큰 구조체를 사용해야 한다는 것이죠. 또한 엔트로피가 매우 높아서(132중 66비트가 1이므로) 압축이 잘 되지 않습니다. 따라서 1개의 MAC을 대체하기 위해서 블룸필터를 사용할 얼간이는 없다는 거죠.
자, 다음은 여러개가 MAC을 위해서 블룸필터를 사용하는 경우를 생각해봅시다. 앞선 경우와 동일한 블룸필터를 사용했을 때, 무슨 일이 벌어질지는 대충 예상할 수 있습니다. 66개의 해시 함수가 서로 다른 두 메시지에 대해서 충돌을 일으킬테고 어쩌고 해서 66개보다 많지만 132개보다 작은 수의 비트가 1로 세팅되겠네요. 이 경우, 블룸필터가 갖는 경우의 수가 낮아지게 되면서 MAC이 갖는 정보보다 훨씬 많은 정보가 블룸필터에서 사라지게 됩니다! 따라서 여러개의 MAC을 위해서는 블룸필터의 크기를 늘릴필요가 있습니다!
우리가 원하는 결론에 도달하는 여러가지 경로가 있지만 여기서는 아주 단순하게, MAC의 크기가 128비트에서 128×N비트로 증가했다고 가정합시다. 그러면 여기서 해당 MAC의 정보를 모두 갖게 되는 블룸필터의 크기와 해시 함수의 갯수를 생각해보면 됩니다. 블룸필터가 최대 엔트로피를 갖게 될 경우는 해당 블룸필터의 절반이 1로 셋팅되어 있는 경우라고 했고, 언젠가는 블룸필터가 MAC보다 더 효율적으로 되는 경우를 가정하여 블룸필터의 크기를 128×N로 가정할 때, 과연 N이 몇 이상이면 블룸필터가 효율적이 될까요. 수식으로 쓰면,
와 같이 되는 n을 찾으면 됩니다. 아.. 뭔가 대충 복잡하긴 한데, Stirling's approximation을 따르면
와 같이 된다고 합니다. 따라서 어떠한 n이 오더라도 앞의 √(1/32\pi n)은 1을 넘지 않습니다. 그런 n은 존재하지 않는 거죠.
따라서 블룸필터로 동일한 정보를 갖는 MAC을 대체할 수 없습니다!
그럼 MAC을 대체한다는 블룸필터 이야기는 도대체 뭐냐하면, 해당 논문들(!)이 원래 기법들이 갖는 보안 수준을 자의적으로 떨으뜨려놓고서는 자기들의 기법이 효율적이다라고 하는 것이죠. 그에 대한 근거 또한 빈약하기 그지 없습니다. 원래의 기법은 128비트의 MAC을 사용하고 자신들은 일정 크기의 블룸필터를 사용하므로, 몇 개 이상의 MAC이 모이게 되면 블룸필터가 효율적이 된다는 겁니다.
저는 블룸필터를 역으로 분석하여 보안성을 추정한 뒤, 그에 필요한 MAC의 크기에 대해서 고민해본적이 있습니다. 결과는 역시나 였지요. 굳이 128비트 MAC을 쓸게 아니라, 보안성을 낮출 수 있다면 그냥 앞의 몇 비트를 잘라서 사용하면 되는 거죠. 이게 더 쉬울 뿐만 아니라 연산도 더 효율적입니다.
앞으로는 이런 말도 안되는 촌극이 없기를 바랍니다.
'이기적인유전자' 카테고리의 다른 글
| 블룸필터로 MAC을 효율적으로 대체할 수 있다?! (0) | 2009/12/05 |
|---|