Signito
블로그

MLS로 그룹 채팅을 암호화하는 법

  • 암호화 원리
  • MLS
  • 종단간 암호화

두 사람 사이를 암호화하는 것은 정리된 문제다. 열쇠를 주고받고 메시지마다 굴리면 된다. 사람이 셋만 되어도 이야기가 달라지고 백 명이 되면 다른 문제가 된다.

이 글은 그 다른 문제가 무엇이고 MLS가 어떻게 푸는지를 처음부터 끝까지 본다. 왜 그룹에 MLS가 필요한지를 짧게 정리한 글이 따로 있는데 이 글은 그 긴 판이다. 주된 근거는 RFC 9420이고 규격에 적힌 이름은 번역하지 않고 그대로 쓴다.

목차

사람이 늘면 무엇이 깨지나

먼저 쓰이던 두 방식과 그 한계를 보면 왜 트리가 나왔는지가 보인다.

짝마다 채널을 연다. 가장 단순한 방법은 1:1을 여러 번 하는 것이다. 열 명이면 나와 아홉 명 사이에 채널을 각각 열어 둔다. 메시지 하나를 보낼 때 아홉 번 암호화해서 아홉 번 보낸다. 작은 방에서는 잘 돈다. 사람 수에 그대로 비례하는 것이 문제다.

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

여기까지는 평소 이야기다. 진짜 문제는 사고가 났을 때 나온다.

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

공유 열쇠 구조에서는 그 비용이 크다. 한 사람이 갱신할 때 나머지 전원에게 따로 보내야 하니 한 번에 n번이다. 멤버 전원이 한 바퀴 돌며 갱신하면 n번이 n번 일어나 n의 제곱이 된다. 백 명 방이면 한 바퀴에 수천 번이다.

비용이 크면 자주 못 한다. 미루는 동안은 털린 채로 간다. 그룹 암호화의 어려운 부분은 평소 비용이 아니라 회복 비용이다.

래칫 트리

MLS는 멤버를 한 줄로 세우는 대신 이진 트리의 리프 노드(leaf)에 하나씩 둔다. 이 구조를 래칫 트리(ratchet tree)라고 부르고 그 위에서 도는 키 교환 방식을 TreeKEM이라고 한다.

RFC 9420은 래칫 트리를 멤버들 사이에 비밀과 키 쌍을 배치해 그룹 변경을 효율적으로 반영할 수 있게 만든 구조라고 정의한다.

규칙은 하나다. 어떤 노드의 열쇠를 아는 사람은 그 아래 리프 노드에 있는 멤버뿐이다. 리프 노드의 열쇠는 그 한 사람만 안다. 루트 노드(root) 아래에는 멤버가 전부 들어간다. 루트 노드의 열쇠가 곧 그룹 공유 열쇠다.

리프 노드에 자리 잡은 멤버가 열쇠를 갱신하면 자기 노드에서 루트 노드까지 올라가는 노드만 새 열쇠로 바뀐다. 나머지 가지는 그대로 둔다.

직접 경로를 바꾼다

한 멤버가 자기 열쇠를 갱신할 때 하는 일은 이렇다. 자기 리프 노드에서 루트 노드까지 올라가는 노드만 새 열쇠로 바꾼다. 규격은 그 경로를 direct path라고 부른다. 루트 노드의 direct path는 빈 목록이고 나머지 노드의 direct path는 부모와 부모의 direct path를 이은 것이다.

바꾼 열쇠를 어떻게 나눠 주느냐가 핵심이다. 경로를 한 칸 올라갈 때마다 반대편 가지에게만 새 열쇠를 암호화해 보낸다. 반대편 가지는 그 자체가 하나의 노드로 묶여 있으므로 한 번만 보내면 그 아래 멤버가 모두 받는다. 멤버 한 사람 한 사람에게 따로 보낼 필요가 사라지는 지점이 여기다.

보내는 횟수는 경로의 길이이고 경로의 길이는 트리의 높이다. 여덟 명이면 세 번이고 백 명이면 일곱 번이다. 아흔아홉 번이 일곱 번이 된다. 여기까지는 트리에 빈자리가 없을 때의 셈이다. 빈자리가 생기면 달라지는데 뒤에서 따로 본다.

비용이 로그로 떨어지면 갱신을 자주 할 수 있다. 자주 할 수 있으면 털린 상태가 짧아진다. 트리가 바꾼 것은 속도가 아니라 회복의 빈도다.

