Hot answers tagged

9

Hash functions must be public, so if you want use RSA as hash function you should fix $K$. Now let $n$ be the RSA module and $H$ denote RSA hash function. We have $$H(M)=H(M+n)$$ so this function is not second preimage and collision resistant. Also this system is not first preimage resistant (with known public and private key): Let $M^k=h \pmod n$ ...


9

I'll review the standard mathematical notations used for $H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ , going from the bottom up. Hopefully, that will make the rest evident. $\{0,1\}$ is the set with the two elements $0$ and $1$, known as Booleans. $\{0,1\}^k$ (for some non-negative integer $k$ ) is the set of tuples with $k$ Booleans, or ...


6

If I understood your question correctly, you want a message authentication code (MAC). The "hidden input" is usually called key and the "visible input" is just the message. The output of the MAC is called tag (or also MAC). The main security goal for MACs is resistance against forgery: It should be computationally infeasible for an attacker who does not ...


5

The other answer already explains that what you are looking for is a message authentication code, but did not show a clear attack against your construction. At the very least it seems to be vulnerable to length-extension type attacks, like the keyed hash mentioned: Take the output for some known message, where the length of the key x and message v is ...


5

You are right that if it costs Alice & Bob effort $N$ to agree on a key in this way, then it costs Eve only effort $N^2$ to find it. So the protocol is not secure in the standard sense, and probably not very useful. (Maybe in some highly constrained situation with very short-lived keys?) More generally, this purports to be a key agreement protocol whose ...


4

Is there any problems from using the approach I am suggesting? Yes, there are several. First of all, some sites generate first time passwords, or even long time passwords. You may want to store those too. What if a site requires frequent updates? If one password is reversed, you'd still loose confidentiality. Would it actually be less secure if ...


4

MD4 is Not One-Way. The attack described in the 2008 paper is a theoretical attack with complexity $2^{102}$, which is better than the brute force complexity of $2^{128}$. In later theoretical results reported here the complexity dropped to $2^{94.98}$ and here it dropped even further to $2^{69.4}$ for secondary pre-image attacks. Similarly, The MD2 Hash ...


4

Consider $$H(M)= 9^{-1} (E(M) - 5M) \pmod {2^n}$$ where $E$ is encryption using a random permutation with an efficiently computable inverse $D$. This is a secure hash for the same reason the Matyas–Meyer–Oseas construction is. Now using your definition of $H'$ we obtain: $$H'(M)=5M+9H(M) = 5M + (E(M) - 5M) = E(M) \pmod {2^n}$$ Thus $M = D(H'(M))$ can ...


4

There are different birthday bounds when we draw independent uniform random integers less then $d$  (for some large $d$, including $d=2^{32}$ of the question) and watch for collision(s): In crypto, we often consider the bound of $\sqrt d$  ($65536$ for $d=2^{32}$) draws, at which there is a fair probability of collision: $p\approx1-1/\sqrt ...


3

The right terminology is second preimage resistance and preimage resistance. Edited to reflect comment by otus. Preimage attack takes $O(2^{n})$ hash function calls on average. Second preimage attack takes just one extra call so the complexity is essentially the same as that of the preimage attack. Given $x$ you want $x'\neq x$ such that $H(x)=H(x').$ So ...


3

