こんにちは、CTOの森下です。

今回は、ランダムな値を生成する HMAC Deterministic Random Bit Generator (HMAC-DRBG) をGolangでフルスクラッチで実装してみたいと思います。

乱数生成アルゴリズムの重要性

BitcoinやEthereumを始めとするブロックチェーンは主に楕円曲線を署名に用いています。その署名アルゴリズム[1]で任意の整数kが必要となるのですが、これが単一である場合、トランザクションのメッセージの差分から秘密鍵を導出できてしまうという脆弱性につながってしまいます。したがって、この任意の整数kは決して被ることのないユニークな整数でなければいけません。

HMAC-DRBG

HMAC-DRBGは決定性を持つ乱数生成アルゴリズムです。決定性とは毎回ランダムな値になるのではなく、入力に対して決まったランダムな値が出力される性質を持つということです。 ZilliqaのGolang SDKであるZilleanを実装するにあたってこのHMAC-DRBGが必要であり、Golangでの信頼の置けるライブラリがなかったため、自作することになりました。セキュアな乱数アルゴリズムはいくつかある中、HMAC-DRBG [2]を選ぶメリットとしては、以下が挙げられます。

仕様がシンプル
堅牢なハッシュベースのアルゴリズム
決定性なため、テストがしやすい

HMAC-DRBGは3つの状態からなります。

エントロピーからHMAC-DRBGのインスタンス化

インスタンスが持つStateを入力としたHMACでの乱数生成

Additional Input でのUpdate

インスタンス化

さて、ここからは論文[2]を元に実装していきます。まずはインスタンス化のアルゴリズムです。

これより、HRMAC-DRBGのインスタンスとStateを以下のように定義します。

type HmacDRBG struct {
	k             []byte
	v             []byte
	reseedCounter int
}

次に、インスタンス化のプロセスです。

これを元に、コードへ落とし込むと以下のようになります。

var (
	// Key = 0x00 00...00
	initK = []byte{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}
	// V = 0x01 01...01
	initV = []byte{0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01}
)

func NewHmacDRBG(entropy, nonce, pers []byte) *HmacDRBG {
	// seed = entropy || nonce || personalization
	seed := append(append(entropy, nonce...), pers...)

	k := initK
	v := initV

	h := &HmacDRBG{
		k:             k,
		v:             v,
		reseedCounter: 0,
	}

	h.update(seed)
	h.reseedCounter = 1

	return h
}

プロセス通りに実装するだけなので、非常にシンプルです。

Update

次はこのアルゴリズムの肝となるUpdateメソッドです。プロセスは以下で定義されています。

これを実装すると以下のようになります。

func (h *HmacDRBG) update(input []byte) {
	// K = HMAC(K, V || 0x00 || input)
	var data = make([]byte, 0, len(h.v)+len(input)+1)
	data = append(data, h.v...)
	data = append(data, 0x00)
	data = append(data, input...)
	mac := hmac.New(sha256.New, h.k)
	mac.Write(data)
	h.k = mac.Sum(nil)

	// V = HMAC(K, V)
	mac = hmac.New(sha256.New, h.k)
	mac.Write(h.v)
	h.v = mac.Sum(nil)

	if len(input) == 0 {
		return
	}

	// K = HMAC(K, V || 0x01 || input)
	data = make([]byte, 0, len(h.v)+len(input)+1)
	data = append(data, h.v...)
	data = append(data, 0x01)
	data = append(data, input...)
	mac = hmac.New(sha256.New, h.k)
	mac.Write(data)
	h.k = mac.Sum(nil)

	// V = HMAC(K, V)
	mac = hmac.New(sha256.New, h.k)
	mac.Write(h.v)
	h.v = mac.Sum(nil)

	return
}

基本的に、K, V, input を使って決められた形にアライメントしたデータをHMACでハッシュ化していくというアルゴリズムです。今回、HMACで使うハッシュ関数は本ブログで解説しているSHA-256を採用しました。

Reseed

次は、Reseedメソッドです。プロセスは以下で定義されています。

コードにすると以下のようになります。

func (h *HmacDRBG) Reseed(entropy []byte, input []byte) error {
	seed := append(entropy, input...)
	h.update(seed)
	h.reseedCounter = 1

	return nil
}

これはプロセス通り実装するだけでなので簡単です。

Generate

最後に、Generateメソッドです。プロセスは以下で定義されています。

コードにすると以下のようになります。

var reseedInterval = 10000

func (h *HmacDRBG) Generate(byteLength int32, input []byte) ([]byte, error) {
	if h.reseedCounter > reseedInterval {
		return nil, errors.New("Reseed is reqired")
	}

	if len(input) > 0 {
		h.update(input)
	}

	temp := make([]byte, 0, byteLength)
	for i := int32(0); i < byteLength; i += int32(32) {
		mac := hmac.New(sha256.New, h.k)
		mac.Write(h.v)
		h.v = mac.Sum(nil)
		temp = append(temp, h.v...)
	}
	result := make([]byte, byteLength)
	copy(result, temp[:byteLength])

	h.update(input)
	h.reseedCounter++

	return result, nil
}

プロセスは他のものに比べると少し複雑ですがやってることはupdateとバイト長分だけHMACのイテレーションを回したものをリターンするだけです。

以上で、HMAC-DRBGは完成となります。コードの全体はここ[3]で公開しています。

実行例

実装したHMAC-DRBGのサンプルコードを以下に載せておきます。

package main

import (
	"encoding/hex"
	"fmt"

	crypto "github.com/GincoInc/go-crypto"
)

func main() {
	entropy, _ := hex.DecodeString("28dc2f25b2634c0672a0fa03378563de214500faa77ee4076409aa16bc8512d2")
	nonce, _ := hex.DecodeString("85d52ed34e062909bb5e6175dfa187b8")
	pers, _ := hex.DecodeString("5bb0e422ceec47aaf48082909f11c998a5a77d54320b28eaeaab713221c95419")

	hmacDRBG := crypto.NewHmacDRBG(entropy, nonce, pers)
	result, _ := hmacDRBG.Generate(int32(32), []byte{})
	fmt.Printf("%x\\n", result)
	// 3d5e70675440db53e49d2447a8725b0c4755185a6fc6fc91c180d4f587c2428d
}

まとめ

今回はGolangでブロックチェーンの署名アルゴリズムに必要不可欠であるセキュアな乱数を生成するHMAC-DRBGを実装しました。楕円曲線やハッシュ関数に比べるとアルゴリズム自体がシンプルなので、初めて暗号系のライブラリを実装する人にとってはぴったりだと思います。ブロックチェーンを理解するにあたってその根幹技術の再発明はとても勉強になるのでおすすめです。

次回は、Zilliqaで採用されている楕円シュノア署名(EC-Schnorr)[4]の実装について書きたいと思います。ではまた。

Tip us!

エンジニアチームのブログを書くモチベーションが上がります！

参考文献

[1]</a> https://ja.wikipedia.org/wiki/楕円曲線DSA
[2]https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf
[3]</a> https://github.com/GincoInc/go-crypto/blob/master/hmac_drbg.go
[4]ttps://en.wikipedia.org/wiki/Schnorr_signature

HMAC-DRBGをGolangで実装する