OPE(Order Preserving Encryption)는 안전한 암호화인가

일반기업에서 회사의 정보보안을 담당하고 있는 K씨는 요즈음 고민이 많다. 개인정보보호법 준수를 위해 개인정보들이 저장되어 있는 업무시스템에 암호화 제품을 도입하여 적용하려고 한다. 암호화 제품을 설치하면 개인정보보호법 준수는 문제가 없겠지만 업무시스템의 성능이 저하되지는 않을까 걱정이 크다. 그러던 중 우연히 OPE라는 기술을 채용했다는 암호화 제품의 광고를 보게 된다. OPE기술이 어떤 기술인지는 모르겠지만, 암호화 후에도 DB 검색의 성능 저하가 없다는 설명에 크게 와닿는다. OPE라는 이름이 Order Preserving Encryption이니 암호화(Encryption)가 될 것이고 성능저하도 해결된다니 자신의 고민을 한 번에 해결해줄 것만 같다.

개인정보보호를 위해 DB암호화 제품을 도입하는 경우가 늘면서 위의 가상 이야기처럼 OPE에 대한 관심이 늘고 있다. OPE(Order Preserving Encryption)은 어떤 기술이고, 얼마나 안전한지, 개인정보보호의 안전성과 성능저하 극복의 두 마리 토끼를 잡은 기술일까를 살펴보기로 하자.

순서를 유지하는 암호화는 근본적으로 위험

DB암호화는 개인정보보호를 위한 필수 기술로 인식되고 있다. DB서버에 암호화를 적용하면, DB서버에 저장되는 데이터를 암호화하여 저장하고, 데이터를 조회할 때에는 암호화된 데이터를 복호화한 후 사용자에게 제공된다. DB서버는 암호화와 복호화를 위한 처리연산을 추가로 수행해야하기 때문에 속도 저하가 불가피하다. 암호화 적용으로 인한 DB서버의 성능 저하 문제는 암호화 알고리즘의 효율적인 구현 기술로 해결할 수 있다. DB암호화에서 더 중요한 문제는 검색 색인을 생성하는 문제이다. 검색 색인은 DB에 저장되어 있는 방대한 데이터 중에서 원하는 데이터를 빠르게 조회하기 위해 사용되는 DB 내부의 추가 정보이다. 암호화 된 데이터들로부터 원하는 데이터를 검색하려면 암호화가 되기 전의 원본 데이터들을 알아야 하기 때문에 암호화된 데이터를 전부 일일이 복호화 해야한다. 원하는 데이터를 하나 조회할 때마다 방대한 데이터들을 모두 복호화해야하기 때문에 엄청난 연산량의 부담이 발생할 수 밖에 없다. 이를 해결하는 방법들 중의 하나가 바로 순서유지암호화(Order Preserving Encryption, 이하 OPE)이다.

OPE는 꽤 오래 전부터 존재하던 기술이다. OPE의 역사를 보자면, 세계 1차 대전 때부터 사용된 One-Part Code 기술이 OPE의 시조라 할 수 있다. 암호화된 데이터들에 대해서도 DB의 검색 색인을 용이하게 만들 수 있다는 특장점 때문에 2000년대부터 DBMS업계에서 주목 받기 시작했다. 2004년에는 R.Agrawal을 포함한 4명의 IBM 연구원들이 처음으로 OPE라는 용어를 정의하였다. 그들은 OPE 개념에 대한 수학적 모델과 구현에 대한 방향성을 제시하였으나, 안전성에 대한 구체적인 언급이나 증명을 하지는 않았다. (참고문헌 : R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu, “Order-preserving encryption for numeric data”, SIGMOD 2004, pp. 563~574)

데이터를 빠르게 조회하기 위해서는 데이터를 순서대로 정렬을 해두어야 한다. 가령, 수백만 명의 주민등록번호들 중에서 내가 찾는 주민등록번호가 포함되어 있는지를 쉽게 찾는 방법은 주민등록번호를 13자리 자연수로 보고 크기 순서대로 정리해 두는 것이다. 불행히도 이 방법은 암호화 후에 사용할 수 없다. 암호화는 원본 데이터를 예측할 수 없는 임의의 값으로 변환하는 과정이기 때문에 암호화된 데이터는 원본 데이터와는 전혀 다른 순서로 정렬될 수 밖에 없다. 암호화를 적용하더라도 암호된 데이터들이 원본 데이터와 동일한 순서로 정렬될 수 있도록 해주는 방법이 OPE이다. 크기가 작은 순서로 정렬된 숫자 데이터 1234, 3456, 5678의 세 수가 있다고 가정하자. 일반적인 암호화를 적용하면 세 수의 암호화된 값들 사이의 순서가 섞이게 된다. OPE를 적용하면 1234의 암호값이 3456의 암호값보다 앞에 정렬되고, 3456의 암호값은 5678의 암호값보다 앞서게 된다.

