데이터 보안과 성능을 동시에 잡는 고속 정렬 알고리즘 djbsort
퀵 정렬(Quicksort)의 취약점: 데이터에 따라 실행 시간이 달라져 타이밍 공격(Timing Attack)에 취약함
djbsort의 핵심: 데이터에 의존하지 않는 고정된 연산 순서(Data-Oblivious)를 통해 보안을 강화함
SIMD 및 Branchless 최적화: SIMD(Single Instruction, Multiple Data)를 활용하여 속도를 높이고, 분기 없는(Branchless) 연산을 통해 보안을 강화함
GPU 프로그래밍 방식: 현대 CPU에서 GPU와 유사하게 SIMD를 활용하여 성능을 극대화함
타이밍 공격(Timing Attack) 방어를 위한 데이터 독립성
일반적으로 퀵 정렬(Quicksort)과 같은 데이터 의존적인 정렬 알고리즘은 입력 데이터에 따라 실행 시간이 달라져 타이밍 공격(Timing Attack)에 취약하다. djbsort는 이러한 문제를 해결하기 위해 데이터 미저장 정책(Zero-Retention Policy)을 적용하여, 입력 데이터와 관계없이 동일한 연산 순서를 보장한다. 즉, 정렬 과정에서 데이터의 값에 따라 분기하거나 메모리 접근 패턴이 변경되지 않도록 설계되었다.
SIMD(Single Instruction, Multiple Data)를 활용한 성능 최적화
djbsort는 SIMD 명령어를 사용하여 여러 개의 데이터를 동시에 처리함으로써 성능을 향상시킨다. 특히, SIMD 명령어(SIMD Instructions)를 활용하여 여러 개의 비교 및 교환 연산을 병렬로 처리한다. 이러한 SIMD 최적화는 현대 CPU의 병렬 처리 능력을 최대한 활용하여, 기존의 정렬 알고리즘보다 빠른 속도를 제공한다. 또한, SIMD를 통해 데이터 처리량(Throughput)을 극대화한다.
Branchless(분기 없는) 연산을 통한 보안 강화
djbsort는 분기(Branch)를 최소화하여 분기 예측(Branch Prediction)으로 인한 사이드 채널 공격(Side-Channel Attack) 위험을 줄인다. 대신, 산술 연산과 비트 연산을 사용하여 조건부 교환(Conditional Swap)을 구현한다. 이러한 Branchless 방식은 공격자가 실행 시간을 통해 데이터를 추론하는 것을 어렵게 만든다. 특히, djbsort는 하드웨어 min/max 명령어를 활용하여 분기 없이 비교 연산을 수행한다.
배처 정렬 네트워크(Batcher's Bitonic Sort) 기반 구현
djbsort는 배처 정렬 네트워크(Batcher's Bitonic Sort)를 기반으로 구현되었으며, 이는 데이터 독립적인 비교 연산을 수행하는 정렬 네트워크의 한 종류이다. 배처 정렬 네트워크는 O(n log²n)의 시간 복잡도를 가지며, 퀵 정렬(Quicksort)보다 약간 느리지만, 데이터 격리 아키텍처(Data Isolation Architecture)를 통해 보안을 강화한다. 또한, GPU에서 널리 사용되는 비토닉 정렬(Bitonic Sort)과 유사한 구조를 가지고 있어, 병렬 처리에 적합하다.
Zig 언어를 활용한 djbsort 구현
djbsort는 Zig 언어로 구현되었으며, Zig의 컴파일 타임(Compile Time) 기능을 활용하여 다양한 아키텍처에 대한 최적화를 수행한다. Zig는 메모리 안전성(Memory Safety)과 성능을 모두 제공하며, djbsort의 검증 가능한 코드(Verifiable Code)를 작성하는 데 기여한다. 또한, Zig의 floatSortKey 함수를 통해 부동 소수점(Float) 정렬을 정수 정렬과 동일한 속도로 처리한다.
