SHA-crypt

パスワード用のハッシュ系

Unix crypt using SHA-256 and SHA-512

Version: 0.6 2016-8-31 の翻訳(仮)

暗号化ベースのソリューションは、セキュリティの向上には繋がらないようです（反証はありません）。また、CPU負荷の増加は、ハッシュサムベースのソリューションに複雑さを加えることで補うことができます。そのため、UnixおよびLinuxベンダーのグループがこの方法を採用することに決定しました。

SHAハッシュサム関数は十分にテストされています。SHA-256およびSHA-512アルゴリズムを選択すると、生成される出力サイズはそれぞれ32バイトまたは64バイトになります。これは、少なくとも今後数年間はレインボーテーブルの使用を困難にし、あるいは不可能にする大規模な出力セットの要件を満たしています。

MD5ベースのパスワードハッシュで使用されるアルゴリズムも一般的に安全であると考えられているため、SHAベースのパスワードハッシュソリューションに同様のアルゴリズムを使用しても大きな問題はありません。アルゴリズムの一部は変更されており、MD5ベースの実装における誤りと考えられていた箇所が修正された例もあります。

既存のシステムが既にMD5ベースのソリューションをサポートしている場合、そのシステムへの統合は容易です。 MD5 ベースの方法が導入されて以来、拡張パスワード形式が使用されています。

$<ID>$<SALT>$<PWD>

パスワードがこの形式でない場合は、旧式のDES暗号化パスワードです。パスワードがこの形式である場合、IDは使用されている暗号化方式を識別し、パスワード文字列の残りの部分の解釈方法を決定します。現在、以下のID値が使用されています。

table:ID

ID Method

--- ----------------------------

1 MD5 (Linux, BSD)

2a Blowfish (OpenBSD)

md5 Sun MD5

新しい SHA-256 および SHA-512 方式では、次の値が選択されます。

table:ID

ID Method

--- ----------------------------

5 SHA-256

6 SHA-512

SHAベースの方式では、SALT文字列は最大16文字の単純な文字列です。MD5ベースの実装では最大8文字です。Sunがプラガブル暗号実装に実装した発明に基づく拡張機能を1つ許可することが決定されました。SALT文字列が

rounds=<N>$

ここで、Nは符号なし10進数で、Nの数値は使用されるアルゴリズムを変更するために使用されます。後述しますが、SHAベースのアルゴリズムには、任意の回数実行できるループが含まれています。実行されるラウンド数が多いほど、CPUの負荷が高くなります。これは、コンピューティング能力の向上に伴うブルートフォース攻撃への対抗策として役立つ可能性のある安全機構です。

どちらのアルゴリズムも、デフォルトのラウンド数は5,000です。一方で、最低限のセキュリティと安定性を確保するため、Nの最小値と最大値が強制的に設定されます。

Nの最小値 = 1,000

Nの最大値 = 999,999,999

Nを最小値より小さい値に指定した場合は1,000ラウンド、10億以上の値に指定した場合は999,999,999ラウンドが使用されます。これらの場合、crypt関数によって生成される出力文字列は、入力されたソルト文字列と同じソルトにはなりません。これは、出力には正しく制限されたラウンド数が使用されるためです。

パスワード文字列のPWD部分は、実際に計算されるパスワードです。この文字列のサイズは固定です。

SHA-256：43文字

SHA-512：86文字

出力は、Base64エンコードされたダイジェストで構成されます。したがって、パスワード文字列の最大長は次のようになります（C言語表現の最後のNULバイトを除く）。

SHA-256 80文字

SHA-512 123文字

crypt関数のsaltパラメータに渡す入力文字列は、実際にははるかに長くなる可能性があります。ただし、salt文字列は最大16文字に切り捨てられるため、出力文字列のサイズは制限されます。

パスワードハッシュ化に使用されるアルゴリズムは、Linux/BSD MD5実装で使用されているアルゴリズムに準拠しています。以下では、そのアルゴリズムについて、違いを明確に示しながら説明します。SHA-256とSHA-512はどちらも同じアルゴリズムを使用します。唯一の違いは、MD5版とも異なり、既存のダイジェストを別のダイジェスト計算の入力として使用するケースです。この場合、入力サイズ（つまり、ダイジェストのサイズ）は異なります。MD5の場合、ダイジェストは16バイト、SHA-256の場合、32バイト、SHA-512の場合、64バイトです。以下の説明では、この違いについてはこれ以上触れません。

ハッシュダイジェストを作成するための3つの基本要素を使用するアルゴリズム：

ダイジェストを開始する。これにより、ハッシュ関数に必要なデータ構造と初期状態が設定されます。

ダイジェストにバイトを追加します。これは複数回実行できます。ハッシュ関数の1ラウンドに必要なバイト数が追加された場合のみ、処理が行われます。必要なバイト数に達していない場合は、バイトはそのままキューに入れられます。SHA-256とSHA-512の場合、サイズはそれぞれ64バイトと128バイトです。

コンテキストを終了します。この操作により、現在キューに入れられているバイトはハッシュ関数の仕様に従ってパディングされ、その結果が処理されます。最終的なダイジェストが計算され、使用可能になります。

アルゴリズムでソルト文字列を追加する場合、実際には16文字に切り捨てられたソルト文字列を追加することを意味します。

アルゴリズムで文字列を追加する場合、文字列のC言語表現の終端のNULバイトは追加されません。

SHA-256/SHA-512 を用いた暗号化アルゴリズム：

1. ダイジェスト A を開始

2. パスワード文字列をダイジェスト A に追加

3. ソルト文字列をダイジェスト A に追加。これは、囲み文字「$」、マジックプレフィックス $5$ と $6$、rounds=<N> 指定を除いたソルト文字列そのものです。

