Bijou64: 가변 길이 정수 인코딩에서 정규성 문제 해결

이진 프로토콜 세계에서 정수를 효율적으로 인코딩하는 일은 끊임없는 균형 잡기 작업입니다. 대부분의 개발자는 작은 숫자가 8바이트의 공간을 낭비하지 않도록 가변 길이 정수 인코딩(varint)을 사용합니다. 하지만 이러한 설계들에는 미묘하지만 위험한 결함이 존재합니다: 구조적 정규성의 부재.

단일 값이 여러 다른 바이트 시퀀스로 표현될 수 있을 때, 보안 취약점이 발생합니다—특히 서명된 프로토콜에서 그렇습니다. 시스템이 메시지의 바이트를 기반으로 서명을 검증하지만, 디코더가 서로 다른 바이트 시퀀스를 동일한 값으로 취급한다면, 공격자는 논리적 값을 바꾸지 않고도 메시지 바이트를 조작할 수 있어 보안 검사를 우회하거나 변조 가능성 문제를 일으킬 수 있습니다. 이것이 bijou64가 해결하도록 설계된 핵심 문제입니다.

LEB128의 결함

bijou64를 이해하려면 먼저 업계 표준인 LEB128을 살펴봐야 합니다. LEB128은 숫자를 7비트 구간으로 인코딩하며, 각 바이트의 최상위 비트를 “연속 비트”(continuation bit)로 사용해 추가 바이트가 뒤따른다는 신호를 보냅니다.

실용적이지만 LEB128은 구조적으로 정규성을 갖추고 있지 않습니다. 예를 들어 숫자 0은 0x00으로 인코딩될 수 있지만, 0x80 0x00이나 0x80 0x80 0x00으로도 인코딩될 수 있습니다. 대부분의 디코더는 이들 모두를 0으로 받아들입니다. 이러한 비정규성은 ASN.1, X.509 인증서, 비트코인 트랜잭션 등 중요한 시스템에서 실제 취약점을 초래했습니다.

전통적으로는 디코더에서 런타임 검사를 통해 “정규 형태”(canonical form)를 강제하는 것이 해결책이었습니다. 그러나 bijou64의 저자들이 지적하듯, 이러한 검사는 종종 누락되거나 최적화 과정에서 사라지거나 포팅 중에 잊혀져, 눈에 보이지 않는 보안 약화를 초래합니다.

Bijou64가 정규성을 달성하는 방법

Bijou64는 두 가지 주요 메커니즘인 첫 바이트 태깅(first-byte tagging)과 오프셋(offsets)을 사용해 정수당 여러 인코딩이 존재할 가능성을 없앱니다.

1. 첫 바이트의 이중 역할

bijou64에서 첫 바이트는 두 가지 역할을 합니다. 0에서 247 사이의 값에 대해서는 첫 바이트가 값 자체입니다. 248 이상 값에 대해서는 첫 바이트가 태그 역할을 하여 뒤따르는 바이트 수를 정확히 지정합니다.

이는 즉각적인 성능 향상을 제공합니다: 디코더는 $O(1)$ 시간에 필요한 정확한 메모리 할당량을 알 수 있지만, LEB128은 $O(n)$ 시간에 연속 비트를 스캔해야 합니다.

2. 오프셋 트릭

0과 같은 숫자가 단일 바이트(0x00)와 태그된 시퀀스(예: 0xF8 0x00) 모두로 표현되는 것을 방지하기 위해 bijou64는 오프셋을 사용합니다. 태그된 바이트가 0부터 시작하는 숫자를 나타내는 대신, 이전 단계의 범위와 겹치지 않도록 특정 값만큼 오프셋됩니다.

예를 들어, 태그가 2바이트 시퀀스를 나타낸다면 값은 248(0xF8)만큼 오프셋됩니다. 이는 가능한 가장 작은 2바이트 인코딩이 0이 아니라 248을 나타내도록 보장합니다. 이 패턴은 더 큰 정수에 대해서도 예측 가능하게 계속되어, 첫 바이트를 기반으로 한 오프셋 조회 테이블을 생성합니다.

성능 벤치마크

놀랍게도 보안을 위해 설계하면서도 상당한 성능 향상이 이루어졌습니다. ARM(Apple M2 Pro)과 x86(AMD Zen 5)에서의 벤치마크는 bijou64가 LEB128보다 훨씬 빠른 경우가 많음을 보여줍니다.

  • Decoding Speed: Bijou64는 LEB128보다 대략 2–10배 빠릅니다. 큰 u64 분포에서는 4096개의 값을 약 3 $μ$s에 처리할 수 있으며, LEB128은 약 30 $μ$s가 소요됩니다.
  • Consistency: bijou64는 연속 비트 스캔의 예측 불가능한 분기 패턴을 피하기 때문에 성능이 매우 일관됩니다(벤치마크에서 거의 수직에 가까운 CDF 곡선으로 나타남).
  • Encoding Speed: LEB128가 특정 “작은” 분포(248 – 65,535)에서는 약간 더 빠를 수 있지만, bijou64는 전반적으로 더 높은 성능을 보입니다.

이러한 이점은 연속적인 빅 엔디안 페이로드 사용에서 비롯됩니다. 이는 최신 CPU가 단일 로드와 bswap 명령만으로 처리할 수 있게 하며, LEB128의 7비트 레이아웃에서 필요한 마스킹 및 시프트보다 효율적입니다.

비판적 관점 및 트레이드오프

벤치마크가 인상적이지만, 커뮤니티에서는 몇 가지 중요한 반론을 제기했습니다:

SIMD 및 병렬화

한 기여자는 bijou64가 스칼라 연산에서는 빠르지만, SIMD(Single Instruction, Multiple Data) 명령을 사용할 때 LEB128이나 센티넬 기반 인코딩에 비해 어려움을 겪을 수 있다고 지적했습니다. 병렬화 기회는 선행 태그 바이트에 대한 엄격한 의존 없이 대량으로 처리할 수 있는 형식에 유리합니다.

공간 효율성

LEB128은 특정 범위에서 더 압축됩니다. 예를 들어 LEB128은 $2^{14}$ 이하 값에 대해 2바이트를 유지하지만, bijou64의 2바이트 범위는 훨씬 작아(최대 500)합니다. 모든 바이트가 중요한 프로토콜이며 값이 이 중간 범위에 자주 속한다면 LEB128이 더 적합할 수 있습니다.

“링킹” 사용 사례

DWARF나 WASM과 같은 일부 환경에서는 비정규 인코딩이 실제로 기능입니다. 컴파일러는 종종 최종 주소가 링킹될 때까지 알려지지 않은 심볼에 대한 자리표시자로 가장 넓은 varint(예: LEB128의 경우 5바이트)를 출력합니다. 인코딩이 엄격히 정규화되어 있다면, varint의 폭이 변경될 때마다 링커가 이후 모든 코드를 이동시켜야 하며, 이는 연쇄적인 재계산을 초래합니다.

결론

Bijou64는 철학의 전환을 의미합니다: 결함이 있는 형식에 검사를 추가하는 대신, 형식 자체를 변경해 결함이 발생하지 않도록 합니다. 서명, 콘텐츠 주소 지정, 혹은 구현 간 엄격한 합의가 필요한 새로운 프로토콜을 구축하는 개발자에게 bijou64는 구조적으로 더 안전하고 전반적으로 더 빠른 LEB128 대안을 제공합니다.

Sources