Sim's blog

電子工作はじめてみました

ICFP2007 (15) Fuun Security Features

2007-08-30 23:43:13 | ICFPプログラミングコンテスト
ICFP2007 (14)の続きです。

以前も貼りましたがカタログのpage 4405829です。



help-fuun-securityという関数で表示されています。中身を見てみると何のひねりもなく暗号化された文字列を表示しているだけでした。コードから文字列を抽出しました。
Shhaf pbagnva n terng qrny bs cebcevrgnel grpuabybtl. Gb cebgrpg gur Vagryyrpghny Cebcregl 
evtugf bs ShhaGrpu naq vgf fgbpxubyqref, pregnva cnegf bs n Shha'f QAN ner rapelcgrq hfvat 
bar bs gjb pelcgbtencuvp grpuabybtvrf. Guvf ranoyrf fhpu cnegf gb or npprffrq bayl ol gubfr 
phfgbzref jub unir bognvarq gur arprffnel npprff pbqrf.

Zrgubq N jnf hfrq va gur cnfg, ohg vg unf erpragyl orra oebxra. Vaqrrq, gur rapelcgvba fpurzr 
jnf erirnyrq gb or fb synjrq gung vg pna or oebxra znahnyyl. Vg vf fgvyy va hfr sbe fbzr cnegf bs 
gur flfgrz, ohg ShhaGrpu vf zvtengvat njnl sebz vg. Jr jvyy abg qvfphff vg shegure.

Zrgubq O, n ShhaGrpu genqr frperg, vf fvtavsvpnagyl zber cbjreshy. Vg erdhverf gur phfgbzre 
gb rapbqr n fcrpvny frdhrapr bs punenpgref, pnyyrq n "xrl", vagb uvf Shha'f QAN ng n fcrpvsvp 
ybpngvba. Vs gur xrl vf cerfrag, gur pbeerfcbaqvat shapgvbanyvgl orpbzrf ninvynoyr. Bgurejvfr, 
Shha orunivbhe znl enatr sebz na reebe zrffntr gb ivbyrag qrngu.

Vs lbh unir ybfg n xrl, erpbirel bs gur xrl vf abg trarenyyl cbffvoyr qhr gb gur pbzcyrkvgl bs gur 
pelcgbtencuvp grpuabybtl. (Vg vf n tbbq vqrn gb jevgr qbja xrlf fbzrjurer, znlor rira ba n lryybj 
cvrpr bs cncre nggnpurq gb lbhe pbzchgvat qrivpr.) Ubjrire, vs lbhe xrl vf fhssvpvragyl fubeg, lbh 
znl or noyr gb erpbire vg hfvat gur Shha'f xrl penpxre. Gb or noyr gb hfr gur penpxre, lbh zhfg 
fgvyy unir lbhe chepunfr pbqr (n 24-npvq frdhrapr). Cyrnfr npgvingr gur penpxre trar, cnffvat vg 
gur chepunfr pbqr, naq nsgre fbzr crevbq bs gvzr vg znl cevag bhg lbhe xrl. Or cercnerq gb jnvg n 
ybat gvzr. Va gur Fybj Mbar, penpxvat n 2-punenpgre xrl znl gnxr zvahgrf, juvyr n 3-punenpgre 
xrl znl gnxr ubhef.

*** Qrgnvyrq qrfpevcgvba bs Zrgubq O (fhowrpg gb AQN) ***

1. Znxr n yvfg bs ahzoref, 0 gb 255.

2. Frg gur pbhagre sbb gb mreb.

3. Yrg one pbhag sebz 0 gb 255 naq rnpu gvzr, nqq gur one'gu ryrzrag bs gur yvfg naq gur one
'gu punenpgre bs gur xrl (jenccvat nebhaq gb gur fgneg bs gur xrl vs arprffnel) gb sbb, naq fjnc 
gur sbb'gu naq one'gu ryrzragf bs gur yvfg.

4. Erfrg sbb naq one gb mreb.

5. Sbe nyy gur qngn lbh jnag gb rapelcg be qrpelcg:

     N. Vapernfr sbb, nqq gb one gur sbb'gu ryrzrag bs gur yvfg, gura fjnc gur sbb'gu naq one'gu 
ryrzragf.

     O. Nqq gubfr gjb ryrzragf, fcyvg gur erfhyg vagb sbhe tebhcf, naq KBE gurz jvgu gur npvqf 
(V = 0, P = 1, S = 2, C = 3).

Nyy nevguzrgvp fubhyq or qbar jvgu 8 fvtavsvpnag npvqf.

暗号化はA→N、B→O・・・のように文字を置き換えているだけです。復号結果です。
Fuuns contain a great deal of proprietary technology. To protect the Intellectual Property 
rights of FuunTech and its stockholders, certain parts of a Fuun's DNA are encrypted using 
one of two cryptographic technologies. This enables such parts to be accessed only by those 
customers who have obtained the necessary access codes.

