SHAの仕様と実装比較(SHA-1編)

とあるソースコードを追っていたらsha_init()やsha_transform()をコールしている部分に遭遇し、飛んでみたら謎すぎた(実際は全く謎ではない)ので、SHA(Secure Hash Algorithm)について色々と調べてみました。

その調査の結果を、備忘録として残しておくための記事です。
長くなることを避けるため、あくまでSHAの仕様とその実装を見比べる程度にします。

今回はSHA-1編です。

飛んでみて謎に遭遇したのは、Linux Kernelのソースコードに含まれるlib/sha1.cです。

謎ですねー…。
0x67452301とか、0xefcdab89とか。

というわけで、色々とググっているうちに、SHAの仕様がFIPS 180-2として公開されていることが分かりました(FIPS 180-2は歴史的な目的から残されているようです。)。
新しいバージョンがFIPS 180-4として公開されています。

FIPS 180-2(or 4)には、SHA-1だけでなく、SHA-256、SHA-512等々についても記述されています。

SHAの共通点

SHA-1、SHA-256、SHA-512等々ありますが、以下の点はSHAのアルゴリズムに共通していると言えそうです。(抽象的過ぎるかもしれませんが)。

  1. ブロックサイズやWordサイズが決まっている
  2. ハッシュの初期値がある
  3. いくつかの定数がある
  4. 使用する関数がある
  5. メッセージスケジュールを生成する
  6. ハッシュ値を計算する

Wordの操作

Word(SHAに依存する32bitか64bitの1グループ)の操作としては、ビット単位での和、積、排他的論理和、否定、2^w(wは1Wordのビット数)を法とする加算、左右のビットシフトに加え、以下の操作が定義されています。

bitwise_operation

2番目と3番目の操作は循環シフトで、Linuxのソースコードではinclude/linux/bitops.hに、以下のように定義されています。

103 /**
104  * rol32 - rotate a 32-bit value left
105  * @word: value to rotate
106  * @shift: bits to roll
107  */
108 static inline __u32 rol32(__u32 word, unsigned int shift)
109 {
110         return (word << shift) | (word >> (32 - shift));
111 }
112
113 /**
114  * ror32 - rotate a 32-bit value right
115  * @word: value to rotate
116  * @shift: bits to roll
117  */
118 static inline __u32 ror32(__u32 word, unsigned int shift)
119 {
120         return (word >> shift) | (word << (32 - shift));
121 }
122

事前処理

SHAではハッシュ値を計算する前に、事前処理として対象のメッセージを512か1024(SHAに依存)bitの倍数にパディングし、パディングしたメッセージをN個の512か1024(SHAに依存)bitごとにブロックとして分ける必要があります。
N個に分けられたブロックは、16個の32か64(SHAに依存)bitに分けられて処理されます。
sha_transform()に渡される引数は、この事前処理が終わっている状態です。

SHA-1の仕様と実装の比較

それでは前置きが長くなってしまいましたが、SHA-1の仕様とその実装を見比べてみます。

1.ブロックサイズやWordサイズ

SHA-1のブロックサイズは512bits、Wordサイズは32bitsです。
各ブロックは16個の32bitに分けられて処理されます。

2.ハッシュの初期値

FIPS 180-4で記述されているSHA-1の初期値は以下です。
SHA-1_initial_value

lib/sha1.cのsha_init()で設定されている値と一致します。

189 /**
190  * sha_init - initialize the vectors for a SHA1 digest
191  * @buf: vector to initialize
192  */
193 void sha_init(__u32 *buf)
194 {
195         buf[0] = 0x67452301;
196         buf[1] = 0xefcdab89;
197         buf[2] = 0x98badcfe;
198         buf[3] = 0x10325476;
199         buf[4] = 0xc3d2e1f0;
200 }

3.定数

FIPS 180-4で記述されているSHA-1の定数は以下です。
SHA-1_constants

