So-net無料ブログ作成
検索選択

バーナム暗号 [日誌]

昨日アップしたmigt(仮)ですが、score.iniというファイルを開けばわかるとおり、ハイスコアデータがそのまま保存されています。もっとも、スコアとチェックサムの二つが保存されているので、書き換えたところで俺TUEEEEEできるわけではないんですが、この不正チェックを破るのは、ちょっと頭を使えば簡単だったりします。ネタ晴らしすると、昔作ったゲームのハイスコアルーチンを全て書き換える必要がでるので内緒にしておきますが!!

ただまあ情報理論を学ぶ人間としては、やはりもう少し手の込んだ物を作成したくなるのが人情と言うもので、ちょいと暗号化なる物をやってみました。理系の人間だったら、数学チックな分野に走りたくなりますよね!? というか、俺はただ単に、暗号技術入門(結城 浩 著)を読んでいたら、実際に簡単な物を実装してみたくなっただけです!!

いろいろある暗号化の中で真っ先に思いついたのが、最も簡単な対称鍵暗号の一つである、バーナム暗号と呼ばれる物。詳しい説明は、ググればでるはずなので省略するけど、要するに平文(暗号化したい文字列)に、ランダムのビット列を重ねて暗号化させるという技術。

たとえばスコアが12500点だとして、これを暗号化させたいときはどうするかというと、まずこれを2進数に変換して(しなくてもいいけどわかりやすくするために)

11000011010100   ・・・・ (1)

次に、同じ長さの乱数列を用意して、

10101110010110   ・・・・ (2)

これの和を取ります。和を取ると言っても、ただの足し算じゃなくてXORという排他的論理和ってやつですね。詳しくはググっt(略

(1) XOR (2) を計算すると

01101101000010

で、これを10進数、つまり6978に直して出力。終了。

また復号化はこれの逆をやれば良くて、保存してた6978を同じように2進数に変換。

01101101000010

これと(2)のXORを取ると

11000011010100

を得ることができて、なんとこれが12500なんですよ!! 凄いですねぇ!! そうでもないですか、そうですね。当たり前ですね(´¬`)



とりあえずこれを実装してみたんですが、さっそく欠点を発見...というのも、同じ長さの乱数列というものをどうすればいいのかを、全然考えてなかったんですよ。乱数列とはいえ、暗号化も復号化も同じ乱数列でないとダメなので、ここで言う(2)をどこかに保存しておく必要が出てくるんですね。

ここで馬鹿正直に、score.iniに一緒に入れておくと、なんつーか鍵と鍵穴をセットで置いておくようなもので全然意味がないし、プログラムの中に定数としておいておくのも芸がない...というか定数だと、やはり推測しようと思えばできそうなので(たぶんできる人なら速攻でできそう)、ここで考えたのが、最初に出したチェックサムの値を使うという考え。

チェックサムというのはそもそもなにかというと、ハイスコアが書き換えられたかどうかを確認するため、ハイスコアの数値にある計算を施して小さな数字を計算した結果なんですよ。ハイスコアとチェックサムの値は多対一に対応してるとでも言えばよいのかな?

あるハイスコアの値は、必ず同じチェックサムを出力することに着目すれば、これを使って乱数列を生成すればよいと言うことがわかりますよね。チェックサムの値も、score.iniに書かれているけど、この値から乱数列を推測するには、その乱数を計算するアルゴリズムが必要となるわけで、さっきの生の値をそのまま置いておくよりかは幾分、信頼性が増しそうじゃないですか。いやまあ、法則性がある時点で全然ダメダメなんですがorz

というわけでやってみました...おお、ぱっと見じゃわからない暗号化ができたぞ(゚∀゚)

つーか、まともに不正チェックするんだったら、こんなおもちゃみたいな暗号化だけじゃなくて、もっといろいろと導入していかないとダメなんだろうな。ランキングを登録するときに、実行ファイルの改ざんがあるかどうか確かめるためにMD5を調べたり、あとはメモリが途中で書き換えられてないかどうかチェックしたり...

ああ、めんどくさいからもういいや('A`)



例のマウスゲーですが、明日、もう一度バージョンアップ版をアップする予定です。


nice!(0)  コメント(8)  トラックバック(0) 
共通テーマ:日記・雑感

nice! 0

コメント 8

ていこく

バーナム暗号というのですか。
XORによる暗号化/復号化は今まで何十度もお世話になっているのですが、名前は初めて聞きました。
鍵となる数値は定数では確かに危ないので何かしらの計算結果で鍵を変えたほうがいいですよね。
私の場合は適当な範囲の乱数(0以外)を鍵として暗号に組み込む方法を使っていたりします(無論そのままの数ではない)
本格的に不正チェックするのであればこれではとても足りないと思いますが、簡易的なものであればまぁこれでもいいかな、と。
文章の暗号化にもバーナム暗号を使っております。ファイルサイズが2~4倍に膨れ上がってしまうのが欠点ですが(汗)
by ていこく (2006-01-11 12:35) 

iwasaki_p

>鍵となる数値は定数では確かに危ないので
ですねぇ。数値を少しずつずらしていって、そのデータを解析すれば、もしかしたら破られる可能性もあるし、exeファイルの方を解析されたらひとたまりもないかもしれないし...

>簡易的なものであればまぁこれでもいいかな
文章を軽く暗号化する程度なら、まったく問題ないと思いますよ。昔のベーマガのプログラムだったら、十分合格点じゃないかな?
MSXのプログラムなんかだと、エンディングの文章が偶数と奇数番が入れ替わってるだけみたいなのもあったぐらいなので

例:クリアおめでとうっ! → リクおアでめうと!っ

はじめてこれを解読できたときは、なんか無性にうれしかった覚えがありますwww


>ファイルサイズが2~4倍
そこで、ある初期値だけを保存して、そこから推測できないような疑似乱数を生成すると良いと思いますよ!!
性能がよい乱数生成アルゴリズムなら、周期性もそう簡単には見つけられないと思うので、うまく使えば劇的にファイルサイズを減らせると思うんですが。

しかしこの乱数生成アルゴリズムというのがムズイんだこれまた|ω・)
by iwasaki_p (2006-01-12 01:58) 

