겉보기에는 정렬되지 않은 순서와 순열을 이용해 정보를 숨기는 방법, Lehmer 코드의 원리, 그리고 메타데이터·스타일시트·파일 포맷·현실 세계에 이르기까지의 응용 가능성을 살펴본다.
평범한 곳에 정보를 감춰 두는 일은 내가 꾸준히 끌리는 장난감 같은 문제인데, 대개는 키를 저장하는 터무니없는 방법을 придум어 내면서 그렇다. ext4 타임스탬프의 나노초를 다른 용도로 쓰기, 수정한 Bluetooth 마우스 펌웨어를 통한 방송, 가정용 기기 개조, 그리고 최근에는 Exif 메타데이터를 수정하는 방법까지 여러 접근을 시도해 봤다.
메타데이터나 이미지 노이즈를 추가하거나 수정하는 대신, 메타데이터의 순서를 바꿀 수도 있다. Exif 태그는 낮은 것부터 인코딩되지만, 리더는 이를 강제하지 않는다. Sony A7R 사진 하나에는 63개의 태그가 들어 있는데, 기존 내용을 단지 재배열하는 것만으로도 log2(63!)개의 순서 순열, 즉 289비트를 제공하며, 이는 AES-256 키보다 크다.
실제로는 Exif 재정렬이 그리 훌륭하지 않은데, 리더가 잘못 정렬된 태그에 대해 경고를 출력하고 태그도 그룹 제약을 받기 때문이다. 하지만 이를 구현하는 과정에서 Lehmer code를 알게 되었고, 순열을 인코딩하는 방법을 제공할 뿐 아니라 곳곳에 나타나는 겉보기에 무질서한 집합 속에 숨어 있는 “공짜 저장 공간”에도 적용할 수 있다는 점을 깨닫게 되었다.
Lehmer는 이해하기도 쉽고 구현하기도 쉽다. 유일한 원소들로 이루어진 시퀀스의 각 위치에 대해, 현재 항목보다 더 작은 뒤쪽 항목의 개수를 센다. _(A, B, C, D)_의 Lehmer 자릿수는 _(0, 0, 0, 0)_이고, _(D, C, A, B)_의 경우는 _(3, 2, 0, 0)_이다. 각 위치마다 가능한 최대 자릿수는 하나씩 줄어들고, 필요한 저장 공간도 함께 줄어든다.
여기서는 13개 항목 시퀀스에 적용하여 32비트 숫자를 인코딩하기에 충분한 자릿수를 얻는다:
Key: Sequence:
유일한 시퀀스를 복원할 수 있는 곳이라면 어디서든 Lehmer는 비트스트림을 추출할 수 있다. 그런 시퀀스는 이 페이지에도 있는데, 여기에는 개의 고유한 문장이 들어 있으며, 이는 Lehmer 자릿수로 환산하면 비트의 가치가 있다:
이런 시퀀스를 한 번 발견하고 나면 더는 눈에 띄지 않게 하기가 어렵다. 컴퓨팅에서는 논리적으로는 무순서인 대부분의 컬렉션이 직렬화 과정에서 어떤 순서를 가정한다. 다음은 CSS 스타일시트이다:
td, th { text-decoration: underline; color: green; }
p { font-weight: bold; }
a { color: red; }겹치지 않는 규칙에 대해서는 선택자 목록, 속성, 규칙의 순서가 평가 시 대부분 무시되지만, 파일 안의 순서는 존재하며 DOM을 통해 질의할 수 있다. Wikipedia의 스타일시트에는 규칙 1,003개, 선택자 1,950개, 속성 2,731개가 있다. 규칙의 순서만 바꿔도 1킬로바이트가 넘는 데이터를 심을 수 있고, 선택자와 속성의 순서까지 바꾸면 그보다 더 많이 넣을 수 있다.
1킬로바이트면 작고 무해해 보이는 디코더 뒤에 악성코드를 숨기기에 충분하다. 인터넷 웜을 CSS로 쓸 수 없다고 누가 말했는가? 다음은 이 페이지의 example CSS 블록에 인코딩된 무해한 데모다:
Lehmer 코딩은 파일 워터마킹에서 자연스러운 자리를 찾는 듯하다. 그 외에는 동일한 tarball과 ZIP 파일도 디렉터리 순서를 재배열하는 방식으로 워터마크를 담을 수 있고, 추출 과정에서 이를 놓치기 쉽다. 심지어 그 워터마크는 ext4 생성 타임스탬프의 순서를 좌우하는 식으로 대상 파일시스템에 지속적으로 전이될 수도 있다.
전이 가능성은 다른 방식으로도 존재한다. 절대 위치 지정된 요소들의 순서가 바뀐 HTML이나 SVG를 렌더링할 때, 인쇄 중 브라우저가 어떻게 동작할지 생각해 보라. 적어도 Linux의 Firefox에서 SVG의 경우, PDF 출력은 입력 순서를 따른다 (첫 번째, 두 번째).
프로그램 바이너리의 경우 -ffunction-sections와 GNU 링커 스크립트를 함께 사용해 바이너리 안의 함수 순서를 재배열할 수 있고, 혹은 오류 메시지 렌더링에 쓰이는 정적 문자열 테이블을 변형할 수도 있을 것이다.
랜덤한 순서로 JSON 속성이나 Protocol Buffer 필드를 생성하는 것처럼 보이는 백엔드 API를 다루는 상황을 상상해 보자. 처음에는 구현의 해시 테이블 때문이라고 생각할 수 있겠지만, 만약 그 순서가 사실은 데이터를 유출하고 있다면 어떨까? Protocol Buffers의 경우라면 물리적 표현을 직접 살펴보는 엔지니어는 거의 없을 것이다.
Javascript 인터프리터만 가진 스파이는 정보가 게시되는 새로운 mutable DHT key를 매일 도출해야 한다. 그의 핸들러는 정오의 BBC News 웹사이트에 올라온 기사 제목 목록에 Lehmar를 적용하라고 지시하는데, 현재 그 수는 76개(= 369 bits)이다. 내가 첩보 영화를 쓰지 않아서 세상은 다행이다.
재미있는 응용으로는 Lehmer를 현실 세계와 잇는 방법이 있을 것이다. Amazon에 올라온 이 무해해 보이는 머그잔 걸이를 보자:
이 머그잔들은 서로 구별되지 않는다는 점은 일단 무시하자. 비전 모델은 바운딩 박스를 식별할 수 있고, 각 박스의 평균 밝기나 색조에서 순서를 도출할 수 있다. 이런 걸이는 44비트를 제공하는데, 그 자체만으로는 좋은 비밀번호가 되기엔 약간 부족하다.
이건 만들어 보면 재미있는 모바일 앱이 될 것이다. 다음에 누군가의 집을 방문하게 되면, 고유한 머그잔으로 가득 찬 유난히 큰 걸이가 있는지 꼭 눈여겨보라.
David Wilson · dw@hmmz.org · Sun 5 Jul 20:31:09 2026
