Questions tagged [collision-attack]
For attacks on hash functions that achieve hash collisions with less work than the birthday bound.
37 questions
6
votes
1
answer
866
views
What practical power does an attacker gain if a hash function is not strong but weak collision-resistant?
I am trying to understand the practical implications of a hash function that is weak collision resistant, but not strong collision resistant.
That is, an attacker
can efficiently find some pair of ...
- 253
0
votes
0
answers
115
views
Related precise SAT encoding of SHA-256
Respected mathematicians, I would like to know if there is any GitHub repository that accurately converts SHA-family algorithms into SAT problems. So far, I found the SAT encoder by Saeed Nejati to be ...
user129085
0
votes
2
answers
216
views
How to correctly convert Bitcoin’s double SHA-256 proof-of-work into a CNF satisfiability (SAT) problem? [closed]
Is there any respected mathematician who can correctly transform the double SHA proof-of-work (used in Bitcoin mining) into a satisfiability (SAT) problem, ensuring that the CNF conversion is done ...
user129085
1
vote
0
answers
77
views
Parameters needed to convert $k$-round collision problem to $3SAT$?
What is the $n+m$ value for leading $0$s $k$ round SHA-256 hash collision problem when we convert $k$ round SHA-256 to $n$ variable 3SAT in $m$ clauses?
By leading $0$s $k$ round SHA-256 hash ...
- 1,215
4
votes
2
answers
759
views
How can having a cycle help finding a hash collision?
Edit: background:
I was thinking about using iterating $H$ on some arbitrary $x$ to find a collision. Eventually I will have a cycle for the first time, and until then $x, H^1(x), H^2(x), \dots$ are ...
- 213
-1
votes
1
answer
165
views
Found collision in fnv132 hash
I'm experimenting with hash functions in PHP using the built-in hash() function... and I've stumbled upon something interesting: I have found collision in fnv132 ...
1
vote
1
answer
135
views
Prefix Free secure PRF Security strength
This question is in regards to "A Graduate Course in Applied Cryptography" by Boneh-Shoup, section 6.4.1 "The CBC prefix-free secure PRF".
In the proof for the security strength of ...
- 1,155
1
vote
1
answer
184
views
What is wrong with this hash function
I have been asked what is a problem with hash function:
$$h(S) = \left(\left(\sum S[i]*x^i\right)\bmod p\right)\bmod m$$
where $i=\{0,\ldots,s-1\}\,$; $S$ is some long string; $x$ is some positive ...
- 11
2
votes
1
answer
203
views
Ideal Cipher assumption for DES collision probability: Dan Boneh Coursera lecture
In Dan Boneh's lecture Exhaustive Search Attacks from module 2 of his coursera course, he gives an explanation for why the probability of two different DES keys ...
- 123
5
votes
2
answers
206
views
Is it viable to find an MD5 collision for Haskell's sparse unicode string encoding?
I've recently discovered a potential vulnerability in the type system of Haskell, a functional programming language in use in critical applications at Facebook, Standard Chartered, Input Output et ...
3
votes
2
answers
180
views
How can a attacker find a collision of a keyed digest without knowing the key? Are collisions not an issue anymore if we apply a keyed-digest?
Same as the title.
How can an attacker find a collision in a keyed digest without knowing the key? Does using a keyed digest eliminate the problem of collisions?
- 163
0
votes
2
answers
1k
views
How to generate an arbitrary file matching a given MD5 hash? [duplicate]
I have an MD5 hash and need to generate a file that matches it.
There are absolutely no constrains on the contents of said file, it can be binary gibberish.
The only important thing is that it matches ...
- 11
2
votes
2
answers
85
views
Does having a known suffix on the input to PBKDF2 make you more vulnerable?
I have an implementation of PBKDF2, which I know
Has two bytes of '=' at the end of the input
Has an input length of 24 (which is a Base64 encoded character representation of 16 bytes of entropy)
...
- 121
0
votes
0
answers
124
views
Having trouble providing a distinguisher proving this hash function is not collision-resistant
As suggested by the title, I'm working on an exercise where I'm given a hash function $H$ that takes in an input string $x$. I'm supposed to construct a distinguisher that proves $H$ isn't collision-...
- 19
0
votes
0
answers
60
views
On the exposition of SHA-1 attack (known_prefix + user_input + backend_secret)
In this question on sha1(known_prefix + user_input + backend_secret), an answer states that is realistically possible to find the first few bytes of ...
- 101