Method A was used in the past, but it has recently been broken. Indeed, the encryption scheme 
was revealed to be so flawed that it can be broken manually. It is still in use for some parts of 
the system, but FuunTech is migrating away from it. We will not discuss it further.

Method B, a FuunTech trade secret, is significantly more powerful. It requires the customer 
to encode a special sequence of characters, called a "key", into his Fuun's DNA at a specific 
location. If the key is present, the corresponding functionality becomes available. Otherwise, 
Fuun behaviour may range from an error message to violent death.

If you have lost a key, recovery of the key is not generally possible due to the complexity of the 
cryptographic technology. (It is a good idea to write down keys somewhere, maybe even on a yellow 
piece of paper attached to your computing device.) However, if your key is sufficiently short, you 
may be able to recover it using the Fuun's key cracker. To be able to use the cracker, you must 
still have your purchase code (a 24-acid sequence). Please activate the cracker gene, passing it 
the purchase code, and after some period of time it may print out your key. Be prepared to wait a 
long time. In the Slow Zone, cracking a 2-character key may take minutes, while a 3-character 
key may take hours.

*** Detailed description of Method B (subject to NDA) ***

1. Make a list of numbers, 0 to 255.

2. Set the counter foo to zero.

3. Let bar count from 0 to 255 and each time, add the bar'th element of the list and the bar
'th character of the key (wrapping around to the start of the key if necessary) to foo, and swap 
the foo'th and bar'th elements of the list.

4. Reset foo and bar to zero.

5. For all the data you want to encrypt or decrypt:

     A. Increase foo, add to bar the foo'th element of the list, then swap the foo'th and bar'th 
elements.

     B. Add those two elements, split the result into four groups, and XOR them with the acids 
(I = 0, C = 1, F = 2, P = 3).

All arithmetic should be done with 8 significant acids.

purchase codeをcrackerに渡すと鍵を表示してくれると書いてあります。impdoc2に載っているcrackKeyのことです。purchase codeは3つ分かっています(8/24)。
- int24 help-beautiful-numbers_purchase_code
- int24 help-error-correcting-codes_purchase_code
- int24 vmu-code_purchase_code

このドキュメントに載っている暗号アルゴリズムはRC4そのものです。SSLやWEPなんかで使われています(もしかすると過去形?)。

コンピュータの横に張っておくなんてことも書いてあります。stickyの画像のことなんでしょうね。


ICFP2007 (14)

2007-08-28 22:05:47 | ICFPプログラミングコンテスト
ICFP2007 (13) gene tableのpage 15の続きです。

helpシリーズで見忘れていた画像がありました。


その他、気づいたことです。

関数の最初はIIIから始まっています。これはRNA出力コマンドですが、Cから始まる無効なRNAを出力します。このRNAは関数にユニークなようです。また、関数からリターンするときも無効RNA、CFPICFPを出力します。つまりRNAを見れば、どの関数に入ったとか抜けたとかがトレースできるようになっているみたいです。まだ関数とトレース用RNAの対応表は作っていません。

関数の直後にはint24のchecksumが格納されています。これはcheckIntegrityを解析した結果わかったことです。
bool checkIntegrity(int size, int offset){
	int sum1;	//[BZ]
	int sum2;	//[BZ+18]

	sum2 = checksum(offset, size);
	offset += size;
	sum1 = [GZ+offset];
	rc = F;
	if(sum1 == sum2) rc = P;
	return;
}

ちなみにchecksumを求める計算はIを0、Cを1、Fを2、Pを3とみなして、sum = rol(sum, 2) ^ cという操作を関数の最初から最後まで行います。sumの初期値は1です。下のencode( )はICFPを0123に対応させています。rcは戻り値です。
int24 checksum(int24 offset, int24 size)
{
	int24 end = 0;
	int24 sum = 1;
	base t[3];

	if(size > 2500) size = 2500;
	end = offset + size;
	while(end != offset){
		sum = rol(sum, 2) ^ encode([GZ+offset]);
		offset++;
	}
	rc = sum;
}

9/1 追記 sizeの判定が逆でした。最大でも2500バイトしかチェックサムを求めないようです。
関数の最後は固定パターンになっています。
CPPPPPPIICIICIICIICIICIICIICIICIICIICCCFIICIICIFFCPICCFPICICFCPICIICIICIII
何か意味があるのでしょうか?

関数の戻り値のためのスタックは呼び出し側が確保します。通常のパラメータの前に置くので第0パラメータになります。
通常実行時のスタックのレイアウトは以下のようになっています。
[BZ]    ローカル変数
[BZ+??] リターンアドレス(int24が2つ)
[BZ+??] パラメータn
[BZ+??] パラメータn-1
...
[BZ+??] パラメータ1
[BZ+??] 戻り値

