データの破損チェックの方法

経緯

仕事上の都合で、データが破損しているかどうかの確認をする必要がありました。（ダウンロードしたデータが壊れていないかなど）
どのアルゴリズムを使うのが適当なのか、情報をまとめておきます。

自分は全然この手の専門家ではないので、間違いあればご指摘ください。

手法

調べると様々手法があるようですが、３つをピックアップ。（他にもパリティとかありますが、今回は除外）

誤り検出率（=信頼性）と処理負荷の面で、ざっくり並べるとこんな感じになりました。

	手法	信頼性	処理負荷	出力ビット数	特徴
1	チェックサム	低	低	8~64	高速処理が可能だが、誤り検出率が低い。
2	巡回助長検査	中	中	8~64	チェックサムより誤り検出率が高い。CRC-32が一般的。
3	ハッシュ関数	高	高	128~512	誤り検出率が一番高い。その分負荷が高い。改ざんチェックにも使われる。

いずれのケースでもデータ（ファイル）を入力し、得られた値を破損チェックに使用します。

手法１は信頼性の面で評価から除外。（どのアルゴリズムを使えばいいのかよくわからないし・・・）
手法３はSHA-3など1024ビット超えるアルゴリズムがありますが、データ破損チェックには重すぎると思うので、その辺も除外。

手法２と手法３の中から、代表的なアルゴリズムを選ぶことにします。

余談

手法２、３で得られた値のこともチェックサムと呼ばれるようですが、紛らわしいのでここでは手法１の出力のみをチェックサムと呼ぶことにします。

性能評価対象アルゴリズム

探すとアルゴリズムいっぱい出てきます。
RIPEMDというハッシュ関数もあるみたいですが、検索してもあまり情報が出てこないので除外。

