접근 패턴 유출 위협

데이터를 암호화하면 권한이 없는 당사자로부터 데이터 내용을 보호할 수 있지만, 암호화만으로는 데이터에 접근하는 방식에 관한 메타데이터까지 숨길 수 없습니다. 어떤 기록을 읽거나 쓰는지, 언제 접근하는지, 얼마나 자주 접근하는지와 같은 접근 패턴은 데이터 자체가 완전히 암호화되어 있어도 민감한 정보를 드러낼 수 있습니다. 내용 프라이버시와 접근 프라이버시 사이의 이 간극이 망각형 RAM의 핵심 동기입니다.

접근 패턴을 분석하면 다음과 같은 정보를 알아낼 수 있습니다. 사용자가 어떤 데이터베이스 기록을 조회하는지(어떤 기록에 접근하는지를 바탕으로 질환을 추론), 통신 패턴(메시지 내용이 암호화되어 있어도 누가 누구에게 연락하는지), 금융 활동(사용자가 어떤 가격 정보를 요청하는지를 바탕으로 거래 전략을 추론), 행동 패턴(접근 시각과 빈도를 바탕으로 일상적인 생활 패턴을 추론)입니다. 이러한 추론 결과는 데이터 내용 자체만큼 민감할 수 있습니다.

CryptDB(MIT, 2011)는 암호화된 데이터베이스를 조회하기 위한 영향력 있는 시스템이었습니다. 이후 Grubbs, McPherson, Naveed, Ristenpart, Spooner가 수행한 연구(2016)는 CryptDB와 유사한 순서 보존 암호화 방식이 추론 공격을 가능하게 하는 접근 패턴을 유출한다는 사실을 밝혔습니다. 접근 분포에 관한 보조 데이터 세트를 가진 공격자는 암호화를 깨지 않고도 접근 빈도와 순서만으로 평문 값을 추론할 수 있습니다.

암호화된 클라우드 저장소 서비스가 어떤 암호문 블록에 접근했는지 로그로 기록하면, 공격자는 빈도 분석을 수행할 수 있습니다. 사용자는 인기 있는 파일에 더 자주 접근하는 경향이 있으므로, 암호문 블록의 접근 빈도 히스토그램은 평문 접근 분포를 반영합니다. 암호화된 빈도 히스토그램을 알려진 접근 패턴과 대조하면 어떤 암호화된 파일이 인기 콘텐츠 범주에 해당하는지 식별할 수 있습니다.

정직하지만 호기심 많은(준정직) 위협 모델에서 클라우드 제공자는 프로토콜을 올바르게 따르지만 클라이언트 데이터에 대한 모든 접근 패턴을 관찰합니다. 많은 클라우드 제공자는 청구, 오류 수정, 성능 최적화를 위해 접근 패턴을 합법적으로 로그로 기록합니다. 악의적인 의도가 없더라도 이러한 로그는 위험을 초래합니다. 클라우드 제공자가 침해되거나, 악의적인 직원이 있거나, 정부의 소환장이 발부되면 민감한 접근 패턴이 노출될 수 있습니다.

Goldreich와 Ostrovsky가 1996년에 소개한 망각 RAM(ORAM)은 서버에서 접근 패턴을 숨기는 암호학적 기본 도구입니다. ORAM 방식에서는 실제로 어느 위치에 접근하는지와 관계없이 모든 메모리 위치에 대한 각 접근(읽기 또는 쓰기)이 서버에서 볼 수 있는 연산에 대해 동일한 분포를 생성합니다. 서버를 관찰하는 공격자는 균일하게 무작위인 접근 패턴만 볼 수 있습니다.

ORAM은 접근 패턴의 비공개성이 필요한 다양한 분야에서 폭넓게 활용됩니다. 예를 들어 안전한 클라우드 저장소(사용자가 어떤 파일에 접근하는지 숨김), 망각 데이터베이스 질의(질의가 어떤 행을 반환하는지 숨김), SGX 엔클레이브(엔클레이브 메모리에 대한 접근 패턴 부채널 방지), 비공개 정보 검색(사용자가 어떤 데이터베이스 항목을 가져오는지 숨김), 안전한 다자간 계산(중간 상태에 대한 접근 패턴 숨김) 등에 사용됩니다.

가장 단순한 ORAM 해결책은 자명합니다. 어떤 블록 하나에 접근하든 전체 저장소의 모든 블록을 읽고 다시 기록하는 것입니다. 이렇게 하면 어떤 블록에 접근했는지 숨길 수 있지만(모든 접근이 동일하게 보임), 논리적 접근마다 O(n)의 통신 오버헤드가 발생하므로 대규모 데이터셋에는 전혀 실용적이지 않습니다. 실제 ORAM 방식은 완벽한 또는 통계적 접근 패턴 은닉성을 유지하면서 이 오버헤드를 O(polylog n)으로 줄이려고 합니다.

Goldreich와 Ostrovsky는 하한을 증명했습니다. 서버 저장 공간 오버헤드가 O(1)인 모든 ORAM은 접근마다 최소 Omega(log n)의 통신 오버헤드를 부담해야 합니다. 이 로그 하한은 결정론적 ORAM에 적용됩니다. 실제 구현은 O(log^2 n) 또는 O(log n)의 오버헤드를 달성하여 이론적 최솟값에 근접하는 것을 목표로 합니다. 이 하한은 접근 패턴을 완벽하게 숨기려면 피할 수 없는 비용이 따른다는 것을 보여 줍니다.

검색 가능한 대칭 암호화(SSE)를 사용하면 암호화된 데이터를 검색할 수 있습니다. 기본 SSE 방식은 검색 패턴(어떤 키워드를 검색하는지)과 접근 패턴(어떤 문서가 반환되는지)을 노출합니다. 순방향 비공개성을 제공하는 SSE는 새 문서에 대한 검색 패턴을 숨기지만, 어떤 문서에 접근했는지도 숨기려면 ORAM이 필요합니다. SSE와 ORAM을 결합하면 가장 강력한 개인정보 보호를 제공할 수 있지만 성능 비용이 상당히 커집니다.

ORAM이 항상 필요한 것은 아닙니다. 결정은 위협 모델에 따라 달라집니다. 공격자가 접근 패턴을 관찰할 수 있습니까? 전체 디스크 암호화가 적용된 로컬 저장소에서 원격 공격자를 상대로 한다면 ORAM이 필요하지 않을 수 있습니다. 클라우드 제공자를 신뢰할 수 없는 클라우드 저장소에서는 ORAM이 적합합니다. 접근 패턴 유출이 실제 위협이고 데이터의 민감성이 비용을 정당화한다면, 일반적으로 대역폭이 20~50배 증가하는 오버헤드를 감수할 가치가 있습니다.

암호화된 데이터에서도 접근 패턴이 민감한 정보인 이유를 올바르게 설명한 것은 무엇입니까?

데이터의 내용을 암호화해도 접근 패턴은 숨겨지지 않으며, 접근 패턴은 빈도 분석과 시간 분석을 통해 민감한 정보를 드러낼 수 있습니다. 정직하지만 호기심 많은 모델의 클라우드 제공자는 클라이언트가 어떤 암호문 블록에 접근하는지 관찰합니다. CryptDB 공격은 암호화된 데이터베이스의 접근 패턴으로부터 실제적인 추론이 가능함을 보여 주었습니다. ORAM은 모든 접근이 서버에 동일하게 보이도록 만들어 이 문제를 해결합니다. 단순한 해결책(접근마다 모든 것을 읽기)은 O(n)이므로 실용적이지 않으며, 실제 ORAM은 O(log^2 n)의 오버헤드를 달성합니다.