제2058호-[사이버보안] 순서 보존 암호 최신 연구 동향(손선희)

1.서론

등장배경	-데이터 중요성이 강조되는 클라우드 서비스, 빅데이터, 인공지능 등의 기술에 대해 전통적인 정보보호 기술로는 정보보호와 활용이라는 양립되는 문제를 해결하기가 어렵다. -암호화된 데이터베이스 효율적인 접근에 대한 암호기술로 순서보존암호가 부각되고 있다.
개념	평문의 순서를 암호화 이후에도 순서를 보존하므로 기밀성을 유지하면서 효율적인 검색을 가능하게 하는 암호화 알고리즘
데이터베이스 검색 가능 암호 알고리즘 연구분야	1.순서 보존 암호 2.대칭키 기반 검색 가능한 암호 3.공개키 기반 검색 가능한 암호 4.순서 노출 암호
순서 보존 암호 두각	순서보존암호는 다른 기술과 비교했을 때 적당한 안정성과 높은 효율성을 제공하는 기술로 실용화에 가장 가까운 기술이다.

 

2.순서 보존 암호 기술 연구 동향

모델	발표년도, 발표자	설명
0.순서 보존 암호의 개념 등장	2004년 Agrawa	-평문의 크기 순서가 암호화된 이후에도 유지되는 순서 보존 암호의 개념 등장
1.IND-OCPA(indistinguishability under ordered chosen-ciphertext attack) 안전성 모델	2009년 Boldyreva	-(1)구분불가능성(indistinguishability: IND)의 개념 사용 - IND-OCPA는 공격자가 선택한 두 개의 평문 나열 중 하나의 암호문 나열을 보고 어느 쪽의 평문 나열이 암호화된 것인지 구분할 수 없다는 IND-CPA 정의에서 변형 -(정의) 두 평문 나열의 크기 순서가 같을 때 주어진 순서 보존 암호문 나열을 보고 구분할 수 없다 -암호문의 크기가 평문 개수의 지수적으로 커질 수밖에 없음을 증명
		-(2)순서보존 유사 난수 함수를 암호화로 하는 방식 제시 , (취약점) 평문의 절반 정보가 노출
	2013년 Popa	-(3) 불가능성을 우회한 방식은 한번 암호화하면 암호문이 변하지 않는 것이 아닌 필요에 따라 암호문을 변경하는 것이다 -복호화를 위한 데이터 암호문이 변경되는 것은 아니며 순서 정보를 나타내 는 인코딩값이 암호문에 추가되며 필요 시 인코딩값만 변경된다 -IND-OCPA를 만족 하는 가변(mutable) 순서 보존 암호가 제시된 이후로 효율적이면서 안전성이 더 높은 가변 순서 보존 암호
2.IND-FAOCPA(indistinguishability under frequency analyzing ordered chosen-ciphertext attack) 안전성 모델	2015년 Kerschbaum	-초기의 순서 보존 암호는 결정적 암호화 방식이거나 동일한 평문의 개수가 노출되는 방식이었다. 동일한 암호문의 빈도수를 이용한 공격에 취약할 수 있다 -(4) 평문의 빈도수를 숨기기 위한 순서 보존 암호 기법 제시 -평문의 중복이 허용된 두 평문 나열이 최소 하나의 동일한 순서를 가지면 주어진 순서 보존 암호문을 보고도 두 평문 나열 중 어떤 평문 나열이 암호화된 것인지 구분할 수 없다

 

3.가변 순서 보존 암호

-현재 발표된 대부분의 가변 순서 보존 암호문은 비가변 데이터 암호문과 평문의 크기 순서 를 유지하는 가변 인코딩으로 구성된다.

-주로 OPE 응용 환경 인 데이터베이스 서버에 암호문을 삽입하고 범위 질의를 보내는 모델을 고려하여 기법이 설계되는데 스테이트 정보의 저장 위치에 따라 서버-스테이트, 클라이언트-스테이트 기법으 로 구분하기도 한다.

* 가변 순서 보존 암호에서 추가 암호문 삽입 시 필요한 경우 이미 다른 암호문에 부여된 인코딩을 업데이트해야 한다. 인코딩 업데이트를 리코딩 (re-encoding)이라 하며 이때 필요한 정보를 스테이트(state)라 한다.