仕事柄Unityを使うことが多いので、Unity(C#)で簡単に使える下記ハッシュ関数３つ（MD5/SHA-1/SHA-2)をチョイス。
プラス、AssetBundleでも使うCRC-32も追加。（C#にはCRC-32を求める関数がないので落ちてるコードで検証）

ということで以下の５ケースに絞りました。

1. CRC-32 : 32bit
2. MD5 : 128bit
3. SHA-1: 160bit
4. SHA-256: 256bit
5. SHA-512: 512bit

SHA-2は256だけで本来十分ですが、処理負荷がどれぐらいか気になったので参考までに追加。

FNVという、ハッシュ関数もあるようですが、CRCと同じような処理内容かつ汎用性がないということで除外。

Unity上での実行結果

動作確認Unity

• Unity 5.4.0f3

検証内容

1KB、1MB、10MB、100MBのランダム生成したファイルを用意。
（中身がランダムデータである必要もないとは思いますが、一応。）

まずファイルをメモリに読み込み、読み込んだメモリに対してチェックサム・ハッシュ値を取得。
使用APIは、MD5/SHA1/SHA256/SHA512CryptoServiceProvider。CRC-32は独自実装。

データ読み込み時間は"I/O"として計測。各セルの単位はミリ秒。

Unity Editor/macOS (MacBook Air 1.8 GHz Intel Core i7)

	I/O	CRC32	MD5	SHA-1	SHA-256	SHA-512
1KB	2	0	2	1	1	1
1MB	5	7	12	25	56	135
10MB	42	82	154	244	577	1326
100MB	482	868	1537	2432	5810	13491

参考値

md5コマンドを実行した場合、10MBで52ms。100MBで400ms。
shasum -a 256コマンドを実行した場合、10MBで231ms。100MBで1063ms。
shasum -a 512コマンドを実行した場合、10MBで143ms。100MBで1023ms。

rubyでDigest::MD5を使用した場合、10MBで251ms。100MBで730ms。
rubyでDigest::SHA256を使用した場合、10MBで429ms。100MBで1286ms。
rubyでDigest::SHA512を使用した場合、10MBで315ms。100MBで955ms。

iOS (iPhone 6s)

	I/O	CRC32	MD5	SHA-1	SHA-256	SHA-512
1KB	6	0	0	0	0	0
1MB	4	12	12	12	22	17
10MB	29	140	127	121	222	183
100MB	234	1359	1255	1198	2206	1812

記載しませんでしたが、2MBでも1MBと同じような結果に。
データ量が比較的小さい場合は、想定よりもパフォーマンスが出るかもです。

Android (Nexus 5x)

Monoビルド

	I/O	CRC32	MD5	SHA-1	SHA-256	SHA-512
1KB	28	1	6	5	4	5
1MB	31	10	13	26	40	221
10MB	174	103	134	267	400	2214
100MB	635	1050	1351	2621	4005	22188

IL2CPPビルド

	I/O	CRC32	MD5	SHA-1	SHA-256	SHA-512
1KB	2	0	0	0	0	0
1MB	18	15	18	18	19	35
10MB	175	102	145	169	192	349
100MB	588	1045	1483	1722	1947	3662

※AndroidはSDカードからの読み込みで計測。

まとめ

計測結果からの考察

• MD5が一番バランス良さそう。
  • CRC-32はC#実装のためか、MD5と処理負荷がほとんど変わらない結果に（iOSに至っては逆転）
  • CRC-32をネイティブ実装すれば高速化可能？
• 計算負荷もファイル読み込み時間もファイルサイズに正比例。
  • 1KB時にほとんどロード時間がかからないので、この３機種についてはファイル数よりも総ファイルサイズが支配的。
• SHA-256はMD5の2〜４倍の計算負荷。
• なぜかSHA-512の方がSHA-256より負荷が低いケースがある。（そういうもの？）
• C#のハッシュ関数APIではパフォーマンスが出し切れてない？機種固有APIを駆使するともっと高速化できるかも？
• IL2CPPビルドにすると、SHA-1/SHA-2の性能が上がった。

付録１：その他ハッシュの取得方法メモ

macOSでのCRCやハッシュ値の取得

crc32 /path/to/file
md5 /path/to/file
shasum -a 256 /path/to/file

Windows Powershellでのハッシュ値の取得

Get-FileHash /path/to/file -Algorithm MD5
Get-FileHash /path/to/file -Algorithm SHA256

Rubyでのハッシュ値の取得

md5.rb

require "digest/md5"
puts Digest::MD5.file(ARGV[0])

sha256.rb

require 'digest/sha2'
puts Digest::SHA256.file(ARGV[0]).hexdigest

・・・案外CRC-32は標準機能で提供されないものなのでしょうか。

付録２：検証C#スクリプト（部分抜粋）

こんな感じでGameObjectに貼りました。(CRC32の実装は割愛）
※そのままではビルドできませんので注意。

あと、今回は読み込み時間は分けて考えたかったので、データのロードとハッシュ計算を別々に分けました。
ComputeHashにFileStreamを突っ込むと、オーバーラップで読み込み時間は消えるかもしれません。

Test.cs

public class Test : MonoBehaviour {

    System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch ();

    void Start () {
        var da = new Dictionary<string, string>() {
            {"1KB",   "random_0.dat"},
            {"1MB",   "random_1.dat"},
            {"10MB",  "random_10.dat"},
            {"100MB", "random_100.dat"},
        };
        var ha = new Dictionary<string, HashAlgorithm>() {
            { "CRC32", new Hoge.CRC32() },
            { "MD5", new MD5CryptoServiceProvider() },
            { "SHA1", new SHA1CryptoServiceProvider() },
            { "SHA256", new SHA256CryptoServiceProvider() },
            { "SHA512", new SHA512CryptoServiceProvider() },
        };
        long[] ms = new long[ha.Count+1];

        #if !UNITY_EDITOR && UNITY_ANDROID
            string dataRoot = "/sdcard";
        #else
            string dataRoot = Application.streamingAssetsPath;
        #endif

        foreach (KeyValuePair<string, string> d in da) {
            int i=0;
            sw.Start(); /*  読み込み時間計測開始 */
            byte[] bs = LoadFile(dataRoot+"/"+ d.Value);
            sw.Stop();  /*  読み込み時間計測終了 */
            ms[i++] = sw.ElapsedMilliseconds; sw.Reset();
            foreach (KeyValuePair<string, HashAlgorithm> h in ha)
            {
                sw.Start(); /*  ハッシュ・チェックサム計算計測開始 */
                h.Value.ComputeHash(bs);
                sw.Stop(); /*  ハッシュ・チェックサム計算計測終了 */
                ms[i++] = sw.ElapsedMilliseconds; sw.Reset();
            }
            UnityEngine.Debug.Log ("|" + d.Key + "|" + ms[0] + "|" + ms[1] + "|" + ms[2] + "|" + ms[3] + "|" + ms[4] + "|" + ms[5] + "|");
        }
    }

    private byte[] LoadFile(string path) {
        System.IO.FileStream fs = new System.IO.FileStream(
            path,
            System.IO.FileMode.Open,
            System.IO.FileAccess.Read);
        byte[] bs = new byte[fs.Length];
        fs.Read(bs, 0, bs.Length);
        fs.Close();
        return bs;
    }
}

SHA256CryptoServiceProviderクラスは、そのままだと見つからないので注意。@Unity5.4
Player Settignsで、API Compatibility Levelを「.NET 2.0」に変更する必要があります。

付録３：ランダムデータの作成

検証で使用したランダムデータは、macOSからddコマンドで作成しました。
こちらのページを参照させていただきました。

プロンプトから以下を複数行実行すると1MB/10MB/100MBのデータが出来上がります。(1KBは手打ちで・・・)

> for i in 1 10 100                                                                                                                                            do
dd if=/dev/urandom of=random_$i.dat count=$i bs=1048576
done

bsの引数に1Mと打ち込むと dd: bs: illegal numeric value と出てしまったので、バイトで指定しました。