32

A colleague of mine told me about a website that, given a sufficient quantity of output from an PRNG, had been able to deduce which application the PRNG was from. As you correctly identified this would present an immediate and probably devastating attack to any cryptographic PRNG as it indeed would allow you to easily distinguish a random string from a PRNG ...


28

One tool that tries to do this is untwister. It's almost certainly not the tool you were thinking of, though, as it cannot determine if the output came from OpenSSL specifically. It can determine Glibc's rand(), Mersenne Twister (MT19937), PHP's MT-variant (php_mt_rand), Ruby's MT-variant DEFAULT::rand(), and Java's Random() class, though, and can recover ...


20

A valid point of an elliptic curve in Weierstrass form satisfies the equation $$ y^2 = x^3 + ax + b\,. $$ We can rewrite this as $y = \pm \sqrt{x^3 + ax + b}$, which has either 2 solutions when $x^3 + ax + b$ is a square, 1 solution when $x^3 + ax + b = 0$, or 0 solutions when $x^3 + ax + b$ is not a square. In X25519, we only see the $x$ coordinate, but we ...


10

If the DDH is hard in a group $G$ with generator $g$, then it is hard to decide given $(g,g^a,g^b,g^c)$ whether $ab\equiv c\pmod{ord(G)}$. If you take as $G$ the group $Z_p^*$ of order $p-1$ with $p$ being prime, then you will have $(p-1)/2$ elements being quadratic residues ($QR$) and the other half being non-quadratic residues ($QNR$). Now, we know that $...


10

