scryptを実装してみた 後編

前編中編ときて後編です。何度も言いますが、scryptを実装するまでに出てくる各アルゴリズムはそれぞれは単純ですが組み合わせが非常に分かりづらいです。特にアルゴリズムを通過するといつの間にかパラメータでサイズが変わっていたりしますのでそのあたりが注意点になります。中身については事実上scryptの論文を意訳しているのと余り変わりはありませんね。

 

前回のアルゴリズムにパラメータをつけて再度書き直し

です。これをつけておかないと説明がしづらすぎるので。出てきた既存のアルゴリズムは

  • PBKDF2PRF(P,S,c,dklen)
  • HMAC-SHA256(text,key)
  • Salsa20/8(X)

となります。この引数は後で説明で使います。

 

ここからアルゴリズムが入り乱れ

本当に入り乱れ、です。どこがどう呼び出されているのかなど実際に組んでみてもわけがわからなくなりそうな状態でした。説明の順序は論文(?)側に書いてある順序ではなく呼び出しの末端側から書いていきます。

BlockMixH,r(B)

与えられたブロックの撹拌処理を行います。与えられるブロックサイズは撹拌時に使用するハッシュ処理の出力ビット長の2r倍です。つまりここを呼び出す場合、Bのサイズは[ハッシュ長hLen]x[ブロックサイズパラメータr]x2となります。撹拌作業そのものはブロックごとの排他的論理和、ハッシュ撹拌、ブロックの並び替えとなります。ここが使用するブロック長がscryptで一度に処理されるブロック長となることに気をつけましょう。

scrypt内ではパラメータrはscryptの処理引数として与えられます。また、ハッシュ撹拌処理HにはSalsa20/8が使用されます。そのため、上記のブロック長計算を使用するとscrypt全体のブロック長は[64bytes]x[r]x2となります。

ROMixH(B,N)

ブロックを一度拡張させて縮退させるルーチンです。この処理には特にわざとメモリを使用させる効果があり、カスタムチップなどで組みにくくする効果をもたらしています。特にブロック拡張パラメータNを大きくするとかなりメモリを消費します。このルーチンで使用される一時メモリは[ハッシュ長(ブロック長)hLen]x[ブロック拡張パラメータN]となり、Nが2^14くらいになるとメモリ消費だけですごいことになります。なお、このNについては基本的には2の乗数にしないと処理がかなり難しい(いきなり巨大整数ルーチンが必要な羽目に)です。ROMixの安全性の部分については論文(?)中でかなり詳しく説明されていますので気になる人は読んでみるといいと思います。

ここでもハッシュ処理による撹拌を行います。アルゴリズムの解説では任意のハッシュ処理を使用できますが、scryptではこのハッシュ処理に先ほど説明したBlockMixを使います。ハッシュ処理とはいえませんが、一応ブロックデータを与えるとブロックデータを返す処理なのでそういう使用方法が出来る、というわけです。なおROMixもパラメータは持ちますがやはりブロックデータを与えてブロックデータを返す処理ですのでカテゴリ上は同じです。

メモリを使う以外で面倒なのはブロックを縮退させるときにインデックスを取得するルーチンです。アルゴリズム中には「処理ブロックを整数化してNで余りをとる」としか書かれていないのでそれに従います。scrypt中ではこの部分はBlockMixを使っている関係で「ブロック整数化処理=BlockMixで各ブロックを見たときの最終のブロックをリトルエンディアンで整数化」、余りをとる処理については「Nで余りをとる=Nが2の乗数であれば余りをとる動作はN-1で論理積をとることと同一」を使い、結局は「最終ブロックの32bitをリトルエンディアンで取り出してN-1で論理積をとる」という処理に落ち着きます。こうでもしないと遅すぎますよね・・・。

SMixr(B,N)

scrypt内で使用するブロック撹拌処理として再定義しているだけです。上記2つの説明中にscrypt内で使用するときにどうするか、というのを書き直しただけです。一応説明すると

  1. ハッシュ処理H1としてBlockMixを使用し、BlockMix内のハッシュ処理にSalsa20/8(X)、ブロックサイズパラメータにrを使用する。このとき、BlockMixが処理するブロック長は64×r×2bytesとなる
  2. ハッシュ処理H2としてROMixを使用し、ROMix内のハッシュ処理にH1、ブロックサイズは64×r×2bytes、ブロックの整数化処理は「BlockMixで各ブロックを見たときの最終のブロックをリトルエンディアンで整数化」とする。引数としてブロック拡張定数Nを与える。このとき、ROMixが処理するブロック長はH1のブロックサイズと同一となる。
  3. ハッシュ処理H2をSMixr(B,N)とする

