21

First of all, the output of SHA-256 is binary and consists of 32 bytes (256 denotes the output size in bits). What you are talking about is apparently the hexadecimal encoding of these bytes. The possibility that you are talking about is called (1st) pre-image resistance (Wikipedia): Given a hash value $h$, it should be difficult to find any message $m$ ...


15

Yes, it's possible. Given the size of the input space (not actually infinite, but still very, very large), it's also likely, for any given 256-bit value, that several inputs that hash to that value exist. No, there's nothing special in the construction of the algorithm that prevents it (restricting the output space would probably be bad for security). ...


10

The obvious way to do this is to generate N words, and use logical operations to combine them in a single word such that each bit of the output word is a 1 with probability approximately 0.1 (and the individual bits are uncorrelated). In the simplest case, you could generate 3 words, and just AND them together into a single one. In C, this would be: ...


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


6

But would that also be possible practically, or do the algorithms check that this is not happening? This is practically beyond anybody to find a 32-$a$'s for SHA-256 without pure luck or one need breaking the pre-image resistance of SHA-256, that is not possible. Is it possible that a SHA256 hash has the same character 64 times? Yes, and No. We don't know ...


5

In short, with this multiplicative definition, it could be ruled out the possibility that an individual's record would be randomly selected and published. Consider a malicious algorithm $M^*$ that picks a random individual's record from the input database (of size $n$) and outputs it. Note that this $M^*$ should not be considered secure for a good ...


5

