Hot answers tagged

18

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


15

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


11

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


9

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


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

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


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

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


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


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

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


6

Yes, you're misinterpretting the PRF. It's not just a hash function (and when you hit the end of the function function, start back at the beginning). Instead, if 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 ...


6

I am wondering if using Skein or the Keccak hash algorithm in this construction (as a stream cipher) is secure: In the case of Skein and Keccak it should be secure. However, both of those have defined their own cipher modes which you should IMO prefer. (For speed and compatibility, if not security.) The Skein one is defined in section 4.10 of the paper. ...


5

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


5

With the problem as initially stated (that is x = 1000, y = 100000, n = 128), 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 ...


5

$\langle \langle 1\rangle || m_1, 0^n \rangle$ is a valid tag on $m = m_1$


5

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


5

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


5

You are quite correct. A PRP in counter mode is, in fact, distinguishable from a random sequence if you approach the "birthday bound". We get around this by never generating that much output at once. With a 128 bit block cipher, an output of $2^{40}$ bytes (which is a lot of output) gives us a distinguishing advantage of about $2^{-56}$ (the probability ...


5

The CBC-MAC construction indeed can use a PRF instead of PRP. It is now based on PRP due to historical reasons: the blockciphers used for CBC-MAC were based on permutations. From the security point of view there will be no difference: the security proof for the CBC-MAC first converts PRP to PRF (which is indistinguishable up to $2^{n/2}$ queries) and then ...


5

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


5

You don't need to change the key at all in terms of it being "overused". The only reason to change a key is when you use it beyond the bounds given in proofs of security. You have to look this up, but if you are using HMAC-SHA256 with a 256-bit key then you can go on for about $2^{128}$ computations, which you will never every do. Having said that, the ...


5

No, A is not true. Suppose that $G_1$ is a secure PRG and $G_2(s) = G_1(s) \oplus 1$, obviously $G_2 \neq G_1$ and $G_2$ is a secure PRG. You can see that $G(s) = G_1(s) \oplus G_2(s) = G_1(s) \oplus G_1(s) \oplus 1 = 1$ which is obviously not a secure PRG. Now you have a hint. You should think the rest of the problems.


5

HMAC is sometimes called a keyed hash. The key is not part of the input of a secure hash (as CodesInChaos already indicated in the comments). HMAC is a relatively simple construct to allow a key to be used as input to the underlying secure hash. It specifically is constructed to disallow length extension attacks - although those are not likely an issue in ...


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

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

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



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