論文の概要: Inverting Cryptographic Hash Functions via Cube-and-Conquer
- arxiv url: http://arxiv.org/abs/2212.02405v1
- Date: Mon, 5 Dec 2022 16:44:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-06 18:28:16.045463
- Title: Inverting Cryptographic Hash Functions via Cube-and-Conquer
- Title（参考訳）: cube-and-conquerによる暗号ハッシュ関数の反転
- Authors: Oleg Zaikin
- Abstract要約: Cube-and-Conquerは、MD4とMD5のステップレデュースバージョンに適用される。
第一のアルゴリズムはドブバーチンの制約を徐々に修正することでMD4の逆問題を生成する。
第2のアルゴリズムは、カットオフしきい値が異なるキューブ・アンド・コンカヤのキューブ位相を試み、最小のランタイム推定値を求める。
- 参考スコア（独自算出の注目度）: 0.45687771576879593
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: MD4 and MD5 are seminal cryptographic hash functions proposed in early 1990s.
MD4 consists of 48 steps and produces a 128-bit hash given a message of
arbitrary finite size. MD5 is a more secure 64-step extension of MD4. Both MD4
and MD5 are vulnerable to practical collision attacks, yet it is still not
realistic to invert them, i.e. to find a message given a hash. In 2007, the
39-step version of MD4 was inverted via reducing to SAT and applying a CDCL
solver along with the so-called Dobbertin's constraints. As for MD5, in 2012
its 28-step version was inverted via a CDCL solver for one specified hash
without adding any additional constraints. In this study, Cube-and-Conquer (a
combination of CDCL and lookahead) is applied to invert step-reduced versions
of MD4 and MD5. For this purpose, two algorithms are proposed. The first one
generates inversion problems for MD4 by gradually modifying the Dobbertin's
constraints. The second algorithm tries the cubing phase of Cube-and-Conquer
with different cutoff thresholds to find the one with minimal runtime
estimation of the conquer phase. This algorithm operates in two modes: (i)
estimating the hardness of an arbitrary given formula; (ii) incomplete
SAT-solving of a given satisfiable formula. While the first algorithm is
focused on inverting step-reduced MD4, the second one is not area-specific and
so is applicable to a variety of classes of hard SAT instances. In this study,
for the first time in history, 40-, 41-, 42-, and 43-step MD4 are inverted via
the first algorithm and the estimating mode of the second algorithm. 28-step
MD5 is inverted for four hashes via the incomplete SAT-solving mode of the
second algorithm. For three hashes out of them this is done for the first time.
- Abstract（参考訳）: MD4とMD5は1990年代初頭に提案された暗号ハッシュ関数である。
MD4は48ステップで構成され、128ビットのハッシュを任意の有限サイズのメッセージとして生成する。
MD5はMD4のよりセキュアな64ステップ拡張である。
MD4とMD5はどちらも実用的な衝突攻撃に弱いが、ハッシュが与えられたメッセージを見つけることは現実的ではない。
2007年、39段版のMD4はSATに還元され、いわゆるDobbertinの制約とともにCDCLソルバが適用された。
MD5に関しては、2012年に28ステップバージョンがCDCLソルバを介して特定のハッシュに対して追加の制約を加えることなく反転された。
本研究では,cdclとlookaheadの組み合わせであるcube-and-conquerをmd4とmd5の逆ステップ縮小バージョンに適用する。
この目的のために2つのアルゴリズムを提案する。
まず、dobbertinの制約を徐々に修正することで、md4の反転問題を生成する。
第2のアルゴリズムは、キューブ・アンド・コンクエストのキュービングフェーズを異なるカットオフしきい値で試行し、コンクエストフェーズを最小のランタイム推定で見つける。
このアルゴリズムは2つのモードで動作する。
(i)任意の公式の硬さを推定すること。
(ii) 与えられた満足できる式の不完全SAT解法。
第1のアルゴリズムはステップ還元MD4の反転に重点を置いているが、第2のアルゴリズムは領域固有ではなく、ハードSATインスタンスの様々なクラスに適用できる。
本研究では,40段,41段,42段,43段のMD4を,第1のアルゴリズムと第2のアルゴリズムの推定モードで反転させる。
28ステップmd5は、第2アルゴリズムの不完全sat解決モードを介して4つのハッシュに対して反転する。
そのうちの3つのハッシュは、これが初めて行われる。
関連論文リスト
- A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions [0.0]
我々は,暗号アルゴリズムに焦点をあてて,準拘束的二項最適化の最先端を推し進めることを目指している。
AES-128/192/256、MD5、SHA1、SHA256など、最も広く使われている暗号アルゴリズムについて考察する。
これらの結果から,QUBO 行列のスパースと係数の大きさを低く保ちながら,これまでに公表した結果と比較して,QUBO のインスタンスを数千の論理変数で減らした。
論文 参考訳（メタデータ） (2024-09-10T18:46:26Z) - Low-Complexity Integer Divider Architecture for Homomorphic Encryption [5.857929080874288]
ホモモルフィック暗号化(HE)は、計算を直接暗号文で行うことができ、プライバシ保護のクラウドコンピューティングを可能にする。
余剰かつ活発な数学的証明を計算するアルゴリズムが提案されている。
論文 参考訳（メタデータ） (2024-01-19T23:53:59Z) - 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) - Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
ターゲットの折り畳みは、公開可能な削除(PVD)を可能にすることを示す。
我々は、弱い暗号的仮定から公開可能な削除を支援する様々なプリミティブを得るために、このフレームワークを構築している。
論文 参考訳（メタデータ） (2023-03-15T15:00:20Z) - A quantum algorithm for finding collision-inducing disturbance vectors
in SHA-1 [2.963904090194172]
現代の暗号プロトコルは、ユーザ認証やその他のセキュリティ検証のシグネチャとして機能する準ユニクティックな数値を生成するために、洗練されたハッシュ関数に依存している。
セキュリティは、同一の番号にマッチするハッシュテキストを見つけ、いわゆる衝突攻撃を発生させることによって妥協される可能性がある。
本稿では,絡み合った量子状態を利用して,候補外乱ベクトルの同時シード化を行うアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-23T16:01:17Z) - Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。
これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。
我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
論文 参考訳（メタデータ） (2022-07-26T04:38:47Z) - Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。
実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。
本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-13T02:44:05Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Multi-objective Recurrent Neural Networks Optimization for the Edge -- a
Quantization-based Approach [2.1987431057890467]
本稿では,Multi-Objective Hardware-Aware Quantization (MOHAQ)法を紹介する。
本研究では,検索空間内でのみ選択された解を学習し,ビーコンとして利用し,他の解に対する再学習の効果を知るための「ビーコンベース検索」という検索手法を提案する。
論文 参考訳（メタデータ） (2021-08-02T22:09:12Z) - Deep Momentum Uncertainty Hashing [65.27971340060687]
我々は,新しいDeep Momentum Uncertainity Hashing (DMUH)を提案する。
トレーニング中の不確実性を明示的に推定し、不確実性情報を利用して近似過程を導出する。
提案手法は,すべてのデータセット上で最高の性能を達成し,既存の最先端手法を大きなマージンで超越する。
論文 参考訳（メタデータ） (2020-09-17T01:57:45Z) - Faster Person Re-Identification [68.22203008760269]
本稿では,新しいハッシュコード検索戦略を定式化することによって,高速ReIDのための新しいソリューションを提案する。
より短いコードを使用して、より正確なReIDのいくつかのトップ候補を洗練するために、より広い一致の類似性を粗くランク付けし、より長いコードを使用する。
2つのデータセットに対する実験結果から,提案手法(CtF)は現在のハッシュReID法よりも8%精度が高いだけでなく,5倍高速であることがわかった。
論文 参考訳（メタデータ） (2020-08-16T03:02:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。