自堕落な技術者の日記

NISTのSHA-3 HASHコンペのメーリングリストでJeff JohnsonさんがSHA-3候補のハッシュアルゴリズムとRSA署名アルゴリズムのオブジェクト識別子(OID)をテンポラリでもいいから割り当ててという発言がありました。

同じような事を考えてくれる人がいてよかったですが、テンポラリはいただけない。混乱するだけだから、、、、、候補になった奴は正式にNISTでOID振っちゃっていいんじゃないですかね？

大御所Paul Hoffmanさんは、「評価も終わってないのに使うつもり？」みたいな話をしていますが、コンペで一等賞になろうがなるまいが一部のアルゴリズムは使う人（国）が出てくるでしょうから、多分お金のかからないNIST内の決め事だけの話だと思うので先に割り当てといていいのではと思います。

例えばRound1候補に "1.3.14.3.2.777.1" から "1.3.14.3.2.777.51" 割り当てて
その中の一つ "1.3.14.3.2.777.7" が優勝して他を殆ど捨てることになっても大した問題じゃない気がするんですが、どうですかね、、、、、「13」は嫌だ、とか、後になってこのOIDにしたせいで不具合が多いんじゃないかという都市伝説が生まれるとかそういうのはあるのかな？

実際に署名やMACなどハッシュアプリケーションとして使ってみないとわからない問題も出てくるんじゃないかと、、、、、

kurushima @ 自堕落な技術者のヰキ(公開版) - Hash/次世代SHA3ハッシュアルゴリズム

Engineering comparison of SHA-3 candidates / SHA3参加アルゴリズムの比較調査
http://www.skein-hash.info/sha3-engineering
Classification of the SHA-3 Candidates / SHA3参加アルゴリズム比較の論文
http://www.uni-weimar.de/cms/fileadmin/medien/medsicherheit/Research/SHA3/Classification_of_the_SHA-3_Candidates.pdf

SHA-3コンペまとめサイトでETSI ESI副議長のErnstさんに教わったリンクを追加しときました、、、、

クロックサイクルで少ない時間で速い方が良いみたいな話になっているようですが、、、少ない時間で処理できるほど、その分衝突が見つけやすくなったってことにならないんですかね？？？（素人ですみません、、、）

PDFとかも最新版ではパスワードによる暗号化機能でAESを使うようになって、前よりも解くスピードが速くなっちゃったからPDF password reminderみたいなブルートフォースによるパスワード解析ソフトでも（何も手を加えていないのに）従来手法のままで解析スピードが格段にアップしちゃったらしいですよね、、、、、

NIST.gov - Computer Security Division - Computer Security Resource Center

The First SHA-3 Candidate Conference will be held at K.U. Leuven, Belgium, following the 16th International Workshop on Fast Software Encryption (FSE 2009) which is scheduled for February 22-25, 2009. The purpose of the SHA-3 Conference is to allow the submitters of the first round candidates to present their algorithms, and for NIST to discuss the way forward with the competition.

来年2009年2月22〜25日、ベルギーのルーヴェンでNISTのSHA3ハッシュアルゴリズムのコンペティションの候補の会議が行われるそうな、、、、、

ルーヴェン(Leuven)ってどこ？

＜追記＞
ほほ〜〜っ、ブリュッセルの東、大陸側ですな、、、距離的に電車で２０〜３０分ってとこでしょうか、、、、、


View Larger Map

Schneier.com

Skein is a new family of cryptographic hash functions. Its design combines speed, security, simplicity, and a great deal of flexibility in a modular package that is easy to analyze.

米国NISTの次世代ハッシュアルゴリズムSHA3のコンペティションにセキュリティ業界では有名なBruce SchneierのチームはSkeinというハッシュアルゴリズムで参加しており、論文、実装、テストベクターなどがサイトでダウンロードできるようになっています。実装がシンプルでSHA512よりも倍は速いぜ！！と書いてあります。

早速これでちょっと遊んでみたいと思います。

ZIPアーカイブ(Skein_NIST_CD_111008.zip)をダウンロードし解凍してみると、Makefileも見事に無く何から手をつけていいのかわかりません。簡単なドキュメントもあるみたいですがあまりためになりません。（＾＾；とりあえずソースを見てみることにします。

Skeinのソースコード解析

とりあえず動かすのに最適化されたコードを見てもしょうがないので覗いてみると NIST/CD/KAT_MCT/src が今回のコンペに参加するためのコードのようです。重要なファイルや関数の簡単な説明は以下のようになります。

■genKAT.c - AHSコンペ用テスト実装

　main() - 全テスト

　　genShortMsg(ハッシュビット長(={224,256,384,512}))



■SHA3api_ref.c - AHSコンペ用のハッシュ関数のラッパー

　Init()

　Update()

　Final()

　Hash() - Init,Update,Finalの一発実行



■skein.c リファレンス実装のSkein関数

　Skein_256_Init()

　Skein_512_Init()

　Skein1024_Init()

　Skein_256_Update()

　Skein_512_Update()

　Skein1024_Update()

　Skein_256_Final()

　Skein_512_Final()

　Skein1024_Final()

　※メッセージ認証MAC用

　Skein_256_InitExt()

　Skein_512_InitExt()

　Skein1024_InitExt()

　※末尾パディング付きFinal

　Skein_256_Final_Pad()

　Skein_512_Final_Pad()

