  |
はてなキーワード: ハッシュ関数とは
ビットコインマイニングは、ビットコインネットワークのトランザクションを確認し、新たなビットコインを生成するプロセスである。
これは数学的な問題を解くことによって行われる。具体的には、以下のようなステップが含まれる：
1. 新しいブロックの作成： マイナーは未確認のトランザクションから新しいブロックを作成。
2. ハッシュの計算： マイナーは新しいブロックのハッシュを計算。ハッシュ関数は、任意の長さのデータを固定長のハッシュ値に変換。ビットコインでは、SHA-256というハッシュ関数が使用される。
3. 難易度ターゲットの比較： 計算されたハッシュが難易度ターゲット以下であるかどうかを確認。難易度ターゲットは、ネットワーク全体のマイニングパワーに基づいて調整される。
4. ブロックの追加： ハッシュが難易度ターゲット以下であれば、そのブロックは有効とされ、ブロックチェーンに追加される。そして、そのブロックを作成したマイナーは新たなビットコイン（ブロック報酬）とトランザクション手数料を受け取る。
これらのステップを繰り返すことで、ビットコインマイニングは行われる。
このプロセスは競争的であり、最初に問題を解いたマイナーだけが報酬を受け取ることができる。
ISUCON 9 参加記 - kyuridenamidaのブログ
ISUCON9 レギュレーション違反の対応について [追記あり] : ISUCON公式Blog
「パスワードを平文で保存すること禁止する」というレギュレーションに対して、「パスワード+#」が違反したと見なされたのが最初の見解。
ここでいう「平文」が出てくる文脈は、初期実装のbcryptからも明らかなように暗号理論の文脈だと考えられる。ここに疑念を挟む人はまずいないだろう。
そして暗号理論の文脈で言う「平文」とは明確な定義があり、今回で言えば「パスワード文字列そのもの」だ。
これは学問的には異論の余地がないので、このことを知らなかった人や、どっちもどっち論に立っていた人は、素直にごめんなさいすべきだ。
たとえば以下のツイート主が主張するような「原理的に元に戻せるのは全部平文」なんて定義は暗号理論では受け入れられていない。複合可能なら全部平文なの？
どこまでが平文って、そりゃ原理的に元に戻せるのは全部平文でしょ。Base64で保存してたパスワードが流出しました！でも平文じゃないから安全です！とでもいうのかよ(´･_･`)いやまじで。— Hideyuki Tanaka (@tanakh) September 11, 2019
もう話はここで終わってもいいのだが、まだまだ論点があるので続ける。
この立場に立っている人も結構いるように見かけたが、レギュレーションからそれが読み取れないので無理がある。
第一に、レギュレーションでは暗号強度に関して全く触れられていない。
第二に、OKな暗号強度の線引きがあるのならベンチマークでチェックすべきだ。
特に後者は今回（自分の知る限り）誰も言っていなかった気がするが、セキュリティの側面も持たせるのなら仕組みで担保しなきゃダメだろう。
運営側が想定していたレギュレーションが、平文よりも高い暗号強度での保持であったとしても、そのことが明確にわかる文章になっていないので、レギュレーション文言の実装バグとしか言いようがない。
実はこの立場で運営を擁護していた人が一番多かった気がしてしまうのだが、見事にハシゴを外されてドンマイとしか言いようがない。
たとえば有名人だとこの人とか。
平文保存がルールに抵触したかどうかは全く興味ないけど、「パスワードの末尾に#つけてから保存してたから平文じゃないです」っていうのは言い訳としては成り立たないよね。ウェブアプリケーション開発者・運用者として、仮にパスワードデータベースが流出したとして、顧客にそう言えるの？っていう— Kazuho Oku (@kazuho) September 11, 2019
残念ながらISUCON運営公式の言説として、平文とまではいかなくても暗号強度を犠牲にすることは想定内であったことがアナウンスされている。
bcryptによる負荷の対処方法として、サーバを追加、軽量なハッシュ関数での代替、あるいは平文での保持を開発チームにおいて想定しましたが、現実の問題として、パスワードなどの情報流出などの事件が発生しており、平文での格納は一般的に推奨されない実装方法だという認識を同時に持ちました。
ウェブアプリケーション開発者として、みたいなことを大上段に出されても、ISUCONは現実のウェブサービスであれば許容できないようなハックを用いてでも高速化するコンテストである、という文脈は、それこそ過去のISUCONで確立されてきたものなわけで、ISUCONを知らないのなら黙っといたほうがいい、としか言いようがない。
なお実サービスでは当然やらないことをやるのはどうよ、みたいな話を持ち出すと、今回おそらく運営の脳内レギュレーションではMD5あたりもOKだったのでは、という辺りを考え出すと、やはりどこがラインなのか明確じゃないよねって話に結局なる。（2019年にMD5を許す実サービスは流石にないよね？）
そこを明確にしたいなら文章化（脳内レギュレーションの実装）をがんばるか、ベンチマークなどで担保するしかなかったという結論は変わらない。
それが出来ないなら何でもありになるのは当然の帰結だし、それを美学だとかプライドだとか個々人の価値観が大きく異なる概念で縛ろうとするのは、こと競技に関しては真摯な姿勢ではない。
（たとえば大相撲のような競技でも、横綱が変化しちゃダメという美学に関して喧々諤々な議論が起きたりする）
王道はこれ。
脳内レギュレーションを明文化できていなかった、という反省を踏まえて次がんばるしかない。
今回は他チームから問い合わせがあったらしいが「平文」の定義をきちんと調べさえすれば、想定していた回答ではないが「パスワード+#」は平文ではないので今回のレギュレーション違反には当たらない、という結論を伝えるべきだったように思う。
現実的な落とし所はこっちだったかもしれない。おそらく該当チームも、これなら反発はしなかったんじゃないか。
ということで騒ぎは終わりにしたい、という気持ちに関しては多くの人の一致を見るはずだ。
一方で運営側の朝令暮改のような対応に不信感や疑問を持つ人が多いのも事実だと思う。
ボランティアでがんばってるんだから目を瞑ろう、という感情的な意見もまあ分かる。お疲れ様だ。
またこれは個人的な見解だが、特に今回の予選問題は過去最高傑作と言っても過言ではないくらいよく出来ていると思うし、流通額をスコアとするビジネス上の目的を意識させるというメッセージ性も素晴らしいと思うので、今回の一件を持って問題作扱いされてほしくない気持ちは正直ある。
でもきちんと総括しないで先に進んでも誰も幸せにならないのもまた事実だと思う。
ということで、運営側はレギュレーション文言がバグっていたことをちゃんと認めて、該当チームに落ち度が全く無かったことを謝罪した上で、次に進んでほしい。
競技中に質問に答えなかったこと、参戦後のブログを根拠に裁定をくだしたことも悪手だと思うが、それ以上に、「レギュレーション違反はなかった」ことをきちんと伝えて名誉回復してあげるのが一番の筋のはずだ。
ブロックチェーン流行ってるじゃん。あれ使えば何でも、改竄が絶対不可能になって、所有権を保証できるんだろ。超すげー。
ということで、俺様が考えるブロックチェーンの使いどころを書き記す。よく聞け。
これらの違いは、早い話がブロックチェーンを誰が運用してるんですか、という話だ。
パブリックブロックチェーンでは、誰もがブロックチェーンを運用するノードになれる。そのために、現実的に不正ができないよう、ノード間で見張り合うシステムが必要になる。
Bitcoinのようにお金を扱うシステムで、皆が台帳を持ったら、誰もが、自分のところにお金が入ってきたことにしたり、自分の使ったはずのお金を使ってないことにしたり、といったことをやりたがる。
Bitcoinは、Proof of Workという仕組みで、そういった不正を現実的にはできないようにすることで、お互いに信用できない人同士の分散台帳というものを可能にした。
Bitcoinが革新的だったのは、「信用できない人たちに分散台帳を管理させたらみんな好き勝手に不正するに決まってる！」という常識をぶち破り、そういった人達による台帳管理ができることを示したから。
企業が業務や商売でブロックチェーンを使おうとすると、誰もがノードになれるとか、誰もがノードにアクセスできるとか、そういった仕組みは望まれないことが多いらしい。
そこで、自分たちだけの閉じた環境でブロックチェーンを作ろうという試みが、プライベートブロックチェーンだ。
ここでは、Bitcoinが起こした革命である、信用できない人たちによる分散台帳管理なんてものは必要がない。
プライベートブロックチェーン、いろいろと研究されたり、実証実験が行われたりしているが、
「なんでブロックチェーンでやる必要があるんですか?」にどう答えられるのか、よく分からない。
「なんでブロックチェーンでやる必要があるんですか?」については、後でさらに深く掘り下げる。
プライベートブロックチェーン意味ないよね、と気づいた人達が次に考えたこと。
銀行間とか、企業間とか、組織をまたいでブロックチェーン作ればいいじゃないか、と。
組織力学の都合上、そうするのがいいなら、勝手にやってください。
けれど、Bitcoinが起こした革命である、他のノードに嘘ついてまで不正をしようとしている者同士が、ひとつの台帳を保持できる、というその特性、必要ある?
今も銀行間でいろいろ、電子データをやりとりしてると思うけど、そんな不正しようとしてる銀行あるの?
「なんでブロックチェーンでやる必要があるんですか?」に、技術的には答えられないのがコンソーシアムブロックチェーンだ。
ブロックチェーン使って何かやろうとすると、大体の人がぶち当たるのが「それ、ブロックチェーンでやる必要あるんですか?」「データベースじゃダメなんですか?」って問題だ。
この問題に陥るのは大抵、ブロックチェーンの持つ自律分散の思想を理解せずに、誰かが管理しよう、特権を持とう、中心的存在になろうとしてるからだ。
管理者がいるなら、管理者がデータベースを作って、そこでやればいい。その方が話はシンプルだ。
もっとひどいのは、データベースはデータベースで別で置いて、ブロックチェーンに載せられるカラムはブロックチェーンに載せて、その取引IDをデータベースに記録しようと考えている場合だ。
全部データベースでやった方が作るのも運用するのも楽なことになぜ気づかない。アホなのか。
改竄防止だトレーサビリティだと騒いでいる人がいるが。そもそもブロックチェーンは何を保証するのか。
ブロックチェーンに載ってからは、確かに改竄は難しい。電子署名が不正な取引はブロックチェーンに載せないこともできる。
けれど、必要なタイミングで正しい入力を与えるのは、ブロックチェーンを使う側の仕事で、
電子署名などのプログラム的に検証できるもの以外で不正が行われても、ブロックチェーンは何も検知できない。
ブロックチェーン自体は最近の発明だが、ブロックチェーンで使われている、ハッシュ関数、電子署名などは、
もっと昔から改竄検知や偽造防止に使われていた技術で、それらを適切に利用すれば、ブロックチェーンを使わずとも、大抵の目的は達成できる。
これらの話、知っている人には「うん、そうなんだよねー」って感じだったと思うが、知らなかった人は「じゃあブロックチェーン、一体何に使えるんだよ」と苛ついてきた頃かと思う。
ブロックチェーンは何にも使えないのか。いいや、そんなことはない。
Bitcoinは、送金するのには手数料がいるが、残高照会は無料でできる。他のブロックチェーンも同様のものが多い。
そこで、参照されることは多数あるが追加、変更されることが滅多にないものをパブリックなブロックチェーンに載せて、データ置き場として活用する方法を考えれば、
ブロックチェーンを使って低コストで何かをすることは可能かもしれない。
ブロックチェーンは、誰も管理しなくても動く夢のような仕組みだ。
ブロックチェーンと、staticなHTMLやjsなり、なんかのスクリプトなりがあれば成り立つシステムを作ると、作った人が何もしなくてもネットワークが維持されるシステムの完成だ。
「量子コンピューターが一般化したら 」というと焦点がぼやけるから
という前提でいこう。
何か中央集権的な手段で、過去の取引履歴を保護してやらないかぎり
ビットコインでは過去の取引履歴から口座の残高を求めるので、取引履歴が捏造されると
ある人はあなたの口座には100BTCがあると言い、
別の人はあなたの口座には1BTCも入っていないと言う状況になる。
しかし、過渡期に量子コンピュータでも有効なハッシュ関数などを使って
「『正しい』過去の取引履歴」が中央集権的に確定させることはできる。
そうすれば前述の問題は発生しなくなる。
ブロック生成の仕様を、量子コンピュータでも解けない計算に切り替えれば、
運用も続けられる。
まじな話をすると、N予備校のプログラミング入門コースやるのがオススメ。
一日8時間勉強時間があるなら、だいたい一ヶ月で終わる内容。
月額1000円だけどしっかり勉強すれば一ヶ月の無料期間中に終わると思う。
もともとN高等学校のノンプログラマーの生徒をWebエンジニアとして就職させるために作られたカリキュラムで講師曰く去年はこれで二人エンジニア就職を決めたらしい。
内容も相当親切に説明していて、プログラミングで何か作るだけじゃなくて、就職に必要な環境構築やセキュリティまでみっちりやる。
で講師が書いてる入門コースで習うことがまとめ。テキスト教材もあるけど授業も1項目を2時間で説明している。授業は週2の生放送とそのアーカイブがある。
↓みたいなことが学べる
----
Web ブラウザとは (Chrome, デベロッパーコンソール, alert)
はじめてのHTML (VSCode, HTML, Emmet)
さまざまなHTMLタグ (h, p, a, img, ul, tableタグ)
HTMLで作る自己紹介ページ (HTMLタグ組み合わせ, コンテンツ埋め込み)
はじめてのJavaScript (JS, ES6, エラー)
JavaScriptでの計算 (値, 算術演算子, 変数, 代入)
JavaScriptで論理を扱う (論理値, 論理積, 論理和, 否定, 比較演算子, if)
JavaScriptのループ (ループ, for)
JavaScriptのコレクション (コレクション, 配列, 添字, undefined)
JavaScriptの関数 (関数, 関数宣言, 引数, 戻り値, 関数呼び出し, 再帰)
JavaScriptのオブジェクト (オブジェクト, モデリング, プロパティ, 要件定義)
はじめてのCSS (CSS, セレクタ, background-color, border)
CSSを使ったプログラミング (transform, id, class)
Webページの企画とデザイン (企画, 要件定義, モックアップ, 16進数カラーコード)
診断機能の開発 (const, let, JSDoc, インタフェース, 正規表現, テストコード)
診断機能の組込み (div, 無名関数, アロー関数, ガード句, truthy, falsy)
ツイート機能の開発 (リバースエンジニアリング, URI, URL, URIエンコード)
LinuxというOS (VirtualBox, Vagrant, Ubuntuのインストール, OS, CUIの大切さ)
コンピューターの構成要素 (ノイマン型コンピューター, プロセス, lshw, man, ps, dfの使い方)
ファイル操作 (pwd, ls, cd, mkdir, rm, cp, mv, find, ホストマシンとの共有ディレクトリ)
標準出力 (標準入力、標準出力、標準エラー出力、パイプ、grep)
vi (vimtutor)
シェルプログラミング (シバン, echo, read, 変数, if)
通信とネットワーク (パケット, tcpdump, IPアドレス, TCP, ルーター, ping)
サーバーとクライアント (tmux, nc, telnet)
HTTP通信 (http, https, DNS, hostsファイル, ポートフォワーディング)
GitHubでウェブサイトの公開 (GitHub, リポジトリ, fork, commit, 情報モラル)
イシュー管理とWikiによるドキュメント作成 (Issues, Wiki)
GitとGitHubと連携 (git, ssh, clone, pull)
GitHubへのpush (init, add, status, インデックス, commit, push, tag)
Gitのブランチ (branch, checkout, merge, gh-pages)
Node.js (Node.js, nodebrew, Linux, REPL, コマンドライン引数, プルリク課題)
集計処理を行うプログラム (集計, 人口動態CSV, Stream, for-of, 連想配列Map, map関数)
アルゴリズムの改善 (アルゴリズム, フィボナッチ数列, 再帰, time, プロファイル, nodegrind, O記法, メモ化)
ライブラリ (ライブラリ, パッケージマネージャー, npm)
Slackのボット開発 (slack, mention, bot)
HubotとSlackアダプタ (hubot, yo)
モジュール化された処理 CRUD, オブジェクトライフサイクル, filter)
ボットインタフェースとの連携 (モジュールのつなぎ込み, trim, join)
同期I/Oと非同期I/O (同期I/O, 非同期I/O, ブロッキング)
例外処理 (try, catch, finally, throw)
HTTPサーバー (Web, TCPとUDP, Webサーバーの仕組み, Node.jsのイベントループ, リスナー)
HTTPのメソッド (メソッド, GET, POST, PUT, DELETE, CRUDとの対応)
HTMLのフォーム (フォームの仕組み, form, input)
HerokuでWebサービスを公開 (Webサービスの公開, heroku, dyno, toolbelt, login, create, logs)
認証で利用者を制限する (認証, Basic認証, Authorizationヘッダ, ステータスコード)
Cookie を使った秘密の匿名掲示板 (Cookie, Set-Cookie, expire)
UI、URI、モジュールの設計 (モジュール設計, フォームのメソッド制限, リダイレクト, 302)
フォームによる投稿機能の実装 (モジュール性, textarea, 303)
認証された投稿の一覧表示機能 (パスワードの平文管理の問題, 404, テンプレートのeach-in)
データベースへの保存機能の実装 (データベース, PostgreSQL, 主キー)
トラッキングCookieの実装 (トラッキング Cookie, IDの偽装, Cookie の削除)
削除機能の実装 (データベースを利用した削除処理, 認可, サーバーサイドでの認可)
管理者機能の実装 (Web サービスの管理責任, 管理者機能の重要性)
デザインの改善 (Bootstrap, レスポンシブデザイン, セキュリティの問題があるサイトを公開しない)
脆弱性 (脆弱性, 脆弱性で生まれる損失, 個人情報保護法, OS コマンド・インジェクション)
XSS脆弱性の対策 (XSS, 適切なエスケープ処理, リグレッション)
パスワードの脆弱性の対策(ハッシュ関数, メッセージダイジェスト, 不正アクセス禁止法, パスワードジェネレーター, 辞書攻撃)
セッション固定化攻撃脆弱性の対策 (セッション, セッション固定化攻撃, ハッシュ値による正当性チェック)
より強固なセッション管理 (推測しづらいセッション識別子, 秘密鍵)
安全なHerokuへの公開 (脆弱性に対する考え方, HTTPの廃止)
Webフレームワーク (Express.js, フレームワーク導入, 簡単なAPI, セキュリティアップデート, Cookie パーサー, ミドルウェア, 外部認証, ロガー)
ExpressのAPI (app, Properties, Request, Response, Router)
GitHubを使った外部認証 (Passport, OAuth)
テスティングフレームワーク (Mocha, レッド, グリーン, リファクタリング)
継続的インテグレーション (CircleCI)
クライアントのフレームワーク (Webpack, Chrome 以外のブラウザでもES6)
DOM操作のフレームワーク (jQuery, jQueryアニメーション, this)
AJAX (jQuery.ajax, クロスドメイン, 同一生成元ポリシー, x-requested-by, CORS)
WebSocket (WebSocket, WebSocketの状態遷移, Socket.io)
RDBとSQL (DDL, DCL, CREATE, DROP, INSERT, DELETE, UPDATE, WHERE)
テーブルの結合 (外部結合, 内部結合, 片側外部結合, JOIN ON)
インデックス (インデックス, 複合インデックス, Bツリー)
集計とソート (SUM, COUNT, ORDER BY, GROUP BY)
「予定調整くん」の設計 (要件定義、用語集、データモデル、URL設計、モジュール設計、MVC)
認証とRouterモジュールの実装 (Mocha, supertest, passport-stub, モックテスト)
予定とユーザーの保存 (セキュリティ要件, UUID, 複合主キー)
予定とユーザーの一覧の表示 (非同期処理, Promise, then)
出欠とコメントの表示 (入れ子の連想配列, Promise.all, 子どもからデータを消す)
出欠とコメントの更新 (Promiseチェイン, リファクタリング)
はてなブックマーク - 新井俊一のソフトウェアビジネスブログ: 今話題のブロックチェーンとは何なんだ？ 部外者の技術者として考察してみる。
はてなブックマーク - イーサリアム共同創業者Vitalik Buterinが語る、ブロックチェインの真の価値 | ビットコインニュースのBTCN
ビットコインがブロックチェーンより重要な理由 | TechCrunch Japan
「ブロックチェーン技術は、蒸気機関や燃焼機関と同様に扱われるべき世紀の発明であり、金融界どころか、その外までをも変貌させてしまう可能性を秘めている。」
ブロックチェーンというのは、ブロックチェーン+Pow+トークンによる経済インセンティブ、この３つがセットになっているのが決定的に重要。 対検閲性、対改ざん性、非中央集権は、その３つがあって始めて達成される。— 佐藤ヒロシ(※旧大石哲之） (@tyk97) 2015, 12月 22
ロシアの政治家でIT起業家でもあるニコライ・ニキフォロフはブロックチェーンテクノロジーに注目
http://itpro.nikkeibp.co.jp/article/COLUMN/20071031/286012/?ST=selfup&P=2
http://developers.linecorp.com/blog/ja/?p=3591
Letter Sealing って何でしょうか。私気になります。
必要な範囲で、原文を引用しています。原文は先に引用元のアドレスと閲覧日時を記し、引用記法によって地の文と識別できるようにしています。
ECDHとAES256-CBC 使ってみた。通信相手の認証については読み取れない。
図2 において、 Server のところで Re-Encryption (一度復号されて、再度暗号化されている) ことが明示されています。
この図を素直に読むと、送信者からサーバーまでの通信路は暗号化されているものの LINE のサーバーが受信したところで復号されて平文で保存され、サーバーから受信者までの通信路は暗号化されていると理解できます。文脈から、この流れを変えたいのであると推測できます。
http://developers.linecorp.com/blog/ja/?p=3591 より引用、2015年10月14日 22時40分に閲覧：
加えて、LINEでは、仮に通信ネットワークの傍受が行われたとしてもメッセージを覗くことができないように、公開鍵暗号(public key encryption)方式を使っています。ユーザーに対してLINEアプリを提供する際、暗号化ができる公開鍵のみをアプリに入れて提供し、ユーザー端末とサーバが接続されたときだけLINEサーバでのみ解析できる暗号化された安全なチャネルを作ります。こうすることで、SSL(Secure Socket Layer)より軽く、LINEの全バージョンで使用できる安全な暗号化を実現できます。
SSL はすでに時代遅れの代物で、 2015年秋現在は皆さん TLS を利用されていることでしょう。 Web ブラウザで SSL 2.0 や SSL 3.0 を有効にしているそこのあなた、今すぐ無効にしましょう。
TLS では、公開鍵暗号方式や共通鍵暗号方式、電子証明書、暗号学的ハッシュ関数といった複数の暗号技術要素を組み合わせて安全な通信路を確保しています。
RSA に代表される公開鍵暗号方式は一般的に AES に代表される共通鍵暗号方式と比べて計算量が大きい、つまり重たい処理となります。
このため TLS では、通信路を流れるデータの暗号化に共通鍵暗号を用いて、共通鍵の共有や相手の認証のために公開鍵暗号方式を用いるのが一般的です。
仮にメッセージの暗号化に RSA を用いているとしたら、 SSL より軽いという点をどのように実装しているのか気になります。
http://developers.linecorp.com/blog/ja/?p=3591 より引用、2015年10月14日 22時40分に閲覧：
ユーザー側のLINEアプリ(クライアント)には、サーバが発行したRSA鍵を使用してデータの暗号化に使う暗号化鍵値を共有します。この鍵を利用してデータを暗号化すると、第三者はメッセージを見ることができなくなります。
これは上で説明したとおり SSL や TLS でも行っていることです。
RSA を用いているので安全であるという主張をしていますが、メッセージの暗号化に用いられている暗号スイート（アルゴリズムの種類、鍵の長さ、ブロック暗号の場合は暗号利用モード、そしてハッシュアルゴリズムの種類）は、その通信路が安全であると判断できるか否かを決める大切な情報です。
http://developers.linecorp.com/blog/ja/?p=3591 より引用、2015年10月14日 22時40分に閲覧：
既存のRSA方式も秘密データの共有に使う安全な方式ではありますが、鍵管理の面から見ると、ユーザー側の端末でそれぞれのRSA鍵をすべて管理しなければならないという問題があり、その代替手段としてDHを使用するようになりました。
DH および ECDH による共通鍵暗号に用いる鍵の交換は SSL や TLS でも実装されており近年では広く使われています。 SSL より軽いと主張し、 SSL や TLS が公開鍵暗号方式以外の要素によって担保している安全性をどのように確保しているか不明な実装に比べると、大きな改善です。
なお SSL や TLS においては通信相手の公開鍵を全て管理する必要がないように、上で説明した電子証明書による公開鍵基盤 (PKI) の仕組みを利用しています。
つまり共通鍵暗号に用いる鍵の交換にどのような手段を用いるかは、鍵管理とは（ほぼ）独立です。
http://developers.linecorp.com/blog/ja/?p=3591 より引用、2015年10月14日 22時40分に閲覧：
ここでメッセージの暗号化に使用している暗号化アルゴリズムはAES-CBC-256という方式で、現在一般に使われている暗号化アルゴリズムの中で最も強度が高いと評価されています。
メッセージ認証と組み合わせない CBC はビット反転攻撃に弱いことが知られています。 GCM ではデータの暗号化と認証を同時に行うためビット反転攻撃に耐性があります。 AESを GCM で利用するのは、 最近の TLS の実装では広く用いられており、 Google や twitter も利用しています。
CBC も CBC-MAC のようにメッセージ認証と組み合わせることでビット反転攻撃に強くなります。
図6 のとおり、 ECDH で共通鍵暗号に用いる鍵の交換を行うにしても通信相手の公開鍵は必要です。 上で説明したとおり鍵管理という問題への解決策になりません。また公開鍵が本当に通信相手のものであることをどのように検証するのかについても不明です。通信相手の検証は、送信側では秘密の話を他の人に知られないように、受信側では他の人になりすまされないように、双方にて必要です。
ここからは安易なパターンの想像ですが、通信相手の公開鍵情報は LINE ユーザー情報の一部として LINE サーバーで管理されており、必要に応じて安全な通信路を用いて LINE サーバーから取得するようなものではないかと思います。公開鍵情報のやりとりに用いられる通信路に正しく実装された TLS が用いられていて、サーバーとクライアントの両方が認証されていて、現在の水準から見て妥当なレベルの暗号スイートが用いられていることを願うばかりです。
公開鍵と秘密鍵がどこでどのように保管されているのか気になります。各端末で保管するのが安全ですが、サービスの要求として端末を乗り換えてもメッセージが読めるという条件を安易に満たすために秘密鍵を LINE サーバーに預託していないことを祈るばかりです。
ECDH 鍵の生成は計算量が大きい処理であり質の良い乱数を必要とします。 PC に比べると非力なスマートフォンで生成した鍵の質をどのように担保しているのか気になります。
先ほど閲覧したところ、上記引用箇所の多くは削除されていました。公開鍵が本当に通信相手のものであることをどのように検証するのかについては明らかではないようです。 LINE サーバーが介在する形であれば、鍵をすり替えることで別のユーザーになりすますことが可能でしょう。または、 LINE アプリに何か細工をする方がより簡単でしょう。
ECDH 鍵はその場限り (ephemeral) という説明がないので Perfect Forward Secrecy ではないと考えられ、望ましくないという意見もあるようです。 LINE サーバーとの間に安全な通信路を確立する目的で ECDH 鍵を用いる場合、 LINE サーバーが用いる秘密鍵の漏洩は全てのユーザーに影響を与えうるため PFS は非常に重要です (TLS を用いた Web サーバーでも同様です) 。一方ユーザー間でメッセージを暗号化する場合、ユーザー所有の ECDH 鍵についてはそのユーザーに影響が限定されます。通信相手ごとに必要なその場限りの鍵生成とユーザー所有の ECDH 鍵を利用した鍵交換にかかる計算量と ECDH 鍵漏洩のリスクを天秤にかけて PFS を採用しないという判断かもしれません。
通信の秘密という観点ではメッセージの内容だけではなく誰と通信したか (または、していないか) という情報も守りたくなります。宛先を LINE サーバーで確認できない形に暗号化されるとメッセージの配送ができなくなるため、通信相手や通信の有無については秘密ではないと考えられます。
「プロテクトかけたアルゴリズムを実装したバージョンに差し替え」たなんて言われると本当に「プロテクト」がかかっているのか確かめてみたくなるのが人情というもの。というわけで、プロテクト強化後のもふったー(v0.9.6b)からconsumer secretが抜けるか試してみた。結論から言うと、あっけなく取り出せた。以下に手順を記す。
動作がよくわかっていないアプリケーションを解析して仕様を明らかにすることをリバースエンジニアリングと呼ぶ。ソフトウェアのリバースエンジニアリングは基本的に対象を逆アセンブルしてひたすら読むことによって行う(その補助に1命令ずつ実行してレジスターやメモリーの様子を観察することもある)。しかし、よっぽど小規模なものでなければオブジェクトコード全体を逆アセンブルして最初から最後まで読むなんてのは不可能だ。人間の読速度には限界があるし、時間も有限だからだ。そして、詳しい動作を知りたい部分というのは全体のごく一部であることが多いので全逆アセンブリを読むのには非常に無駄が多い。
だから、リバースエンジニアリングではいかに詳らかにすべき動作を行っているコードを絞り込むか(=読むべき逆アセンブリを少なくするか)が重要になる。
この場合も同様だ。TwitterのGUIクライアントを頭から読むのは到底無理なので、どうやって解析すべきコードの範囲を狭めるかを考えた。それにはOAuth認証においてconsumer secretがどのような役割を果たすのかを知る必要がある。
OAuth認証で、consumer secretはそのままサーバーに送信されたりはしない。signatureの生成にHMAC-SHA1が使われ、その鍵にconsumer secretが使われる。HMACは次のように算出される。
HMAC (K,m) = H ((K ⊕ opad) ∥ H ((K ⊕ ipad) ∥ m))
ここで
である。
まずはこのあたりから攻めようと思った。SHA-1の計算にはいくつか特徴的な定数が使われるので、そこからSHA-1の計算に使われているであろう関数444190を特定する。この関数のエントリーポイントに中断点(ブレークポイント)を設定してOAuth認証をさせるべくもふったーの「ブラウザで認証」ボタンを押す。狙い通り中断するので関数を抜けるまで実行する。関数401100の4012DAに出た。少し下を見るとこのようになっている。
CPU Disasm Address Hex dump Command Comments 00401311 |. 33F6 xor esi, esi 00401313 | 8D8C24 A40000 /lea ecx, [local.54] 0040131A |. 394C24 14 |cmp dword ptr ss:[local.90], ecx 0040131E |. 75 0E |jne short 0040132E 00401320 |. 3BF5 |cmp esi, ebp 00401322 |. 73 29 |jae short 0040134D 00401324 |. 0FB68434 A400 |movzx eax, byte ptr ss:[esi+esp+0A4] 0040132C |. EB 21 |jmp short 0040134F 0040132E | 3BF5 |cmp esi, ebp 00401330 |. 73 1B |jae short 0040134D 00401332 |. 8B5424 18 |mov edx, dword ptr ss:[local.89] 00401336 |. 52 |push edx ; /Arg1 = [LOCAL.89] 00401337 |. 8D8C24 FC0000 |lea ecx, [local.33] ; | 0040133E |. 8BD6 |mov edx, esi ; | 00401340 |. E8 CB4D0000 |call 00406110 ; \mofooter.00406110 00401345 |. 83C4 04 |add esp, 4 00401348 |. 0FB6C0 |movzx eax, al 0040134B |. EB 02 |jmp short 0040134F 0040134D | 33C0 |xor eax, eax 0040134F | 34 5C |xor al, 5C 00401351 |. 888434 B80000 |mov byte ptr ss:[esi+esp+0B8], al 00401358 |. 83C6 01 |add esi, 1 0040135B |. 83FE 40 |cmp esi, 40 0040135E |.^ 72 B3 \jb short 00401313 00401360 |. 895C24 3C mov dword ptr ss:[local.80], ebx
0040134F | 34 5C |xor al, 5C
が注意を引く。もしかしてこれはopadとのxorではないか?
00401351 |. 888434 B80000 |mov byte ptr ss:[esi+esp+0B8], al
はxorした結果を格納している。
先ほどの中断点は無効化しこのループを抜けた地点である401360まで飛ばす。この時点でesp+0B8を見ると次のようになっている。
Hex dump 64 2E 16 64|37 04 32 6D|0F 0D 26 29|3A 37 1F 2F| 18 69 6E 6E|0D 25 29 33|11 34 29 69|12 36 24 1E| 05 16 33 6A|04 3B 0E 68|7A 5C 5C 5C|5C 5C 5C 5C| 5C 5C 5C 5C|5C 5C 5C 5C|5C 5C 5C 5C|5C 5C 5C 5C|
あとはこれと5Cとをxorすればconsumer secretが手に入る。終わり。
はてなは増田のスーパーpre記法で半角の＜＞が含まれていると投稿が出来ないのを早く直してください。
もふったーの作者から反応があった。「本気だったつもりのもふったーのデバッグ処理が残ってた」らしい(http://blog.livedoor.jp/blackwingcat/archives/1763951.html)。修正したとのことなので最新版(v0.9.6e)を見てみた。確かに若干変更されているが何の問題もない。SHA-1の呼び出しに中断点を設置して渡されているバイト列を見るだけ。
CPU Disasm Address Hex dump Command Comments 00401324 |. 8D4424 20 |lea eax, [local.102] 00401328 |. 50 |push eax ; /Arg1 = 00401329 |. E8 623A0400 |call 00444D90 ; \mofooter.00444D90
ここでeaxが指すメモリーを見ると以下のようになっている。
01 23 45 67|89 AB CD EF|FE DC BA 98|76 54 32 10| F0 E1 D2 C3|00 02 00 00|00 00 00 00|40 00 00 00| 40 4F 73 53|62 54 5C 7E|59 57 53 42|55 45 7A 57| 61 47 7A 5B|42 4F 7B 61|5D 66 5E 7A|42 7F 40 63| 79 66 05 55|79 4C 60 42|02 10 36 36|36 36 36 36| 36 36 36 36|36 36 36 36|36 36 36 36|36 36 36 36|
一言でバイナリツリーと言っても
積み込みをどこで均一化するか？とかハッシュ関数はどうするか？
削除するときに木の均衡をどうするか？
など、B木といっても山ほどアルのでB木と書いても、山ほどやることはあるので
どんなB木かってのは、もっと書き込まないとわからないとおもう。
少なくともB木というだけでは何も説明できていないとおもう。
逆に、その程度なら、関数名を なんちゃらBtreeと書いておけば済むことだと思う。
最悪のツリー構造のバイナリーツリーじゃぁ、ベクターの方がマシだし。
その部分をどうしたか？という部分が重要で、それって、日本語で書いた方が長くならない？
やっぱり、横暴かなぁ。バランスが難しいです。
http://anond.hatelabo.jp/20090326142330 の続き
pythonでベンチとった。試した方法は以下
長くなるので、使用したスクリプトと生の結果は http://anond.hatelabo.jp/20090326123924 に貼った。
結果としては、早さは3, 4, 1, 2の順で、３を基準にとると、
| 文字列長 | md5hex | crc32x4 | headtail | skipover | ループ回数 |
|---|---|---|---|---|---|
| 256 | 6.6 | 36 | 1.0 | 1.4 | 65536 |
| 1024 | 8.3 | 36 | 1.0 | 2.0 | 16384 |
| 4096 | 26 | 85 | 1.0 | 2.5 | 4096 |
という比率になった。
文字列長が長くなるとやはり後2つが有利だ。また、今回は32文字に切り詰めたがそれでもコリジョンは発生しなかった。アルゴリズム上、数文字だけの変化には対応出来ない可能性があるが、切り詰める量が少なく入力にいくらかのランダム性があれば実用になると思う。
(追記：URLで使ったら、ランダム性が悪くてコリジョン出た。素直にmd5がベターかもしれない)
しかし、この程度の速度差であれば、コリジョン耐性を重視して素直にmd5を使用するのも良いかもしれない。特に、今時はネイティブコードのライブラリをほぼ標準で持つ処理系が多いため、まずはmd5で、としても間違いはなさそう。
セキュリティ目的ではない。ハッシュテーブルで使うような奴でキャッシュで使いたい。
手軽なほうが良い。軽いほうが良い。推測可能でよい。数十バイトくらいの文字列にしたい。
md5が一番汎用っぽいけど、無駄に重い気がする。crc32は軽そうだしそれなりに汎用っぽいけど、ハッシュ長が短いのがめんどい。
調べた→ http://anond.hatelabo.jp/20090327015620
ベンチ用スクリプト
#!/usr/local/bin/python from sys import argv, stderr from time import time from string import ascii_letters, join from random import choice from hashlib import md5 from binascii import crc32 from itertools import izip time_fmt = '%10s: %5d ms' shift = int(argv[1]) if len(argv)>1 and argv[1].isdigit() else 2 length = 0x100 << shift cycle = 0x10000 >> shift print >> stderr, 'string length: 0x%x, cycle: 0x%x' % (length, cycle) data = tuple(''.join(choice(ascii_letters) for i in xrange(length)) for j in xrange(cycle)) start = time() md5hex = tuple(md5(s).hexdigest() for s in data) print >> stderr, time_fmt % ('md5hex', (time() - start) * 1000) start = time() crc32x4 = tuple(''.join('%08x' % abs(crc32(s[i::4])) for i in (0, 1, 2, 3)) for s in data) print >> stderr, time_fmt % ('crc32x4', (time() - start) * 1000) start = time() startend = tuple(s[:16]+s[-16:] for s in data) print >> stderr, time_fmt % ('headtail', (time() - start) * 1000) start = time() skip = tuple(s[::(len(s)/32+1)] for s in data) print >> stderr, time_fmt % ('skipover', (time() - start) * 1000) for s in izip(data, md5hex, crc32x4, startend, skip): print join(s)
実行結果
% python hashbench.py 0 > hash0.txt string length: 0x100, cycle: 0x10000 md5hex: 199 ms crc32x4: 1081 ms headtail: 30 ms skipover: 41 ms % python hashbench.py 2 > hash1.txt string length: 0x400, cycle: 0x4000 md5hex: 83 ms crc32x4: 363 ms headtail: 10 ms skipover: 20 ms % python hashbench.py 4 > hash2.txt string length: 0x1000, cycle: 0x1000 md5hex: 52 ms crc32x4: 170 ms headtail: 2 ms skipover: 5 ms