Questions tagged [preimage-resistance]

Difficulty of finding an input string that hashes to a given value

Filter by
Sorted by
Tagged with
36
votes
3answers
38k views

What are preimage resistance and collision resistance, and how can the lack thereof be exploited?

What is "preimage resistance", and how can the lack thereof be exploited? How is this different from collision resistance, and are there any known preimage attacks that would be considered feasible?
19
votes
1answer
7k views

Could we break MD5 entirely in the future?

Even of today MD5 is (sadly) still heavily used in some applications. Even big tools like ApacheMD5. But even today there are more then enough MD5 hashes which are still not cracked. According to ...
17
votes
2answers
7k views

Pre-image resistant but not 2nd pre-image resistant?

Are there any cryptographic hash functions for which there is a known pre-image attack, or a known second pre-image attack, but not both? The attack doesn't have to be practical - just anything that ...
53
votes
11answers
19k views

How do hashes really ensure uniqueness?

This might seem an impractical and unnecessary conversation, but I feel it's something I need to clarify. Especially, as I just got my first developer job in a blockchain startup. So hashes are said ...
13
votes
2answers
7k views

Why does second pre-image resistance imply pre-image resistance

I am studying hash functions. I can understand why collision resistance implies second preimage resistance, but I don't get why second preimage resistance should imply first preimage resistance. Could ...
11
votes
1answer
3k views

Why doesn't preimage resistance imply the second preimage resistance?

Let the preimage resistance be defined as »given a hash value $h$, it is hard to find any message $m$ such that $\operatorname{hash}(m)=h$«, and let the second preimage resistance be defined as »given ...
17
votes
1answer
4k views

What are the consequences of removing a single byte from a sha256 hash?

I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash. Sha256 would meet this ...
29
votes
11answers
8k views

Why can't I reverse a hash to a possible input?

I'm going to provide “proof” why a hash function can be reversed, and I hope you can tell my why I'm wrong So, a hash function can be implemented as a series of logic gates. All logic gates can be ...
2
votes
1answer
144 views

Is it possible to deduce the value of a string when given its hash and multiples hashes of the string + other known strings?

To be clear, I have access to $H(S)$ and as many $H(S||K)$ as I want. Every string $K$ is known. Can I use the extra information to my advantage and try to deduce $S$, without requiring bruteforce? Or ...
21
votes
2answers
8k views

What makes SHA-256 secure?

For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem. What makes SHA-256 and similar hash functions, of the same family, ...
5
votes
1answer
4k views

Pre-image attack on MD5 hash

I read somewhere MD5 is broken in terms of collision, but I am wondering if it is broken in terms of pre-image resistance? Given a hash of Md5, is it possible to find the original message of it? If ...
18
votes
2answers
7k views

SHA-256: (Probabilistic?) partial preimage possible?

Currently busying myself with the Bitcoin "mining" algorithm, I am wondering if the process really cannot be simplified. For reference, the algorithm is basically SHA-256d: $$\mathit{success} := \...
7
votes
1answer
677 views

Does preimage resistance and/or collision resistance imply the infeasiblility of finding fixed points in hash functions?

For example, if $H$ is a secure cryptographic hash function, is it infeasible to find $x$ such that $H(x)=x$ or such that $H(H(x))=x$ ? What about finding $x, y$, and $z$ such that $H(y||H(z||x))=x$ ?...
7
votes
3answers
530 views

Why can't hashes be reversed with toffoli gates?

This is a follow up question to this question: Crack cryptographic hash functions using Toffoli gates?. Suppose there is a hash function $$H(x)=y,$$ where $x$ is the input of the function and $y$ is ...
6
votes
1answer
1k views

What is the security strength of an n-bit HMAC?

HMACs depend on preimage resistance, or so I have read. The security strength of hash function with an $n$-bit output against collision attacks is $2^{\frac{n}{2}}$. Against preimage attacks, it is $2^...
4
votes
0answers
403 views

How hard is a known prefix hash preimage attack on SHA-2?

Suppose the attacker knows $X, Z$ such that $H(X || Y) = Z$ If bit-length(Y) < 60 then a brute force attack is possible. What if ...
19
votes
2answers
2k views

What is the general justification for the hardness of finding preimages for cryptographic hash functions?

Since most cryptographic hash functions are simple, compact constructions does this simplicity impose a limit on the complexity and the size of a function that can generate preimages? That is, given a ...
15
votes
3answers
976 views

