Analysis of DGHV Security I want to know how security of DGHV can be breached using oracle and Binary GCD. As I study this paper : Fully Homomorphic Encryption over the Integers But I am not able to understand Section 4.1:

  Theorem 4.2.
  Fix the parameters (ρ, ρ′, η, γ, τ) as in the Somewhat Homomorphic Scheme from Section 3 (all polynomial in the security parameter λ).

  Any attack A with advantage ε on the encryption scheme can be converted into an algorithm B for solving ( ρ, η, γ ) -approximate-gcd with success probability at least ε/2. The running time of B is polynomial in the running time of A, and in λ and 1/ǫ.

I also can't understand the Subroutine Learn-LSB(z,pk) and the Binary GCD following it.

Basically, this part of the paper aims at proving that, as long as the approximate GCD problem is hard, the DGHV scheme is "secure". So, as it is standard in reduction proofs, you go and prove the contrapositive: you show that if there exists an adversary $\mathcal{A}$ that is able to break the DGHV scheme, then there exist an adversary $\mathcal{B}$ that uses $\mathcal{A}$ to break the approximate GCD problem. For more information on reduction proof and how they work, I recommend this video.

The outline of the proof is as follows: first, the authors exhibit the Learn-LSB routine, in which $\mathcal{B}$ uses $\mathcal{A}$ to learn the leats significant bit of the secret key. This corresponds to step 2 in the paper. Then (step 3 and 4), the authors show that, using this Learn-LSB, it is possible for $\mathcal{B}$ to fully recover the secret key $p$, which also means breaking the approximate GCD problem.

Concerning the Learn-LSB routine (step 2 of the proof)

Here, $\mathcal{B}$ uses $\mathcal{A}$ in a black-box manner to find the least significant bit of the secret key $p$, assuming that when $\mathcal{A}$ is fed with a ciphertext, it returns the corresponding plaintext. The subroutine LearnLSB takes some number $z$ and a public key $pk$ as input. It should output the least significant bit of the quotient of $z$ by $p$, noted $[q_p(z)]_2$ in the paper.

EDIT: note that $\mathcal{A}$ and $\mathcal{B}$ are sorts of imaginary adversaries. Thought experiments, I you will. It is actually impossible to realize the Learn-LSB subroutine (or at least, all crypto experts agree that it is impossible). We are using them only to show that, IF there exists $\mathcal{A}$ able to break DGHV, THEN we can construct $\mathcal{B}$ that breaks approximate GCD problem (and in passing, that realizes the Learn-LSB oracle). YET we know that approximate GCD is hard. We reach a contradiction: therefore $\mathcal{A}$ can not exist. See the video linked above on this reasoning.

Let's look at what happens in one turn of the loop. In lines 2 and 3 of the subroutine, $\mathcal{B}$ creates a rigged ciphertext $c_j$ for the public key $pk$, which it feeds to $\mathcal{A}$ at line 4. $\mathcal{A}$ should return its guess on the plaintext that is inside $c_j$. $\mathcal{B}$ is not directly interested in the plaintext itself, but a function of it (see line 5). The trick is in how $c_j$ is rigged: notice (on line 3) that $c_j$ is a standard ciphertext, except that $z$ was added to $m_j + 2r_j +2\sum x_k$. So instead of $c_j$ being an encryption of $m_j$ it is actually an encryption of a combination of $z$ and $m_j$: specifically, of $[r_p(z)]_2 \oplus m_j$  where $r_p(z) = z \bmod p$. To understand why, see that the decryption of $c_j$ will give (if we simplify, and under some assumption of the form of $z$, which the authors detail in section 4.1.1):
$$\begin{align}
\mathsf{Dec}(sk = p, c_j) &= \left[ \left[ [z+m_j+2r_j+2\sum x_k]_{x_0} \right]_p \right]_2 \\
&\approx \left[ \left[ [ q_p(z) \cdot p + r_p(z) +m_j+2r_j+2\sum x_k]_{x_0} \right]_p \right]_2 \\
&\approx \left[ r_p(z) +m_j + 2r_j+2\sum x_k \right]_2 \\
&= [r_p(z) + m_j]_2 = [r_p(z)]_2 \oplus m_j \\
\end{align}$$

Therefore, coming back to what $\mathcal{A}$'s guess, on line 4, $a_j$ should be equal to $[r_p(z)]_2 \oplus m_j$. However, remember that we want $[q_p(z)]_2$ and not $[r_p(z)]_2$. But as the authors note $[q_p(z)]_2 = [r_p(z)]_2 \oplus parity(z)$, where $parity(z) = 0$ when $z$ is even, and $1$ otherwise. What this small relation says is that, when $z$ is even, then $[q_p(z)]_2 = [r_p(z)]_2$ ; and when $z$ is odd, then $[q_p(z)]_2 \neq [r_p(z)]_2$. Convince yourself by looking at all possibilities for the parities of $[q_p(z)]_2$ and $[r_p(z)]_2$, knowing that $z = [r_p(z)]_2 \cdot p[r_p(z)]_2$ and $p$ is odd.

At last, we can understand line 5, in which $\mathcal{B}$ translates $\mathcal{A}$'s guess on the rigged ciphertext $c_j$ into $[q_p(z)]_2$ by computing $a_j \oplus parity(z) \oplus m_j$

The whole process is repeated a several times because errors might appears (notably, $c_j$ may not be well formed), and the majority of votes is returned.

Concerning the Binary GCD (step 3)

Now, with the Learn-LSB subroutine, the authors run a special version of the binary GCD algorithm on $z_1$ and $z_2$ near-multiples of $p$, and are able to obtain $z = q \cdot p + r$, where $q$ is the odd part of $GCD(q_p(z_1), q_p(z_2))$.

The binary gcd algorithm is not complex in itself. Only, here, the authors run an algorithm on $z_1$ and $z_2$ in appearance, but the actual GCD is computed on $q_p(z_2)$ and $q_p(z_2)$. The Learn-LSB subroutine is useful to know, given $z_1$ and $z_2$, whether $q_p(z_1)$ and/or $q_p(z_2)$ are odd or not. Indeed, the binary GCD algorithm on some number $a$ and $b$ needs to make decision based on the parity of $a$ and $b$.

Finding the secret key p (last step)

At last, using these tools, it is possible to recover $p$ by a final twist. First, $\mathcal{B}$ takes two near-multiples of $p$, $z_1^*, z_2^*$, and runs the above algorithm on them. The result is: a number $\bar{z} = q \cdot p + r$ where $q$ is the odd part of $GCD(q_p(z_1^*), q_p(z_2^*))$. If $q \neq 1$, $\mathcal{B}$ begins again with new $z_1^*$ and $z_2^*$ ($\mathcal{B}$ can check whether $q = 1$ later actually).

