32
votes
Accepted
A website that identifies an RNG from its output
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 ...
29
votes
A website that identifies an RNG from its output
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 ...
23
votes
Accepted
Distinguishing x25519 public keys from random?
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 + ...
11
votes
Accepted
Statistical closeness implies computational indistinguishability
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 ...
9
votes
Accepted
Is this simple PRNG secure?
$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 ...
7
votes
Accepted
Hashing a counter to prevent distinguishers in CTR mode
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 ...
6
votes
Definition of a distinguisher
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 ...
6
votes
Accepted
Are two outputs of a PRF computationally indistinguishable when using two different keys?
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 ...
5
votes
Accepted
Is there only one formula for the statistical difference between a pair of distribution ensembles?
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 ...
4
votes
Is this simple PRNG secure?
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 ...
4
votes
Statistical closeness implies computational indistinguishability
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 ...
4
votes
Accepted
Why the differential cryptanalysis complexity is linear with inverse of the probability while linear cryptanalysis is quadratic with the bias inverse?
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 ...
4
votes
How many encryptions are needed before OpenPGP key privacy is violated?
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 ...
3
votes
Accepted
Distinguishing between a Polynomial and a Laurent Polynomial
Is this possible
Unless querying $g(0)$ gives you a distinguishable error for a Laurent polynomial, and assuming that the values $a_0, …, a_d$ are equidistributed (for both the Laurent and normal ...
3
votes
Accepted
Probability distribution of bitwise-&
Not very. A few lines of code produces this for a & b with both variables uniformly distributed across $2^8$:-
I don't think that it has a specific ...
3
votes
Accepted
A confusion on the proof of Yao's theorem (Yao 82)
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 ...
3
votes
Does concatenation of two pair computational indistinguishable distributions still indistinguishable?
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')...
3
votes
Accepted
why do we take computational distinguishability over ensembles
Why not just define it over two distributions $X$ and $Y$?
Because this is an asymptotic definition (using a negligible function explicitly).
If you were to only consider two fixed distributions, ...
3
votes
Accepted
Given an input x, can a distinguisher D output 1/2?
Such a distinguisher is certainly valid. In fact, in many proofs of security, we use this strategy. In particular, assume that there is some event that can be detected by $D$ with some non-negligible ...
3
votes
How to distinguish X25519 output from random?
Alice generates several $X_* = \operatorname{X25519}(S_*,P_*)$.
If Alice uses the X25519 function, the output will belong to $\mathbb{F_{2^{255}-19}}$ and will represent a $X$-coordinate of a point ...
2
votes
Accepted
Distinguishing two sets of pseudorandom values when their keys differ by one
Question: Are the set of $w_i$ values are computationally indistinguishable from the set of $q_i$ values?
No, that is not guaranteed by standard security notions.
AES for example is considered a ...
2
votes
Accepted
Can an adversary distinguish a private key from a pseudo-random string of the same length?
Usually choosing a safe password and standard parameter for the PBKDF2 key derivation would be enough protect your cipher. If PBKDF2 is correctly used, the symmetric key you get as output is well ...
2
votes
Can an adversary distinguish a private key from a pseudo-random string of the same length?
To basically summarize Ricky Demer's answer, regardless of how "random-looking" your private key is, an attacker can always recognize the correct private key as long as they have access to at least ...
2
votes
Accepted
Computationaly efficient distinguisher for a PRP generator
a distinguisher is possible with 3 queries if we disregard efficiency. But how can we build an efficient distinguisher?
I'm not sure exactly what you mean by efficient (since $n \approx 2^{27}$ is a ...
2
votes
Accepted
Are two outputs of a PRF computationally indistinguishable when the keys are somehow related?
They are indistinguishable because the keys are related only by a value that random from the distinguisher's point of view. More formally, you can argue that your distribution is indistinguishable ...
2
votes
Accepted
Is there distinguisher?
It looks like you're asking the following:
Consider the following families of distributions over functions from $\{0,1\}^{n} \to \{0,1\}^{n}$:
$\{X_n\}, \text{ where } X_n \text{ is the uniform ...
2
votes
Proving a function is or is not a pseudorandom function F_k(x) = F_k(x)||0
You have shown a distinguisher for $F^1$ with high advantage that does not involve a distinguisher for $F$, so you can conclude there must be an error in your argument that that any distinguisher for $...
2
votes
Example of not computationally indistinguishable
The usual way of proving that two distributions are distinguishable is by devising an attack such as the one you mentioned. Finding an attack may not be easy or even doable. In general, you should ...
2
votes
Accepted
In SKE, can we assume without loss that the ciphers of a fixed plaintext distribute identically?
Is this possible without using any cryptographic assumptions which don't already follow from the existence of an IND-CCA1 secure SKE?
Yes, symmetric-key encryption implies the existence of "...
2
votes
Distinguishers and next bit predictors without the uniform distribution
Nice question!
This seems to have been addressed in a conference paper also available here by Schrift and Shamir in 1991:
A.W. Schrift, A. Shamir, On the universality of the next bit test,
Conference ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
distinguisher × 84provable-security × 15
pseudo-random-generator × 12
pseudo-random-function × 8
cryptanalysis × 7
diffie-hellman × 6
indistinguishability × 6
pseudo-random-permutation × 4
probability × 4
encryption × 3
hash × 3
rsa × 3
aes × 3
block-cipher × 3
zero-knowledge-proofs × 3
random-number-generator × 3
stream-cipher × 3
public-key × 2
elliptic-curves × 2
symmetric × 2
discrete-logarithm × 2
multiparty-computation × 2
terminology × 2
cbc-mac × 2
rc4 × 2