lib/sha1.cで定義されているマクロに該当する値があります。

 59 #define T_0_15(t, A, B, C, D, E)  SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )
 60 #define T_16_19(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )
 61 #define T_20_39(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0x6ed9eba1, A, B, C, D, E )
 62 #define T_40_59(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, ((B&C)+(D&(B^C))) , 0x8f1bbcdc, A, B, C, D, E )
 63 #define T_60_79(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) ,  0xca62c1d6, A, B, C, D, E )

T_0_15とT_16_19で同じ値が渡されていることが分かります。

4.関数

FIPS 180-4で記述されているSHA-1の関数は以下です。
SHA-1_functions

この1番目と3番目の関数に一致しそうな箇所がなく困ったのですが、WikipediaのSHA-1の記述によると、それぞれ代替方法があるようです。
SHA-1_alternatives

上記のSHA_ROUNDの3番目の引数にしている箇所を確認すると、Linuxの実装では、この0-19ラウンドのalternative 1と40-59ラウンドのalternative 3が採用されているようです。

5.メッセージスケジュールの生成

FIPS 180-4では、SHA-1のハッシュ値の計算方法が2種類記述されており、Linuxでは後者の方を採用しているようです。
後者のメッセージスケジュールの生成部分は以下のようになっています。
SHA-1_message_schedule

lib/sha1.cでSHA_ROUNDの2番目の引数に指定されているマクロに該当する処理があります。

 44 /* This "rolls" over the 512-bit array */
 45 #define W(x) (array[(x)&15])
 46
 47 /*
 48  * Where do we get the source from? The first 16 iterations get it from
 49  * the input data, the next mix it from the 512-bit array.
 50  */
 51 #define SHA_SRC(t) get_unaligned_be32((__u32 *)data + t)
 52 #define SHA_MIX(t) rol32(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)

6.ハッシュ値の計算

FIPS 180-4に記述されている方法は、以下です。
SHA-1_computing

lib/sha1.cでの該当部分は以下です。

 54 #define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \
 55         __u32 TEMP = input(t); setW(t, TEMP); \
 56         E += TEMP + rol32(A,5) + (fn) + (constant); \
 57         B = ror32(B, 2); } while (0)

TEMPにメッセージスケジュールWiを入れておくことで、EにはTの値が入ります。
また、ROTL^30(x)はROTR^2(x)と等価です。

FIPS 180-4では変数の中身を1つずつずらすような処理が入っていますが、Linuxでは引数の順番を変えていくことで代替しているようです。

 92         T_0_15( 0, A, B, C, D, E);
 93         T_0_15( 1, E, A, B, C, D);
 94         T_0_15( 2, D, E, A, B, C);
 95         T_0_15( 3, C, D, E, A, B);
 96         T_0_15( 4, B, C, D, E, A);
 97         T_0_15( 5, A, B, C, D, E);
 98         T_0_15( 6, E, A, B, C, D);
 99         T_0_15( 7, D, E, A, B, C);
100         T_0_15( 8, C, D, E, A, B);
101         T_0_15( 9, B, C, D, E, A);
102         T_0_15(10, A, B, C, D, E);
103         T_0_15(11, E, A, B, C, D);
104         T_0_15(12, D, E, A, B, C);
105         T_0_15(13, C, D, E, A, B);
106         T_0_15(14, B, C, D, E, A);
107         T_0_15(15, A, B, C, D, E);

変数のBからC、EからAに移る時に値が変っていくイメージです。

このような処理を0-79ラウンドまで行い、32bitのA、B、C、D、Eの5つの変数の値を並べることで、160bitのメッセージダイジェストが得られます。

なかなか大変ですね。

以上がSHA-1の仕様とその実装の比較でした。
初見では謎にしか見えなかった内容が、仕様と実装を比較していくうちに理解することができました。
この記事がどなたかの理解の役に立てば幸いです。

また、折角、FIPS 180-4を読んだので、SHA-256とSHA-512についても仕様と実装の比較を行う予定です。
次回はSHA-256編です。

Share on FacebookTweet about this on TwitterShare on Google+Share on TumblrEmail this to someonePrint this page

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

*