Proposal과 Commit

그룹을 바꾸는 일은 두 단계로 나뉜다.

Proposal은 다음 에포크에 반영할 변경을 제안하는 메시지다. 멤버를 더하거나 빼거나 자기 열쇠를 갱신하겠다는 뜻을 담는다. 제안만으로는 아무것도 바뀌지 않는다.

Commit은 모아 둔 제안을 실제로 반영하는 메시지다. Commit이 올라가야 그룹 상태가 바뀐다.

왜 둘로 나누나. 변경을 모아서 한 번에 적용할 수 있기 때문이다. 세 명을 더하고 한 명을 빼는 일이 제안 네 개로 쌓였다가 Commit 하나로 끝난다. 트리를 네 번 고치지 않고 한 번 고친다.

그리고 Commit을 보내는 사람은 그 과정에서 자기 direct path를 함께 갱신한다. 그래서 멤버가 바뀌는 일과 열쇠가 새로 도는 일이 같은 순간에 일어난다.

에포크

에포크(epoch)는 그룹 상태의 한 판이다. 규격은 특정한 멤버 집합이 공유 암호 상태를 들고 있는 그룹의 상태라고 정의한다. Commit이 하나 올라갈 때마다 에포크가 하나 올라가고 그 에포크의 epoch_secret이 새로 만들어진다. 이 비밀은 그 에포크의 멤버만 안다.

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

전방 비밀성. 다음 에포크의 비밀은 지금 비밀에서 한 방향으로만 뽑힌다. 그래서 지금 상태를 쥐어도 지난 에포크의 비밀은 거꾸로 계산해 낼 수 없다. 규격이 보장하는 것은 여기까지다. 지난 에포크의 열쇠를 기기에 남겨 둘지는 앱이 정한다.

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

대가도 있다. 에포크는 줄줄이 이어지므로 순서가 어긋나면 상태가 갈라진다. 두 사람이 같은 에포크에서 동시에 Commit을 보내면 하나만 살아야 한다. 누가 살아남을지 정해 주는 역할이 필요하고 규격은 그 자리를 전달 서비스(Delivery Service)라고 부른다. 내용을 못 읽어도 순서는 정한다.

에포크 안에서 쓰는 열쇠도 한 덩어리가 아니다. 규격은 핸드셰이크 메시지와 애플리케이션 메시지에 각각 다른 래칫을 만든다. 그룹을 바꾸는 메시지와 사람이 쓴 메시지가 같은 열쇠를 쓰지 않는다.

에포크와 generation은 다르다

헷갈리기 쉬운 자리가 하나 있다. 에포크가 오르는 것과 generation이 오르는 것은 다른 일이다.

에포크는 그룹 전체가 함께 넘어간다. Commit이 올라가야 바뀌고 모든 멤버가 같은 번호를 쓴다.

generation은 보내는 사람 한 명의 것이다. 규격은 generation을 보내는 쪽이 자기 래칫에서 새 열쇠를 꺼낼 때마다 하나씩 오르는 카운터라고 적는다. 메시지를 한 통 보낼 때마다 그 사람의 generation이 오른다. 에포크가 바뀌면 래칫이 새로 만들어지므로 generation은 0으로 돌아간다.

그래서 메시지 하나를 열려면 어느 에포크의 누구의 몇 번째 열쇠인지가 다 있어야 한다. 에포크 번호만으로는 찾지 못한다.

키 스케줄

에포크의 비밀이 어디서 나오는지를 규격은 키 스케줄(key schedule)이라고 부른다. 여기를 들여다보면 앞에서 말한 전방 비밀성이 왜 성립하는지가 드러난다.

재료가 둘이다. 지난 에포크의 init_secret과 이번 Commit이 만들어 낸 commit_secret이다. 둘을 섞어 joiner_secret을 뽑고 거기서 다시 epoch_secret을 뽑는다. 중간에 미리 나눠 둔 열쇠를 끼워 넣는 자리가 하나 있는데 쓰지 않으면 0이 들어간다.

한 에포크의 비밀은 앞 에포크의 비밀과 이번 Commit이 만든 비밀을 섞어 만든다. 섞는 방향이 한쪽이라 지금 판의 상태를 모두 쥐어도 지난 판의 비밀로 거슬러 갈 수 없다.

