The Stack Overflow podcast is back! Listen to an interview with our new CEO.
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]; ...


30

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 ...


27

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 ...


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 ...


19

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; ...


16

Well, the chief vulnerability is that if an attacker is given a large enough sample of Mersenne Twister output, he can then predict future (and past) outputs. This is a gross violation of the properties that a cryptographically secure random number generator is supposed to have (where you're supposed to not even be able to tell if the random bit string ...


15

The answer 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$, ...


12

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

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 ...


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

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 ...


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

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 ...


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 ...


8

Let's start with a general secure KDF construction, as follows. Let $F(k,x) \rightarrow \{0,1\}^n$ be a secure PRF. Then choose $L$ such that $L \times n$ provides as many output bits as you need for all of your generated keys. Let $S$ be your original secret key/entropy. Generate the following string: $KDF(S,N,L) := F(S, C || 0) || F(S, N || 1) || ... || F(...


8

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 ...


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

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$ ...


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

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

In my practice (Smart Cards, often using DES and increasingly AES) Key Expansion is often used to designate production of subkeys in a block cipher. This process is often a mere bit extraction, as part of the algorithm's Key Schedule. Key Diversification is, almost exclusively, the process of producing a device key from its serial number (or other ...


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 ...


7

It is not accurate to say that the keystream from AES-CTR is a pseudorandom function. However, it is a pseudorandom generator. Furthermore, the construction that you gave is close to working but it's unclear where the key fits in. I will therefore elaborate on what we can exactly say. Let $F$ be a pseudorandom function, and for simplicity assume that the ...


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