Great original post: CRYPTOGRAPHIC HASHING IN HASKELL..

2017年 9月 18日 Michael Snoyman

cryptonite は現在、Haskell で暗号を扱う際のデファクトスタンダードです。 一般的に安全な乱数、共通鍵・公開鍵暗号、MAC (メッセージ認証符号)等をサポートしていて、その中には今日の話題、暗号学的ハッシュも含まれています。

まず、ハッシュ関数について軽く説明しましょう。ハッシュ関数とは、任意長のデータを固定長のデータに変換するものです。暗号学的ハッシュ関数は、暗号を扱う上で望ましい性質をそなえたハッシュ関数です (詳しくは Wikipedia を参照)。 一般的な暗号学的ハッシュ関数の使われ方の一例として、ダウンロードされたファイルが改ざんされていないことを保証するための、チェックサムを提供する、というものがあります。 今日使われている暗号学的ハッシュ関数には、SHA256、Skein512、そしてまぁ、ちょっと古いですが MD5 などがあります。

cryptonitememory というライブラリの一番上の階層にあります。この memory ライブラリは、Byte 配列を扱うための型クラスと便利な関数を提供しています。 「全て ByteString でいいのでは?」と思うかもしれませんが、後ほどこの型クラスの便利さを示します。

一旦これら 2つのライブラリに慣れれば、簡単に使いこなすことができます。 ですが、API のドキュメントを見るだけでは、部分部分がどう組み合わさるのか理解するのは至難の技です。特に、どこで明示的な型シグネチャが必要になるのかの理解が難しい。 この記事では、理解に必要な部分について1つ1つの簡単な例を、実行可能なコードで紹介します。 読み進める中で、API のドキュメントについてざっくりと理解していってください。

この記事のコードの例は、全て Stack のスクリプトインタプリタ機能を使っています。 まず Stackインストールして、次の手順で実行してください。

  • Main.hs にコードをコピペする
  • stack Main.hs を実行

基本的な型クラス

文字列っぽい型を扱うのは慣れているでしょう? 正格・遅延評価される ByteStringText や普通の String などです。 正格なバイトシーケンスを表現する際、Data.ByteString.ByteString を思い浮かべるのではないでしょうか。 しかし、これから見るように、バイトシーケンスとして扱いたい型はいろいろ見つかります。

memory はこの要望に答えるべく、以下の 2つの型クラスを定義しています。

  • ByteArrayAccess ある型のバイトへ、読み取り専用のアクセスを提供
  • ByteArray 読み / 書きのアクセスを提供する。ByteArrayAccess の子クラス

例えば、以下に示すコードは、意味もなく ByteStringByte の変換をしています。

bytestring ライブラリを使ってファイルの入出力から話を始めたのは、入出力は bytestring でやるべき だからです。 convert関数を使うと、ByteStringBytes に変換することができます。

練習問題 上の2つの型クラスの説明を踏まえて convert の型シグネチャは何だと思いますか? 答えはこちら

bytes の値につけた、明示的な型シグネチャに気がつきましたか? えーと、memorycryptonite を使っていく上で、これは大事です。 こうして、よく GHC に、型推論についてのヒントを与えてやらないといけなくなります。 なぜなら、これらのライブラリの中のかなり多くの関数が、具体的な型ではなく、型クラスを使っているからです。

さて、ByteArrayAccess に属する型の例をお見せしましたが、それはByteArray についての例ではありませんでした。 今は型クラスを分ける意味が分からないかもしれませんが、実際にハッシュを使う段階で、型クラスを分けることの利点が見えてくると思います。 ちょっと待ってくださいね。

なぜ違う型があるのか

当然、memory の中になぜ Bytes という型があるのか、疑問に思う人もいるでしょうね。 ByteString と同じじゃないの? ってね。 まぁ違うんですけどね。 Bytes はメモリスライスのオフセットと長さを追跡しないことで、メモリのオーバーヘッドを小さくしています。 その代わりに、Bytes の値をスライスすることは許されません。 言い換えれば、Bytes に関する drop関数は、バッファの新しいコピーを作らなければならないということです。

まぁつまり、これはパフォーマンスの問題です。暗号を扱うライブラリは、一般的にパフォーマンスを重視する必要がありますからね。

また別の memory のおもしろい型に、ScrubbedBytes というものがあります。 この型は、3つの特別な性質を有しています。 Haddock によると、

  • スコープの範囲から出るとゴシゴシされる
  • Show インスタンスは、中身を何1つとして出力しない
  • 定数時間の Eq インスタンス

つまり、これらの性質は何か機密性の高いデータを扱うとき、ありふれた脆弱性をいくつも塞いでくれるものです。