戻り値やローカル変数は関数によってはないこともあります。関数を呼び出すときは、パラメータをスタックに積んでから呼び出すので、ローカル変数の前にパラメータが置かれます。このとき、ローカル変数がスタック先頭ではなくなるのでコードが読みずらくなります。

本来の目的であるはずの画像の修復はどうでもよくなってきていて、中身を覗いて遊んでいます。

ICFP2007 (13) gene tableのpage 15

2007-08-25 18:45:19 | ICFPプログラミングコンテスト
ICFP2007 (12) 修復済みgene tableの続きです。

怪しいものを見つけました。gene tableは1/14~14/14です。helpScreenを42にして、ページ番号をAAA_geneTablePageNrに設定すると表示されます。試しに15ページ目を表示してみたところ、右下に今までなかった小さな絵が表示されています。鯨の噴水のさかさまっぽいです。こんな所にまで隠されているんですね。



この絵を表示するRNAはDNA上では圧縮されています。圧縮は20種類あるRNAに0~19の番号をつけて、ひたすら番号を並べています。20が終わりのマークになっています。圧縮しないときのRNAは7文字なのが、圧縮したときは最短が1 (0はP一文字) 最長が6 (19はCIICCP)になります。出現頻度の高い順に番号をつけているっぽいです。圧縮したRNAは、展開するコードと符号表と一緒にDNAの中に埋め込まれています。page 123456のRNA Compression(ICFP 2007(4))とpage 1024のCompressor(ICFP20007(5))に書かれている話です。Compressor自体は自己書き換えしまくりで命令の内部まで書き換えているので、やたら読みずらいコードでした。

printGeneTableに含まれているcompressorは50528バイトで23103個のRNAを表現しています。RNAは1個あたり7文字ですが、DNAに埋め込むときはRNA出力コマンドのIIIに連結してやらないといけないので10バイト必要です。結局231030バイトが50528バイトになったということで、1RNAあたり2.18文字、つまり21.8%に圧縮したことになります。ただしcompressor自身のサイズはテーブルも含めて1028バイトあります。compressorのサイズも含めて考えると51556バイトなので圧縮率は22.3%と多少効率が落ちます。

圧縮ということで思ったのは、prefixとかも既存の部分列の並びみたいな感じで圧縮可能な気がします。

ICFP2007 (12) 修復済みgene table

2007-08-24 02:01:35 | ICFPプログラミングコンテスト
ICFP2007 (11) 隠されていた絵の続きです

gene tableは隠されたDAMAGED ENTRYの所だけあればいいやと思っていましたが、
PASSやFAILと出るintegrity checkをしている所も実は関数っぽいことに気づいたので、やっぱり全部貼っておくことにします。

failになっているエントリーです。壊れているか暗号化されているそうです。
5706a4	001365	caravan				F P
60fea4	001962	cloud				F P
0d985b	000b34	cow-spot-middle			F P
4aa77d	00145c	cow-tail			F P
2bc2cb	00c0eb	help-activating-genes		F P encrypted page 23
0e5d10	007e2d	help-beautiful-numbers		F P encrypted goodVibration = ?
42ccf3	006ed8	help-error-correcting-codes	F P encrypted page 84
613180	0078e9	help-virus			F P corrupted
2c8aff	00345d	motherDuck			F P
206d37	0006e0	sun				F P
6d3fb5	00293f	surfaceTransform		F P
213563	0080f4	vmu-code			F P encrypted giveMeAPresent = "OPE"

リストを眺めていて気になったのは3つあるpurchase code
- int24 help-beautiful-numbers_purchase_code
- int24 help-error-correcting-codes_purchase_code
- int24 vmu-code_purchase_code
と、1つあるreg code
- int9[128] vmuRegCode
です。purchase codeは暗号化されている関数に対応しています。reg codeは前々回のVehicular Morphological Unit(VMU)のregistration codeに関係していそうです。




























ICFP2007 (11) 隠されていた絵

2007-08-22 22:33:16 | ICFPプログラミングコンテスト
ICFP2007 (10) gene tableの修復の続きです。

前回、gene tableを修復して見つかった関数を呼び出してみました。

(50599b 00501b babel-survey)


地球の言語、ってプログラミング言語の名前がいっぱい載っています。知らないものだらけです。

(655a6a 0065e8 help-palindromes)はカタログのpage 1230321と同じでした。

(469865 03f2c2 help-steganography)はカタログのpage 3と同じでした。

(444492 0073b1 majorimp-episode1)です。謎の連載小説(?)です。


(55ac1e 009639 majorimp-episode2)


(278e22 0061bc majorimp-episode125)


(3cbfdb 007b8e majorimp-episode126)


(253694 0095f5 majorimp-episode222)


(6caa97 008be0 majorimp-episode285)


(453c7d 00701f majorimp-episode496)