　Skein1024_Final_Pad()

　※処理状態出力用

　Skein_256_Output()

　Skein_512_Output()

　Skein1024_Output()

ハッシュ処理のプログラムを書いたことのある方はご存知と思いますが、一般にハッシュ関数は少しずつバイトの塊単位でハッシュを計算できるように

init - ハッシュ計算の初期化

update - バイトの塊単位でハッシュ計算するよう流し込む

　　　　　必要に応じ適当な単位で分割しupdateを何回も行う

final or digest - 最後のバイトの塊を流し込み最終的な計算をしハッシュ取得

これはJava JCEでもOpenSSLでもCryptoAPIでも同じようなものです。

重要なデータ型としてはハッシュ対象となるデータやハッシュ値を格納するためのバイト配列としてBitSequence型というのがあります。これはマシンアーキテクチャ、OS、コンパイラに依存しますが概ねこんな感じです。

BitSequence型→u08b_t型→uint_8t型→unsigned char

あとユーティリティ関数としてこんなのがあります。

ReadHex(+FIN, +MsgBuf, +BufLen, "foo = ")

　- ファイルポインタより16進数表現のバイトの読み込み

Hash(+hashbitlen, +Msg, +msglen, -MD) - ハッシュ計算

fprintBstr(+FOUT, "foo = ", +byte, +byteLen) - バイト列16進数出力

genShortMsg()関数の中の変数で覚えておくとよいのはこんだけ

hashbitlen: ハッシュビット長

msglen: メッセージビット長

msgbytelen: メッセージバイト長

Msg: メッセージバイト

MD: ハッシュ計算結果バイト

テスト実装とテストベクター

テストを行う実装はNIST/CD/KAT_MCT/srcにあるgenKATとなりますが、これはカレントディレクトリにあるテスト用のメッセージファイルを読み込み、ファイル中の全てのメッセージに対しハッシュ値の計算結果がそれぞれ224、256、384、512バイトとなるようなSkeinによるハッシュ計算を行い結果をそれぞれバイト毎に別ファイルとして出力します。

入力ファイルとなるメッセージを含んだファイルは
・ShortMsgKAT.txt (0〜2047ビット)
・LongMsgKAT.txt (2048〜34304ビット)
・ExtremelyLongMsg.txt (16777216ビットのみ)
で、以下のファイルを生成します。
・ShortMsgKAT_{224,256,384,512).txt
・LongMsgKAT_{224,256,384,512).txt
・ExtremelyLongMsg_{224,256,384,512).txt

ファイルの中身はメッセージの数だけ以下のような行があります。
Len = 1 (メッセージのビット長)
Msg = 00... (メッセージのバイト列16進数)
MD = ??... (ハッシュ計算結果。入力時は無視)

超シンプルなサンプルコード

genKAT.cじゃごちゃごちゃしているで超シンプルなサンプルコードを以下に示します。

#include 

#include "SHA3api_ref.h"



/* バイト配列の16進数表示 "type = 1F2F3F..." */

void fprintBstr(FILE *fp, char *S, BitSequence *A, int L) {

  int	i;

  fprintf(fp, "%s", S);

  for ( i=0; i
  if ( L == 0 ) fprintf(fp, "00");

  fprintf(fp, "\n");

}



/* メイン： "FF"のSkein256ハッシュ値の表示 */

void main() {

  BitSequence in[1];

  BitSequence out[32]; /* 256bit buffer */

  in[0] = 0xff;



  fprintBstr(stdout, "in = ", in, 1);    /* 入力バイトの表示 */

  Hash(256, in, 8, out);                 /* ハッシュの計算 */

  fprintBstr(stdout, "out = ", out, 32); /* ハッシュ結果の表示 */

}

これを実行してやると

in = FF

out = A47BE71A185BA0AF820B3CE845A3D35A80EC64F96A0D6A36E3F5363624D8A091

となり、サイトの論文の末尾にある1バイト"FF"のハッシュ値と結果が一致します。

時間があればJavaに移植してハッシュやSkein256withRSAなどの署名のJCE暗号プロバイダを作ってみたいところですが、明日から師走ですからねぇ、、、、（＾＾；

NIST.gov - Computer Security Division - Computer Security Resource Center

The new hash algorithm will be called “SHA-3” and will augment the hash algorithms currently specified in FIPS 180-2, Secure Hash Standard. Entries for the competition must be received by October 31, 2008.

NISTではSHA2の次のハッシュアルゴリズム SHA3の公募とコンペティションを行い、2010年Q2には最良のアルゴリズムを選定します。

まとめは別館のほうで行っていこうと思います。IAIKのまとめページSHA3 Zooによると34のアルゴリズムが参加し、セキュリティでは有名なBruce SchneierやRon Rivestなどのチームも参加するようです。

ハッシュ関数の一番重要なアプリケーションは署名だと思うんですが、これらのハッシュ関数を署名で使う場合にはハッシュアルゴリズムのオブジェクト識別子(OID)およびこれらを用いた署名アルゴリズムのOIDを規定しないと利用することができません。

コンペの開催と同時にとりあえずOIDの割り当てをしてしまい、すぐに署名に使えるようにして欲しいなぁ、、、と思っています。最優秀が決まってから１〜２年かけてOID決めましょうなんていうんじゃ話にならないと思いません？ただの決め事なので、、、、