개인정보 암호화와 검색, 암호화한 이메일로 회원을 찾는 법

회원 테이블의 이메일 열을 암호화해 저장하라는 요구를 받으면, 암호화 자체는 라이브러리로 금방 붙는다.
문제는 그다음에 생긴다.
로그인할 때 이메일로 회원을 찾던 쿼리가 아무것도 찾지 못한다.

데이터베이스는 저장된 값과 입력한 값이 같은지 비교해서 행을 찾는다.
저장된 값이 암호문으로 바뀌었으니 입력한 이메일과 같을 수가 없다.
같은 이메일을 다시 암호화해서 비교하면 될 것 같지만, 요즘 쓰는 방식에서는 그것도 통하지 않는다.

AES는 같은 키로 암호화하고 복호화한다

원문을 읽을 수 없는 형태로 바꾸는 것을 암호화, 다시 원문으로 되돌리는 것을 복호화라고 한다.
이때 쓰는 비밀 값이 키다.

AES(Advanced Encryption Standard)⁠는 같은 키로 암호화와 복호화를 모두 하는 대칭키 암호다.
미국 국립표준기술연구소(NIST)⁠가 공개 경쟁을 거쳐 2000년 Rijndael이라는 암호를 골랐고, 2001년 표준으로 발표했다.

AES-128, AES-192, AES-256은 키 길이만 다른 같은 표준이다.
AES를 실제로 쓸 때는 운영 모드라는 방식을 함께 고른다.

그중 GCM(Galois/Counter Mode)⁠은 내용을 숨기는 데 더해, 암호문이 중간에 바뀌지 않았는지 확인하는 기능까지 준다.
암호화하면 암호문과 함께 인증 태그라는 짧은 값이 나오고, 복호화할 때 이 값이 맞지 않으면 실패한다.

OWASP의 암호화 저장 지침도 GCM 같은 인증 모드를 우선 쓰라고 권한다.
OWASP는 소프트웨어 보안을 높이는 일을 하는 비영리 재단이다.

같은 이메일인데 암호문은 매번 다르다

GCM으로 암호화할 때는 키 말고도 IV(Initialization Vector)⁠라는 값을 하나 더 넣는다.
IV는 암호화할 때마다 새로 정하는 값이다.
비밀은 아니어서 암호문 옆에 함께 저장한다.

IV가 매번 다르니 같은 이메일을 두 번 암호화해도 암호문은 서로 다르다.
데이터베이스를 들여다본 사람이 같은 값이 반복된다는 사실조차 알아채지 못하게 하는 장치다.

그렇다면 IV를 고정하면 검색이 되지 않을까.
GCM에서는 절대 하면 안 되는 일이다.
NIST의 GCM 표준은 같은 키에서 IV가 한 번이라도 반복되면 보안이 거의 전부 무너질 수 있다며, IV를 겹치지 않게 하는 일을 키를 비밀로 지키는 일에 버금가는 요구로 다룬다.

암호문은 원문을 지키는 데만 쓰고, 검색은 다른 값으로 한다.

검색은 따로 만든 토큰으로 한다

검색용 값을 만들려면 해시 함수를 먼저 알아야 한다.
암호에서 쓰는 해시 함수는 어떤 입력이든 정해진 길이의 값으로 바꾼다.
같은 입력은 언제나 같은 값이 되고, 나온 값에서 원래 입력을 거꾸로 계산해 낼 수는 없다.

검색에 쓰는 값은 HMAC⁠으로 만든다.
HMAC은 비밀 키와 해시 함수를 함께 써서 입력마다 고정된 길이의 값을 만드는 방식이다.
원래는 메시지가 바뀌지 않았는지 확인하는 데 쓰여 왔다.

HMAC은 같은 키에 같은 입력을 넣으면 항상 같은 값이 나온다.
이메일로 이 값을 만들어 따로 저장해 두면, 로그인할 때 입력한 이메일로 같은 계산을 해서 값이 같은 행을 찾을 수 있다.
이 글에서는 이 값을 검색 토큰이라고 부른다.

키 없는 해시 함수만 써도 같은 값은 나온다.
그런데 이메일은 추측하기 쉬운 값이라, 누구든 흔한 이메일 목록을 해시해서 데이터베이스와 대조해 볼 수 있다.
HMAC은 검색 키를 모르면 이 대조를 할 수 없다.

같은 예시 값 A를 한 번 더 저장해 두 결과를 비교한다.

저장 1 · 암호문

2513802483bf…

검색 토큰 b9d55cbf7741…

저장 2

아직 없음

AES-GCM에 고유한 IV를 쓰면 같은 값의 암호문이 달라진다. 별도 키의 HMAC 토큰은 같아서 같은 값을 찾을 수 있다.

첫 저장의 암호문과 검색 토큰이다. 둘은 서로 다른 키로 계산했다.

암호문은 달라졌지만 검색 토큰은 같다. 같은 값의 두 기록을 찾고 반복도 알아볼 수 있다.

예시 값만 미리 계산했으며 개인정보나 키를 입력받지 않는다. 화면은 앞부분만 표시한다. 검색 토큰은 반복을 숨기거나 익명화를 보장하지 않는다.

이 방식은 실제 제품에도 쓰인다.
AWS Database Encryption SDK⁠는 HMAC으로 만든 검색용 값을 비콘(beacon)⁠이라고 부르고, 암호화한 데이터 옆에 함께 저장한다.

데이터베이스에는 두 묶음이 남는다

한 이메일에서 출발한 값이 데이터베이스에는 두 묶음으로 남는다.
원문을 되살리기 위한 암호문 묶음과, 같은 값을 찾기 위한 검색 토큰이다.

