S/KEY

この項目では、ワンタイムパスワードの生成アルゴリズムについて説明しています。日本の女性シンガー・作詞家・ボイストレーナーについては「S-KEY-A」をご覧ください。

S/KEYはUnix系オペレーティングシステムの認証用に開発されたワンタイムパスワードの生成方法で、特に長期的に有効なパスワードを入力することが好ましくないダム端末や信頼できない公共のコンピュータで用いられている。ユーザーが記憶するパスフレーズにソルト^{[注釈 1]}とデクリメントカウンタの値を組み合わることで、オフラインのデバイス内で使い捨てのパスワードを生成することができる。各ワンタイムパスワードは一度しか用いられないため、LANアナライザに耐性がある。

概要

ソルト^{[注釈 1]} はカウンタがゼロになるまで変更されないため、ユーザーが持ち運び可能な使い捨てのパスワードのリストを順番に用意することができる。あるいは、ユーザーはパスフレーズ・ソルト・任意のカウンタの値をローカルの計算機に提示することで適切なワンタイムパスワードを生成させることも可能であり、しかもこれは平文でネットワークに送信しても差し支えない。後者の用法の方がより一般的であり、これは実質的にチャレンジレスポンス認証（英語版）と同等である。

S/KEYはLinux（Pluggable Authentication Modules（英語版）を通して）・OpenBSD・NetBSD・FreeBSDでサポートされており、また、汎用のオープンソース実装を用いることで他のシステムに組み込むこともできる。OpenSSHもまた1999年12月1日に公開されたバージョン1.2.2からS/KEYを実装している。^[3] 一般的な実装の例の一つとしてOPIE認証システム（英語版）が挙げられる。なお、S/KEYは、以前はBell Communications Research社やTelcordia Technologies社という名で知られていたiconectiv（英語版）社の商標である。^[2][4][5]

S/KEYは、レスリー・ランポートが発明したランポート署名を元に、Bellcore社のニール・ハラー、フィル・カーン（英語版）、ジョン・ウォルデンによって1980年代後半に開発された。^[1][6] このことから、S/KEYを指してランポート署名と呼称する場合もある。^[要検証] 公開鍵暗号に関する基礎的な特許が失効したことと、パスワードだけでなくセッション全体を保護可能なSSHなどといった暗号化プロトコルを実行するノートパソコンが広範囲に普及したことにより、S/KEYは使われなくなっていった。^[要出典] それに比べると、多要素認証を実装する目的においては利用が広まっている。^[7]

ワンタイムパスワードの生成

ここで言う「サーバー」とは、認証を要求する側のコンピュータを指す。

S/KEYのワンタイムパスワードの生成過程

1. 最初に、パスフレーズWを準備する。このパスフレーズはユーザーが用意することも、コンピュータが生成することもできる。いずれにせよ、このパスフレーズが漏洩するとS/KEYの安全性が破綻してしまうため、取り扱いには十分注意を払う必要がある。
2. 暗号学的ハッシュ関数HをWにn回適用する。これにより、n個のハッシュチェインが求まる。:

   H(W), H(H(W)), ..., H^n-1(W), Hⁿ(W).

3. パスフレーズWを破棄する。
4. n個のハッシュチェインを逆順に並べてユーザーに表示する。これらがワンタイムパスワードとなるので、ユーザーはメモを取っておかなければならない。:

   Hⁿ(W), Hⁿ⁻¹(W), ..., H(H(W)), H(W).

5. ワンタイムパスワードのうちH(W), H(H(W)), ..., H^n-1(W)はサーバーから破棄する。ユーザーに提示されたワンタイムパスワードの先頭にあたるHⁿ(W)のみサーバーに保管する。

固定長が64ビットより長いハッシュ関数を用いる場合、RFC 2289によれば、ハッシュ化に引き続いて所定のアルゴリズムで64ビット長に短縮する処理もセットで繰り返し行うことになっている。これにより、Hⁱ(W)の長さはすべて64ビットに統一されている。だが、アルゴリズムが用いるハッシュ関数によって異なることから、煩雑化を避けるため、解説ではこの処理自体の説明を省略する場合も多い。^[8][2][4]

