MLS는 왜 그룹 채팅에 필요한가

1:1 종단간 암호화는 오래전에 정리된 문제다. 두 사람이 열쇠를 주고받고 메시지마다 열쇠를 굴리면 된다. 그런데 사람이 셋만 되어도 이야기가 달라지고 백 명이 되면 다른 문제가 된다.

이 글은 그 차이가 어디서 오는지와 MLS가 그 차이를 어떻게 다루는지를 살핀다. MLS는 Messaging Layer Security의 줄임말이고 2023년에 RFC 9420으로 표준이 되었다.

짝마다 채널을 여는 방식

가장 단순한 그룹 암호화는 1:1을 여러 번 하는 것이다. 열 명이면 나와 아홉 명 사이에 채널을 각각 열어 둔다. 메시지 하나를 보낼 때 아홉 번 암호화해서 아홉 번 보낸다.

이 방식은 작은 방에서 잘 돌아간다. 문제는 사람 수에 그대로 비례한다는 것이다. 백 명이면 한 번 말할 때마다 아흔아홉 번이다.

그래서 실제로는 중간 단계를 쓴다. 그룹 전체가 공유하는 열쇠를 하나 만들어 두고 그 열쇠로 메시지를 암호화한 다음 그 열쇠만 짝마다 채널로 나눠 주는 방식이다. 메시지는 한 번만 암호화하면 되니 평소 비용이 확 줄어든다.

진짜 문제는 회복이다

평소 비용이 아니라 사고가 났을 때가 문제다.

누군가의 기기가 털려 그룹 열쇠가 새어 나갔다고 하자. 그때부터 공격자는 그 방의 모든 메시지를 읽는다. 다시 잠그려면 새 열쇠를 만들어 공격자를 뺀 나머지에게만 나눠 줘야 한다. 이 성질을 사후 침해 보안(post-compromise security)이라고 부른다.

공유 열쇠를 짝마다 채널로 나눠 주는 구조에서는 이 비용이 크다. 갱신할 때마다 나머지 전원에게 새 열쇠를 따로 보내야 한다. 멤버 각자가 자기 열쇠를 정기적으로 갱신하도록 하면 전체 비용이 그룹 크기의 제곱으로 늘어난다. 백 명 방에서는 한 바퀴 도는 데 수천 번이다.

비용이 크면 자주 하기 어렵다. 그리고 미루는 동안은 털린 상태가 그대로 이어진다.

래칫 트리

MLS는 멤버를 한 줄로 늘어놓는 대신 이진 트리의 잎에 앉힌다. 이 구조를 래칫 트리(ratchet tree)라고 부르고 그 위에서 도는 키 교환 방식을 TreeKEM이라고 한다.

트리의 각 노드에는 열쇠가 하나씩 달려 있다. 어떤 노드의 열쇠는 그 아래 잎에 있는 멤버 전원이 알고 있고 바깥 사람은 모른다. 뿌리의 열쇠는 그래서 그룹 전체가 공유하는 열쇠가 된다.

한 멤버가 자기 열쇠를 갱신할 때 하는 일은 이렇다. 자기 잎에서 뿌리까지 올라가는 경로 위의 노드만 새 열쇠로 바꾼다. 그리고 각 단계에서 반대편 가지에게만 새 열쇠를 암호화해 보낸다. 반대편 가지는 하나의 노드로 묶여 있으므로 한 번만 보내면 그 아래 전원이 받는다.

경로의 길이는 트리의 높이다. 백 명이면 일곱 단계다. 아흔아홉 번이 일곱 번이 된다.

에포크와 세대

MLS에서 그룹의 상태는 에포크(epoch)라는 세대로 관리된다. 멤버를 더하거나 빼거나 누가 열쇠를 갱신할 때마다 에포크가 하나 올라가고 그 세대의 비밀이 새로 만들어진다.

여기서 두 가지 성질이 나온다.

전방 비밀성. 에포크가 넘어가면 이전 세대의 메시지 열쇠는 버려진다. 지금 기기를 털어도 지난 세대의 메시지는 열지 못한다.

사후 침해 보안. 털린 멤버가 갱신을 한 번 올리면 그 순간부터 새 세대가 시작되고 공격자는 밖으로 밀려난다. 공격자가 계속 읽으려면 계속 털고 있어야 한다.

새로 들어온 사람이 이전 대화를 읽지 못하는 것도 여기서 나온다. 입장할 때 받는 것은 현재 에포크의 상태이고 지난 세대의 비밀은 그 안에 없다. 단톡방에서 벌어지는 일을 사용자 입장에서 정리한 글이 따로 있는데 그 밑바닥이 이 구조다.

그래도 남는 것

트리가 모든 것을 풀어 주지는 않는다.

누가 그 방에 있는지는 서버가 안다. MLS가 지키는 것은 메시지 내용이다. 누가 언제 그룹에 들어오고 나갔는지는 서버가 전달을 하려면 알아야 한다. 내용이 아니라 겉에 붙는 정보는 여기서도 남는다.

순서가 중요해진다. 에포크는 줄줄이 이어지므로 갱신이 뒤섞여 도착하면 상태가 어긋난다. 서버가 순서를 정해 주는 역할을 맡아야 하고 그만큼 구현이 까다로워진다.

기기마다 따로다. MLS에서 잎에 앉는 것은 사람이 아니라 기기다. 한 사람이 기기 두 대를 쓰면 잎이 두 개다. 새 기기를 더하는 것은 멤버를 더하는 일과 같아서 그 기기는 더해진 시점부터의 에포크만 안다.

시그니토(Signito)도 이 구조를 쓴다.

자주 묻는 질문

MLS와 시그널 프로토콜은 무엇이 다른가요

푸는 문제가 다르다. 시그널 프로토콜의 더블 래칫은 두 사람 사이를 다루고 그 영역에서는 여전히 표준적인 선택이다. MLS는 여러 명이 모인 그룹의 열쇠를 어떻게 함께 굴릴 것인가를 다룬다. 그룹에서는 갱신 비용이 트리 구조 덕에 로그로 떨어진다.

왜 제곱이 나오나요

한 사람이 갱신할 때 나머지 전원에게 보내야 하면 한 번에 n번이다. 멤버 전원이 한 바퀴 돌며 갱신하면 n번이 n번 일어나므로 n의 제곱이 된다. 트리에서는 한 사람의 갱신이 log n이라 한 바퀴가 n log n이다.

그룹이 커지면 어디가 먼저 힘든가요

갱신 비용보다 상태 동기화가 먼저 힘들어진다. 오래 꺼져 있던 기기가 돌아오면 밀린 에포크를 따라잡아야 하고 그 사이에 멤버가 많이 바뀌었으면 따라잡을 양이 늘어난다.

표준이 되면 서로 다른 메신저끼리 대화가 되나요

MLS는 열쇠를 다루는 층을 표준화한 것이라 그 층만으로 연동이 되지는 않는다. 계정을 어떻게 식별하고 메시지를 어떻게 주고받을지는 그 위에서 따로 정해야 한다. RFC 9750이 그 바깥 구조를 다룬다.