A distinguisher is an arbitrary algorithm. In fact, we do NOT want to formalize anything about the distinguisher (except that its output is a single bit, although we don't even really need to do this). In definitions, we require that no distinguisher should succeed with non-negligible probability. So, this should hold for any algorithm. Of course, we do ...


9

$s_i = s_{i-1}\cdot(N + 1) + 1 = s_{i-1} \cdot N + s_{i-1} + 1$ but $s_{i-1} \cdot N = 0 \pmod N$, so $s_i = s_{i-1} + 1 \pmod N$ which means you can discover the next number to be generated just looking to the current one...


8

For any $n \in \mathbf{N}$, let $X_n$ be a random variable which always equals $n$, and $Y_n$ be a random variable which equals $n$ or $n+1$ each with probability $1/2$. Then the probability ensembles $X = \{X_n\}_{n\in \mathbf{N}}$ and $Y = \{Y_n\}_{n\in \mathbf{N}}$ are not computationally indisinguishable. A possible distinguisher is an algorithm $D$ ...


8

A probabilistic distinguisher is still a deterministic function of its input and random coins. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins (importantly: independent of $X$/$Y$). But: \begin{...


7

Quoting from "On beating the hybrid argument" (by Bill Fefferman, Ronen Shaltiel, Christopher Umans and Emanuele Viola; 2012): The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor $k$ equal to the bit-length of the ...


7

I'm reading the question as generating a keystream per: $S_i\gets E_K(F(\mathrm{IV},i))$ where $F$ is a public function built from a hash function; for incremental index $i$ starting from $0$ and public random $\mathrm{IV}$, with $F$ having a sizable collision rate when $i$ varies; and for $E$ a block cipher with secret key $K$. That is quite insecure: the ...


6

I would say a distinguishing attack should count as a break. Especially so if it is practical. The reason for this is that if you can distinguish the key-stream from random, you invariably leak details about the plain-text. For example, suppose somebody turned up a few terabyte disks encrypted with VMPC under the same key. It says in the paper that after ...


6

Actually, it is possible to define RSA in such a way that the RSA ciphertexts are indistinguishable from random bit strings of the same length. The method is quite simple: When you select the RSA key, you deliberately pick a modulus that is just under a power of 256; for example, if you are generating a 2048 bit key, you select a modulus between $2^{2048} -...


6

Computational indistinguishability is transitive, the proof can be found in these lecture notes. Informally speaking: We have an advantage $\epsilon_1$ to distinguish distributions $X$ and $Y$, and we have an advantage $\epsilon_2$ to distinguish distibutions $Y$ and $Z$, and the triangle inequality gives us an advantage $\leq \epsilon_1 + \epsilon_2$ to ...


5

Patarin's proof isn't about distinguishing ciphertext from "random text", it's about distinguishing a Feistel cipher from a random permutation. That proof is also in the information theoretic world, which means that the Adversary is computationally unbounded, and as such can deduce everything about the cipher (the 'key', all remaining ciphertexts, etc). In ...


5

The quoted sentences means: if there is a collision among the MACs of the $2^{(n+1)/2}$ messages submitted, the attacker playing the distinguishing game announces that the oracle is a random function; else announces that the oracle is CBC-MAC. This works because the messages submitted differ only in their first block, thus will never collide under CBC-MAC, ...


5

I think of it this way: think of a distinguisher as an adversarially-chosen statistical experiment that attempts to support or refute some hypothesis, that again is adversarially selected. This means that the honest party doesn't get to assume what meaning the adversary assigns to $0$ or $1$; their PRG has to behave like a random distribution no matter what ...


5

What we call "statistical distance" in cryptography is called total variation distance by statisticians. So it certainly exists outside of cryptography. I can't speak to its applications within statistics. But it certainly is the most natural metric for cryptography because it has an equivalent formulation in terms of distinguishing two source ...


4

Why the CFS signature is affected Let us review the structure of the CFS signature, which is strongly related to the Niederreiter PKE scheme. In the Niederreiter PKE scheme, a public key is $H \in \mathbb{F}^{n \times k}$, which is a scrambled parity-check matrix of the Goppa codes. A plaintext is a decodable error; for example, we set $S = \{\vec{e} \in \...


4

See Vitor's answer for the answer your professor was looking for. However, for any PRNG of the form $s_{i+1} = F(s_{i})$, where the attacker sees the $s_i$ values, and knows $F$, then he can distinguish it. Given a sequence of values $r_1, r_2, ...$, he can determine whether it was generated by that PRNG by checking if $r_2 = F(r_1)$; this is always true ...


4

Another way to see this would be to try and upper bound the distinguishing advantage for any distinguisher and relate that to the statistical distance. Edit: Since the following answer is really good, I will just give ideas without proofs. Was supposed to be : Since @Mikero's answer is really good... What happens when you answer late and do not ...


4

What I don’t get is why the complexity became quadratic in linear case? Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that bias is $0.5 + \epsilon$ or whether it is $0.5 - \epsilon$ If we were to query a random bit (that is, one with no bias) $n$ times and sum the results, we're ...


4

I'll leave alone the OpenPGP spec, and consider the problem of identifying among $k$ public keys $(n_i,e_i)$ the RSA public key $(n_j,e_j)$ used to encrypt $m$ messages per RSA with proper encryption padding. The only way is by examining the $m$ cryptograms $c_\ell$, which essentially are indistinguishable from uniformly random in $[0,n_j)$ (I assume the $c_\...


3

Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bitlength is polynomial in the security parameter), and thus allowing the distinguisher to decrypt? This is up to your security ...


3

If $(X \approx X')$ and $(Y \approx Y')$, then it holds that $(X \times Y) \approx (X' \times Y')$. Indeed, let us consider an adversary which is able to distinguish $(X \times Y)$ from $(X' \times Y')$ with probability $1/2+\varepsilon$; the adversary returns $0$ if he estimates that the sample comes from $(X' \times Y')$, and $1$ else. Indeed, let us ...


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

I think abstractly, it implies that the attacker understands something about the structure of the cipher, and the fear is that with that knowledge, something of the plaintext or key could be known. Much of this comes first from Shannon's proof of perfect security--having all the ciphertext in the world did not help you one wit to guess anything about the ...


3

First off, your definition is not IND-CPA: In the IND-CPA setting, the adversary has access to an encryption oracle. As you have already determined, no deterministic encryption scheme can be IND-CPA secure. I don't think IND-CPA is widely used for symmetric encryption though (although I might be wrong), semantic security might be a better option. For public ...


3

Your idea for constructing a distinguisher from a predictor is fine, assuming you know that the predictor predicts the last bit. The more general statement is: if you can predict any bit of the output, say the $i$th bit, given the first $i-1$ bits, then you can also build a distinguisher. A similar idea to what you showed also works to prove this statement....


3

Such reductions I know are the reductions in hardcore predicates/functions from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, the reductions in (provably-secure) PRGs/PRFs from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, and the reductions in LPN/LWE. Re: Can you be more specific? I.e: ...


3

He's doing a pretty poor job of expressing a very simple idea here, which is that if there exists a distinguisher $D$ for which $Pr\lbrack D(H^{i-1})=1\rbrack$ > $Pr\lbrack D(H^{i})=1\rbrack$ (which means the advantage is negative before taking the absolute value), there also exists a distinguisher $\overline{D}$ for which $Pr\lbrack D(H^{i})=1\rbrack$ > $Pr\...


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