乌云峰会puzzle 第四题命题报告

writeup

这个题目的最初思路来自于2015年台湾逢甲大學張真誠教授在上海交通大学做的一个学术报告，張教授介绍了关于使用数独方阵进行信息隐藏的主题报告。从这个非常有意思的方案出发，我们设计了一个类似的信息隐藏小程序，并命题制作了本次峰会Puzzle系列的第四题。

首先，我们给出的题目包含了一张图片（图片本身是一个数独，也就是解题需要的数独方阵）以及三个二进制可执行文件，三个可执行文件分别对应的是Windows，Linux和Raspberry Pi ARM平台，出题的时候有意对最后一个树莓派上可执行文件的符号进行了保留（从后来看到的解题报告来看，这个信息对解题起到了一定的帮助）。

我们设计的基于数独方阵的信息隐藏算法很简单，首先介绍一下这个算法：隐藏信息的方案依赖于我们选择的数独方阵，熟悉数独的同学都知道数独可以按每行，每列或者每个9x9的小方格；对于每一行、列或者小方格，可以将其视为[1,2,3,4,5,6,7,8,9]的一个随机置换。这个随机置换是之后信息隐藏的关键：我们将一张bmp图片中的每个像素点（RGB值）取出得到一个三元组，三元组中每一个像素点都可以用来隐藏信息。根据人眼的视觉特性，稍微改变一下像素点的RGB值，并不会让视觉产生很大的差异，因此我们对每个像素点的RGB值三元组进行一个“偏移”，假设一个像素点的RGB值原先为[x,y,z]，我们通过对每个值加上或者减去一个小于9的数，人为将其修改为[x',y',z']，使得x',y',z'每个值 mod 9之后都变为我们指定的值a, b, c；这里的a, b, c再通过数独方阵中特定的行、列或者小方格指定的置换所对应的逆变换，就恢复得到了原始的信息。

为了编码特定的明文，我们先将字符串转换成hex值，然后对每4bit信息m转成两个值(m & 0xF) / 9和(m & 0xF) % 9，再把这一系列的值通过数独方阵指定的行、列和小方格进行置换。最后把置换写回到bmp里面去。在操作bmp时，我们使用了http://partow.net/programming/bitmap/提供的一个简单方便的bmp C++ library，使得程序可以很简洁地完成这个编码变换。

#include "bitmap_image.hpp"
/* solution
unsigned char soduku[] = "126730458075684132483215607204563781358471026617028345531807264742356810860142573";
unsigned char text[] = "1aed56787db88808434ed857e200507c4de68ef3";
 */
unsigned char soduku[] = "251764983683921475947835126824576391395182764176493852539648217418257639762319548";
unsigned char text[] = "50105f052d4681d28c642188cabfff5b7492817d";
unsigned char msg[sizeof(text) * 4];
unsigned int transform( unsigned int input, size_t counter )
{
 unsigned char table[9];
 if ( counter % 3 == 0 )
 {
  unsigned int row = counter / 3 % 9;
  for ( size_t i = 0; i < 9; ++i )
  {
   table[i] = soduku[row * 9 + i];
  }
 }
 if ( counter % 3 == 1 )
 {
  unsigned int col = counter / 3 % 9;
  for ( size_t i = 0; i < 9; ++i )
  {
   table[i] = soduku[i * 9 + col];
  }
 }
 if ( counter % 3 == 2 )
 {
  unsigned int cell = counter / 3 % 9;
  for ( size_t i = 0; i < 3; ++i )
  {
   unsigned int row = i + cell / 3 * 3;
   for ( size_t j = 0; j < 3; ++j )
   {
    unsigned int col = cell % 3 * 3 + j;
    table[i * 3 + j] = soduku[row * 9 + col];
   }
  }
 }
 unsigned int x = input / 9 * 9 + table[ msg[counter % sizeof(msg)] ] - 0x30;
 /*
 if ( counter < sizeof(msg) )
 {
  printf("%d", x % 9 );
 }
 */
 return x > 255 ? x - 9 : x;
}
int main()
{
 for ( size_t i = 0; i < sizeof(text); ++i )
 {
  msg[i * 4 + 0] = (text[i] & 0xF) / 9;
  msg[i * 4 + 1] = (text[i] & 0xF) % 9;
  msg[i * 4 + 2] = (text[i] >> 4 & 0xF) / 9;
  msg[i * 4 + 3] = (text[i] >> 4 & 0xF) % 9;
 }
 /*
 for ( size_t i = 0; i < sizeof(msg); ++i )
  printf("%d", msg[i]);
 puts("");
 */
 bitmap_image image("input.bmp");
 if (!image)
 {
  printf("Error - Failed to open: input.bmp\n");
  return 1;
 }
 unsigned char red;
 unsigned char green;
 unsigned char blue;
 unsigned int total_number_of_pixels = 0;
 const unsigned int height = image.height();
 const unsigned int width  = image.width();
 size_t counter = 0;
 for (size_t y = 0; y < height; ++y)
 {
  for (size_t x = 0; x < width; ++x)
  {
   image.get_pixel( x, y, red, green, blue);
   if ( (y * width + x) % 3 == 0 )
   {
    red = transform( red, counter++ );
   }
   if ( (y * width + x) % 3 == 1 )
   {
    green = transform( green, counter++ );
   }
   if ( (y * width + x) % 3 == 2 )
   {
    blue = transform( blue, counter++ );
   }
   image.set_pixel( x, y, red, green, blue);
  }
 }
 image.save_image("soduku.bmp");
 return 0;
}

我们发布的binary executables中所编码的unsigned char soduku[]数组并不是对应发布的包含隐写信息bmp所采用的数组，实际使用的数组可以通过解这个数独来得到。我们选择的这个数独很有名，它来自于Gary McGuire在其著名的论文《There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration》中所给出的一个17个数字具有唯一解的数独puzzle。
实际上，在我们自己对几个发布发binary executables进行分析的时候发现如果对raspberry pi版本的elf进行分析（例如使用Hex-rays分析插件），得到的结果基本上和源代码是差不太多的，因此解答此题的主要难点在于理解这个思路，对每个像素点取到其隐藏的信息并拼接起来就可以得到正确的答案：字符串"http://www.securitygossip.com"的SHA-1值。