ハッシュ値の使い方について - クックパッド開発者ブログ
モバイル基盤グループのヴァンサン(@vincentisambart)です。 先日以下のツイートを拝見しました。 Swift's stdlib moves to randomly seeded hashing: https://t.co/2T5oRYtD8B— ericasadun (@ericasadun) 2018年3月10日 この変更はSwift 4.1にはまだ入りませんが、4.2か5.0に入るはずです。コードレビューでこの変更が問題を起こそうなコードを指摘したことあるので、ハッシュ値のおさらいをする良いタイミングではないでしょうか。 Swiftのことを考えて書いていますが、多くのプログラミング言語にも当てはまります。ハッシュ値はSwiftではhashValueというプロパティが返しますが、多くの言語では単にhashというメソッド・関数が返します。 ハッシュマップ ハッシュ値はハッシュ
いろいろな言語での Map, Dictionary 的なものの名前 - Qiita
いろいろな言語で、キーと値とを対応づけるデータ構造、いわゆる連想配列、辞書、……たちがどのように呼ばれているか、気になったので調べてみた。 おおよそ、対応表（map）、辞書（dictionary）、実装の名前をそのまま（hash-table）、 Perl風（hash）に分けられると思う。 Common Lisp: hash-table Scheme: hash-table (SRFI-69, SRFI-125 → R7RS-large), hashtable (R6RS Scheme, SRFI-126), map (SRFI-44), mapping (SRFI-146) Haskell: Map OCaml: Hashtbl, Map SML: hash_table (sml-nj-lib) C++: map, multimap, unordered_map, unordered_mu
Knuth multiplicative hash が最小完全ハッシュ関数であることの証明 | メルカリエンジニアリング
こんにちは！サーチチームの @metal_unk です。普段はサーバーサイドエンジニアとして、メルカリの検索を改善する仕事をしています。 メルカリには Be Professional Day という「普段できないことをやろう」をテーマとする日があり、その日は業務に直接関係のないことや、普段は手をつけられないリファクタリングなどがされます。Be Professional Day の様子はこちらで紹介されています。 tech.mercari.com わたしは今回の Be Professional Day で、Knuth multiplicative hash が最小完全ハッシュであることを証明しました。このブログはその証明についての記事です。 「普段できないことをやろう」という Be Professional Day では、証明もアリです。 Knuth multiplicative hash
Node.js で発生した Hash flooding DoS とその内容について - from scratch
Node.js のセキュリティアップデート 7/11 に Node.js のセキュリティアップデートがリリースされました。 Security updates for all active release lines, July 2017 | Node.js これには複数の脆弱性が報告されており、今回はそのうちの1つの Hash flooding DoS という脆弱性が何なのか、それに対して採用された対策が何なのかについてお話します。 Hash flooding DoS (hashdos) Denial Of Service 、つまりサービス拒否攻撃の一種です。 JavaScript のオブジェクトは内部的にハッシュテーブルとして表現されています。 図はこちらから引用 ハッシュ関数は同じkeyなら同じ値を返しますが、別なkeyなら通常は別な値になります。 ハッシュテーブルのinsert, g
私が書いた最速のハッシュテーブル – PART 2 | POSTD
素数か2のべき乗か ハッシュテーブルのアイテムをルックアップする際に高負荷なステップが3つあります。 キーをハッシングする キーをスロットにマッピングする 該当スロットのメモリをフェッチする ステップ1は、キーが整数であれば、低負荷になります。単にintをsize_tにキャストするだけです。しかし、文字列のようなタイプのキーの場合は高負荷となります。 ステップ2はよくある整数モジュロ演算です。 ステップ3はポインタの間接参照です。std::unordered_mapの場合は複数のポインタ間接参照となります。 処理の遅いハッシュ関数でなければ、直観的にステップ3が最も高負荷になると考えると思います。しかし、全てのルックアップでキャッシュミスが生じなければ、整数モジュロが最も高負荷な処理となります。現代のハードウェアにおいても整数モジュロは非常に遅いのです。 Intelマニュアル では、整数モ
GoogleのSHA-1のはなし
5. • その暗号技術がどのぐらい安全かを表す大雑把な指標 • nビットセキュリティは2 𝑛 回攻撃が必要 • 1回あたりの攻撃コストはあまり気にしない • 𝑂 2 𝑛 という表記 セキュリティビット 𝑛 直線 :𝑂(𝑛) 3次関数 : 𝑂(𝑛3 ) 指数関数 : 𝑂(2 𝑛) 𝑂(log 𝑛) 5 / 21 6. • 第二原像計算困難性（弱衝突耐性） • 𝑚1に対して𝐻 𝑚2 = 𝐻 𝑚1 となる𝑚2 ≠ 𝑚1が分からない • 同じじゃなくてもいいから何か一つ見つけるのが困難 • 𝑂(2 𝑛 )回トライ ; nビットセキュリティ • 衝突困難性（強衝突耐性） • 𝐻 𝑚1 = 𝐻(𝑚2)となる𝑚1 ≠ 𝑚2を見つけるのが困難 • 𝑂(2 𝑛/2 )回トライ ; 𝑛/2ビットセキュリティ • 第二原像を見つけるのは単なる衝突より2
yebo blog: SHA-1の脆弱性が更に進む
2009/06/12 SHA-1の脆弱性が更に進む SHA-1の脆弱性は2005年のXiaoyun Wang氏、Yiqun Lisa Yin氏，Hongbo Yu氏 が公表したSHA-1に対する攻撃の成功から始まった。今までは、衝突を発生させるには、263回の演算が最短記録だったが (SHA-1は160ビットなので誕生日攻撃をしようとすると、理論上は280回の計算が必要)、オーストラリアのマッコリー大学のセキュリティ研究者が252回の演算で衝突を発生させることに成功したそうだ (PDF)。差分経路の探索にブーメラン攻撃を組み合わせるそうだ。高いセキュリティが必要な場合は、そろそろ本気でSHA-2への移行を考えておくべきだろう。 Register | Crypto attack puts digital sig hash on collision course Differential Pa
PerlとRubyで省メモリなハッシュを使おう - mixi engineer blog
サボっていた早朝ジョギング＠駒沢公園を再開して2週間たち、やっと抜かれる数より抜く数の方が増えてきたmikioです。今回は、PerlやRubyのハッシュの代用としてTokyo Cabinetを使うことでメモリ使用量を激減させられることを説明します。 抽象データベースAPI Tokyo Cabinetには抽象データベースという機構があり、先日、そのPerlとRubyのバインディングをリリースしました。それを使うと、各種言語のハッシュとほぼ同じような共通したインターフェイスで、以下のデータ構造を利用することができます。 オンメモリハッシュ：各種言語に標準のハッシュと同じく、メモリ上でkey/valueの関係を表現する。 オンメモリツリー：メモリ上の二分探索木としてkey/valueの関係を表現する。 ファイルハッシュ：いわゆるDBMとして、ファイル上でkey/valueの関係を表現する。 ファ
ハッシュアルゴリズムの次世代標準候補の中にセキュリティ関係のコーディングの不備
ミスをしない人間などいない。ハッシュアルゴリズムの次世代標準の候補となっているアルゴリズムのうち2つが，バッファオーバーフローの問題を抱えていることが明らかになった。 標準暗号アルゴリズムを指定する責任を負う政府組織である，米国の国立標準技術研究所（NIST）は，次世代の標準ハッシュ関数を選択する提案競争を実施している。その資料となるリファレンス実装をFortifyのコード分析ツールで検証したところ，提出された実装のうち2つがバッファオーバーフローの問題を抱えていることが明らかになった。 これらの問題は，そのアルゴリズムの暗号学的な正しさに影響を与えるものではなく，アルゴリズムの大きさが比較的小さいため，これらの問題は選定プロセスが進むに従って速やかに発見された可能性が高い。ともあれ，この事例は，セキュリティ専門家でさえセキュリティ上のミスを犯すことがあることを証明する事例として機能するだ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Looking for a good hash table implementation in C