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


## 経緯

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

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

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

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

| | 手法 | 信頼性 | 処理負荷 | 出力ビット数 | 特徴 |
|:-:|:-:|:-:|:-:|:-:|:-:| 
|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
- MD5 : 128bit
- SHA-1: 160bit
- SHA-256: 256bit
- 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コマンドで作成しました。
[こちらのページ](http://tekitoo.sakura.ne.jp/2010/01/05/dd%E3%82%B3%E3%83%9E%E3%83%B3%E3%83%89%E3%81%A7%E5%9B%BA%E5%AE%9A%E9%95%B7%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E4%BD%9C%E6%88%90/)を参照させていただきました。

プロンプトから以下を複数行実行すると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` と出てしまったので、バイトで指定しました。