wiz.code

パディング処理

データ補足の不都合

ハッシュ計算処理を行う前にパディング処理で帳尻合わせを行います。 ハッシュ計算処理の中でパディング処理を行う方法もありますが、処理が複雑になってしまうのでここはFIPSに示された手順どおりに進めていきます。

前述したようにパディング処理とは、そのあとのハッシュ計算処理の制約である「64Byteで割り切る」ための帳尻合わせです。 元のデータが50Byteしかなかった場合は、不足している14Byteを補って64Byteにしなければなりません。 かといって、単純に足りない分を補えば良いわけではありません。 理由は、入力データの長さが異なるのに同じデータが生成されてしまう「ハッシュ衝突」が発生してしまうからです。 例えば、次のような入力データ(16進数表記)があったとします。

0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677

このデータは全体で40Byteです。 ここから不足分である24Byteを0で埋めたとします。すると、次のようになります。

0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

これでめでたく64Byte、つまりメッセージブロック1つ分になりました。 しかし、「入力データがもともとこの状態だった場合」はどうでしょう。 あるいは数Byteだけ短かった場合は…?次の例を見てください。

データ1(40Byte)
0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677
データ2(50Byte)
0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677 0000 0000 0000 0000 0000
データ3(64Byte)
0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

このような本来異なる3つの入力データがあったとします。 これを単純に不足分だけ補うと…

データ1(40Byte → 64Byte)
0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
データ2(50Byte → 64Byte)
0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
データ3(64Byte → 64Byte)
0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

このように入力データが同じになり、結果的に得られるメッセージダイジェストも同じになってしまいます。 パディング処理では「不足分のデータを補っても必ず異なるデータになるようにする」ことが不可避となります。

64Byteに合わせる方法

これを解決する最も簡単な方法が、もともとの入力データの長さを記録することです。 こうすれば、例え不足分を補ったとしても、元の入力データの長さが違うので完全に一致することはありません。

SHA256のパディング処理では、入力データの直後に1bitを置いてから、64Byteで割り切れるサイズに拡張し、さらに拡張した最後の部分に入力データのビット数を64bit値(8Byte)で記録するようにしています。 これで、長さが異なるのに同じデータが生成される、ということはなくなります。

ところが、この処理を行うことでひとつ不都合が発生します。 例えば64Byteぴったりの入力データだった場合、入力データのビット数を記録するとその分だけデータが伸び、64Byteを超えてしまいます。 しかしこれは「入力データのビット長を記録する猶予がなかった場合は、次のブロックの末端に記録する」という条件を加えることで万事解決です。

先ほどの3つのデータをそれぞれパディング処理すると、次のようになります。

データ1(40Byte → 64Byte)
0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677 8000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0140
データ2(50Byte → 64Byte)
0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677 0000 0000 0000 0000 0000 8000 0000 0000 0000 0000 0000 0190
データ3(64Byte → 128Byte)
0000 1111 2222 3333 4444 5555 6666 7777 8888 9999 aaaa bbbb cccc dddd eeee ffff
0011 2233 4455 6677 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
8000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0200

(赤字が補った部分、青文字が入力データのビット数を記録した部分)

データ3は入力データのビット数を記録すると64Byteを超えてしまうので、メッセージブロックをひとつ増やしています。

これで、メッセージブロック処理を施す準備が整いました。