S/KEY

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

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

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

S/KEYは、レスリー・ランポートが発明したランポート署名を元に、Bellcore社のニール・ハラー、、ジョン・ウォルデンによって1980年代後半に開発された。   それに比べると、多要素認証を実装する目的においては利用が広まっている。

## ワンタイムパスワードの生成
ここで言う「サーバー」とは、認証を要求する側のコンピュータを指す。

# 最初に、パスフレーズ*W*を準備する。このパスフレーズはユーザーが用意することも、コンピュータが生成することもできる。いずれにせよ、このパスフレーズが漏洩するとS/KEYの安全性が破綻してしまうため、取り扱いには十分注意を払う必要がある。
# 暗号学的ハッシュ関数*H*を*W*に*n*回適用する。これにより、*n*個のハッシュチェインが求まる。: 
#:*H*(*W*), *H*(*H*(*W*)), ..., *H**n*-1(*W*), *H**n*(*W*).
# パスフレーズ*W*を破棄する。
# n個のハッシュチェインを逆順に並べてユーザーに表示する。これらがワンタイムパスワードとなるので、ユーザーはメモを取っておかなければならない。:
#:*H**n*(*W*), *H**n*−1(*W*), ..., *H*(*H*(*W*)), *H*(*W*).
# ワンタイムパスワードのうち*H*(*W*), *H*(*H*(*W*)), ..., *H**n*-1(*W*)はサーバーから破棄する。ユーザーに提示されたワンタイムパスワードの先頭にあたる*H**n*(*W*)のみサーバーに保管する。
固定長が64ビットより長いハッシュ関数を用いる場合、によれば、ハッシュ化に引き続いて所定のアルゴリズムで64ビット長に短縮する処理もセットで繰り返し行うことになっている。これにより、*H**i*(*W*)の長さはすべて64ビットに統一されている。だが、アルゴリズムが用いるハッシュ関数によって異なることから、煩雑化を避けるため、解説ではこの処理自体の説明を省略する場合も多い。

## 認証

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

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

何にせよ、1番目のワンタイムパスワード*OTP<sub>1</sub>*はサーバーが保管しているものと同一であるため認証には用いられず（ユーザーは*OTP<sub>1</sub>*を予めメモから消しておくべきである）、2番目のワンタイムパスワード*OTP<sub>2</sub>*が以下の流れで使用される。:
* ユーザーは*OTP<sub>2</sub>*をサーバーに提示し、メモから消す。
* サーバーは*H*(*OTP<sub>2</sub>*)を計算する。もし*H*(*OTP<sub>2</sub>*)がサーバーが保管している*OTP<sub>1</sub>*と一致すれば、認証は成功となる。サーバーは、次回以降の参照値として*OTP<sub>2</sub>*を保管する。

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

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

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

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

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

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

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

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

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

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

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

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

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

置き換えの手順は以下の通りである。
# 生のワンタイムパスワードをバイナリ値に変換し、2ビットずつ区切る。
# 生じた32個のバイナリ値を全て足し合わせる。
# 和の下位2ビットをパリティとする。
# バイナリ形式の生のワンタイムパスワードに、先の手順で算出したパリティを末尾に付加する。この処理によりワンタイムパスワードの長さが66ビットに拡張される。
# 先頭から11ビットずつ区切る。生じた6個のバイナリ値がインデックスとなる。
# インデックスが取り得る値の範囲が(10進数で)0~2047であることに留意し、英単語リスト内で各インデックスに対応する英単語を検索する。
# 導出された6つの英単語を順番通り並べたものが変換後のワンタイムパスワードとなる。
* 「0xD1854218EBBB0B51」の場合（内の値は全てバイナリ値）
*# 分割結果は                               。
*# 和は。
*# 末尾2ビットのがパリティ。
*# の末尾にを付加する。
*# 分割結果は     。
*# は10進数で1676なので、リスト内で**1677**番目の英単語を探す。今回はとなる。
*# 全て置き換えた結果はとなる。

## 脚注

### 注釈

### 出典

## 関連項目
* 
* 
* PGPワードリスト - 256個から成る英単語群が2組含まれており、どちらも1単語で8ビット分のビット列を表現する。

## 外部リンク
* The S/KEY One-Time Password System (RFC 1760)
* A One-Time Password System (RFC 2289)
* jsotp: JavaScript OTP & S/Key Calculator
* Introduction to the system