とあるソースコードを追っていたら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のアルゴリズムに共通していると言えそうです。(抽象的過ぎるかもしれませんが)。
- ブロックサイズやWordサイズが決まっている
- ハッシュの初期値がある
- いくつかの定数がある
- 使用する関数がある
- メッセージスケジュールを生成する
- ハッシュ値を計算する
Wordの操作#
Word(SHAに依存する32bitか64bitの1グループ)の操作としては、ビット単位での和、積、排他的論理和、否定、2^w(wは1Wordのビット数)を法とする加算、左右のビットシフトに加え、以下の操作が定義されています。
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の初期値は以下です。
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の定数は以下です。
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の関数は以下です。
この1番目と3番目の関数に一致しそうな箇所がなく困ったのですが、WikipediaのSHA-1の記述によると、それぞれ代替方法があるようです。
上記のSHA_ROUNDの3番目の引数にしている箇所を確認すると、Linuxの実装では、この0-19ラウンドのalternative 1と40-59ラウンドのalternative 3が採用されているようです。
5．メッセージスケジュールの生成#
FIPS 180-4では、SHA-1のハッシュ値の計算方法が2種類記述されており、Linuxでは後者の方を採用しているようです。
後者のメッセージスケジュールの生成部分は以下のようになっています。
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に記述されている方法は、以下です。
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編です。