認証

S/KEYの認証

ワンタイムパスワードを生成後、ユーザーの手元にはn個のワンタイムパスワードのメモが残る。n個のワンタイムパスワードを全て保管しておく方法も、毎度H(W)からワンタイムパスワードを算出する方法も、nが非常に大きい場合は非効率的である。そこで、ワンタイムパスワードを順序通り効率的に計算する方法が存在しており、それはステップ毎に、${\displaystyle \left\lceil {\frac {\log n}{2}}\right\rceil }$回だけハッシュ化を繰り返し、${\displaystyle \lceil \log n\rceil }$個ワンタイムパスワードを保存するというものである。^[9]

より理想的なのは、実際にはおそらくあまり一般的ではないものの、小さくて、持ち運び可能で、安全で、ネットワークから隔離されている、パスフレーズ・ソルト^{[注釈 1]}・必要なハッシュ関数の反復回数が与えられればワンタイムパスワードを再生成できる計算デバイスを、ユーザーが所持することであろう。ソルトと必要なハッシュ関数の反復回数については、サーバーから良い具合に提供される。

何にせよ、1番目のワンタイムパスワードOTP₁はサーバーが保管しているものと同一であるため認証には用いられず（ユーザーはOTP₁を予めメモから消しておくべきである）、2番目のワンタイムパスワードOTP₂が以下の流れで使用される。:

• ユーザーはOTP₂をサーバーに提示し、メモから消す。
• サーバーはH(OTP₂)を計算する。もしH(OTP₂)がサーバーが保管しているOTP₁と一致すれば、認証は成功となる。サーバーは、次回以降の参照値としてOTP₂を保管する。

その後の認証では、ユーザーはOTP_iをサーバーに提示する。サーバーはH(OTP_i)を計算し、保管しているOTP_i-1と比較する。

最後のワンタイムパスワードOTP_nは、初期設定時にパスフレーズWからサーバーが最初に生成したH(W)となる。

セキュリティ

原像計算困難性

S/KEYの安全性は、使用する暗号学的ハッシュ関数の原像計算困難性に依存している。認証に成功した際に使用されたワンタイムパスワードを、攻撃者が何らかの手段で入手したと仮定する。このワンタイムパスワードをOTP_iとおくと、各ワンタイムパスワードは一度限り有効であることから、OTP_i自体は既にその後の認証に用いることができなくなっている。よって、攻撃者の興味は、次回の認証で利用できるOTP_i-1を探し出すことにある。

とはいえ、これにはハッシュ値がOTP_iとなる原像を計算しなければならず（H(OTP_i-1) = OTP_i）、これは現在の暗号学的ハッシュ関数においては非常に難しい。

→「暗号学的ハッシュ関数 § 特性」も参照

単独利用時の脆弱性

S/KEYは、単独で使用すると中間者攻撃に脆弱である。また、攻撃者のソフトウェアがスニッフィングによりワンタイムパスワードのN−1桁目（Nはワンタイムパスワードの桁数）までを入手し、独自のTCPセッションをサーバーと確立した上でN桁目として有効な全ての文字を高速で総当たりする特定の競合状態にも脆弱である。これらの類いの脆弱性は、SSH・SSL・SPKM等といった暗号化されたトランスポート層を利用することで回避できる。

ソルトについて

S/KEYの仕組みを解説する際、当記事のようにパスフレーズのみをハッシュ化する流れで説明する文献が多い。^[8][2][4] しかし、この状態では同じパスフレーズを種とするワンタイムパスワードは全て同一の値となるので、以下の場合に脆弱となる。

• 複数の端末で同じパスフレーズを使い回している場合
• カウンターがゼロになった後の再初期化時に前回と同じパスフレーズを指定した場合
• 指定したパスフレーズ自体が脆弱な場合（辞書攻撃・レインボーテーブル攻撃）

