New answers tagged

1

Question1: How can we show/prove that the random element only with a negligible probability can have such structure? If we assume the random oracle model and have $h: \{0,1\}^* \to \{0,1\}^n$ then we can state that $h(.)$ is equivalent to randomly sampling from $\{0,1\}^n$. Thus for a random element $r = r'||r''$ the probability that $r$ has the structure $...


3

If I understand you correctly, you are using the Simon key expansion process, so that the input to your block is the 256 bit Simon key, and the output is the 256 bit last round key (and you're ignoring the Simon encryption process entirely). If so, three nits: I believe that you can find preimages for your hash function in $O(2^{64})$ compression function ...


1

That is the point of ROM. You assume 'somehow' the existence of a truly random function with no collisions. You do not care how this is constructed and designed because there is no real truly random hash function. But you assume it exists in an ideal world. Of course this has implications in real world because such a function does not exist. But ROM ...


1

The main question about this topic is: Guarding against cryptanalytic breakthroughs: combining multiple hash functions. There you will find some better combiners for multiple hash functions. I would generally recommend against the extra complexity - a single good hash ought to be enough. Now, regarding your way of combining them: Does this make sense? ...


0

With a cryptographic hash function, reversing hashes amounts to trying potential inputs until you find an input that matches the hash. If you do find an input that hashes to the target, it is presumed to be the same input that was originally used (e.g. the user's password). In that case, the entropy and length of the input is useful to know since it can ...


1

Generating collisions for a 32-bit hash is trivial; thanks to birthday paradox, the expected effort is only about 217 hash evaluations. If you don't believe me, try running this Perl code: use strict; use warnings; use Digest::SHA 'sha256'; my $message = "a"; my %preimages; while (1) { my $hash = unpack("H8", sha256($message)); print "$hash: $...


1

Based on the more recent Disturbance vectors for collision attacks against SHA-1 by the same author, which Maarten Bodewes mentioned in the comments, the initial attack/complexity was optimistic/erroneous. The algorithm actually leads to a disturbance vector that had already been published: Using our algorithm and those cost function we retrieved all ...


4

Surprisingly enough, it would appear that generating a simultaneous collision wouldn't be that much more expensive than generating a single collision for SHA-1. The basic idea is to form a $2^{64}$ wide multicollision on SHA-1; that is, $2^{64}$ distinct messages that all SHA-1 hash to the same value. We can do this by using Joux's idea of forming finding ...


1

The basic problem seems to be that of canonicalization. If you can't reorder the set, then you will have to choose a commutative, associative, operator to concatenate the values; $a \otimes b = b \otimes a$ and also $a \otimes (b \otimes c) = (a \otimes b) \otimes c$ An immediate candidate for this would be to interpret the elements, $m_i$ as integers and ...


1

As pointed out by @kodlu, given an input sequence of 512 bits ($2^{512}$ possibilities), and given a hash function which spreads out the resulting hash approximately evenly, you would wind up with approximately $\frac{2^{512}}{2^{256}} = 2^{256}$ input sequences in your table which store the result of your exhaustive mapping for a given 256 bits hash (...


1

If you're tossing $n=2^{512}$ balls into $m=2^{256}$ bins, as a model of a good hash function, so $n=m^2$, the average load will be $n/m=m$ so the typical output will have $2^{256}-$fold collisions. See paper here, last case of theorem 1, whereby the maximum load won't be too far away from average load in a multiplicative sense, in your case. What about ...



Top 50 recent answers are included