平成  年度
学士学位論文 プロト コルにおける同期問題    



上岡 隆

指導教員

清水 明宏

 年  月  日
高知工科大学 情報システム工学科

要 旨

 プロトコルにおける同期問題
上岡 隆

情報通信分野の発展に伴い，インタネットやモバイルコミュニケーション環境において，通信相手の資格認証が必要不可欠なものとなっている．本研究室では，セキュリティが十分でないネットワーク上でユーザ等の資格認証を行う際，被認証者側および認証者側共に，実行する計算量が極めて少なく，被認証者側にも認証者側にも簡易で小さいプログラムサイズで実現可能，さらに，通信路上での盗聴に強い安全な認証方式，  パスワード 認証方法を提案している．本方式は現在，携帯電話における個人認証用に実装されているが，この実用システムにおいて用いられている同期管理方式には，第三者の改ざんにより認証が不能になる問題がある．
本論文では，  プロトコルにおける既存の同期管理方式における問題点を指摘し ，ほとんど 追加コストを必要とせずにこの問題を解決する方法を提案・評価する．
キーワード

 認証方式，ワンタイムパスワード，同期管理，盗聴，サービ ス不能攻撃        


 

 









  





                  

 

 

" 

         Æ     !
 

 

      !    #                                                                                                                                                      $     





 

目次
第章

はじめに



第章

研究背景



ワンタイムパスワード                            

'

%&&

定義と記法                               

'

%&%

(

 の方法                            

)

%&'

*++ 法                               

,

%&)



                                 

-%% における同期問題                            

&.

%'

フラグを用いる同期管理方式

                       

&%

%'&

概要                                  

&%

%'%

問題点及び攻撃法                           

&)カウンタを用いた同期管理方式                       

&,

%)&

概要                                  

&,

%)%

性能                                  

&-

%&

%)

第章

カウンタ同期方式の問題と攻撃法



'&

カウンタ同期方式の問題点                          

%.

'%

カウンタ同期方式に対するサービ ス不能攻撃                

%.解決法の提案と評価

)&

解決案                                    

%'

)%

評価                                      

%'

)%&

安全性                                 

%'再利用攻撃                               

%)

第章





目次

)%%
第章

サービ ス不能攻撃                           

%,処理量                                 

%-

おわりに



謝辞



参考文献



 

図目次
%& (

 の方法の登録，および認証フェーズ                

/%% *++ 法の登録，および認証フェーズ                   0%' の登録，および認証フェーズ                      

1 ，*++，  の性能比較                    

&.

%/ 同期問題                                    

&&%, フラグを利用した同期管理方法                        

&'%0 フラグのすり替え                               

&/%- カウンタを利用した同期管理方法                       &0%1 なりすましが行われた場合                          

&1'& カウンタ同期方式に対するサービ ス不能攻撃                 

%&)& 提案方式におけるカウンタの鍵                        

%))% 提案方式に対する再利用攻撃                         

%/)' 提案方式に対するサービ ス不能攻撃                      

%0

