ハッシュベースの署名(公開鍵署名)を書いてみた

Post-Quantum Cryptography, Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, Springer-Verlag Berlin Heidelberg, 2009の冒頭部で、ごく簡単なハッシュベースの署名アルゴリズムが紹介されていて感動したのを思い出したので書いてみた。

コードは長いので一番下に載せる。

概要

これは、堅牢なハッシュ関数を用いて、整数論的な何かに頼らなくても、署名を実現できるというものである。

ハッシュで署名というと、HMACが連想されるが、MACと署名は微妙に異なる。簡単に言うとMACが共通鍵で署名が公開鍵のものを指す。

仕組み

Lamport–Diffieのワンタイム署名という部品をベースにしている。これは、大量のハッシュ値を公開鍵として渡しておき、署名をするときは、その一部の元データを開示するというものである。元データを知っているのは自分だけだから、「どのデータを開示するか」は自分にしか決定できないことであり、この選択とメッセージのダイジェストを対応づけることでメッセージに署名をしたことにする。

この方法は明らかに、同じ鍵で2つ以上のメッセージに署名をすると破綻するという欠点がある。それがワンタイム署名と呼ばれる所以である。そこで、署名をチェインさせることで複数回の署名をできるようにするというのがこのハッシュベース署名の考え方である。

「署名をチェインさせる」と聞いた時点で「多分こんなんだろう」と思って実装したのが以下にある(あとから考えると、ちゃんと最後まで読んでから考えるべきであった)。そういうわけなのでこのプロトコルが本当に安全かはよくわからない。

今回は、各ワンタイム鍵は、「別のワンタイム公開鍵2つ」を署名するか、または実際のメッセージを署名するものとして、ワンタイム鍵からなる二分木を動的に生成するようにしてみた。チェインの長さは32で固定にしたので、最大232個のメッセージを署名できる。

二分木にするというアイデア自体は当然既存のもののようで、Merkle Treeなどがあるようだ。ただMerkle Treeはパッと説明を見た限り、2H個のデータブロックを最初に生成するようなので、少し違うものという気がする。この辺りはもう少し調べる必要がありそうだ。

欠点

プロトコル部分は筆者の想像で書かれたものなので、筆者が気付いていない問題があるかもしれない。

それ以外の問題点としては、

  • 鍵がとても大きい。 (これは、より効率的なワンタイム署名を使えば改善されるのかもしれない)
    • これは木をランダムに掘っていることにも由来している。左から順番に掘れば、秘密鍵の膨張は抑えられるが、何回署名をしたかがわかってしまう。
  • 秘密鍵を丸ごとコピーするなどして、別々のコンピューターで独立して運用すると、安全でなくなる。

以下に示す実装の利用例

$ ls
hashsign.py lipsum2.txt lipsum.txt
$ python3 hashsign.py keygen
$ ls
hashsign.py id_hash id_hash.pub lipsum2.txt lipsum.txt
$ python3 hashsign.py sign < lipsum.txt > lipsum.txt.asc
$ ls
hashsign.py id_hash id_hash.pub lipsum2.txt lipsum.txt lipsum.txt.asc
$ python3 hashsign.py verify -s lipsum.txt.asc < lipsum.txt
Verification succeeded
$ python3 hashsign.py verify -s lipsum.txt.asc < lipsum2.txt
Verification failed

実装

Python3で書かれている。

gist.github.com