ISUCONで話題の暗号などについて調べてみた
tags: 情報
間違ってたら教えてください><
ISUCONは燃えているか?
ISUCONが燃えている
ISUCON本戦出場のチームが取り消しとなった(後で取り消し無効となった)件1で燃えています 理由はレギュレーションの曖昧な記述,運営の対応のミスなど色々あると思います
正直僕は出場していないので理由がなんだろうと知ったこっちゃないのですが,この時に話題として出てきた以下の用語について気になったので調べました
- 平文
- シーザー暗号
- 暗号学的ハッシュ関数
- salt
- bcrypt
- clat(番外編)
↑こんな感じのノリ
平文
国語の話
まずはコトバンクを見ます
すると平文にも色々と定義があるのですが｢暗号化されていない｣ことが共通して書かれています
ということで暗号化(encryption)について調べることに
で,またコトバンクを見ると｢第三者がデータを読めない形に変換する｣ことが共通して書かれています
で,ここで問題なのは｢第三者｣が誰かということです
コンピュータならばABCとABC#は違うと認識するでしょう(比較した場合に)し,人間ならも似ているので｢もしや?｣などと勘が働きすぐにデータが分かってしまう人もいるでしょう
大会公式ブログからも
当初失格の経緯について
経緯としては、マニュアルの制約事項にあった「パスワードを平文で保存すること禁止する」が該当しました。
とブログに書かれており,この｢平文｣の解釈に関して揉めているのはリンク[^1]からわかります
平文は曖昧だとわかりましたね^^
シーザー暗号
平文と言われるとそうではないけどセキュリティ上はパスワードに"#"を連結させたものと大差ないよねということで若干文句を言われていたシーザー暗号君です❗
シーザーは英語じゃないよ
シーザーとはかの有名なCaius lulius Caesar(英語で読むとシーザー)(とよく言われますが英語で読むとCaesarで,シーザーは日本語です)のことです
めちゃくちゃ単純な暗号で,これはA→X,B→Yにするなど決まった文字数分アルファベットをずらす暗号のことです
実装もめちゃくちゃ簡単なことからわかるように暗号としては非常に弱いです
↑出典: https://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%BC%E3%82%B6%E3%83%BC%E6%9A%97%E5%8F%B7
ROT13
ROT13はシーザー暗号における,ずらす文字数を13と定めた暗号です
暗号化(平文を暗号にする処理)と復号化(暗号を平文にする処理)が同じだという特徴があります
アルファベットは26文字なので13回ずらすことを二度繰り返したら当然元のアルファベットになります...(わかりますよね?)
↑出典: https://ja.wikipedia.org/wiki/ROT13
暗号学的ハッシュ関数
ハッシュ関数はご存知の通り入力から決定的に(同じ)出力が得られる関数で,その出力の長さは全て同じです.加えて出力過程で情報を失うので暗号化とは異なり入力値を復元することはできません2
このうち
- 弱衝突耐性
- 入力が変わると規則性がなく出力が大きく変わる
- 強衝突耐性
- 同じ出力となる入力が簡単に見つけられない
- 同じ値を出力する入力を検索することが困難
という特徴を持つものを暗号学的ハッシュ関数と呼ぶようです
で,この暗号学的ハッシュ関数として考案されたのがmd53やSHA-1ですが,どっかの誰かさんがこれを破る方法を思いついてしまったので別の暗号学的ハッシュ関数が今は使われているようです
SHA-2
SHAは"Secure Hash Algorithm"の頭文字から来ています
上で書いたようにSHA-1は"Secure"でないくせにSHA-1と名乗っているようです
↑贅沢な名じゃないのか...
はい
で,進化したものがSHA-2というものらしいです
SHA-2は下4つのハッシュ関数をまとめたもので単一のハッシュ関数ではないです
- SHA-224
- SHA-256
- SHA-384
- SHA-512
他にもSHAを関するハッシュ関数があるので興味のある人は調べてみてください(投げやり)
salt
いきなりですが塩(salt)の話をしたいと思います
saltというのはパスワードに加えるランダムに生成したデータのことです
この後にハッシュ関数に通すことによって生成されるハッシュ値をより強固なものにします
｢獣のような攻撃｣と｢虹色のテーブル｣
パスワードを攻撃してくる輩は色々考えます
その中でもsaltが無効なものと有効なものがあります.
前者からは"brute force attack"と,後者からは"rainbow table attack"と呼ばれるものを紹介したいと思います
チンパンジー
brute force attackはその名の通りチンパンジー的発想から生まれています
つまり全種類の文字列を試せばどれかは当たるだろうという攻撃法です
ただ,チンパンジーが考えるレベルなので当然計算量が半端ないことになっています
例えばSHA-512のハッシュ値は512ビットです
$2^{512} \simeq 10^{154}$パターンあり1回の値を出すのに$10^{-16}$秒かかる[^3]として全通り計算するのに165日かかります
この攻撃はどのハッシュ値に対しても同じ程度に効果がないのでsaltを付け加えようが付け加えまいが効果はないです)元々効率が悪すぎるので)
塩が...効きますねぇ!!
rainbow table attackの説明です
あらかじめレインボーテーブルという適当な入力とそのハッシュ値が対応している表を作ります
そして,手に入れたいパスワードのハッシュ値と比較して実際のパスワードを推察します
実際にはもっと色々しているのですがこれだけで記事が一つ書けるレベルで面倒なので今回はパスで＾＾；
ただこの攻撃はsaltを使うことで同じパスワードでもハッシュ値がランダムに大きく変化するので予防できます(ハッシュ関数を複数回使うことでも可能)
おまけ
おまけにもう一つ有名な｢辞書攻撃｣に関してざっくり説明します
これはその名の通り辞書に載っている単語を延々と試す攻撃です
謝辞
すみません,今までの説明は暗号学におけるsaltでしたね...
お詫びとして塩をかけておきます
bcrypt
ISUCONではこの処理がボトルネックだったらしいです
Blowfish
bcryptにはこのブロック暗号(暗号化と復号化に使う鍵が同じ暗号)であるblowfishが使われています
遅い方が安全でもパスワードの長さは変えたくない
時代とともにコンピュータのスペックは上がりますが,それに伴いbrute force attackなど単純にマシンパワーが必要なクラッキングの手法も強力になります
これに対抗するべくより遅いハッシュ関数が求められますが,同時にパスワードの長さが一定であることも考えないといけません
そこで登場したのがbcryptです
bはblowfish,cryptはUNIXで使われているハッシュ関数の名前です
これまた詳しく説明すると記事が長くなるので割愛します...
大雑把にはbcryptの強みは以下の通りです
- blowfishを使うことで遅くハッシュされるようにしている
- brute force attackや辞書攻撃に対応している
- saltを使っている
- rainbow table attackに対応している
わざと遅くするという特徴から確かにボトルネックになるよねと言った感想を持ちました
clar
調べてみました系らしく最後はわかりませんでした❗を入れることにします
ISUCON運営がclarを無視した
というような感じの使われ方をしていて,slackでのメッセージを無視していたことからはっきりさせること(clarification)と思っているのですがどうでしょう
誰か復号化を手伝ってください❗
最後にどうでもいいことを最後に2つ
1つ目
ISUCONって"Iikanjini Speed Up CONtest"の略称だったんですね
2つ目
夏に行っていたインターン先(W)でWebも何もかもダメダメだったので今(主に電気回路と電磁気の)勉強をしています
その流れでISUCONにも興味が湧いたので一緒に過去問を解いてくれる学生を募集しています
1人Voyageでインターンをしていた強い人が見つかっているのですが(Goも書ける)3人で出てみたい...
もう一人誰かいないかな...
