scryptにまつわる各アルゴリズムを実装してみる

どうもscryptでは日本語でアルゴリズムを紹介している数少ないサイトとなっているなぁ、と眺めていたのですが、それならば、と汎用コードを紹介してみようかと思います。解説については前編および後編を参考に。中編は外部アルゴリズムの説明なので飛ばしてもいいでしょう。

なお、何度も書いておきますが、これは各アルゴリズムをC言語で組んだもので最適化もなにも考えられた状態ではありません。そのため速度はかなり遅いのと外部にあるアルゴリズムはコード内ではプロトタイプ宣言のみを示した状態にします。使いたい場合はその意味に合うように対象のコードを組んでください。

また、C言語で書かれた各アルゴリズム内のコメントはbuffer alloc/release(内部バッファの確保および解放)とStep n(論文(?)上のアルゴリズムステップ番号)を示しています。本体を読んだ上でコードを見ている場合は参考にしてください。

まずは型や外部処理のプロトタイプ宣言

#include <stddef.h>
#include <memory.h>
#include <malloc.h>

//型の置き換え処理
typedef unsigned char byte_t;
typedef unsigned int uint32_t;

//メモリ簡易確保
#ifdef _WIN32
#define allocstack(n)		_alloca(n)
#define freestack(p)		_freea(p)
#else
#define allocstack(n)		malloc(n)
#define freestack(p)		free(p)
#endif //_WIN32

//内部で使用するハッシュ処理の定義
//なお、各処理においてdestがsrc、key、textと同一であったとしても正しい結果が返せることを前提とする
typedef void (*LPFNHASHFUNC)(void *dest,const void *src,void *hashctx);
typedef void (*LPFNHASHRAND)(void *dest,const void *key,size_t keylen,const void *text,size_t textlen,void *hashctx);
typedef size_t (*LPFNHASHLENGTH)(void *hashctx);
typedef uint32_t (*LPFNINTERGERIFY)(const void *dat,void *hashctx);

//リトルエンディアン処理
uint32_t SetLittleEndian(uint32_t n);

//Salsa20の宣言
void *NewHashSalsa20(int rounds);
void DeleteHashSalsa20(void *hashctx);
void GetHashSalsa20(void *dest,const void *src,void *hashctx);
size_t GetLengthHashSalsa20(void *hashctx);

//HMAC-SHA256の宣言
void *NewHashHMACSHA256(void);
void DeleteHashHMACSHA256(void *hashctx);
void GetHashHMACSHA256(void *dest,const void *key,size_t keylen,const void *text,size_t textlen,void *hashctx);
size_t GetLengthHashHMACSHA256(void *hashctx);

//PBKDF2の宣言
bool PBKDF2(void *dkdata,size_t dklen,LPFNHASHRAND hashrand,void *hashctx,size_t hashlen,const void *password,size_t pwlen,const void *salt,size_t saltlen,size_t itercount);

//バッファのXOR処理
void XORBuffer(void *dest,const void *src,size_t len);

上記に存在する関数プロトタイプはすべて外部処理となります。コードを実行してみたい場合はこれらを名前の意味に合うように組んでください。ハッシュ系はNew=>Get(+GetLength)=>Deleteの流れで良くある状態になっているはずです。一応リトルエンディアン処理も入っていますのでもしビックエンディアンのCPUで実行する場合は気をつけてください。

各アルゴリズムが使用するパラメータを保存する構造体を宣言

//使用するパラメータ
//ROMixで使用するパラメータ
typedef struct _ROMixParam{
	LPFNHASHFUNC hashfunc; //内部で使用するハッシュ処理
	LPFNINTERGERIFY intergerify; //内部で使用するハッシュ整数化処理
	void *hashctx; //ハッシュコンテキスト
	size_t hashlen; //ハッシュ長
	uint32_t metric; //メートリック(ブロック拡張パラメータ)
} ROMIXPARAM;

