보안이 중요한 환경에서 정렬 알고리즘의 실행 시간이 데이터에 따라 달라지면 사이드 채널 공격에 취약해집니다. Branchless sorting이 해답입니다.
문제: 타이밍 사이드 채널
일반적인 정렬 알고리즘은 데이터 값에 따라 조건 분기(branch)가 발생합니다. 공격자는 실행 시간 차이를 측정하여 정렬되는 데이터의 패턴을 추론할 수 있습니다.
해결책: Sorting Networks
Sorting network는 고정된 비교-교환 패턴을 따릅니다. 입력 데이터와 상관없이 항상 같은 연산을 수행하므로 타이밍이 일정합니다.
Branchless 구현
// 조건 분기 없는 min/max
int min = y ^ ((x ^ y) & -(x < y));
int max = x ^ ((x ^ y) & -(x < y));
비트 연산으로 조건문 없이 최솟값/최댓값을 계산합니다. CPU의 분기 예측 실패도 방지됩니다.
사용 사례
- 암호화 키 비교
- 인증 토큰 검증
- 금융 데이터 처리
- SGX/TrustZone 같은 보안 영역
트레이드오프
일반 정렬보다 성능이 떨어질 수 있습니다. 하지만 보안이 최우선인 상황에서는 필수적인 선택입니다.
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Categories:
