Writeup for 0000000000000000 in TSG CTF

0000000000000000-writeup.md

Writeup for 0000000000000000 in TSG CTF

Problem

I took a photo at university on a sunny day~~

天気がいい日に大学で写真を撮ったよ

(with a JPEG file, attached to this writeup as problem.jpg)

Solution: TL;DR

• Some of the 8x8 blocks in the provided JPEG image have a redundant ZRL just before an EOB.
• If you plot those blocks, a QR code shows up.
• The QR code reads:

  Whoa, congratulations! The flag is:
  TSGCTF{I_understand_JPEG_perf3ctly}
  

Details

In JPEG encoding, the image is partitioned into 8x8 (= 64 pixels) blocks and each block is transformed by the forward DCT into 64 coefficients. 63 out of the 64 coefficients are called AC coefficients and are encoded with Huffman encoding in the zig-zag sequence. The zig-zag sequence orders coefficients by (roughly) ascending frequency.

In Huffman encoding, coefficients of value zero are treated specially: they are encoded as a run-length of zero coefficients (in 4 bits). If the run-length exceeds 15 (the maximum 4-bit number), a special value ZRL is put which means a run of 16 zero coefficients. In addition, a special value EOB is put when all the remaining coefficients in the block are zero.

Here I noticed that a sequence of ZRL+EOB is just the same as a single EOB. This led me to think that I can embed arbitrary data, corresponding one bit to whether one block has ZRL+EOB or not.

Solution script

This plots the blocks in the provided JPEG file which have the ZRL+EOB sequence. (patch.diff and solve.js are attached to this writeup)

$ npm install jpeg-js@0.3.5
$ cp node_modules/jpeg-js/lib/decoder.js ./decoder.js
$ patch < patch.diff
$ node solve.js | gnuplot -e "set size square; set terminal png; set output 'plot.png'; plot '-' using 1:(-\$2) pt 5 ps 0.3"

Then a QR code shows up (see plot.png). Read it and get the flag. TSGCTF{I_understand_JPEG_perf3ctly}

There is some noise in the QR code because some blocks had more than 48 non-zero coefficients so I couldn't put a ZRL before an EOB.

patch.diff

--- decoder.js	2019-05-06 15:35:41.000000000 +0900
+++ decoder_.js	2019-05-06 16:03:52.000000000 +0900
@@ -148,19 +148,26 @@
       var diff = t === 0 ? 0 : receiveAndExtend(t);
       zz[0]= (component.pred += diff);
       var k = 1;
+      var lastZRL = false;
       while (k < 64) {
         var rs = decodeHuffman(component.huffmanTableAC);
         var s = rs & 15, r = rs >> 4;
         if (s === 0) {
-          if (r < 15)
+          if (r < 15) {
+            if (lastZRL) {
+              throw "redundant ZRL";
+            }
             break;
+          }
           k += 16;
+          lastZRL = true;
           continue;
         }
         k += r;
         var z = dctZigZag[k];
         zz[z] = receiveAndExtend(s);
         k++;
+        lastZRL = false;
       }
     }
     function decodeDCFirst(component, zz) {
@@ -256,7 +263,15 @@
       var mcuCol = mcu % mcusPerLine;
       var blockRow = mcuRow * component.v + row;
       var blockCol = mcuCol * component.h + col;
-      decode(component, component.blocks[blockRow][blockCol]);
+      try {
+        decode(component, component.blocks[blockRow][blockCol]);
+      } catch(e) {
+        if (e === "redundant ZRL") {
+          console.log(blockCol, blockRow);
+        } else {
+          throw e;
+        }
+      }
     }
     function decodeBlock(component, decode, mcu) {
       var blockRow = (mcu / component.blocksPerLine) | 0;

plot.png

problem.jpg

solve.js

const fs = require('fs');
const decoder = require('./decoder');

const data = fs.readFileSync('problem.jpg');

// The modified decoder prints to the stdout the coordinates of
// blocks which have ZRL+EOB
decoder(data);