scryptを実装してみた 前編

本当に人が興味を持たないものに持つんですね~といわれるような選択のscryptです。名前を書くときによくscriptと間違えて打ち込んでしまいます。もちろん間違いでscryptが正しいです。なお記事を書く前に検索をしてみましたが日本語の記事はほとんどありませんでした。日本語のWikipediaにも解説はないので先行するのが何となくいい感じです。ちょっと記事が難しい、というより実装がとんでもなく「面倒」だったために前後編に分かれています。

 

P2Pの貨幣であるLitecoinで使われているハッシュ方式

Bitcoinだったらメジャーなんですが・・・。この頃Bitcoinの発掘がほぼ不可能になっているのでまだまだGPUの並列演算などで発掘が可能であるLitecoinを紹介する記事が妙に増えています。で、その中で使われているハッシュの方式です。ちなみにBitcoinの方はメインとなるハッシュにSHA256を使っているのは有名な話ですね。

なお、今のところですがこのハッシュ形式の場合はカスタムチップで効率よく計算するような方法が見つかっていないようです。そのため発掘作業には普通にCPUやGPUを使った並列演算が有効という状態担っています。というよりはこの方式自体がカスタムチップで効率よく計算できないようにするために考え出された計算式を使っているからなのですが・・・。

 

本体のアルゴリズムは「鍵付きハッシュコード」

つまるところHMAC-SHA1などの仲間です。鍵付きハッシュコードはデータベースにパスワードを保存するときに安全性を確保するときによく使われます。パスフレーズ部分にユーザーが入力したパスワード、ソルト部分にサービス作成時に設定させたキー文字列を使うことで万が一データベースが抜かれたときにただのハッシュコードよりもパスワードのアタックに対して時間を稼ぐことができる、という効果があります。それ以外にも今回のように「特定のハッシュコードになるように計算させる」場合にどちらかを固定してどちらかに指定した形式のデータを与えてテストすることで出す、というのが比較的簡単に定義できるわけです。

ちなみに今であればだいたいのフレームワークですでに計算するための処理はくっついていると思うので適当に呼び出してみればいいと思います。Javaやphp、Rubyにも実装されているもしくはサンプルコードがあるようなので単純な計算ならそちらを使うのが良いと思います。

 

アルゴリズム自体は汎用的なのだが・・・

汎用的、というよりは「どの方式でも使えるようにしてある」が正しいです。後でこの意味を説明します。論文(?)中にいくつかの証明およびscryptで使用される各種アルゴリズムの紹介が載っているのでコードを見たくない人はそちらから実装ができます。コードを見れば一発なのですが、まあ相も変わらずライセンスを避ける意味+高速化をどうやって考えるか、という意味で完全自前実装に挑んでみています。

論文(?)中にscryptにたどり着くために必要なアルゴリズムで記述されているものは

  • ROMixH(B,N)
  • BlockMixH,r(B)
  • SMixr(B,N)
  • MFcryptH,MF(P,S,N,p,dkLen)

となっています。これらを組み合わせてがんばれば実装できるのか?というと全く違いまして・・・。

 

横から現れる既存のハッシュ関数やら何やら

上のアルゴリズムで下付文字で「H」がよく出てきていると思いますが、これは別のハッシュ関数を表します。つまりこれらのアルゴリズムは既存のハッシュ関数をうまく使って強度を上げている、というものなのですね。そのため手動での実装が面倒なのは「横から現れる既存のハッシュ関数を片っ端から実装しなければならない」と言うことにあります。OpenSSLのように様々なハッシュ関数やらを実装しているならいざ知らず、ゲーム用のハッシュ関数しかないところにこれを実装しようものなら不足している処理群の説明書を取ってきて実装しなければ最後まで行かないわけです。

scryptとして実装する場合は上のアルゴリズムに追加して既存のハッシュ関数群

  • PBKDF2(RFC2898)
  • HMAC-SHA256(RFC2104+FIPS180)
  • Salsa20/8

が必要になります。これらを上記のアルゴリズムのハッシュ関数部にそれぞれ当てはめて実装するとscryptのルーチンになります。別のものを当てはめても動作はしますが、それはscryptとは呼ばないのでこの場合は除外です。高速化を考えて組むのであれば上記も組み込んだ上でできる限り展開をする、汎用性を高めるのであれば各処理をインターフェイスクラスなどで分離させて実装するのが効果的です。私の場合はHMACおよびSHA256は組んであったので今回は汎用性重視でばらばらに組んだものを結合させていく形を取っています。

これがLitecoinなどで速度が必要になればものすごいルーチンの展開やらSIMDを使った並列演算ができる形に持って行かないとだめなのですが・・・。

 

前編はここまでです。後編はこれらを結合させていくとどうなるか、というところに注目していきたいと思います。

 

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

この記事のトラックバック用URL