" 순서 보존 암호화 (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)

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

알고리즘 자체만으로는 CPA 공격에서 벗어날 수 없기 때문에, "어떻게 실현할 것인가 ' 가 업계의 주요 관심사로 떠오르고있다. 현재 대부분의 보안 회사가 OPE의 안전성을 보완 해주는 기술 및 보안 장치를 함께 사용하고 OPE의 취약점을 보완하기 위해 노력하고있다. OPE 함께 다른 검증을받은 암호화 알고리즘을 사용하거나 순서 정보 만 추가 암호화하는 것 등을 그 예로들 수있다. 그러나이 같은 상황에 대해 잘 모르는 일반인들은 "순서 보존 암호화 '라는 이름 만 믿고 OPE를 다른 암호화 알고리즘과 같이 안전성이 높다고 생각하기 쉽다.

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

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

따라서 보안 업계는 OPE 기술을 적용 할 경우 안정성이 취약한 부분과 정도에 대해서는 사용자에게 정확히 알려야한다. 한편, 사용자는 기존의 블록 암호화 알고리즘과 동일한 수준의 안전한 암호화를 제공하거나하지 않는다는 것을 이해하고 안전도보다 성능이 중요한 응용에 선택적으로 적용하도록 . 그러면서 부족한 안전도를 보완 해주는 보안 장치 및 기능이 제품 내에 포함되어 있는지를 꼭 검토해야한다.