构建第一个 JPEG XL MD5 哈希quine

原文

Constructing The Words First JPEG XL MD5 Hash Quine writeup

You may have heard the term Quine before… It means a program which prints its own source. For example in python:

$ cat quine.py
s='s=%r;print(s%%s)';print(s%s)
$ python3 quine.py
s='s=%r;print(s%%s)';print(s%s)

$ md5sum shark_hashquine.jxl
c0dec0007b5246f7428936d9bed2f446  shark_hashquine.jxl

download the .jxl file
The image above is a PNG render which does not have the same MD5 properties

Download JPEG XL Hashquine

What In The Hash!

You have likely computed a hash before. It is a seemingly mundane string of numbers which is the result of passing the entire file through a one-way function. In a real way, this calculation can represent the soul of the file in as much as the source itself does.

$ md5sum ./my-cool-file.pdf
6cef0cf6194efa36cb5be483ce87bd3b   my-cool-file.pdf

Now the fun thing about a hash is you can do it to any file, anything at all! So by making a Quine print its own hash we open up the Quine Cinematic Universe (QCU) to all other file formats.

By doing so we also learn new mediums with entirely different computational paradigms. After all, what is an image other than a program which runs inside of a graphic codec runtime…

So, to learn more, let’s create an image which can display its own MD5 Hash!

Finding a fixed point where the file displays its own hash sounds impossible! You can imagine that every time you change the file to display one hash, the hash of the file changes again!

Content To Hash

<div readability="7">
<p>
Computed MD5 Hash:
</p>
<p>
d41d8cd98f00b204e9800998ecf8427e
</p>
</div>

<button id="generateBtn" onclick="calculateMd5()">
Calculate MD5
</button>
<button onclick="recurseHash()">
RECURSE
</button>
</div>
</div>
</div>
<p>However, this is not a new field, and I am not the first to have
attempted this… In fact there have been many other impressive Hash
Quines across a variety of file formats</p>

<p>You can find a big list of them here: <a href="https://github.com/corkami/collisions/tree/master/hashquines">github.com/corkami/collisions</a></p>
<p>The proof lies in these very files, you can download them and hash
them for yourself to verify! It clearly is possible to produce such
artifacts. In fact this last PNG one, (which was a beautiful piece of
work, please read the <a href="https://x.com/David3141593/status/1573218394358386688">detailed
writeup here</a>), is exactly what we are looking for.. but that is not
reason to be satisfied or give up on creating our own!</p>
<figure>
<img src="./hashquine_by_retr0id.png" alt="PNG Hash Quine By retr0id"/>
<figcaption aria-hidden="true">PNG Hash Quine By retr0id</figcaption>
</figure>
<p>So why attempt to create a new one? Well every file format is unique
and different, bringing new challenges to overcome and new avenues of
attack to try out. There are plenty of image formats left to tackle
beyond PNG!</p>
<p>To make it even more interesting and novel, we can also add some
additional constraints..</p>
<ol type="1">
<li><strong>No animated frames</strong> - The final result should be a
single rendered image without relying on enabling or disabling image
frames.</li>
<li><strong>No dead bytes</strong> - Many hash quines abuse lax parsers
which happily skip over regions of data (comments, empty blocks, etc).
We will ensure that every byte of our data is relevant to the rendering
of the final image</li>
<li><strong>No length field hacks</strong> - Another common attack is to
rely on corrupting a length field of a chunk or structure in the file,
ideally to cause the parser to change how it interprets the file data.
We will also avoid this in our construction.</li>
</ol>
<p>The length field hack is actually how the only <a href="https://shattered.io/">public SHA-1 collision</a> files work. Two
PDFs which have different length fields, causing different objects to
render. (This attack cost an estimated ~$2.7M to pull off btw)</p>
<p><img src="./shattered.png"/></p>
<p>With these constraints in mind, we can get started. But where to
start? Even when we have proof in hand that this task is feasible, it
still seems intractable to produce a file which displays its own MD5
hash!</p>

<p>Well from a pure mathematical stance it is technically possible… as
the space of possible hashes (128 bits for MD5) is much smaller than the
space of all possible images displaying hashes. You would expect that
with enough time you would be able to brute force and locate such a
file…</p>
<p>However, even if you hashed with the speed of the entire bitcoin
network (currently 1.2 zettahashes per second), it would be expected to
take <strong>4.5 billion years</strong>!</p>
<p>We want to get this done in a weekend! Rather than brute force 128
bits, MD5 hash quines generally abuse cryptographic weaknesses of the
MD5 hash itself. In particular we will make use of the
<strong>“Identical-Prefix Collision”</strong> attack.</p>
<h2 id="md5-collisions">MD5 Collisions</h2>
<p>If you are familiar with hashing, you should know that at this point
in time, MD5 is considered a <strong>broken hash</strong>. This is
particularly true when we consider its <strong>collision
resistance</strong>.</p>
<p>The collision resistance of a hash is determined by how difficult it
is to find any two inputs which result in the same hash output. You
should expect that a cryptographically secure hash function makes it
computationally infeasible to find two such inputs.</p>
<p>However as computing power and understanding of hash functions
increases, functions which were previously thought to be resistant have
fallen to this attack. This is what will make our task possible to do in
a <strong>reasonable amount of time</strong>.</p>
<p>To do this we will be using a <a href="https://github.com/brimstone/fastcoll">tool called fastcoll</a>,
created by Marc Stevens.</p>
<p>You can even do it in a few seconds right here in your browser! Just
push the <strong>“Generate MD5 Collision”</strong> button below:</p>
<div class="md5_container" readability="7">

<div>

<button id="generateBtn" onclick="generateCollision()">
Generate MD5 Collision
</button>
<button onclick="clearResults()">
Clear Results
</button>
</div>
<div id="results" readability="9">
<p>
Message 1 (hex):
</p>

<p>
Message 2 (hex):
</p>

<p>
MD5 Hash (both messages):
</p>

<p>
<button onclick="downloadMessages()">
Download Messages
</button>
<button onclick="verifyCollision()">
Verify Collision
</button>
</p>
</div>

</div>

<p>Beyond just creating two inputs with the same hash, the technique
used here can be done in an <strong>Identical Prefix</strong> attack. <a href="https://marc-stevens.nl/research/papers/eprint-2006-104-S.pdf">You
can read more about the attack here</a>.</p>
<p>In this setup we can provide any starting input data, which we can
then extend with 128 byte colliding data blocks.</p>
<p>What’s more, due to the nature the MD5 hash function, it is <a href="https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction">merkle–damgård</a>,
once we have a collision after some point in the message, we can append
the same suffix to both and preserve the collision. Here is an example
with both a prefix and a suffix (bitflips highlighted in red):</p>
<figure>
<img src="./blog_col2.png" alt="A 128 Byte Colliding MD5 Block With A Selected Prefix And Suffix"/>
<figcaption aria-hidden="true">A 128 Byte Colliding MD5 Block With A
Selected Prefix And Suffix</figcaption>
</figure>
<p>With this setup we can produce two files with identical hashes, which
differ by a few bits somewhere in the middle!</p>
<p>This is the core capability used in MD5 hash quines to produce
different effects from two files with the same hash…</p>
<p>Unfortunately producing colliding MD5 blocks is the easy part… we
still have to be very clever about how we use these bitflips to
conditionally render an entire 32 character string! Doing this depends
heavily on the structure of the file format in question…</p>
<p>So knowing the core technique of this challenge, we now must choose
an image format to take on!</p>

<p>For this task I decided to choose the <a href="https://jpegxl.info/">JPEG XL file format</a>. It is a very modern
image format with many features.</p>
<p>It does have a slightly spotty history of implementation, but that
seems to slowly be changing! As of right now it is supported in:</p>

<p>It also is now being included in the PDF standard, which may force
adoption. As of a few days ago Chromium has signaled that they are <a href="https://groups.google.com/a/chromium.org/g/blink-dev/c/WjCKcBw219k/m/NmOyvMCCBAAJ">interested
again in including an implementation</a>, likely one written in
rust.</p>
<p>Personally, I have explored the JPEG XL spec before.</p>
<p>I have even created a Capture-The-Flag challenge which involves
techniques very similar to some used here</p>
<p><a href="https://github.com/Nautilus-Institute/quals-2025/tree/main/jxl4fun" target="_blank">https://github.com/Nautilus-Institute/quals-2025/tree/main/jxl4fun</a></p>
<p>If you want more to read after this, check out the writeup on that
challenge!</p>
<p><a href="https://blog.cykor.kr/2025/04/DEFCON-33-Series-jxl4fun-pwn" target="_blank">https://blog.cykor.kr/2025/04/DEFCON-33-Series-jxl4fun-pwn</a></p>
<figure>
<img src="./exp_screenshot.png" alt="Final jxl4fun Capture-The-Flag Challenge Exploit Rendered"/>
<figcaption aria-hidden="true">Final jxl4fun Capture-The-Flag Challenge
Exploit Rendered</figcaption>
</figure>
<h2 id="modular-mode">Modular Mode</h2>
<p>In particular, my favorite feature of the JPEG XL format is the
lossless modular mode. In modular mode, each pixel in the image is
rendered through the use of two components: a “Prediction Tree”, and a
residual error stream.</p>
<p>You can think of the Prediction Tree as a small virtual machine with
a few opcodes, which is executed on every pixel in the image. It can
perform many branching conditional comparison operations, where values
such as X and Y coords, adjacent pixels, and previous color channels.
Then based on which branches are taken, a final opcode will output an
integer color value for the input pixel.</p>
<p>This Prediction Tree alone is very powerful and can produce
approximations of images with very few bytes. It is even used as a form
of algorithmic art crossed with code golfing.</p>
<p>However to achieve full lossless encoding of detailed images, the
predictions are only that, predictions of what pixels should be. To
recover the full original pixel values, an error delta / residual value
must be applied to the computed prediction value. These residual values
are stored in the image in a compressed format.</p>
<div class="sourceCode" id="cb4" readability="11"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb4-1"><a href="#cb4-1" aria-hidden="true" tabindex="-1"/>pixel(x,y) <span class="op">=</span> PredictionTree(x,y,...) <span class="op">+</span> Residual[x,y]</span></code></pre></div>
<p>here is an example of what a simple prediction tree can render</p>
<div readability="313.47062871442">
<div class="col" readability="9">
<pre><code>Height 512
Width 512
Bitdepth 8
DeltaPalette

if x > 0
  if y > 100
    - W -80
    - Set 255
  if N > 150
    - Gradient -50
    - Set 0

if y > 100
  if W > 100
    - N +40
    - Set 200
  - W -30

if |W-NW| > 40
  if x > 150
    - Set 0
    - N +70
- Set 150</code></pre>
</div>
<div class="col-art">
<p><img src="./art.png" width="400/"/></p>
</div>
<p>The prediction tree can also perform computation which resembles the
capabilities of a Turing machine:</p>
<figure>
<img src="./art3.png" class="crisp"/>
<figcaption aria-hidden="true">
More Complex Prediction Tree Computations
</figcaption>
</figure>
<details readability="5">
<summary>
View Full Prediction Tree
</summary>
<pre><code>Width   1024
Height  1024
Bitdepth 8

if c > 1

if y > 0
  if N > 250
    if W > 250
      - Set 0
    - Set 255
    if W > 250
      - Set 255
    if W > 60
     - W - 40
    if W > 10
     - W + 1
    - Set 50
 - Set 255

if c > 0

if y > 96
  if N > 250
    if W > 250
      - Set 0
    - Set 255
    if W > 250
      - Set 255
    if W > 20
     - W - 40
    if W > 10
     - W + 2
    - Set 100
 if y > 95
  - Set 255
    if W > 20
     - W - 40
    if W > 10
     - W + 2
    - Set 100

if y > 192
  if x > 97
  if N > 250
    if W > 250
    - Set 0
    - Set 255
    if W > 250
      - Set 255
    if W > 140
     - W - 60
    if W > 20
     - W + 2
    - Set 200
   if x > 95
  - Set 255
     if W > 140
     - W - 60
    if W > 20
     - W + 2
    - Set 200
 if y > 191
  - Set 255
     if W > 140
     - W - 60
    if W > 20
     - W + 2
    - Set 200</code></pre>
</details>
<p>We will make heavy use of this computational power!</p>

<p>Now the inkling of a plan forms! We have two pieces to the puzzle
through an image decoding mode which allows:</p>
<ol type="1">
<li><strong>Control pixel values from contents of the file, meaning MD5
collision bitflips would directly change pixel values</strong></li>
<li><strong>A conditional decoder which can be “programmed” to react to
these changed pixel values</strong></li>
</ol>
<p>If this works out, we should be able to chain the bitflips across
pixels into rendering hex digits elsewhere in the image!</p>

