総当たり攻撃

総当たり攻撃（そうあたりこうげき）とは、暗号解読方法のひとつで、可能な組合せを全て試すやり方。力任せ攻撃、または片仮名でブルートフォースアタック（）とも呼ばれる。

 概要 
総当たり攻撃とは、暗号や暗証番号などで、理論的にありうるパターン全てを入力し解読する暗号解読法。例としては、自転車のチェーンロックやトランクのダイヤル錠に対して、全ての番号の組み合わせ（4桁なら0000から9999まで）を片っ端から試す方法がある。このように「片っ端から」で、いずれ正解に行き着こうという方法である。

人間による操作では、気が遠くなるほどの時間的・肉体的・精神的な負荷がかかる回数の計算が必要になるが、それをコンピュータにまかせ、時間の許す限りパスワードの検証等を行う行為がコンピュータセキュリティ分野でよく知られている。時間的制約が無い限りは、確実にパスワードをクラックする方法である。

「人間が発想するパスワード」はワンパターンな事が多いため、予め言葉が予想される候補を優先的に組み合わせて検証していく辞書攻撃等が、類似する暗号解読方法としてはある。一部ハッカーなどは「的中する効率が良い辞書」の育成の為に、「過去の流出したパスワードからの傾向性分析」などに血道をあげる者もいる。あるいはどちらの辞書が優秀か、ハッカー同士で競い合うケースもある。実際には、総当たり攻撃と辞書攻撃を組み合わせて、確率が高いワードから取り掛かり、総当たりの時短を図るケースも多い。

メリット
人間が手作業で行った場合、入力が速い人が行ったところでとてつもなく膨大な時間と労力が掛かる事となるが、単純なコンピュータプログラムで自動化する事が可能であり、またコンピュータはそのような繰り返しの作業において、非常に有効に機能する。

1台のコンピュータを使った場合は、そのコンピュータの処理速度（主演算装置の処理能力だけではなく、処理に関係する部分の全体的な処理能力）に応じていずれは正解に行き当たる。分散コンピューティングにおいては、（個々のコンピュータの空き時間に）探索する役割を分担して検索するようプログラムすると、使えるコンピュータの数によっては直ちに解読できる事がある。インターネットを使用したサイバーアタックでの総当たり攻撃では、回線速度も関係してくるが、近年光ファイバー等のブロードバンドインターネット接続の普及により、回線速度がボトルネックになる事は減少している。なお、遅いか早いかはあくまでも確率の問題である。

ゆえに、もっとも原初的な方法論でありながら、時間的制約が無い、あるいは試行回数制限が無い場合など条件を満たせば、最も万能かつ普遍的に使う事が出来る方法である為、暗号解読あるいはサイバー攻撃の基礎とみなされる。

 パスワード長と解読時間の関係 