%) (



第章

はじめに
インタネットおよびモバイルコミュニケーション環境において，ユーザや通信相手の資格認証が必要不可欠なものとなっている．資格認証方法として，& 指紋や顔，声等の身体情報を利用したもの，% * カード のような本人の所有物を利用したもの，' パスワード や
暗証番号等の本人の知識によるものが考えられる．しかし ，&，% は指紋や顔，声，*カード 等を読み込む装置等が必要であり，インタネットやモバイルコミュニケーション環境
で利用するにはコストが大きく，現実的でない．
そこでこれらの環境でよく用いられるのが ' のパスワード を用いた資格認証方法であり，特に，毎回送信される認証データが異なるために通信の盗聴に強いワンタイムパスワー
ド 認証方式が広く用いられている 2&32%32'3．しかし ，(

 の方法には，被認証者がパス

ワード を定期的に再設定する必要性や，認証者側に比較して処理能力の小さい被認証者側での処理負担が大きいという問題がある．また，*++ 法では，(

 の方法の欠点であるパスワード の更新の必要性をなくす事ができたが，被認証者および認証者における計算量が大きいという問題は依然残った．さらに，通信途中の認証情報を第三者により二回続けて盗聴された場合，「 なりすまし 」の危険性もあった．
そこで我々はセキュリティが十分でないネットワーク上でユーザ等の資格認証を行う際，被認証者側および認証者側共に，実行する計算量が極めて少なく，被認証者側にも認証者側にも簡易で小さいプログラムサイズで実現可能，さらに，通信路上での盗聴に強い安全な認証方式，  パスワード 認証方法を提案した 2)3．本方式は現在，携帯電話での個人認証用に実装されているが，実装されているカウンタ同期方式には通信途中で第三者に認証情報をすり替えられる事によって正規ユーザが以降の認証を行えなくなるという問題がある事を発



見した．
本論文では，  におけるカウンタ同期方式の問題点及び攻撃法を指摘し ，ほとんど 追
加コストを必要とする事なく，それらの問題を克服できる案を提案する．
本論文の以下の部分では，まずワンタイム認証方式おける  の優位性と同期問題，既存同期管理方式等の研究背景について  で述べ，カウンタ同期方式に対する脅威について 
で，その問題の解決法と評価を  で述べる．最後に  で本論文のまとめとする．



第章

研究背景
まず本章では，本研究で対象としている  認証方式がワンタイムパスワード の中で優位な方式である事を示し ，その  における同期問題と提案されている同期管理方式についてを述べる．

 ワンタイムパスワード
ネットワークを経由したサーバとクライアント間の操作で，もっとも盗聴されると危険な情報はログ インの情報である．そのため，パスワードが盗めないようにするか，もしくは盗まれても使えないようにする必要がある．そのための手法として，ワンタイムパスワード という手法が提案されている．ワンタイムパスワード とは，認証の際にパスワード を毎回変えるシステムである．同じパスワード を二度と使わないので，盗聴などでパスワード を知られてしまっても問題がない．以下にワンタイムパスワード の代表的なものである (方法，*++ 法，  について説明する．



定義と記法

本論文で用いる定義と記法は以下の通りである．

& 4 を，認証用プロトコルを用いるコンピュータユーザとする．
% 5 を，ユーザを認証するサーバとする．
'を，ユーザの $ とする．

)  を，ユーザのパスワード とする．


 の

%& ワンタイムパスワード/  を，認証セッション回数を表す . 以上の整数とする．
,  を， 回目の認証に対応する乱数とする．
0  を，サーバの識別のための公開情報とする．
-  は認証子とする．
1  を，暗号用のハッシュ関数とする．また   とは， を使い，    が  回
ハッシュされた事を示す．

&.  は，ビットごとの排他的論理和を表す．

( の方法
 の方法の認証メカニズムは ，一方向性関数を複数回適用し たデ ータを事前にサーバ側に登録しておき，認証の際には，登録しているデータの適用一回前のデータを示す
事によって認証を行い，次回用の鍵はユーザが示した一つ前のデータに置き換えるという方式である．概要は以下に示す 図 %& 参照．

& 登録フェーズ   6 . 

47  ， を任意に設定，以下のデータを計算する．ただし， 6     である．

  6       6 &・・・
そして，を保存しておく．

47   をサーバに送信する．
5 7   を保存する．
% 認証フェーズ   647 記録してある



および



を読み出し，   を計算する．

47    をサーバに送信する．
5 7 受信した    から    を計算する．
5 7 生成した    と前回登録されている    を比較，マッチすれば認証成功として を新たに鍵として記録する．アンマッチなら認証は拒否される．



%& ワンタイムパスワード

User

Host

S
One-way Translation
0

0

E

E

Last(m-th) Authentication

・
・
・

・
・
・

・
・
・

m-2

m-2

E

E

Second Authentication

m-1

m-1

E

E

First Authentication

m

m

E

E
Registration(Initial Phase)図  の方法の登録，および認証フェーズ

この方法では元のデータを公開し尽くした時点で，パスワード の再設定が必要となってしまうという問題がある．また連続認証回数を増やすために一方向性関数の適用回数を増加させると処理量が増大してしまい，サーバに比べて処理能力の低いユーザ側での計算量が増えてしまう．よって携帯電話といったような処理能力の低い端末での応用は望ましくない．



%& ワンタイムパスワード


(



法

 の方法におけるパスワード の再設定や処理量を解決する方式として *++ が提案された．この方式はサーバに対して以下の ' つのデータを送信する．

& 前回に正当性の確認が終わっている一方向性データの元のデータ% 次々回の認証に用いる一方向性データ' 前回送信されている一方向性データの正当性を確認するためのデータ
毎回，これらのデータを送信する事によって安全に認証情報の更新を行いつつ，認証を行っていく方式である．概要は以下に示す 図 %% 参照．

& 登録フェーズ  6 .

47  ， ， を任意に設定し，以下のデータを計算する． 6        6    
 6      
 6    
 6    47 そして  ， ， を保存する．
47   ， ， をサーバに送信する．
5 7   を次回認証用データとして，
 を次々回認証用データとして，正当性の検証は次回に行う
 を  の正当性を検証するために保存する．
% 認証フェーズ  6 47 記録してある   および  を読み出す．さらに， を任意に設定し ，以下のデータを計算する．

  6       
 6       6      %& ワンタイムパスワード

User

Host

n=0 (Initial Phase)E0

1

P , E 00

P ,S

N0

1
E1

0
, E1

P ,S

N1

P

1

1

E 0 , E 1 , M01

1

Store Data: E 0 , E 1 , M 0

01

E1 , E0
M0
Store Data:N 0 , N 1
n=1
0
E0
0
E1

P ,S

N0

1

1
0
E0 , E2

N1

P ,S
0
, E2

1
E2

P

M1

E2 , E1

P ,S

, M1

N2

0
E2

P ,S

Store Data:E 11 , E 12 , M 1

N1

1

1
0
E1 , E3

N2

P ,S
0
, E3

1
E3

P

M2

E3 , E2

P ,S

, M2

N3

P ,S

N k-1

0
E1

P ,S

Nk

P

M1

E k+1 , E k

10(Second Authentication)
01

E2 , E1

Store Data:E 12 , E 13 , M 2

n=k
0
E k-1
1
E2

P , E 01

(Validity Check)

Store Data:N 1 , N 2

0, E k+1

E1
M1

0

1

0

1

E1 , E0(Validity Check)

Store Data:N 1 , N 2
n=2
0
E1

P , E 00

(First Authentication)

M0

0

1

E0

1

0
E k-1,P ,S1
E k+1 , M k

N k+1

E k-1

P , E 0k-1

(First Authentication)

M k-1

1

0

E k , E k-1(Validity Check)

Store Data:E 1k , E 1k+1 , M kStore Data:N k , N k+1
図 法の登録，および認証フェーズ

 6   
 6    
47   ， ， をサーバに送信する．
5 7 受信した   から   6     を計算する．
5 7 生成した   と前回登録されている   を比較，マッチすれば認証成功となる．


%& ワンタイムパスワード
5 7 さらに，  と記録してある  により，  6      を計算し，前回記録してある  と比較．マッチしていたら先に受け取った  が正当であると判断する．

5 7  を次回認証用データとして， を次々回認証用データとして，正当性の検証は次回に行う
 を  の正当性を検証するために保存する．
*++ では理論的にはパスワード の再設定が必要とならず，永遠に認証が行える．しかし，攻撃者によって二回分の認証情報を立て続けに盗聴され，さかのぼって攻撃者にとって都合の良いデータにすり替えられる事により，なりすましの被害を受けるというセキュリ
ティ上の問題がある．また (データ量ともに (( に比べて処理量は減ったものの，送信データ量，記録

 の約 ' 倍となっている．

 や *++ といったプロトコルの問題を解決した方式として，  パスワー

ド 認証方式が提案されている．この方式はワンタイムパスワード の中で最も少ない計算量とプログラムサイズで，そして最も通信路上の盗聴による攻撃に強いプロトコルである． は．前回の認証フェーズで登録しておいた一方向性関数を二回適用したデータの元のデータと次回認証用データを今回認証用データと次回認証用データに一方向性関数を適用したもの
でマスクして送り，認証と同時に次回認証用データの正当性の検証と登録を行うという方式である．概要は以下に示す 図 %' 参照．

& 登録フェーズ  6 .

47   6       を計算する．
47    をサーバに安全なチャネルを用いて送信する．
5 7    を保存する．
% 認証フェーズ  6 47 以下のデータを計算し，ユーザ $と共に 5 に送信する．



%& ワンタイムパスワード

User

Host
2

n = 0 A, N0 , E20

A, E0

2

n=1

2

N1 , E10 , E0
2

A,

E10

3

2

E1 , E1E20

3

E1 , E1

Store

A, E0

(through a secure channel)

2

2

(E21

E20 = E1 …(1)E0)

E(E21 ) = E31(E10 E13) E13 = E01
2
CompareE(E10 ) = E0
2
Update stored E0 to (1)

・
・
・

・
・
・

・
・
・
E2k-1

n = k Nk , E1k-1 , E2k-1

A, E1k-1

3

2

Ek , Ek

2

Ek-1
( E2k

E2k , E3k2

Ek-1 )
2

E2k-1 = E2k …(k)3

E(E k ) = Ek
(E1k-11

3E3k = Ek-1

Ek )

1

2

E(E k-1 ) = Ek-1

Compare2
E
Update stored k-1 to (k)

・
・
・

・
・
・

図 

・
・
・

 の登録，および認証フェーズ

   8 &   5 7    と，保存されている  との排他的論理和を取り，以下を取得する．
5 7  にハッシュ関数を適用する．
  6 



%%

 における同期問題 を    と排他的論理和を取り，今回認証用中間データ  を取得する． にハッシュ関数を適用し ，保存している  と比較する．マッチすれば ，4 は認証され，次回認証フェーズのために， を  に更新する．
取得した

アンマッチならば認証は拒否される．

 では認証を行う度に次回用鍵の登録を行うので ( と違い，パスワード の再設定の必要がない．また処理量や記憶量，データ通信量も図 %) のように少なくてすむ．安全性に関しても，認証情報の再利用攻撃やサービ ス不能攻撃に対して耐性がある．
Performance

Host
Hash
Interation(time)

Data
Storage(bits)

Hash
Interation(time)

Lamport1

70

100-1000

CINON

2

200

2

70

MethodSAS

User-Host

User
Data
Storage(bits)
64
for n

Transmission
Interation(time)
S.R(2 way)
& 1(1 way)

5

128
for
N1&N2

1

200

5

0

1

140

図   ，Transmission
Bulk(bits)
70， の性能比較   における同期問題
 は軽量かつ安全なプロトコルとして，計算能力の低い携帯電話など への実装が検討されてきた．その実装の段階で問題となったので，同期問題である．同期問題とは，  プ
ロトコルではユーザが認証フェーズ毎に生成した乱数を元に認証用データを作り出して認証を行う．しかし第三者からの攻撃や通信路断絶といったような何らかの理由でサーバだけ乱数が新しいものに更新されてしまい，次回の認証時にユーザの使用する乱数とサーバが使用する乱数にずれが発生して正常な認証が行えなくなる問題である 図 %/ 参照．この同期問  

%% における同期問題

題が発生し うる事象について，以下のように切り分けて考える事ができる．

& ユーザからの認証情報がサーバに届かなかった場合% サーバでの認証処理が正常に終了しなかった場合' サーバでの認証処理終了後に，認証成功の応答がユーザに届かなかった場合) 悪意のある第三者により盗聴，なりすまし認証が行われてた場合& については，ユーザ，サーバともに認証情報の更新が行われないため，同期問題は生じない．また，% については認証情報の更新の前であれば & と同様に考えられ，更新後であれば' と同様のと考えられる．' と ) ではサーバのみが新しい認証情報に書き換わってしまうた
めに同期ずれが発生してしまう．
以上の事から，対策を考慮すべき点は ' と ) という事になる．
User

Host

1

n =k

N k , E k-1 , E 2k-1
2
Ek

E1k-1

3

2

Ek , E k2

E k-1

This time key: E 2k-1

Counter=m
Authentication Success1

n = k+1 N k , E k-1 , E 2k-1

E1k-1

3

Ek

2
,E k

2

E k-1

2

OK

(1)Authentication by E 2k

NG(1)Authentication byE k-1(2)DATA Update

This time key:E 2k

2
Ek

Counter=m+1
Authentication Failure

The authentication of the rest
becomes impossible.

・
・
・

・
・
・

・
・
・
X …stored data

図 

同期問題

  

%' フラグを用いる同期管理方式

 フラグを用いる同期管理方式
 の同期管理方式として本学卒業生によりフラグを用いて同期管理を行う方式が提案されていた 2/3．ここでは本学卒業生の大石 恭弘が提案した，サーバとユーザが交互に同じフラグを保持するという同期管理方式について説明する．

 

概要

通信が切断される場合には，ユーザからサーバへの認証用データが未達の時，サーバからユーザへの認証成功のメッセージが未達の時の % つが考えられる．これらの問題に対し，この方式ではユーザ，サーバ共にフラグ .，もしくは & の値を取る を使用して同期管理を行う．概要は図 %- で示す．

& 登録フェーズ
・ ユーザとサーバのフラグをそろえておく．図 %- の場合では 9.9である．

% 認証フェーズ  6 47 認証フェーズ毎にユーザ $ と認証用データに加え，フラグの値もサーバに送信する．
5 7 フラグの値によって，同期が取れているかど うかをチェック．保持しているものと同じ値であれば ，同期チェックは成功とし ，認証成功するとサーバはフラグを 9&9に更新し応答を返す．違っている場合は同期エラーのメッセージをユーザに送信してフラグの値を修正させる．

47 ユーザは認証成功のメッセージを受け取るとフラグの値を更新する．
このようにしてユーザ側とサーバ側で同じフラグの値9.9と 9&9を交互に保持ようにする．
もしこの方法において応答が途絶えた場合，次のフェーズでフラグがサーバ側でフラグが違っている事を検出し，ユーザに対して同期エラーメッセージを返す．ユーザは同期エラー
メッセージを受け取り，前回の認証フェーズで認証成功したものの，応答を受信出来なかっ  

%' フラグを用いる同期管理方式

User

Host

・
・
・

n=k

・
・
・

・
・
・
2

Nk-1

Ek-1

counter = 0

counter = 0

generate and
store
Nk

counter = 0,
Authentication Data (use N k-1 ,N k)
Authentication Succeed
store E2k
Authentication Succeed

counter = 1

counter = 1
clear Nk-1

n = k +1 generate and
store
Nk+1

counter = 1,
Authentication Data (use N k , N k+1)
Authentication Succeed
2store Ek+1
counter = 0

Authentication Succeed
User coudn’t receive
counter = 1,n = k +2

Authentication Data (use N k , N k+1)
Counter Check Failed

Counter Check Failed

counter = 0
clear Nkgenerate and
store
Nk+2

Authentication Data (use N k+1, N k+2)
Authentication Succeed
store E2k+2Authentication Succeed

counter = 1

・
・
・

・
・
・

counter = 1
clear Nk+1
・・・

X …stored data

図  フラグを利用した同期管理方法

  

%' フラグを用いる同期管理方式た事に気付く．そして次回用鍵を今回用鍵に置き換えて認証を行い，同期ずれの修正を行う事が出来る．

 

問題点及び攻撃法

この方式では第三者からのフラグの改ざんを想定していないので，フラグの値をそのまま送信している．つまり第三者によって容易に有意味な値に改ざんが可能である．またフラグの値のみで同期のずれをチェックしようとしているので，フラグの値を変更する事によって再送とサーバ側に勘違いさせる事が可能となる．
次に具体的にこの方式に対する攻撃法を解説する．図 %0 を例にとって説明すると，まず，ユーザがサーバに対して正常なフラグと認証情報を送信した際に，攻撃者はフラグの値を変更する 図 %0 の場合では 9.9から 9&9に変更．サーバは送信されてきたフラグの値をチェッ
クし，本来は同期ずれが起きていないのにも関わらず，フラグの値より同期ずれと判断して同期エラーメッセージをユーザに返してしまう．同期エラーメッセージを受け取ったユーザ
側でも同期のずれが起こったと判断して，次回用鍵を今回用鍵に置き換え，新たに次回用鍵を作り直し，フラグの値を修正して送信する．攻撃者は再びフラグの値を改ざんする．これ
によってフラグの値は正常な状態に戻り，同期チェックは成功する．しかし ，ユーザ側の今回用鍵だけが更新してしまう事によって同期のずれが生じ，認証自体が失敗に終わってしまい，以降の認証が不能となってしまう．

  

%' フラグを用いる同期管理方式

User
・
・
・

n =k

Host
・
・
・

・
・
・
2

Nk-1

Ek-1

counter = 0

counter = 0

generate and Attacker changes into "1" from "0"
store
counter = 0,
Nk
Authentication Data (use N k-1,N k )Counter Check Failed

Counter Check Failed
counter = 1
clear Nk-1

n = k +1 generate and
store
Nk+1

Attacker changes into "0" from "1"
counter = 1,
Authentication Data (use N k , N k +1 )Authentication Failed

・
・
・

・
・
・

・
・
・

X …stored data
図  フラグのすり替え  

%) カウンタを用いた同期管理方式

 カウンタを用いた同期管理方式
現在，  プロトコルは +!! アド バンステクノロジ株式会社により，携帯端末用個人認証システム9: ;<9として商品化されている．この実装の際に，同期管理が大きな問題となった．そこで彼らはカウンタを用いた独自の同期管理方式を採用して，この問題の解決を図った 2,3．以下に，そのカウンタ同期方式の概要と性能について説明する．



概要

この方式ではシーケンシャルナンバをカウンタとして使用し ，今回認証用の鍵で暗号化して送り，カウンタの値が進んでいるかチェックする事によって再送のチェックを行う．概要
は図 %- に示す．

& 登録フェーズ・ 乱数でカウンタの初期値を決定し，ユーザが保持する．サーバのカウンタは 9.9とする．

% 認証フェーズ  6 47 カウンタを今回認証用の鍵と用いて暗号化し，認証情報と共にサーバに送信する．
5 7 まず保持している今回認証用の鍵を用いて認証を行う．認証成功した場合は，今回認証用の鍵を用いてカウンタを復号し，保持しているカウンタと大小比較する．

5 7 もし今回認証用の鍵で認証が失敗した場合は，再送であるか検査するために保存しておいた前回認証用の鍵を用いて認証を行う．認証が成功した場合は前回認証用の鍵を用いてカウンタの復号を行い，保持しているカウンタと大小比較する．

5 7 今回用もし くは前回用の鍵のど ちらかで認証が成功し ，カウンタのチェックが成功した
場合は認証成功のメッセージをユーザに送信する．今回認証用と前回認証用の鍵の両方で認証失敗した場合は認証失敗のメッセージを送信する．またカウンタの値が不正であった場合も認証失敗とする．

 %) カウンタを用いた同期管理方式

User

Host

・
・
・

n=k

・
・
・

・
・
・
2

Nk-1

Ek-1

counter = 0

counter = 0

generate andstore

counter = 0,
Authentication Data (use N k-1 ,N k)

Nk

Authentication Succeed
store E2k
Authentication Succeed

counter = 1

counter = 1
clear Nk-1

n = k +1 generate and
store
Nk+1

counter = 1,
Authentication Data (use N k , N k+1)
Authentication Succeed
2store Ek+1
counter = 0

Authentication Succeed
User coudn’t receive
counter = 1,n = k +2

Authentication Data (use N k , N k+1)
Counter Check Failed

Counter Check Failed

counter = 0
clear Nkgenerate and
store
Nk+2

Authentication Data (use N k+1, N k+2)
Authentication Succeed
store E2k+2Authentication Succeed

counter = 1

・
・
・

・
・
・

counter = 1
clear Nk+1
・・・

X …stored data

図 

カウンタを利用した同期管理方法 %) カウンタを用いた同期管理方式



性能

携帯電話での実装を考慮して，この方式ではユーザである携帯電話側での処理を減らす
工夫がされている．まず一つ目は，ユーザが再送を行っていないかをチェックするために，サーバ側で認証が失敗した際に前回の鍵を使用して認証処理を行っている．これによって処
理能力の低いユーザ側での計算を減らす事が出来る．そして次に，この方式が第三者が認証情報を盗聴し ，再送を装って認証を行おうとする事を防ぐために，カウンタを今回認証用の鍵で認証毎に新たに暗号化して送っている．これによってカウンタまで同じものは正規ユー
ザから一度も送られないので，第三者からのアクセスを防止する事ができる．また，このカ
ウンタは常にインクリメントされるだけで，初期化されない．初期値については乱数発生させているので第三者が通信回数を数えていたとしても容易にはカウンタの値を予想できな
い．カウンタの値は =  の   でとっているため，取り得る値は − % から % − & となっており，有限であるが実用上は問題ない程度に多い．もし正規ユーザ以外がなりすまし認証を成功させたとしても，ユーザはカウンタをインクリメントしているので以降の認証に問題は起きないようになっている 図 %1 参照．

 %) カウンタを用いた同期管理方式

User
1

n =k

N k , E k-1 , E 2k-1
2Ek

E(m), E1k-1

3

2

2

E k-1

Ek , E k

Counter=mn = k+1

Host

AttackerCounter=m-1

Send stolen Data The last key : E 2k-2
Authenticatioin
Success

1

N k , E k-1 , E 2k-1 E(m+1), E1

k-1

3
2
Ek , E k

2(1)Authentication by E k-1(2)Counter Check(3)DATA Update22(1)Authentication by E k2(2)Authentication by E k-1(3)Counter Check(4)DATA Update

Authenticatioin Success

・
・
・

・
・
・
X …stored data

図  なりすましが行われた場合  

OK
OK

Counter=m
The last key : E 2k-1
This time key: E 2k

2
E k-1

Ek
Counter=m+1

・・・This time key: E2k-1

NG
OK
OK

第章

カウンタ同期方式の問題と攻撃法

 カウンタ同期方式の問題点
カウンタ同期方式では今回認証用の鍵を用いてカウンタを暗号化する．これによって今
回認証用の鍵を含んでいる認証情報を保障する事ができるが，これでは次回認証用の鍵が本当にユーザの意図したものかは保障できない．今回認証用の鍵は同じで，次回認証用の鍵だ
け違う認証情報をすり替えて送る事が出来たら，正規ユーザは以降の認証ができない状態になる．この問題点に着目して私は盗聴，すり替えによるサービ ス不能攻撃を発見した．

 カウンタ同期方式に対するサービス不能攻撃
カウンタ同期方式ではユーザは今回認証用の鍵を使用してカウンタを暗号化し ，サーバ側では 認証情報から今回認証用の鍵を取得し ，カウンタを 復号化する．一見はこれによってカウンタと認証情報に関連性が生まれ ，認証情報やカウンタのすり替えが行えないように思われる．しかし 先ほど 述べたように，次回認証用の鍵だけ違う認証情報をすり替
えて送る事が出来たら，正規ユーザは以降の認証ができない状態になる．そこで私は認証失敗した際に，ユーザが次回認証用の鍵を作り直し ，新たに今回認証用の鍵は同じで，次回認証用の鍵が違う認証情報を作成する点に注目した．それでは発見した攻撃法を説明する．

図 '& の 例を 使 用し て 説 明す る ．

規ユーザからの認証情報9  

回 目の 認 証フェーズ に おいて ，攻 撃 者は 正

      9を盗聴し ，認証情報を同じ長さの乱数に  

'% カウンタ同期方式に対するサービ ス不能攻撃

User

Host

1

n =k

N k , E k-1 , E 2k-1
2

Ek
Counter=m

2Counter=m-1
The last key :E 2k-2
2
It is exchanged to Rundom number This time key: E k-1
E(m), E1k-1

32

Ek , E k

E k-1

2(1)Authentication byE k-1(2)Authentication by E 2k-2

Authentication Failure

12

n = k+1 N k , E k-1 , E k-1 E(m+1), E1k-1

3

2

2

E k-1

Ek+1 , E k+1

It is exchanged to k th DATACounter=m-1
2
The last key : E k-2
This time key: E 2k-1

Authentication Success(1)Authentication by E 2k-1
(2)Counter Check(3)DATA Update

2
Ek

Counter=m+1

n = k+2 Nk+2,E1k-1 , E 2k-1 E(m+2), E1k+1

3

OK
OK

2

2

Ek+1 Counter=m+1

Ek+2 , Ek+2

The last key : E 2k-1
This time key: E 2k

2
E k+2

Counter=m+22

Authentication Failure

・
・
・

NG
NG

(1)Authentication by E k-1(2)Authentication by E 2k

NG
NG

・
・
・

・
・
・

X …stored data
図 

カウンタ同期方式に対するサービ ス不能攻撃

すり替えて送信する．サーバは受け取った認証情報で認証を行うが，攻撃者によって適当な値に変更されているので，もちろん認証失敗の応答をユーザに送信する． 8 & 回目の認証フェーズに認証失敗の応答を受け取った正規ユーザはパスワード の入力が失敗したと判断して，新たにパスワード の入力を行い，前回と同じ乱数9   9を使用して今回認証用の鍵を作成する．しかしここで次回認証用の鍵9  9 を新しい乱数9  9を使用して作り出し  

'% カウンタ同期方式に対するサービ ス不能攻撃てしまう．こうして正規ユーザは先程と今回認証用の鍵が同じで次回認証用の鍵だけが違う     9 を作成して 8 & 回目の認証フェーズに送信する．
そこで攻撃者は前回，正規ユーザが再送した時の認証情報9         9と今回


認証情報9  の認証情報をすり替えて送信する．これによって認証自体は成功するが，次回認証用の鍵が

正規ユーザが意図していた9  9ではなく，9  9が登録されてしまう．この認証は成功するが，次回の8 % 回目の

8 ' 回目以降の認証はユーザの使用している認証情報の乱数とサーバ側で保持している認証情報の乱数が異なるので認証できなくなる．

  

第章

解決法の提案と評価

 解決案
この攻撃法はカウンタ同期方式がカウンタを暗号化した鍵と，認証情報の今回認証用の鍵が同じであれば正規ユーザからの認証であると判断するという所が弱点となっている．つまり既存方式の問題点はカウンタと認証情報との関連性がない事が問題点となっている．そこで私はカウンタの暗号化の鍵に今回認証用の鍵と次回認証用の鍵にハッシュ関数を一度適用したものを排他的論理和演算したものを使用する方法を提案する。これによって暗号化されたカウンタと認証情報に関係を持たせる事が出来る．

 評価 

安全性カウンタ同期方式において，問題であったカウンタと認証情報との関連性がない点であった．本方式はカウンタの暗号化の鍵に今回認証用の鍵だけでなく，次回認証用の鍵に関連したものを使う事によって問題を解決する事に成功した．この方式によって何故，カウンタと認証情報に関連性を持たせる事が出来たと言えるを説明する．  プロトコルの認証情報
はユーザ $ 以外に二つある．一つは今回認証用の中間データと次回認証用の鍵に一回ハッシュ関数を適用したものとを排他的論理和演算したもの．もう一つは次回認証用の鍵と今回認証用の鍵を排他的論理和演算したの二つである 図 )& 参照．

  

)% 評価