섞는 재료가 둘이라는 점도 같이 본다. 지난 비밀만 쥐어서는 다음 비밀이 나오지 않고 이번에 갱신된 경로의 비밀을 함께 알아야 한다. 앞에서 본 사후 침해 보안이 여기에 걸려 있다. 털린 사람이 갱신을 한 번 올리는 순간 공격자에게 없는 재료가 섞여 들어간다.

epoch_secret을 그대로 쓰지 않는다

용도마다 다른 값을 뽑아 쓰고 규격이 적어 둔 것이 여덟 가지다. 묶으면 네 갈래다.

메시지를 가리는 쪽. encryption_secret에서 규격이 secret tree라고 부르는 구조를 펼쳐 멤버마다 래칫을 만든다. 앞에서 본 핸드셰이크 래칫과 애플리케이션 래칫이 여기서 나온다. sender_data_secret은 누가 보냈는지를 담은 부분을 따로 가리는 데 쓴다.

맞는지 확인하는 쪽. confirmation_key는 이 에포크가 제대로 적용됐는지 확인하는 값을 만든다. membership_key는 암호화하지 않고 보내는 메시지가 정말 멤버에게서 왔다는 것을 증명한다. epoch_authenticator는 두 기기가 같은 그룹 상태를 보고 있는지 맞춰 보는 데 쓴다.

나중을 위한 쪽. resumption_psk는 뒤에 이 에포크의 멤버였음을 증명하는 데 쓴다. external_secret은 초대를 받지 않고 들어오는 경로에 쓰는 열쇠 쌍의 재료다. 그중 공개키가 밖으로 나간다.

밖으로 내보내는 쪽. exporter_secret은 MLS 밖에서 쓸 열쇠를 뽑아 가는 자리다. 규격이 애플리케이션을 위해 열어 둔 문이다.

그리고 하나가 더 갈라진다. 다음 에포크의 init_secret이다. 이 값이 다음 판의 재료가 되면서 에포크가 줄줄이 이어진다.

용도를 쪼개 두는 이유는 하나가 새어도 나머지가 버티게 하려는 것이다. 확인용 값이 드러나도 메시지 열쇠는 거기서 나오지 않는다.

한 사람을 더하는 과정

조각이 실제로 어떻게 맞물리는지 한 번 따라가 보자. 여덟 명 방에 한 명을 더한다.

1. 초대하는 멤버가 Add 제안을 만든다. 새 멤버가 미리 올려 둔 공개 키 묶음을 가져와 Add Proposal에 담는다. 이 단계에서 바뀌는 것은 아직 없다.

2. 같은 멤버가 Commit을 보낸다. 쌓인 제안을 반영하면서 자기 direct path를 함께 갱신한다. 트리에 리프 노드가 하나 늘고 그 경로의 노드가 새 열쇠를 받는다.

3. 기존 멤버들이 Commit을 처리한다. 각자 자기 트리를 같은 모양으로 고치고 새 epoch_secret을 뽑는다. 에포크가 하나 올라간다.

4. 새 멤버에게 Welcome이 간다. 규격은 Welcome을 새 멤버가 자신이 추가된 에포크의 상태를 초기화하는 데 필요한 정보를 받는 메시지라고 적는다. 담기는 것은 지금 에포크의 트리 상태와 비밀이다. 지난 에포크의 것은 담기지 않는다.

2번이 멤버 변경과 열쇠 갱신이 겹치는 자리다. 초대가 곧 기존 멤버 전원에게 새 에포크가 시작되는 때다.

빼는 쪽도 모양이 같다. Remove 제안과 Commit이 올라가고 나가는 사람을 뺀 멤버 전원에게 새 재료가 돌아간다. 나간 사람은 그 재료를 모르니 그 뒤 대화는 열리지 않는다.

Welcome에 지난 에포크의 비밀이 안 담기는 것이 한 가지를 결정한다. 새로 들어온 사람이 이전 대화를 읽지 못하는 것은 정책이 아니라 구조다. 보여 주고 싶어도 줄 열쇠가 없다.

빠진 자리는 비워 둔다

멤버를 빼면 트리에 구멍이 생긴다. 규격은 값이 없는 노드를 blank라고 부르고 Remove를 적용하는 절차를 이렇게 적는다. 나가는 사람의 리프 노드를 blank로 바꾸고 그 리프에서 루트 노드까지 올라가는 중간 노드를 전부 blank로 만든다. 그 경로의 열쇠는 나간 사람도 알던 것이라 그대로 둘 수 없기 때문이다.