Does a partial preimage attack imply a preimage attack?

Let's assume we have an $n$-bit hash function and a $b$-bit partial preimage attack that is faster than brute force. Does this imply a faster than brute force preimage attack on the whole hash? It ...
6
votes
2answers
14k views

Computational requirements for breaking SHA-256?

Let's define "breaking" a hash function $H$ as being threefold (corresponding to the main properties of a cryptographic hash function): preimage attacks to get $m$ knowing $H(m)$ second-preimage ...
3
votes
1answer
671 views

How is pre-image resistance defined, formally?

Earlier today, forest asked in our chat, The Side Channel whether the definition of first pre-image security actually requires that an input that evaluates to the challenge hash result must be known ...
2
votes
1answer
1k views

What's the perfect chain length : number of chains ratio for rainbow tables?

I'm building a SHA-1 rainbow table to crack basic passwords (i.e. up to 10 character, 0-9,a-z), but I can't seem to calculate that golden ratio that would give me the most coverage. What ration of ...
4
votes
1answer
605 views

Do well-known hash functions have any “impossible” output values?

What I'm wondering is whether the codomain and image of common hash functions are strictly equal… or whether there are any known values which have no possible preimage. For example, SHA-1 outputs a ...
3
votes
2answers
1k views

Finding partial pre-image of MD5 hash

I have the following requirement for hashing using MD5. H(A,B,C,X); Where values A,B & C are given. However X is not given. I would like to find out what value of X would give a hash beginning ...
3
votes
3answers
1k views

For any hash value, is there an infinite number of inputs that hash to it?

Bruce Schneier writes (back in 2005) in a post on cryptanalysis of SHA-1: SHA-1 produces a 160-bit hash. That is, every message hashes down to a 160-bit number. Given that there are an ...
2
votes
1answer
454 views

Hash-based signature scheme XMSS/LMS susceptible to preimage/second preimage attack?

Are the quantum secure hash based signatures (XMSS/LMS) susceptible to preimage/second preimage attack?
1
vote
0answers
49 views

Hash Function SHA-3 [duplicate]

I would like to discuss the minimum input of hash function to consider strong (e.g Shack128 (SHA-3)). I have a mechanism based on SHA-3, but the input is just 40-bit, some friends told me 40-bit input ...
6
votes
1answer
568 views

Can iterated hashing be used to mitigate collision and preimage weaknesses?

How much security does double hashing add regarding collisions and preimages? Is it helpful to iterate a hash function even more times than two? For example, can MD5 be fixed (in practice) by ...
4
votes
1answer
2k views

Concatenation of two strong hashes may have striking weakness

For any hash functions $H_0$ and $H_1$, it is easily proved that their concatenation $H_0\|H_1$, defined by $(H_0\|H_1)(X)=H_0(X)\|H_1(X)$, is at least as resistant as the strongest of $H_0$ and $H_1$ ...
3
votes
1answer
1k views

Is SHA-256 safe when used in this way?

I am wondering whether an attacker can gain any useful information from having several hashes of an unknown plaintext that differs in relatively few bits. For example, if provided with: ...
3
votes
3answers
890 views

Computational feasible to reverse MD5SUM?

This might be out of ignorance, I apologize, but how complex of a problem might it be to generate a file of size $N$ whose MD5SUM is $X$? For example, ...
3
votes
1answer
970 views

Difficulty of collision vs preimage vs second-preimage attacks

It seems at first glance that brute-forcing a collision would be exactly as difficult for all of them. They all (I would expect) work like this: select a hash value, and then try messages to get an ...
2
votes
1answer
587 views

Why does a fixed key not make MACs like CBC-MAC or GMAC into secure hash functions? [duplicate]

Why does setting the secret key to a fixed, public value not make MACs like CBC-MAC or EMAC into secure unkeyed cryptographic hash functions? In other words, why is the resulting hash function not ...
1
vote
1answer
94 views

Potential weaknesses when combining hash functions?

For consistency's sake, M is the message, H1 and H2 are separate hash functions. I've heard that concatenation or XORing hash outputs together do not provide improved security against preimage and ...
-3
votes
3answers
650 views

If we know a sha256 hashed value and its message length can we find the message?

Is it possible to find the original message if we know a sha256 hashed value and its message length?