うん、コードがあまりない説明になりましたね。 もっと楽しいことをしよう!

Base16 エンコード/デコード

ユーザの入力を、Base16 (16進数) に変換してみましょう。

convertToBase は、どんな ByteArrayAccess も、与えられた基数を使って ByteArray に変換することができます。Base16 以外の基数には、Base64 などがあります。

見てお分かりの通り、上の例では明示的に ByteString の型シグネチャを指定する必要がありました。なぜならそうしなければ、GHC がByteArrayAccess のインスタンスの内、どれを使うべきなのか判断できないからです。

既にお分かりかもしれませんが、全く逆の変換を行う、convertFromBase関数も存在します。 この関数は、入力のフォーマットが正しくなかった場合にも対応できるように、Either String ByteArray の値を返します。

練習問題 入力に対して、Base16 のデコードを行うプログラムを書いてください (解答はすぐ下)。

練習問題 Base16 の入力を、Base64 のエンコードに変換するプログラムを書いてください。

正格な ByteString のハッシュ

よし、memory ライブラリに関する説明はもう十分でしょう。 これからは実際に暗号的なものをやっていきます。ユーザの入力を、SHA256 のハッシュ値 (ダイジェスト) に変換してみましょう。

たった今、ByteString (かもしくは ByteArrayAccess のインスタンス) を Digest SHA256 に変換するために hash 関数を使いました。 実際、SHA256 以外のハッシュアルゴリズムも指定することができます。

今回の例では、Digest SHA256 という型シグネチャが大事でした。GHC にどんなハッシュを使うのか知らせるためです。しかし次の例では、その代わりの関数が登場します。

DigestShow インスタンスは、ダイジェストを16進数 (Base16) で表示します。これはいいですね。 しかし、これをBase64 で表示したい欲求にかられたらどうでしょう? 考えてみましょう。 DigestByteArrayAccess のインスタンスです。なので、convertToBase を使うことができます (そして、DigestByteArrayのインスタンスではありません。そうしてしまったら問題が生じるのですが、それはなぜでしょうか? 行き詰まったら、この関数のドキュメントを読んでみましょう。答えが載っています。)。

練習問題 ダイジェストを Base64 でエンコードされた文字列として出力してみましょう (答えはすぐ下)。

digestByteString であることを明確にするために、型シグネチャが必要な理由を押さえてください。

マッチするファイルがあるかどうか調べる

ここにちょっとしたプログラムがあります。ユーザはコマンドライン引数として、複数個のファイル名を渡します。そして、プログラムは同一の内容の全てのファイルのリストを表示します (少なくとも、SHA256 のハッシュ値がマッチするファイルを。それと、以下の定義には、メモリの効率がよろしくない部分があります。見つけてみてください。この点についてはまた後述します)。

練習問題 コマンドライン引数として与えられた全てのファイルの SHA256 ハッシュ値を表示するプログラムを書いてください。

質問 上のコードの、どこが非効率的なのでしょうか? 答えは次の章にあります。

より効率的なファイルハッシュ

もしもハッシュ関数を使わなければ、さっきのプログラムの実装は、それぞれのファイルの中身をメモリ上に一度に展開するか、O(n^2) のペアの比較をするような変なものになっていたでしょう。 さっきのハッシュを使った実装は、それよりも良い実装です。しかし、まだ問題があります。 Data.ByteString.readFileを使っているので、際限なくメモリを使ってしまう可能性があります。 cryptonite-conduit を使うと、ファイルの内容全てをもっと効率良くハッシュできます。

かなりシンプルな変更です (というか、こっちの方が少し読みやすいのではないでしょうか)。 さらに、かなりメモリ効率の良いコードになりました(ファイル数に対して線形時間、ファイルサイズに対しては定数時間です)。

ストリーム・ハッシュ

conduit と聞いて、耳か目が即座に反応したかもしれません。 質問された体で答えましょう。 はい、ハッシュに関してもストリーミング処理ができます。ここに、URL とファイルパスを受け取って、その URL の response body の中身をファイルパスに書きこみ、SHA256 でダイジェストを表示するプログラムがあります。 そして、それぞれのデータチャンクを 1回しか参照しないのがいいですね。

conduit にできるなら、もちろんあなたにもできるはずです。 conduit を使わずに、hashFile を実装してみましょう。 こうすることで、ハッシュの API の内部がいくらか分かります。

この実装では Crypto.Hash で提供されている純粋なハッシュ更新用関数を使っています。 今回の場合、いくつかバッファのコピーをスキップすることで、もう少し効率の良い実装を可能にする、可変ハッシュの関数を使うことができます。

練習問題 遅延入出力と hashlazy関数を使って、hashFile を実装してください (遅延入出力を支持しているわけじゃないですよ。)。