In k th authentication phase
Authentication DATA:

E1k-1

3

2

Ek , E k2

E k-1

Counter Key:

3

Ek

2

E k-1

図  提案方式におけるカウンタの鍵

既存方式では今回の鍵を使用して二つ目のデータに含まれる，今回認証用の鍵を使用し今回の鍵の検証を行うと共に，  プロトコル自身の次回認証用の鍵を検証するメカニズム
によって認証情報を保障しているように考えられるが，  プロトコルの次回認証用鍵の正当性検証はあくまでも，一つ目の認証情報と二つ目の認証情報の間にある次回認証用の鍵が同じものであるかを検証しているのであって，カウンタが作られた時の次回認証用の鍵という保証にはならない。カウンタと認証情報の組み合わせに関連性を持たせるためには，一つ目の認証情報と二つ目の認証情報のそれぞれから，今回認証用の鍵と次回認証用の鍵に関係したものを取り出さなければならない．そこで今回の提案方式では一つ目のデータに含まれる，次回認証用の鍵に一回ハッシュ関数を適用したものと，二つ目の式に含まれる，今回認証用の鍵を使用する事によって，この二つのデータにカウンタを関連付けた．これによって今回認証用の鍵のみなず，次回認証用の鍵をも保証する事が可能となる．

再利用攻撃
もし攻撃者が認証情報を改ざんし，なりすまし等の攻撃を行おうとするならば，まずカウンタの鍵を作成し，取得したカウンタを新たに改ざんした認証情情報を使用して作成する必要がある．そこでこの提案方式で使用されているカウンタの鍵が通信路上の盗聴によって作成される危険性がないかの検証を行う．

  

)% 評価
ここで第三者が，なりすましを成功させるために必要なデータについて考えてみる 図 )%参照．