목적	데이터베이스에 남는 것	쓰는 키
권한 있는 화면에서 원문을 보여 준다	암호문, IV, 인증 태그와 키 버전	암호화 전용 키
정확히 같은 값을 찾는다	HMAC 검색 토큰과 키 버전	검색 전용 키

IV와 인증 태그, 키 버전은 비밀이 아니어서 암호문과 함께 둬도 된다.
비밀로 지킬 것은 키 자체다.

OWASP는 가능하면 키를 암호화한 데이터와 다른 곳에 두라고 권한다.
그래야 데이터베이스만 새어 나갔을 때 키까지 함께 넘어가지 않는다.

암호화 키와 검색 키도 따로 둔다.
NIST도 키 하나는 한 가지 목적에만 쓰라고 권한다.
그러면 한쪽 키를 바꾸거나 한쪽이 새어 나가도 다른 쪽까지 흔들리지 않는다.

토큰은 늘 같은 규칙으로 만든다

토큰을 만들기 전에는 입력을 같은 규칙으로 다듬는 정규화를 거쳐야 한다.
대소문자만 다른 이메일, 하이픈 유무만 다른 전화번호를 같은 값으로 볼지는 암호 알고리즘이 정해 주지 않는다.
저장할 때와 검색할 때 같은 규칙을 써야 같은 토큰이 나온다.

토큰 만들기를 빠뜨린 경로가 있어도 문제가 된다.
회원 가입이나 정보 수정처럼 데이터를 쓰는 경로 가운데 하나라도 토큰을 빠뜨리면, 그 경로로 들어온 회원은 검색에 걸리지 않는다.

조회는 오류 없이 빈 결과를 돌려주니 그 회원은 없는 사람처럼 보인다.
그래서 데이터를 쓰는 모든 경로가 토큰을 만드는지 테스트로 확인해 둔다.

검색 토큰이 드러내는 것

검색 토큰은 원문을 그대로 적은 색인보다는 안전하지만, 아무것도 드러내지 않는 것은 아니다.
같은 값이면 같은 토큰이 나오므로, 데이터베이스만 봐도 어느 행들이 같은 이메일을 가졌는지 보인다.

이 반복 횟수로 원문을 짐작하는 공격을 빈도 분석이라고 한다.
그래서 AWS Database Encryption SDK는 HMAC 값을 일부러 짧게 잘라, 서로 다른 값이 같은 비콘을 갖기도 하게 만든다.

대신 검색 결과에 다른 값의 행이 섞일 수 있어서, 복호화한 원문으로 한 번 더 확인하는 단계가 필요하다.

검색 키까지 새어 나가면 이야기가 달라진다.
공격자가 흔한 이메일 목록으로 토큰을 만들어 대조할 수 있다.
검색 키도 암호화 키만큼 조심해서 다뤄야 한다.

이 토큰으로는 정확히 같은 값만 찾을 수 있다.
이메일의 일부로 찾거나, 범위로 찾거나, 정렬하는 검색에는 쓸 수 없다.

비밀번호는 암호화하지 않는다

이메일과 달리 비밀번호는 원문을 다시 볼 일이 없다.
그래서 복호화할 수 있게 암호화하지도, 빠른 HMAC으로 저장하지도 않는다.

OWASP는 Argon2id처럼 일부러 느리게 만든 비밀번호 해시를 쓰라고 권한다.
후보를 대량으로 넣어 보는 계산을 비싸게 만들기 위해서다.

키를 바꾸는 동안에도 찾을 수 있어야 한다

키는 영원히 쓰지 않는다.
오래 쓴 키를 새 키로 바꿔야 할 때가 오는데, 이미 저장된 암호문과 토큰을 한순간에 모두 바꿀 수는 없다.

그래서 행마다 어떤 세대의 키를 썼는지 키 버전을 함께 저장한다.
새 데이터는 새 키로 쓰고, 아직 옮기지 않은 행은 기록된 버전의 키로 읽는다.

뒤에서는 옛 행을 조금씩 새 키로 다시 암호화하고 토큰도 다시 만든다.
다시 만든 결과를 실제로 열어 보고 찾아본 뒤, 옛 키로 된 행이 하나도 남지 않았을 때 옛 키를 폐기한다.

검색 키를 바꿀 때는 한 가지가 더 까다롭다.
전환하는 동안 같은 이메일이 옛 키의 토큰과 새 키의 토큰 두 가지로 저장돼 있으니, 검색할 때도 두 토큰을 모두 만들어 찾아야 한다.

이 작업은 중간에 멈췄다 다시 시작해도 같은 결과가 나오게 만들어야 한다.
일부만 옮겨진 채 실패를 놓치면 그 행들만 옛 키에 남는다.

암호화를 설계할 때 먼저 묻는 질문

개인정보 암호화를 설계할 때는 알고리즘 이름보다 질문 세 개가 먼저다.
누가 원문을 다시 봐야 하는가, 어떤 검색이 꼭 필요한가, 데이터베이스만 통째로 유출됐을 때 무엇까지 드러나도 되는가.

첫 질문의 답이 ‘아무도’⁠라면 복호화할 수 있는 암호문으로 둘 이유가 없다.
비밀번호처럼 해시로 충분하거나, 처음부터 저장하지 않아도 되는 값일 수 있다.

검색 토큰은 정말로 같은 값 검색이 필요한 열에만 붙인다.
토큰을 붙인 열마다 반복 패턴이 하나씩 데이터베이스에 남기 때문이다.