<p>The first major challenge we face is embedding the MD5 collision
blocks into the residual data stream.</p>
<p>The main obstacle in our way is compression! JPEG XL is well known
for its small file sizes and it partly achieves this through multiple
layers of compression. Here is what matters for the residual stream:</p>
<ul readability="0.5">
<li readability="0"><p>The residual stream is made of “tokens”, where each token can be
decoded to an integer value.</p></li>
<li readability="-1"><p>ANS Entropy encoding or Huffman Encoding</p></li>
<li readability="-1"><p>LZ77 compression over final bit streams</p></li>
</ul>
<p>This can prove an issue because the MD5 Collision chunks are full of
random bytes. If we were to try to naively swap out a chunk of a
compressed JPEG XL file with these random bytes, it will fail to decode
with an error!</p>
<p>Trying to find chunks which happen to decode correctly would greatly
increase the difficulty of this task… so how about we bypass all these
compression steps instead!</p>
<p>Luckily, at least for LZ77, we can simply choose to not enable it
while encoding our original image. However the entropy encoding step is
much more integral to the way the file format functions. There did not
appear to be an easy on/off switch for that.</p>
<h2 id="forging-an-ideal-huffman-tree">Forging An Ideal Huffman
Tree</h2>
<p>We won’t let this stop us! We just need a better understanding of how
it works.</p>
<p>To perform <a href="https://en.wikipedia.org/wiki/Huffman_coding">Huffman Coding</a>,
first statistics are collected on all the tokens (pixel values, etc) in
the data stream. A histogram is built to learn the distribution of the
tokens. This histogram is then used to give preferential treatment to
tokens which appear more often. A binary tree is built where each leaf
is a token. The path from the root to a given token represents the
encoded bit pattern.</p>
<figure>
<img src="./blog_huffman.png" alt="Huffman Code Tree"/>
<figcaption aria-hidden="true">Huffman Code Tree</figcaption>
</figure>
<p>This setup allows frequent tokens to be represented by a very small
number of bits, while uncommon tokens can be much longer (even > 8
bits). You can see an example of the bit patterns for a simple image
below. Notice how 0 is encoded with a single bit:</p>
<pre><code>[DEBUG] Huffman codewords:
[DEBUG]   symbol   0: depth= 1 bits=0x0000 (0)
[DEBUG]   symbol   2: depth= 5 bits=0x0007 (00111)
[DEBUG]   symbol   3: depth= 5 bits=0x0017 (10111)
[DEBUG]   symbol   7: depth= 5 bits=0x000f (01111)
[DEBUG]   symbol  15: depth= 5 bits=0x001f (11111)
[DEBUG]   symbol  32: depth= 3 bits=0x0003 (011)
[DEBUG]   symbol  46: depth= 2 bits=0x0001 (01)</code></pre>
<p>This presents an issue for our need to decode random bytes ->
tokens. Random bytes will contain a random number of tokens (as tokens
have variable length). This causes the decoder to miscount and fail to
decode the image with an error.</p>
<p>Ideally, to make this work, we would need to have it so that each
random byte maps to some token. This way no matter what random bytes we
use, each byte will successfully decode into a valid token and some
value for the pixel.</p>
<figure>
<img src="./huffman.png" alt="Comparing Huffman Encoding Lengths"/>
<figcaption aria-hidden="true">Comparing Huffman Encoding
Lengths</figcaption>
</figure>
<p>To construct this ideal histogram during encoding, we will modify the
libjxl library encoder itself. We change the code to override the normal
Huffman histogram calculations and make it think we have an even
distribution of every possible 256 byte values.</p>
<p>We choose a histogram over 256 symbols so that the huffman builder
emits a full 8-bit code with one symbol per codeword, effectively making
the residual stream a raw byte stream from the decoder’s
perspective.</p>
<div class="sourceCode" id="cb8" readability="11"><pre class="sourceCode patch"><code class="sourceCode diff"><span id="cb8-1"><a href="#cb8-1" aria-hidden="true" tabindex="-1"/><span class="va">+    // When set, ignore actual frequencies and force all symbols to have count=1</span></span>
<span id="cb8-2"><a href="#cb8-2" aria-hidden="true" tabindex="-1"/><span class="va">+    if (force_full_alphabet) {</span></span>
<span id="cb8-3"><a href="#cb8-3" aria-hidden="true" tabindex="-1"/><span class="va">+      fprintf(stderr, "[DEBUG] Forcing all 256 symbols to frequency=1 (ignoring actual token frequencies)\n");</span></span>
<span id="cb8-4"><a href="#cb8-4" aria-hidden="true" tabindex="-1"/><span class="va">+      for (size_t i = 0; i < size; i++) {</span></span>
<span id="cb8-5"><a href="#cb8-5" aria-hidden="true" tabindex="-1"/><span class="va">+        histo[i] = 1;</span></span>
<span id="cb8-6"><a href="#cb8-6" aria-hidden="true" tabindex="-1"/><span class="va">+      }</span></span>
<span id="cb8-7"><a href="#cb8-7" aria-hidden="true" tabindex="-1"/><span class="va">+    }</span></span></code></pre></div>
<p>Even with this change, the resulting .jxl file is still spec
compliant and can be decoded by the standard JPEG XL decoder.</p>
<p>After applying this change (and configuring a few things such as
disable LZ77 mode) we get the following codes:</p>
<pre><code>[DEBUG] Forcing all 256 symbols to frequency=1 (ignoring actual token frequencies)
[DEBUG] force_full_alphabet mode: size=256
[DEBUG] Huffman codewords:
[DEBUG]   symbol   0: depth= 8 bits=0x0000 (00000000)
[DEBUG]   symbol   1: depth= 8 bits=0x0080 (10000000)
[DEBUG]   symbol   2: depth= 8 bits=0x0040 (01000000)
[DEBUG]   symbol   3: depth= 8 bits=0x00c0 (11000000)
[DEBUG]   symbol   4: depth= 8 bits=0x0020 (00100000)
[DEBUG]   symbol   5: depth= 8 bits=0x00a0 (10100000)
[DEBUG]   symbol   6: depth= 8 bits=0x0060 (01100000)
[DEBUG]   symbol   7: depth= 8 bits=0x00e0 (11100000)
[DEBUG]   symbol   8: depth= 8 bits=0x0010 (00010000)
[DEBUG]   symbol   9: depth= 8 bits=0x0090 (10010000)
[DEBUG]   symbol  10: depth= 8 bits=0x0050 (01010000)
[DEBUG]   symbol  11: depth= 8 bits=0x00d0 (11010000)
[DEBUG]   symbol  12: depth= 8 bits=0x0030 (00110000)
[DEBUG]   symbol  13: depth= 8 bits=0x00b0 (10110000)
[DEBUG]   symbol  14: depth= 8 bits=0x0070 (01110000)
[DEBUG]   symbol  15: depth= 8 bits=0x00f0 (11110000)
[DEBUG]   ... (240 more symbols)</code></pre>
<p>The end result is that every 8 bit pattern maps to a valid token. We
can now swap in chunks of random bytes in the file and the image still
successfully decodes!</p>

