# Tag Info

## Hot answers tagged pseudo-random-function

13

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

9

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

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

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

6

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

6

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) || ... || ... 5 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 ... 5 With the problem as stated, the main weakness is that knowledge of the 873th to 1000th bits of the sequence is enough to trivially determine its 1001th to 100000th bits. That's because these 873th to 1000th bits are both part of the output and used as seed for the rest of the sequence. Update: In order to test if a sequence is produced by the stated ... 5 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 ... 5 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 four bits of entropy or it could have zero. In fact, it only has one bit of entropy, but you have no way of verifying that. Here is the definition of Shannon entropy. Let ... 4 If you have a PRF (with larger input than output), you can use it as compression function in a Merkle-Damgård structure, yielding a hash function which you can subsequently turn into a MAC with HMAC. Indeed, the security proof of HMAC relies on indistinguishability of the compression function from a PRF. There are still an awful lot of details, though. And ... 4 Levin showed that combining PRG with a universal hash function, one can reduce the number of calls. Roughly speaking, we shorten a message with a universal hash function before applying the GGM construction. That is,$y = F_{k,k'}(x) = \mathrm{GGM}_G(k,h(k',x))$, where$h$is a universal hash function. At TCC 2012, Jain, Pietrzak, and Tentes gave another ... 4 This is a common abstraction throughout theoretical crypto that is borrowed from complexity theory. It is a formalization of the idea that an adversary is only allowed to attack a primitive (PRF, PRP, etc.) by observing its "input/output behavior." Formally, adversaries are (often implicitly) thought of as Turing machines, circuit families, or whatever ... 4 I think this paper may help: M. Bellare, T. Krovetz and P. Rogaway (1998), "Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible", Advances in Cryptology - EUROCRYPT '98, Lecture Notes in Computer Science, Vol. 1403. "Abstract: We argue that the invertibility of a block cipher can reduce the security of schemes that use it, ... 4 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$... 4 The following was originally written as an edit to the question, but I'm going to put it here instead because I think formalizing the schemes might well provide you with enough of a hint for you to solve this question yourself: Let$f(k,m)$be a pseudo-random function, taking as inputs a key and a message, and outputing a value of the same length as the ... 3 As D.W. said, your questions are not very clear. I interpret your first question as asking how the security of an$\epsilon$-PRP varies with$\epsilon$. The answer to this is quite clear from Tessaro's introduction:$\epsilon=0$corresponds to the standard definition of PRP (also called fully-secure PRP in the paper). As$\epsilon$grows, the security ... 3 There are various adversary models, in fact it is typical to test our schemes against multiple adversaries to prove various nuances of security. The most intuitive of all is an adversary that can produce the plaintext (or a part of it) given only the ciphertext. An extension to this model, stronger than the other, is the one you mentioned, letting the ... 3 The term "pseudorandom permutation" is normally used for a family of (computable) bijections$f_k : M \to M$, where$M$is some finite set, and usually$M = \{0,1\}^n$. (Usually we also have a computable inverse for each$f_k$, and some security properties.) If we stretch the meaning a bit, we can expand this to any finite set$M$, like "the set of all byte ... 3 There are so many possible solutions here. Without giving your requirements more carefully, it's just not possible to tell what would count as a valid solution. Here are a bunch of schemes that offer better security than simply truncating to$N/2$bits and applying 4 rounds of Luby-Rackoff: For instance, one approach is to truncate the random function to ... 3 Here's a different attack, one that runs in$O(2^{b/2})$time. I'll also present a theoretical framework for how to think about the security of these sort of schemes. The bottom line is that it looks like no scheme of this form can be secure; I'll try to make more precise what I mean by that, below. We can consider a generalized scheme,$H_K(x) = ...

3

Here are two different ways to break $G$. Attack 1. $G$ is unlikely to be a secure PRF, at least against non-uniform adversaries. In particular: there is likely to exist a fast attack (though it might take $2^b$ steps of computation to find the attack). The idea of the attack: With high probability, there exists $x,x'$ such that $E_A(x)\wedge 1 = E_A(x') ... 3 Scrypt is the best function for key-stretching we have. With such a bad password, you'll need all the stretching you can get, so make sure to use a large work parameter and a fast implementation. But you should really consider using a stronger password. 10 random characters are much better than only 6. 3 If you take a pseudo random permutation permutation you usually get a hard to invert PRF. AES with its 128 bits is a bit narrow, but Salsa's 512 bits are certainly wide enough. Commonly used compression functions are built from block-ciphers with similar techniques: For example Davies–Meyer (used in popular hashes such as MD5, SHA-1 and SHA-2) uses:$H_i ...

3

Yes, of course other modes have been studied. See this paper for one study, and that paper for another study. The bottom line is that CFB, OFB and CTR modes are also good PRFs (assuming you use random IVs). As for ECB mode, it is a good PRF if you limit it to inputs of precisely one block (128 bits for AES); it is not a good PRF if you are allowed to ...

3

In terms of the question in the title, the mode of operation has no effect at all on the pseudo randomness of the underlying block-cipher. If a block cipher is pseudo random then it is pseudo random, regardless of the mode it is embedded in -- with the caveat that if we differentiate between (weak) CPA-resistant pseudo randomness and (strong) CCA-resistant ...

3

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

2

In cryptography, the standard we use when evaluating a cryptographically secure random number generator is "how much effort does it take to distinguish this generator from a truly random source". By this criteria, we find that, as specified, your $f_2$ is considerably better than your $f_1$. With $f_1$, we can distinguish the generator from random (and ...

2

Short answer: I'm pretty sure that your suggestion would "work," but I don't think that it would be better than the GGM approach from either a performance or a security point of view. Long answer: As Mikero suggestions, we have to be careful about the intput and output lengths of the PRGs. So the GGM problem starts with a family of pseudorandom generators ...

2

Okay, I think I know why. If you have a n bit input, and you wanted to run the PRG, you would need to run it maximum $2^n$ times (I made a mistake by thinking you could run the PRG n times). Whereas if you change the key and run the PRG in a recursive manner using the output of the last PRG as input, then you would only need to run it $2 \cdot n$ times.

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