Authenticatoin DATACounter key

Phase
k th

b

d

a

b , c

d

(k+1) th

f

c

e

f , g

c

(k+2) th

i

g

h

i ,

j

g

(k+3) th

l

j

k

l ,

m

j

In (k+3)th authentication phase Attacker needs
f

j

,

k

f

, g

j

c

, d

j

or
c

j

,

k
or
・
・
・

図 

第

提案方式に対する再利用攻撃

回目の認証フェーズにおいて，4 から送信される認証情報       とカウンタの暗号化に使用する鍵    は，
認証情報7    カウンタの鍵： と表す事ができる．同様に第  8 & 回目から  8 ' 回目の認証情報をそれぞれ  ，認証情報7      …第  8 & 回目
カウンタの鍵：   ，認証情報7     …第  8 % 回目
カウンタの鍵：   ，認証情報7      …第  8 ' 回目
カウンタの鍵：と表せる．ここで，第三者によってこれまでの全ての通信を盗聴したとし，例えば第  8'  

)% 評価

目の認証フェーズでユーザから送られたカウンタを盗聴し，認証情報から生成した鍵を使用   9 が必要になる．このデータの99を作成する場合，第 8 ' 回目の認証情報である9  9から取り出す事になる．しかし ，9  9から取り出す
ためには 9 9で排他的論理和演算して取り出す必要があるが， は 9  9にしか出てこない．
排他的論理和は同じもの同士は打ち消してしますので，もし 9      9と演算した