(6607e7 068c6a selfCheck)はself checkでした。

(1b015a 049cc6 sticky)です。


ディスプレイの横に張ってある紙が怪しいです。「no1@Ax3」と書いてあるように見えます。stickyといのうは付箋のことだそうです。

(3ea79a 00f371 transmission-buffer)です


古代の壁画みたいな絵が描かれています。データを転送しようとしたらエラーがおきたということでしょうか。

ICFP2007 (10) gene tableの修復

2007-08-21 23:14:17 | ICFPプログラミングコンテスト
ICFP2007 (9) mainの逆アセンブルの続きです。

printGeneTable(bool)でgene tableの1/14~14/14が見れます。しかし、DAMAGED ENTRYとなって表示されない部分があります。printGeneTableを解析してみると、最初のスタックフレームを作るところに、geneTableの中身が書かれています。一つのエントリが5個組みで(offset, size, name, flag1, flag2)みたいな感じになっていて、これが400個並んでいます。C風に書くと以下のようになります。
struct {
    int24 offset, size;
    int9[128] name;
    bool flag1, flag2;
} gene_table[400] = {
    {0x000510, 0x00018, "AAA_geneTablePageNr", F, F},
    {0x2ccd88, 0x03c7f0, "M-class-planet", F, P},
    ...

};

flag1がP(真)のときDAMAGED ENTRYと表示されます。flag2が真のときはintegrity checkの対象であることを意味します。

printGeneTable()にパッチを当ててDAMAGED ENTRYを表示しないようにします(隠されたエントリーが表示されます)。方法ですが、GZ+2a9113から3文字分をPICからIPFに書き直します(GZ=352fです)。書き換えるのはIPCでもいいです。これは元々数字の終わりのPと、Pに変換されるICが並んだものでしたが、数字にダミーの最上位ビットIを付け加えて長さ調整して、数字の終わりのPとCに変換されるFの3つに書き換えています。元々はflag1がPならjumpするというコードでしたが、Cならjumpするにしています。flag1はPまたはFなので、Cと一致しないので常に失敗するコードになります。IPCに書き換えたときはflag1とIを比較することになります。
ちなみにFに書き換えると通常表示がDAMAGED ENTRYになってDAMAGED ENTRYが通常表示とちょうど反転するコードになります。パッチはprefixを作らずにファイルからメモリにロードした直後に書き換えています。

結果のpage 42です。integrity checkもPにしてみました。


元のpage 42と違ってPASSの文字やDAMAGED ENTRYがなくなっているのが分かります。


全ページ表示してもいいのですが、面倒なのでDAMAGED ENTRYが通常表示に変わった差分だけ示します。19個あります。
0ee064	0a4e1d	alien-lifeforms		P P
50599b	00501b	babel-survey		P P
0c97b1	000001	cloudy			P F
033964	000001	ducksShown		P F
655a6a	0065e8	help-palindromes	P P
469865	03f2c2	help-steganography	P P
03346a	000001	hillsEnabled		P F
6f8481	001968	majorimp-background	P P
444492	0073b1	majorimp-episode1	P P
278e22	0061bc	majorimp-episode125	P P
3cbfdb	007b8e	majorimp-episode126	P P
55ac1e	009639	majorimp-episode2	P P
253694	0095f5	majorimp-episode222	P P
6caa97	008be0	majorimp-episode285	P P
453c7d	00701f	majorimp-episode496	P P
6607e7	068c6a	selfCheck		P P
0c15dd	002f64	shoutOut		P F
1b015a	049cc6	sticky			P P
3ea79a	00f371	transmission-buffer	P P

flagっぽいのが3つと残りは関数のようです。

一番最初のalien-lifeformsを呼び出してみました。


問題の作成チームでしょうか?みんなでprefixらしきものをもっています。
IIPIFFCPICFIICIPCCICCPIICIPPPCFFCFCCFICFFFCFCCFICFCFCCCCFICIIC
(  ?  IFP C)  ! 1b    $  #0  ICCICIICP CCCICIICP CICIIIICP $

IFPCというマーカーの後の27byteを書き換えています。書き換えデータはint9が3つで0x96, 0x97, 0x85です。Intergalactic codeの文字列に直すと'O' 'P' 'E'です。IFPCマーカーはgiveMeAPresent(GZ+5d)の直前にあります。つまり、このコードはgiveMeAPresentの先頭に"OPE"を設定していることになります。実際に実行してみると、復号されたvmu_code()が表示されます(前回のmain逆アセンブルの最初の方のコード)。ちなみにgiveMeAPresentは最初128個の0xffが書かれているので文字列の長さは3文字ということになります。



またもや謎のregistration codeなるものが表示されました。

さすが、隠されているだけあって、暗号の鍵があったりします。
なんか情報に惑わされていて迷路に迷い込んだような気分です。疲れてきたので続きます。