<p>Next let’s verify that we can place the MD5 collision blocks into the
image file. We can start with an image containing all 0 pixels, then
replace parts of the image file on disk.</p>
<p>As a test, here we have found many MD5 Collision Blocks and inserted
them into the black image file. We end up with two files with a few
flipped bits between them. We can see that the MD5s match, while their
SHA1s do not.</p>
<div class="sourceCode" id="cb10" readability="9"><pre class="sourceCode bash"><code class="sourceCode bash"><span id="cb10-1"><a href="#cb10-1" aria-hidden="true" tabindex="-1"/><span class="ex">$</span> md5sum collide_<span class="pp">*</span>.jxl</span>
<span id="cb10-2"><a href="#cb10-2" aria-hidden="true" tabindex="-1"/><span class="ex">711006dc2d914cf2ce1a0c914be263d0</span>  collide_a.jxl</span>
<span id="cb10-3"><a href="#cb10-3" aria-hidden="true" tabindex="-1"/><span class="ex">711006dc2d914cf2ce1a0c914be263d0</span>  collide_b.jxl</span>
<span id="cb10-4"><a href="#cb10-4" aria-hidden="true" tabindex="-1"/><span class="ex">$</span> sha1sum collide_<span class="pp">*</span>.jxl</span>
<span id="cb10-5"><a href="#cb10-5" aria-hidden="true" tabindex="-1"/><span class="ex">7fa4db84031ef4558bfa85447b8fa96cf80e203d</span>  collide_a.jxl</span>
<span id="cb10-6"><a href="#cb10-6" aria-hidden="true" tabindex="-1"/><span class="ex">e05383faf062e6f749a0dbc78de8065b64c45d59</span>  collide_b.jxl</span></code></pre></div>
<p>Can you see the changed pixels?</p>
<figure>
<img src="./collide_a.png" class="crisp" width="256/"/>
<img src="./collide_b.png" class="crisp" width="256/"/>
<figcaption aria-hidden="true">
Two Different Images With The Same MD5
</figcaption>
</figure>
<p>Here is a flip-card:</p>

<p>We can visualize just the bits which have been flipped by diffing the
images:</p>
<figure>
<img src="./blog_diff.png" class="crisp" width="512/"/>
<figcaption aria-hidden="true">
Isolated Bitflips
</figcaption>
</figure>
<p>The key is that we can swap ANY of the collision blocks for their
pair, allowing us to toggle any of the indicated bits in the image
without changing the MD5.</p>
<p>Note: In the final image, we will hide these random collision bits by
placing them in an alpha channel instead of red. The data is still
rendered by the decoder, but is not visible in the final render.</p>

