"순서 저장 암호화(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의 역사를 거슬러면 제일차 세계 대전부터 사용된 "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.)

볼디레와은 제한적인 환경에서는 OPE의 취약 공격인 CPA공격을 어느 정도 수준까지는 방어할 수 있다고 증명했다. 게다가, 제한 조건에서 OPE에 CPA공격을 블록 암호화 알고리즘과 동등한 수준으로 방어하는 것은 현실적으로 불가능하다는 것도 밝혔다.즉, 단순 알고리즘의 개선만으로 이 이상의 안전성을 기대하기 어렵다는 것이다.

알고리즘 자체만으로는 CPA공격으로부터 피할 수 없으니" 어떻게 가능할까"이 업계의 주요 관심사로 떠오르고 있다. 현재 대부분의 보안 업체들이 OPE의 안전성을 보완하고 주는 기술 및 보안 장치를 함께 사용하고 OPE의 취약성을 보완하기 위해서 노력하고 있다. OPE와 함께 다른 검증을 받은 암호화 알고리즘을 사용하거나 순서 정보만 더 암호화하는 것 등을 그 예로 꼽힌다.그러나 이런 상황에 대해서 잘 모르는 일반인들은 "순서의 저장 암호화"라는 명칭만 믿고 OPE을 다른 암호화 알고리즘처럼 안전성이 높다고 생각하기 쉽다.

실제로 어떤 회사에서는 OPE기술의 안전성을 과대 평가하고 업계의 비난을 사기도 했다. 그러므로 OPE관련 솔루션을 선택할 때는 제품 내에 OPE의 안전성을 보완하는 보안 장치 및 기술이 있는지를 알아본 후 제품을 선택해야 한다.특히 CPA공격은 공격자가 암호화 시스템에 접근할 수 있을 때 주로 발생하므로, 제품에 이러한 약점은 없는지를 확인해야 한다.

암호화를 필요로 하는 응용은 다양하다. 안전도가 높은 수준에서 요구되는 응용이 있으면 안전도가 높지 않아도 괜찮은 응용도 있다. OPE의 경우 안전성을 일부 희생하고 성능을 선택한 응용으로 보인다. 칼럼의 모두에 가상 시나리오의 주인공이었던 K씨처럼 개인 정보 보호를 필요로 하는 응용에서는 오랫동안 검증된 안전도를 보장하고 줄 수 있는 표준적인 암호화 기술이 필요하다.OPE는 오리지날 데이터의 순서가 암호화 후도 유지된다는 장점이 있기 때문에 데이터 검색 등에서 유용한 기술임에 틀림없지만 안전성에는 한계가 있다는 것을 잊어서는 안 된다.

그래서 보안 업계는 OPE기술을 적용할 경우 안정성이 취약한 부분과 정도에 대해서는 사용자에 정확히 알려야 한다. 한편 사용자는 기존의 블록 암호화 알고리즘과 비슷한 수준의 안전한 암호화를 제공하지는 않다는 것을 이해하고 안전도보다는 성능이 중요한 응용에 선택적으로 적용하도록 한다.이와 함께 부족한 안전도를 보완하는 보호 디바이스 및 기능이 제품 내에 탑재되어 있는지 꼭 검토해야 한다.