--- lang: ja-jp breaks: true --- 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) が連続することなどから,腕木シンボルと数値の対応関係を推測する. ![](https://i.imgur.com/qu0SSxZ.png) 動画の冒頭部分を見ると,腕木のシンボルと,A-Yまでのアルファベットの対応がわかる. これら A-Y はそれぞれ三十二進数の 0 - 24 に対応しているっぽい. 残りの 25 - 31 も,A-Y までの規則性などからなんとなく推測できる. わからないところは試行錯誤. ### 画像のマッチング 三十二進数に対応する32種類の画像を人力で探し出し,それらとマッチさせる. 単純に画像をベクトルと見なして,平均0, ノルム1になるように正規化しておき,内積の大きいやつを選べば識別できた. 腕木がぶれたりカメラの位置がずれたりするので,画像を1画素ずつずらしながらマッチングし,一番内積が大きいものを採用する. ```C++= #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; } ``` ### 復号 ```C++= #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; } ``` これが出てくる. ![](https://i.imgur.com/WNiE6Wp.png) ## 議論 三十二進数っぽい 三十二進数なので,それに加えて7つのシンボルがあるみたいだけど対応がよくわからない.