# Tag Info

4

A "generic attack" against a cryptographical primitive is one that can be run independently of the details of how that cryptographical primitive is implemented. The most obvious case is a cipher that takes an $N$ bit key; the generic attack of brute force takes a ciphertext, and attempts to decrypt it with all $2^N$ keys; when we find the known (or ...

4

The definition of perfect hash functions do not have any security/cryptographic requirements. For example, the hash function that simply outputs the first n bits of any string is a perfect hash function on the set of n bit strings. Obviously this function does not hide the input at all. So the answer to your questions is that it depends on the hash ...

3

I prefer using definitions that explicitly specify who does what. Weak collision resistance: After Bob creates some message x1, it is "computationally infeasible" for an attacker Mallory to compute some other message x2 such that h(x1) == h(x2). Strong collision resistance: It is "computationally infeasible" for an attacker Mallory to find any two messages ...

2

First, I must warn you that any definition that uses "feasible" will not be a rigorous one. The only way I know to rigorously define collision and preimage resistances is using function families, i.e. keyed hash functions. That said, if you believe the negations are equivalent, the definitions you are using are themselves equivalent (you correctly negated ...

0

I think your two negations are not the same, here is my reasoning: The existence of a $x \in D$ for which it is feasible to find a second pre-image (the second negation), does not guarantee that it is feasible to find that $x$. Therefore, the second negation does not immediately imply the first.

2

Is appending the hash of the plaintext to the end of an encrypted message sufficient to ensure integrity? Not in the sense of authentication. Such a construction is malleable for many reasonable encryption algorithms. It also leaks the plaintext to anyone who can guess it, since they can calculate $h(P_i)$ for guesses (brute force or dictionary attack) ...

3

Instead of rolling your own, you should use PBKDF2, which does what you try, but right. Alternatively use scrypt or maybe bcrypt, they try to be more expensive on GPUs and custom cracking hardware. (this will take about a million times longer compared to the usual method of calling a single hash function) If you used $n=10^9$, brute force would take a ...

1

Edit: Sorry, I know this is bad form, but I'm replacing my entire answer :). The proof takes place in the so-called CKS-light model, which allows the adversary only two "register honest" queries, i.e. the ability to register two identities of his choice and receive their generated public keys. In the end, he must distinguish the shared secret of these keys ...

4

My understanding is that, for the even more special case where a and b are not only of equal length but some power of two times a fixed block size, all hash tree systems (also called a Merkle tree system or a binary hash chain) meet your criteria. E.g. satisfying following relation h(a || b) = h(a) · h(b), where h(x) is hash function itself, x || y is ...

1

I don't know if the mathematical property you are looking for has a name. It's a bit similar to linearity, but $||$ is of course not an addition operator (e.g. not commutative). A function with this property is not as secure as a perfectly secure cryptographic hash function of the same output length. You can find collisions with a probability related to the ...

2

MD5 is a Merkle–Damgård hash, so it's vulnerable to the length extension attack. That means there's a simple way to find multicollisions using any algorithm that can find collisions for an arbitrary IV: Find some collision $\operatorname{MD5}(a) = \operatorname{MD5}(b)$ using the normal IV. Find another collision $\operatorname{MD5}'(c) = ... 1 There is at least one secure, homomorphic hash function that I know of. It's found in the paper "On-the-Fly Verification of Rateless Erasure Codes for Content Distribution" located here: http://pdos.csail.mit.edu/papers/otfvec/paper.pdf The paper was published in the 2004 IEEE Symposium on Security & Privacy. Section IV describes the scheme and ... 0 The order of every element$g$of a group$G$divides the order of the group ($p$). Since$p$is prime, every$g\in G$has order$1$or$p$. Only the identity element$e$satisfies the first case, so every$g\in G\setminus\{e\}$is a generator of$G$, i.e., $$G = \{g^0,g^1,g^2,\cdots,g^{p-1}\}.$$ This allows defining a bijection ... 6 The cost of finding collision for SHA-1 is currently estimated as$2^{61}$SHA-1 calls. To understand how much (or how little) it is, we could look at Bitcoin mining. Right now (September 2014) the entire mining network computes 200,000,000 giga-double-hashes of SHA-256 per second, or$2^{61}$hashes in three seconds. 3 Stevens' attack is on full SHA-1, not a reduced round variant. The differentials are on only part of the rounds, but the attack itself extends to the full algorithm. However, the attack (pdf of full paper) described as "fully working" in the slides you link has still not been used to demonstrate actual collisions, so it's indeed theoretical. Additionally, ... 5 If you had an algorithm that used a Base64 conversion as a part of its processing, that would not be considered grounds for disqualifying it as a hash function (be it a cryptographical or noncryptographical hash). We consider a function to be a hash solely on the properties it has (statistical in the case of a noncryptographical hash; preimage, second ... -1 Hash functions are defined to work on an arbitrary integer number of blocks. The minimal quantity of data that can be processed by an hash function is a single block. So, if the message size is not an integer multiple of the block size one has to pad it to the right size. One needs also to make the message + padding have one and one only interpretation, ... 1 Actually the HMAC value is not decrypted at all. The recipient takes all the needed input and she computes the HMAC on her own side and check if the result she got it is equal to the value on the message she got. You can roughly see the HMAC algorithm as an symmetric key signature. You cannot decrypt an HMAC, you only check that the value is correct. 2 That Wikipedia article is full of errors and false claims. Most importantly, FSB has not been proven to be as hard as an NP-complete problem. This is because the syndrome decoding problem is NP-hard in the worst case, but FSB uses random instances of the problem. Indeed, these random instances may be much easier to break than arbitrary instances. There is no ... 4 On the non technical side, the main reason for choosing PBKDF2 or BCrypt is that they're commonly used. This means they have seen more analysis, reducing the risk of a dumb mistake and it's easier to defend them when somebody questions your choice. What I dislike about your third variant is that it does not separate the different inputs. This isn't an issue ... 2 Are variable-length crypto hash functions still susceptible to collisions? Yes. Even if you choose an output length equal to the input length, you expect some collisions from even an ideal PRF. E.g., if my test code works:$\operatorname{SHAKE256}(\text{'6'}, 8) = \operatorname{SHAKE256}(\text{'8'}, 8)$. Is there any work done to show or prove ... 5 Is there any work done to show or prove collision resistance gained by increasing digest length? Actually, as CodesInChaos has mentioned, the variable length versions of Keccak ("SHAKE128" and "SHAKE256") are known not to have any collision resistance beyond their security level, independent of how long we make the output. So, what's the point? So, as ... 1 The answer is in the CEN-EN 14890-1:2009, 7.3 General Aspects, and in the SHA-1 and SHA-2 specifications. The output of the hash algorithm for both SHA-1 and SHA-2 is the state of the hash algorithm (specified by$H^{(0..N)}_x\$), after the last block is processed. So the output size is identical to the running state, possibly truncated to the leftmost bits. ...

5

What you are describing is essentially the same things as a hash list. A hash list is a sequence of hashes over which another hash is calculated. Your scheme does the same thing after sorting. The sorting won't matter for the security of the scheme; it won't increase the chance of collisions. Hash lists are also used for a well known structure called a ...

1

My personal opinion: "proven secure" is more of an advertising slogan than anything else. The one-time pad and certain multiparty protocols can be shown to have some kind of information-theoretic security; these are exceptions to the rule. "Don't roll your own crypto" is still sensible advice however. For the rest of this discussion, I'll try and stick to ...

2

Is it necessarily a peer review process? Does an algorithm need to withstand exploit attempts for N amount of time by M many experts? Or, is there a mathematical proving process that security experts can apply on their own to evaluate an algorithm? Yes, yes, and sometimes. Some algorithms can be proved secure under certain assumptions. However, ...

Top 50 recent answers are included