数字0～9のみのパスワード（10ワード）6桁で100万パターン、8桁で1億パターン。アルファベットA～Z(26ワード）＋数字の組み合わせ(＋10ワード合計36ワード)6桁で21億7678万2336パターン、36ワード8桁で2兆8211億0990万7456パターン。アルファベット大文字小文字を区別してA～Z・a～zおよび数字の場合(62ワード)において6桁時に568億0023万5584パターン、62ワード8桁時に218兆3401億0558万4896パターンとなる。（詳細な試行パターンは、下表参照）

+総当たり攻撃の全パターン試行回数使用する文字の種類1文字の場合4文字の場合6文字の場合8文字の場合10文字の場合数字のみ（0～9）1010,0001,000,000100,000,00010,000,000,000英字（大文字、小文字区別しない）26456,976308,915,776208,827,064,576141,167,095,653,376英字（大小区別しない）+数字361,679,6162,176,782,3362,821,109,907,4563,656,158,440,062,976英字（大文字、小文字区別）＋数字6214,776,33656,800,235,584218,340,105,584,896839,299,365,868,340,224英字（大小区別）＋数字＋記号31文字9374,805,201646,990,183,4495,595,818,096,650,40148,388,230,717,929,320,352英字（大小区別）＋数字＋記号34文字9684,934,656782,757,789,6967,213,895,789,838,33666,483,263,599,150,104,576

独立行政法人情報処理推進機構(IPA)が2008年に行った試験によれば、パスワード解析には以下の時間が必要となる。

+使用できる文字数と入力桁数によるパスワードの最大解読時間(IPA,2008)使用する文字の種類 4文字の場合  6文字の場合  8文字の場合  10文字の場合英字（大文字、小文字区別しない） 約3秒  約37分  約17日  約32年 英字（大文字、小文字区別）＋数字 約2分  約5日  約50年  約20万年 英字（大文字、小文字区別有）＋数字＋記号 約9分  約54日  約1千年  約1千万年

上記試験に使用したパソコンはIntel Core 2 Duo T7200 2.00GHz、メモリ：3GB。パスワード解析に使ったアルゴリズムは未公開。また、ネットワーク経由でのものかどうかも不明。記号は、31文字使用可能と仮定した場合。

また、Lockdown.co.ukが2009年に行った試算によると、総当たり攻撃によるパスワードの解読時間は、次のとおりとしている。

+ コンピュータ性能によるパスワード解読時間の関係(Lockdown.co.uk,2009) 使用する文字の種類  使用できる文字の選択肢の数  低速パソコン(Pentium 100MHz）  高性能パソコン(当時)  コンピュータ・クラスター又は、ワークステーション  スーパーコンピュータ 6桁の大小いずれかの英字だけのパスワード 26  5分間～8.5時間  30秒  3秒  瞬間 8桁の大小英数字を含むパスワード 62 7年～692年  253日  25.25日  60.5時間 8桁の大小英数字および記号を含むパスワード 96  229年～2万2875年  23年  2.25年  83.5日

上記コンピュータの性能は2009年の当時。なお、日進月歩で性能が向上しているため、現在は上記より大幅に高速化されているとみられる。例えば、上記の表のスーパーコンピュータは10億回/秒の解析能力とされているが、2016年の市販GPUを一つ使用して解析すれば、その10倍以上の速度を出すことができる。また、仮想通貨の採掘業者などは数千万倍の計算能力を持っている。
なお、パスワードの保管に脆弱性がある場合は、数分で突破される場合がある（例：Microsoft Windows XPと以前のバージョンにあるLMハッシュ（回避方法:レジストリに NoLMHash を設定する。））

 問題点 
総当たり攻撃は、回答となるキーワードが長ければ長い程、指数的に正解（目的の結果が得られるキーワードが出る）へ至るのに掛かる時間が長くなる。また「入力する」、「正解かどうかチェックする」、「不正解だったら1ビット追加する」を繰り返して行うため、正解かどうかチェックする対象のシステム（攻撃を被っている側）が何らかの理由で反応を返さなくなった場合には、検証作業は停止してしまう。

一般的にパスワードによる保護を行っているコンピューターは、一定時間内に規定回数以上のパスワード誤入力が続いた場合、アクセス禁止にしてしまうように設計（アカウントロック機能）されているため、総当たり攻撃による解析が難しい場合がある。銀行のキャッシュディスペンサーが一定回数以上連続して暗証番号を間違えると、それ以上の操作を受け付けなくなるのと同様である。

 対策 
攻撃されても、主要なシステムへの侵入が困難であるようシステムを構築することが大事である。よく以下のような防衛手段が挙げられるが、次項以降に挙げるように攻撃方法は日進月歩で進化するため、すぐに有効でなくなる事を考えるべきである。
多要素認証(MFA)を導入する
第2のパスワードを用意する（セキュリティーコードなど）
パスワードの試行回数を制限する（アカウントロックアウト）
IPアドレスによるアクセス制限
CAPTCHAによる回答を求める
推測されにくいユーザー名の強制
強力なパスワードポリシーの徹底
パスワードの桁数を増やす
文字種に記号や漢字などを許可しパターンを増やす
文字数、文字種（大文字、小文字、数字、記号）の組み合わせを必須とし、パターンを増やす
辞書に載っている単語や単純な文字列を禁止
ログイン試行の監視とアラート
一定の速度以上でのパスワード試行を禁止する
数分ごとに自動変化するパスワードにする
ハニーポットを設置する。ハニーポットには、Cowrieなどのツールが存在する。

 影響 
総当たり攻撃には、様々な悪影響が出る。サーバーに対しては数万～数億回（あるいはそれ以上）のアクセスが殺到するために、負荷がかかりサーバーが重くなる。CPU使用率の異常負荷から技術者が気が付く事も多い。また、防衛策を使用すればするほど、パスワード入力が複雑化していき、ユーザーの手間が増え利便性が低下する。ブルートフォースアタックを遮断するために、攻撃元のIPアドレスを遮断するのが負荷対策としてもっとも有効だが、IPアドレスを次々に変更するためにいたちごっことなり、その際に「正規のユーザー」までIPブロックに巻き込まれてログオンできなくなるなどの弊害も発生している。また、試行回数の上限に達したIDがパスワードロックされる事により正規ユーザーが使用できなくなる例も発生しているなど、サーバー担当者のみならず正規ユーザーにも悪影響が出ている。年々、パスワードの桁数は増加傾向にあり、複雑化したパスワードを忘れるなどのデメリットも発生しており、ITコストおよび事務手間コストの増大を発生させており、コスト面からも悪影響が出ている。

 逆総当たり攻撃 
「逆総当たり攻撃」（リバースブルートフォース（））は、特定のパスワード（1つまたは少数）を固定し、多数のユーザIDに対して総当たりでログインを試行する攻撃である。その狙いとしては、脆弱なパスワードを使い回している複数のアカウントを効率的に発見するというものである。IDごとに施行するため、アカウントロックアウトを回避できるのが特徴である。

これは「パスワード長が短くパスワードに使用できる文字種が少ない」システムに対して極めて有効である。例えば「IDは必ず連続した数字10桁、パスワードは必ず数字4桁」といったシステムでパスワードに偏りがないと仮定すれば、パスワード「1234」をID:1000000000からID:1000010000までの10,000件のIDに対して試行すると、一つのIDに不正ログインできる計算になる。またこの場合、銀行ATMにあるような「ひとつのIDに対するパスワードの試行回数を制限する」防御方法では防ぐことができない。1万枚のキャッシュカードを手に入れた犯罪者が1枚ずつカードを試すところを想像するとよい。

2014年1月末から3月にかけてJALおよびANAのマイレージサービスに対して行われた不正アクセスは、パスワードロックがかかる寸前まで総当たり攻撃を行い、ロック寸前にIDを変更する「総当たり攻撃」と「逆総当たり攻撃」の組み合わせで行われた。また、この際は、成功確率を上げるために確率が高いパスワードを試行された可能性が指摘されている為、考えようによっては、辞書攻撃も組み合わされた可能性もある。

 対策 
基本的な対策は、総当たり攻撃（ブルートフォースアタック）と同じだが、パスコードを固定して攻撃を行うため、「パスワードの試行回数を制限する（アカウントロックアウト）」は無効である。

 パスワードスプレー攻撃 
パスワードスプレー攻撃とは、一般的に使われがちな少数のパスワードリストを用意し、それらを多数のユーザIDに対して順番にログインを試行する攻撃である。

広範囲のユーザに対し、よく使われる簡単なパスワードで突破できるアカウントを探す。アカウントロックアウトを避けるため、各IDに対して試行するパスワードの数を少数に抑える。また、異常検知をさけるために、低頻度でゆっくりと攻撃することが多い。

リバースブルートフォース攻撃とパスワードスプレー攻撃の違いは、1つのパスワードについてログイン試行を繰り返すのか、パスワードリストに対してログイン試行を繰り返すのかが違う。いずれもアカウントロックアウトを回避できるが、異常検知に強いのはパスワードスプレー攻撃である。

 ボットネットを利用した攻撃 
ボットネット（BotNet）と呼ばれる「世界中に散らばった、ウイルス感染等によって支配した複数のコンピュータに1台ずつ順に攻撃させる」手法を利用された場合、「ひとつのアクセス元からのパスワード試行回数を制限する」「一定の速度以上でのパスワード試行を禁止する」としても防ぐことができない。1万枚のキャッシュカードを手に入れたメンバー1万人の犯罪組織が1人に1枚ずつカードを渡し、個々人がてんでばらばらにATMを訪問するところを想像されたい。

もちろんこのボットネット攻撃は、前述の逆総当たり攻撃と組み合わせることも可能である。

 脚注 

 関連項目 
 暗号理論
 辞書攻撃
 パスワード
 パスワードクラック
 レインボーテーブル

Category:セキュリティ技術
Category:コンピュータセキュリティ
Category:暗号技術
Category:暗号解読攻撃
de:Brute-Force-Methode#Kryptologie