ICFP2007 (9) mainの逆アセンブル

2007-08-20 00:45:19 | ICFPプログラミングコンテスト
ICFP2007 (8) FuunDocの続きです。

mainを手動で逆コンパイルしてみた結果です。間違いはあると思いますが、たぶんこんな感じです。

最初にスタックフレームを作っているのに気づいたのでC風に書いてみました。リターンする直前にスタックフレームを解放しています。

関数呼び出しのパラメータもC風で、呼び出す直前にスタックに積んでいます。最初のパラメータからスタックに積むので、メモリ上では逆順になってBZの先頭が最終パラメータになります。パラメータのスタックは関数側で解放してくれるみたいで、呼び出し側は何もしていません。これはCとは違います。

とにかく、追っかけるのがやたら大変です。普通のプロセッサと違って、現在実行している命令が、新たに命令を生成して、それを実行したりします。要は自己書き換えする命令が存在します。さらにそれが2段階、3段階と変化しまくったりします。その場合、templateの中に実行される命令が書かれています。また、命令の直後にデータがあったりとか、次の命令の直後にデータを挿入したりと、もうすごいことになっています。ある程度パターンは決まっているようなので、うまくパターンマッチングすると高機能な逆アセンブラが作れるかもしれませんが、そこまではいっていません。

mainを(半手動)逆アセンブルして分かったことは4つです。
(1) giveMeAPresentに正しいパスワードを入れるとvmu_code()が実行できる
(2) goodVibrationsに正しい1バイトの数値を入れるとhelp_beautiful_numbers()が実行できる
(3) 未発見のページp.1230321とp.180878があった
(4) printGeneTable(bool)はパラメータとしてboolを受け取る。mainではFを渡している

goodVibrationsは256通りなので探索可能な範囲です。
printGeneTableのパラメータはintegrity checkでした(impdocにも書いてあります)。mainの中のFを直接Pに書き換えようとしましたが、templateの中ではFはC、PはICなので長さが合わず、直接書き換えは断念しました。
63bb22の命令コードは何をしているのかまだ分かっていません。Super gene adaptation関連みたいです。

C風に(半手動)逆コンパイルした結果
extern bool doSelfCheck;            // [GZ+000058 size 000001]
extern int9[128] giveMeAPresent;    // [GZ+00005d size 000480]
extern int24 helpScreen;            // [GZ+0004e4 size 000018]
extern int9 goodVibrations;         // [GZ+000501 size 000009]
extern font fontTable_Tempus_Small; // [GZ+07b7cc size 002400]

// [GZ+63a4fd size 01303b]
main()
{
    int9  c = 0;      // [BZ    :BZ+8  ]
    int24 i = 0;      // [BZ+9  :BZ+20 ]
    int9  s[128] = {  // [BZ+21 :BZ+4a0]
          0xd8, 0xc6, 0xe6, 0xce, 0xda, 0xca, 0xe7, 0xe7, 0xff
    };
    int24 fp = 0;     // [BZ+4a1:BZ+4b8]
    int24 fn = 0;     // [BZ+4b9:BZ+4d0]

    if(doSelfCheck == P){
        call(0x6607e7, 0x68c6a); //self check
    } else if(giveMeAPresent != 255){
        fp = vmu_code;
        fn = sizeof(vmu_code);
        crypt(giveMeAPresent, fp, fn);
        vmu_code();
        return;
    } else if(goodVibrations != 0){
        while(i != 8){ // generate passcode from goodVibrations
            s[i] += goodVibrations
            i++;
        }
        drawString(fontTable_Tempus_Small, 10, 10, s);
        makeDarkness();
        fp = help_beautiful_numbers;
        fn = sizeof(help_beautiful_numbers);
        crypt(s, fp, fn);
        help_beautiful_numbers();
        return;
    }

    // [GZ+63bb22 size 16d] under analysis, this code calls subroutine at 6fd9b6

    switch(helpScreen)
    case 0:
        scenario();
        anticompressant();
        break;
    case 1:       help_intro(); break;
    case 2:       help_integer_encoding(); break;
    case 1337:    help_catalog_page(); break;
    case 1729:    help_fuun_structure(); break;
    case 23:      help_activating_genes(); break; // encrypted
    case 42:      printGeneTable(F); break;
    case 112:     most_wanted(); break;
    case 10646:   printCharSet(); break;
    case 3:       call(0x469865, 0x3f2c2); break; // show "Steganography"
    case 84:      help_error_corecting_codes(); break; // encrypted
    case 8128:    help_beautiful_numbers(); break;
    case 1230321: call(0x655a6a, 0x65e8); break; // show "Palindromes"
    case 2181889: help_undocumented_rna(); break;
    case 180878;
        // show "Synthesis of complex structures (2)" long code here
        break;
    case 5:       help_lsystems(); break;
    case 8:       help_encodings(); break;
    case 4405829: help_fuun_security(); break;
    case 123456:  help_compression_rna(); break;
    case 85:      help_patching_dna(); break;
    case 100:     help_virus(); break;
    case 9:       help_adaptive_genes(); break;
    case 1024:
        // show "Compressor" long code here
        break;
    default:
        fatalError("The Field Repair Manual page you tried to access does not exist.");
    }
    return;
}


