Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
746
questions
5
votes
5
answers
1k
views
Which hash algorithms support binary input of arbitrary bit length?
Background
In theory, hash functions produce a binary number having bounded (often fixed) length from binary data of arbitrary length.
In practice, specifications and implementations constrain the ...
- 153
0
votes
0
answers
51
views
Why hashing when generating account from public key?
When producing an account out of public key it's a common approach to hash the latter multiple times (sometimes using different algos) before encoding and taking a portion of the product. Is this done ...
1
vote
0
answers
46
views
Is there a perfect hash function for a tree data structure with different kinds of nodes?
I am working on a tree structure that has the following structure (you can find the source code here)
...
- 111
1
vote
1
answer
45
views
Low-Collision Abbreviation For Public Key Hex Representation
I am writing an application where each client generates its own public/private key pair that uniquely identifies it to other clients. Clients are using the Web Crypto API to generate ECDSA P-384 keys. ...
- 111
5
votes
4
answers
4k
views
Is the XOR of hashes a good hash function?
Definitions:
Let $h$ be a hash function with output size $n$ bytes. Suppose the file $F$ can be divided into chunks of size $n$ bytes $F=f_0+f_1+\dots +f_i$ where the operator "$+$" stands ...
- 153
1
vote
2
answers
115
views
Why does HMAC-SHA1-96 need to pad message to a multiple of 160 bits?
HMAC-SHA1-96 is performed in AH of IPSec, to have data authentication and integrity.
I don't understand why I need to pad message M to a multiple of 160 bit, which is the output length of SHA1. Why is ...
- 51
3
votes
2
answers
128
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?
- 51
1
vote
2
answers
136
views
Looking for a lightweight hashing algorithm
I'm looking for a hashing algorithm with some unique properties:
Most important: It has to be small. Ideally ~400 bytes of x86 assembly
Resistant to preimage & collision attacks with no known ...
- 11
0
votes
2
answers
115
views
Adding 2 hash values
hash(a) + hash(b) = hash(c)
When adding 2 hashes values can it be equal to another hash value? Is it unlikely for this to happen? If so why?
1
vote
1
answer
64
views
Necessity of all three MD-Compliant padding conditions
For Merkle-Damgård hashing, MD-compliant padding is defined as any padding scheme satisfying:
$M$ is a prefix of $\text{Pad}(M)$
$|M_1|=|M_2|\Rightarrow |\text{Pad}(M_1)|=|\text{Pad}(M_2)|$
$|M_1|\...
- 113
0
votes
0
answers
15
views
How many extra bits of security can I get from an intermediate finalisation of SipHash-2-4?
I'm currently using SipHash-2-4 to hash 4096-byte blocks into 64-bit hashes. The key is secret, as that is required by SipHash.
I have 128 bits of space available for hashes, but I don't want to use ...
- 958
1
vote
0
answers
48
views
Are saltless PoW's ok?
So, I'm building a system loosely based on the S/Kademlia principles and I have a question.
I generate IDs from hashing a public key such that $ID = H(PK)$. Further, I say that for an ID to be valid ...
- 11
4
votes
1
answer
99
views
Security impact of weakened collision resistance for 128-bit Fiat-Shamir challenges
As I understand, to achieve a security level of $\lambda$, a hash function's output should be at least $2\lambda$ in length, since the search space is halved for collision resistance.
However, I am ...
- 43
2
votes
0
answers
72
views
Inequalities in collision search on the separation between the classical and quantum random oracle (ROM vs QROM)
I'm trying to read the separation between the classical and quantum random oracle through a paper "Random Oracles in a Quantum World" by Dan Boneh, Ozgur Dagdelen, Marc Fischlin, Anja ...
- 33
1
vote
0
answers
47
views
Suffix-free padding scheme for hash function
I would like an easy to read proof that shows that it is sufficient for a padding scheme to be suffix-free for it to be collision resistant.
Whenever I have come across such a proof it always seems to ...
- 75
2
votes
1
answer
82
views
How to design a reversible shifted XOR with an S-box?
According to this post, S-boxes are invertible.
Inverting S-boxes can be very easy: you simply create a lookup table that reverse all the possible substitutions of the S-box. E.g. if the S-box maps ...
- 123
1
vote
0
answers
69
views
I do not understand the result of 'proposition 2' of "MDx-MAC and building fast MACs from hash functions"
I saw the difference between the proof and the statement of "proposition 2" in the paper "MDx-MAC and building fast MACs from hash functions" by Bart Preneel & Paul C. van ...
- 31
0
votes
0
answers
40
views
Proving Insecure Hash Function Through Not Collision Resistant
There is a function H : {0, 1}* → {0, 1}^n. On input a message m and two
shares of it x, w such that m = x ⊕ w, the function outputs y = H(m) =
H(x) ⊕ H(w). How would I find that this NOT a collision ...
- 21
1
vote
0
answers
30
views
Proof of UOWHF construction from a strongly universal hash family
I am currently trying to rigorously prove Lemma 2.2 of [NY].
More specifically, a UOWHF family can be constructed from a composition of a strongly universal family $G_k = \{g : \{0, 1\}^k \rightarrow \...
0
votes
1
answer
53
views
Finding security constraints for different input domains of Ajtai functions
I know that the normal construction for Ajtai hash functions is as follows:
Pick $n, m, q \in \mathbb{Z}^+$ such that $n \log q < m < \frac{q}{2n^4}$ and $q = O(n^c)$ for some $c>0$, and some ...
- 147
0
votes
0
answers
30
views
Obfuscation scheme wanted
I'd like to know if there's any cryptographic scheme that implements something similar to what I'm summarizing here below.
Thanks a lot for reading and for any hint or question.
Intro-Scenery:
There's ...
- 101
2
votes
1
answer
59
views
Is it hard to find m, R to make RG^H(m||R)=C?
Assuming the generator of one group $\mathbb G$ is $G$. Given an element $C\in \mathbb G$ and a cryptographic hash function $H(\cdot)$, is it hard for one adversary to find a pair of message $m$ and ...
- 43
0
votes
0
answers
33
views
Is it possible for a given plaintext and ciphertext to have two different keys? [duplicate]
This has probably been asked before but for a given ciphertext and plaintext pair, is it possible to have two different keys producing said pair? Or there are no collisions in AES, unlike hashing ...
0
votes
0
answers
222
views
What is the fastest stable 128-bit non-cryptographic hash function?
I need a stable 128-bit hash function which is extremely fast since it will be used for generating unique IDs for billions of objects.
It doesn't need to be a cryptographic hash function, nor does it ...
- 123
1
vote
3
answers
124
views
Is the composition of a hash function with a block cipher collision resistant?
Assume $H$ is a collision resistant and preimage resistant (unkeyed) hash function and $E(k,y)$ is a block cipher where $k$ is the key.
I am interested into the collision resistance of the composed ...
- 55
0
votes
2
answers
167
views
Calculating maximum plaintexts without birthday collisions given a probability, when the encryption scheme has multiple parts?
I'm sorry if the answer to this is actually simpler than it seems to me.
I'm running AES-GCM to encrypt some data keys, but I don't actually know how to go about calculating the probability of ...
2
votes
1
answer
104
views
Difficulty of finding a claw for AES-CMAC
Consider the problem of finding two keys K1 and K2, such that for two distinct plaintexts P1 and P2, AES-CMAC(K1, P1) = AES-CMAC(K2, P2).
Is this problem any easier than brute-forcing? If so, how much ...
- 183
1
vote
0
answers
57
views
Grow-only set homomorphic hash function from semigroup?
I have been exploring Bellare and Micciancio's "randomize-then-combine" paradigm for deriving set homomorphic hashing functions. I am particularly interested in grow-only sets, such that ...
- 131
1
vote
1
answer
83
views
Security of this MAC scheme
I'm studying for a cryptography exam, I have this question from a past exam:
Consider the MAC with key $k$, based on a block cipher $E_{(k)}$ with block size $n$, and a collision-resistant hash ...
- 11
4
votes
0
answers
162
views
Is the XOR-combiner of independent keyed hash-functions collision resistant?
Assume there are two keyed hash-functions $H_1(k_1, m)$ and $H_2(k_2, m)$, with $k_1$ and $k_2$ being independently randomly sampled public keys.
The XOR-combiner is defined as $C_\oplus^{H_1, H_2}:=...
3
votes
1
answer
820
views
What is the advantage of using hash function families instead of a single hash function?
My guess would be that families are more secure. In which way though?
I have seen claims that hash function families can be collision resistant while single hash functions can not be. Is this true? ...
- 31
0
votes
0
answers
173
views
Is the following hash function construction collision resistant?
The problem
Let the following function be a collision reisistant hash function
$$H=\{H_s:\{0,1\}^{2n} \rightarrow \{0,1\}^{n} \}$$
Let the following function be a PRG
$$G:\{0,1\}^{n+1} \rightarrow \{0,...
- 1
0
votes
1
answer
131
views
Set with probability of SHA-3 collisions lower than for a random oracle?
Can we define one finite set of input strings for a SHA-3 hash (or SHAKE XOF) function so that the collision probability is arguably lower than for a random oracle, with a definition of the set making ...
- 144k
3
votes
2
answers
812
views
How much entropy is lost due to collision?
If entropy is hashed with SHA-256 for example, and the input has exactly 256 entropy bits, how much entropy is reduced after hashing due to collision? Is there any reference that explains how to ...
0
votes
0
answers
141
views
Do "superfast" keyed hash functions exist?
A common family of requirements for (cryptographic) keyed hash functions is that the function $h(k,-)$ should have good collision resistance for all keys $k$, even if the key $k$ is known to the ...
1
vote
1
answer
142
views
Hash-Then-Encrypt or Encrypt-Then-Hash on Keyed Hash Functions
I have seen other answers here on Stack Exchange regarding MAC-Then-Encrypt vs. Encrypt-Then-MAC (and this article regarding MAC-Then-Encrypt padding oracle attacks on SSL) as well as generic Hash-...
- 11
0
votes
0
answers
81
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
1
vote
1
answer
101
views
Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]
I came upon the following hash function (pseudo-code):
...
- 33
2
votes
2
answers
186
views
A question about "attacks on MAC key space"
At page 336 in "Handbook of Applied Cryptography - Menezes", I see the sentence
For $n$-bit MAC with $t$-bit key space this requires $2^t$ MAC operations, after which one expects $1+2^{(t-n)...
- 31
1
vote
1
answer
53
views
Collision ISIS Problem
I'm trying to understand the inhomogeneous SIS problem and I'm came across to a scenario that I don't know how to evaluate.
Let $A,B \in \mathbb{Z}_q^{n\times m}$ be two random matrixes and $u,v \in \...
1
vote
0
answers
73
views
Is it possible to get the negative point with −x in that version of the Pedersen hash over the BaybyJubJub curve?
The Pedersen hash is a low constraints friendly hash for Zk-Snarks.
Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
- 240
2
votes
0
answers
105
views
Security of Even-Mansour based Merkle-Damgård
Assuming I have single-key Even-Mansour with single $2n$-bit permutation in wide-pipe Merkle-Damgård specifically with Matyas-Meyer-Oseas mode outputting $n$-bit hash.
What security can I expect ...
- 1,682
2
votes
1
answer
145
views
Recommended output filter for Rumba20 [closed]
Rumba20 is a compression function that maps a 192-byte (1536-bit) string to a 64-byte (512-bit) string. It's designed to provide collision resistance by using Salsa20 (or ChaCha20) with the ...
- 2,060
1
vote
1
answer
424
views
Pedersen Hash : when truncating the hash to keep only the X coordinate, is it possible to compute a collision when the Babyjubjub curve is used?
The Pedersen hash is a low constraints friendly hash for Zk-Snarks.
Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
- 240
0
votes
1
answer
207
views
If we supply a random uuid4 hashed salt to Hashid, will it be considered secure?
Ideally, Hashids -: https://pypi.org/project/hashID/ are considered insecure and it is recommended that we should not use them for any sensitive functions. Though, is a HashId considered secure if we ...
5
votes
1
answer
161
views
The rigorous proof in the commitment based on CRHF
I'm reading about the lecture of Yevgeniy Dodis. In his lecture 14, section 2.3.2, gives a commitment construction based on CRHF, but the proof of hiding is high-level. I want to know the rigorous ...
- 311
2
votes
1
answer
348
views
Implementing a Merkle tree using a 128 bit hash function?
I need to implement a Merkle tree using a 128 bit hash function. In general, any hash function that guarantees pre-image, second pre-image and collission resistance should be fine to implement a ...
- 149
1
vote
1
answer
2k
views
What does the 256 in SHA3-256 and SHAKE256 refer to?
I am simply wondering what the bit-length in the algorithm variant in the table below refers to? For the hash functions I assume that this refers to the ouput length in bits. For instance for SHA3-256 ...
- 335
2
votes
1
answer
176
views
theoretical hash collisions vs random number collisions
I have a theoretical question about the probability of collisions of hashes versus random numbers. I'm not interested in the exact probabilities. The exact hash function is not relevant (we can assume ...
- 123
3
votes
0
answers
113
views
Are there "light" versions of cryptographic hash functions?
After tinkering with cryptographic hash functions, I started wondering if they do have counterpart functions that would imitate their cryptographic properties but with a lower level of strength in ...
- 153