して復号し ようとした場合，9場合，答えは . となってしまう．この次回認証用の鍵にハッシュ関数を一度適用したものが複製できないので，鍵自体の複製も出来ないという事になる．

サービス不能攻撃
カウンタ同期方式で問題であったサービ ス不能攻撃について，今回提案した方式で考えてみる．
図 )' の例を使用して説明する． 回目の認証フェーズにおいて，攻撃者は正規ユーザからの認証情報9       9を盗聴し ，認証情報を同じ 長さの乱数にすり替えて送信する．サーバは受け取った認証情報で認証を行うが，攻撃者によって適当な値に変更されているので，もちろん認証失敗の応答をユーザに送信する． 8 & 回目の認証フェーズに認証失敗の応答を受け取った正規ユーザはパスワード の入力が失敗したと判断



して，新たにパスワード の入力を行い，前回と同じ 乱数9   9を使用して今回認証用の鍵

を作成する．そしてここで次回認証用の鍵9  9 を新しい乱数9  9を使用して作り出す．そして正規ユーザは先程と今回認証用の鍵が同じで次回認証用の鍵だけが違う認証情      9 と，前回と同じ今回用鍵と新たに生成した次回用鍵にハッシュ関数を一度適用したもので作った9    9をインクリメントしたカウンタの鍵