注：MD5 アルゴリズムは $1$ プレフィックスを追加しました。これは定数文字列であり、セキュリティを強化するものではなく、プレーンテキスト攻撃を許す可能性があるため、不要とされています。rounds=<N> 指定は追加されるべきではないため、これも不整合の原因となります。

4. ダイジェストBを開始する

5. ダイジェストBにパスワードを追加する

6. ダイジェストBにソルト文字列を追加する

7. ダイジェストBに再度パスワードを追加する

8. ダイジェストBを終了する

9. パスワード文字列の32バイトまたは64バイトのブロックごとに（C言語表現の終端のNULを除く）、ダイジェストBをダイジェストAに追加する

10. パスワード文字列の残りのNバイトについて、ダイジェストBの最初のNバイトをダイジェストAに追加する

11. パスワード文字列の長さを2進数で表した各ビットについて、最上位の1桁目まで（数値1から最下位のビット位置まで）以下の処理を実行します。

a) 桁が1の場合、ダイジェストBをダイジェストAに追加します。

b) 桁が0の場合、パスワード文字列を追加します。

注：この手順はMD5アルゴリズムとは大きく異なります。これにより、ランダム性が向上します。

12. ダイジェスト A を終了

13. ダイジェスト DP を開始

14. パスワードの各バイト（文字列の C 表現における終端の NUL バイトを除く）について

パスワードをダイジェスト DP に追加

15. ダイジェスト DP を終了

16. パスワードと同じ長さのバイトシーケンス P を生成する。ただし、

a) パスワード文字列の 32 バイトまたは 64 バイトの長さの各ブロックについて、ダイジェスト DP 全体を使用する。

b) 残りの N バイト（最大 31 バイトまたは 63 バイト）については、ダイジェスト DP の最初の N バイトを使用する。

17. ダイジェスト DS を開始

ソルトをダイジェスト DS に追加

19. ダイジェスト DS を終了

20. ソルト文字列と同じ長さのバイトシーケンス S を生成する。ただし、

a) 32 バイトまたはソルト文字列の長さが64バイトの場合、ダイジェストDS全体が使用されます。

b) 残りのNバイト（最大31または63バイト）の場合、ダイジェストDSの最初のNバイトが使用されます。

21. ソルト内のrounds=<N>指定で指定された回数（指定されていない場合はデフォルト値）だけループを繰り返します。各ラウンドは0からN-1までの番号が付けられます。

このループはダイジェストを入力として使用します。最初のラウンドでは、ステップ12で生成されたダイジェストが使用されます。後半のステップでは、前のラウンドのステップ21.hで生成されたダイジェストが使用されます。以下の説明では、この動作を説明するために「ダイジェストA/C」という表記を使用します。

a) ダイジェストCを開始する

b) 奇数ラウンド数の場合、ダイジェストCにバイトシーケンスPを追加する

c) 偶数ラウンド数の場合、ダイジェストA/Cを追加する

d) 3で割り切れないすべてのラウンド数の場合、バイトシーケンスSを追加する

e) 7で割り切れないすべてのラウンド数の場合、バイトシーケンスPを追加する

f) 奇数ラウンド数の場合、ダイジェストA/Cを追加する

g) 偶数ラウンド数の場合、バイトシーケンスPを追加する

h) ダイジェストCを終了する

22. 出力文字列を生成する。これは、上記で指定した最大サイズのASCII文字列で、複数の部分から構成される。

a) ソルトプレフィックス（それぞれ$5$または$6$）

b) 入力ソルト文字列にrounds=<N>指定が存在する場合、rounds指定。この場合、rounds指定と後続のテキストを区切るために、末尾に'$'を追加する。

c) 16文字に切り詰められたソルト文字列

d) '$' 文字

e) Base64エンコードされた最終的なCダイジェスト。使用されるエンコードは次のとおりです。

code:base64

111111111122222222223333333333444444444455555555556666

0123456789012345678901234567890123456789012345678901234567890123

----------------------------------------------------------------

./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

ダイジェストの各3バイトグループは、出力として4文字を生成します。

1. 文字: 最初のバイトの下位6ビット

2. 文字: 最初のバイトの上位2ビットと、2番目のバイトの下位4ビット

3. 文字: 2番目のバイトの上位4ビットと、3番目のバイトの下位2ビット

4. 文字: 3番目のバイトの上位6ビット

3バイトグループは、以下の通りです（この順序で）。これらは、ダイジェストを含むバイト配列のインデックスであり、インデックスは0から始まります。最後のグループでは、ダイジェストに十分なバイト数が残っていないため、代わりに値0が使用されます。このグループも、SHA-256とSHA-512でそれぞれ3文字または2文字のみを出力します。

code:For SHA-256

0 - 10 - 20

21 - 1 - 11

12 - 22 - 2

3 - 13 - 23

24 - 4 - 14

15 - 25 - 5

6 - 16 - 26

27 - 7 - 17

18 - 28 - 8

9 - 19 - 29

* - 31 - 30

code:For SHA-512

0 - 21 - 42

22 - 43 - 1

44 - 2 - 23

3 - 24 - 45

25 - 46 - 4

47 - 5 - 26

6 - 27 - 48

28 - 49 - 7

50 - 8 - 29

9 - 30 - 51

31 - 52 - 10

53 - 11 - 32

12 - 33 - 54

34 - 55 - 13

56 - 14 - 35

15 - 36 - 57

37 - 58 - 16

59 - 17 - 38

18 - 39 - 60

40 - 61 - 19

62 - 20 - 41

* - * - 63

以下は、SHA-256とSHA-512をそれぞれ使用した暗号バリアントの完全な実装です。ソースコードにはセルフテストが含まれており、マクロTESTを定義することで有効にできます。

(略)