このため、RFC 2289ではパスフレーズの前にソルト^{[注釈 1]} を結合したものをハッシュ関数に入力するよう指示している。ソルトは秘密でないため、サーバーに保管しておいても、認証時に被認証者に通知しても問題ない。一般的な解説と実際のプロトコルとでは若干差異がある点に注意されたい。

なお、ソルトが用いられるのは最初の1回だけで、以後の反復ではソルトやカウンターの値がハッシュ値に作用することはない。従って、パスフレーズを見つけることなく直接的にワンタイムパスワードの衝突を引き起こすことが可能である。ワンタイムパスワードのパターンは高々2⁶⁴通りであり、計算結果を格納するストレージ容量があれば事前に対応表を計算しておくことができる。必要なストレージ容量はレインボーテーブルによって最適化可能だが、特に、長いチェインでは衝突によって網羅すべき範囲を削減できるかもしれない。^[10]

攻撃者が最後に使われたワンタイムパスワードのデータベースへのアクセスに成功した場合、前述の対応表があればすべてのワンタイムパスワードを並行処理で調べ上げることができる。この場合、例えパスフレーズが分からなくても、攻撃者は各ユーザーの有効な認証情報を見つけることができる。この点では、強力でユニークなパスワードを、ソルトを使わずに64ビットのハッシュ値で保存しているのと状況は変わらない。

→「鍵導出関数」も参照

ループ

S/KEYのプロトコルはループする可能性がある。万が一S/KEYのワンタイムパスワードのチェイン内にこのループが生じれば、攻撃者は元のパスフレーズを探すことなく、場合によっては正当なユーザーに知られることなく、認証情報を使用することができる。その中でも特に最悪なケースは、あるワンタイムパスワードAから生成したワンタイムパスワードBが一致してしまう場合である。

ユーザビリティ

S/KEYのワンタイムパスワードの生値は64ビット長の数値であるが、人間のユーザビリティを考慮し、予め用意された2048語の単語リストから選ばれた対応する6個の単語に置き換える形を取ることもできる。^{[注釈 2]}

なお、RFC 2289には1~4文字の短い英単語のリストが示されているが^[11]、サーバーとクライアントで合意が取れていれば、別の単語リストを用いても構わない。

置き換えの手順は以下の通りである。^[12]

1. 生のワンタイムパスワードをバイナリ値に変換し、2ビットずつ区切る。
2. 生じた32個のバイナリ値を全て足し合わせる。
3. 和の下位2ビットをパリティとする。
4. バイナリ形式の生のワンタイムパスワードに、先の手順で算出したパリティを末尾に付加する。この処理によりワンタイムパスワードの長さが66ビットに拡張される。
5. 先頭から11ビットずつ区切る。生じた6個のバイナリ値がインデックスとなる。
6. インデックスが取り得る値の範囲が(10進数で)0~2047であることに留意し、英単語リスト内で各インデックスに対応する英単語を検索する。
7. 導出された6つの英単語を順番通り並べたものが変換後のワンタイムパスワードとなる。

• 「0xD1854218EBBB0B51」の場合（内の値は全てバイナリ値）
  1. 分割結果は11 01 00 01 10 00 01 01 01 00 00 10 00 01 10 00 11 10 10 11 10 11 10 11 00 00 10 11 01 01 00 01。
  2. 和は101011。
  3. 末尾2ビットの11がパリティ。
  4. 11010001 10000101 01000010 00011000 11101011 10111011 00001011 01010001の末尾に11を付加する。
  5. 分割結果は11010001100 00101010000 10000110001 11010111011 10110000101 10101000111。
  6. 11010001100は10進数で1676なので、リスト内で1677番目の英単語を探す。今回はROMEとなる。
  7. 全て置き換えた結果はROME MUG FRED SCAN LIVE LACEとなる。