報9  として暗号化したものを

8 & 回目の認証フェーズに送信する．そこで攻撃者は前回，正規

ユーザが再送した時の認証情報9        9と今回の認証情報をすり替えて送信する．サーバはまず，今回用の鍵で認証し，認証成功する．カウンタ同期方式ではこの後，カウンタのチェックも成功し認証成功となるが，提案方式のカウンタには次回用鍵に関係し )% 評価

User

Host

1

n =k

N k , E k-1 , E 2k-1
2

Ek
Counter=m

2Counter=m-1
The last key :E 2k-2
2
It is exchanged to Rundom number This time key: E k-1
E(m), E1k-1

32

Ek , E k

E k-1

2(1)Authentication byE k-1(2)Authentication by E 2k-2

Authentication Failure

12

n = k+1 N k , E k-1 , E k-1 E(m+1), E1k-1

3

2

Ek+1 , E k+1

2

E k-1

2
Ek

Counter=m+1

It is exchanged to k th DATANGNGCounter=m-1
2
The last key : E k-2
This time key: E 2k-1
(1)Authentication by E 2k-1
(2)Counter CheckOK
NG

Authentication Failuren = k+2 Nk+2,E1k-1 , E 2k-1 E(m+2), E1k-1

3

2

Ek+2 , Ek+2

