もなちゃとのトリップ生成アルゴリズムは2007年、Linux Userによって解読され、2008年12月14日に変更され、再び解読され、2010年4月3日に現在の方式に変更された。

ここではもなちゃとのトリップの歴史を振り返る。

最初のトリップ(-2008/12/14)は6桁で、キーをSHA-1でハッシュし、Base64のような符号化を行ったものだった。

現在でもInternet Archiveから当時のmojachat5e.swfをダウンロードして逆コンパイルすることにより、当時の生成コードを確認することができる。ここでは不自由なFlashの逆コンパイラであるflareを使用している(macOSではflareが動かないため、VirtualBox上のKali Linuxで実行)。

$ wget https://web.archive.org/web/monachat.dyndns.org/mojachat5e.swf
$ wget http://www.nowrap.de/download/flare06linux64.tgz
$ tar zxvf flare06linux64.tgz flare
$ ./flare mojachat5e.swf
$ grep -A104 'Object\.protoype\.crypt' mojachat5e.flr
    if (typeof Object.protoype.crypt == 'undefined') {
      Object.prototype.crypt = new Object();
      ASSetPropFlags(Object.prototype, ['crypt'], 1);
    }
    crypt.sh = function (val) {
      crypt.sh.hex_chr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789./';
      var x = crypt.sh.str2blks_SHA1(val);
      var v2 = new Array(80);
      var a = 1732584193;
      var b = -271733879;
      var c = -1732584194;
      var v3 = 271733878;
      var e = -1009589776;
      var i = 0;
      while (i < x.length) {
        var olda = a;
        var oldb = b;
        var oldc = c;
        var oldd = v3;
        var olde = e;
        var v1 = 0;
        while (v1 < 80) {
          if (v1 < 16) {
            v2[v1] = x[i + v1];
          } else {
            v2[v1] = crypt.sh.rol(v2[v1 - 3] ^ v2[v1 - 8] ^ v2[v1 - 14] ^ v2[v1 - 16], 1);
          }
          var t = crypt.sh.safe_add(crypt.sh.safe_add(crypt.sh.rol(a, 5), crypt.sh.ft(v1, b, c, v3)), crypt.sh.safe_add(crypt.sh.safe_add(e, v2[v1]), crypt.sh.kt(v1)));
          e = v3;
          v3 = c;
          c = crypt.sh.rol(b, 30);
          b = a;
          a = t;
          ++v1;
        }
        a = crypt.sh.safe_add(a, olda);
        b = crypt.sh.safe_add(b, oldb);
        c = crypt.sh.safe_add(c, oldc);
        v3 = crypt.sh.safe_add(v3, oldd);
        e = crypt.sh.safe_add(e, olde);
        i += 16;
      }
      return crypt.sh.hex(a) + crypt.sh.hex(b) + crypt.sh.hex(c) + crypt.sh.hex(v3) + crypt.sh.hex(e);
    };

    crypt.sh.hex = function (num) {
      var v3 = num;
      var v2 = '';
      var v1 = 7;
      while (v1 >= 0) {
        v2 += crypt.sh.hex_chr.charAt(v3 >> v1 * 4 & 63);
        --v1;
      }
      return v2;
    };

    crypt.sh.str2blks_SHA1 = function (str) {
      var v3 = str;
      var nblk = (v3.length + 8 >> 6) + 1;
      var v2 = new Array(nblk * 16);
      var v1 = 0;
      while (v1 < nblk * 16) {
        v2[v1] = 0;
        ++v1;
      }
      v1 = 0;
      while (v1 < v3.length) {
        v2[v1 >> 2] |= v3.charCodeAt(v1) << 24 - (v1 % 4) * 8;
        ++v1;
      }
      v2[v1 >> 2] |= 128 << 24 - (v1 % 4) * 8;
      v2[nblk * 16 - 1] = v3.length * 8;
      return v2;
    };

    crypt.sh.safe_add = function (x, y) {
      var v1 = (x & 65535) + (y & 65535);
      var v2 = (x >> 16) + (y >> 16) + (v1 >> 16);
      return v2 << 16 | v1 & 65535;
    };

    crypt.sh.rol = function (num, cnt) {
      return num << cnt | num >>> 32 - cnt;
    };

    crypt.sh.ft = function (t, b, c, d) {
      var v1 = b;
      var v2 = d;
      var v3 = c;
      if (t < 20) {
        return v1 & v3 | ~v1 & v2;
      }
      if (t < 40) {
        return v1 ^ v3 ^ v2;
      }
      if (t < 60) {
        return v1 & v3 | v1 & v2 | v3 & v2;
      }
      return v1 ^ v3 ^ v2;
    };

    crypt.sh.kt = function (t) {
      var v1 = t;
      return v1 < 20 ? 1518500249 : (v1 < 40 ? 1859775393 : (v1 < 60 ? -1894007588 : -899497514));
    };