//BlockMixで使用するパラメータ
typedef struct _BlockMixParam{
	LPFNHASHFUNC hashfunc; //内部で使用するハッシュ処理
	void *hashctx; //ハッシュコンテキスト
	size_t hashlen; //ハッシュ長
	uint32_t blocksize; //処理ブロック数
} BLOCKMIXPARAM;

//MFCryptで使用するパラメータ
typedef struct _MFCryptParam{
	LPFNHASHFUNC hashfunc; //内部で使用するハッシュ処理
	LPFNHASHRAND hashrand; //内部で使用する疑似乱数処理
	void *hashfuncctx; //ハッシュコンテキスト
	void *hashrandctx; //疑似乱数コンテキスト
	size_t hashfunclen; //ハッシュ長
	size_t hashrandlen; //疑似乱数長
	uint32_t parallelparam; //並列パラメータ
} MFCRYPTPARAM;

//MFCryptに渡すデータ
typedef struct _MFCryptData{
	void *dkdata; //生成されるデータ列
	void *passphrase; //パスフレーズ
	void *saltstring; //ソルト文字列
	size_t dklen; //生成されるデータ長
	size_t passlen; //パスフレーズ長
	size_t saltlen; //ソルト文字列長
} MFCRYPTDATA;

この辺はアルゴリズムの文章と見比べて意味を把握してください。scrypt本体を実装する段階でどうなるのかは紹介しますので。

各アルゴリズムを単体で見るとそれぞれでハッシュ処理を使用しているのが分かると思います。これが汎用実装する場合に訳が分からなくなる原因だと思います。scryptのみを実装する場合はパラメータが特定されている状態なので特殊化すればよい(処理を埋め込めばよい)のでわかりやすいですが、汎用だとこんな感じになります。

BlockMixアルゴリズムの実装

//Intergerify
uint32_t BlockMixIntergerify(const void *dat,void *hashctx)
{
	BLOCKMIXPARAM *param = (BLOCKMIXPARAM *)hashctx;
	return SetLittleEndian(*(uint32_t *)((byte_t *)dat + param->hashlen * (param->blocksize * 2 - 1)));
}

//BlockMix
void BlockMix(void *dest,const void *src,void *hashctx)
{
	void *dat,*tmp; byte_t *buf; size_t i,round,hashlen,buflen;

	BLOCKMIXPARAM *param = (BLOCKMIXPARAM *)hashctx;
	round = param->blocksize * 2; hashlen = param->hashlen; buflen = hashlen * round;

	//buffer allocation
	buf = (byte_t *)allocstack(hashlen + buflen);
	dat = buf; tmp = buf + hashlen;
	
	//Step1
	memcpy(dat,(byte_t *)src + buflen - hashlen,hashlen);

	//Step2
	for(i = 0;i < round;i++){
		//Step 3
		XORBuffer(dat,(byte_t *)src + hashlen * i,hashlen);
		param->hashfunc(dat,dat,param->hashctx);

		//Step4(+Sort(for Step6))
		memcpy((byte_t *)tmp + hashlen * ((i >> 1) + (i & 0x01) * (round >> 1)),dat,hashlen);

	//Step 5
	}

	//Step6(Copy sorted buffer)
	memcpy(dest,tmp,buflen);

	//buffer release
	freestack(buf);
}

最終の並び替えが非常に面倒なので各ブロックのハッシュ計算時に並び替えを行って最終は単にバッファをコピーするだけにしてあります。BlockMixのループ数は2*blocksizeとなります。

ROMixアルゴリズムの実装