기법	설명
서버-스테이트 기법	- Popa 등의 기법은 이진 탐색 트리가 인코딩을 위한 스테이트이고 이를 서버에서 관리한다. 서버는 이진 탐색 트리에 저장된 암호문의 순서만 알 뿐 다른 정보를 알 수 없으므로 해당 기법은 IND-OCPA 안전성을 만족할 수 있다.  -(특징) 클라이언트가 새로운 암호문 삽입 또는 범위 질의를 하기 위해서는 루트노드부터 말단 노드까지 특정 평문의 위치를 찾을 때까지 서버에게 노드의 암호문을 받아 복호화해서 비교하고 그 결과를 서버에게 알려 주는 추가적인 인터렉션이 필요 -(취약점) 평문의 빈도수가 노출되는 기법으로 뒤에서 설명할 추론 공격
클라이언트-스테이트 기법	-2015년에는 평문의 빈도수를 이용한 추론 공격으로부터 안전하도록 평문 빈도수를 숨기 는 기법이 제안 - 데이터 암호문이 아닌 평문을 이진 탐색 트리에 저장하며 스테이 트인 이진 탐색 트리를 클라이언트가 관리하는 클라이언트-스테이트 기법 -빈도수를 노출하지 않기 위해서 데이터 암호문은 확률적(probabilistic) 암호문을 이용하여 암호화하 며, 트리 탐색 과정 중 중복되는 값을 만나게 되면 무작위 코인을 이용하여 경로를 결정 -(인코딩방식) 클라이언트가 새로 암호화할 평문이 저장된 트리의 위치를 탐색하고 저장했 을 때 크기순으로 양옆의 값의 중간 값으로 인코딩한다.
서버-클라이언트-스테이트 기법	- 질의문 처리 단계에서 인터렉션을 통한 정렬을 수행하기 때문에 질의 문 처리가 느린 단점을 보완 - 2021년에는 (1)인터렉션이 없으면서 (2)클라이언트 저장량을 줄이기 위해 스테이트를 서버와 클라이언트가 나눠서 갖도록 설계된 평문 빈도수 감춤 기법이 발표 -(특징) 동일한 평문이 많이 나타나는 데이터를 암호화할 때 매우 효율적으로 클라 이언트 저장량이 줄어들지만 반대의 경우에는 큰 효과가 없는 것이 기법의 특징 -동일한 평문도 확률적 암호 알고리즘으로 암호화되기 때문에 데이터 암호문이 다르며 저장되는 순 서위치도 달라서 다른 인코딩 값을 가지므로 빈도수 숨김을 제공

 

4.순서 보존 암호 공격

- 순서 보존 암호화가 적용된 데이터베이스를 공격하는 방법에는 크게 추론 공격(inference attack)과 볼륨(volume attack) 공격이 있다. 

 

 

추론 공격(inference attack)

- (정의) 공공기관이 공개하는 통계치와 같이 공개된 데이터를 보조(auxiliary) 데이터 로 사용하여 순서 보존 암호문의 평문을 추론 분석하는 공격

-추론 공격은 보조 데이터와 암호화된 데이터의 분포가 유사할수록 공격의 정확도가 높아지며, 매우 유사한 경우 단순한 정렬 공격조차 높은 정확도를 가질 수 있다.

추론공격 알고리즘	공격 방법	공통점	차이점
결정적인 순서 보존 암호 알고리즘 - 빈도수 이용	축적(cumulative) 공격		1.그래프의 가중치를 정의하는 방법 2.이분 그래프의 순서 교차(crossing) 허용 여부
	비교차(Non-crossing) 공격
확률적 암호 알고리즘 - 빈도수를 알지 못할때	이항분포(binomial distribution) 공격	-특정 평문의 보조 데이터로부터 계산되는 이항 확률값 을 통해 해당 평문 암호문이 처음 나타나는 위치와 해당 평문 암호문의 개수 기댓값을 계산하여 순서 보존 암호문들 사이에서 해당 평문의 암호문이 어느 위치에 있는지 추론하는 방법

 

 

5.결론

- 순서보존암호는 검색 가능한 암호화 기술 중에서 효율성과 안전성을 고려할 때 실용화에 가장 가까운 기술이지만

- 몇가지 고려사항 요구 된다.

 

고려사항

1.중복이 발생하지 않는 데이터는 '빈도수 감춤 기능'을 사용하지 않아도 된다.

2.중복이 많이 발생하는 데이터는 '빈도수 감춤 기능'을 제공하는 최적을 알고리즘을 선택한다.

3.데이터의 크기, 순서도 보존해야하는 경우에는 사용하면 안된다.

4.데이터 셋이 공개되어 있는 데이터 셋과 유사한 분포를 가지고 있는 경우, '빈도수 감춤 기능'을 사용하지 않을 경우 추론공격에 매우 위험 할 수 있다.