<p>The final piece of the puzzle will be: How can we convert these
bitflips into a hex digit display?</p>
<p>To pull this off we need to construct these components into our
prediction tree:</p>
<ol type="1">
<li>Detect the pixel bitflips from our MD5 Collision Block pixel
data</li>
<li>Combine bitflips to produce a 4-bit number (a single hex digit)</li>
<li>Move this signal to the correct render locations in the image</li>
<li>Display correct digit based on signal</li>
</ol>
<p>We have a very limited set of operations available. Here is a
selection of useful ones:</p>
<p>Comparison operators (taking the form
<code>if <prop> > <int></code>)</p>
<ul>
<li><code>c</code>: the channel number, where 0=R, 1=G, 2=B, 3=A</li>
<li><code>x</code>, <code>y</code>: coordinates</li>
<li><code>N</code>: value of pixel above (north)</li>
<li><code>W</code>: value of pixel to the left (west)</li>
<li><code>Prev</code>: the pixel value in this position in the previous
channel</li>
</ul>
<p>Prediction operators (returns the computed pixel value)</p>
<ul>
<li><code>Set <int></code>: effectively sets the pixel value to
<code><int></code></li>
<li><code>W</code>: value of pixel on the left</li>
<li><code>N</code>: value of pixel above</li>
<li><code>NW</code>: value of topleft pixel</li>
<li><code>Gradient</code>: Computes <code>W+N-NW</code>, clamped to
<code>min(W,N)..max(W,N)</code></li>
<li>etc</li>
</ul>
<p>You can find a mostly full list here: <a href="https://jxl-art.lucaversari.it/wtf.html">https://jxl-art.lucaversari.it/wtf.html</a></p>
<p>With these operators we can achieve all 4 goals!</p>
<h4 id="detecting-bitflips-with-probes">Detecting Bitflips with
“Probes”</h4>
<p>When we swap out an MD5 Collision Block, one or more pixels within
that range will change. Luckily the <code>N</code>, <code>W</code>, and
<code>Prev</code> comparison operators allow us to compare pixels to a
fixed value.</p>
<p>We can choose a value (for example 64), and then search for Collision
Blocks which swap from below to above this value.</p>
<p>For example a bit flip may cause a pixel to go from
<code>20 -> 84</code>, thus with one version of the block the
condition is false, and for the other the condition is true.</p>
<p>When the condition is true, we can output a pixel value of
<code>2**N</code> (for Nth bit in a hex character).</p>
<figure>
<img src="./blog_layout_0.png" alt="Detecting Bitflips"/>
<figcaption aria-hidden="true">Detecting Bitflips</figcaption>
</figure>
<p>These make up our “Probes”. We need 128 probes to render the full MD5
hash.</p>
<h4 id="combining-bit-values">Combining Bit Values</h4>
<p>The next step is to compute the actual 0-15 value for each set of 4
bitflips. This will make the later digit rendering much easier. So far
we have the values 1,2,4,8 set based on which bit we flip on, so we just
need to add them together.</p>
<p>While we just need an addition operator, there are actually very few
pure arithmetic operators available. Most are weighted averages or other
image rendering related operations.</p>
<p>The closest one is the <code>Gradient</code> which does a computation
of <code>W + N - NW</code> (each is a relative pixel value). It seems we
could use this if we set W to one bit value, N to another, and NW to
0…</p>
<p>BUT there is a catch! The <code>Gradient</code> is clamped, meaning
we cannot get a value larger than <code>max(W,N)</code>… so 1 + 2 ->
2</p>
<p>To make this work as addition, we need to increase this max value
above 15. Luckily, doing some simple algebra we find that it is possible
if we manipulate the <code>W - NW</code> to do the addition, and set
<code>N</code> to a value like 32.</p>
<p>Rather than using bit values <code>B = 1,2,4,8</code>, we will
instead use <code>32 - B</code> so <code>31, 30, 28, 24</code>. Then we
set <code>N = 32</code>, <code>W = acc</code> (accumulator across bits)
and <code>NW = 32 - B</code>. If you simplify:
<code>acc + 32 - (32 - B) == acc + 32 - 32 + b == acc + b</code>, and
the <code>max(acc, 32) = 32</code>, so we achieved our addition
operator!</p>
<figure>
<img src="./blog_layout_1.png" alt="Summing Bits"/>
<figcaption aria-hidden="true">Summing Bits</figcaption>
</figure>
<h4 id="pixel-wires">Pixel Wires</h4>
<p>We have computed our 4 bit sets, one for each of the 32 hex digits,
and this value exists as a pixel. Now we need to get this value to the
right digit location in the image.</p>
<p>This is actually very easy, as we can use the North and West
operators to duplicate a previous pixel value. We simply need to draw
some N/W “wires” from our bitflips to our digit locations. The only
caveat is that this only can move down and right, so we will place the
bitflips in the upper left corner of the image.</p>
<p>Here is what 32 wires looks like when rendered:</p>
<figure>
<img src="./blog_wires.png" class="crisp"/>
<figcaption aria-hidden="true">
Rendered Wires
</figcaption>
</figure>
<p>At the top of each wire is the bitflip <code>Gradient</code> addition
logic for 4 bits.</p>
<h4 id="rendering-digits">Rendering Digits</h4>
<p>The final step! We have a “wire” with the correct hex value, now we
just have to display it…</p>
<p>There are several ways you might do this, but for simplicity I took
the easiest route: Build a giant prediction tree to conditionally output
a value for each pixel in the digit.</p>
<p>To get the pixels, we pick a font (I chose <a href="https://www.theleagueofmoveabletype.com/orbitron">Orbitron</a> a
nice font for digital numbers), render it as a bitmap of some size
(15x15 here).</p>
<p>With this bitmap, we can then make a conditional tree which handles
all 16 cases, such as the following:</p>
<pre><code>if Prev > 15
  - Set 0
  if Prev > 14
    - Set 1
    if Prev > 13
      - Set 1
      if Prev > 12
        - Set 0