You are creating a key stream using a hash function. This is often called a stream mode of operation (although it doesn't seem to be a well defined term). This is a known method of creating a key stream. An OTP requires the key stream to be completely random. This is because it would otherwise be possible to brute force the key. If you can brute force the ...


3

The difference is: All SHA-0, 1 & 2 and MD5 come under a class of algorithm called Merkle–Damgård construction, while SHA-3 falls under Sponge functions. Merkle–Damgård construction is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. And, Sponge functions are a class of ...


3

Such a category of functions is not generally used as is, but compression functions, which are close to what you describe, are (as you describe) used to build (variable length) hash functions. For example, Merkle–Damgård hashes like SHA-2 have a compression function that takes an IV (or previous block output) and a fixed size data block to generate a smaller ...


3

Indeed, this question is answered by What is the "Random Oracle Model" and why is it controversial?. However, I would like to add a few more thoughts on this. (Please read the other answer as well, since I will not repeat the very important things said there.) First and foremost, the random oracle is a model and not an assumption. We do not assume ...


2

If you want to construct a PRF for arbitrarily-long inputs using AES, then just use CBC-MAC (while prepending the message length in the first block). I don't see any advantage in what you are proposing and therefore don't see any point in trying to analyze something non-standard.


2

In general yes, but the hash function will not be cryptographic. I give you h(X) select A,B, find h(A),h(B) compare h(X) > h(A) compare h(B) > h(X) therefore h(A) < h(X) < h(B) make A bigger, B smaller repeat 2.~6., until A + 2 = B Now A + 1 = X You discovered X from h(x) therefore h() is not preimage resistant


2

There are several different scenarios to consider. If you assume all the sites/apps do things right, use a strong password hash, stay uncompromised, then no one should be able to find your master password anyway (unless it is a very poor low entropy password). So how or whether it is combined at all does not matter. More likely, you are interested in ...


2

Yes, this logic works. You have shown that given the discrete log $x$ lets you easily find collisions. Now you need to show that any collision lets you extract the discrete log $x$ and then you are done (then you have shown the equivalence).


2

How can he do that? He could take api_signature = h = md5(m) and use it as the Initialization Vector of the hash function and hash the extra data and another padding. This is the idea behind the hash length_extension attack, isn't it? Correct. My question: The api_signature will change then because it is calculated like: md5(extra || padding) with ...


2

The approach you describe is very much like the approach that is used in the masterpassword app (http://masterpasswordapp.com/). Roughly they generate a password for each site depending on: Your master password The site name A number (so that if you have to change your password you can just increase the number) Some salts that they decice. And then they ...


2

It all depends on how you define the machine that implements the random oracle. Consider this pseudo code random oracle that uses a hash table: def rand_oracle(input, hash_table): input_hash_key = get_hash(input) if input_hash_key in hash_table: return hash_table[input_hash_key] else: return something truly random You need to ...


2

A password manager that produces 16-character passwords is sufficient for most cases. Users who go for 100-byte passwords are usually overly-paranoid, since the actual security benefit is outweighed by the inconvenience. Therefore, limiting a password to 72 characters, while in theory reducing the number of possible passwords, is still very reasonable. ...


1

If I understand the question correctly, you have some sensitive data -- say, a list L of social security numbers in some order -- and you want to somehow create and publish a file D from that list such that If the person has a piece of data S, to query a database D to see if S is in L and if so, the row number where S occurs in L. You don't want some ...


1

I don't believe that it is possible given the requirements you've listed. Let us consider an arbitrary $C, M$ that meets the requirement. To reveal the entire database, what an attacker can do is compute $C(d,s)$ for every possible $d$ (about 4 million, as you said); then, he can use $M$ to compare that to every value you actually have - this reveals ...


1

While it is well known that hash1(hash2(x)) only serves to increase collisions, Collisions essentially do not matter at all for password hashing. You will only lose entropy to collisions if the input entropy is near the size of the hash output. And in that case you are well and truly out of the realm of what can be cracked for any popular hash function. ...


1

Given only the information in the original question, it would be easy for an attacker to calculate generate an arbitrary message E, then calculate the Hash("This is message E + ab3ed") = 31415, and if the system can be tricked into trusting that 31415 is the hash of a valid message, there's no way to prove that E isn't really a valid sibling of B. This may ...


1

I would like to extend Chrystographer answer. If this is a part of a incoming or outgoing message, you cannot prove it. Anybody can write valid messages. You need Merkle tree and digital signature of the root's hash.


1

@Jeroba88 your idea of using a hash function rather than just appending the service name to your secret password is simple yet crucial to achieve what you have set off to do. Some level of customisation (be careful), such as using PBKDF2 (or Scrypt) in place of just a plain HASH(Password|Service) (especially since it's probably preferable to use ...


1

Encrypting the salt is actually equivalent to just using the cipher as an initial step. That is, you could redefine the scheme as follows: tmp := D(hash(password), salt) password_hash = F(password, tmp) output := salt, password_hash Where D is the decryption function and F is the actual iterated password hash you defined. The addition of the cipher is ...



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