PNG over Teregraph

問題概要

ジャンル

Crypto

点数

300 points

問題文

PNG over Telegraph
Analyze signal in this video.
You will able to get PNG, if you success to decode it.
https://youtu.be/Y6voaURtKlM

フラグ

SECCON{SEMAPHORE_LINE_IS_THE_1ST_TELEGRAPH_SYSTEM_IN_THE_WORLD}

挑戦者

idzuna

解法

フレームの切り出し

動画のフレームを1秒ごとに切り出す．
オフセットは試行錯誤の結果，0.8秒がちょうどよかった．

ffmpeg -i video.mp4 -vf crop=200:200:260:20 -ss 0.8 -r 1 -f image2 %06d.bmp

符号の推測

動画を見ていると，腕木のシンボルは32通りあるっぽい．
三十二進数であると仮定して，PNGフォーマットのヘッダ構造や，特定の符号 (0や31) が連続することなどから，腕木シンボルと数値の対応関係を推測する．

動画の冒頭部分を見ると，腕木のシンボルと，A-Yまでのアルファベットの対応がわかる．
これら A-Y はそれぞれ三十二進数の 0 - 24 に対応しているっぽい．
残りの 25 - 31 も，A-Y までの規則性などからなんとなく推測できる．
わからないところは試行錯誤．

画像のマッチング

三十二進数に対応する32種類の画像を人力で探し出し，それらとマッチさせる．
単純に画像をベクトルと見なして，平均0, ノルム1になるように正規化しておき，内積の大きいやつを選べば識別できた．
腕木がぶれたりカメラの位置がずれたりするので，画像を1画素ずつずらしながらマッチングし，一番内積が大きいものを採用する．

#include <TNLib\Bitmap.hpp>
#include <TNLib\Raw.hpp>
#include <Eigen\Eigen>
#include <string>
#include <sstream>
#include <iomanip>
#include <iostream>

int main()
{
  const int h = 184;
  const int w = 192;
  Eigen::MatrixXd pattern[32];

  for ( int i = 0 ; i < 32 ; ++i )
  {
    pattern[i].resize( w*h , 128 );

    Eigen::MatrixXd r , g , b;
    std::ostringstream filename;
    filename << "pattern/(" << i << ").bmp";
    std::cout << filename.str() << std::endl;
    TNLib::loadBitmap( filename.str() , r , g , b );

    for ( int k = 0 ; k < 16 ; ++k )
    for ( int l = 0 ; l < 8 ; ++l )
    {
      for ( int j = 0 ; j < w ; ++j )
        pattern[i].block(j*h,k*8+l,h,1) = r.block(k,l+j,h,1);
      pattern[i].col(k*8+l) = pattern[i].col(k*8+l).array() - pattern[i].col(k*8+l).mean();
      pattern[i].col(k*8+l).normalize();
    }
  }

  static int indices[2984];
#pragma omp parallel for
  for ( int i = 0 ; i < 2984 ; ++i )
  {
    Eigen::MatrixXd r , g , b;
    std::ostringstream filename;
    filename << std::setfill('0') << std::setw(6) << (i+78) << ".bmp";

    std::cout << filename.str() << std::endl;
    TNLib::loadBitmap( filename.str() , r , g , b );

    Eigen::VectorXd v(w*h);
    for ( int j = 0 ; j < w ; ++j )
      v.block(j*h,0,h,1) = r.block(8+i*8/2984,j+4-i*3/2984,h,1);
    v = v.array() - v.mean();
    v.normalize();

    double result[32];
    for ( int j = 0 ; j < 32 ; ++j )
    {
      Eigen::VectorXd prod = pattern[j].transpose() * v;
      result[j] = prod.maxCoeff();
    }
    indices[i] = static_cast<int>( std::distance( result , std::max_element( result , result + 32 ) ) );
  }
  TNLib::saveArrayToFile( "indices.bin" , indices );
  return 0;
}

復号

#include <TNLib\Raw.hpp>
#include <string>
#include <sstream>
#include <iomanip>
#include <iostream>

int main()
{
  static int indices[2984];
  TNLib::loadArrayFromFile( "indices.bin" , indices );
  std::ofstream out( "out.png" , std::ios::out | std::ios::binary );

  for ( int i = 0 ; i < 2984 ; i += 8 )
  {
    std::uint64_t v = indices[i];
    v = ( v << 5 ) | indices[i+1];
    v = ( v << 5 ) | indices[i+2];
    v = ( v << 5 ) | indices[i+3];
    v = ( v << 5 ) | indices[i+4];
    v = ( v << 5 ) | indices[i+5];
    v = ( v << 5 ) | indices[i+6];
    v = ( v << 5 ) | indices[i+7];

    char buf[5];
    buf[0] = ( v >> 32 ) & 0xff;
    buf[1] = ( v >> 24 ) & 0xff;
    buf[2] = ( v >> 16 ) & 0xff;
    buf[3] = ( v >>  8 ) & 0xff;
    buf[4] =   v         & 0xff;

    out.write( buf , sizeof(buf) );
  }
  return 0;
}

これが出てくる．

議論

三十二進数っぽい
三十二進数なので，それに加えて7つのシンボルがあるみたいだけど対応がよくわからない．