新たに見つかったカタログページです。mainから呼ばれている、つまりページ番号がついているものは暗号化されている2つ以外は見れたはずです。
(page 1230321)


(page 180878)


カタログページはhelpからはじまる関数を呼び出して表示しています。help-initial-condはページ番号がついていないようです。直接呼び出して表示してみました。
(page ?? help-initial-cond)


super adaptive gene関連でしょうか?初期値と書いてあるので63bb22の命令コードと対応しているのかもしれません。

ICFP2007 (6) gene table

2007-08-17 00:03:27 | ICFPプログラミングコンテスト
ICFP2007 (5) 修理ガイド(3)の続きです。

修理ガイドのpage 42はgene tableです。AAA_Gene_TablePageNrにページ番号を入れてやると14ページのうちの他のページも見れるようになります。0が1ページ、1が2ページと1少ない値を入れます。

prefixです。長いので途中で改行しました。
IIPIFFCPICFPPICIICIPIIICCPIIPIFFCPICPCICIICIPIIICCPIIC
IPPPCFCFCFCCCCCCCCCCCCCCCCCICIPPCPCCCFCCCCCCCCCCCCCCCCCCCICIIC
カタログインデックス(GZ+4e4)の直前にはIFPCFFPマーカーが、AAA_Gene_TablePageNr(GZ+510)の前にはIFPFIPマーカーがあることを利用しています。patternが(?IFPCFFP)!24(?IFPFIP)!24でtemplateが#0int24(カタログインデックス)#1int24(ページ番号)です。

色々とおもしろそうな名前の関数(?)がいっぱいあります。





























ICFP2007 (5) 修理ガイド(3)

2007-08-16 23:04:09 | ICFPプログラミングコンテスト
ICFP2007 (4) 修理ガイド(2)の続きです。

カタログには載っていないページです。

(page 3 help_steganography)


画像の中にメッセージを隠すとはなかなか意味深です。この画像にも何か隠されているのでしょうか?

(page 9 help_adaptive_genes)


さて、何のことでしょう?gene tableにはactivateAdaptationTreeという名前が載っています。

(page 100 help_virus)


ウイルスにやられたのでしょうか。フォントを変えれば読めるようになるかもしれません。

(page 1024)


画像圧縮ルーチンに渡すデータ構造?

とりあえず総当り的に探して見つかったのはこのくらいです。探していない範囲に他のページがあるかもしれません。

ICFP2007 (4) 修理ガイド(2)

2007-08-15 23:53:54 | ICFPプログラミングコンテスト
ICFP2007 (3) 修理ガイド(1)の続きです。

修理ガイドのカタログ(ICFP2007 (2) 見つけた画像の一番下)に従ってページを見ていきます。

(page 85 help_patching_dna)


blue zoneのスタックにデータを積む方法やgreen zone内のサブルーチンを呼び出す方法が書いてあります。green zone内のサブルーチンはgreen zoneの直前に置かれることを前提にしているので、ユーザーのprefixの前とかに置いても正しく動作しません。

新たなマーカーが2つ登場しています。IFPICFPPCCCはサブルーチン呼び出し用ルーチンを探すためのマーカーで、IFPICPPCFIPPはblue zoneを探すためのマーカーです。
blue zone markerはGZ+729594で見つかります(GZ+ほにゃはgreen zoneからのオフセットの意味)。この直後のGZ+7295a1からblue zoneが開始します。
サブルーチン呼び出し用ルーチンのマーカーは一つ目がGZ+24344Bで二つ目がGZ+25357dで見つかります。このルーチンの開始番地は最初のマーカーの後なのでGZ+253456になります。このあたりからオチコボレはじめています。

page 84は暗号化されているそうで見れませんでした。

(page 2181889 help_undocumented_rna)


無効RNAのことが書いてあります。morphing processって何?

(page 5 help_lsystems)


Lシステムというのがあるみたいです。見た感じ再帰的に絵を描くものみたいです。画像の修復に使うのではないでしょうか。

(page 4405829 help_fuun_security)


