Embedding information in disorder

Embedding information in disorder

Disguising information in plain view is a toy problem I'm regularly drawn to,<br>usually by inventing ridiculous methods to store a key. I've tried many<br>approaches, like repurposing the nanoseconds of ext4 timestamps, broadcasting<br>via modified Bluetooth mouse firmware, modifying a home appliance, and recently<br>by modifying Exif metadata.

Rather than adding or modifying metadata or image noise, metadata can be<br>reordered. Exif tags are encoded lowest-first, but readers do not enforce this.<br>One Sony A7R photo includes 63 tags, offering log2(63!) order<br>permutations, or 289 bits, larger than an AES-256 key, simply by rearranging<br>existing content.

In practice Exif reordering isn't great, as readers print warnings for<br>misordered tags, and tags are constrained by groupings, but implementing it<br>introduced me to Lehmer<br>code, which offers a way to encode permutations, and revealed its<br>applicability to "free storage" hiding in seemingly unordered collections<br>appearing everywhere.

Lehmer Code

Lehmer is straightforward to understand and easy to<br>implement. For each position in a unique sequence, count later items<br>smaller than the current item. The Lehmer digits for (A, B, C, D) are<br>(0, 0, 0, 0), while for (D, C, A, B) they are (3, 2, 0,<br>0), with the maximum digit decreasing by one at each position, alongside<br>its required storage.

Here it is on a 13-item sequence, yielding enough digits to encode a 32-bit<br>number:

Key:

Sequence:

Anywhere a unique sequence can be recovered, Lehmer can extract a bitstream.<br>Such a sequence occurs on this page, which contains<br>unique sentences, or bits worth of Lehmer digits:

Everywhere

It's difficult to avoid noticing these sequences after spotting one. In<br>computing, most collections which are logically unordered assume some order<br>during serialisation. Here is a CSS stylesheet:

td, th { text-decoration: underline; color: green; }<br>p { font-weight: bold; }<br>a { color: red; }

The order of the selector lists, properties, and rules is mostly ignored during<br>evaluation for non-overlapping rules, yet a file order exists and can be<br>queried via DOM. Wikipedia's<br>stylesheet has 1,003 rules with 1,950 selectors and 2,731 properties. It is<br>possible to embed over a kilobyte of data just by reordering the rules, and<br>even more by reordering selectors and properties too.

A kilobyte is enough to hide malware behind a tiny and innocuous decoder. Who<br>said an Internet worm couldn't be written in CSS? Here's a benign demo encoded<br>in this page's example CSS block:

rule.type === CSSRule.STYLE_RULE)<br>.map(rule => rule.selectorText)<br>">Click Me

Watermarking

Lehmer coding seems to have a natural home in file watermarking. Otherwise<br>identical tarballs and ZIP files might have their directories reordered in a<br>manner easy to miss during extraction, and the watermark may even durably<br>transfer to a target filesystem, such as by dictating the order of the ext4<br>birth timestamp.

Transferability is possible in other ways. Consider how a browser might behave<br>during printing when rendering HTML or an SVG where absolutely positioned<br>elements have been reordered. At least with Firefox on Linux for SVG, the PDF output follows the input order (first, second).

For program binaries, -ffunction-sections along with a GNU linker<br>script could reorder functions in a binary, or perhaps transform a table of<br>static strings used for rendering error messages.

Data From Nowhere

Imagine working with a backend API that appears to generate JSON properties or<br>Protocol Buffer fields in a random order. A first thought might attribute this<br>to a hash table in the implementation, but what if the ordering was instead<br>exfiltrating data? In the case of Protocol Buffers, few engineers would even<br>examine the physical representation.

Invisible Key Exchange

A spy armed with only a Javascript interpreter must derive a new mutable DHT key each<br>day to which intelligence is published. Their handler instructs them to use<br>Lehmar on the list of article titles appearing on the BBC News web site at<br>midday, of which there are currently 76 (= 369 bits). The world is glad I don't<br>write spy movies.

Physical Security

A fun application might be to bridge Lehmer to the real world. Take this<br>innocuous mug rack advertised on Amazon:

Ignoring the non-unique nature of these particular mugs, a vision model could<br>identify bounding boxes, and an order derived from the average lightness or hue<br>of each box. Such a rack would offer 44 bits, not quite enough for a good<br>password by itself.

This would make a fun mobile app to build. Next time you visit someone's home,<br>be sure to keep an eye out for any extra large racks filled with unique mugs.

David Wilson &middot; dw@hmmz.org &middot; Sun 5 Jul 20:31:09 2026