트리 자체도 줄인다. 오른쪽 부분트리에 비어 있지 않은 리프 노드가 하나라도 남을 때까지 오른쪽을 잘라 낸다.

여기서 비용 이야기가 다시 나온다. 앞에서 보낼 횟수가 경로의 길이라고 했는데 빈 노드가 많으면 그 말이 흐트러진다. 어떤 노드로 암호화하려면 그 아래에서 비어 있지 않은 노드를 찾아 전부 덮어야 하고 규격은 그 목록을 resolution이라고 부른다. 빈 노드가 늘어나면 목록이 길어지고 한 번에 보낼 수 있던 것이 여러 번으로 쪼개진다.

새로 들어온 사람도 비슷한 자리에 있다. 더해진 리프 노드는 위쪽 노드의 개인키를 아직 모른다. 더하는 과정이 위쪽 열쇠를 주지 않기 때문이다. 어떤 조상 노드의 개인키를 모르는 리프를 규격은 그 노드의 unmerged 리프라고 부른다. 그래서 그 조상 노드로 보낼 때는 노드의 공개키뿐 아니라 아래에 달린 unmerged 리프 하나하나에도 따로 암호화해야 한다. 그 리프가 나중에 열쇠를 받으면 비로소 합쳐진다.

정리하면 트리의 효율은 모양이 깔끔할 때의 값이다. 멤버가 자주 들고 나는 방은 빈 노드와 unmerged 리프가 쌓여 보낼 횟수가 로그에서 멀어진다. 멤버들이 각자 갱신을 한 번씩 올리면 경로가 다시 채워지면서 모양이 회복된다.

메시지 프레이밍

앞에서 본 것은 열쇠를 만들고 트리를 고치는 일이다. 그 열쇠로 감싼 봉투가 어떻게 생겼는지는 따로 정해져 있고 규격은 그 층을 프레이밍(framing)이라고 부른다.

규격은 프레이밍이 두 가지를 한다고 적는다. 그룹 밖에서 내용을 못 보게 하는 것과 보낸 사람을 확인하게 하는 것이다. 뒤쪽이 열쇠만으로는 안 되는 부분이다. 에포크 열쇠는 멤버 전원이 알고 있으니 열쇠로 열렸다는 사실은 멤버 중 누군가까지만 말해 준다.

서명이 누가 썼는지를 말한다

그래서 메시지마다 보낸 사람의 서명이 붙는다. 규격은 서명의 대상에 내용만 넣지 않는다. 프로토콜 판 번호와 봉투 종류와 그룹 상태까지 함께 묶어 서명한다. 그래서 같은 서명을 다른 그룹이나 다른 에포크로 옮겨 붙일 수 없다.

Commit에는 하나가 더 붙는다. 그 에포크가 맞게 적용됐는지 확인하는 값이고 앞에서 본 confirmation_key로 만든다.

봉투가 두 종류다

PrivateMessage는 서명하고 암호화한 봉투다. PublicMessage는 서명만 하고 암호화하지 않은 봉투다.

규격이 그은 선은 분명하다. 사람이 쓴 메시지는 반드시 PrivateMessage여야 한다. 그룹을 바꾸는 핸드셰이크 메시지는 PrivateMessage를 쓰는 쪽이 권장이고 전달 서비스가 그 내용을 들여다봐야 하는 경우에만 PublicMessage로 보내도 된다.

PublicMessage에는 멤버가 보낼 때 값이 하나 더 붙는다. 앞에서 본 membership_key로 만든 MAC이다. 암호화를 하지 않았으니 그룹 안에서 왔다는 증거가 따로 없기 때문이다. 서명은 그 열쇠의 주인이 썼다는 것까지만 말하고 지금 이 방의 멤버인지는 말하지 않는다. PrivateMessage는 에포크 열쇠로 열린다는 사실 자체가 그 증거라서 이 값이 없다.

누가 보냈는지도 가린다

봉투를 받으면 어느 열쇠로 열어야 할지 알아야 한다. 그 정보가 보낸 사람의 리프 노드 번호와 앞에서 본 generation이다. 그런데 그대로 적어 두면 암호문을 열지 못하는 쪽도 누가 몇 통 보냈는지 셀 수 있다.