なにやら暗号化されているようです。雰囲気的に原文は英語で単換字式暗号っぽいです。
英語で1文字の単語はaなのでa→nに変換されているっぽいです。そうすると下の方の5.の次の行はA.になるので、その次の行はB.でしょうか。となるとb→oになっています。3.の行にある0 gb 255はたぶんtoでしょう(t→g, o→b)。3番目のパラグラフのカッコ内の24-npvqはたぶん24-acidなのでc→p, i→v, d→qが分かります。NqqはAddなのでNyyはAから始まる3文字だとAllです(l→y)。sbbは?ooですがたぶんfoo、oneはba?ですがたぶんbarです(f→s, r→e)。よく出てくるgur(t??)をtheに決め打ちにします(h→u, e→r)。対応表を作ってみると
a→n
b→o
c→p
d→q
e→r
f→s
・・・
というわけでシーザー暗号でした。平文に復号するのは面倒そうです。

(page 123456 help_compression_rna)


RNAの圧縮について書いてあります。

画像を貼るのに疲れてきたのでこのくらいにしておきます。この次はカタログページに載っていないページをいくつか見つけたので、それを載せます(p.3 p.100 p.1024等)。いっぱい情報がはいりすぎで、混乱気味です。

ICFP2007 (3) 修理ガイド(1)

2007-08-15 21:51:28 | ICFPプログラミングコンテスト
ICFP2007 (2) 見つけた画像の続きです。

前回の修理ガイドのカタログに従ってページを見ていきます。

(page 1729 help_fuun_structure)


DNA自体は3つのエリアに別れていて、先頭のred zoneには現在実行しているコード片が置かれていて、red zoneに置かれるコード片はgreen zoneからコピーされてくることや、blue zoneが作業域として使われることなんかが書いてあります。blue zoneは実際はスタックになっています。

(page 8 help_encodings)


真理値はPとFとか色々書いてあります。負の数は1の補数じゃない?文字は9acidと書いてありますが、数値は最後にPがつくので実際は8bitです。ここまでに色々なフォントが出てきていますが、画像として表示しているのではなく、フォントテーブルと文字列といった形で表示しているみたいです。

self testをしたり、空が青くなるprefixではF→PやP→Fという書き換えをしていましたが、これは真を偽にしたりといった真理値の書き換えだったということです。

次のpage 23 Activating Genesは暗号化されているそうなので中身は見れませんでした。
(page 23 help_activating_genes)

(page 42 printGeneTable)


一番左の列がgreen zoneからのオフセットで、二番目の列が長さ、三番目の列が名前です。14pageのうちの1page目ということですが、他のページも見れるのでしょうか?試しにpage 43を見てみましたが駄目でした。

page 43の画像


green zoneの先頭にIFPICFPPCFFPPというマーカー(?)があることも分かります。検索してみると先頭から13615バイト目からの13バイトで見つかります。この値はマーカーとしては使えません。IFPICFPPCFFPPの先頭のIのあるところがgreen zoneの先頭番地だからです。

ダメージを受けたエントリー(damaged entry)という表示は、表示の上や下のエントリーがダメージを受けているという意味ではなくて、本来ならそこに表示すべき値がダメージを受けていて表示できないという意味です。

integrity checkはよく分かりません。一般的には壊れているかどうかハッシュ値とかで検査するという意味のはずです。

長さが短いのはグローバル変数っぽいです。int24とかint9とか書いてあります。int9は8bit、int24は23bit?

一番最初のAAA_geneTablePageNrは0x510から24バイトです。前回のダンプの範囲なので見てみます。
0004d0  CCCPCCCCCCCCPIFP
0004e0  CFFPIIIIIIIIIIII
0004f0  IIIIIIIIIIIPIFPF
000500  PIIIIIIIIPIFPFIP
000510  IIIIIIIIIIIIIIII
000520  IIIIIIIPCCCCCCCC

直前にIFPFIPマーカーがついていて、値が0になっています。前回あてずっぽうにマーカーでないかと思ったものは実際にマーカーとして使えそうです。名前からすると、ページ番号なので14ページの他のページが見れるかもしれません(後回し)。

(page 112 most_wanted)


イメージというか画像も貼れるんですね。原理的にはできることは分かりますがなんかすごいです。これはジョークでしょうか。一番下の外人さんは誰?

(page 10646 printCharSet)


page 8 encodingで触れられていた文字セットです。って、文字が全部四角になっています。昔なつかしいEBCDICを寝かせています。これを見てピーンとくるのはかなり年配の人ってこと? (分かったので年寄りかも・・・)

長くなってきたので続きます。

ICFP2007 (2) 見つけた画像

2007-08-15 20:20:38 | ICFPプログラミングコンテスト
ICFP2007 (1)の続きです。

RNAは1つが7文字で表されるコマンドで、このコマンドがひたすら並んでいます。パラメータとかはないのでタートルグラフィックみたいな感じです。色はバケツにためた色の平均になります。バケツに赤を入れるとか青を入れるといったコマンドがあります。描画コマンド自体は直線と塗りつぶしだけです。色はRGB以外にTransparency(透明度?)が画素ごとにあって、画像を重ね合わせるときの比率になります。画素数は600x600で作業用に9個まで同サイズの画像を作って、後で重ね合わせることができます。コマンド自体は20種類なのですが、RNAには無効なコマンドがたくさん含まれています。処理するときは単純に無視するだけですが、何かのマーカーになっているのかもしれません。

