Tag Info

New answers tagged

1

Any PRNG with a finite state size is eventually periodic. The maximum period possible is $2^n$ for an $n$-bit state, but the average with a well mixed state is $2^{n/2}$. Here the hash function used is SHA-512, but the state is 1024 bits. A first guess would be a period of $2^{512}$, rather than the $2^{256}$ mephisto gives. Let's look at the cycles. Both ...


10

This is trivially true via the pigeonhole principle. SHA-2/512 has $2^{512}$ possible outputs, but $2^{2^{128}} - 1$ possible inputs. Trying $2^{512}+1$ unique inputs is sufficient to produce at least one collision. That said, SHA-2/512 is designed to be collision resistant, which implies that it should be hard to find two inputs that hash to the same ...


7

What choice did they have? F1 is a bitwise function with three inputs and one output. There are $2^8 = 256$ such functions. Only 70 of them are "unbiased" (i.e. have as many 0 and 1 outputs in their image). If you further require that each input, as well as the order of inputs, matters for the output, you are left with only 36. However, those 36 are all ...


1

Yes, this PRG is theoretically periodic. Approximately after generating $2^{512}$ outputs a state will be generated that collides with a previous state. (A previous version of this answer said $2^{256}$ as I missed that two outputs are used for the state. Otus answer pointed out this mistake.) This follows from the birthday problem. However, $2^{512}$ is ...


5

With respect to collisions, hashing twice can not increase security, because if $x$ and $x'\ne x$ collide for $H$, that is $H(x)=H(x')$, then $H(H(x))=H(H(x'))$. Otherwise said, any collision for $H$ is a collision for the double hash $H\circ H$. It is therefore trivial to exhibit collisions for $\operatorname{MD5}\circ\operatorname{MD5}$. Hence the answer ...


0

Assuming you mean a normal HMAC with a strong unknown key, no amount of MAC values for known, or even chosen messages would help you find the key. That would mean a failure of HMAC's forgery resistance, which is expected of MAC algorithms. (It would be a very bad case of forgery attack, since it would allow forging MACs for any messages. Even much lesser ...


2

When the lower 63 bits of current_block are 0 (that is, for current_block either $0$ or $2^{63}$), the step last += current_block is the same as last ^= current_block, and all operations in compress are linear. Otherwise said each bit of the output of compress is a function that reduces to the XOR of some of the input bits. We express this as a boolean ...


3

Actually, if you define the $H_i$ functions properly, it can be done. I'll make the simplifying assumption that we can treat the $H_i$ and $F$ functions as Oracles (that is, you're not allowed to look inside their implementation); I believe that it's still possible without that assumption (but the solution may be more complex). For our primitives, we'll ...


2

Proof by contradiction is easy in this case. Assume the construction is not collision resistant. Then there's an adversary who can efficiently find a pair $H(x) = H(x')$. However, that also gives them $H_1(x) = H_1(x')$ and $H_2(x) = H_2(x')$, so neither hash function is collision resistant, which contradicts the assumption.


2

No, that's not possible, as you calculate sha512(F2) without the state of sha512(F1). What you require is compress(mix(compress(mix(IH, F1)), F2)) while what you have is compress(mix(IH, F1)) and compress(mix(IH, F2)). So you would have to undo that last compression, which is obviously not possible. Here IH is the initial state (the values of $h_1$ etc.) ...


5

Most standard-use iterative hash functions (including SHA-512) are build in a way that these types of operation are not possible (without breaking the hash function). They work generally in this way: The message is split in same-size blocks (usually with some padding at the end to fill the last block): $pad(M) = M_0 || M_1 || M_2 ... || M_n$. There is ...


0

I think I found the answer to my own question, and please correct me if I'm wrong. Just for example, let $H_1$ be the collision resistant hash function and $H_2$ the not collision resistant one. This means that for some certain input $x' \neq x$, $H_2(x')=H_2(x)$. So $H(x) = H_1(x)||H_2(x)=h_1||h_2$ and $H(x') = H_1(x')||H_2(x')=h_1'||h_2$, which means that ...


0

What you are describing sounds something like a Merkle Tree: https://en.m.wikipedia.org/wiki/Merkle_tree Note that the organization of a Merkle tree is fairly arbitrary; the graph can look like just about anything so long as it is acyclic. The interesting aspect of a Merkle tree is that any change anywhere in the data "bubbles up" the tree to the root, ...


2

I would use HMAC-SHA256. While poncho's answer that both are secure is reasonable, there are several reasons I would prefer to use SHA-256 as the hash: Attacks only get better. SHA-1 collision resistance is already broken, so it's not impossible that other attacks will also be possible in the future. It allows you to depend on just one hash function, ...


1

Short answer: Yes, you're right.


2