Next, perform the above binary GCD with $z_1^*$ and $\bar{z}$. And magically, the bit-decomposition of $q_p(z_1^*)$ appears during the iteration of the algorithm. That is, at iteration $i$, $b_1$ (of line 2 of the paper's binary-GCD) gives the $i$ least significant bit of $q_p(z_1^*)$. Maybe the best way to see how/why is by running (by hand) the algorithm with small parameters, such as $p = 23$, $z_1^* = 11 \cdot p + 2$ and $\bar{z} = p + 1$. It finishes in 4 steps, yielding in order $b_1 = 1, 1, 0, 1$, and $(1011)_2$ is $11$ (Remember that the authors define that all remainders are $r_p(z)\in (−p/2, p/2]$)

Last step: now that you know $q_p(z_1^*)$, do $z_1^*/q_p(z_1^*) = p + r_p(z_1^*)/q_p(z_1^*)$. Round the result and you obtain $p$, since $r_p(z_1^*)$ is (normally) much smaller than $q_p(z_1^*)$.

Wrap-up

So $\mathcal{B}$ started with access to samples of $\mathcal{D}_{\gamma,\rho}(p)$ giving near-multiples of $p$, and found $p$. Thus, it broke the approximate GCD problem. Yet, the approximate GCD problem is deemed hard and assumed unbreakable: we reach a contradiction. Thus, the DGHV scheme is secure !

Note: the answer, although very long already, purposely ignores many important elements, such as the size of some elements and possible wrap-around in moduli computation.


Is calculating a hash code for a large file in parallel less secure than doing it sequentially? I would like to improve the performance of hashing large files, say for example in the tens of gigabytes in size.

Normally, you sequentially hash the bytes of the files using a hash function (say, for example SHA-256, although I will most likely use Skein, so hashing will be slower when compared to the time it takes to read the file from a [fast] SSD). Let's call this Method 1.

The idea is to hash multiple 1 MB blocks of the file in parallel on 8 CPUs and then hash the concatenated hashes into a single final hash. Let's call this Method 2, show below:

I would like to know if this idea is sound and how much "security" is lost (in terms of collisions being more probable) vs doing a single hash over the span of the entire file.

For example:

Let's use the SHA-256 variant of SHA-2 and set the file size to 2^35=34,359,738,368 bytes. Therefore, using a simple single pass (Method 1), I would get a 256-bit hash for the entire file.

Compare this with:

Using the parallel hashing (i.e., Method 2), I would break the file into 32,768 blocks of 1 MB, hash those blocks using SHA-256 into 32,768 hashes of 256 bits (32 bytes), concatenate the hashes and do a final hash of the resultant concatenated 1,048,576 byte data set to get my final 256-bit hash for the entire file.

Is Method 2 any less secure than Method 1, in terms of collisions being more possible and/or probable? Perhaps I should rephrase this question as: Does Method 2 make it easier for an attacker to create a file that hashes to the same hash value as the original file, except of course for the trivial fact that a brute force attack would be cheaper since the hash can be calculated in parallel on N cpus?

Update: I have just discovered that my construction in Method 2 is very similar to the notion of a hash list. However the Wikipedia article referenced by the link in the preceding sentence does not go into detail about a hash list's superiority or inferiority with regard to the chance of collisions as compared to Method 1, a plain old hashing of the file, when only the top hash of the hash list is used.

If you want to use Skein (one of the SHA-3 candidates) anyway: it has a "mode of operation" (configuration variant) for tree hashing, which works just like your method 2.

It does this internally of the operation, as multiple calls of UBI on the individual blocks. This is described in section 3.5.6 of the Skein specification paper (version 1.3).

You will need a leaf-size of 1 MB (so, Y_l = 14, for the 512-bit variant, 15 for 256, 13 for 1024) and a maximum tree height Y_m = 2 for your application. (The image shows an example with Y_m >= 3.)

The paper does not really include any cryptographic analysis of the tree hashing mode, but the fact that it is included (and even mentioned as a possible use for password hashing) seems to mean that the authors consider it at least as save as the "standard" sequential mode. (It is also not mentioned at all in the proof paper.)

On a more theoretical level:
Most ways of finding collisions in hash functions rely on finding a collision in the underlying compression function f : S × M -> S (which maps a previous state together with a block of data to the new state).

A collision here is one of these:

a pair of messages and a state such that f(s, m1) = f(s, m2)
a pair of two states, a message block, so that f(s1, m) = f(s2, m)
a pair of messages and a pair of states such that f(s1, m1) = f(s2, m2).

The first one is the easiest one to exploit - simply modify one block of your message, and let all the other blocks same.

To use the other ones, we additionally need a preimage attack on the compression function for the previous blocks, which is usually thought to be even more complicated.

If we have a collision of this first type, we can exploit it in the tree version just as well as in the sequential version, namely on the lowest level. For creating collisions on the higher levels, we again need preimage attacks on the lower levels.

So, as long as the hash function (and its compression function) is preimage resistant, the tree version has not more collision weak points than the "long stream" one.


Does adding complexity mean a more secure cipher? I have a cryptography workshop question I'm having trouble with as follows;

Person A creates a cipher $E_k(m)$ which produces a ciphertext from message $m$ using key $k$. The function inside $E$ is kept secret but the length of $E_k(m)$ is known.

Person B recommends "increasing" security of the cipher by instead doing :

$(E_k(m) \oplus m)\ ||\ (E_k(m) \oplus 1111...11)$

Does this in fact increase security of the cipher or increase new problems.

My thinking is, depending on the function within $E$, xoring the output of the cipher with the plaintext message $m$ could expose the key $k$, meaning the extra complexity is for nothing. Am I on the right track, or am I missing something?

I have tried searching for examples of similar schemes and found nothing (which probably means it's not a good scheme) but I need to justify my answer.

Any steers in the right direction would be greatly appreciated, I'm more than happy to do the research myself just unsure what specifically to look for.

Unfortunately the above context is all I have been provided for this question.

xoring the output of the cipher with the plaintext message

Xoring the message into the ciphertext removes the ability to decrypt the ciphertext.

If all you have is $k, c = E_k(m) \oplus m$, then you need to know $m$ in order to strip the external $m$ off of $E_k(m)$ before you can apply $m = D_k(E_k(m))$; Basically, you would need to know the message in order to "decrypt" the message, but since you already know the message, then there would be no knowledge gained from "decrypting".

$(E_k(m)\oplus m)||(E_k(m) \oplus 1111...11)$

The previous section was striked out, because there was more to the suggestion than simply xoring the message into the ciphertext.

In fact, the complete suggestion is far, far worse then simply implying the inability to decrypt a ciphertext: Anyone can decrypt a ciphertext from this scheme without requiring the key.

$$c = (E_k(m) \oplus m) || E_k(m) \oplus 1111\dots 11)\\c_{\text{a}} = E_k(m) \oplus m\\c_{\text{b}} = E_k(m) \oplus 1111 \dots 11\\c' = c_{\text{b}} \oplus 1111\dots11\\m = c_{\text{a}} \oplus c'$$

The value $1111\dots11$ is known to all, so anyone can compute $$E_k(m) = E_k(m) \oplus 1111\dots11 \oplus 1111\dots11$$

So $E_k(m)$ is effectively public knowledge, so again anyone can compute $$m = E_k(m) \oplus m \oplus E_k(m)$$

This scheme is completely broken.

  I have tried searching for examples of similar schemes and found nothing (which probably means it's not a good scheme) but I need to justify my answer.

See the previous section - "encryption" is an invertible process: You have to be able to undo the transformation so that you can retrieve the plaintext from any given ciphertext.

It is completely broken, so you won't find anything similar to it (other than situations where people asked this same question and found it to be broken)

  Does this in fact increase security of the cipher or increase new problems.

It's a lot easier to determine whether or not doing x or y will increase/decrease security once you have a clear goal of what it means to be secure. This is a context dependent notion.

It helps to list:

What you have
What your adversary can do
What you want to accomplish (in very specific terms).

If you don't know where to start, then look for the standard notions of security that cryptographers have already worked out for the context of interest (e.g. indistinguishability for ciphers)


How to test implementation of primality tests like Miller–Rabin? The Miller-Rabin primality test is an algorithm for checking if number is a prime. What would be best way to test implementation of such algorithm (or any primality test in general)?

Well, the obvious thing to do is give it a long list of integers of known primality, and see whether the algorithm reports it correctly (with it occasionally reporting a composite as "relatively-prime" not being counted as an error, as long as it reports that value as composite at least 75% of the time).

However, that simple-minded test might miss something.  The Miller-Rabin test can report $n$ is "composite" because of one of two reasons:

Because $g^{n-1} \ne 1 \bmod n$; that is, the Fermat test fails
Because $g^{(n-1)/2^\ell} \bmod n$ is a nontrivial squareroot of 1

If you just throw random composites $n$ at it, then it'll run into the first reason almost all the time.  Hence, it makes sense to deliberately try a value $n$ that fails for the second reason.

One set of values $n$ are known as Carmichael numbers; these are composites with $g^{n-1} = 1 \bmod n$ for all integers $g$ relatively prime to $n$; if we test a Carmichael number with no small factors, the Fermat test will almost always succeed, and so if the test fails, it'll be be the second reason.

One way of finding such Carmichael numbers is to search for prime triplets $6p+1, 12p+1, 18p+1$; if all three are prime, then $(6p+1)(12p+1)(18p+1)$ is a Carmichael number.


Does the Richard Sorge cipher still provide good security? Is the cipher used by soviet spy Richard Sorge still sufficiently secure nowadays?

Short Answer: No
But it depends on what you mean by good. If pretty lousy by modern standards is your idea of good enough, and you want to use it on your little brother, then this cipher may exceed expectations. Sorge's cipher was powerful in its day.  However, it is not a one-time pad; that is, it never offered perfect security. The Sorge cipher is not a modern cipher, and almost no one would ever use it because it depends on the obfuscation of the key, and security by obfuscation is anathema to modern cryptography.
What is the Sorge Cipher?
In The Codebreakers (Macmillan, 1967, p. 650), David Kahn points out that the Sorge cipher was regarded as unbreakable, a triumph of cryptography.  It was a mainstay of Soviet espionage during their days of stunning successes.  Richard Sorge has been described as the best spy who ever lived, his work impeccable.
No one that we know of ever broke it while it was being used.  Kahn says, "it remained hermetically sealed against cryptanalysis."

It brought the old Nihilist substitution to a peak of perfection. It
merged the straddling checkerboard with the one-time key.

A Straddling Checkerboard

The innovation of the Sorge cipher was to assign the highest-frequency letters of the English alphabet (yes, communications were in English) to single numerals in the straddling checkerboard.  The phrase "a sin to er(r)" gives us the seven most commonly used English letters: A, E, I, N, O, R, S.  Matching these to single digits helped flatten the distribution of letters and shorten the messages, which made radio transmission faster and thus safer.
The Sorge cipher's straddling checkerboard was not partly alphabetical, as seen in the example above.  It was made with a keyword in such a way as to muddle the order of the letters.

Clausen [Sorge's radio operator] used SUBWAY. The encipherer wrote
this out, followed by the rest of the alphabet in rows beneath it,
with a full stop and a letter-number switch sign at the end. Then the
digits 0 to 7 were assigned to ASINTOER as they occurred vertically
in columns from left to right. Finally the two-digit groups from 80 to
99 were assigned to the remaining letters and symbols, also
vertically:

Which results in this checkerboard (Kahn, p. 651):

Which gives this fractionation to the plaintext (Where is 106 Division):

Now for encryption with a one-time numerical key from a book
The key was chosen "randomly" in Moscow from a book about railroad construction in Luxembourg in 1931. Where one started in the tables of statistics had already been agreed upon. Non-carrying addition produced the ciphertext.
There are many obscure books.  Every book on our planet has not been scanned yet.  Would such a key provide "good" security?  Probably not, and its strength is certainly nowhere near perfect or anything resembling the strength of modern encryption.  This cipher method depends on obscurity, which is a critical mistake.


ElGamal signature - show that $(\gamma, \delta)$ signs $m$ We have as a given: $gcd(j, p − 1) = 1$.

$$γ = \alpha^i \beta^j \bmod p $$
$$ \delta = −\gamma j^{-1} \bmod (p−1) $$
$$m = i \delta \bmod (p − 1)$$

I want to show that $(\gamma; \delta)$ is an ElGamal signature for message $m$.

In this book, they show an example:

How can I take the proof that $(\gamma, \delta)$ signs $m$?

A valid ElGamal signature satisfies, in the notation from the book you posted:

$$\beta^\gamma \gamma^\delta = \alpha^m \bmod p$$

That's just the definition of an ElGamal signature. The snippet you posted is not an example, but precisely the proof that $(\gamma, \delta)$ is a valid signature of $m = i \delta \bmod (p-1)$. On page 68 of the book, it says

  ($\gamma, \delta$) este o semnatura valida pentru x. Intr-adevar, se verifica...

(In English: "$(\gamma,\delta)$ is a valid signature for $x$. Indeed, one verifies...")

So let's step through the proof. Everything is $\bmod p$:

$$\beta^\gamma \gamma^\delta = \beta^{\alpha^i \beta^j } (\alpha^i \beta^j)^{-\alpha^i \beta^j j^{-1} }$$

(Substitution of values)

$$... = \beta^{\alpha^i \beta^j } \alpha^{-i j^{-1} \alpha^i \beta^j  } \beta^{-\alpha^i \beta^j}$$

(Just distribute the exponent across $\alpha^i$ and $\beta^j$. In the $\beta$ exponent, you get a $j j^{-1} = 1$)

$$...=  \alpha^{-i j^{-1} \alpha^i \beta^j  }$$

(The $\beta$ terms cancel out)

$$...=  \alpha^{-\gamma i j^{-1}  }$$

(definition of $\gamma$)

$$...= \alpha^m$$

(definition of $m$)

Here, $i$ and $j$ are such that $0 \leq i,j \leq p-2$. The proof you are showing is that this scheme is existentially forgeable (see page 381, Theorem 16). This is a two-parameter forgery (the $(i,j)$).


Purpose of folding a digest in half The Linux kernel's random driver generates randomness by hashing an entropy pool using SHA-1. From the driver's source, the SHA-1 hash is apparently folded in half before being returned:

/*
 * In case the hash function has some recognizable output
 * pattern, we fold it in half. Thus, we always feed back
 * twice as much data as we output.
 */
hash.w[0] ^= hash.w[3];
hash.w[1] ^= hash.w[4];
hash.w[2] ^= rol32(hash.w[2], 16);

The reasoning in the comment strikes me as a bit odd. Why would there be any expectation that SHA-1 would have a pattern in output, much less one where folding the hash in half would solve the issue? It looks to me like the kernel developers are attempting to design a worthless "hash" to try to solve some supposed problem with SHA-1. This behavior even goes back to 2003 (and possibly before), in kernel 2.4. Is there any possible advantage to this behavior, or is it wholly unnecessary?

Look at the rest of the code around it. The hash value gets used twice: once to feed back into the pool and once as an output. Ideally those two would be independent, but the requirement is that an attacker who sees the output is not be able to tell what went into the pool.

Another option would be to halve the hash, throw half of it back in and the other half out. However, in that case the data being fed back would be just 80 bits - short enough for a brute force attack without knowing the output. Hence the comment earlier in the file: "By mixing at least a SHA1 worth of hash data back, we make brute-forcing the feedback as hard as brute-forcing the hash."

So basically the XOR is used as a cheap one way function. Is it any better than taking just the first half and throwing both back in the pool? SHA-1 would have to be pretty broken for that to make any difference.

Then again, this code to fold in half is actually from a time when using SHA-1 was an option and MD5 the default (early-mid 90s, not sure exactly when). So distrusting the hash was not nearly as paranoid as it seems today. Later patches have left it in because it's "harmless".


Difference between Hash function and Random Oracle Going through the blog post, I was under the impression that any cryptographic scheme which makes use of hash function is said to be using random oracle. But, I have come across one construction of ring signature scheme which uses hash function, yet the paper is titled as Sub-linear Blind Ring Signatures Without Random Oracles. Where is my understanding incorrect?

The random oracle model is a way to analyze schemes that need a hash function; essentially, you replace the hash function with some black box (the random oracle) which evaluates a function selected uniformly at random from all functions from its input domain to its output domain. Equivalently, it takes input and gives output like this:

If you give it an input it hasn't seen yet, it gives you an output selected uniformly at random from its possible outputs. It then saves that output for later use.
If you give it an input it has seen before, it gives you the output it saved previously.

No actual hash function is a random oracle. Hash functions are deterministic; for a given hash function, $H(x)$ in one problem is equal to $H(x)$ in some other problem. With a random oracle, this is not the case: the function used is random. Random oracles are often used to approximate hash functions in security proofs, but no actual hash function can be a random oracle because anything used in a real, sensible security scheme must be a deterministic algorithm.

Random oracles aren't used when analyzing hash functions, they're used when analyzing other things. Unfortunately, for any real, deterministic hash function $H$, you can come up with schemes which are secure when used with a random oracle but not when used with $H$. Essentially, you construct a signature scheme that hashes a bunch of stuff and checks if the hash of $x$ is $H(x)$ for all the $x$ it tested; if not, it outputs a normal signature, if so, it outputs a normal signature and then sticks the private key on the end. With a random oracle, it's extremely unlikely that the hashes represent any pre-specified function (as they're completely random), but if you use $H$ they will obviously always fit the relationship. So, random oracles are an imperfect model, and we generally prefer security proofs not relying on them.


Safety of encrypting a plaintext with its hash as the key What are the safety issues of using the the hash of plaintext as the key to encrypt it? The first that comes to mind is that if I can guess an approximation or part of the plain text, brute force attack complexity will be reduced considerably. Suppose that this is not an issue. Are there other security risks on this approach?

No, there are no security risk beyond "(with) an approximation or part of the plain text, brute force attack complexity will be reduced considerably", understood to cover the fact that an exact (or near complete) guess of the plaintext can be verified with near certainty by one not holding the key. That is under the plausible assumptions that the hash is secure in the random oracle model, and the cipher's design is independent of the hash (the later condition takes care of a cipher purposely made insecure specifically when the key is equal to the hash of the plaintext).

Decryption works just as usual: under the standard assumption that the ciphertext is public, revealing the key allows decryption. The only functionality issues that I can think of are that encryption requires more work, including two passes on the plaintext, and on-the-fly encryption is impossible.

So-called Convergent Encryption goes one step further: it uses a hash of the plaintext as key, and deterministic encryption (the hash is typically stored conventionally encrypted along the ciphertext, possibly using asymmetric cryptography). The same plaintext is therefore always enciphered to the same ciphertext (except for the conventionally encrypted hash). That is nice for de-duplicating encrypted data, but gives up a little more on security: it becomes slightly easier to recognize a known piece of data from its enciphered form.


Complexity of Boudot's zero-knowledge range proof scheme According to Camenisch et al. in Efficient Protocols for Set Membership and Range Proofs (see Section 1.2), the range proofs devised by Boudot in Effcient Proofs that a Committed Number Lies in an Interval are based on representing a number as the sum of four squares.

Based on this, Camenisch et al. claim that the complexity of Boudot's scheme is governed by the cost of finding these squares (see Section 4.4 of the paper by Camenisch et al.)

However, studying Boudot's schemes, I do not see any reference to this issue. Rather, Boudot defines the squares involved in the proof as $\tilde{x}^2_1,\bar{x}^2_1$, where $\tilde{x_1} = \lfloor\sqrt{x-a}\rfloor$ and $\bar{x_1} = \lfloor\sqrt{b-x}\rfloor$, where the value being proved, $x$, belongs in $[a,b]$. So the computation of these squares seems quite straight forward.

What am I missing?

Boudot's protocol is not based on the four-square decomposition - in fact, he was the first to come up with this idea of using a decomposition in four squares, but this was only mentioned orally in the talk he gave on this paper (as I was told by people who saw it - I do not think there is any written record). The first written record on this four squares idea is Lipmaa's Asiacrypt'03 paper (where you'll find additional discussion on the cost of finding these four squares). Boudot's original protocol has other efficiency shortcoming, though, but they are related to the communication required for the protocol, not to the cost of finding the decomposition.


Explanation of trace function $\operatorname{Tr}_m(x) = x^{2^{m}} \oplus x$ The following statement is from a paper (Partitions in the S-Box of Streebog and
Kuznyechik) about S-Boxes:

  For all $ x \in \operatorname{GF}(2^{n})$, it holds that $x^{2^{n}} \oplus x = 0$.
  If $n= 2m$ then we define the trace from $\operatorname{GF}(2^{2m}) \to \operatorname{GF}(2^{m})$ as the function $\operatorname{Tr}_m(x) = x^{2^{m}} \oplus x$.

I don't understand why this works for all $ x \in \operatorname{GF}(2^{2m})$.
Why is it safe to say that this operation ends in the subfield $\operatorname{GF}(2^{m})$?

All elements of $\text{GF}(q)$ are roots of $x^q-x$. In fact, this is a litmus test for determining membership in $\text{GF}(q)$: when working in an extension field of $\text{GF}(q)$, say $\text{GF}(q^m)$, we can determine whether an $\alpha$ is a member of $\text{GF}(q)$ by computing $\alpha^q$ and checking whether the result equals $\alpha$ or not.

So, in $\text{GF}(2^n)$, $\alpha^{2^n} - \alpha = 0$, and if we remember that addition and subtraction are the same operation in fields of characteristic $2$ and that this operation is often denoted by $\oplus$, we have that $x^{2^n}\oplus x = 0$.

The trace function from $\text{GF}(q^k)$ to $\text{GF}(q)$ is defined as
$$\operatorname{Tr}(x) = x + x^q + x^{q^2} + \cdots + x^{q^{k-1}}.$$
Verify that for all $x \in \text{GF}(q^k)$, $\operatorname{Tr}(x)$ belongs to $\text{GF}(q)$.  (Hint: apply the litmus test). So for the special case when $k=2$, the trace function from  $\text{GF}(q^2)$ to $\text{GF}(q)$ is just $\operatorname{Tr}(x) = x + x^q$. I will leave it to the OP see what happens when $q$ equals $2^m$ and whether the statements of the S-Box book are true or not.


Encrypting RNG output Under the following premise:

I need to generate multiple symmetric keys;
I cannot be sure about the quality of local system RNG;
I already have a strong key K (generated by other means / elsewhere).

Does it make sense to encrypt the output of system RNG with K (or some derivation of it) with the purpose of strengthening generated keys. More generally, can I strengthen the output of the RNG using K?

Clarifications:

Length - let's say that the entropy of K is 128 bit.
Number of keys - multiple, but not numerous (several or dozens, not more).

Second edit:

More clarifications and comment:

Persistent (and secure, as long as the whole system is not compromised) storage is available, so a sequential IV can be implemented.

I am starting to have doubts about the idea that RNG may be flaky while the system is still not compromised, but initially I assumed that RNG quality is not black and white and because it is easy to provide K, generated keys can be strengthened.

Apropos, I can deliver 256 bits K, so I can really just use it as seed for a PRNG and forget about all else. In any way, a compromise on the source of K is total falldown, so this starts to look like a straightforward option.

Don't even use the system RNG if you don't trust it but do trust K.

Use K to seed a secure PRNG; then generate keys from that RNG instead. (For example, ChaCha. Not RC4, because it's obsolete and insecure, but other secure stream ciphers work.)
Or use K with a key derivation function. If you don't need to follow standards then use HMAC with K for its key. Every time you need a symmetric key up to 512 bits long, increment a counter, HMAC the counter value, then take however many bits you need from the output.

Why?

You could encrypt the output of an RNG. Symmetric key encryption is supposed to produce ciphertext which is indistinguishable from a uniform random bit source. Encrypting a random or pseudorandom sequence isn't any better than encrypting some simple non-repeating sequence like a counter.

However, you could mess up the encryption by reusing nonces, using a block size that's too small, using a bad algorithm, or using a buggy implementation. I say don't use the system RNG if you don't trust it because encrypting its
output is at best equal to the alternatives I listed.

If your system RNG is biased or isn't seeded with enough entropy, then you have the problem of nonce reuse if you encrypt with a (not sufficiently) random IV. If you can prevent nonce reuse with a deterministic algorithm, then you can also prevent nonce reuse with secure PRNG or maintain a counter for the HMAC construct I mentioned.

You should be able to trust your operating system's secure RNG. But if you don't have access to one or you know it wasn't seeded with enough energy then that is reason to use something else.

You can't really make a better unpredictable non-deterministic RNG than what the OS can provide you. Userland attempts at entropy-gathering (non-deterministic) RNG algorithms don't have a good track record.

If you have a high entropy key, a secure algorithm, and ability to prevent nonce reuse, then PRNG/KDF output will be good.


Is it okay for a non-cryptographer to submit crypto code to an open source probject? I am not a cryptographer, nor do I claim to be.

However, at times I have wanted to contribute to open source cryptography projects such as libsodium.  The maintainer of libsodium is a cryptographer, and I consider it a good assumption that they will review any code submitted to the repo.

Under these conditions, is it okay to write the code, doing my best to get things right, and rely on a qualified person to catch any mistakes?

Edit: I am talking about implementations of already well-known, software-friendly algorithms that are not especially complex.  That is: zero new ideas, just "grunt work" — the problem is already solved and there is only the relatively mechanical task of writing the code.

I am especially talking about "glue code" that ties existing primitives together.

At least make sure that your code is reviewed. Verify you don't have possible buffer overflow or any kinds of implementation attack because of the use of non secure primitives. Moreover if you do so, test all your functions and in particular :

bitwise rotations
permutations
S-boxes...

Check everything as it is really easy to screw with it. Then use the test vector provided by the algorithm and check your results. For example here are the test vector I used when I implemented DES (which I don't use in production).

You can find other tests vectors of most ciphers here, i.e. for the AES-128-128.


Proof that a function constructed from a PRP is, or is not a PRF? Let $E$ be a family of Pseudo-Random Permutations of $b$ bits, with $E_K$ indistinguishable from random permutation with effort less than $O(2^b)$, easily computable as well as the inverse permutation, e.g. as instantiated by AES-192 for $b=128$. Let $E_A$ and $E_B$ be two public members of this family.

For an $E_K$ in $E$, let $F_K$ and $G_K$ be the functions
$$F_K:x\mapsto F_K(x)=E_K(E_A(x))\oplus E_K(E_B(x))$$
$$G_K:x\mapsto G_K(x)=E_K(E_A(x)\lor1)\oplus E_K(E_B(x)\land\overline{1})$$
where $\lor1$ (resp. $\land\overline{1}$) sets (respectively clears) the rightmost bit, and $\oplus$ is exclusive-OR.

Question: Are $F$ and $G$ families of Pseudo-Random Functions indistinguishable from random function with effort less than $O(2^b)$ ?

Note: formerly, I thought of an attack on $F$ by considering a cycle in $x\mapsto E^{-1}_B(E_A(x))$; but thinking about it, that attack is $O(2^b)$.

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') \wedge 1$ and $E_B(x)\vee \overline{1} = E_B(x') \vee \overline{1}$.  This immediately yields a distinguishing attack on $G$, since (regardless of $K$) we are guaranteed that $G_K(x)= G_K(x')$, something that should happen with just $1/2^b$ probability (not with probability 1).

I don't know how to efficiently find $x,x'$.  I can see how to find such a pair in about $2^b$ steps of computation.  Basically, pick a random $b$-bit value $y$, then compute $E_A^{-1}(y)$ and $E_A^{-1}(y) \oplus 1$; this gives a candidate pair $x,x'$, and you can then check whether $E_B(x)\vee \overline{1} = E_B(x') \vee \overline{1}$ holds.  The latter holds with probability $1/2^{b-1}$, so you'll probably have to try about $2^{b-1}$ different values of $y$ before success.  Nonetheless, even though the attack is hard to find, once you know the attack, the attack requires only 2 oracle queries and minimal computation.  This suffices to demonstrate that $G$ is not a secure PRF, at least under standard definitions of security.

Attack 2. I'll show an attack on $G$ that has about the same complexity as the best attack I can find on $F$.  In both cases, the attack requires about $2^b$ steps of precomputation just to find the attack, but then once the attack is known, it takes a lot less than $2^b$ steps to distinguish $G$ (or $F$) from a random function.

My attack on $G$ is an adaptation of my attack on $F$, so let me start by spelling out the attack on $F$ that I have in mind.  Define the permutation $\pi$ by $\pi(y)=E_B(E_A^{-1}(y))$.  The precomputation is as follows: find a short cycle of $\pi$, say $y_0,y_1,y_2,\dots,y_k$ (where $y_k=y_0$ and $y_{i+1}=\pi(y_i)$ for each $i$).  Define $x_i=E_A^{-1}(y_i)$.  Then we are guaranteed that $F_K(x_1)\oplus F_K(x_2) \oplus \dots \oplus F_K(x_k) = 0$.  This gives a distinguishing attack on $F$ that requires $k$ oracle queries and trivial work.  Since $\pi$ is effectively a random permutation, we should be able to find a short cycle in $\pi$: it is very likely that a short cycle will exist.

How long does it take to find the attack on $F$?  I can't see how to do it much faster than $2^b$ steps of computation.

Now here's the attack on $G$.  First, we're going to construct a new function $H$, as follows: $H_K(x) = G_K(x) \oplus G_K(x')$, where $x' = E_A^{-1}(E_A(x) \oplus 1)$.  Notice that, if you have an oracle for $G$, you can extract an oracle for $H$.  Also, expanding the definition of $H$ yields $H_K(x) = E_K(E_B(x) \wedge \overline{1}) \oplus E_K(E_B(E_A^{-1}(E_A(x) \oplus 1)) \wedge \overline{1})$.  By analogy to the attack on $F$, let's define a permutation $\sigma$ by $\sigma(y) = E_B(x') \wedge \overline{1}$ where $x=E_B^{-1}(y)$, i.e., $\sigma(y) = E_B(E_A^{-1}(E_A(E_B^{-1}(y)) \oplus 1)) \wedge \overline{1}$.  During precomputation, find a short cycle of $\sigma$, say $y_0,y_1,y_2,\dots,y_k$, and define $x_i=E_B^{-1}(y_i)$.  Then we are guaranteed that $H_K(x_1)\oplus \dots \oplus H_K(x_k)=0$.  This in turn implies a relation on $G$, where the xor of $2k$ $G$-outputs is guaranteed to be zero (regardless of $K$).  Thus, any short cycle in $\sigma$ yields a distinguishing attack on $G$.  The distinguishing attack itself is very fast (assuming $k$ is small).

How long does it take to find the attack on $G$?  I can't see how to do it much faster than $2^b$ steps of computation---in other words, about the same complexity as finding the attack on $F$.

This provides an alternate way to break $G$.


How is the precomputed table for 25519 Elliptic curve generated? I am wondering how the precomputed table for scalar multiplication for elliptic curve (in my case 25519) is generated/precomputed?

I am talking about this
[https://github.com/WhisperSystems/libsignal-protocol-javascript/blob/master/native/ed25519/base.h

The piece of code which uses this header file is:

/* base[i][j] = (j+1)*256^i*B */
/*static const ge_precomp base[32][8] = {
#include "base.h"
} ;*/

ge_precomp is defined as

ge_precomp (Duif): (y+x,y-x,2dxy)

Is there a paper or a piece of code where I can see how this table is generated? I am not trying to learn more about elliptic curves, I simply want to precompute this myself because of the specifics of my project.

I guess I would have to add point B to itself for (j+1)*256^i mod p times for each i and j.
Is there a less compute intensive way to do this on an e.g. Raspberry Pi?

Thanks in advance!

CodesInChaos created an exact gist in C# for this:
https://gist.github.com/CodesInChaos/ef914909941ce7caf514

It worked for me, took around 8 seconds on a 48MHz 32bit device, but either way, works.
My C port can be found here
https://gist.github.com/irfansehic/9c0b204845370f372bdfccfb66ec5942


Do sites store login password with hash? If so, can people can use hash collision to log in? I was researching about hash, and I thought, If sites store passwords with hash algorithms, then can't this happen:

User A has the password 'hello'
User B finds out the hash code of the password of user A
User B knows the username of user A and uses hash collision to find a string with an identical hash
User B logs in the account of user A

So now, my main question is:
Do databases store the hash of the password or not? And if they do so, can the thing I wrote above happen?

Databases generally store hashed passwords (as they should), but some store it plaintext.  If someone were to find a hash collision that matched the stored, unsalted, and hashed password, then yes, they would be able to use that collision to login, because the client would send the password to the server, the server would calculate the hash and compare it to the one in the database. Since the two match (different input, same hashed value), login would  succeed. However, I might like to add, it's more computationally feasible that one would bruteforce the password as opposed to finding a collision, especially with the generally small size of a password.


Does CPA-secure means security against differential cryptanalysis? I've read on differential cryptanalysis where it traces the differences on the changes of ciphertexts of the same plaintext, except for some bits.

However, I wonder is the differential cryptanalysis is applicable to CPA secure cryptos like El-Gamal?

Thanks in advance.

Differential cryptanalysis is a tool which is used to analyze symmetric primitives such as block ciphers and cryptographic hash functions. So it is applicable to CPA secure symmetric encryption schemes.

ElGamal, however, is an asymmetric encryption scheme. Its CPA security essentially relies on the decisional Diffie-Hellman assumption in some group $\mathbb{G}$. Roughly speaking, under this assumption, the adversary can not distinguish the ElGamal ciphertext $C = (C_1, C_2)$ from a random element in $\mathbb{G} \times \mathbb{G}$.

Generally speaking, in the asymmetric setting, security is typically proven by showing that an adversary against some security property would imply an adversary against some underlying hardness assumption (e.g., DDH in the case of ElGamal). That is, as long as the underlying assumption holds, also the cryptosystem is secure. Therefore, one does usually not apply custom attack techniques to the cryptosystem itself, but rather analyzes the underlying hardness assumption. In contrast, in the symmetric setting, the security of the cryptosystem can typically not be reduced to breaking some underlying assumption, which is why one directly analyzes the cryptosystem regarding potential "weaknesses". Differential cryptanalisis is one such tool.


Why RSA uses {d,n} as private key instead of {e,n}? While studying the RSA algorithm I referred to some books and some sites such as RSA (wikipedia) and all of them chose {d,n} as the secret (private) key and release {e,n} as the public key but as d and e are multiplicative inverse of each other, can't we keep {e,n} as private key and use the other as public key? Is it a standard rule to choose the {d,n} as the private key?

The letters d and e are just a notation -- what matters is that there are two exponents, each undoing what the other does, and making one public does not intrinsically reveal the other. By tradition, the one made public is called e.

However, there is a twist: the exponent that is not made public, i.e. the private key, can be really private only if it is sufficiently big. If the private exponent is very small (e.g. it fits on 20 bits), then it is easy to rebuild it from the public key, if only by trying all possibilities. If the private exponent is not so small but still substantially smaller than the modulus n, more advanced attacks are possible, to the same effect (there is an attack by Coppersmith which works as long as the private exponent length is no more than 29% of the length of n).

Conversely, there is no issue in the public exponent being small. That exponent can be as small as the value 3, although, there again by tradition (and also out of a solid dose of historical confusion), 65537 is often used as public exponent. Small exponents promote faster computations. Since the public exponent can be small, we thus make them very small.

So if you generate your key pair and choose both exponents as big numbers (more or less the same size as n), then you can choose either one to be the public exponent (which will be thereafter called e). However, if you selected one of the exponents to be small, then the small exponent shall be the public one, because otherwise your key would be very weak and prone to cracking.

Some widespread implementations of RSA don't tolerate big public exponents; e.g. the one in Windows CryptoAPI, used by Internet Explorer when doing SSL, requires the public exponent to fit on 32 bits.


how to define the Truncated Polynomial? In NTRUEncryption, I seen the trucated polynimials, but I cannot understand the trunacated polynomial calculation.
So, could tell me anyone How do we calculate the truncated polynomial?

The term "truncated polynomials" shouldn't really be used in relation to NTRU. A truncated polynomial is, strictly speaking, a polynomial with terms of order N or more discarded. NTRU instead uses polynomials mod $X^N-1$. So, for example, if $N=3$, then $x^2+1 * x^2+1$ = $x^4+2x^2+1$. Truncated this is simply $2x^2+1$. Reduced mod $X^3-1$, it's $2x^2 + x + 1$.


Generate ANF equation? Given an SBox, how can I generate its component equations (in ANF)?
given in this link: https://en.wikipedia.org/wiki/Algebraic_normal_form
For example, let's say I have this SBox:
$$\{1, a, 4, c ,6 ,f ,3, 9, 2, d, b, 7, 5, 0, 8, e\}$$

There is a simple way based on repeated linear interpolation, known as the Shannon-expansion.
With this you can extract the ANF expression from any black-box map function (for example, an S-Box) using on the order of $2^n$ evaluations for an $n$-bit Boolean function. It's slow but remarkably simple. I will demonstrate using $2$-bit function.
$$f(x_0,x_1)$$
can be expanded in the first bit
$$\small{f(x_0,x_1) = f(0,x_1)(1-x_0) \; + \; f(1,x_1){x_0}}$$
and then again in the second bit
$$\small{f(x_0,x_1) = f(0,0)(1-x_0)(1-x_1) \; + \; f(0,1)(1-x_0)x_1 \; + \; f(1,0){x_0}(1-x_1) \; + \; f(1,1){x_0}{x_1}}$$
Repeating this with larger functions, the pattern becomes clear. The $k$th term in this expression simply multiplies $\small{f(x)}$ with either a $x_i$ or $\small(1-x_i)$, depending on the setting of the bit in the input to the map function.
So for a larger Boolean function, the first term would be
$$\small{f(0,0,0,0,\ldots,0) = (1-x_0)(1-x_1)(1-x_2)(1-x_3)\ldots(1-x_n)}$$
and the final term would be
$$\small{f(1,1,1,1,\ldots,1) = x_0 x_1 x_2 x_3\ldots x_n}$$
The ANF can then be derived from this expression by multiplying out the parenthesis. This is laborious by hand, but a small amount of code in a computer program.
Here is the idea implemented in C++
#include <iostream>
#include <vector>

/* black-box map function to extract ANF */
int map(int x) {
  int sbox[] = {0x01, 0x0a, 0x04, 0x0c, 0x06, 0x0f, 0x03, 0x09, 0x02, 0x0d, 0x0b, 0x07, 0x05, 0x00, 0x08, 0x0e};
  return sbox[x % 16];
}

int num_input_bits = 4; /* number of map input bits to consider */
int num_output_bits = 4; /* number of map output bits to consider */

/* (1-x_0)(1-x1)x_2 = x_2*(1 + x_0 + x_1 + x_0*x_1) */

int main() {
  /* step 1) calculate ANF of the map function */
  int num_input_states = 1 << num_input_bits;
  for (int i = 0; i < num_output_bits; ++i) {
    std::vector<int> anf(num_input_states); /* accumulate ANF here */
    for (int j = 0; j < num_input_states; ++j) {
      int bit = (map(j) >> i) & 1; /* extract map output bit */
      if (bit == 1) {
        for (int k = 0; k < num_input_states; ++k) { /* "broadcast" result to ANF terms */
          if ((j & k) == j) { /* does this bit contribute to this ANF term? */
            anf[k] = (anf[k] + 1) % 2;
          }
        }
      }
    }
    /* step 2) print the ANF expression */
    std::cout << "y_" << i << " = ";
    int term_count = 0;
    for (int j = 0; j < anf.size(); ++j) {
      if (anf[j]) {
        std::cout << (term_count++ != 0 ? " + " : "");
        size_t factor_count = 0;
        for (int k = 0; k < num_input_bits; ++k) {
          if ((j >> k) & 1) {
            std::cout << (factor_count++ != 0 ? "*" : "");
            std::cout << "x_" << k;
          }
        }
        if (factor_count == 0) {
          std::cout << "1"; /* empty product */
        }
      }
    }
    if (term_count == 0) {
      std::cout << "0"; /* empty sum */
    }
    std::cout << std::endl;
  }
  return 0;
}

Which outputs the ANF representation of your S-Box:
y_0 = 1 + x_0 + x_1 + x_0*x_1 + x_2 + x_3
y_1 = x_0 + x_0*x_1 + x_2 + x_0*x_2 + x_3
y_2 = x_1 + x_2 + x_0*x_3 + x_1*x_3 + x_1*x_2*x_3
y_3 = x_0 + x_1*x_3 + x_0*x_2*x_3


Public Key generation for Ed25519 vs X25519 It is my understanding that EdDSA uses a slight variant of Curve25519 (typically used for ECDH), called Ed25519.

Given the same private key, are the differences between the two algorithms enough to make the resulting public keys different between X25519 and Ed25519?

In other words, if I'm writing code to generate private/public key pairs, do I need separate implementations for EdDSA/Ed25519 and ECDH/X25519?

Clarification: I realize that EdDSA mandates a SHA-512 step which ECDH/X25519 does not specify. I'm curious if the public keys are the same for the given input to the scalar multiplication step.

The public key representations are related but not the same. They cannot be used interchangeably without additional processing.

The curves are birationally equivalent; a point on a curve has an equivalent on the other curve.

So, given an EdDSA public and/or private key, you can compute an X25519 equivalent. Libraries such as libsodium provide functions to perform these computations.

Of course, it also works the other way round, even though this is slightly more convoluted due to the fact that the sign is not present in encoded X25519 keys.

There are alternatives. One of them is to use the same curve for both operations. There is nothing wrong with using Ed25519 for DH.

If what you need is store a single secret, you can simply use it for both operations. You will get 2 public keys, but given how small they are, it is rarely an issue.

Speaking of which, is storing a combined 64 byte key instead of a 32 byte key really an issue? For most applications, it rarely is.


ElGamal with elliptic curves II There is an encryption scheme using elliptic curves given by @tylo explained here: @tylo's answer on ElGamal with elliptic curves and here: ElGamal with elliptic curves I. The encryption idea is to multiply (in the field) the message $m$ with the $x$-coordinate of a specific point on the elliptic curve (which is assumed to be hard to compute without breaking discrete log).

My question is why this is a secure encryption -- basically, only about half the $x$-coordinates are in use on an elliptic curve, so I guess it's a bit hard to say that the $x$-coordinates are really random. Is it assumed that the $x$-coordinate of a random elliptic curve point is pseudo-random? (There is no mentioned hashing)

Could anyone please supply a link to further reading or a brief explanation on the security of this scheme? Another question (also appearing in the mentioned questions) is if using addition in the field (instead of multiplication) is also secure.

EDIT: Following the discussion in the comments, I have a concern regarding the security of the scheme -- let's suppose that there are only two possible messages, $m_0$ and $m_1$. Then, the encryption is done by multiplying, in the field, the chosen message with the $x$-coordinate of an unknown point on the curve. A challenger receiving the cipher-text $c=x\cdot m_i$ can then compute $x_0=c/m_0$ and $x_1=c/m_1$. If only one of these is an $x$-coordinate of a point on the curve, then the other cannot be the chosen message. Can someone tell me what I missed in this "attack"?

I have a concern regarding the security of the scheme -- let's suppose that there are only two possible messages, $m_0$ and $m_1$. Then, the encryption is done by multiplying, in the field, the chosen message with the $x$-coordinate of an unknown point on the curve.

What I highlighted is your problem; that is an invalid way of combining the point which is the result of the DH exchange with the plaintext.

In the standard El Gamal scheme, we use the 'modular multiplication' operation as the group operation within the key exchange, and hence we use that to combine the plaintext with the DH value.

So, when perform the operations on an Elliptic Curve, we do the same.  So, what you need to do is (somehow) convert the plaintext into an elliptic curve point, and add it to the point derived from the DH exchange; if the plaintext point is in the same prime-sized subgroup is the DH generator, you're safe.

Alternatively, you can just do ECIES, and not have to worry about translating plaintexts into points...


How to invalidate decryption key in multi user model? I want to develop an application that will allow a user to create a public/private key pair, and encrypt it symmetrically with a key such that once they enter their password, they will be able to decrypt the key pair and retrieve its contents.

However, it is desirable for someone else that they trust to be able to decrypt the key as well, in case they lose access or have a reason for someone to be able to access the key pair (like a joint account).

Let's say that a user John has given Adam, Emily, and Scott access to the key pair, but it turns out that John no longer trusts Emily and wants to invalidate her access. Since she has already seen the private key, he has to generate a new one, but wants to do it in such a way that Adam and Scott will still have access without having to enter their password or do anything additional.

How can this be accomplished? Is this possible?

Sure.  Encrypt John's private key under Adam, Emily, and Scott's public key.  When you revoke Emily and change John's keypair, encrypt John's new private key under Adam and Scott's public key.  If Adam or Scott need access, they can decrypt.  After the key change they will still have access and still be able to decrypt it, same as they were able to before.


Is an equality test possible when using paillier crypto? Given two ciphertexts $c_1=Ek_1(p_1)$ and $c_2=Ek_2(p_2)$ encrpted by two different users with two different keys, i.e. $Ek_1$ and $Ek_2$ using a homomorphic crypto such as Paillier. Can a third party perform an equality test on $c_1$ and $c_2$ without knowing the keys?

As for my research efforts…

I read few papers on equality tests, and homomorphic encryption. However, in those papers almost all the scenarios are like when a client upload its encrypted data on the cloud and then search an encrypted keyword on it. In my case, I have a shared table of cipher texts and i have to find common attributes among the cipher texts encrypted by different clients stored in shared database. whereas normally comparison is made on cipher texts encrypted by a single client and done by the owner of the data.

No, you can't let a party test for equality with different keys without also allowing that party to guess and confirm the message contents.

I'll now show that a scheme that allows you to test for equality is trivially insecure against passive eavesdropping adversaries.

Suppose we're in the usual multiple-message eavesdropper game, that is our challenge messages actually are allowed to consist of multiple messages and we get the pair of individual encryptions as our challenge ciphertexts and are not allowed to ask the oracle for encryptions or decryptions.

Select $m_0=(m, m)$ and $m_1=(m, m')$ where $m\neq m'$.
Receive $c_b=(c,c')$ with $b\in\{0,1\}$ being chosen uniformly at random.
Use your special functionality "$=$" to evaluate $c=c'$. If it is true, return $b=0$ and if it is not return $b=1$.
Note that this special functionality may involve choosing a key for the cryptosystem yourself and encrypting $m$ and $m'$ under that key you know and which is unrelated to the key used for $c,c'$.

Obviously, this strategy works with the same probability with which you can detect duplicates, which is $1$ which is non-negligible and as such this scheme cannot be secure against eavesdroppers who can observe multiple messages and make this equality test.

Note that Paillier-Encryption is IND-CPA secure, meaning it is secure in the above scenario even when you'd be given a way to encrypt messages and as such Paillier-Encryption cannot possibly allow for passive equality tests without being given the decryption key.

The best technical solution I could offer for your problem is to let each party encrypt the hash of the contents for the storage provider and then let the provider make the deduplication based on these hashes which only he can read. But this bears the problem that the users can of course lie about the hash because you have no way of verifying it. Alternatively you could run Socialist-Millionaires-Protocols between all pairs of files (well their owners should) and you use the reported results (if they agree) for deduplication which again relies on the honesty of the users.


Does AES encryption of a NTRU pivate key reduce security? The NTRU crypto system requires quite long keys. For example with parameters N=439 and q=2048 the security is 128 bits and the key_size is 4829 bits.
When the private key is encrypted with AES-256 and the ciphertext is made public, can an attacker learn something from that? Or is the 128 bit security of NTRU reduced by doing this?

No, 128-bit NTRU private key will retain its security when encrypted by AES-256 using a properly generated/derived key.

Suppose 2 ciphertexts, 1 NTRU, 1 IES-ECC, both are 128-bit secure, what you have right now is 2 ciphertexts requiring $2^{128}$ work to recover the plaintext without having the corresponding private key. This is true even if the encoded private key is longer than 128 bits (because of non-generic attacks such as lattice-reduction or Pollard's rho algorithm)

Now suppose the keys are encrypted with a 256-bit cipher, this doesn't reduce the security nor increase it. This is because one can always attempt recover the private key from the already known public key without attacking the encrypted private key anyway.


How to solve the reverse of an equation that uses MOD? I've been tasked with reverse engineering an unknown crypto function.  The function uses the following constants:

$a=380951$:
I noticed that this is a prime number
$b=3182$:
I noted that this is a prime number + 1

The math function applied is as follows:
$\mathrm{result}=((\mathrm{value} \bmod a) \cdot b) \bmod a$

The value is a 24 bit number, as is the result (obviously). The result is subsequently fed into a lookup table of which bits it represents. My plan is to find an efficient algorithm to determine what number $\mathrm{value}$ needs to be to achieve a desired $\mathrm{result}$. If this answer is not within the 24 bit limit, then retry with one of the others that result in the same answer through the lookup table data.

If someone can identify possible algorithm names then I can use that directly, I just can't figure out what this scheme is...

Here is an example:

1434758 becomes 83172 -> lookup table results in 0x37e5 (decrypted 2 bytes of data)

Better answer:
291905 becomes 83172 -> lookup table results in 0x37e5 (decrypted 2 bytes of data)

Lookup table:
7,
15,
23,
47,
93,
186,
372,
744,
1488,
2976,
5952,
11904,
23808,
47616,
95233,
190465

The algorithm used for that is if the result is >= the lookup table then the bit in that position is 1, its number is subtracted and we move to the next bit.

Does anyone recognize this routine?

Alternatively:

Let $x=((y \bmod 380951) \cdot 3182) \bmod 380951$.

How can I efficiently find $y$ given a value of $x$?

If $a$ is a prime number and you know $r$ and $b$, and want to solve $v$ given the equation $r = v*b\mod a$, all you have to do is to apply the extended Euclidean algorithm for finding the multiplicative inverse $b^{-1}\mod a$, and then calculate $v = r*b^{-1}\mod a$. Alternatively, you could apply Fermat's little theorem and calculate $v = r*b^{a-2}\mod a$.


What is a simple information authentication protocol for constrained devices? Background: I have an application where devices will poll information from some source on the network.

These devices are very basic and have modest processing and memory capabilities. Hashing (and by extension, HMACs) is doable, but more might be too much.

The information is public, and the devices do not need to authenticate themselves to the source. However, the information must be authentic and fresh.

The protocol I have in mind is that (edited for clarity)

a device would generate an appropriately large nonce, and send it unencrypted to the source. The nonce is never seen before and can not be predicted.
the source would accept the nonce, concatenate it with the information,  generate the HMAC for the result, and then send the result back to the device. Note that the source does not authenticate devices and accepts any nonce sent to it.
the device would check that the HMAC is valid, and proceed to act on the information.

I believe this would provide the required security (Hopefully). However, I would very much rather use a well-known protocol if such protocol can meet both security and hardware constraints.

This leads me to my two questions:

What are the well-known and studied protocols that can meet these constraints?
In the unlikely case that no such protocol exists, what do you think of the protocol proposed in this post?

Any input on this matter would be appreciated.

Your initial idea is good. What is needed here is a challenge response protocol but rather than key agreement we need to authenticate a piece of data.

device issues challenge:(device id , nonce)
server signs and replies with MAC and data:(data,mac(device_key,nonce||data))
device verifies mac

As long as nonces don't repeat the data must be re-MACed by a party knowing the devices secret key and the device can be sure it has fresh, valid, data.

all that's left is picking a MAC function. You want a low cost keyed MAC. SHA256 and other well known hash functions are expensive because they need to resist collisions when the adversary can see their internal state and using them for MACing a message is wasteful. Less expensive MAC functions exist.

Here are a few mac algorithms that would work well:

CBC-MAC_AES (use this if you have AES hardware)
CBC-MAC_SPECK64/128 (designed by NSA (do you trust them?), likely <200 bytes code size on 8bit platform but similar on 32bit platforms)
Siphash (on Atmel AVR requires 1500 bytes code 42 bytes memory)

note on CBC_MAC: The wikipedia page mentions an IV which prevents replay attacks. IVs must be both unique and secret. If you have a secret IV used elsewhere, it can be reused with some caveats. The IV can also be generated from a nonce by encrypting the nonce. In your application though you can just prepend the nonce to the data before MACing.


How can I determine key length for message encrypted by many-time-pad? For message $ m $ and key $ k $ I get encrypted message $ c $ ($ m \oplus k = c $) where $ length(k) < length(m) $. Additionally I know that message $ m $ is English text. Instead of using pure brute force method, I want to narrow possible keys, by estimating key length using language pattern like “relative frequencies ordered by frequency” Letter frequency. So for example, for key with length 3, I should get three sets: $ \{c_0, c_{0+3}, c_{0+6}, …\}; \{c_1, c_{1+3}, c_{1+6}, …\}; \{c_2, c_{2+3}, c_{2+6}, …\} $, and each of this sets should somehow be compared with relative frequencies pattern. What is the best method (statistical?) to compare this sets with pattern, and final score for each key length, with scores for other keys length?

I am basing my answer on Cryptopals.

The basic idea is that as {c0,c0+3,c0+6,…} have all been xor-ed with the same byte, the number of differing bits between c0 and c3 is the same as between p0 and p3. (this number is called the Hamming distance between two characters.

Furthermore, the distance between [c0 c1 c2] and [c3 c4 c5] is the same as between [p0 p1 p2] and [p3 p4 p5], assuming the key length is 3. In regular English text, the hamming distance between two blocks of plaintext should be small, as the letters actually used occupy a highly ordered small fraction of the total ASCII range.

However, the distance between [c0 c1 c2 c3] and [c4 c5 c6 c7] would be ~50% of the total number of bits, because the xored key does not "cancel itself out".

So iterate over a range of possible keysizes, and compute the hamming distance between the first two blocks. Then normalize this result by the keysize.

The lowest value should correspond to the keylength.

Now you have a many time pad, where many = len(m)/keylength.
Each message is [c0 c1 c2] or [c3 c4 c5] or [c6 c7 c8]

Once you know this, then apply frequency analysis to {c0,c0+3,c0+6,…};{c1,c1+3,c1+6,…};{c2,c2+3,c2+6,…} independently to find each key byte.

You could also apply crib dragging. This is basically where you guess that a word is in a certain spot

There is also a cool attack that relies on a quirk of ASCII: 'a' ^ ' ' = 'A'. That is, xor-ing an English letter with a space simply flips the sign.
Helpfully, spaces are statistically the most common "letter" in English text.

If you take {c3,c6,c9,c12,…} and xor each byte with c0, you get {p3^p0, p6^p0, p9^p0,...}.
If this resulting sequence is mostly (~70%) in the range of "a-z" union "A-Z", then 9/10 times, p0 is a space.

You can of course instead xor the sequence with p3 or p6 or ... to check if that character is a space. Given a long enough message, one of the plaintext characters WILL be a space, and then you can instantly get every other plaintext characters which were xor-ed with the same key byte!

As a rule of thumb for attacking N-time pads:

Frequency analysis works once N =~ 6 and is a joke below that
Crib dragging becomes slow past N =~ 8, but is your best bet for small N.
Finding spaces works better than frequency analysis at ALL message sizes. It works even on 2-time pads.


suitable programming language for cryptography algorithms I know as programming languages C and java , and I know that java is slow so for this reason it is not suitable for cryptography applications espacially low level programming (manipulating bits) , so for this reason I turned to C as programming language but C is difficult in some how especially for GUI (graphical interfaces) , inaddition to this there is no byte type . My question is can we integrate C to java . it means when preparing GUI I use java and when programming the application I use C it is my first suggestion for asking you if it is possible and if we will not have a slow runtime. secondly using delphi ruther than C and java so , please advice me I am in adeadline ,and i must take a decision.

You can call C from Java. You can call C libraries from just about anything.

Java isn't suitable for some cryptographic applications because you can't guard against garbage collector attacks, not because it's slow. It's not particularly slow. C does have a byte type, it's called "char". Object Pascal (Delphi) isn't a systems programming language, and so shouldn't be used to implement a crypto library.

Finally, do not implement your own cryptographic algorithms. Use an existing library.


Why are there only positive value points on an elliptic curve? I read about elliptic curve cryptography $E$ over $Z_p$ where $p$ is prime number and $G$ is a base point on the curve. I noticed the points resulting from multiplication e.g. $2G$,$3G$,.....,$(N-1)G$ are always be positive numbers for $x , y$ and don't contain any negative values.

Whats the reason for these results not containing any negative values?

Actually, strictly speaking, the $x$ and $y$ values on an elliptic curve point aren't integers; instead, they are field elements.  That is, the elliptic curve is defined in a field, which is a group of elements with addition and multiplication operations defined on them (along with a group of identities); the $x$ and $y$ values are members from these elements.

Now, you specify that you're doing a curve over $Z_p$; that field (often called $GF(p)$), which has precisely $p$ element, is most commonly represented by the integers between 0 and $p-1$.  With this representation, we perform the addition and multiplication operations by taking the represention, adding or multiplying the two values together (using normal integer arithmetic), and then perform a modulo $p$ operation (which maps the value back into the range of 0 to $p-1$.  If $p$ is prime, these operations satisfies all the required identifies of a field.

So, when you say that that points are always have positive numbers for $x, y$, what you're actually saying is that, using this standard representation, negative values never occur.  That's trivially true because this representation only contains values between 0 and $p-1$, and never takes on negative values. We can easily define an alternative representation which does contain negative values; we just don't have any reason to.


Can it be proven that my home-brewed hash function is not LESS secure than a known good hash function it leverages? Home brewed cryptography is strongly discouraged because it is so easy to get it wrong.

Even if we leverage a known good hash function, one example, sha256, here by referred to as g() and use it in conjunction with a home-brew function b(), we can reduce our security because we have reduced our entropy; example:

g(b('secret')) will be less secure than just g('secret') if b() is collision prone.

Proving (I am not using prove in the strictest mathematical sense) a hash function is more secure than another is a herculean task that requires a lot of time from cryptography experts, and is beyond the scope of this question.

However, let's say no crypto-hash function that suits my needs currently implemented on my platform so I want to home-brew. If I am okay with worse performance, ect, and simply want to ensure it is not less secure than a known good function g() it leverages extensively.

For example, if we define b() to be g(g(g(g(g(g(g(g(g('secret'))))))))) we know that b() is not less secure than g()

Are there a set of quick set of guidelines that can be leveraged to ensure a derivative home-brew function is not less secure than the function it uses?

One example function b() might look something like this where it mainly uses a propriety logic as salt for g() (please do not think that this is intended as a replacement for random salt!!):

b() is defined as g('secret' + b1('secret'))

Yes, standard reduction proofs usually do the trick.

Reductions proofs usually work this way: Assume you can break property X of the new primitive, show how this capability (when used as black-box oracle) can be used to break property Y (with X=Y being allowed) on the old / standard primitive. Because property Y holds for the old primitive, you know also know property X holds for the new one by contraposition.

Concretely, you usually want at least collision resistance and preimage resistance.

So let's do an example with collision resistance:
Let $g(x)=f(x)\parallel h(x)$ with $f,g$ being collision resistant. We want to show that $g$ is collision resistant. Assume we have a collision on $g$, that is we know $x\neq x'$ such that $g(x)=g(x')$. Now by construction this means that $f(x)\parallel h(x)=f(x')\parallel h(x')$. Assuming $f$ has a fixed output length (as is usual with hashes), this means that $f(x)=f(x')$ needs to hold, but because we assumed $f$ to be collision resistant, this is clearly impossible and thus $g$ is collision resistant if $f$ is (actually $g$ is collision resistant if at least one of $f,h$ is, but this is about the basic principle).

As for $b(x):=g(x\parallel b_1(x))$, this is obviously collision resistant if $g$ is. Assume we knew $x\neq x'$ such that $b(x)=b(x')$, then we have $g(x\parallel b_1(x))=g(x'\parallel b_1(x'))$ but up to naming this is equivalent to saying $g(y)=g(y')$ which is a collision on $g$ if $y\neq y'$. Now because $y=x\parallel b_1(x)$ and $y'=x'\parallel b_1(x)$ with $x\neq x'$, clearly these are inequal because the leading part(s) consisting of $x$ and $x'$ are unequal. Thus we have constructed a collision on $g$ from a collision on $b$ and because $g$ is assumed to be collision resistant, this means that $b$ is as well.


What are differences between $E(F_p)$ and $E(Z_p)$? When I read some books about elliptic curve cryptography noticed that. sometimes symbolized elliptic curve over $F_p$ is $E(F_p)$ and sometimes symbolized elliptic curve over $Z_p$ is $E(Z_p)$.

I know p is prime number In both cases.

I wonder. Is there a difference between that symbols or they have same meaning .

Just adding the comments of poncho and blackadder here which I think should have just been posted as an answer (answer is community wiki in order not to cowardly get credit for this).

The difference comes if you do ECC in an extension field; where the field size is $p^k$ for k>1. In that case, $Z_{p^k}$ would imply that you're doing your math modulo $p^k$, which would be incorrect (that's not a field). Instead, in that case $E(F_{p^k})$ would be the correct notation. Of course, nowadays we usually stick to prime fields; in that case both notations are equivalent.

Note that as BlackAdder mentioned the correct answer might depend on the author of the paper, if the paper was written by a number theorist then there is a chance that $Z_p$ means the $p$-adic integers, and arithmetic in $Z$ modulo $p^k$ (i.e. the $Z_{p^k}$ in poncho his comment) would be denoted by $Z/{p^k}Z$ in such papers.


Is there any knapsack-based cryptosystem that has not yet been broken? I co-authored and implemented SRVB, an asymmetric cryptosystem, only to eventually realize that it is strongly related to Merkel-Hellman cryptosystem, which has been broken. In order to help me investigate the efficacy of this development I took part of, what are the knapsack inspired attempts of asymmetric cryptosystem?

Thank you in advance.

edit:

SRVB is finally documented in an academic style:

Thank you for your attention!

It seems that the Okamoto-Tanaka-Uchiyama and the Murakami-Nasako knapsack cryptosystem have not been broken, but I'm not an expert in this field and cannot tell whether it received enough attention from experts to be deemed secure. The OTU cryptosystem was analyzed in this paper, and the authors state that they "actually
believe that this system may be secure with an appropriate choice of the
parameters".

In any case, the link you gave seem strange. Why not trying to publish your cryptosystem in a peer-reviewed conference, or recruiting an expert to study its security, rather than offering a "crowdfunded money prize" to anyone that breaks it? It does not look like a good way to make people confident regarding the security of your proposal.


Battleship game state save so players can't look up each others' states but server can 1. Summarize the problem
I want to encrypt save game data for 2 players game - you can think of it as classic "Battleship" game:

Player A knows his game state, does not know Player B's game state.
Player B knows his game state, does not know Player A's game state.

To create a save game, both states are combined to encrypted format.
This way, both players can download a save game without looking into it what is an opponent game state.
The server can know both game states and has to decrypt both players' game states to know them.
Inputs to create crypto keys can be:

players names (known only to player A and B)
game ID (known only to player A and B)
players' passwords (each password is known only to the respective player and is always typed into the Frontend - the server does not need to know it)

2. Provide details and any research
I figured out I want to use asymmetric encryption and public key cryptography.
But when looking at my solution, I realized it might seem simple and easy, but I remember rule 1 of crypto: never do it yourself so I seek advice here.
3. When appropriate, describe what you’ve tried
Players type in frontend their name, password & game ID.
If a match found for name A, name B, password A, password B & game ID we have a "decryption key" that successfully is going to decrypt both players' game states for the server.
The problem is I have "too many" inputs (public keys) and too few private keys. I do not know how to mix them up.
A model I found only works on 1 public and private key https://docs.huihoo.com/globus/gt4-tutorial/ch09s03.html - I have times 2 complexity than this. Many different inputs to combine for a 1 key... How do I mix them together I have no idea.
PS
I do not know how to describe the problem better to find a surly already existing solution. Can you recommend a primer course focused on multiplayer games?

You don't even need the server to decrypt.
You need players to commit to their initial board by providing a hash of the board(probably with extra random data to increase entropy).
They can then play as usual. And save the game in encrypted form using independent keys.
At the game end commitment are to be revealed to verify no cheating.
The server need not do anything beyond store information and optionally forward messages.
Alternatively if you have a trusted server, skip encryption of state entirely, only have both parties authenticate to the server, and communicate with it over a secure channel (e.g HTTPS) and the server will enforce permissions and let each player see only their own state.


How should one create an ephemeral Diffie-Hellman private key? When picking an ephemeral Diffie-Hellman private key (little a or little b), can I reasonably just pick 32 random bytes? I am specifically interested in use within SRPv6.

RFC5054 says that these ephemeral keys are "a random number that SHOULD be at least 256 bits in length."

RFC2631 says

  X9.42 requires that requires that the private key x be in the interval
  [2, (q - 2)].  x should be randomly generated in this interval.

(where q is (N-1)/2.)

Goals and concerns

It would be nice to just get a bunch of random bytes and make those into a big integer than to have to uniformly pick a big integer within a specific range.

Question updates following comments

When rfc2631 was first published (1999) DH groups were very small my todays (2017) standards. I am using the 4096-bit group from Appendix A of rfc5054, which means that q is a 4095-bit number. So if I shorten the range to a whole number of bytes, I would need to get 511 random bytes (4088 bits). That is an enormous amount of entropy to be asking.

As noted in a comment, picking a number uniformly in a range (that isn't a whole number of bytes) means addressing the modulo bias. I would much prefer to not try to deal with the modulo bias and so just pick a whole number of bytes.

Related questions (and answers)

My question is related to – but distinct from –  Diffie-Hellman secret key choices, which is asking about some very specific values of generated keys.

It would be nice to just get a bunch of random bytes and make those
  into a big integer than to have to uniformly pick a big integer within
  a specific range.

If you pick a uniformly random value from a bigger set and throw away everything that is not in your range until you find something you will get a uniformly random value in that range.

If however you do something like taking a random big integer and reducing it modulo $q-2$ to put it into your range you will skew the distribution and you will lose some security.


Is this an acceptable All-or-Nothing Transform? I was thinking about AONTs, and designed the one below, I call it CHANT for Chained-Hash All-or-Nothing Transform; it's my very first shot at something of the sort, and was hoping I could get your opinions.

Suppose you have a hash function $H$ of block size (ie. the size of the generated hash) $b$, you'd like to "wrap" a message $m$; CHANT works as follows:

Break $m$ up into blocks of $b$ bits, call the resulting blocks $m_{1}$, $m_{2}$, $\ldots$, $m_{n}$.
Generate a random block of $b$ bits, call that block $m_{0}$.
Now, for each message block $m_{i}$ (with $1 \leq i \leq n$), calculate its wrapped block $w_{i}$ as $w_{i} = H^{i} (m_{0}) \oplus m_{i}$ (where $H^{i}$ denotes the $i$-th iteration of the hash function $H$).
Finally, calculate $w_{0} = H(w_{1} \Vert w_{2} \Vert \cdots \Vert w_{n}) \oplus m_{0}$, the wrapping will then be $w = w_{0} \Vert w_{1} \Vert w_{2} \Vert \cdots \Vert w_{n}$ (where $x \Vert y$ denotes concatenation).

Now in order to unwrap a CHANT-wrapped message $w$, one proceeds as follows:

Break $w$ up into blocks of $b$ bits, call the resulting blocks $w_{0}$, $w_{1}$, $w_{2}$, $\ldots$, $w_{n}$.
Calculate $m_{0} = w_{0} \oplus H(w_{1} \Vert w_{2} \Vert \cdots \Vert w_{n})$.
Now for each wrapped block $w_{i}$ (with $1 \leq i \leq n$), calculate its unwrapping $m_{i}$ as $m_{i} = w_{i} \oplus H^{i} (m_{0})$.
Finally, discard $m_{0}$, the unwrapping will then be $m = m_{1} \Vert m_{2} \Vert \cdots \Vert m_{n}$.

If $w_{0}$ is missing, then there's simply not enough information to retrieve the original random $b$ bits, if $w_{i}$ with $i \neq 0$ is missing, then with high probability, the hash value needed to retrieve $w_{0}$ will be incorrect.

CHANT is basically a (very simple) stream cipher which discloses the (random) encryption key given the wrapped message's hash.

As some of its (in my eyes) pros, I'd mention the fact that it requires nothing more than a hash function and a (pseudo-)random source (but see question 4 below), and that it's very easy to understand (for a layman like myself at least).

As one of its cons, I'd point out the need to add an additional block (ie. $w_{0}$) to the output.

Now, my questions are:

Have I missed something? is this really an AONT?
I'm sure there are faster / better approaches to AONTs, but is this terribly bad? is it any better than others in any respect?
What should be asked of the hash function $H$? collision resistance? pre-image resistance?
Is it having a (pseudo-)random source a bad thing? would it be any better if the construction above were to replace $m_{0}$ (randomly generated) by $H(m)$? would it be any worse? (at the very least, it would make the wrappings of two identical messages the same).

Thank you in advance, and sorry if I overlooked something trivial, it's my first post in this SX site.

Have I missed something? is this really an AONT?

An iterated hash doesn't make a secure stream cipher. If the attacker can guess $m_i$, they can calculate $w_i \oplus m_i = H^i(m_0)$, then decrypt the rest of the message by taking hashes of that value.

An option would be to use the hash function like a block cipher in counter mode $w_i = H(m_0||i)$. That should be secure.

  I'm sure there are faster / better approaches to AONTs, but is this terribly bad? is it any better than others in any respect?

If will likely be significantly slower than just using AES or a stream cipher for the encryption and a hash to make the key depend on the rest. Hash functions don't always produce a lot of output fast.

The advantage is that you only depend on one primitive. If you wanted that, you could use a hash function with a stream cipher mode, like Keccak (which SHA-3 is based on). That should be faster.

  What should be asked of the hash function H? collision resistance? pre-image resistance?

The hash function should be (first) preimage resistant and a PRF. Collision resistance doesn't matter unless the attacker can control or at least predict the random $m_0$.

  Is it having a (pseudo-)random source a bad thing? would it be any better if the construction above were to replace m0 (randomly generated) by H(m)? would it be any worse? (at the very least, it would make the wrappings of two identical messages the same).

No, it's a good thing. A deterministic $m_0 = H(m)$ would, for example, let an attacker verify any guess of the message $m$ with high likelihood from just a single $w_i$. Just transform the guess message and see if any block matches.


Finding Nonlinear boolean functions Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements. I wonder if there is any known algorithm/construction that, given any $n\geq 1$, returns a boolean function $f:\mathbb{F}^n_2\rightarrow \mathbb{F}_2^m$ (for some $m\geq 1$) such that:

$f$ is injective;
for each $S\subseteq \mathbb{F}^n_2$, with $|S|<n$, the image of $S$ under $f$, $f(S)$, is a set of linearly independent vectors in $\mathbb{F}_2^m$ (seen as a vector space over $\mathbb{F}_2$).

Both $m$ and the returned representation of $f$ should be "succinct", that is, of size polynomial in $n$.

The algorithm might also be probabilistic, in the sense that the two required properties might hold with "high probability" (possibly approaching 1 as $m-n$ grows).

One trivial possibility is to sets $m=2^n$, and defines $f(x)$ as the $m$-bit vector $y$ with
$$y_j=\begin{cases}
1&\text{if }j=\displaystyle\sum_{i=0}^{n-1}x_i\,2^i\\
0&\text{otherwise}
\end{cases}$$
where subscripts denote bit index.

Is that "succinct"? I can't tell for lack of a definition. We sure can make an $O(n)$ representation of $y$; in essence, $x$ will do!

If there was not the restriction $|S|<n$, we could take $S=\mathbb{F}^n_2$, with $|S|=2^n$, thus there would no solution with $m<2^n$.

Kodlu's answer is about making use of $|S|<n$ in order to minimize $m$, using coding theory. Also it shows there can be cryptographic applications.


Encrypting with Davies-Meyer hash function scheme So I need to to illustrate Davies-Meyer hash function for a message “123” with 1-byte blocks. I can use the extended ASCII representation where each character is represented as a byte. And I can pick the initial value of hash H0 as all zeros.

So far I've padded the message, but now I'm stuck and don't understand where to go from here. Here is what I have so far...

x = 123

l = 24 bits or 11000

[0000 0001][0000 0010][0000 0011][1][0000…0][0000…0001 1000]

The first block is "1", the second is "2", the third is "3", the fourth is the appended "1", the fifth and so on is 423 zeros, and the last block is the length of 24 bits, totaling 512 bits.

Now I'm thinking I gotta divide the 512 bit block into 16 words of size 32 bits. But I'm not sure how to do that or hot to apply the Davies-Meyer hash function to it.

Davies-Meyer is a compression function construction. You need to call a block cipher with your to-be-hashed data as the key and the chaining value as the plaintext. You then XOR the plaintext to the output of the block cipher call to obtain the next chaining value.


How secure is a system that retrieves encrypted private keys from a public database? The system in question is one with multiple users. Each user has a password associated with their account, and each user owns several public-private keypairs. A user's private keys are encrypted using the user's password, and stored in a publicly accessible database. A system like this would allow users to retrieve their public-private keypairs from any machine, and decrypt the private key using their password.

Assuming that a strong encryption algorithm was being used to encrypt the private keys (perhaps Blowfish/Twofish), what sorts of attacks might this system be vulnerable to?

PS: There are two ways I can think to encrypt the user's private keys.

Each private key could be encrypted and stored individually
The private keys could be aggregated into one file which is then encrypted and stored

In the first option, users would be able to retrieve keys individually, leaving the other keys encrypted and not risking their exposure. However this might lead to an association attack on the user's password, as there would be multiple cyphertexts all encrypted using the same key (the password). Aggregation of the private keys before encryption might help avoid this, but then the user would have to retrieve the entire file and decrypt all of their keys at once, potentially exposing all their secrets. Which of these two methods (or maybe there are more) would be more secure?

EDIT
So far, the answers to this question have mentioned deriving keys from the password and storing secret, randomly generated salts to be provided to the user upon login. These are great ideas that slipped my mind. However, what I failed to clarify was that the system database has all the data public with no stored, hidden fields. With such a system, it might be possible to implement this as a distributed P2P network, and would nullify the threat of data breaches (nothing to steal since it's all public).

With this requirement, storing secrets is impossible, and we should assume any algorithm used to derive keys from a password is public as well, to avoid security through obscurity. Because the deriving algorithm is public, it wouldn't add any security (in theory) to the private key encryption as opposed to just using the password as the key.

Lets say every user averages ~100 private keys. How realistic is an association attack on these cyphertexts encrypted with the same key if TwoFish were being used? Is brute forcing still the easiest path?

What about every user owning ~1 million keys? How many keys (about) would it take to make some sort of association attack plausible? And is there any way that this system could be hardened, like by somehow increasing the password entropy?

A user's private keys are encrypted using the user's password, and stored in a publicly accessible database.

A publicly accessible database like this can be easily corrupted through an offline dictionary attack because passwords often have very low entropy. This can be improved (but still hackable) by adding salts (that are also stored in the public database). This post introduces how to use salts to protect passwords: Can you help me understand what a cryptographic “salt” is?

On the other hand, I don't think encrypting a client's private keys with different keys (derived from the same password) help here because an adversary can easily crack all the derived keys if it finds the correct password.


Is one big file as secure as X small files with the same password? Hello people of StackExchange.

It's my first time asking and I know little about Cryptography, so be gentle.
My problem can be simplified to this:

I can create a 2GB Volume that contains 1GB of text files and 1GB of photos. It has the password 123.

Or I can create a 1GB Volume with 1GB of text files with the password 123 and a 1GB Volume with 1GB of photos, again password 123.

It seems to me that it makes no difference in security. If the attacker gets the password he gets all the files. But I may have oversimplified the issue. What's your take on it?

It depends on the possible attack vectors.

Generally password reuse is very dangerous. For instance, you could have less important files in one volume - say that the photos are less important. An attacker could ask you to show him a photo or two. You enter the password and the attacker performs classic shoulder surfing to get to know the password. Now the password is known for the important text files as well. Possibly you would not have entered the password if both sets of files were in one volume. This is one of the many reasons why you should not share passwords of internet sites either.

At the very least you'll have to enter the password twice to unlock all the files, it seems to me. So having two times the same password is less secure than having one whatever you do.

If you want to use one password: use a password manager, preferably on an unconnected device and unlock two highly complex and different passwords with the one used to unlock the database file.


Disk encryption with AES have few more questions about disk encryption with AES cipher:

Do we consider all zeros (0000000) as empty block of data or is it still a data?

Do we really need padding to the data blocks if a disk sector is multiplication of data block?

Also if one data block is empty (all 000000) why we just dont apply encryption on that block as usual?

Most of the disk encryption software let us to encrypt used space vs full disk. In case of full disk , how is the empty space being encrypted with AES?

is disk encryption always encrypt data into same location? lets say data from sector 200 will always land after encryption in sector 200? (assuming that we are not adding any HMAC which expands the data).

Does AES keep track which sector of disk is encrypting? Or this info is irrelevant for encryption? I think bitlocker in CBC mode adds IV as encrypted sector number - but is it to keep track on sector number or just to randomize the input (instead of sector number they could just add any random number)

Do we consider all zeros (0000000) as empty block of data or is it still a data?

Either it is a block of data or it isn't, there is no such thing as an "empty block". And yes, it is still data (data is always plural), as it has certain properties such as a size. For AES it needs to be 16 bytes of any value to be considered one block of data.

  Do we really need padding to the data blocks if a disk sector is multiplication of data block?

No, in most disk encryption protocols padding is not required (and the problem is where to store the encrypted block of padding as it doesn't fit in the sector).

  Also if one data block is empty (all 000000) why we just dont apply encryption on that block as usual?

As indicated, it is not empty, and we would use encryption as usual.

  Most of the disk encryption software let us to encrypt used space vs full disk. In case of full disk , how is the empty space being encrypted with AES?

Just like always. Note that empty space - or rather unused space is not necessarily put to all zero. For instance, a quick format only makes sure that the file system meta information is created, commonly at the start of the partition. The rest is left untouched.

  is disk encryption always encrypt data into same location? lets say data from sector 200 will always land after encryption in sector 200? (assuming that we are not adding any HMAC which expands the data).

Depends I guess. Usually you have two situations: encrypting an already existing file system structure and adding information to the file system. If it is encrypted then generally the sectors would probably stay the same for most software, although the physical location may still change (e.g. for an SSD with write leveling). And yes, that can be dangerous.

When writing new data to a "live" file system you'd expect that the data gets encrypted before it is written, so there is no "source sector".

  Does AES keep track which sector of disk is encrypting? Or this info is irrelevant for encryption? I think bitlocker in CBC mode adds IV as encrypted sector number - but is it to keep track on sector number or just to randomize the input (instead of sector number they could just add any random number)

The disk encryption uses AES, AES doesn't use disk encryption. AES is a block cipher algorithm and as such instances of AES doesn't know anything about what task it is performing, other than that required to encrypt or decrypt a single block.

Yes, the IV is just used to randomize the input.