그래서 규격은 그 정보도 암호화한다. 열쇠는 sender_data_secret과 본문 암호문의 앞부분을 섞어 만든다. 본문마다 암호문이 다르니 열쇠도 매번 달라진다. 여기에도 그룹 식별자와 에포크와 내용 종류를 함께 묶는다.

사람이 쓴 메시지는 규격이 PrivateMessage만 허용한다. 본문과 서명뿐 아니라 누가 보냈는지를 담은 부분까지 가려지고 밖에 남는 것은 전달에 필요한 세 가지다.

늦게 온 메시지

메시지에 그룹과 에포크와 generation이 적혀 있으므로 순서가 뒤바뀌어 도착해도 열 수 있다. 받는 쪽은 그 번호까지 래칫을 굴려서 맞춘다.

여기에 함정이 하나 있고 규격이 직접 경고한다. 누군가 generation을 아주 큰 값으로 적어 보내면 받는 쪽이 그 번호까지 열쇠를 유도하느라 수십억 번을 계산한다. 그래서 한 번에 굴릴 수 있는 칸 수에 상한을 두라고 적는다. 쓰지 않은 열쇠를 얼마나 오래 들고 있을지도 앱이 정할 일로 남겨 둔다.

표준이 풀지 않는 것

MLS를 쓴다고 끝나지 않는 것이 넷 있다. 설계를 시작하기 전에 알아 두는 편이 낫다.

누가 그 방에 있는지는 드러난다. 앞 절에서 본 것은 어느 메시지를 누가 보냈는지가 가려진다는 이야기이고 방에 누가 있는지는 다른 층이다. 들어오고 나가는 것은 전달을 하려면 알아야 한다. 내용이 아니라 메타데이터가 여기서도 남는다.

순서를 정하는 자리가 필요하다. 앞에서 본 대로 동시에 올라온 Commit 중 하나를 골라야 한다. 전달 서비스가 내용을 못 읽는 것과 아무 역할도 안 하는 것은 다르다.

신원은 MLS 바깥에서 온다. 규격은 전달 서비스는 거의 믿지 않으면서 인증 서비스는 믿는다고 가정한다. 상대의 공개키가 정말 그 사람 것인지를 보증하는 일은 MLS가 맡지 않는다. 그래서 종단간 암호화를 하고도 신원 검증은 따로 풀어야 하는 문제로 남는다.

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

자주 묻는 질문

전달 서비스가 순서를 정하면 그쪽을 믿는 셈 아닌가요

할 수 있는 일이 정해져 있다. 어느 Commit을 살릴지 고르고 특정 기기에게 전달을 끊거나 그룹을 둘로 갈라 놓을 수도 있다. 알아채기 어려운 쪽이라 앞에서 본 epoch_authenticator를 서로 맞춰 봐야 드러난다. 다만 내용을 읽거나 없는 메시지를 만들 수는 없고 신뢰의 종류가 다르다.

Proposal 없이 Commit만 보낼 수 있나요

보낼 수 있다. 바꿀 멤버가 없어도 자기 열쇠만 갱신하는 Commit을 올리면 에포크가 올라간다. 정기적으로 갱신하는 동작이 이 모양이다.

제안한 사람과 Commit 하는 사람이 달라도 되나요

된다. 제안은 쌓아 두는 것이고 그룹의 멤버라면 쌓인 제안을 모아 Commit을 올릴 수 있다. 제안과 반영을 나눈 이유가 여기 있다.

기기가 꺼져 있는 동안 올라온 에포크는 어떻게 되나요

켜진 뒤에 밀린 Commit을 순서대로 처리해야 따라잡는다. 에포크는 앞 에포크의 상태에서 다음 에포크를 뽑는 구조라 건너뛸 수가 없다.

양자 내성 암호로 바꿀 수 있나요

TreeKEM은 키 캡슐화 방식을 갈아 끼울 수 있는 구조라 그 자리에 양자 내성 방식을 넣는 작업이 IETF에서 진행 중이다. ML-KEM만 쓰는 갈래와 기존 타원곡선 방식과 함께 쓰는 하이브리드 갈래가 제안돼 있다. 다만 아직 RFC가 아니라 스위트 번호가 비어 있고 번호는 문서가 RFC가 될 때 배정된다.

참고한 자료