Hot answers tagged

21

In most applications, it's desirable that a hash function is fast, and it would not be a problem if it was ultra fast (say, as fast as input in cache memory can reach a CPU) if that's not at the expense of security. This includes usage in signature, encryption padding, construction of block ciphers. In application doing key stretching, including access ...


9

The currently accepted answer is good, but I'd like to add something. "security" is a broad term in this context, and you should ask what threat you want to defend against. In most discussions "collision" is all about finding a different input with an identical output. But for the password case, the "fast hash" is problematic ...


8

No, the proposed construction is not secure, unless the block size $b$ of the block cipher is unusually large, or much wider than the MAC. Assuming $p$ known distinct message/MAC pairs $(m_i,h_i)$ with $b$-bit message $m_i$ and $h_i$ at least $b$-bit, there's a simple attack of expected cost dominated by $2^b/p$ hashes and searches among the $h_i$. The ...


6

Consider $H$ defined as: SHA-512, with it's output XORed with the first 512 bits of the input message (padded with zeroes for short message). With such $H$, the proposed MAC is insecure. Yet, as far as we know, this $H$ is no worse than SHA-512 from a standard standpoint. Argument: observe that if $H(m_1\mathbin\|m_2)=\operatorname{SHA-512}(m_1\mathbin\|m_2)\...


5

This application reveals that some expressions in the algorithm can be reversed" Actually, it is known that a large majority of the code in SHA-2, SHA-3 can be reversed. The SHA-2 hash compression function $h(s,m) = s + f_m(s)$, where $f_m(s)$ is invertible for a fixed message block $m$ [1][2] - that is, if you know what $m$ is and what you want the ...


4

I prefer to think of cryptography as infrastructure. We should strive to develop infrastructure that minimizes the number of usage caveats. It's not cryptography's job to define what are "meaningful" messages in your application. Can you look at a specific collision $m_1, m_2$ and say with certainty that no application of a hash function will ever ...


4

Does Grover's algorithm (or any other applicable quantum algorithm) only apply to weakening the hash function itself or can it also search only plausible inputs (a-z, A-Z, 0-9 <=14 characters) to reduce the search space? Grover's is a general search method - it doesn't know or care how the function is given interprets the input. If you give it a ...


3

Yes, it would, but (for any halfway decent Password Hashing Function) it's practically impossible to find such a collision. Password Hashing Functions are Cryptographic Hash Functions with some extra properties. Cryptographic hashing functions have a single input, and are collision, preimage, and second-preimage resistant. Collision resistance means that it'...


3

This is already answered here for 1 iteration, and here for many iterations, but since the latter answer presents an heuristic argument I'll leave here Lemma 4 of Functional Graphs and Their Applications in Generic Attacks on Iterated Hash Constructions which gives a good approximation based on Theorem 2 of Random Mapping Statistics, and (3.10) of On the ...


3

Given a hash function that is tuneable for "speed", (iterations, perhaps), increasing the speed at which it hashes does not create more collisions. The security issue with a hash that is too fast is that given X amount of time, a hash that is faster will generate a greater quantity of outputs, so an attacker has a higher chance of finding a ...


2

No. The birthday paradox applies to all image spaces. Randomly evaluating any function with large input space and an image space of size $2^{n/2}$ is expected to produce a collision after roughly $2^{n/4}$ evaluations.


2

given an algorithm of a hash function, how to transform it into a circuit? Most importantly we first want to better state the problem What hash function? Do we want a circuit for the full hash function and a fixed-length input [which seem best matches the question], or for some part of the hash [like a round of the hash function with input one padded ...


2

I am wondering why some people think it is suitable for many cryptographical primitives Well, I'm not one of those 'some people', however I will give you my perspective. One of the good properties we like in our cryptosystems in 'avalanche'; that is, a small change somewhere ripples throughout the system. I expect that 'some people' take notice of this and ...


2

The OP got the idea from a YouTube post that argues around the MD5. Here is the simple argument if anyone watches the video. The speed doesn't imply that a hash function is insecure, the design makes it secure. Over the years, the researcher find weaknesses in the design of the MD5 and improved over time. Once the MD5 was released, 1992, the attacks set out, ...


2

Is it feasible to build a whole branch of cryptography on a family of pseudo-random sources? In theory, yes. If there was an efficient and Cryptographically Secure Pseudo Random Number Generator built from a chaotic system, then that could serve as the foundation of reasonably practical symmetric cryptography, and even signature. Problem is we know no such ...


2

Privacy-preserving distance computation on coordinates is certainly possible, with some restrictions. The paper "Homomorphic Proximity Computation in Geosocial Networks" (2016) by Hu et. al. (PDF) is a quite accessible example of doing this. The main approach they demonstrate is based on an asymmetric Somewhat Homomorphic Encryption (SWHE) scheme ...


2

I want a hash function as $H_4: G_2\to \{0, 1\}^n$ for some length $n$ i.e., mapping from group element to a binary string of length $n$. In this case the group $G_2$ consists of points on an elliptic curve. If $r\in G_2$, we can define $H_4(r)$ as $\operatorname{SHAKE256}(R,n)$ where $R$ is a unique representation of $r$ as bitstring, and $\operatorname{...


2

The quoted text seems to talk about finding a collision of a 128-bit hash function with the Birthday attack. In a birthday attack, one creates around $\sqrt{2^{128}} = 2^{64}$ messages so that they expect to find a colliding pair with 1/2 probability. In the described attack, Oscar wants to create two specific messages that have the same hash value. $x_1$= ...


2

Given a hash function $\mathcal H()$ and a hash value $H$ that is in the codomain/range of outputs of $\mathcal H()$, can you determine if $H$ can be produced by $\mathcal H()$ (i.e. is $H$ in the image of $\mathcal H()$)? I'll assume "codomain/range of outputs" is defined without reference to what the hash actually outputs (rather than as the set ...


2

Given a hash function H() and a hash value h that is in the codomain/range of outputs of $H()$, can you determine if $h$ can be produced by $H()$ (i.e. is $h$ in the image of $H()$)? Generally, you cannot if you consider $H$ to be a black box. I would be surprised if there are values that cannot be reached by a hash function like SHA-2/3 though, because of ...


1

To: ["The",""] First International Bank ["Panama",""] Subject: ["Money",""] ["Wire","Transfer"] ["Order",""] from my account ["Num","#"]1234[".",""] I ["hear by","would like to"] Instruct ["you &...


1

Providing a hash value is no evidence that you have a pre-image. I can easily produce the 256-bit number 0x9A867C4957D32E09420239682A3502F6, but that doesn't prove that I have an input to SHA256 that generates it. A NIZK construction would allow me to demonstrate that I do have an input that produces that value, but without revealing any information about ...


1

Sounds a bit like coursework. (: Some ideas to get you started: Are you aware of how a ciphertext $C = (c_1, c_2)$ is constructed? That is, can you state $c_1$ and $c_2$ in terms of the message $m$, and the key pair $x, y$? Can you then state what form a ciphertext would have to have, in order to be a valid encryption of $m \cdot m'$? Once done, can you ...


1

Apparently chaotic behavior is necessary but insufficient for cryptography. It's a result of cryptographic security, not a cause. Some people invert causation, and think that anything displaying chaotic behavior is suitable for cryptography. I don't know why some people make this mistake, and it's not unique to cryptography. Lorenz's definition of chaos: &...


Only top voted, non community-wiki answers of a minimum length are eligible