Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Difficulty of finding two different inputs that hash to the same value

2
votes
0answers
49 views

How to derive a hash function from another hash function?

Problem: I'm trying to figure out how to solve this, apparently it's hashing the hash value itself. So G has two rounds of hashing the original message x. I tried searching for the relationship ...
0
votes
1answer
45 views

Why do m and m' both hash to H2?

I'm trying to understand the following text: I'm having trouble understanding why $m$ and $m'$ both hash to $H_2$. I tried doing truth tables for $m_1'$ and $m_2'$ given the equations but I don't ...
0
votes
0answers
44 views

Attacks on Hash Functions [duplicate]

When I study attacks on hash functions, I saw the sentence like below. If $m$ is the length of message, value $2^{m/2}$ determines strength of hash code against brute-force attacks. But I cannot ...
3
votes
1answer
91 views

What does Keccak being “efficiently invertible” mean?

Reading through Wikipedia, I saw this: It has been shown that the Merkle–Damgård construction, as used by SHA-2, is collapsing and, by consequence, quantum collision-resistant, but for the sponge ...
3
votes
1answer
73 views

MD5 - Chosen Prefix Collision Attack

Given 2 messages $m_1$ and $m_2$, in a chosen prefix attack, we want to find $s_1$ and $s_2$ such that: $\text{MD5}(m_1 || s_1) = \text{MD5}(m_2 || s_2)$ Are $s_1$ and $s_2$ found by brute force ...
0
votes
1answer
79 views

Is there an $n$-bit hash function such that $n$ is equal to the length of input and the collision resistance is close/equal to $2^{n/2}$?

Let $B$ denote a non-empty bitstring of arbitrary length. Then let $n$ denote the length of $B$. The question: does there exist a cryptographic hash function $H$ that outputs a hash $h$ of $B$ such ...
1
vote
1answer
71 views

AES-128 as compression function in Merkle-Damgard construction

Using a compression function $f : A × A → A$. A basic version given by: $W_0 = IV$ $W_1 = f(W_0, m_1)$ $W_2 = f(W_1, m_2)$ ... $W_n = f(W_{n-1}, m_n)$ $W_n$ is the output of the hash function, $...
0
votes
0answers
57 views

How to prove this hash function does not achieve preimage resistance

I have the following hash function and I am trying to prove it is not preimage resistant ...
-1
votes
1answer
78 views

finding encoding based collision

For example, If I enter as a sample "hello world" in English, how hashing protocol generates a hash of it? is in the first step, change it to ASCII or Unicode or Binary? What if I find a word in other ...
19
votes
5answers
2k views

How many hex digits do I need to compare when manually checking hash functions?

I sometimes run sha256sum on large files after transferring them from one place to another, and will just skim the hash output to verify it's correct. But, I usually just look at the first/last 5 or 6 ...
4
votes
2answers
48 views

Feasible to find two sets with the same RSA accumulator value if a prime representative hash function is used?

Consider the RSA accumulator scheme with random oracle as proposed by Barić and Pfitzmann, with the random oracle replaced by a secure hash function $H$ as follows. For a set $S$, the accumulator ...
1
vote
1answer
87 views

repeatedly hashing result and using reverse sequence as RNG secure?

I want to have a source of randomness for which: no one but me can predict the next number in the sequence. I know the entire sequence in advance, but I have no way of manipulating it once the first ...
1
vote
1answer
96 views

Hashing based on the discrete logarithm problem

At a first look, one could use the elliptic curve discrete logarithm problem to grant for the onewayness of $H(x)=x*G$ (where $G$ is the generator point of the cyclic subgroup). Additionally, $H(x)$ ...
5
votes
2answers
65 views

Can RFC 5649 be used to wrap multiple keys with the same KEK?

I am unable to convince myself that RFC5649 is secure when storing multiple keys with the same KEK. My point is: RFC5649 uses AES-ECB, therefore the usual weakness of this method applies, namely an ...
1
vote
5answers
212 views

What is the mathematical property stating that it is hard to find a collision in the AES algorithm?

Finding a collision in the AES algorithm is (apparently) hard. Why ? What is the mathematical property stating that there is a negligible probability to find a collision by taking two random ...
4
votes
1answer
113 views

Cryptanalysis of MD4 (Wang et al) — how did the authors come up with the collision differential?