... etc ...</code></pre>
<p>With this in place, each digit renders based on the value of 128
pixels in the upper left corner of the image!</p>
<figure>
<img src="./blog_digits.png" class="crisp"/>
<figcaption aria-hidden="true">
All 32 Digits Rendered
</figcaption>
</figure>

<p>Almost at the finish line!</p>
<p>Before we do the final “render”, let’s give the image some extra
flare. We can inject some nice graphics into the rest of the residual
pixels. I chose a <strong>cyber shark</strong> because why not…</p>
<p>Now the final steps:</p>
<ul>
<li>Ensure that our 128 “probes” line up with the locations of the
future bitflips.</li>
<li>“Render” the image for the first time into a JPEG XL
<code>jxl</code> file</li>
<li>Progressively search for 128 pairs of MD5 Collision Blocks, placing
each one in the correct location in the <code>jxl</code></li>
<li>Verify everything is happy along the way (I had a few blocks fail to
function and had to redo parts of the search a few times)</li>
</ul>
<p>Once everything is in place we have a final <code>jxl</code> image
file and a set of 128 pairs of blocks…</p>
<p>Using a script we can swap these blocks in at will to encode any 128
bit pattern we like!</p>
<figure>
<div class="image-container">
<p><picture> <source srcset="./with_41414141.jxl" type="image/jxl" class="crisp" width="512" height="512"/> <img src="./with_41414141.jxl.png" onload="this.parentElement.parentElement.parentElement.className='';" class="crisp" width="512" height="512"/> </picture></p>
</div>
<figcaption aria-hidden="true">
Displaying 41414141…
</figcaption>
</figure>
<figure>
<div class="image-container">
<p><picture> <source srcset="./with_deadbeef.jxl" type="image/jxl" class="crisp" width="512" height="512"/> <img src="./with_deadbeef.jxl.png" onload="this.parentElement.parentElement.parentElement.className='';" class="crisp" width="512" height="512"/> </picture></p>
</div>
<figcaption aria-hidden="true">
Displaying DEADBEEF…
</figcaption>
</figure>
<figure>
<div class="image-container">
<p><picture> <source srcset="./with_md5.jxl" type="image/jxl" class="crisp" width="512" height="512"/> <img src="./with_md5.jxl.png" onload="this.parentElement.parentElement.parentElement.className='';" class="crisp" width="512" height="512"/> </picture></p>
</div>
<figcaption aria-hidden="true">
Displaying Its Own MD5 Hash!
</figcaption>
</figure>
<div class="jxl-warning" readability="11.623616236162">
<strong>NOTE</strong>: Your browser does not support JPEG XL! <br/>If
you want to verify the hashes, either try a browser that does (safari),
or download the .jxl files:

<p>The images above are PNG renders which do not have the same MD5
properties</p>
</div>
<div class="sourceCode" id="cb12" readability="8"><pre class="sourceCode bash"><code class="sourceCode bash"><span id="cb12-1"><a href="#cb12-1" aria-hidden="true" tabindex="-1"/><span class="ex">$</span> md5sum with_<span class="pp">*</span></span>
<span id="cb12-2"><a href="#cb12-2" aria-hidden="true" tabindex="-1"/><span class="ex">6812e709a47c620a679850629e66f42c</span>  with_41414141.jxl</span>
<span id="cb12-3"><a href="#cb12-3" aria-hidden="true" tabindex="-1"/><span class="ex">6812e709a47c620a679850629e66f42c</span>  with_deadbeef.jxl</span>
<span id="cb12-4"><a href="#cb12-4" aria-hidden="true" tabindex="-1"/><span class="ex">6812e709a47c620a679850629e66f42c</span>  with_md5.jxl</span></code></pre></div>
<p>We have done it!!! We have produced a JPEG XL image which displays
its own MD5 Hash!</p>

