Tag Info

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

Under the assumption that SHA-1 is a random oracle, $f_2$ is better (if I understand it properly, i.e. concatenating a constant seed with a counter) in that it forbids the possibility of a short cycle. Specifically, $f_2$ guarantees that no two inputs will be the same, which means that any two outputs are independent of each other, whereas $f_1$ does not ...

I am not sure if $\mathsf{PRF}$ alone can be used to construct; however there is a natural way to construct $\mathsf{MAC}$ using $\mathsf{PRF}$ and $\mathsf{UHF}$. You can see the following papers for more detail: LFSR-based hashing and authentication. In CRYPTO 1994. Bucket hashing and its application to fast message authentication. In CRYPTO 1995. On ...