Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
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 ...
SEJPM's user avatar
  • 46.1k
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 ...
ChrisInEdmonton's user avatar
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 + ...
Samuel Neves's user avatar
  • 12.6k
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 ...
Mikero's user avatar
  • 13.4k
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 ...
Hilder Vitor Lima Pereira's user avatar
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 ...
fgrieu's user avatar
  • 142k
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 ...
Luis Casillas's user avatar
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 ...
tylo's user avatar
  • 12.7k
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 ...
Mikero's user avatar
  • 13.4k
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 ...
poncho's user avatar
  • 148k
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 ...
Marc Ilunga's user avatar
  • 3,288
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 ...
poncho's user avatar
  • 148k
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 ...
fgrieu's user avatar
  • 142k
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 ...
poncho's user avatar
  • 148k
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 ...
Paul Uszak's user avatar
  • 15.5k
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 ...
pg1989's user avatar
  • 4,646
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')...
Geoffroy Couteau's user avatar
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, ...
SEJPM's user avatar
  • 46.1k
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 ...
Yehuda Lindell's user avatar
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 ...
Ruggero's user avatar
  • 7,104
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 ...
ddddavidee's user avatar
  • 3,334
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 ...
Ilmari Karonen's user avatar
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 ...
Mikero's user avatar
  • 13.4k
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 ...
Mikero's user avatar
  • 13.4k
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 ...
lkowalcz's user avatar
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 $...
Squeamish Ossifrage's user avatar
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 ...
hlz2103's user avatar
  • 369
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 "...
Mikero's user avatar
  • 13.4k
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 ...
kodlu's user avatar
  • 22.6k
2 votes
Accepted

Computing the advantage when checking PRF

The definition of the distinguishing advantage is a (pseudo)metric that captures the performance of some distinguished $D$ in distinguishing two experiments, say $E_0$ and $E_1$. The larger the value, ...
Marc Ilunga's user avatar
  • 3,288

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