//ROMix
void ROMix(void *dest,const void *src,void *hashctx)
{
	void **vec,*dat; byte_t *buf,*ptr; size_t i,hashlen,memsize; uint32_t index,metric;

	ROMIXPARAM *param = (ROMIXPARAM *)hashctx;

	hashlen = param->hashlen; metric = param->metric;
	memsize = sizeof(void *) * metric + hashlen * (metric + 1);
	
	//buffer allocation
	ptr = buf = (byte_t *)malloc(memsize);
	vec = (void **)ptr; ptr += sizeof(void *) * metric;
	dat = ptr; ptr += hashlen;
	
	//Step 1
	memcpy(dat,src,hashlen);

	//Step2
	for(i = 0;i < metric;i++){
		//Step3
		vec[i] = ptr; ptr += hashlen;
		memcpy(vec[i],dat,hashlen);

		//Step4
		param->hashfunc(dat,dat,param->hashctx);

	//Step5
	}

	//Step6
	for(i = 0;i < metric;i++){
		//Step7
		index = param->intergerify(dat,param->hashctx) & (metric - 1);

		//Step8
		XORBuffer(dat,vec[index],hashlen);
		param->hashfunc(dat,dat,param->hashctx);

	//Step9
	}

	//Step10
	memcpy(dest,dat,hashlen);
	
	//buffer release
	free(buf);
}

ROMixはバッファ拡張パラメータN(プログラム内ではmetricと表記)のためにかなりメモリを使用するルーチンです。そのためスタックからメモリを確保すると不足することがあるためmalloc関数によるメモリ確保を使用しています。(たとえばscryptでN=1024、blocksize=1とすると1024×64×2×1=128kBとなる)scryptを専用に実装する場合はこのメモリ確保は外からやるようにしないと速度に影響します。

またアルゴリズムをそのまま実装しているのでROMix内で呼び出されるハッシュ処理の回数は2×Nとなります。N=1024だと2048回も呼び出されることになります。scryptだとこのハッシュ処理はBlockMixアルゴリズム(下にはさらにSalsa20/8がある)のでメモリだけではなくCPU負荷としてもかなり重い処理ですね。scryptを専用に実装する場合はROMixをどうやって高速になるように実装するかが重要となります。

SMixアルゴリズムの実装は・・・

汎用実装している場合はBLOCKMIXPARAM構造体に意味に合うようにパラメータを設定してROMixを呼び出すことと同じなので説明はscryptの実装に譲ります。

MFcryptアルゴリズムの実装

//MFcrypt
bool MFcrypt(MFCRYPTDATA *data,MFCRYPTPARAM *param)
{
	byte_t *buf,*dat; size_t i,blocklen,hashrandlen; bool ret = false;

	do{
		//buffer allocation
		hashrandlen = param->hashrandlen; blocklen = param->hashfunclen * param->parallelparam; buf = (byte_t *)allocstack(blocklen);

		//Step1
		if(!PBKDF2(buf,blocklen,param->hashrand,param->hashrandctx,hashrandlen,data->passphrase,data->passlen,data->saltstring,data->saltlen,1)) break;

		//Step2
		for(i = 0,dat = buf;i < param->parallelparam;i++,dat += param->hashfunclen){
			//Step3
			param->hashfunc(dat,dat,param->hashfuncctx);

		//Step4
		}

		//Step5
		if(!PBKDF2(data->dkdata,data->dklen,param->hashrand,param->hashrandctx,hashrandlen,data->passphrase,data->passlen,buf,blocklen,1)) break;

		ret = true;
	} while(0);

	//buffer release
	freestack(buf);
	return ret;
}

実装の鍵はPBKDF2をどう実装しているか、という部分です。今回は汎用実装なのでPBKDF2を普通に呼び出しているだけになります。scryptを専用で実装する時にはPBKDF2の呼び出しは「常にIterationCountを1で呼び出す」ためループを実装する必要が無いことに注意しましょう。今回一応PBKDF2にはパラメータ異常時にエラーを返すようにしてあるのでその処理が入っています。

scryptアルゴリズムの実装