とまあ面倒ですね~。記号として書くなら下付文字を増やすだけで済むのですが、それだと説明が「あれ~?」の状態になること間違いないので。

MFcryptPRF,MF(P,S,N,p,dkLen)

前編からちょっと表記を変えました。scryptの本体となるアルゴリズムです。疑似乱数生成およびブロック撹拌を使って暗号化処理(ハッシュ処理)を行います。ここでも並列処理パラメータpを使ってブロックを拡張した後各ブロックごとにブロック撹拌を行い再度縮退を行います。ブロック生成とブロック縮退は両方ともPBKDF2が使用されます。難しいのはここでのブロック長はブロック撹拌処理が生成するブロック長がそのまま使用される、というところです。この段階では決まっていないので変数を使って表記されています。pについてはこの中だけで使用される引数なので後ろには響きません。説明にも「並列度パラメータ」の名の通り、ブロック撹拌をいくつ同時に行うかを決めているだけです。

 

最後に組み合わせ

それではがんばって組み合わせていきましょう。

scrypt内で使用するブロック撹拌処理として再定義しているだけです。上記2つの説明中にscrypt内で使用するときにどうするか、というのを書き直しただけです。一応説明すると

  • scryptの処理をscrypt(P,S,N,r,p,dkLen)=MFcrypt(P,S,N,p,dkLen)とする。
  • MFcryptで使用されるPBKDF2内で使用される疑似乱数処理PRFはHMAC_SHA256(text,key)を使用する
  • MFcryptで使用されるブロック撹拌処理はSMixr(B,N)を使用する
  • scryptの内部ブロック長はSMixr(B,N)と同一なので64×r×2bytesとなる。

最後にそれぞれのパラメータがどこに渡されるのかを見ていきましょう。

  • パスフレーズP => MFcryptのパスフレーズP => PBKDF2のパスワード文字列P
  • ソルト文字列S => MFcryptのソルト文字列S => PBKDF2のソルト文字列S
  • CPUおよびメモリのコストパラメータN (基本は2の累乗) => MFcryptのパラメータN => ROMixのブロック拡張パラメータN
  • ブロックサイズパラメータr => SMixのブロックサイズパラメータr (scrypt内で使用されるブロック長はSalsa20/8のブロック長64bytes×r×2)
  • 並列処理パラメータp => MFcryptの並列数(ブロック生成数)p
  • 出力鍵長dkLen => MFcryptの出力鍵長dkLen => PBKDF2の最終出力長dkLen

やっと最後まで行き着きました・・・。

 

ちなみにLitecoinでのパラメータは?

そのためにやったのですからね・・・。

Litecoinでscryptを使用する場合はパラメータは以下に固定されます。

  • ソルト文字列S => 80byteの文字列(計算時は固定される)
  • CPUおよびメモリのコストパラメータN = 1024
  • ブロックサイズパラメータr = 1
  • 並列処理パラメータp = 1
  • 出力鍵長dkLen = 32 octets (256bits)

定数系のパラメータが軒並み固定されているのでその部分のループを展開するのが高速な実装の近道ですね。問題なのはNが1024となっているのでここをどうやって高速かつ低メモリで処理するか、にかかるわけです。ROMixの一時ブロックサイズは64×r×2×Nを消費し、しかも添え字を使用する各ブロックは先頭から依存した計算を行っているので指定したブロックだけを生成するのはまず不可能です。あらかじめ使われるブロックを調べてその最大のブロックまでしか生成しない、という方法が真っ先に思い浮かぶくらいでしょうか。

一応はLitecoinでも各処理ブロックを連続させたときに計算されるハッシュ値が指定した状態にならなければならない、なのでscrypt処理を並列で走らせれば済む話なのですが、それだとおもしろくもない結論ですよね・・・。CPUやGPUで計算させる方法が有効のままである、という結論だけですし。

個別の演算では排他的論理和やメモリ転送にレジスタ幅が広い演算を使用したり、Salsa20の処理時にSIMDを使って高速化させる、という発想があります。特にSalsa20の演算は32bitx4の演算が大量にあるのでSSE2を使えば高速化しやすい演算になっているようですね。

 

Litecoinで稼ぎ出せ?

BitcoinだともうPCを使った自前発掘はまず不可能ですからね・・・。Litecoinがメジャーになるかどうかは不明として、まあ発掘作業についてののアルゴリズムは見てみましたので掘り出してみたい人はオフィシャルのプログラムを使うなりアルゴリズムを参考に高速化を考えてみたりしてみてください。私は知りません。(発掘には参加するかもしれませんが)

 

14/03/17 追記

各アルゴリズムの実装例についてはこちらで紹介しています。コードが大量にあるので関連する記事で紹介されないという状態に・・・

 

コメントを残す

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

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