暗号アルゴリズムのなかのハッシュを実装してみる MD5からSHA-3まで
デジタルな暗号の実装はいろいろあるのだけど、中身はあまり把握していないなということで、暗号やハッシュの実装を見てみようと思いいくつか実装してみた。
暗号の中でも使われていることもあり、実装が簡単そうなのがハッシュ関数というわけなのか、最初に目についたからかハッシュのMD4、MD5からSHA-1、SHA-2、SHA-3を実装してみた。GitHubに公開してみたが、結局他の実装はあまり見なかったかもしれない。
入門程度に詳細は省略するのでソースかWikipediaでも見てもらえればハッシュの単純さがわかる。
ハッシュとは、データの固まりに固有の番号(乱数っぽいもの)を生成するアルゴリズムで、ダウンロードしたデータが正確かどうか判定するために使ってみたりする。
昔はチェックサムだとか、CRCだとかがあったところの延長線上でもあり。 結果が分散している、結果からデータを逆に辿れないというのもポイント。
構造は、入力データを512ビットや1024ビット毎に区切り、ビット演算を繰り返した結果256ビットくらいの結果が出力される。
1ビットの違いが出力のほぼ全ビットに影響するので同じ値を探すのも難しい。
入門レベルで書かれているものでは、1回の暗号の構造については書かれているが、初期値がどうなるとか繰り返しがどこからどこまでででどうなるのかなど、よくわからないことも多々ある。
実装するには、基本的にインターネット関連の情報はRFCを読めば見つかる。MD4、MD5などの廃止された古いものもしっかり残っているのはRFCのよいところ。SHA-3はまだRFCにはなさそうだ。日本語化されたものもIPAなどのサイトで見つかるかもしれない。
内部状態を持っている MD5の場合 32bit a,b,c,d で128bit、SHA2-256はa,b,c,d,e,f,g,hで256bit、SHA2-512では64bitの8つで1024bitなど。初期値は0ではない(MD5以降)。
暗号ではほぼ固定だけれど、これの初期値が変えられるものもあり、initial vector といってIVなどと略してよく見られるので覚えておくといい。暗号で使われる鍵とは別のもの。
入力はブロック単位(512bitや1024bit、SHA-3では異なる)。
ブロック(512bit), vector (256bit) → ハッシュ計算(4x4回くらい) → vector の繰り返し。
SHA-3の場合はvectorがブロックより長い。 vectorの先頭にブロックをXORで足していくだけ。
vectorは5x5x64の3次元配列っぽくなっていて、いろいろシャッフルする。逆計算は無理っぽい。
ブロックの単位は512bitや1024bitなので、足りない部分は最後のブロックにpaddingといって空白を埋める。そのあとに長さのデータなどを足してちょうど512の倍数ビットになるようにして最後のブロックをハッシュ計算することになる。元のデータが512ビットの倍数丁度の場合にも終了フラグや長さなどのデータが必要なのでパディングが入る。
SHA-1, SHA-2 ではブロックはシフトなどしたデータで数倍にふくらませてから。
疑似乱数っぽい列を持っているか生成して使う(MD2,MD5,SHA-2,SHA-3)。MD4、SHA-1は固定。
ブロックを入力し、内部状態を変化させ、最終的な内部状態を切り出してハッシュ値とする。ブロック長より短い。
疑似SHA2 (256bit)
内部状態(vector) H[32x8(256)bit]
hash(block[8x64(512)bit])
{
a,b,c,d,e,f,g,h = H[0,1,2,3,4,5,6,7]
block をint列に写し、4倍くらいにする
表に書けそうな計算 x 64回 ( abcdefghにblockと疑似乱数的なものを加える)
H[0,1,2,3,4,5,6,7] += a,b,c,d,e,f,g,h
}
H[0...] += a...
があるのでHからaが取り出せなくなり戻れない。
データ並びのバイト列やビット列を上から数えるか下から数えるかは各プロトコルでバラバラなので仕様から読み解くか実装してみて気づく罠あり。
計算結果を加算していく過程(H[0,...] = a,... )があるので基本的に戻れない? 戻れそうな気がしてくるので謎。逆に戻る過程のabcdの初期値が出せないので安全なのだろうけど、よくわからない。
変数の列を入れ換えているようなところは、入れ換えているのではなく列の先頭から順番に同じ処理をしているだけのものを処理しやすく組み立てているだけのものもあり、これがMD5、SHA-1などでは何回繰り返すというふうに誤魔化されている。MD5では変数が4つあり、1処理16回まわすので、abcd各4回まわしているくらいの攪拌量になる。SHA-2では8回か。
変数ではなく入力をシフトする作りにしてみれば、a,b,c,... に対して同じことをしている様子がわかる。 最終的にどちらが速いのかは最適化次第だと思うのでMD5は変な実装にしてみた。
単体で使うこともJavaに登録して使うこともできるっぽい形になった。古い形式はオプション変えないと使えなくなっているのでその代わりに使ってみるのもいい。
RIPEMDみたいなのも作ってみる予定。 GitHubへ。
乱数の生成のようなものもあり、最終的なところで暗号かな。
次回は暗号のざっくり?
暗号の中でも使われていることもあり、実装が簡単そうなのがハッシュ関数というわけなのか、最初に目についたからかハッシュのMD4、MD5からSHA-1、SHA-2、SHA-3を実装してみた。GitHubに公開してみたが、結局他の実装はあまり見なかったかもしれない。
入門程度に詳細は省略するのでソースかWikipediaでも見てもらえればハッシュの単純さがわかる。
ハッシュとは、データの固まりに固有の番号(乱数っぽいもの)を生成するアルゴリズムで、ダウンロードしたデータが正確かどうか判定するために使ってみたりする。
昔はチェックサムだとか、CRCだとかがあったところの延長線上でもあり。 結果が分散している、結果からデータを逆に辿れないというのもポイント。
構造は、入力データを512ビットや1024ビット毎に区切り、ビット演算を繰り返した結果256ビットくらいの結果が出力される。
1ビットの違いが出力のほぼ全ビットに影響するので同じ値を探すのも難しい。
入門レベルで書かれているものでは、1回の暗号の構造については書かれているが、初期値がどうなるとか繰り返しがどこからどこまでででどうなるのかなど、よくわからないことも多々ある。
実装するには、基本的にインターネット関連の情報はRFCを読めば見つかる。MD4、MD5などの廃止された古いものもしっかり残っているのはRFCのよいところ。SHA-3はまだRFCにはなさそうだ。日本語化されたものもIPAなどのサイトで見つかるかもしれない。
- RFC 1319 MD2
- RFC 1320 MD4
- RFC 1321 MD5
- RFC 3174,FIPS 180-1 SHA-1
- RFC 6234,FIPS PUB 180-4 SHA-2, HMAC,HKDF
- FIPS PUB 202 SHA-3
ハッシュの基本
SHA-2までとSHA-3では違うので別々に。内部状態を持っている MD5の場合 32bit a,b,c,d で128bit、SHA2-256はa,b,c,d,e,f,g,hで256bit、SHA2-512では64bitの8つで1024bitなど。初期値は0ではない(MD5以降)。
暗号ではほぼ固定だけれど、これの初期値が変えられるものもあり、initial vector といってIVなどと略してよく見られるので覚えておくといい。暗号で使われる鍵とは別のもの。
入力はブロック単位(512bitや1024bit、SHA-3では異なる)。
- 入力 ブロック
- 内部状態 vector
- 出力 vector から切り取ったハッシュ値
ブロック(512bit), vector (256bit) → ハッシュ計算(4x4回くらい) → vector の繰り返し。
SHA-3の場合はvectorがブロックより長い。 vectorの先頭にブロックをXORで足していくだけ。
vectorは5x5x64の3次元配列っぽくなっていて、いろいろシャッフルする。逆計算は無理っぽい。
最後のブロック
ブロックの単位は512bitや1024bitなので、足りない部分は最後のブロックにpaddingといって空白を埋める。そのあとに長さのデータなどを足してちょうど512の倍数ビットになるようにして最後のブロックをハッシュ計算することになる。元のデータが512ビットの倍数丁度の場合にも終了フラグや長さなどのデータが必要なのでパディングが入る。
計算
基本はvector を複製してブロックを混ぜ込み、結果をvecrtorと足してvectorに戻す。SHA-1, SHA-2 ではブロックはシフトなどしたデータで数倍にふくらませてから。
疑似乱数っぽい列を持っているか生成して使う(MD2,MD5,SHA-2,SHA-3)。MD4、SHA-1は固定。
ブロックを入力し、内部状態を変化させ、最終的な内部状態を切り出してハッシュ値とする。ブロック長より短い。
疑似SHA2 (256bit)
内部状態(vector) H[32x8(256)bit]
hash(block[8x64(512)bit])
{
a,b,c,d,e,f,g,h = H[0,1,2,3,4,5,6,7]
block をint列に写し、4倍くらいにする
表に書けそうな計算 x 64回 ( abcdefghにblockと疑似乱数的なものを加える)
H[0,1,2,3,4,5,6,7] += a,b,c,d,e,f,g,h
}
H[0...] += a...
があるのでHからaが取り出せなくなり戻れない。
データ並びのバイト列やビット列を上から数えるか下から数えるかは各プロトコルでバラバラなので仕様から読み解くか実装してみて気づく罠あり。
ハッシュの裏
計算している部分はビットの反転、シフト演算などが主な計算方法で、ビット操作ではXORやNOTだけでなく、データ量の減りそうなANDやORも使われているのだが、処理後のデータは内部状態の1つしか変化させないので他のデータは残っていて容易に逆計算で復元可能。(SHA-2など)計算結果を加算していく過程(H[0,...] = a,... )があるので基本的に戻れない? 戻れそうな気がしてくるので謎。逆に戻る過程のabcdの初期値が出せないので安全なのだろうけど、よくわからない。
何回
入力はブロック単位で処理するので、細切れな入力を蓄積してまとめるところから作るのがいいが、そのあたりの作りが各者の最適化のしどころか。JavaならStreamを貯めてBlockの長さ以上ならループへ、くらいの形にすればいいのでStreamをBlockに変換する処理としてまとめてみたりもする。abcdに同じことしてみる
変数の列を入れ換えているようなところは、入れ換えているのではなく列の先頭から順番に同じ処理をしているだけのものを処理しやすく組み立てているだけのものもあり、これがMD5、SHA-1などでは何回繰り返すというふうに誤魔化されている。MD5では変数が4つあり、1処理16回まわすので、abcd各4回まわしているくらいの攪拌量になる。SHA-2では8回か。
変数ではなく入力をシフトする作りにしてみれば、a,b,c,... に対して同じことをしている様子がわかる。 最終的にどちらが速いのかは最適化次第だと思うのでMD5は変な実装にしてみた。
完成品
最終的に作ったハッシュはMD2,MD4,MD5,SHA-1,SHA-2,SHA-3各シリーズとKeccakそれとCRC。単体で使うこともJavaに登録して使うこともできるっぽい形になった。古い形式はオプション変えないと使えなくなっているのでその代わりに使ってみるのもいい。
RIPEMDみたいなのも作ってみる予定。 GitHubへ。
ハッシュの次、暗号になると
ハッシュの次はHMACなどがあるのでそういうのも見てみるといい。HMACや暗号では鍵の引き延ばしとかいろいろ別の要素が出てくる。乱数の生成のようなものもあり、最終的なところで暗号かな。
次回は暗号のざっくり?
コメント
コメントを投稿