As usual, choosing the security parameters represents a tradeoff between the security and the efficiency. Therefore, it also strongly depends on two things: how crucial it is that no one breaks the security guarantee (if an adversary succeeds at "guessing correctly" the challenge, hence can break soundness, how dangerous is that? How strong is the incentive ...


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


5

This section talks about Fortuna, where it uses a block cipher with a 128-bit block and a 256-bit key size. The cipher is used in CTR mode. In the CTR mode, if an attacker can access the internal state than then the security is lost ( the key and current counter value), therefore after a request, 2 new blocks are generated and used as a new key, and the old ...


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

But this notation is defined (informally) in the first paper. The notation $O(\nu(n))$ is used for any function, $f(n)$, that vanishes faster than the inverse of any polynomial, that is for every polynomial, $\mathrm{poly} (n)$, and $n$ large enough, $f(n) \leq 1/\mathrm{poly}(n)$ Therefore, what it means is no probabilistic polynomial time (PPT) algorithm ...


4

The three equations you reference are (we'll just take them as truth - their proof can be found in the PDF): $$ \begin{align} |Pr[S_0] - Pr[S_1]| & = \epsilon_{\text{ddh}} & \text{ (1)} \\ |Pr[S_1] - Pr[S_2]| & = \epsilon_{\text{es}} & \text{ (2)} \\ Pr[S_2] & = \frac{1}{2} & \text{ (3)} \\ \end{align} $$ Then: $$ \begin{align} \...


3

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space? No. If you consider EdDSA verification a legitimate signer can generate more than one signature of a given message, and all will pass EdDSA verification. However, only the signature generated with the EdDSA signing ...


3

If $m$ divides $N$, then you get the uniform distribution over $[m].$ Let $k=N-\lfloor N/m \rfloor m.$ Note that $k\geq 0,$ with $k>0,$ if $m$ does not divide $N.$ When you reduce $Z$ modulo $m$, due to wraparound, the smallest $k$ values $0,1,\ldots,k-1$ are "hit" an extra time, as $Z$ varies from $0$ to $N-1.$ Thus the probability distribution of $W=Z \...


3

No, you cannot prove that, since it is not generally true. Consider the following counter example. Let $X$ be a distribution over $\{0,1\}$ with $$\Pr_{b\gets X}[b=0] = \Pr_{b\gets X}[b=1]=\frac{1}{2}.$$ Let $f,g,h : \{0,1\} \to \{0,1\}$ be defined as $$f : b \mapsto b,\quad g : b \mapsto b, \quad \text{and} \quad h : b \mapsto b\oplus 1.$$ The statistical ...


3

No, it means that the functions are chosen from some domain with some probability distribution. This is standard for randomized algorithms. For simplicity, assume there are $N$ randomized functions $\mathcal{K}$ possible, and one choose one uniformly with probability $1/N.$ For example, if we restricted ourselves to polynomials of degree $\leq k$ over $...


3

If I wanted to create a TOTP-esque algorithm that generated a string n characters long, with each character being a base64 character, generated from a user secret r Base64 characters long, every s seconds, for each of u number of users, where the probability of collision is very small, how would I calculate the length of the string that was needed? Well, ...


3

Caveat: that answer is written with my mind in Vulcan mode. That is, I'm answering the question as taken literally (in the first part); or in only a minor variant (second part); and ignoring the question's title, which I find unrelated, especially given the limited span of $n$. The probability considered is $0$ for each of the many different common ways to ...


3

In cryptography the notation of $x\stackrel{\\\$}{\gets}S$ (also sometimes seen as $x\gets_{\\\$}S$) means that $x$ is chosen uniformly at random from the set $S$. If an algorithm is on the right side of the $\stackrel{\\\$}{\gets}$ then it typically means that the algorithm is invoked and may use randomness, for algorithms the $\\\$$ is also sometimes ...


2

We are given two plaintext/ciphertext pairs $(P_1, C_1)$ and $(P_2, C_2)$ with $E_{k_1^*}(P_i) = D_{k_2^*}(C_i)$ where the true key is $k^* = (k_1^*, k_2^*)$. Suppose the cipher key is $n$ bits long, and the block is $b$ bits long. (Schneier uses $m$ for the block size, but as a confusion of minims I cannot keep these letters straight, so I will use the ...


2

In the sentence, the "probability of success" of «1 in $2^{2m - 2n}$» or «1 in $2^{3m - 2n}$» really is an approximation of the probability of concluding that the key was found, when in fact another key that happens to give the same result as the true key for 2 or 3 blocks was found. It should be read "probability of wrongly concluding success" instead; or "...


2

The point $u$ here means that instead of sampling a point from the lattice $\Lambda$, you're sampling a point from the coset of the lattice $u + \Lambda$. This is a "shifted copy" of the lattice (shifted by precisely $u$). Generically though, you're looking for tail bounds of gaussian mass on lattices. You can find these a variety of places in the ...


2

The probability becomes more intuitive when one pictures the $t$ persons entering one by one in the room. Before the first person enters, there's no collision/coincidence of birth-date, thus probability of no collision is $P_0=1$. When the first person enters, there can't be a collision/coincidence of birthdate, probability of no collision is $P_1=1$. ...


2

My first understanding was yes, but in fact, it depends. First understanding: You can view them as IID, unless you have some knowledge about the secret $s$ and enough other variables. Take for example a Shamir Secret, a simpler secret sharing scheme which is a special case of this. A Shamir secret allows to reconstruct $s$ with any set of $k$ parts from $n$ ...


2

I'll try to show the probability that the matrix has rank equal to $n$. Two important facts, since $\mathbb{Z}_p$ is a field and not just a ring: Each column of the matrix can be considered as a random vector drawn from a set of an $n$-dimensional vector space over $\mathbb{Z}_p$, which has $p^n$ vectors. The number of vectors in a $k$-dimensional subspace ...


2

What exactly is an $n$‑bit number? In the context, number designates an element $m$ of the set $\mathbb N$, the non-negative integers. Such $m$ is $n$‑bit if and only if $n\in\mathbb N$ and $\lfloor2^{n-1}\rfloor\le m<2^n$, or equivalently $n=\left\lceil\log_2(m+1)\right\rceil$. When $n\ne0$, that simplifies to $2^{n-1}\le m<2^n$, or equivalently $n=\...


2

You are approximately correct; they are wrong. Their answer calculates the chance of matching a particular value i.e. hash inversion. To see this $k$ tries have a $(2047/2048)^k$ of failing to find a match so you want $k>\log(0.5)/\log(2047/2048)$. For small numbers we can calculate the exact value of the birthday bound by finding the smallest $k$ such ...


2

So, the full analysis for random trials is that the initial probability of a hit is $p_0=k/n$ and $k=10,$ and $n=1000$ for your case. Define the number of trials until the first hit as $N_0$ which is a geometric random variable with expectation $$ \mathbb{E}(N_0)=p_0^{-1}=\frac{n}{k}. $$ This is indeed 100 as you guessed. If you wanted to find 2 codes your ...


2

No. The birthday paradox applies to all image spaces. Randomly evaluating any function with large input space and an image space of size $2^{n/2}$ is expected to produce a collision after roughly $2^{n/4}$ evaluations.


2

In the Gaussian mechanism case, it is important to distinguish the use of $\epsilon$ to parameterise the Gaussian distribution and its use to quantify the level of differential privacy. For any $0<\epsilon<1$ and $0<\delta<1$ we can construct the mechanism which adds noise distributed $$\mathcal N(0,2\log(5/4\delta)(\Delta f)^2/\epsilon^2)$$ and ...


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