Assuming that you know that $h_0$ is the root hash of a Merkle tree for the file, you can be sure that $h_1$ is a hash of a section of the file if you know that it's one of the hashes of the sections one level below the root and you know its sibling hashes, i.e. you have values $(h_1^1, \dots, h_1^{m_1})$ such that $\mathscr{H}(h_1^1, \dots, h_1^{m_1}) = ...


2

SipHash doesn't claim to be a secure hash function. Only a secure MAC. So if you try to use it as a hash function, with a constant, public key, you are on your own. SHA-512/64 should be a "secure" 64-bit hash, which is of course not enough for a truly secure hash, since it only has 32-bit collision resistance. However, since you only desire preimage ...


1

A quick resarch showed that there are no (good) attacks on Siphash. For SHA-512 there are defintely no known attacks. The first 64 bits of SHA-512 should have the same security guarantees as full SHA-512 has. So breaking any of the two comes down to how fast they are. SHA-512 is slower, in particular it achieves 192.5 cycles / byte in a 64-bit C ...


4

As pointed out by poncho, a hash function $H(.)$ that would consistently map two close strings $s_1$ and $s_2$ to the same value, would have to map all the strings to the same value. (Since you could go from one string to the next and it would always have to map to the same value.) So this does not make any sense. I think, like you also suggest, that an ...


6

SHA-1 is still thought to be secure whenever collision resistance isn't required. The hash is both used for signing certificates and ECDHE public keys. There's however a difference with regard to collision attacks. It is possible for an attacker to attack the collision resistance with certificates by getting their own certificate signed by a CA. In ECDHE ...


0

Your question is about breaking password hashing schemes (PHSs). The usual way to break password hashes is by brute-forcing the input until you find a match between the resulting hash and the obtained hash. Now there're some counter-measures to harden the schemes against various attacks that would allow you to break many passwords very fast, because most ...


1

Well, firstly, SHA-1 still seems to have 160-bit preimage and second preimage resistance, so using it in HMAC requires more than 128-bit AES keys to get equivalent security. AES 192 would be sufficient, but isn't used in e.g. TLS – RFC 3268 says: The AES supports key lengths of 128, 192 and 256 bits. However, this document only defines ...


4

The expected number of collisions (assuming that the hash function can be modeled as a random function) is precisely $2^{-n}\binom{m}{2}$; that is, the expected number of pairs of values $x \ne y$ with $H(x) = H(y)$ (and so, to answer Ricky's question, $H(x) = H(y) = H(z)$ would count as three collisions). The reasoning is the obvious one; there are ...


1

The goal of this method is to achieve collision-resilience (resistance against collision attacks). The second hash can be viewed as $H(R || M)$ for message M and some randomness R that is unknown to an attacker. Now, even if an attacker could efficiently find collisions for $H$, he cannot use this ability to run the standard forgery attack that works as ...


1

While the approach seems to work in general, it is not true that there would always be at most two hashes required per elided range. Suppose you have an eight-byte long content and want to elide all but the last. You need to supply one hash for the left half, one to cover the next two and one more to cover the last one. Similarly, with 16 bytes of content, ...


3

Ignore the integer overflow issue I mentioned in a comment, for a moment. I don't see how this adds any security. For all $n>2$, the function you are calling Fibonacci is one-to-one, and since $n<256$, you could easily build a lookup table without much memory to invert the function. Therefore, to break this, all one has to do is invert the Fibonacci ...


2

You can use those values more than once and there isn't much of a reason to choose another pair – except longer values for a cipher with a larger block size. The only real requirement for the values is that they differ. However, if someone found a fixed point or other cycle for MDC-2 with a given block cipher, they could choose that point as an IV and be ...


1

if(checkValue.compareTo(resultOfModulus) == 0) Here's your problem; you're checking if $y^3 = (md5BigInteger \bmod 2^i)$; that's wrong (as $md5BigInteger \bmod 2^i$ won't typically be a cube). Instead, what you want is to check if $y^3 \equiv md5BigInteger \pmod{2^i}$; or, in other words (thinking less like a mathematician, and more like a programmer) if ...


3

If the checksums (MD5 or SHA...) First things first: there is a BIG difference between a checksum (aka “cyclic redundancy checks” like CRC32) and a hash (aka “cryptographically secure hash functions” like MD5 and the SHA families). The biggest difference between checksums and hashes is that checksums are neither build, nor meant to be ...


1

If you have the hash of a 700MB file then to reconstruct the file you would have to generate random 700MB files until you found one which has the hash you were looking for. There are two reasons why this wont work well in practice: It will take far too long to get lucky and find a file with the correct hash (the chance of it happening is so low that it ...


3

Peter Schwabe, one of the authors of Ed25519, directed me to a recent paper titled "EdDSA for more curves". The section "Security notes on prehashing", page 5, says that the Ed25519 algorithm without prehashing the message is resistant to collisions in the hash function, while using the algorithm with prehashing is not. Of course the hash function is not ...



Top 50 recent answers are included