S/KEY

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

概要

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

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

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

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

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

S/KEYのワンタイムパスワードの生成過程
  1. 最初に、パスフレーズWを準備する。このパスフレーズはユーザーが用意することも、コンピュータが生成することもできる。いずれにせよ、このパスフレーズが漏洩するとS/KEYの安全性が破綻してしまうため、取り扱いには十分注意を払う必要がある。
  2. 暗号学的ハッシュ関数HをWにn回適用する。これにより、n個のハッシュチェインが求まる。:
    H(W), H(H(W)), ..., Hn-1(W), Hn(W).
  3. パスフレーズWを破棄する。
  4. n個のハッシュチェインを逆順に並べてユーザーに表示する。これらがワンタイムパスワードとなるので、ユーザーはメモを取っておかなければならない。:
    Hn(W), Hn−1(W), ..., H(H(W)), H(W).
  5. ワンタイムパスワードのうちH(W), H(H(W)), ..., Hn-1(W)はサーバーから破棄する。ユーザーに提示されたワンタイムパスワードの先頭にあたるHn(W)のみサーバーに保管する。

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

認証

S/KEYの認証

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

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

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

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

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

セキュリティ

原像計算困難性

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

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

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

単独利用時の脆弱性

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

ソルトについて

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

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

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

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

→「鍵導出関数」も参照

ループ

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

ユーザビリティ

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

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

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

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

脚注

[脚注の使い方]

注釈

  1. 1 2 3 4 RFC 2289では「シード」と呼称しているが、これに対してパスフレーズのことをシードと呼称している文献も存在する。当記事では混乱を避けるため、より実態に近い「ソルト」に表現を変更している。
  2. ↑ 2048進数と捉えると、1単語で11ビット分の情報を持つことになる。単語が6個並べば情報量は66ビットとなるので、64ビットのワンタイムパスワードを表現できる。余剰の2ビットはパリティビットとして用いる。

出典

  1. 1 2 Philip J. Nesser II; Mike Straw; Craig Metz; Neil M. Haller (2013-03-02) (英語). A One-Time Password System. IETF. RFC 2289 2025年8月26日閲覧。
  2. 1 2 3 4 “S/KEY”. IT用語辞典 e-Words. インセプト (2022年4月17日). 2025年8月25日閲覧。
  3. ↑ “OpenSSH Project History” (英語). OpenSSH. 2019年12月5日閲覧。
  4. 1 2 3 中村 健之 (2006年10月11日). “セキュアな無線LANを構築する技術を求めて”. atmarkit.itmedia.co.jp. アイティメディア. 2025年8月24日閲覧。
  5. ↑ “corporate fact sheet” (PDF) (英語). iconectiv (2018年2月). 2025年8月26日閲覧。
  6. ↑ Takasuke TSUJI; Akihiro SHIMIZU (2004-06). “Cryptanalysis on One-Time Password Authentication Schemes Using Counter Value” (英語). IEICE TRANSACTIONS on Communications E87-B (6): 1756-1759.
  7. ↑ “Global Multi-factor Authentication Market 2017-2021” (英語). TechNavio (2017年8月). 2019年12月5日閲覧。[リンク切れ]
  8. 1 2 TAC株式会社（情報処理講座）『情報処理安全確保支援士』（初版）TAC出版〈2023年度版 ALL IN ONE パーフェクトマスター〉、2022年8月20日。ISBN 978-4-300-10186-5。
  9. ↑ Yum, Dae Hyun; Seo, Jae Woo; Eom, Sungwook; Lee, Pil Joong (2009), Fischlin, Marc, ed. (英語), Single-Layer Fractal Hash Chain Traversal with Almost Optimal Complexity, 5473, Springer Berlin Heidelberg, pp. 325–339, doi:10.1007/978-3-642-00862-7_22, ISBN 978-3-642-00861-0 2025年8月26日閲覧。
  10. ↑ Samuel, Michael (2011年7月1日). “S/Key Dungeon Attack” (英語). MikNet. 2019年12月5日閲覧。
  11. ↑ Haller, Neil; Metz, Craig; Nesser II, Philip J.; Straw, Mike (1998-02). “Appendix D: Dictionary for Converting Between 6-Word and Binary Formats” (英語). A One-Time Password System (IETF). doi:10.17487/RFC2289.
  12. ↑ Haller, Neil; Metz, Craig; Nesser II, Philip J.; Straw, Mike (1998-02). “6.0: GENERATION OF ONE-TIME PASSWORDS” (英語). A One-Time Password System (IETF). doi:10.17487/RFC2289.

関連項目

外部リンク