<p>As a final touch, we can hide some leet speak inside the hash.</p>
<p>Any data we change after the last MD5 Collision Block will change the
final MD5 hash, but the image will still function as expected. We can
simply brute force changes to the last bytes in the file until the hash
appears how we want.</p>
<p>For my final image, I chose to start the md5 with
<code>c0dec000</code> (since we are abusing such an expressive image
codec). It took about 2-3 min on my laptop to brute force the 32-bits in
rust and locate a hash starting with this.</p>
<p>And so the final image is now complete!</p>
<div class="sourceCode" id="cb13" readability="7"><pre class="sourceCode bash"><code class="sourceCode bash"><span id="cb13-1"><a href="#cb13-1" aria-hidden="true" tabindex="-1"/><span class="ex">$</span> md5sum shark_hashquine.jxl</span>
<span id="cb13-2"><a href="#cb13-2" aria-hidden="true" tabindex="-1"/><span class="ex">c0dec0007b5246f7428936d9bed2f446</span>  shark_hashquine.jxl</span></code></pre></div>
<figure>
<div class="image-container">
<p><picture> <source srcset="./shark_hashquine.jxl" type="image/jxl" class="crisp" width="512" height="512"/> <img src="./shark_hashquine.jxl.png" onload="this.parentElement.parentElement.parentElement.className='';" class="crisp" width="512" height="512"/> </picture></p>
</div>
<figcaption aria-hidden="true">
Final JPEG XL Hash Quine
</figcaption>
</figure>
<div class="jxl-warning" readability="9.8949771689498">
<p><strong>NOTE</strong>: Your browser does not support JPEG XL! <br/>If
you want to verify the hash, either try a browser that does (safari), or
<a href="./shark_hashquine.jxl">download the .jxl file</a> <br/>The
image above is a PNG render which does not have the same MD5
properties</p>
</div>
<p><a href="./shark_hashquine.jxl">Download Final Hashquine</a></p>

<p>This was a very fun project which further increased my understanding
of the litany of features JPEG XL provides.</p>
<p>Creating a <strong>Weird Machine</strong> inside a predictive image
decoder opens a world of possibilities for strange and wonderful
images.</p>
<p>I do hope that JPEG XL support will become widespread soon. Safari is
ahead of the game here, and chrome/firefox need to catch up!</p>
<p>As for the final image, there are a few things I perhaps would like
to improve for a future version:</p>
<h3 id="improve-image-size">Improve Image Size</h3>
<p>The image size is ~2mb. This is mostly caused by the lack of
compression due to our trivial huffman tree.</p>
<p>I believe this size can be greatly reduced by limiting which channels
have this tree applied, removing a huge number of uncompressed null
bytes.</p>
<h3 id="improve-prediction-tree">Improve Prediction Tree</h3>
<p>The prediction tree was massive. The final version compiles to >
90000 nodes. I actually had to add additional channels to the image so
the decoder would allow it!</p>
<p>The majority of this comes from the digit rendering. The naive tree
creation algorithm can be improved for sure.</p>
<p>I also want to try out the “patch” feature of JPEG XL. This may allow
us to render an entire digit in one go. The main difficulty is
conditionally selecting the patch.</p>

<p>Thank you for reading!</p>
<p>If you are inspired, maybe think about some of your favorite file
formats and see if you can make your own <strong>Hash
Quine</strong>!</p>
<p>Every file format lives in its own unique computational world.</p>
</div>
</body>
</div>        </div>
    </div>
</div>
<div class='clear'></div>    </div>
    <div style='position:fixed; bottom:0; left:0; right:0;'>
        </div>
    <div align='center' style='border-top:1px solid #EEE; padding:1em; margin-top:2em;'>
  联系我们 contact @ memedata.com
</div>

<script async src="https://www.googletagmanager.com/gtag/js?id=G-PFMR8YTWGP"></script>
<script>
  window.dataLayer = window.dataLayer || [];
  function gtag(){dataLayer.push(arguments);}
  gtag('js', new Date());

gtag('config', 'G-PFMR8YTWGP');
</script>
</body>
</html>

构建第一个 JPEG XL MD5 哈希quine Constructing the Word's First JPEG XL MD5 Hash Quine

What In The Hash!

构建第一个 JPEG XL MD5 哈希quine
Constructing the Word's First JPEG XL MD5 Hash Quine