論文の概要: SHA-256 Collision Attack with Programmatic SAT

• arxiv url: http://arxiv.org/abs/2406.20072v1
• Date: Fri, 28 Jun 2024 17:30:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-01 16:10:57.822413
• Title: SHA-256 Collision Attack with Programmatic SAT
• Title（参考訳）: プログラムSATによるSHA-256衝突攻撃
• Authors: Nahiyan Alamgir, Saeed Nejati, Curtis Bright,
• Abstract要約: 最良のSHA-256衝突攻撃は、より少ないステップで縮小されたSHA-256の簡易バージョンにおける衝突を見つけるために差分暗号解析を使用する。 本稿では,ステップ再現型SHA-256衝突を探索するツールとして,SAT(SAT)ソルバを用いる。 我々のハイブリッドSAT+CASソルバは、純粋なSATアプローチよりも優れており、ステップリデュースされたSHA-256における衝突を、はるかに多くのステップで検出することができる。
• 参考スコア（独自算出の注目度）: 4.971729553254844
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cryptographic hash functions play a crucial role in ensuring data security, generating fixed-length hashes from variable-length inputs. The hash function SHA-256 is trusted for data security due to its resilience after over twenty years of intense scrutiny. One of its critical properties is collision resistance, meaning that it is infeasible to find two different inputs with the same hash. Currently, the best SHA-256 collision attacks use differential cryptanalysis to find collisions in simplified versions of SHA-256 that are reduced to have fewer steps, making it feasible to find collisions. In this paper, we use a satisfiability (SAT) solver as a tool to search for step-reduced SHA-256 collisions, and dynamically guide the solver with the aid of a computer algebra system (CAS) used to detect inconsistencies and deduce information that the solver would otherwise not detect on its own. Our hybrid SAT + CAS solver significantly outperformed a pure SAT approach, enabling us to find collisions in step-reduced SHA-256 with significantly more steps. Using SAT + CAS, we find a 38-step collision of SHA-256 with a modified initialization vector -- something first found by a highly sophisticated search tool of Mendel, Nad, and Schl\"affer. Conversely, a pure SAT approach could find collisions for no more than 28 steps. However, our work only uses the SAT solver CaDiCaL and its programmatic interface IPASIR-UP.
• Abstract（参考訳）: 暗号ハッシュ関数は、可変長入力から固定長ハッシュを生成することで、データのセキュリティを確保する上で重要な役割を果たす。 ハッシュ関数SHA-256は、20年以上にわたる厳しい精査の後、レジリエンスのためにデータセキュリティを信頼されている。 その重要な性質の1つは衝突抵抗であり、同じハッシュを持つ2つの異なる入力を見つけることは不可能である。 現在、最も優れたSHA-256衝突攻撃は、SHA-256の簡易版での衝突を見つけるために差分暗号解析を用いており、より少ないステップに削減されているため、衝突を見つけることが可能である。 本稿では,SHA-256の段階的衝突を探索するツールとしてSATソルバを用い,不整合を検知し,それ以外は検出しない情報を引き出すために使用する計算機代数システム(CAS)の助けを借りて動的に導出する。 我々のハイブリッドSAT+CASソルバは、純粋なSATアプローチよりも優れており、ステップリデュースされたSHA-256における衝突を、はるかに多くのステップで検出することができる。 SAT + CASを使用すると、SHA-256と修正初期化ベクトルとの38ステップの衝突が見つかる。 逆に、純粋なSATアプローチは、28歩以内の衝突を発見できる。 しかし,本研究はSATソルバCaDiCaLとそのプログラムインタフェースIPASIR-UPのみを用いている。

関連論文リスト

• Performance Evaluation of Hashing Algorithms on Commodity Hardware [0.0]
  本稿では,一般的なハッシュアルゴリズムBlake3,SHA-256,SHA-512の性能評価を行う。 これらのハッシュアルゴリズムは、デジタル署名、メッセージ認証、パスワードストレージなど、様々なアプリケーションで広く使われている。 評価の結果、Blake3はスループットとレイテンシの点でSHA-256とSHA-512の両方を上回っている。
  論文  参考訳（メタデータ） (2024-07-11T08:31:02Z)
• Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
  分解硬度(d硬度)の概念を導入する。 d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
  論文  参考訳（メタデータ） (2023-12-16T12:44:36Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  冗長な手法を排除し、単純で効率的なシェープリー推定器SimSHAPを提案する。 既存手法の解析において、推定器は特徴部分集合からランダムに要約された値の線形変換として統一可能であることを観察する。 実験により,SimSHAPの有効性が検証され,精度の高いShapley値の計算が大幅に高速化された。
  論文  参考訳（メタデータ） (2023-11-02T06:09:24Z)
• SOCI^+: An Enhanced Toolkit for Secure OutsourcedComputation on Integers [50.608828039206365]
  本稿では,SOCIの性能を大幅に向上させるSOCI+を提案する。 SOCI+は、暗号プリミティブとして、高速な暗号化と復号化を備えた(2, 2)ホールドのPaillier暗号システムを採用している。 実験の結果,SOCI+は計算効率が最大5.4倍,通信オーバヘッドが40%少ないことがわかった。
  論文  参考訳（メタデータ） (2023-09-27T05:19:32Z)
• Quantum-enhanced symmetric cryptanalysis for S-AES [0.0]
  ダウンスケールSimplifed-AES暗号に対するGroverの攻撃を最適化するアルゴリズムを提案する。 16ビットのS-AESの場合、提案された攻撃は一般に23量子ビットが必要であり、4,8,12ビットが折り畳みでリークされた場合、19,15,11である。
  論文  参考訳（メタデータ） (2023-04-11T17:46:44Z)
• A quantum algorithm for finding collision-inducing disturbance vectors in SHA-1 [2.963904090194172]
  現代の暗号プロトコルは、ユーザ認証やその他のセキュリティ検証のシグネチャとして機能する準ユニクティックな数値を生成するために、洗練されたハッシュ関数に依存している。 セキュリティは、同一の番号にマッチするハッシュテキストを見つけ、いわゆる衝突攻撃を発生させることによって妥協される可能性がある。 本稿では,絡み合った量子状態を利用して,候補外乱ベクトルの同時シード化を行うアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-23T16:01:17Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。 そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
  論文  参考訳（メタデータ） (2022-10-04T09:19:13Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。 これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。 我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
  論文  参考訳（メタデータ） (2022-07-26T04:38:47Z)
• Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation [40.75034970144169]
  SLASHはテラバイト規模のデータセットの類似性を近似的に検索する分散システムである。 SLASHはこの2.3テラバイトのデータを1時間以内に20ノードにインデックスし、クエリ時間をミリ秒単位で表示する。
  論文  参考訳（メタデータ） (2020-08-05T18:15:36Z)
• Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
  ホモモルフィック暗号化(HE)は、最近、暗号化されたフィールド上で計算を行う能力により、ますます注目を集めている。 本稿では,スケーリング問題の解決に向けて,新しい分散HEベースのデータマイニングフレームワークを提案する。 各種データマイニングアルゴリズムとベンチマークデータセットを用いて,新しいフレームワークの有効性と有効性を検証する。
  論文  参考訳（メタデータ） (2020-06-17T18:14:30Z)
• Image Hashing by Minimizing Discrete Component-wise Wasserstein Distance [12.968141477410597]
  競合するオートエンコーダは、バランスよく高品質なハッシュコードを生成する堅牢で局所性を保存するハッシュ関数を暗黙的に学習できることが示されている。 既存の逆ハッシュ法は、大規模な画像検索に非効率である。 本稿では,サンプル要求と計算コストを大幅に低減した,新しい対向型オートエンコーダハッシュ手法を提案する。
  論文  参考訳（メタデータ） (2020-02-29T00:22:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。