0x0E 망각적 연산 (Oblivious Computing)
1. 망각적 연산 개요
1.1 메모리 계층의 위험성
메모리 계층구조의 보안 위험:
• 메모리 접근 패턴을 통한 정보 유출 가능
• 캐시 타이밍 공격의 취약점 제공
• 사이드 채널 공격의 근본적 원인
1.2 망각적 연산의 정의
기본 개념
Oblivious Computation (망각적 연산):
• 실행 코드에 관계없이 동일한 메모리 접근 패턴 생성
• 입력 데이터에 관계없이 동일한 메모리 접근 패턴 생성
• 정보 유출을 방지하기 위한 특별히 설계된 연산 방식
목적:
• 사이드 채널 공격 차단
• 프라이버시 보장 연산 제공
2. PC-Security (Program Counter Security)
2.1 PC-Security 정의
Program Counter Security:
• 제어 흐름 망각성(Control-flow Obliviousness)이라고도 함
• 실행 중 입력과 무관한 프로그램 카운터 진행 강제
• 분기 패턴을 통한 정보 유출 방지
핵심 원리:
• 모든 가능한 실행 경로가 동일한 메모리 접근 패턴을 가져야 함
• 조건부 분기가 입력 데이터를 노출하지 않도록 설계
2.2 Predicated Execution
조건부 실행 (Predicated Execution):
• 분기 대신 조건부 실행 사용
• 모든 경로를 실행하되 결과만 선택적으로 적용
• 실행 시간과 메모리 접근 패턴을 일정하게 유지
예시:
기존 방식:
if (condition) {
result = func_a();
} else {
result = func_b();
}
망각적 방식:
result_a = func_a();
result_b = func_b();
result = condition ? result_a : result_b;
3. 상수 시간 연산 (Constant Time Computation)
3.1 상수 시간 연산 정의
Constant Time Computation:
• 모든 입력에 대해 동일한 계산 시간을 갖는 알고리즘
• 실행 시간을 통한 정보 유출 방지
• 타이밍 사이드 채널 공격 차단
조건:
• 입력 크기에 관계없이 일정한 실행 시간
• 분기 예측 실패를 통한 정보 유출 방지
• 캐시 접근 패턴 균일화
3.2 해시 함수 사례
비상수 시간 해시 함수의 문제점:
Hash("Hello World") → 25ms
Hash("SWE3009 is the most interesting course...") → 60ms
문제점:
• 실행 시간 차이로 입력 길이 추정 가능
• 타이밍 공격을 통한 정보 유출
• 프라이버시 침해 가능성
해결방법:
• 모든 입력에 대해 동일한 실행 시간 보장
• 패딩을 통한 입력 크기 균일화
• 더미 연산을 통한 시간 정규화
4. 데이터 접근 망각성 (Data Access Obliviousness)
4.1 데이터 접근 망각성 정의
Data Access Pattern Obliviousness:
• 입력에 관계없이 항상 동일한 데이터 접근 패턴 보장
• 메모리 접근 순서와 위치를 균일화
• 캐시 사이드 채널 공격 방지
구현 방법:
• 모든 가능한 메모리 위치에 접근
• 접근 순서를 입력과 무관하게 고정
• 더미 접근을 통한 패턴 마스킹
4.2 Signal Messenger 사례 연구
Signal Messenger의 연락처 검색:
• 사용자가 특정 연락처를 검색할 때
• 검색 패턴이 연락처 정보를 유출할 수 있음
• 망각적 검색을 통해 프라이버시 보호
망각적 구현:
┌─────────────────────────────────┐
│ 연락처 데이터베이스 │
├─────────────────────────────────┤
│ Alice → 항상 접근 │
│ Bob → 항상 접근 │
│ Charlie → 항상 접근 │
│ David → 항상 접근 │
└─────────────────────────────────┘
• 실제 검색 대상과 관계없이 모든 연락처에 접근
• 검색 결과만 선별적으로 반환
• 접근 패턴을 통한 정보 유출 방지
💡 추가 정보: Signal은 개인정보 보호에 특화된 메신저로, 망각적 연산을 통해 메타데이터 수집을 최소화하고 사용자의 연락처 검색 패턴을 보호합니다.
5. 망각적 RAM (Oblivious RAM)
5.1 ORAM 개념
Oblivious RAM (ORAM):
• 이진 트리 기반 알고리즘
• 사용 시 균일한 메모리 접근 패턴 생성
• 기존 시스템을 망각적 연산으로 개조하는 빌딩 블록
주요 알고리즘:
• Path ORAM: 경로 기반 ORAM
• Circuit ORAM: 회로 기반 ORAM
• 가장 잘 알려진 ORAM 알고리즘들
5.2 ORAM 동작 원리
ORAM 메모리 구조:
Root
/ \
/ \
Node1 Node2
/ \ / \
L1 L2 L3 L4
접근 패턴:
• 실제 데이터 위치와 관계없이 항상 Root에서 Leaf까지 전체 경로 접근
• 더미 블록과 실제 블록을 섞어서 접근
• 재배치를 통해 접근 패턴 마스킹
예시:
데이터 A 읽기: Root → Node1 → L1 (전체 경로)
데이터 C 읽기: Root → Node2 → L3 (전체 경로)
→ 동일한 접근 패턴 유지
5.3 Obelix 시스템
Obelix (SP '24):
• ORAM을 적용한 난독화 엔진
• 코드/데이터 저장소의 백엔드로 ORAM 메모리 사용
• 각 ORAM 블록은 64바이트 (캐시 라인 크기)
• 캐시 사이드 채널 공격 완전 차단
특징:
• 하드웨어 캐시 라인과 정확히 일치하는 블록 크기
• 캐시 충돌을 통한 정보 유출 방지
• 완전한 메모리 접근 패턴 은닉
6. 강의 마무리
6.1 수업 정리
인터넷서비스와정보보호 과목 내용:
• 현대 정보보안 문제와 해결책의 기초 습득
• 현대 시스템에서 보안 문제가 나타나는 방식의 실습 경험
• 정보시스템의 보안 문제를 식별하고 해결할 수 있는 능력 배양
목표 달성:
• 시스템 아키텍처 이해
• 프로그래머로서의 보안 인식
• 엔지니어로서의 문제 해결 능력
6.2 CTF 도움 세션
CTF (Capture The Flag) 도움 세션:
• 일시: 6월 12일 16:30-17:45
• 장소: 27310B
• 실습을 통한 보안 기술 습득 기회
💡 추가 정보: CTF는 정보보안 분야의 실무 능력을 기르는 가장 효과적인 방법 중 하나로, 이론으로 배운 내용을 실제 공격과 방어 시나리오에서 적용해볼 수 있습니다.
예상 시험문제
1. 망각적 연산의 개념과 목적에 대해 설명하시오.
답안: 망각적 연산(Oblivious Computation)은 실행 코드나 입력 데이터에 관계없이 항상 동일한 메모리 접근 패턴을 생성하도록 특별히 설계된 연산 방식이다.
주요 목적:
- 사이드 채널 공격 차단: 메모리 접근 패턴을 통한 정보 유출 방지
- 프라이버시 보장: 연산 과정에서 입력 데이터나 중간 결과 노출 방지
- 타이밍 공격 방지: 실행 시간을 통한 정보 추론 차단
해설: 망각적 연산은 현대 보안에서 중요한 개념으로, 특히 클라우드 컴퓨팅이나 암호화 시스템에서 메타데이터 보호를 위해 필수적이다.
2. PC-Security와 Predicated Execution의 관계를 설명하시오.
답안: PC-Security(Program Counter Security)는 입력과 무관한 프로그램 카운터 진행을 강제하는 보안 기법이며, Predicated Execution은 이를 구현하는 주요 방법이다.
PC-Security의 원리:
- 제어 흐름 망각성(Control-flow Obliviousness) 보장
- 분기 패턴을 통한 정보 유출 방지
- 모든 실행 경로가 동일한 메모리 접근 패턴 유지
Predicated Execution 구현:
// 기존 방식 (취약)
if (secret_bit) {
result = expensive_operation();
}
// 망각적 방식 (안전)
temp = expensive_operation();
result = secret_bit ? temp : 0;
해설: 조건부 분기 대신 모든 경로를 실행하고 결과만 선택적으로 사용함으로써 실행 패턴을 균일화한다.
3. 상수 시간 연산이 필요한 이유와 구현 방법을 예시와 함께 설명하시오.
답안: 상수 시간 연산은 모든 입력에 대해 동일한 실행 시간을 보장하여 타이밍 사이드 채널 공격을 방지하는 기법이다.
필요성:
- 실행 시간 차이를 통한 정보 유출 방지
- 입력 크기나 값에 대한 추론 차단
- 암호화 시스템의 키 정보 보호
문제 예시:
// 취약한 해시 함수
Hash("Hello") → 25ms
Hash("Very long input string") → 60ms
// 실행 시간으로 입력 길이 추정 가능
해결 방법:
// 상수 시간 구현
int constant_time_compare(char* a, char* b, int len) {
int result = 0;
for (int i = 0; i < len; i++) { // 항상 전체 길이 처리
result |= a[i] ^ b[i];
}
return result == 0;
}
해설: 패딩, 더미 연산, 고정 반복문 등을 통해 입력과 무관한 일정한 실행 시간을 보장한다.
4. ORAM(Oblivious RAM)의 동작 원리와 보안 효과를 설명하시오.
답안: ORAM은 실제 메모리 접근 패턴을 숨기기 위해 이진 트리 구조를 사용하여 균일한 접근 패턴을 생성하는 기법이다.
동작 원리:
Root
/ \
Node1 Node2
/ \ / \
L1 L2 L3 L4
접근 방식:
- 실제 데이터 위치와 관계없이 항상 Root→Leaf 전체 경로 접근
- 더미 블록과 실제 블록을 섞어서 접근
- 주기적 재배치를 통한 접근 패턴 마스킹
보안 효과:
- 메모리 접근 패턴 완전 은닉
- 캐시 사이드 채널 공격 차단
- 데이터 위치 정보 유출 방지
실제 적용:
- Obelix 시스템: 64바이트 블록으로 캐시 라인과 정확히 매칭
- 클라우드 컴퓨팅에서 데이터 접근 패턴 보호
해설: ORAM은 성능 오버헤드가 크지만 완전한 메모리 접근 은닉을 제공하는 강력한 프라이버시 보호 기법이다.
5. Signal Messenger의 망각적 연락처 검색 구현을 설명하고, 이것이 필요한 이유를 논하시오.
답안: Signal Messenger는 사용자의 연락처 검색 패턴을 보호하기 위해 망각적 검색을 구현한다.
구현 방법:
연락처 데이터베이스:
┌─────────────────┐
│ Alice ← 항상 접근│
│ Bob ← 항상 접근│
│ Charlie← 항상 접근│
│ David ← 항상 접근│
└─────────────────┘
• 실제 검색 대상과 관계없이 모든 연락처 데이터 접근
• 검색 결과만 클라이언트에서 필터링
• 서버는 실제 검색 대상을 알 수 없음
필요성:
- 연락처 관계 정보 보호: 누구와 소통하는지 서버가 알지 못함
- 메타데이터 수집 방지: 통신 패턴 분석을 통한 개인정보 유추 차단
- 검열 회피: 특정 인물과의 연락 사실 숨김
프라이버시 효과:
- 정부나 서비스 제공자로부터 연락처 관계 보호
- 사회적 그래프 분석 방지
- 정치적 탄압이나 감시로부터 사용자 보호
해설: 단순한 암호화를 넘어서 메타데이터까지 보호하는 진정한 프라이버시 보장 메신저의 핵심 기술이다.
6. 망각적 연산의 한계점과 실용적 고려사항을 논하시오.
답안: 망각적 연산은 강력한 프라이버시 보호를 제공하지만 여러 한계점과 실용적 고려사항이 존재한다.
주요 한계점:
-
성능 오버헤드
- ORAM: 100-1000배 성능 저하
- 상수 시간 연산: 최악 케이스에 맞춘 실행 시간
- 메모리 사용량 증가
-
구현 복잡성
- 모든 코드 경로의 균일화 필요
- 컴파일러 최적화와 충돌 가능
- 하드웨어 레벨 고려사항
-
완전성 보장의 어려움
- 전력 소비 패턴
- 전자기 방사 (TEMPEST)
- 음향 사이드 채널
실용적 고려사항:
보안 vs 성능 트레이드오프:
├── 고보안 요구사항
│ ├── 암호화 키 처리
│ ├── 의료/금융 데이터
│ └── 정치적 민감 정보
├── 중간 수준
│ ├── 개인 메시징
│ └── 클라우드 저장소
└── 낮은 보안 요구사항
├── 공개 데이터 처리
└── 성능 중심 애플리케이션
적용 전략:
- 하이브리드 접근: 중요한 부분만 망각적 처리
- 하드웨어 가속: 전용 ORAM 하드웨어
- 점진적 적용: 단계별 보안 강화
해설: 망각적 연산은 완벽한 해결책이 아니라 특정 위협 모델에 대한 강력한 방어 수단으로, 보안 요구사항과 성능 제약을 균형있게 고려해야 한다.