XRL

 私が以前実際に使ったのは実データの前後や途中に数十バイト~数Kバイトほどの無意味なダミーデータを埋め込んでどこに何が格納されているかを攪乱し xorと rotateで暗号化を行っていました。
 その xorする値や rotateのビット数はキーやオリジナルデータのチェックサムやその直前までのデータやらを元に動的に算出するものにしてまいた。
 これでも完全な不正チェックにはならないのですが、一般向けなら十分だと思っています。

> exeファイルの方を解析
 これをされると辛いですね。
 今は実行時にプログラムを展開する方式でも解析されてしまうんでしたっけ?
 まぁ、有名なデバッガが起動されているかどうかを検出すれば対処できなくもないですけど・・・。

> 性能がよい乱数生成アルゴリズム
 boost::random系は駄目ですか?
by XRL (2006-01-12 22:55) 

iwasaki_p

>これでも完全な不正チェックにはならないのですが
たぶん、個人が趣味で作っているようなフリーソフトのゲーム程度なら十分だと思いますね。シェアウェアのパスワード認証部分あたりだと、もうちょい考えなくてはダメかもしれませんが。

>有名なデバッガが起動されているかどうか
自作の解析ツールでも作られてない限り、これが手っ取り早そうですねww
恐らくそういうツールを持っているような人間ならば、俺があれこれ考えたところで無駄なような気がします|ω・)

>boost::random系は駄目ですか?
おおっと、boostのことをすっかり忘れてました!
やね本2などでも紹介されていたので、一度使ってみようと思いつつ、まだノータッチだったので、これを機にちょいといじくってみようかな。

ちなみになんであそこで、アルゴリズムの話になったかというと、いま自分の研究分野が、乱数生成や符号化理論あたりなので、どうしても自作の方へ偏ってしまうんですね(ノ∀`)
by iwasaki_p (2006-01-14 01:45) 

よせやい、やめて〜

小生のソフトではバーナムを変形して使っています。擬似乱数によるxorとmod 256の演算です。これらを組み合わせた事で線形解読、差分解読に耐えることができました。バーナムは基本的には等長なのでファイル長が膨れ上がるのは本質的ではない何かがあるのだと思います。小生のソフトは暗号データにヘッダを儲けキーの一部を隠していますから冗長になっていますがね、。小生の暗号 CryptOne と申します。宜しく願います。
by よせやい、やめて〜 (2010-07-31 17:54) 

Iwasaki++

数年前の記事になってますが、コメントありがとうございます!

なるほど、ただ単にxorかけるだけだけではなく、それにmodを取ればより複雑度は増加しそうですね。そして、暗号データにヘッダを用意すれば、冗長になる反面、鍵穴の横に鍵を置くような事にもならず、弱点がかなり克服されていると思います。

今後もよろしくお願いします!
by Iwasaki++ (2010-08-01 23:54) 

よせやい、やめて〜

CryptOne は暗号サーバと公開鍵サーバで構成されます。これらサーバは開発できたのですが、メールクライアントと組み合わせて「書留電子メール」クライアントができないのかなと思っています。しかし、メールソフトの開発が情報の壁に打ち当たり一向に進みません。誰かメールクライアントの開発者でCryptOneを使ってみようと思われる方は居ませんか。居ないだろうな。
by よせやい、やめて〜 (2011-09-27 12:14) 

よせやい、やめて~

CryptOne の開発は終了しました。Linux 版は6.01でMacOSX 版は7.02です。特長は暗号アルゴリズムにストリームの転置が入っていることです。最大の転置サイズは1024バイト、8192ビットです。Linuxでは最大転置サイズが512バイトです。巷で利用できる暗号で転置のアルゴリズムがストリームで入っているもの CryptOne 以外にあるのでしょうか。復号アルゴリズムを利用しないと大変な時間と労力を必要としますが、暗号は作るのは簡単ですが、復号操作よりレスポンスの良い解読法を見つけるには苦労する事でしょう。
by よせやい、やめて~ (2015-04-11 11:28) 

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

この記事のトラックバックURL:
※言及リンクのないトラックバックは受信されません。
メッセージを送る