45

You asked for the practical impact, so the answer is that for \$120 I could probably have your entire password database done by tomorrow. Here is your program, or something similar to it: using System; using System.Text; using System.Security.Cryptography; class Program { static void Main(string[] args) { byte[] pwd = new byte[128]; ...


32

A Pseudo Random Function is a function that is indistinguishable from a function selected at random from the set of all functions with the same domain and value set. A Pseudo Random Permutation is, similarly, a bijective function that is indistinguishable from a bijective function selected at random from the set of all bijective functions over the same ...


26

From what you have described, it sounds like your system works as follows: Consult the system clock to find a 32-bit seed $s$. Use System.Random to generate a passphrase $p = G(s)$. (Here $G$ is shorthand for whatever computation happens inside System.Random.) Hash the passphrase with PBKDF(2?) into output $x = H(p, \sigma)$, where $\sigma$ is a salt known ...


22

The main fundamental issue with this approach, as with approaches that attempt to base cryptography on NP-completeness, is that the hardness you refer to is worst case hardness, and not average case hardness. In particular, the fact that the halting problem is hard merely means that for every algorithm there exists a TM $M$ for with the algorithm fails upon. ...


19

Entropy is a function of the distribution. That is, the process used to generate a byte stream is what has entropy, not the byte stream itself. If I give you the bits 1011, that could have anywhere from 0 to 4 bits of entropy; you have no way of knowing that value. Here is the definition of Shannon entropy. Let $X$ be a random variable that takes on the ...


18

The official documentation for System.Random explicitly says it should not be used for generating passwords. It’s predictable, and seeded only from the system clock. This means System.Random has at most 20 bits of entropy to anyone who has a clock accurate to within a second. Indeed, try creating two new instances in quick succession on different threads; ...


17

When there is no known weakness in the hash function we talk about their generic1 resistances Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. E.g., consider storing the hashes of passwords on the server. An attacker will try to find a valid password to your account. Second Pre-image resistant: given a message $m_1$ is ...


15

The answer is given by Henrick is good, but I try to give a explanation with more details in security area. When you think about PRF (Pseudo Random Function), you will think that there are three elements with PRF, which is $K, X, Y$. $K$ means the key, $X$ means the message and $Y$ means the output. PRF is a function, when you give this function $K$ and $X$, ...


13

If there exists an IND-CPA symmetric encryption scheme (where the key is shorter than the total length of the messages, i.e., the scheme is not the OTP), then there are one-way functions. A sequence of articles have shown how to construct pseudorandom generators out of OWFs (culminating with this paper). By the GGM construction, pseudorandom generators can ...


11

No, the two primitives are definitely not the same. A pseudorandom function is a keyed function that is (computationally) indistinguishable from a function chosen at random from all functions with matching domain and range as long as the key remains secret. On the other hand, a cryptographic hash function is a function with either a publicly known key (in ...


11

If the adversary takes $x, y \in \{0, 1\}^n$ such that $(0 \parallel x) = (y \parallel 1)$ then $$G_K(x) = F_K(0 \parallel x) \parallel F_K(x \parallel 1)$$ $$G_K(y) = F_K(0 \parallel y) \parallel F_K(y \parallel 1) = F_K(0 \parallel y) \parallel F_K(0 \parallel x)$$ The left half of $G_K(x)$ is equal to the right half of $G_K(y)$, which lets the adversary ...


11

A PRF or pseudorandom function family is a family of functions $F_k\colon \{0,1\}^n \to \{0,1\}^m$ such that if $k$ is uniformly distributed, then $F_k$ appears to be uniformly distributed among all functions $G\colon \{0,1\}^n \to \{0,1\}^m$. A PRF $F_k$ is secure if an adversary who does not know the key $k$ can't distinguish $F_k$ from a uniform random ...


10

What you're looking for is often called a construction of a PRF with "beyond the birthday bound security," and you can probably find some constructions by searching on variants of that term. For concreteness, this paper by Iwata (alternate link) almost gives a solution to your problem: The only deficiencies are that the resulting $F$ has inputs one bit ...


10

The proof is loosely as below. Lets assume a one round Feistel network, where $2n$ bits are divided into $n$ bits each $L_0, R_0$ The encryption is defined as $L_{1} = R_{0}, \\ R_{1} = L_0 \oplus f(R_0) $ where f is any random function (PRF) and $\oplus$ is XOR operation Now the cipher text is $L_{2} = R_{1}, R_{2} = L_1 $ Decryption is same as ...


10

Your intuition is not right. The fact that no forger can obtain new valid message/tag pairs doesn't say anything about the "shape" of the MAC. For instance, if $\Pi$ is a secure MAC, then the MAC obtained by appending a bunch of zeros at the end of the tag is secure as well: If a forger $\mathcal{A}$ is able to create a new and valid message/tag pair $(m,...


10

You won't be able to find a reduction since you need somehow to XOR $k$ with the output you would get from oracle queries to the PRF, and you can't do this. In fact, the answer is that this is not necessarily a PRF, meaning that I can build a (convoluted) PRF $F$ such that $F'$ is not a PRF. Specifically, let $\tilde F$ be any PRF and define $F_k(x) = \...


10

What you describe is exactly using AES-CTR to encrypt a 32-bit or 64-bit message. So, yes.


9

If you applied a PRF directly to the message to obtain cipher-text, you would not have the guarantee that you could actually decrypt the message. Suppose the PRF maps $n$ bit inputs to some $m$ bit output. The mental model of a PRF is as follows. You have have a gnome in a black box. When you hand him a string from the input space, he flips a coin $m$ ...


9

Some time ago (more than 5 years, I think) in a local forum one guy gave a "cryptographic challenge" to the community. He gave an encrypted string and a small piece of code that produced it. The goal was to find what the encrypted string was. The encryption key was based on System.Random(), which is the spot where it could be attacked. At the time my work ...


9

A n-bit hash can be brute forced $O(2^n)$ operations. If you run the numbers, you find that a 256-bit hash is completely immune to brute force attacks. $2^{256}$ is so large that it would literally take a good chunk of the available energy in our galaxy to break it. So in that sense, they are both "completely secure against brute force." However,...


8

I agree with David Cash that what you are looking for is a construction of a PRF with "beyond the birthday bound" security. There has been a variety of work on this topic. Stefan Lucks analyzes several simple constructions: SUM$^2$: Here $F_{K,K'}(x) = E_K(x) \oplus E_{K'}(x)$. This has security for up to about $2^{2b/3}$ queries, which is better than ...


8

Yes, you're misinterpreting the PRF. It's not just a hash function (and when you hit the end of the function, start back at the beginning). Instead, it is a function that generates a rather long (actually, infinite) output; we use the first $N$ bits of that output to populate the various key values. See section 5 of RFC5246; we have: TLS's PRF is ...


8

As far as I know (which, admittedly, might be limited; I do not claim to possess encyclopedic knowledge of attacks on KDFs), there are no known practical attacks against KDF1 or KDF2 (which are also mentioned on this page, following ISO-18033-2) when instantiated with a secure hash function. Regarding the relative security of these KDFs vs. HMAC-based KDFs ...


8

Before answering the actual question, I will offer some general advice. It is important to pay attention, both in class and to the textbook you are reading. If learning how to solve such exercises is a key goal of the course, such solutions have very probably been discussed at length in class. Moreover, your textbook also has proof examples, and in this ...


8

By definition, a family of functions (with a given domain and codomain) is a PRF if no efficient algorithm can (with non-negligible advantage) distinguish a randomly chosen member of the function family from a function chosen at random from the entire set of functions with the same domain and codomain. Obviously, if the family contained just one function, ...


8

In a cryptographic sense this is not really possible. The entropy of the numbers is determined by the way they have been chosen. From only a list of numbers, say $(1, 2, 3, 4)$, we cannot just determine the entropy. But if we instead say that we choose four numbers uniformly from 1 to 10, we can calculate the entropy. Recall the definition of (Shannon) ...


8

Nobody uses generic statistical tests to verify correctness of encryption algorithms. To verify correctness of an implementation, engineers write proofs of correctness for their code, tr running it on known-answer tests, confirm round-trips on randomized inputs, etc. None of this involves statistical tests, since the point is to implement a specific ...


7

Any Pseudo Random Number Generator using a Linear Congruential Generator, and no cryptography, is going to be unsafe, or at the very least unsatisfactory, per the criteria in our FAQ. Likely, a skilled adversary would be able to predict future output from some amount of past output with moderate work; at best, that won't happen, but there will be no sound ...


7

You have the math right, but you seem to have mis-interpreted the formulas. So, let me try to walk you through it. The "advantage" of an attack is the difference $|\Pr[Exp(0)=1] - \Pr[Exp(1)=1]|$. The advantage is a measure of how effective the attack is. If the advantage is large (significantly greater than 0), the attack is successful (and the function ...


7

Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. – xagawa @xagawa Yes, I want that :-) – Dingo13 I list the PRFs based on the number-theoretical assumptions. They are ``arithmetic or mathematical function.'' You can use the Feistel network to obtain (S)PRPs from PRFs in theory. From the DDH assumption The Naor-Reingold ...


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