순서유지암호화라는 이름처럼 OPE는 안전한 암호화일까? 안전한 암호화는 암호문으로부터 원본 데이터에 대한 어떤 정보도 얻을 수 없어야 한다. OPE는 암호문에서 ‘순서’라는 정보를 얻을 수 있고 이를 바탕으로 평문을 유추할 수 있다. 앞서 설명했던 1234, 3456, 5678의 예로 돌아가 보자. 1234의 암호문(A)과 3456의 암호문(B)을 안다면, 암호문A와 암호문B 사이에 정렬될 수 있는 암호문C는 1234와 3456의 사이에 있는 어떤 값으로부터 만들어진 암호문임을 알 수 있다. 이 경우에 암호를 해독하려고 시도하는 공격자가 1234와 3456을 알고 두 수를 암호화한 값(암호문 A, B)들도 알고 있기 때문에 이러한 공격 방법을 선택평문공격(Chosen Plaintext Attack; 이하 CPA)이라 한다. 안전한 암호알고리즘은 CPA 공격모델을 채용한 공격자가 암호문C가 어떤 수를 암호화한 값인지를 구분할 수 없는 비구별성(Indistinguishability)를 만족해야 하지만, OPE는 이를 만족하지 못하기 때문에 안전한 암호화라 할 수 없는 것이다. 따라서 OPE는 DES, AES, SEED, ARIA 등과 같은 보통의 블록암호화알고리즘과 어깨를 나란히 할만한 높은 수준의 안전성을 갖추고 있지 않다. 세계의 정보보안 관련 표준들에서 OPE를 찾아볼 수 없는 것도 이러한 이유이다.

순서유지를 제공하는 안전한 암호화는 불가능한 것일까라는 문제를 해결하기 위해 미국 조지아텍(Georgia Tech)의 Boldyreva 교수를 포함한 4명의 연구자들이 2009년 연구결과를 발표했다. (참고문헌: A. Boldyreva, N. Chenette, Y. Lee, A. O’Neill, “Order-Preserving Symmetric Encryption”, EUROCRYPT 2009, pp. 224~241.) Boldyreva는 제한적인 환경에서는 OPE의 취약 공격인 CPA 공격을 어느 수준까지는 방어할 수 있다고 증명하였다. 뿐만 아니라 제한 조건들 때문에 OPE로 CPA공격을 블록암호화알고리즘과 동등한 수준으로 방어하는 것은 현실적으로 불가능하다는 것도 밝혀내었다. 즉, 단순 알고리즘의 개선만으로는 더이상의 안전성을 기대하기는 어렵다는 것이다.

알고리즘 자체만으로는 CPA공격으로부터 안전할 수 없으므로, ‘어떻게 구현할 것인가’가 업계의 주요 관심사로 대두되고 있다. 현재 대부분의 보안 업체들이 OPE의 안전성을 보완해 줄 기술 및 보안장치를 함께 사용하여 OPE의 취약점을 보완하기 위해 노력하고 있다. OPE와 함께 다른 검증받은 암호화 알고리즘을 함께 사용한다거나, 순서정보만을 한번 더 암호화 하는 것 등을 그 예로 들 수 있다. 그러나 이러한 상황에 대해 잘 알지 못하는 일반인들은 순서유지 ’암호화’라는 이름만 믿고 OPE를 다른 암호화 알고리즘처럼 안전성이 뛰어나다고 생각하기 쉽다. 실제로 어떤 업체에서는 OPE기술의 안전성을 과대 포장해 업계의 비난을 사기도 했다. 따라서 OPE관련 솔루션을 선택할 때에는, 제품 내에 OPE의 안전성을 보완해주는 보안장치 및 기술이 있는지를 살펴본 후 제품을 선택해야 한다. 특히, CPA 공격은 공격자가 암호화 시스템에 쉽게 접근할 수 있을 때 주로 발생하므로, 제품에 이러한 허점은 없는지 확인해 보아야 한다.

암호화를 필요로 하는 응용은 다양하다. 안전도가 높은 수준으로 요구되는 응용이 있는가하면 안전도가 높지 않아도 괜찮은 응용도 있을 수 있다. OPE의 경우 안전성을 일부 희생하고 성능을 택한 응용이라고 볼 수 있다. 글의 서두에 가상 시나리오의 주인공이었던 K씨처럼 개인정보의 보호를 필요로 하는 응용에서는 오랫동안 검증되고 높은 안전도를 보장해줄 수 있는 표준적인 암호화기술이 필요하다. OPE는 원본 데이터의 순서가 암호화 후에도 유지된다는 장점이 있기 때문에 데이터 검색 등에서 유용한 기술임에 분명하지만, 안전성에는 한계가 있다는 것을 잊지 말아야 한다. 따라서 보안 업계는 OPE 기술을 적용할 경우, 안정성이 취약한 부분과 정도에 대해서는 사용자에게 정확하게 알려야 한다. 한편, 사용자는 기존의 블록암호화 알고리즘들과 동일한 수준의 안전한 암호화를 제공하지는 않는다는 것을 이해하고, 안전도보다는 성능이 중요한 응용에 선택적으로 적용하도록 한다. 이와 더불어, 부족한 안전도를 보완해 줄 보안장치 및 기능이 제품 내에 탑재되어 있는지를 꼭 검토해야 한다.