//scrypt
bool scrypt(MFCRYPTDATA *data,uint32_t cpucost,uint32_t blocksize,uint32_t parallelparam)
{
	MFCRYPTPARAM mfcryptparam; ROMIXPARAM romixparam; BLOCKMIXPARAM blockmixparam; void *salsactx,*hmacsha256ctx; bool ret;

	//Setup hash algorithm
	salsactx = NewHashSalsa20(8);
	hmacsha256ctx = NewHashHMACSHA256();

	//Setup BlockMix
	blockmixparam.hashfunc = &GetHashSalsa20;
	blockmixparam.hashctx = salsactx;
	blockmixparam.hashlen = GetLengthHashSalsa20(salsactx);
	blockmixparam.blocksize = blocksize;

	//Setup ROMix
	romixparam.hashfunc = &BlockMix;
	romixparam.intergerify = &BlockMixIntergerify;
	romixparam.hashctx = &blockmixparam;
	romixparam.hashlen = blockmixparam.hashlen * blockmixparam.blocksize * 2;
	romixparam.metric = cpucost;

	//Setup MFCrypt
	mfcryptparam.hashfunc = &ROMix;
	mfcryptparam.hashrand = &GetHashHMACSHA256;
	mfcryptparam.hashfuncctx = &romixparam;
	mfcryptparam.hashrandctx = hmacsha256ctx;
	mfcryptparam.hashfunclen = romixparam.hashlen;
	mfcryptparam.hashrandlen = GetLengthHashHMACSHA256(hmacsha256ctx);
	mfcryptparam.parallelparam = parallelparam;

	//Call scrypt(MFcrypt)
	ret = MFcrypt(data,&mfcryptparam);

	//Release hash algorithm context
	DeleteHashHMACSHA256(hmacsha256ctx);
	DeleteHashSalsa20(salsactx);

	//Return
	return ret;
}

やっと最終です。各構造体へのセットアップや呼び出しを一気にやっています。ちなみにROMixをSMixとして呼び出す場合BLOCKMIXPARAMおよびROMIXPARAMをこの中で設定しているようなパラメータを設定してROMixを呼び出せばOKです。この実装を見れば各処理でハッシュ処理として何を使用しているか？などが分かると思います。汎用で組むとパラメータがかなり移動したりハッシュコンテキストが入れ子になったりする不思議なコードになるのですね・・・。

ちなみにエラー処理などは省いていますので動作検証用程度にしてください。ハッシュコンテキストが作成できない場合などいろいろとありそうなので・・・

アルゴリズムを「できるだけ正確に組む」とこんな感じ

となります。論文(?)として示されたアルゴリズムを組んでみる、というのは大学などだとよくあることなのだと思いますが私のような立場だとどうなのでしょうか。また実際に使用する場合にはLitecoinなどパラメータが固定の場合はこれを最適化した上で組めばいいのでこんなコードにはなりません。また私の内部実装だとC++を使っているのでもう少しすっきりしています。C++だとインターフェイスクラスなどを示す必要があるため今回は崩した形で、というわけでした。

プログラマのつれづれなるままに

音宮志久が思ったことなどをネタにします。プログラムネタ・数学ネタがメインです。

まずは型や外部処理のプロトタイプ宣言

各アルゴリズムが使用するパラメータを保存する構造体を宣言

BlockMixアルゴリズムの実装

ROMixアルゴリズムの実装

SMixアルゴリズムの実装は・・・

MFcryptアルゴリズムの実装

scryptアルゴリズムの実装

アルゴリズムを「できるだけ正確に組む」とこんな感じ

コメントを残すコメントをキャンセル

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

まずは型や外部処理のプロトタイプ宣言

各アルゴリズムが使用するパラメータを保存する構造体を宣言

BlockMixアルゴリズムの実装

ROMixアルゴリズムの実装

SMixアルゴリズムの実装は・・・

MFcryptアルゴリズムの実装

scryptアルゴリズムの実装

アルゴリズムを「できるだけ正確に組む」とこんな感じ

関連する記事

コメントを残す コメントをキャンセル

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

コメントを残すコメントをキャンセル