画像表示のデバッグの時に見つけた画像です。最初に一瞬だけ表示されます。左上にprefixらしきものが見えます。


IIPIFFCPICFPPICIICCIICIPPPFIICと書いてあります。これはDNAからIFPCFFPというマーカーを探して、マーカーに続くIをCに置き換えています。ドキュメントの記法に従えばpatternが(?IFPCFFP)I、templateが#0,0Cです(#はドキュメントのn_lの代わりです)。IFPCFFP自体はendo.dnaの先頭から14860バイト目にあるので14867バイト目を書き換えていることになります。IFPCFFPマーカーの直後はIが23個並んでPが1個あります。

このprefixを連結してみると次の画像が得られました。
(page 1 help_intro)


ここにもprefixが2つあります。IIPIFFCPICFPPICIICCCIICPPPCFIICとIIPIFFCPICPCIICICIICIPPPPIICです。最初のはIFPCFFPマーカーを探して直後のIIをICにしています。マーカーは上のと一緒です。直後の23個のIのうちどれかをCにすると違うことがおきるようです。後のprefixはIFPFIマーカー直後のPをFに書き換えています。新たなマーカーです。フラグ(?)を書き換えると色々なことがおきるということでしょうか?

とりあえず最初の方をつけてみたときの画像です。
(page 2 help_integer_encoding)


また、新たな画像が出ました。こうやってマーカーとかヒントを探していくアドベンチャーゲームみたいなものなんでしょうか?でも、元々のコンテストの目的の画像の修復とはどんな関係にあるんでしょう。

後の方のprefixをつけてみたときの画像です。


問題の誤り入り画像より空というか全体が明るくなっています。とりあえず、こっちの方はほっておいてrepair guideの方を追っかけてみます。もしかすると、アドベンチャーゲームで言うと選択ミス?罠にはまったかもしれません。このあたりはたぶんチュートリアルというか操作の基本になれる例題と割り切ります。

この段階でマーカーは3つ分かっています。
(1) IFPP 直後をF→Pでセルフテスト
(2) IFPCFFP 直後をI→Cでrepair guideの画面(上から2番目)、直後をII→ICでrepair guide navigationの画面(上から3番目)
(3) IFPFI 直後をP→Fで青空画面(上から4番目)

repair guide navigation画面でexisting repair guide prefixと言っているのは(2)のIFPCFFPのことだと思われます。また、2進数に最下位ビットからエンコードして0をI、1をCで置き換えるということも書いてあります。IをCに書き換えているのでrepair guideはpage 1、IIをICに置き換えているのでrepair guide navigationはpage 2ということになります。そして、カタログページのインデックスが1337と書いてあります。

ちょっと寄り道。既存のマーカーは(といっても3つだけだけど)全てIFPから始まっています。patternだとマーカーの検索はIFから始まることになっていて、3文字目はは何でもよくて4文字目以降に探索するマーカーを書くことになっています。見た感じ、3文字目としてはFが使われているみたいです。templateだとIFはIPと書いてもいいことになっているけど、たいていIPが使われています。何が言いたいかというと、もしかするとpatternとtemplateにはIFPというのが現れないからIFPがマーカーの接頭辞として使われているのかもしれない、ということです。それならIFPを検索すればマーカーの一覧が作れるかもしれないとふと思いました。

試しにダンプしてみるとマーカーっぽいものが見つかります
0004d0  CCCPCCCCCCCCPIFP
0004e0  CFFPIIIIIIIIIIII
0004f0  IIIIIIIIIIIPIFPF
000500  PIIIIIIIIPIFPFIP
000510  IIIIIIIIIIIIIIII
000520  IIIIIIIPCCCCCCCC

0004dd-0004e3にマーカーIFPCFFP (既出(2))
0004fc-000500にマーカーIFPFP (未知、IFPFPIとかかもしれない)
00050a-00050eにマーカーIFPFI (既出(3))
(アドレスはGreenZone起点)

さて、1337は16進で0x539最下位から2進でエンコードすると1001 1100 101、0→I, 1→CにするとCIIC CCII CICになります。page1やpage2を表示したprefixを真似してIFPCFFPマーカーの直後の11個のIをCIICCCIICICに書き換えるprefixを作ります。
IIPIFFCPICFPPICIICCCCCCCCCCCCIICIPPPFCCFFFCCFCFIICです。patternとtemplateの解釈時に文字変換が行われるのでI→C、C→Fになります。

作ったprefixを連結した画像です。
(page 1337 help_catalog_page)


さらにいっぱいページが見れそうです。下から2番目の「究極の答え」というのはSFで有名な42のことでしょうか。長くなってきたので続きます。