Tag Info

Hot answers tagged

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


13

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

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

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


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

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


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

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


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

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$


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

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.


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

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

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


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 $q$ $n$-bit values, where $q<2^n$ and the $x_i$'s are all distinct. Then ...


4

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


4

$\;\;\;$ No. $\:$ A PRF involves a secret key; a Random Oracle doesn't. $\;\;\;$ One can construct a PRF from a random oracle.


4

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


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

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

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



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