2

Ek-1

2
E k+2

Counter=m+2

Counter=m-1
2
The last key : E k-2
This time key: E 2k-1
2Authentication Success

・・・(1)Authentication by E k-1(2)Counter Check(3)DATA Update

・
・
・

OK
OK

・
・
・
X …stored data

図  提案方式に対するサービス不能攻撃たものを使用しているのでカウンタの復号の時点で失敗してしまい，第三者による改ざんを検出できる．

 )% 評価 

処理量

計算量であるが，今回認証用の鍵と認証の際に得られた次回認証用の鍵にハッシュ関数を一度適用したものと排他的論理和演算する必要があるので排他的論理和演算が以前より一つ増える事になる．しかし他の処理は全くカウンタ同期方式と同じで出来るので，カウンタ同期方式のシステムを大幅に変更する必要はなく問題を解決する事が出来る．

 

第章

おわりに
インタネット およびモバ イルコミュニケーション環境において，ユーザや通信相手の資格認証が必要不可欠なものとなっている．資格認証の方法の中には  ワンタイムパス
ワード 認証方式という極めて簡易かつ安全なプロトコルが提案されており，同期管理という実装上の問題を解決し ，携帯端末用個人認証システム9: ;<9として商品化されている．本論文では，  を実装した際に用いたカウンタ同期方式が今回認証情報の検証だけを行い，次回認証情報の検証を行わないで認証成功させるという問題があり，その問題を利用し，次回認証情報だけが違う認証情報をすり替えられて，サービ スが不能になるという問題がある事を指摘した．そしてこの次回認証情報を検証しない事による認証情報のすり替えを回避するために，カウンタの鍵に今回用鍵だけでなく，次回用鍵に関係したものを使用する事によってカウンタの復号の際に次回認証情報の検証も行えるという解決法の提案を行った．これによってすり替えを防ぐ 事が出来るようになっただけではなく，認証情報とカウンタとの間に一意な関係を持たせる事によって，カウンタか認証情報のど ちらかだけを改ざんする事が出来ないようにし，改ざんの検出が行えるようになった．この提案法によって増加した処理は排他的論理和演算一つだけと極めて少ない追加コストで問題の解決が可能となった．
今後の課題であるが，現在の方式では今回用鍵で認証が失敗する度に，認証情報が再送されてたものでないかをチェックするために前回の鍵を用いて認証を行わなければならな
い．これではただ認証が単純に失敗した際にも前回の鍵を用いて認証情報が再送でないかのチェックを行わなければならない．そこで今後の課題として認証情報の再送をより簡易に行える方法の検討を行う必要がある．また現在の方式ではサーバの応答は単純のメッセージで  

