とあるソースコードを追っていたら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編です。