# Tag Info

17

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

8

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

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

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

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) || ... || ... 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 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 ... 6 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 ... 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 ... 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 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 ... 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 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 ... 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 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 ... 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 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 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 (Note the OP's clarification that even for 1, the adversary does not have the key k.) Yes.$\:$The way to show anything like those, is to use the fact that oracle access to prfk is sufficient to efficiently determine the extent to which an adversary is violating those. def straight-line_reduction_1_(): m = random_element_of_(domain(F)) query F on 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 ... 4 Not if the attacker is given enough time to ask for the values$F(k,x)$for all$2^n$values of$x$. We have$\Sigma_x F(k,x) = 0$which is distinguishable from random. 4 Theorem. (Barring any errors, which are certainly possible): Let$A$be any adversary attacking$F$. As long as$A$makes fewer than$2^n$queries, there is an adversary$B[A]$attacking$f$, making at most twice the queries of$A$and running in (roughly) the same time such that$ \mathsf{Adv}^{\mathsf{prf}}_F(A) = \mathsf{Adv}^{\mathsf{prf}}_{f}(B[A]). $... 4 Yes, it is a secure PRF, as long as the attacker can make at most$2^n-1$queries. The key lemma is purely information-theoretic in nature. From this lemma, you can prove your result using standard methods. Lemma. Let$x=(x_1,\dots,x_q),y=(y_1,\dots,y_q)$are any sequence of$qn$-bit values, where$q<2^n$and the$x_i\$'s are all distinct. Then ...

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