このActionScriptコードは3行目(と1行目のtypo)を除けばJavaScriptコードとしても妥当である。

Perlによる初代トリッパーの実装は次のようになる。

$ perl -MAlgorithm::Combinatorics=tuples_with_repetition -MDigest::SHA=sha1 -E '@a = (A..Z, a..z, 0..9, qw(. /)); $i = tuples_with_repetition \@a, shift; while ($k = $i->next) { $k = join "", @$k; $h = unpack "x16 N4", sha1 $k; $t = ""; $t .= $a[$h >> $_ * 4 & 63] for reverse 0..5; say "$k\t$t" }' 6

この出力をtripdb.txtにリダイレクトし、tripdb.txtが18GiBを超えたあたりで止め、最終行が中途半端な場合はtruncate -s -$(tail -n 1 tripdb.txt | wc -c) tripdb.txtで最終行を削除し、LC_ALL=C sort -S 50% --parallel=4 -t \t -k 2,2 -uo tripdb.txt tripdb.txtでトリップでソートし重複をなくすことで、896MiB、2^26 = 67108864行の完全トリップデータベースが得られる。

トリップでソートした効果で、次のようなプログラムにより指定したトリップが何行目にあるかを計算し、seekしてreadすることで、完全一致のトリップの検索はO(1)で行える。

#!/usr/bin/env perl
use v5.12;
use warnings;
use autodie;

my %alphabet;
@alphabet{ qw(. /), 0..9, 'A'..'Z', 'a'..'z' } = 0..63;

my %succ;
@{ $succ{$_} }{ 'g'..'v' } = 0..15
  for qw(. 2 6 C G K O S W a e i m q u y);
@{ $succ{$_} }{ qw(. /), 0..9, 'w'..'z' } = 0..15
  for qw(/ 3 7 D H L P T X b f j n r v z);
@{ $succ{$_} }{ 'A'..'P' } = 0..15
  for qw(0 4 8 A E I M Q U Y c g k o s w);
@{ $succ{$_} }{ 'Q'..'Z', 'a'..'f' } = 0..15
  for qw(1 5 9 B F J N R V Z d h l p t x);

my $trip = shift;
my @chars = split //, $trip;
my $n;
$n += (
      $_
    ? $succ{ $chars[ $_ - 1 ] }{ $chars[$_] }
    : $alphabet{ $chars[$_] }
  ) * 16**( $#chars - $_ )
  for 0..$#chars;

open my $fh, '<', 'tripdb.txt';
seek $fh, ( 6 + 1 + 6 + 1 ) * $n, 0;
my $buf;
read $fh, $buf, 6 + 1 + 6;
say $buf;
close $fh;

一般にキーをトリップと同じ長さにし、トリップと同じ文字集合をキーに使うことは、チェイン化(前のトリップを次のキーにすれば、トリップだけをDBに書けば済む)によってレインボーテーブルのサイズを削減するためにも重要である。

2代目のトリップ(2008/12/14-2010/4/3)は10桁で、2chと同様にcrypt(3)を使用しており、総当たりで即座にsaltが特定された。Perlによるトリッパーの実装は次のようになる。

$ perl -MAlgorithm::Combinatorics=tuples_with_repetition -E '$i = tuples_with_repetition [qw(. /), 0..9, A..Z, a..z], shift; while ($k = $i->next) { $k = join "", @$k; say "$k\t", substr crypt($k, $k . "H."), -10 }' 8

そして現在のトリップ(2010/4/3-)は10桁で、.記号の代わりに+記号が出現するものとなっている。

これまでのところ、末尾には048AEIMQUYcgkoswの16文字しか出現しないことが分かっている。

キーをSHA-1でハッシュしBase64エンコードした場合も、末尾にはこれらの16文字しか出現しないようだが、単純なSHA-1 + Base64ではないようである。

2009年6月19日に2chでSHA-1 + Base64の12桁トリップが採用されたことに影響を受けているのではないかと考えられ、キーに何らかの処理をしてSHA-1 + Base64を行ったものではないかと推測されるが、現在のトリップ生成アルゴリズムは9年経った今も解読されておらず、もなちゃと上の最大の未解決問題となっている。