Login
Immutable PageDiscussionInfoAttachments
CTF/Writeup/SECCON 2014 Quals Online Winter/Decrypt it (Easy)

MMA

Decrypt it (Easy) (Crypto 200pts)

バイナリを読んだ結果,概ね次のような動作をすることがわかった。

   1 srand(time(NULL));
   2 while (!feof(rfp)) {
   3   fread(buf, 1, 1, rfp);
   4   buf[0] = buf[0] ^ (rand() % 256);
   5   fwrite(buf, 1, 1, wfp);
   6 }

ファイルの最終更新日時を中心に時刻の探索を行った。

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 char buf[10];
   4 int main() {
   5   FILE *fp  = fopen("ecrypt1.bin","r");
   6   fread(buf, 8, 1, fp);
   7   int i,j,cnt=0;
   8   for(i = 1416606360+100000; i > 1416606360-1000000; i--) {
   9     srand(i);
  10     char enc[10];
  11     for(j = 0; j < 8; j++) {
  12       enc[j] = buf[j] ^ (rand() % 256);
  13     }
  14         if (enc[0] == (char)0x89 &&
  15                 enc[1] == (char)0x50 &&
  16                 enc[2] == (char)0x4E &&
  17                 enc[3] == (char)0x47 &&
  18                 enc[4] == (char)0x0D &&
  19                 enc[5] == (char)0x0A &&
  20                 enc[6] == (char)0x1A &&
  21                 enc[7] == (char)0x0A) {
  22                 printf("%d\n", i);
  23         }
  24   }
  25 }

結果,時刻は1416667590であることが判明したので復号を行ったところ次の画像が得られた。

crypt1.png

これはRabin暗号である。nを素因数分解して秘密鍵を得て復号を行う。

   1 require_relative 'math'
   2 nn = [0xb8ae199365, 0xb86e78c811, 0x7bd4071e55]
   3 bb = [0xffeee, 0xfffee, 0xfefef]
   4 cc = [0x8d5051562b, 0x5ffa0ac1a2, 0x6008ddf867]
   5 for i in 0..2
   6   n = nn[i]
   7   b = bb[i]
   8   c = cc[i]
   9 
  10   p, q= Math::prime_factorization2(n).map{|a|a[0]}
  11   puts [p,q].map{|a|a%4}
  12 
  13   for xx in 1..p
  14     if (xx * xx + b * xx - c)% p == 0
  15       p (['!',xx])
  16       x_p = xx
  17     end
  18   end
  19   for xx in 1..p
  20     if (xx * xx + b * xx - c)% q == 0
  21       p (['!',xx])
  22       x_q = xx
  23     end
  24   end
  25 
  26   puts ['%x' % (Math::chinese_remainder(p, q, x_p, x_q))].pack('H*')
  27   puts ['%x' % Math::chinese_remainder(p, q, p - b -  x_p, x_q)].pack('H*')
  28   puts ['%x' % Math::chinese_remainder(p, q, p - b -  x_p, q - b-x_q)].pack('H*')
  29   puts ['%x' % Math::chinese_remainder(p, q, x_p, q - b-x_q)].pack('H*')
  30 end

暗号文に対して平文は4種類対応するため,その中から意味のあるものを採用する。

こうしてフラグが得られた。

SECCON{Ra_b1_N}

なお,WikipediaのRabin暗号のページに書かれていた式はコンテスト時点では間違っており, 平方根を求めるために\((p+1)/4\)乗すべきところが\((p-1)/2\)乗になっていた。 これでは二乗すると1になってしまう。 これに騙されたチームも多かったのではないだろうか。

<del>Pari/GP芸</del>Pari/GPによる実装例

具体的な数字は最後のブロックだけ

n=531838213717
b=1044463
c=412465625191

p=factor(n)[1,1]
q=n/p
xp = sqrt(c+Mod(b,p)*b/4)-Mod(b,p)/2
xq = sqrt(c+Mod(b,q)*b/4)-Mod(b,q)/2 
x1 = chinese(xp, xq)
x2 = chinese(-xp-b, xq)
x3 = chinese(xp, -xq-b)
x4 = chinese(-xp-b, -xq-b)

? x1 = chinese(xp, xq)
%8 = Mod(421735124605, 531838213717)
? x2 = chinese(-xp-b, xq)
%9 = Mod(368810693940, 531838213717)
? x3 = chinese(xp, -xq-b)
%10 = Mod(163026475314, 531838213717)
? x4 = chinese(-xp-b, -xq-b)
%11 = Mod(110102044649, 531838213717)

CTF/Writeup/SECCON 2014 Quals Online Winter/Decrypt it (Easy) (last edited 2014-12-07 19:45:01 by ytoku)