Edit: ok, after I re-read the paper a couple of times it is clear that Table 6 is easily derived from Table 5, which describes the collision differential. So the real question is: how did the ...
27
votes
3answers
3k views

Does “Shattered” actually show SHA-1-signed certificates are “unsafe”?

Note: I am not advocating anyone continues using SHA1-signed certificates: they are dead as far as security is concerned and should no longer be used. I'm just trying to clarify my understanding of ...
14
votes
3answers
7k views

After Google's collision attack, is RSA-SHA1 signature still safe?

Google succeeded to get a collision in SHA-1 last year in an attack called shattered. Does this fact make certificates based RSA-SHA1 Signature risky for creating fraud certificates? If RSA-SHA1 ...
2
votes
1answer
41 views

The Collision Differential for MD4 - a question on notation (Wang, et al)

In the paper "Cryptanalysis of the Hash Functions MD4 and RIPEMD" the authors introduce the following notation (paragraph 4.1): $\Delta$$H_0$ = 0 $\xrightarrow{(M_,M')}$ $\Delta$$H$ = 0 What exactly ...
0
votes
0answers
45 views

Anonymized identifier

I'm trying to find an algorithm which would allow me to create anonymized zero-metadata identifiers. I'm creating a system which creates integer identifiers using a counter. Using such identifiers ...
0
votes
2answers
137 views

MD5 hash functions to prove integrity of a download

It doesn't take a lot of time on the crypto StackExchange to realise the sentiment around MD5 hash functions is poor. My questions are: If it's such a bad idea to make use of MD5 hash functions why ...
3
votes
4answers
96 views

Find some hash function with deliberate collisions

I guess this should be well known (or trivially desperate), but I couldn't find any reference. I have a small number (say $k=15$) of messages $m_i$ ,$i=1\cdots k$ (they are fixed length and short, ...
0
votes
0answers
200 views

Security of custom JSON-Object hash

I am currently implementing a signed JSON-Blob, and thus i need to create a hash of any JSON-Object possible. Currently for the hash of the JSON-Object i ended up with the following Java-Code using ...
5
votes
2answers
97 views

Finding k collisions on hash function

Let $n$ be the size of the image-space of a hash function $H$. It is known that you can find a collision on $H$ in $O(\sqrt{n})$ time (by birthday paradox). How can I show that, in order to find $k$ ...
2
votes
2answers
82 views

Is it possible to generate an infinite number of collisions given an infinite amount of strings?

Let us assume that we have a string $w$ such that it belongs the set $C$, where every member of $C$ is not null, and contains every string of characters that can be permuted (numbers, letters etc.). ...
3
votes
0answers
42 views

Ambainis quantum collision-finding alg; triple hash output lengths?

I just stumbled onto a series of 2017 papers about applying the Ambainis quantum collision-finding algorithm to hash functions. (disclaimer: I haven't read all of them in full yet): Post-quantum ...
7
votes
2answers
2k views

How many trials does it take to break HMAC-MD5?

I know that you can find collision in MD5 with 2^64 trials using Birthday paradox. Now everyone is saying that HMAC-MD5 is significantly more secure. How can I ...
0
votes
2answers
50 views

Technical term for hash value being uncorrelated to input message?

Is there a technical term for the desirable property of hash functions. That a small change to the input message will produce a massive unpredictable and seemingly uncorrelated change to the output ...
2
votes
2answers
457 views

collisions on hash functions

Why do we say that collision-resistance is a "harder" property than second pre-image for hash functions whereas if you have an attack on the second pre-image then you find a collision ? Moreover, a ...
1
vote
1answer
129 views

Security of XORing hashes vs concatenating

On this question https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes a couple of the answers say that xoring is a bad/insecure choice for combining hashes. However,...
-1
votes
2answers
174 views

(strong) collision resistance Example

I'm studying Cryptography & Network Security. It has the following example for collision resistance: "Suppose Bob writes an IOU message, sends it to Alice, and she signs it. Bob finds two ...
4
votes
1answer
78 views

For a random permutation $P$, what's the probability of the following event?

For a random permutation $P$ and $q$ distinct inputs $x_1,\ldots,x_q\in\{0,1\}^n$, what's the probability of the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\...
1
vote
2answers
240 views

Rolling your own crypto

I know this is usually frowned upon, but supposing you were to roll your own encryption cipher (completely on your own or with a small group of friends, with no peer review possible), what could you ...
1
vote
0answers
41 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 ...
0
votes
1answer
68 views

Taking $n-1$ bits from hash function will also be hash function?

If $\mathcal{H}=\left(\text{Gen},H\right)$ is a collision resistant hash family does $\mathcal{W}=\left(\text{Gen},W\right)$ where $W_{s}\left(x\right)$ denote the $n-1$ left most bits of $H_{s}\left(...
3
votes
2answers
509 views

Attack MD5 with partial information?

If I generate an MD5 hash from 2 pieces of information – i.e. by concatenating two strings – how easy is it to guess what that hash is, assuming an attacker has knowledge of only 1 piece of those info?...
5
votes
1answer
145 views

What is the collision resistance of a 2048-bit hash based on SHA-3?

Let $M$ denote the message. Let $B_i$ denote eight different bitstrings (chosen arbitrarily or randomly) such that $$0 \le \text{length}(B_i) \le 12345678.$$ Consider the following function (it ...
3
votes
2answers
287 views

Is there are a metric based on collisions to compare bad hash functions?

Bad hash functions are not so perfect as in the "general collision probability" hypothesis... And a general concept of "collision resistence" not need the constraint of independence between the ...
0
votes
1answer
52 views

The collision rate probability decreases when using compression?

Some standard compression procedures, like the IANA's gzip provided by HTTP protocol, will consume CPU-time anyway... So we can reuse compressed file, $Z(x)$, in the checksum procedure. That is, we ...
0
votes
2answers
217 views

Does the double-hash H(H(x)) have greater collision probability than H(x)?

Let $H$ be a collision resistant hash function and $P_c[H](S)$ the collision probability about a sample set $S$ of input elements (eg. random numbers). It increases with double hash? That is, $P_c[H\...
1
vote
1answer
67 views

Is exponentiation of a fixed generator modulo a prime collision-resistant?

Let $p$ be a prime number, and $g$ a generator of $\mathbb Z/p\mathbb Z$. For a message $m$, define the hash function $$h(m) = g^m \pmod p.$$ Is $h$ collision-resistant?
0
votes
0answers
103 views

Davies-Meyer with DES insecure

I'm stuck in coming up with a collision for a hash function $H$, which is built using a Davies-Meyer construction chained in a Merkle-Damgard fashion. I I guess its actually easy using the fact that ...
1
vote
1answer
141 views

Is there a deterministic one-way collision-free crypto algorithm?

I use usernames encrypted using a function f as ids of records. Users see records identified by f(username). I must not know real usernames. I want to be protected from attack when adversary who has ...
0
votes
1answer
58 views

6 Byte for HMAC in wireless system secure?

A wireless system has 8 byte payload and 6 byte for message authentication. Scheme: ...
0
votes
2answers
112 views

Security of password hash with known prefix and appendix

Assume I have a password that is exactly 32 characters long. I hash it the following way: Prepend 1524 bytes (known to an attacker) Append 3356 bytes (known to an attacker) Do the checksum It is ...
1
vote
1answer
37 views

Randomized public-key encryption as binding commitment / “collision-resistance”?

I am looking to use randomized public-key encryption in a context where it should also serve as a sort of "binding commitment". That is, I want to encrypt a value $x$ with some randomness $rnd$ under ...
0
votes
0answers
28 views

Can a hash-input be the same as the hash-output? [duplicate]

Could it be that (i.e. for SHA-2) the hash-output is identical to the input or is this deliberately prohibited by some sort of mechanism?
23
votes
4answers
11k views

How can hashes be unique if they are limited in number? [duplicate]

I'm curious, how can for example SHA-256 be unique if there are only a limited number of them?! For clarification: how many MD5 hashes are there? $16^{32}$ MD5 hashes can be produced. $16^{64}$ SHA-...
6
votes
1answer
152 views

Is there a way one can combine two correlated hash outputs to maximize the collision resistance?

While practically diving into collision resistance, I am trying to first write a non-cryptographic hash (to learn from it) which is limited to arithmetic operations on 32-bit integers only. It ...
3
votes
1answer
61 views

Security implications of slow-by-design hashes on relative security vs. hash size

Would it be true to say that that one can get away with much smaller cryptographic hashes if the hashing algorithm is slow and expensive by design? Example: let's say you want 128-bit hashes. This is ...