あるので，サーバの応答を偽るといったようなサーバのなりすましという危険性がある．そこでこの問題にプロトコルレベルで対応するために，ユーザの認証だけでなくサーバの認証も行える，相互認証も検討する必要もある．また現在の方式ではカウンタを用いる事によって同期の管理を行っているが，この方式では第三者からの改ざんを防ぐためにカウンタを暗号化をする必要があり，処理量が増えてしまう．今後の課題としてカウンタを用いない方式の検討も必要である．

  

謝辞
高知工科大学工学部情報システム工学科 清水明宏教授には，卒業研究を含め，多岐に渡って懇切に御指導，御教示を賜った．ここに深謝申し上げる．
また，本学大学院工学研究科基盤工学専攻 岡田 実氏，辻 貴介氏には研究途上において有益な御議論，御助言を頂いた．ここに心からお礼を申し上げる．
清水研究室学部生 中務秀和氏，河村智氏をはじめ研究室の方々には，研究途上において有益な御議論を頂いた．諸氏に心より感謝する．

  

参考文献
2&3 ( (

  >?       9 * *:  %)  &&  00.00% &1-&
2%3   @  > $ ?    

 :  4   ;  9 <*< !   A0'$  0  ,'.,', &1-&
2'3   @  ! 5   5    >     



 

     9 <*< !  *    <-&B -  &,,,&,0'   &11-2)3 上岡 隆 清水 明宏 >ワンタイムパスワード 認証方式  の安全性に関する検討9 電
子情報通信学会技術研究報告書 ; %..&)- + )'/  /'/- %..&

2/3 大石 恭裕， モバイルコンテンツ課金プロトコルの検討 ，高知工科大学卒業論文 %..&
2,3 真島 大介 羽田 知良 渋谷 充喜 清水 明宏 >モバ イル端末への  （     ）認証実装方式の検討9 電子情報通信学会技術研究報告書 ; %..&)1 +)'/  /1,' %..& 