Can you help me understand this exam answer related to “breaking discrete logarithm over P256”? I'm having trouble understanding the solution to a problem that tries to solve the discrete logarithm problem over an elliptic curve. It goes as follows:

  Consider an elliptic curve P256 generated by $G$ with size $n$. Consider function $H:P256 \rightarrow \mathbb{Z}_n$ that is used to build a random walk $P(i)$ as follows: $P(i) = W(P(i-1))$ with $W(P) = P + H(P)G$. Finally, consider a distinguisher function $D: P256 \rightarrow \{0,1\}$ (if $D(P) = 1$ we say that P is a distinguished
  point). Assume for all P and P' that $H(P)$ is independent from $D(P')$, $H(P)$ is uniformly distributed and $P[D(P') = 1] =\frac{1}{t}$.

  Consider the following algorithms:

Precom(t,m) -> L
for i = 1,...,m
 take P_0 = aG with a random
 compute P(0),...,P(l-1)
 until P(l-1) is in the set P(0),...,P(l-2) or D(P(l-1)) = 1
 if P(l-1) is in the set P(0),...,P(l-2) abort else add to L (P(l-1),log)

Dlog(Q)
loop
 set P(0) = aG+Q
 compute P(0),...,P(l-1)
 until P(l-1) is in the set P(0),...,P(l-2) or D(P(l-1)) = 1
 if P(l-1) is not in the set P(0),...,P(l-2) then
  (if (P(l-1),b) is in L then stop)
endloop

The question I'm trying to solve goes as follows:

  We assume that Dlog never finds a looping random walk (the condition "until $P(l-1)$ is in the set $P(0),\dots,P(l-2)"$ is never satisfied). We further assume that Precomp visited at least $\frac{nk}{t}$ points (for some value k, where t is the parameter of the algorithm). Show that the expected number of iterations of the loop in Dlog is at most $1+\frac{1}{k}$.

I even have the answer:

  An iteration repeatedly picks a new point. If new, this new point is distinguished with probability $\frac{1}{t}$. But the point is not new with probability at least $\frac{\text{number of visited}}{n} \ge k\frac{1}{t}$. So, each new point has a probability to be new and distinguished with less than $\frac{1}{k}$ times the probability of being not new. So, we reach a distinguished point from $L$ with probability at least $\frac{k}{k+1}$ and iterate with a probability less than $\frac{1}{k+1}$. So, the expected number of iterations is at most $1+\frac{1}{k}$.

What do I not understand from this answer? Well for starters how are they calculating the expectation? But the whole process is quite obscure. Also if you could comment on the usefulness of conditions of the kind:

  Assume for all P and P' that $H(P)$ is independent from $D(P')$,
  $H(P)$ is uniformly distributed and $P[D(P') = 1] =\frac{1}{t}$.

would be useful for me because I find them in many problem statements and I'm not always sure where I am using them.

Please feel free to enhance my $\LaTeX$ where needed. Also, if there is something you do not understand, don’t hesitate to post a comment asking for clarification. In case of doubt, you can see also take a look at the PDF describing the complete problem.

I hope I interpreted this correctly, as both the question here and the pdf are not completely clear to me. As the question seems to do, I will everywhere assume that the chosen walks are completely random.

The idea is that we are going to run the ${\tt Dlog}$ function, and we want to know the expected value of the number of times we have to iterate its loop. Suppose we start a loop, and we have chosen points $P_0,\ldots,P_{\ell-1}$. Three things can happen:

We have seen the point $P_{\ell-1}$ before.
We have not seen the point $P_{\ell-1}$ before, and the point is distinguished.
We have not seen the point $P_{\ell-1}$ before, and it is not distinguished.

This is an exhaustive list of options. Now let's suppose that if we are in 3, that we choose $P_{\ell}$ and continue the loop. Then after a while we are going to end up either in 1 or 2. This shows that every loop either ends up on a point which we have seen before (let's call this event $X$), or ends up on a point which we have not seen before, and the point is distinguished (let's call this event $Y$).

Estimating some probabilities:

Let's call $\mathcal{P}(X)=x$ and $\mathcal{P}(Y)=y$. Since these two options are exhaustive, we have $$x+y=1.$$
Since by assumption we visited at least $k\frac{n}{t}$ points, we have
$$x\geq \frac{1}{n}\cdot k\frac{n}{t}=k\frac{1}{t}.$$
Moreover, suppose we visited $v$ points, then
$$y=\frac{n-v}{n}\frac{1}{t}\leq\frac{1}{t}.$$
Combining the last two equalities, we conclude that $x\geq k\frac{1}{t}\geq ky$. Writing $x=1-y$, from this it follows that $1-y\geq ky$, and therefore that $y\leq\frac{1}{k+1}$. Thus $-y\geq\frac{-1}{k+1}$. From this we we have that
$$x=1-y\geq1-\frac{1}{k+1}=\frac{k}{k+1}.$$
Finally we conclude that $$\frac{1}{x}\leq \frac{k+1}{k}=1+\frac{1}{k}.$$

The final argument:

So why did we do all of this. Well, we have defined a "successful" event, namely $X$, and an "unsuccessful" event, namely $Y$. How many times do we have to repeat before we end up in $X$? This is a standard geometric distribution with probability $x$. It has expected value
$$\sum_{i=1}^{\infty}\left(i\cdot xy^{i-1}\right),$$
which is known to equal $\frac{1}{x}$. As $\frac{1}{x}\leq 1+\frac{1}{k}$, we are done.


Collision resistance of partial SHA-256 hashes XOR'ed My hashing algorithm computes the SHA-256 for each of 12 input strings and XORs them to get the final hash.

Is there a risk of an attacker being able to forge 2 sets of inputs that yield the same final hash?

To avoid trivial attacks by feeding in the same input twice and make this scheme order-dependent, I prepend each input with its index (binary 0 to 11).

For the case of 256 inputs there is an easy attack (as each hash can be used to control a single output bit using matrix calculus), this makes me wonder whether there are similar attacks for just 12 inputs.

I'm aware that there are more secure alternatives such as Merkle trees but I really need maximum performance especially for when just a single input is modified.

Let tne hashlength be $d$. With $k=12,$ this is the $k-$ XOR problem. Fix $k.$ If the vectors are randomly generated and form a list of size roughly at least $2^{d/k},$ there exists a solution with constant probability bounded away from zero. This is because a list of size $M$ contains $$F:=\binom{M}{k}$$ subsets of size $k,$ and thus as
$\{x_1,\ldots,x_k\}$ ranges over these subsets the function $f(x_1,\ldots,x_k):=x_1\oplus \cdots \oplus x_k$ ranges over $\{0,1\}^d.$

This is a $F$ balls into $2^d$ bins problem and if $F\geq 2^d,$ the probability that $f$ misses the bin corresponding to your given hash value
$h_0 \in \{0,1\}^d$ is roughly $e^{-1}\approx 0.37.$ Taking $M=\Omega(k 2^{d/k})$ is enough here. However, finding the solution is computationally more expensive.

Wagner (see here ) has a recursive binary tree based algorithm for the $k-$ XOR problem $$x_1\oplus \cdots \oplus x_k=0 \qquad (1)$$ with $k=2^m,$ with time and memory complexity essentially
$$O(k 2^{d/(1+m)}).$$ The zero vector on the right hand side of (1) can be replaced by any constant vector.

Let $x_9,\ldots,x_{12},$ be arbitrary and use Wagner with $k=8$ to solve the $8-$ XOR problem

$$x_1\oplus \cdots \oplus x_8=c,$$
with $c=x_9\oplus x_{10} \oplus x_{11} \oplus x_{12}\oplus h_0.$ This can be done with complexity
$$O(k 2^{d/(m+1)})=O(8 \times 2^{256/4})=O(2^{67}).$$


Is a LFSR sufficient for post-processing a biased TRNG? I am building a TRNG on a FPGA based on ring oscillators. I found out that Linear Feedback Shift Registers (LFSRs) are commonly used for the post-processing of TRNGs. Here is my initial design:

Let's say that the TRNG core block produces a biased output (e.g. more 1s than 0s or the value is more likely to transition between samples). Is the LFSR sufficient to unbias the input? Would unbiasing the input with e.g. a Von Neumann extractor be beneficial?
A related question is—since a biased input have less entropy—is the LSFR able to extract randomness over time by performing more shifts? If yes, how can we estimate the amount of bits that must be fed into the LFSR from a weakly random entropy source in order to have a strong output?
Edit: Clk is a clock which is slower, independent to the ring oscillator oscillating speed.

I'll assume the right 16 in the question's figure is to tell that the LFSR is unloaded 16 bits at a time; and unless otherwise stated I'll assume that's done every 16 clock cycles of the LFSR.

Is the LFSR sufficient to unbias the input?

Mostly yes, but that's not enough in crypto. It's desired to make the output undistinguishable from random (no just unbiased) for an adversary who knows the design of the system (here, that there is a 16-bit LFSR, and even which). That's per Kerckhoffs's (second) principle.

Is a LFSR sufficient for post-processing a biased TRNG?

Positively no, in an unspecified cryptographic context, and assuming full use of the output (see first paragraph).
Problem is that from the output of the LFSR, and it's design (feedback polynomial mostly), and perhaps it's initial state (see below), it's trivial to get back at the exact input of the LFSR, and from that take advantage of the bias for a distinguisher. If the LFSR output is used for something critical (e.g. generating a One Time Pad), that can be a disaster.
If the LFSR is in "scrambler" configuration, an adversary can feed the LFSR's output in the corresponding "descrambler", and that will output what was the scrambler's input. Exactly so if the descrambler starts in sync with the scrambler, or after the first 16 bits otherwise (a descrambler for and $n$-bit LFSR self-synchronizes after $n$ bits). In other words, that descrambler trick, that the adversary can apply, undoes what the LFSR in the question's generator did, thus the LFSR is not sufficient.
This is illustrated below. On top of the picture is the question's LFSR, simplified (serial output scrambled, $n=4$ stages). The bottom is the descrambler, added/simulated by the attacker. It should be apparent that after $n=4$ clocks, the bottom circuit is in sync with the top's, and descrambled is the input, with whatever detectable bias.

If the LFSR was in some other configuration (descrambler or "additive scrambler"), an adversary needs to guess the LFSR's initial state, if not known in the context (e.g. zero at reset). Even with no clue, attack remains easy: there are only $2^{16}$ possible initial states, and we can select whatever one gives the most marked bias for the reconstructed input, again making the LFSR not sufficient.
For something that works and still only uses a relatively small LFSR, we want to heavily undersample ("decimate") the output of a LFSR in scrambler configuration; e.g. keep one output bit out of 64 (almost equivalently, unload the 16 bits of the LFSR every 1024 clocks instead of 16). The general idea is the entropy is gathered/mixed in the LFSR between outputs. There's a trade-doff between quality of the output and output rate, controlled by the undersampling/decimation rate.
There's a simple theory for how much decimation is too little: if there is $h<1$ bit of entropy per bit out of the sampler, then anything less than $1/h$ bits into the LFSR stage for each bit out is too few. So if when in an experiment we capture the output of the sampler and feed that to a lossless compressor like bzip2, and it compresses by a factor of $c$ (e.g. $c=4$ for 100MiB compressed to 25MiB), then any decimation less then $c=4$ sampled bits in for one bit out of the LFSR stage is too little. Also, if at the output of the sampler we have bits with average $a\ne1/2$, anything less than $c=-1/(a\log_2(a)+(1-a)\log_2(1-a))$ is too few (beware this formula does not account for correlation between bits, and thus is next to useless except for extremely biased input).
Unfortunately I have no simple theory for how much decimation is enough, or how LFSR size matters! The standard recommendation is to be extremely conservative if the LFSR is the only mean to condition the sampler's output, or (better) conservative and use the LFSR to seed a Cryptographically Secure Pseudo Random Number Generator, using the output of that in the end. Also see last paragraph about the need to detect field failures.
I wish I knew exactly what condition (if any) on the LFSR in scrambler mode is necessary to insure no long term bias in the output (assuming no feedback from output to input, and independent bits in input [or even much weaker and plausible assumptions]). But even a 1-stage LFSR in scrambler configuration (feedback polynomial $x+1$, single D gate, 2-input XOR including input) does that. Followed by ample decimation, that's one of the simplest correct RNG post-processing.

Would unbiasing the input with e.g. a Von Neumann extractor be beneficial?

Most likely it would be beneficial. It would even work perfectly if the bits at the output of the sampler are independent. But

Absent that insurance, there can remain a detectable bias.
Output rate becomes irregular, with no minimum, and that can be a serious problem¹.

The first issue could be dealt with by cascading several Von Neumann extractors, but each state halves the average thruoutput and worsens the second issue. An LFSR in scrambler configuration followed by heavy under-sampling is more robust, and at least the throughput is predictable.
Beware that the hardest part in designing a Cryptographically Secure True Random Number Generator is not making it secure² when it works, but detecting when it does not work as intended (like because an attacker pours liquid nitrogen, or just some mundane corollary of Murphy's law), so that the overall gizmo remains secure.

¹ I once was involved with finding why some Smart Card accepting devices sometime got bricked on the field with some type of cards, degenerating into expensive consequences. It ended up being an overreaction by the accepting device to a failure in the ISO/IEC 7816-3 protocol, following a timeout: the card was sometime too slow to answer. According to the Smart Card manufacturer, that was due to random operating delays induced by a Von Neumann extractor (I doubt this is the full story of the card misbehavior but trust it involved irregular RNG throughput).
² It's still hard! Potential problems among many include unwanted feedback loops from conditioned output to the source/sampler.


Is it possible to have self-authenticated message? Consider a text with $n$ words which $m$ words of it can be replaced with an equivalent word. Therefore we have $2^m$ different texts with the same meaning.

For example "You are {so/very} {keen/eager}" has 4 different combinations with the same meaning.

Is it reasonable and possible to use this property for message authentication?

More precisely, knowing a key, only one of these texts can be authenticated. Actually, I do not want to add anything (like HMAC) to the text.

One solution is to use the choice of which equivalent message you send as a way to encode a MAC value.

Take a "base message", where e.g. each word choice is the alphabetically first one. (Or some other known rule.)
Calculate the MAC for that: MAC(key, message). The MAC should be $m$ bits or less. HMAC, possibly truncated would work fine.
Encode that MAC value in the word choices, so that each bit chooses one of the words.

The recipient would need to know the possible word changes (synonym pairs). They would first use the rule to derive the same base message, then compute the MAC using the shared key, and finally check that the same value is encoded in the word choices.

A similar algorithm would work for public key signatures if you had a sufficiently long message. The recipient would decode the signature value from the word choices and use normal signature verification with the base message and a public key.


Can you make a hash out of a stream cipher? A comment on another question made me wonder about something:

  Assume you're on a rather constrained platform — say, a low-end embedded device — with no built-in crypto capabilities, but you do have access to a simple stream cipher; say, RC4 or one of the eSTREAM ciphers.  What other crypto primitives can you build out of that stream cipher?  In particular, are there any practical ways to build a cryptographic hash function and/or a MAC out of just a stream cipher?

We already have questions about turning a hash into a stream cipher and about turning a stream cipher into a block cipher, but this particular transformation doesn't seem to have been covered yet.

Obviously, if the platform constraints permit it, one could ignore the stream cipher and just implement a standard hash function from the ground up.  What I'm wondering is whether having the stream cipher available might let one do better than that in terms of code size, memory usage and/or speed.

While a construction that treats the stream cipher as a black box would be nice, schemes that only use parts of the stream cipher (like RC4-Hash, which, alas, has practical collision attacks) would be interesting too, at least if they're simple enough.

A Pseudo Random Generator (PRG) and a hash function are both Pseudo Random Functions (PRFs), but they have different security considerations. (At least, historically they do. Moving forward some of them may be more closely aligned.) Due to this, building a hash from an existing PRG designed under older security constraints probably isn't a good idea for the intuitive construction of using the plaintext as the key to the PRG and the PRG output as the hash. See this nice summary: Why stream ciphers shouldn’t be used for hashing.


Do all AEAD implementations use symmetric key ciphers in practice? Everything I've seen so far in modern implementations (the Linux Kernel AEAD API, JVM crypto provider (AES-GCM), RFC 8439, libsodium, etc) seems to imply that only symmetric key block ciphers are used in practice for AEAD.  Are there asymmetric key algorithms that ensure authenticated encryption?

When people say "AEAD", they have symmetric schemes in mind. But conceptually, authenticated encryption is not restricted to symmetric keys. It is just the case that public key variants have not received much attention both in the literature and in practice. But there are implementations. For example, NaCl has an API for public-key authenticated encryption, based on security notions by Jee Hea An 2001. The construction is based on public-key encryption and MACs. This shows that AE in the asymmetric setting is fundamentally different from simply signing encrypted messages, as explained in the NaCL API docs:

The crypto_box function is not meant to provide non-repudiation. On the contrary: the crypto_box function guarantees repudiability. A receiver can freely modify a boxed message, and therefore cannot convince third parties that this particular message came from the sender. The sender and receiver are nevertheless protected against forgeries by other parties. In the terminology of https://groups.google.com/group/sci.crypt/msg/ec5c18b23b11d82c, crypto_box uses "public-key authenticators" rather than "public-key signatures."
Users who want public verifiability (or receiver-assisted public verifiability) should instead use signatures (or signcryption).

Apparently this API and the formalization in the paper do not include the "additional data" (AD) part of AEAD but I don't think there is a fundamental limitation. AEAD as a single primitive in the symmetric setting became popular only after 2001, so I believe Jee Hea An simply didn't think about "additional data" as a useful feature back in 2001.
I can only speculate but I believe one reason why authenticated public-key encryption has not received much attention is that (even unauthenticated) public-key encryption itself is a rarely used primitive. Public-key encryption is useful in a setting where the sender and the receiver are not online at the same time. The prominent example is e-mail encryption but unfortunately e-mail encryption never took off for various reasons (Johnny Still, Still Can't Encrypt), and protocols for e-mail security such as PGP/GPG and S/MIME conceptually separate confidentiality and authentication and implement them via public-key encryption and digital signatures (and not MACs!). Of course these can be combined ("sign-then-encrypt", "encrypt-then-sign" or "encrypt-and-sign") but the responsibility for doing so correctly is mostly pushed down to the user, and the 2001 paper shows that all of these constructions are insufficient. (One reason why PGP and S/MIME wanted signatures explicitly is that you can still have authentication for public emails, e.g., posts to public mailing lists.)
The success of the idea that we should consider authenticated encryption as single primitive with a single misuse-resistant API whose users do no need to be cryptography experts came only later in the symmetric setting after people screwed up in endless ways with constructions like "encrypt-then-MAC", "MAC-then-encrypt", "encrypt-and-MAC", which are the symmetric counterparts to the modes mentioned above. Note however that the symmetric and asymmetric settings are hard to compare when it comes to authentication, e.g., due to the mentioned subtleties with repudiability and public verifiability. MACs and signatures are very different beasts.


Attacker in a key exchange I'm having trouble with the following question:

  $X(A) \rightarrow B:(A,N_X)$
  $B \rightarrow X(S):(B,((A,N_X,T_B),K_{BS}),N_B)$
  $X(A) \rightarrow B:(((A,N_X,T_B),K_{BS}),(N_B,N_X))$

  Give two very good reasons why this attack works, in terms of the properties of the messages being exchanged and their content.

$X$ is the attacker in this case.

$A$ and $B$ are the names of two agents, $S$ is the name of a trusted server, $N_X$ denotes a nonce created  by entity $X$, $T_X$ denotes a timestamp created by entity $X$, $K_{XY}$ denotes a key shared between entities $X$ and $Y$

If anyone can help at all, I would greatly appreciate someone going through this question with me step by step.

From this I have understood that $B$ relays the encrypted message back and thinks everything is okay. The attacker doesn’t care about verifying the message. It gets the key and communicates with $B$ where $B$ thinks it is $A$ who has got the key through the server.

I just want to make sure that i have understood it correctly.

I think that this notation "$(A,N_X,T_B),K_{BS}$" isn't correct and must be transcripted as "$(A,N_X,T_B).K_{BS}$", which could be interpreted as the resulting cipherText of "$(A,N_X,T_B)$ under the Key $K_{BS}$".
Under these conditions, we could try to understand that the attacker X begin by impersonating A, by sending to B the plainText $(A,N_X)$

X: Impersonating A:    X(A) -> $(A,N_X)$
B: Ask the Server to generate a shared key for A and B, But the message is intecepted by the Attacker who doesn't know the Master Key $K_{BS}$
The attacker then return back the initial cipherText to B, who can easilly decrypt as he knows its shared Key $K_{BS}$ with the trusted third part.

But there is a problem, this protocol doesn't work, because there is no generation of shared Key by the Server for A and B, and then B after checking the existence of Nonce and TimeStamp, and the absence of shared Key, must logically abort the session, under the assumption that a master Key is never and NEVER send in a plainText.


Meaning of "integers modulo 4 " in "Fully homomorphic encryption modulo Fermat numbers" scheme My question refers to the paper "Fully homomorphic encryption modulo
Fermat numbers" by Antoine Joux. On page 3, the author describes a basic concept of the system:

  As many FHE systems, we deal with noisy messages. In our case, the high
  bits of each block are used to hold significant bits, while the low bits contain
  noise. A fundamental identity that makes the system work is that given two bits
  x and y , we have:
  x + y = 2(x ∧ y) + (x ⊕ y).
  Thus, if we can add the values of two bits as integers, or even as integers modulo 4, we are simultaneously computing an AND and a XOR gate.

I don't understand the difference between "integers" and "integers modulo 4". If we have only two variables which hold a single bit, the sum of both can be a maximum of 2. So what is the necessity to use a modulo 4 ring? And why not modulo 3, modulo 8 or any other number?

"Integers modulo 4" is usually the finite ring $(\Bbb Z_4,+,*)$ which internal laws are

+ | 0 1 2 3     * | 0 1 2 3
--+--------     --+--------
0 | 0 1 2 3     0 | 0 0 0 0
1 | 1 2 3 0     1 | 0 1 2 3
2 | 2 3 0 1     2 | 0 2 0 2
3 | 3 0 1 2     3 | 0 3 2 1

but here, the question's citation only deals with the finite group $(\Bbb Z_4,+)$.

  difference between "integers" and "integers modulo 4"

In the later, everything is reduced to four values, which can be expressed on two bits, the two lower bits of normal integers.


Can private key be specified on key pair creation? Without regards to any specific implementation of asymmetric cryptography, I am wondering if it is feasible to come up with a value of private key I want to use, and calculate the corresponding public key from it.

The use case would be the creation of multiple private/public key pairs where the private keys are merely the concatenation of some masterSecret and the pair ID (the latter is publicly known). This way, whoever knows the masterSecret also knows all the pairs' private keys. This, in essence, makes the owner able to have multiple public keys linked to just one private key, which is ordinarily not possible.

Which asymmetric cryptography implementation/algorithm is reasonably practicable for this purpose, given that typical use for the calculated pairs would be SSH-like authentication?

You can use Elliptic Curve cryptography. Here the private key is a vector $d$ ($s$ is also used sometimes) and the public key $w$ is calculated using $(x_w, y_w) = d \cdot G$ where $G$ is the base point (part of the domain parameters) of the elliptic curve.

To generate the key from the master secret you can just use $K_O = \operatorname{KDF}(K_I, C, L) \mod N$ where the input keying material $K_I$ is set to the masterkey and the Context or OtherInfo $C$ is set to the pair ID. Finally $L$ is the output size in bits, it should just be set to the number of bits in the curve so that the output key material $K_O$ will have the correct size. HKDF-expand would be a KDF that is a good fit for performing the key derivation.

The one thing missing is that you should convert the output to a value between $0$ and $N$ with $N$ the order of the curve. There is a description on how to do this in NIST SP-800-90 Arev1, appendix A 5.3 (the simple modular method). For most curves simply performing $d = K_O \bmod N$ should also return a private key that is random enough (what I would call the simplest modular method) but beware of attacks against certain schemes, sometimes it is worth to go the extra mile.

Note that there is a drawback to creating key pairs this way: the $\operatorname{Gen}$ function is often designed to use a random number generator, not a static value. The generation of private keys may also change between implementations (e.g. big / little endian machines, functions to test the random number generator etc.). So you need low level access to the private and public key generation functions (or just to the point multiplication function, of course).

It would not be too hard to extend this answer to include e.g. keys for schemes based on the Discrete Logarithm problem (i.e. Diffie-Hellman). RSA has a complex key generation function that you probably do not want to use for this.


Suitable 16-bit checksum? I am writing a toy1 transport protocol and I am trying to implement a feature whereby:

A 16-bit checksum is included in every packet.
This checksum can be extended to be 48-bit if the data is large, integrity is important, or whatever (creating this mostly for fun).
This checksum is intended to protect against errors, not a determined attacker.

My initial thought was to use a well known algorithm such as MD5/SHA2 and simply take the first/last 16/48 bits. This raises a few questions:

What are the consequences of simply taking a "substring" of a checksum? I assume, perhaps naively, that it would just increase the likelihood of a collision.
Is there any reason to prefer taking the last x bits instead of the first x bits, or vice versa?
When truncating a checksum like this, does SHA actually perform any better than MD5? Keeping in mind I am concerned with errors, not attackers.

[1] That is to say, I'm creating it for the purpose of learning. So "just use UDP" or "just use TCP" does apply, but that's why I'm not.

[2] Maybe use MD5 if it's 16-bit, SHA if it's 48-bit.

You can use a 16-bit truncation of MD5 or SHA-1 or SHA-256 or SHAKE128 as a checksum, but it's not a good checksum.
Why not?  Let's model them by a uniform random function of $t$ bits, which is a reasonable model in this scenario.  In this case, $\Pr[H(x) = h] = 1/2^t$ for any message $x$ and hash $h$, and every $H(x)$ is independent for each distinct $x$.  Thus, the probability of failing to detect an error $e$ in a message $x$ is $\Pr[H(x + e) = H(x)] = 1/2^t$ for any message $x$ and any error $e$.  This is the best error detection you can hope for from a hash function designed like a random oracle (or close to it, length extensions notwithstanding).
If you choose a good 16-bit CRC (preprint, paywall-free; web site), then you can be guaranteed:

any error of odd parity will be detected, provided the generator polynomial has $x + 1$ as a factor;
any burst error of up to 16 bits will be detected, except an error of the generator polynomial itself, provided the generator polynomial does not have $x$ as a factor (i.e., has a nonzero constant term);
many errors of up to a certain Hamming weights in data words of up to a certain size will be detected.

Cryptographic hash functions designed for random oracle use like MD5, SHA-1, SHA-256, SHAKE128, etc., guarantee none of these.  They're also often much more expensive to compute than error-detecting codes like checksums, because you're paying an extremely high cost for collision resistance which is of no concern for error detection.

What are the consequences of simply taking a "substring" of a checksum? I assume, perhaps naively, that it would just increase the likelihood of a collision.

Collisions are not relevant here.  The only thing that is relevant is the probability of error detection.  Any substring of MD5 or SHA-1 or SHA-256 or SHAKE128 is as good as any other.

Is there any reason to prefer taking the last x bits instead of the first x bits, or vice versa?

No.  If this led to an appreciably different probability of error detection, then that would be a noteworthy result about the hash function.

When truncating a checksum like this, does SHA actually perform any better than MD5? Keeping in mind I am concerned with errors, not attackers.

No.  They're both bad choices for detecting independent random bit errors.


Clarification of the terms "brute force" and "guess" In the answer to the question “What exactly is a negligible (and non-negligible) function?”

There is a part in the explanation that – as far as my knowledge goes – is conflicting:

  But instead of brute force, the adversary can guess (a polynomial number of) random values and hope to chance upon the right one.

From what I understand, a “brute force attack” attempts to guess (to exhaustion)… or am I missing something here? Can someone please explain the distinction in this context?

The difference in that answer is that brute force refers to an exhaustive guessing attack (having guaranteed success but requiring exponential time) whereas guessing (a polynomial number of) random values refers to exactly what it says (requiring polynomial time but having only a certain chance of success).


Is SipHash cryptographically secure? I'm evaluating different hash algorithms for use in my application. One of the kind of algorithms I am looking at are cryptographically secure ones to protect against DOS attacks.

SipHash seems pretty great, but the creators seem very careful to not call it "cryptographically secure".

In the SipHash paper (PDF), they call it “cryptographically strong”, but not secure. Is there any reason to trust SipHash over SpookyHash if both have no known DOS attacks and neither is “cryptographically secure”?

A fast 64-bit hash cannot be completely secure, since a $2^{32}$ brute force collision search is completely doable, and even a $2^{64}$ preimage attack could be feasible.

As a MAC used for hash table keying, that doesn't really matter (unless you leak the key). Finding just a few collisions isn't a problem and gathering statistics for an attack would probably already constitute a DOS attack.

That is to say, SipHash isn't a secure hash function, but should be a strong PRF and thus a secure MAC.


Key Length vs KeySpace I am a newbie here, this is my first post.

I have searched the forum but I haven't found a clear answer to this.

In general. What is the relationship between key length and the keyspace? (if there is any at all)

For example, with the Simple Substitution Cipher, I understand that the keyspace is 26! (because there are 26 characters in the English alphabet)

The key length is 26? (due to 26 characters in the english alphabet) Is it?

The keyspace seems to be quite long, isn't it? so looking at the keyspace the 'Simple Substitution Cipher' would be quite secure.
But looking at the keylengh, being only 26 long, how could this be considered secure by today standards?

Could anyone shed some light here?
Again, sorry for my naivity if I am missing something important here.

Thanks in advance

Key length is the length of the key. It's a term whose meaning has evolved over time; these days, it typically means length in bits. With digital symmetric ciphers, it's fairly simple, because those tend to have a key that's just a string of some number of bits, and any string of that length is a valid key. With RSA, it's more complicated - the key has a bunch of elements, and can be written in various formats or with more or less info. With algorithms like that, there's generally some standard thing whose length is the key length (with RSA, it's the modulus).

The key space is the set of all possible keys. With symmetric ciphers, where any string of $n$ bits is a valid key, the key space has $2^n$ elements. With asymmetric ciphers, it's more complicated.

With monoalphabetic substitution ciphers, you have $26!$ keys, but key length depends on how you're expressing the key. If you compress the key as much as possible, you can fit it in 89 bits ($2^{88}<26!<2^{89}$), so if you want to directly compare key length with other symmetric algorithms (to talk about brute-forcing) you'd say it has an 89-bit key. Expressed another way, it has a 26-letter key, but not all 26-letter keys are valid keys (AA...AA isn't, for instance). But letters are not bits; if each letter is encoded in 5 bits, this is a 130-bit key, but very few of the 130-bit keys are valid. That's why you'd look at the smallest you could possibly make the key, which is 89 bits.

This is actually reasonably long; it's weak by modern standards, but in the 1980s and 1990s would have been fine. The issue is that you don't attack it by brute-force, but by cryptanalysis; that means key length is a bit beside the point.


Password re-use by another person or on another service How does having the same password in different services make it less secure? How does having the same password as someone else make it less secure? Very basic question that I've always wondered about; I've been reminded by GitHub recently seen this message,

  The password you provided has been reported as compromised due to re-use of that password on another service by you or someone else.

and,

  Generate a unique password for GitHub. If you use your GitHub password elsewhere and that service is compromised, then attackers or other malicious actors could use that information to access your GitHub account.

Theoretically, how would that work? Shouldn't a different salt render it almost useless to any attacker?

  different salt values will create completely different hashed values, even when the plaintext passwords are exactly the same [Wikipedia]

Salt is usually stored along with the hashed password. When an attacker knows that your password is "abc123" in "pqr.com", he can try your username and password "abc123" in site "efg.com". Now "efg.com", would retrieve the stored hash against your username and extract the salt from it. Then the extracted salt is used to calculate the hash of the entered password and then matched with the stored hash.

The purpose of salt is to ensure that just by looking at two hashed passwords, the attacker can't tell whether they are same or not.

Salt is not a secret. The only requirement is, it has to be unique within a given DB. Its existence is just for preventing the attacker to prepare a pre-computed lookup table with passwords and their hashes to do a dictionary attack. But if the password itself is known to the attacker, salt cannot save the user.


How to prove that I am part of a list without revealing my identity? Let's suppose and scenario like a secret voting scheme, at the ID verification step.
Considerations:

There is a public list of identities of people who are able to vote (ex, people who live in a certain town).
The identity confirmation process is entrusted to a central server (Bob).
Users send requests remotely and decentralized (ex, with their respective devices).
The idea is that the ID is never sent via the communication channel.
The is no specific ID method, could be anything that does the task, digital signature, etc...

Conditions to be met

The Alice (the voter) must prove to Bob that she is on that list without revealing her identity.
The Bob (the server) has to ensure that no one who is not on the list can access to the voting.

How this problem is called and what is a practical example of the solution?
PD: The voting execution process is not important in this problem, it only deals with identity verification.

The scheme that solves your problem is called Zero Knowledge Proof of Set Membership
ZKP for Set Memberships use Accumulators. Crypto++ library provides an implementation of the accumulator


How would I convert committed coordinates $x$ and $y$ to a commitment of the EC point without revealing the point (in Zero Knowledge) or vice versa? I am working in the secp256k1 elliptical curve, though I suspect this would apply to any elliptical curve.  I have a Pedersen Commitment of the $x$ and $y$ coordinates in some discrete log scheme with generators $g$ and $h$. The point described by $x$ and $y$ is equal to $G^n$, where $G$ a public generator and $n$ is a secret (using exponentiation to represent point scalar multiplication on elliptic curves). Is there a method to get from the $g^x h^{r_1}$ and $g^y  h^{r_2}$ to $G^n H^{r_3}$, where $H$ is a second generator in the curve and all $r$ values are secret random numbers, using Zero Knowledge Proofs where needed?  A method in the other direction, going from the commitment of $n$ to a commitment of the two coordinates $x$ and $y$ would also be applicable.  I haven't been able to find such a proof in my research and I have not been able to think about how to create one.

My goal is to design a Zero Knowledge Proof of Knowledge of the private key associated with a public key which has been hashed (using the Bitcoin address hash) in such a way that the only public information is the environments (generators, settings, etc) and the result of the hash function, as well as all associated functions like the Bitcoin Hash. This proof can be used to prove ownership of a non-spending Bitcoin account without revealing the public key. If someone has done this, then I guess the question is moot and I will reference an applicable paper instead of designing it myself, thus a link to any such paper would also be an acceptable answer to this question. Unfortunately, I have not seen such a paper myself in my research.

EDIT:

I should also note that before the commitments of the coordinates were in the form $g^x h^{r_1}$ and $g^y h^{r_2}$, they were two lists of bitwise commitments that were homomorphically combined to become $g^x h^{r_1}$ and $g^y h^{r_2}$.  I did not lose those commitments, so they are available.  It was probably a mistake to suggest combining them, as it could introduce problems in performing operations on them due to differing orders between groups.

It's quite useful that you included yuor actual goal in the question, to avoid the XY problem.

  My goal is to design a Zero Knowledge Proof of Knowledge of the private key associated with a public key which has been hashed (using the Bitcoin address hash) in such a way that the only public information is the environments (generators, settings, etc) and the result of the hash function, as well as all associated functions like the Bitcoin Hash.

If we assume that pulic parameters are known by everyone, you only give the verifier a single piece of information: The hash-value of the public key. And here it is quite irrelevant what kind of public key is used - you need a ZK proof for a preimage under the according hash function.

I am not sure what you mean with "all associated functions like the Bitcoin Hash". But the goal here seems to be keeping the identity of the Bitcoin account secret, so I guess that additional information does not reveal the public key either.

  This proof can be used to prove ownership of a non-spending Bitcoin account without revealing the public key.

Actually, this is probably wrong. The reason for this is, that knowledge of a preimage under a hash function does not guarantee that the preimage is actually a valid Bitcoin account. For that you would need a different ZK proof, in which the verifier actually needs the according public key.

In the setting of Bitcoins, I think your agoal is not achievable. What you actually would need is a proof for membership of a group, e.g. the group of owners of valid accounts, and I can imagine that being possible - if the system is designed that way. This would be similar to group signatures, etc. But without an according setup, I don't see any way to achieve your goal.

Regarding your idea with the commitments and the EC public key:

You have two Pedersen commitments $a = g^xh^{r_1}, b = g^yh^{r_2}$ and then $c = G^nH^{r_3}$, which is like a Pedersen commitment but not in a prime order group but an elliptic curve.

Now, regardless of what $x$ and $y$ actually are, $a$ and $b$ could potentially be any element of the group, because the Pedersen commitments are perfectly hiding. So maybe you can generate $G^nH^{r_3}$ somehow from $a$ and $b$, but that will definately reveal $n$ itself and it has actually no relation to $x$ or $y$.


What does "constant rate" mean in universal composable commitment scheme? I'm wondering what does the "constant rate" mean in universal composable commitment scheme? I have known the rate of a commitment scheme is message length divided by the communication complexity of the scheme. What's the "constant" mean here? Must the constant be a number less than 1?

Constant rate in general means that the overhead from a non-secure method is constant. So, in a simple way, if I am committing to an $\ell$-bit message, then the size of the commitment is $O(\ell)$. In some cases, however, one also allows an additive factor that is independent of the message size. Thus, for example, it could be that to commit to a message of size $\ell$ the amount is $O(\ell)+{\rm poly}(n)$, where $n$ is the security parameter.

Note that typically these are measured in an amortized manner. So, you have to send many commitments (or a long message) for it to be true. But, again, this depends on the exact scheme, so you'll have to read the details.


Would it be safe to use the message hash as the IV in ChaCha? This seemed like an option if the hash is unpredictable.

It could be the hash of the message or the hash of the message + some common secret (apart from the key).

The only circumstance in which the hash would be predictable is when the message is the same. In that case, looking at the same nonce/hash wouldn't provide the attacker with any new information.

So it seems like a hash could work like a random number. Would it be safe to use the message hash as the IV in ChaCha?

First, this is not safe with ChaCha because the ChaCha nonce is only 64 bits long, since ChaCha nonces are normally chosen sequentially, so there would be a nonnegligible danger of collision with a reasonable number of messages.  Let's say XChaCha instead, with a 192-bit nonce, which is large enough to choose at random without danger of collision.

The recipient must know the nonce in order to decrypt the message, so we presumably have to transmit it alongside the ciphertext.  Call the hash $h$; the ciphertext is $E_k(h, m) \mathbin\Vert h$, where $E_k(h, m)$ is the XChaCha encryption under key $k$ and nonce $h$ of the message $m$.

If you use a fixed public hash $h = H(m)$, such as SHA-256, then the ciphertext $E_k(h, m) \mathbin\Vert H(m)$ reveals information about the plaintext that the adversary can exploit: they can confirm a guess about what a plaintext was, e.g. Attack at dawn! vs. Attack at dusk!, by evaluating $H(m)$ themselves on their guesses and checking.
If you use a secret hash $h = H_\kappa(m)$, such as keyed BLAKE2s-192, you have a kind of MAC-and-encrypt composition.  The adversary doesn't know the secret $\kappa$, and so can't confirm guesses.  It doesn't quite achieve the security goal of authenticated encryption because if you repeat a message, the ciphertext will be repeated too.  But that's the only leak that a cost-limited adversary will get, as you observed.
If you add a nonce parameter back into your system and use a secret hash $h = H_\kappa(n, m)$, then you get a nonce-misuse-resistant authenticated cipher.  If you never repeat a nonce, it's authenticated encryption; if you do repeat a nonce, whether accidentally or cetaceaously, repeated ciphertexts are the only leak that a cost-limited adversary will get as above.

This is an SIV or synthetic initialization vector scheme, similar to others on the market like AES-SIV, AES-GCM-SIV, and various CAESAR gladiators with names that are too cool for a bird like me to remember.  Using BLAKE2 won't beat any speed records—with BLAKE2, you pay for collision resistance, not just pseudorandomness—but it'll do the job if those are the parts you have on hand.  A much faster approach might be to use a universal hash family to compress the message into 256 bits, say hash256, and feed that through a 256-to-192-bit PRF; one could probably do better by exploiting the structure of XChaCha as a composition of ChaCha and HChaCha.


Is there really any way to nullify or avoid MITM attacks? The question pretty much sums it up.

Is there any way to make an attacker who is successfully performing an MITM attack to actually not be able to read or change the messages? Assuming there is no pre-attack key transfer or an agreed upon key that isn't transferred mid-attacking conversation.

You can't get a man-in-the-middle (MitM) resistant channel out of a vacuum.

You need some common knowledge beforehand. Luckily all one needs is a shared trust relation.

Suppose the server Steve trusts Carol, suppose further the client Charlie trusts Carol aswell.

As an example I'll give a simplified TLS-RSA key exchange because it's particularly easy.

First Steve needs to submit his public RSA key to Carol for certification. Carol digitally signs Steve's key and embeds in an certificate tying his name ("Steve") to his public key. It is assumed that Charlie can verify Carol's signature. This only needs to be done once.

Charlie now initiates a connection to Steve containing the request for communication and specifying the available cipher suites Charlie supports. They contain informations on how to encrypt and authenticate the data after the key-exchange is finished. Further a random number will be sent in the initial message. Steve will answer with his selection of the cipher suite and his random number.

In the next step Steve will send his certificate. Charlie will verify the certificate by checking Carol's signature and if it's valid will accept the key to be from Steve. Now Charlie randomly chooses a random "pre-master secret" and encrypts it using Steve's public key. He sends this to Steve. Charlie now derives the master secret from his random number, the pre-master secret and Steve's random number.
Now Charlie sends a message indicating that from now on the selected encryption methods shall be used. He finishes this messages with a message authentication code (MAC) on all previous data using the master secret as key.

Only Steve will be able to decrypt this pre-master secret. He decrypts it and derives the master secret himself. Now he verifies the MAC he received. Next he sends the message indicating he's ready to use encryption. He finishes with the same MAC (on all previous data).

Charlie verifies it and can be assured that no MitM attack has taken place because only the holder of the private key could have sent the MAC and he knows that Steve is the holder of the key because Carol confirmed it via the certificate.

Now a standard pre-shared key data exchange protocol starts (a.k.a. "record layer" in TLS terms)

TL;DR: You use digital signatures to bind public keys to identities and use those keys to construct secure key-exchanges.


What is the overhead of GCM? And how are GCM tags signed by RSA/PKI? I'm mainly trying to wrap my head around the pipeline of encryption, hashing and signing.
I've read over this question, describing the overhead of GCM, which I understand to be configurable for space-efficiency at the cost of security, but will be at most 196 bits.
This article by IETF, describing the overhead of TLS, appears to state that the GMAC/MAC is 128 bits long - which I'll understand as an average value
-----------------------------------------------------------------
AES_128_GCM, AES_256_GCM
-----------------------------------------------------------------
Per-packet overhead (TLS 1.0, 1.1, 1.2)                  29 bytes
   TLS header                                             5 bytes
   Explicit Nonce                                         8 bytes
   GMAC                                                  16 bytes
-----------------------------------------------------------------

My first question is: If we're using the cyphersuite TLS_AES_128_GCM_SHA256; and GCM is using Encrypt-then-MAC (which appears to be always?) and is configured to use a 128-bit tag; and AES_128 is encrypting plaintext in blocks of 128 bits; then is GCM adding a 128-bit tag onto each one of those blocks (thus, halving the amount of cyphertext that can ultimately fit into the data payload of the L3 packet)? Or, is each tag XORed (or transformed in someway) into the next, to produce a single 128-bit tag (2) that is the result of all the previous operations?
The Wikipedia page for GCM repeatedly mentions "authentication", however it seems to be using it in place of "integrity" - ie. ensuring data hasn't been manipulated/corrupted in transit. I have a very basic understanding of the three types of EtM/MtE/EaM functions, of AEAD and of PKI... so my second (multi-part, sorry...) question is:
How/where exactly is SHA and RSA (or any signature algorithm) used in this process?

SHA I know to be a hashing algorithm - used in HKDF during the initial DHKE. It's also used to create small hashes/"fingerprints" of large pieces of data, such as Certificates - which I suppose are then signed by the private key of the private/public RSA key pair for the sake of "authenticating" each message/session.

(1) Is the RSA private key used to sign the tag/tags after they're generated, or are they used in the generation of the tags themselves?

(2) Is the RSA private key of the sender used to "sign" each tag of each block, or just the single 128-bit tag after the whole payload of plaintext is encrypted?

(3) Is the client signing hashes/MACs as well after communicating their public key, or is that usually only done by the server/owner of a signed RSA Certificate?

This thread seems to state that symmetric keys are used instead, but discussion kind of made me more confused.

If we're using the cyphersuite TLS_AES_128_GCM_SHA256; and GCM is using Encrypt-then-MAC (which appears to be always?) and is configured to use a 128-bit tag; and AES_128 is encrypting plaintext in blocks of 128 bits; then is GCM adding a 128-bit tag onto each one of those blocks (thus, halving the amount of cyphertext that can ultimately fit into the data payload of the L3 packet)?

No, the GCM is performed on the entire record; hence the overhead added by the GCM tag is 128 bits per record.  That is, the GCM encryption operation is given the plaintext (which is the original unencrypted record), the AAD (which is made up by the record header plus the record sequence number) and the nonce (the 8 bytes given in the record plus 4 bytes from the key negotiation step), and it produces the ciphertext (which is exactly as long as the plaintext) and a 16 byte GCM tag.  TLS doesn't worry about what GCM does to perform this operation.
The table you cite gives the overhead per record (however, it is mislabeled as per packet; TLS records do not correspond to 'packets'; there may be several records per TCP packet (segment), or a single record may extend over several packets).

How/where exactly is SHA and RSA (or any signature algorithm) used in this process?

SHA and RSA are not involved at all during the record encryption/decryption process, so none of your three options describe the situation.  They may be used (and generally are) during the connection set up phase (which verifies that the server is who he claims to be (and optionally the client as well), and also generates the symmetric keys that GCM uses.


Practicality of codebook in current-day secret communications Codebook appears, if I don't err, to be an antiquitated topic rarely touched upon in discussions of modern cryptography. Couldn't codebook nonetheless be of high practical utility and even be extremely advantageous in certain critical fields of modern secret communications? Consider e.g. the hypothetical situation where a manager has to securely correspond with his representative who is negotiating with the customer in a bid under rival competitions. It seems that the essential instructions and responses could be realistically formulated as sentences and phrases of an appropriately designed codebook having entries of, say, 256 in number. That is, one needs only to suitably employ a highly limited number of code words in entirely neutral appearing text messages or to otherwise transmit somehow a small number of bits denoting the indices of the involved sentences or phrases in the codebook in certain appropriate way (e.g. the scheme http://s13.zetaboards.com/Crypto/topic/6939954/1/). It may be remarked that the codebook need not be static but can preferrably be dynamic, i.e. the mapping between the codewords and their meanings is dependent on a session key, being a random permutation (Fisher and Yates algorithm or alternatives) determined by it. The codewords are preferrably to be chosen to be certain commonly employed words, e.g. surnames etc. in order to ease the composition of a fairly natural covertext. In case it is desired to have integrity check, one could employ two disjoint sets of codewords that are independently permuted w.r.p.t. the set of meanings so that each meaning (or only those meanings that are classified as important) will be trasmitted via the coexistence of at least one keyword from each set.

Thus seen, top secret communication isn't necessarily a hard problem, or is it? Since no encrypted stuffs are involved, the scheme avoids from the outset issues like enforcing delivery of encryption keys or implanting of "official" backdoors (cf. news of a current debate in US on Apple's phones.)

I believe the possible advantages of the principles behind a codebook are:

Can be memorized by humans.
Can be used in normal speech (e.g. over the phone/radio/in normal conversation) or in text (e.g. in a newspaper)
The data is compressed: it can replace longer phrases or concepts with shorter ones.
Plausible deniability: It's possible to deny any code exists at all.
As long as a specific code is only used once and the codebook is kept secret, it's perfectly secure.

So some uses would be for:

Military operations (e.g. "Execute Plan A" would be meaningless to enemies and also allows faster execution of the plan than having to detail it)
Communication to people with no high-tech equipment, e.g. resistance groups with only access to radios/tv.
Groups of people who want to stay anonymous referring to each other by a nickname.
Criminal organizations who do not want to be openly on record talking e.g. about drugs or plans.


Algorithm for generating OAuth tokens I'm trying to find a good algorithm for generating authorization codes, access tokens and refresh tokens in an API.

Currently, I am looking into the following setup:

Tokens are generated using the RNGCryptoServiceProvider class in C#. (I have limited the allowed chars to the following set:  abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNOPQRSTUVWXYZ0123456789!@$?_-)

Authorization codes are generated with 256-bit length and have a lifetime of 5 minutes.
Access tokens are generated with 512-bit length and have a lifetime of 1 hour.
Refresh tokens are generated with 2048-bit length and have a lifetime of 60 days.

Those codes and tokens are then salted with a random 64-bit salt, and then hashed using SHA-256 before being stored in the database.

Considering the token lifetime, salt and hashing algorithm used, would this be a reasonable secure setup?

Your setup is secure. However it is largely "unneccessarily" secure.

First the generation method: You're using the RNG-CSP which is (I guess) Microsoft's software interface to the Windows secure PRNG, so this is fine.

Now for your tokens:
You're restricting the character set, which reduces the possible entropy per byte, but is fine if you're in a Web-Context. Note that you "only" have about 6 bits of entropy per byte (8 bits).
Your tokens are however too large. The standard security levels are 128, 192 and 256 bit security with 256 being considered secure as long as we're stuck in our solar system and don't discover any fancy energy source except our sun. Your current token sizes provide 192, 384 and 1536 bit security which is unneccessarily large in the latter two cases. I'd suggest changing the token's lengths to 384 bit. If you want, you can keep your short-time tokens at 256 bit or you can also raise the size if you feel 192-bit security (secure for a few decades at least) isn't enough.

Your choice of the hash is fine, SHA-256 provides 256 bit pre-image resistance which is just what you seem to want. Larger hash functions may be an option for you if you want to have more than 128-bit security against quantum computers, which would require you to use SHA(-3)-512

TL;DR: The long tokens may be shortened to 384 / 256 bit length, the rest is fine.


how to get the file used to brute force any encryption method Bitlocker as example uses AES 128 Bit encryption as default - if it was brute forced how it can be done , I mean where's the file that will be brute forced to generate the password (If I'm right that file is suppose to be the 128 keys generated from the encryption right?)
 I'm not asking about software to do this ( I'm aware that some apps uses hibernation file or memory dump file to do so) I'm asking about how to find it manually , If i deleted both previous files and stopped any administrative privileges for installing any software will it be impossible ??

If I'm understanding your question right, you're asking "How to brute-force the Bitlocker encryption without being able to install stuff and without using "backdoors" and without having the key-file (if used)?"

You can't brute-force AES-128 without the said key-file.
The reason for this is that the key file contains the 128-bit keys which are too hard to guess by themselves. If you don't have access to this file at all you can't break AES / bitlocker in a passive sense. You could still run evil-maid attacks though...

If you have access to the encrypted key file and it uses a password there is a chance you can break the encryption scheme.
The reason for this that you'd guess the password used to encrypt the key-file and then properly decrypt it and use the embedded key to decrypt the encrypted data. You can guess the password by simply trying all possible ones out until you hit the lucky one which is feasible because there are only usually "a few" passwords possible ($\approx2^{40}$ compared to $2^{128}$)

Note that the inability to install custom software isn't a restriction in the usual threat model for drive encryption. Usually it is assumed to have physical access to the drive and being able to read sectors while at rest. So one could look for a known structure to perform the brute-force attack so this is feasible (in the right scenario).

TL;DR: You can't break AES, but a password if used, so the password may be weakest point to attack.


Is there any encryption system where the sender cannot prove that a specific ciphertext belongs to a specific plaintext I'm trying to create a message-transfer system where

The encrypted messages are stored in a public database.
It is possible to verify who is the sender of this message.
The sender cannot prove to anyone else the content of the message. I mean, he/she cannot re-encrypt the plaintext message and match with the ciphertext on the public database to prove the content of the message to someone else.

Is there any existing encryption protocol that can get the job done? This encryption protocol can be interactive/non-interactive, symmetric/asymmetric or anything else. It just needs to get the job done.

I'm new to cryptography. Please pardon me if my question is too dumb or has been answered already. I tried to look for solutions online but failed to find any practical solution. While searching I came to know a little bit about deniable encryption and zero-knowledge proofs. Can they help with my matter in any way?

Thanks in advance.

Deniable encryption should provide what you want. In a deniable encryption scheme, in addition to the usual $(\mathsf{KeyGen},\mathsf{Encrypt},\mathsf{Decrypt})$ algorithm, you have an algorithm $\mathsf{Explain}$ that takes as input a ciphertext $c$ (which can be any ciphertext) and a message $m$, and outputs a random coin $r$ such that the triple $(m,r,c)$ is indistinguishable from the distribution obtained, given $m$, by sampling a uniformly random coin $r$ and constructing $c$ as $\mathsf{Encrypt}(m;r)$. That is, even though a ciphertext can be correctly decrypted given the secret key, for any plaintext you can find a random coin which "explains" the ciphertext as an encryption of this plaintext.

Given a deniable encryption scheme, a proof that you correctly encrypted a message can never be convincing, because you can always, for any ciphertext $c$ and plaintext $m$, find coins $r$ such that $c = \mathsf{Encrypt}(m;r)$ - and that does not mean that $c$ will necessarily decrypt to $m$. Hence, in such a scheme, if you only know the public key, it is fundamentally infeasible to prove that you encrypted a given message (if you know the secret key, it's a different matter, but that does not seem to be the case in your question).

Note that your requirement 2 can be achieved using any standard authentication mechanism on top of deniable encryption.

Deniable encryption was first constructed in this paper, but this is only of theoretical interest, and does not lead to any efficient instantiation in practice. There exists alternative constructions (see also the many follow ups) that only achieve an inverse-polynomial "deniability", in the sense that it is possible to distinguish "true random coins" from those obtained through $\mathsf{Explain}$ with inverse polynomial probability.


Effect of $L_n[1/4,c]$ integer factorization on RSA-2048 Using the L-notation, integer factorization of an integer $n$ has the best known complexity of $L_n[1/3,c]$ using general number field sieve. Would discovery of an algorithm with complexity $L_n[1/4,c]$ be of any consequential significance to security of RSA-2048? If my computation is correct, for $c \approx 2$, it shows the complexity is reduced from $10^{36}$ to $10^{23}$, which seems doable with today's hardware. But I'm not confident in my computation or my assumptions about the capabilities of today's hardware.

Edit: here are my computations and assumptions: $\log(2^{2048})\approx1420$. $L_n[1/3,2]\approx \exp [2 (1420)^{1/3} (\log 1420)^{^{1 - 1/3}}]\approx 10^{36}$. $L_n[1/4,2]\approx \exp [2 (1420)^{1/4} (\log 1420)^{^{1 - 1/4}}]\approx 10^{23}$. Assuming $10^9$ possibilities can be tested every second and there are $10^6$ such processing units, it takes 3 years to crack RSA-2048: $10^{23} / (10^{9}\cdot60\cdot60\cdot24\cdot365)\approx 3 \times 10^6$.

Unfortunately, deriving actual numbers from asymptotic bounds makes little sense (after all, $10^{36}$ and $10^{23}$ are both $O(1)$). Getting an idea of the actual cost of running an algorithm requires a fine analysis of the algorithm itself; asymptotic results are not sufficient. An $L_n[1/4]$ algorithm for factoring would be a great theoretical result, but it wouldn't necessarily perform better than the current algorithms on, say, RSA-2048.

Fear the hidden constant factors.


If we should not reuse primes in DH, shouldn't we not reuse ECDH elliptic curve properties? An article How is NSA breaking so much crypto? describes NSA's methods for breaking encryption.

  If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number [...] an adversary can perform a single enormous computation to "crack" a particular prime, then easily break any individual connection that uses that prime.

Why do we generate these primes using tools like dhparam when using DH, but in ECDH we often admit which particular curve (like Curve25519) we're using?

Isn't that exactly what we should avoid? Shouldn't we generate the curve properties in a similiar manner? Or is that hypothetically correct but the computation is not even in well-paid adversary's capabilities?

The fact is that the discrete logarithm problem (DLP) is solved using different algorithms in the cases of multiplicative groups (where normal DH applies) and elliptic curves (where ECDH applies).

The behavior of these algorithms is quite different.

For multiplicative groups, where the NFS for logarithm is used, a huge part of the computation depends only on the multiplicative group itself and not on the single discrete logarithm.

See for example the logjam paper where in table 2 they mention the costs for sieving, linear algebra and descent (where descent is the only phase requiring the single logarithm as input, and therefore can't be precomputed).
For DH-1024 sieving and linear algebra requires 45 million core years while just 30 core days are needed for the descent.
This means that after having done a huge precomputation, single logarithms are quite easy to extract.

For elliptic curve groups the situation is different. The best attack is Pollard's rho, which requires $\mathcal{O}(\sqrt{n})$ group additions for a group of size $n$. Now, computing in parallel $l$ discrete logarithm costs $\mathcal{O}(\sqrt{ln})$, which is speedup over the trivial $\mathcal{O}(l\sqrt{n})$, but not a significant one. In fact, the attacker is expected to compute $\mathcal{O}(\sqrt{n})$ additions before finding the first among them (see the "Batch Disscrete Logarithms" of the curve25519 paper.
Once the first discrete logarithm is found, the second one has still similar cost to the first one, not a much smaller one (like with the NFS).

Thus if $n$ is of reasonable size, it doesn't matter how $l$ is big as computing even the first logarithm will be out of reach.

Note: there are techniques that by using an extremely large precomputation effort allow to easily compute discrete logarithms. The important thing to understand the ineffectiveness of these approaches is that the precomputation effort costs significantly more than extracting a single logarithm (about $\sqrt[3]{n^2}$ additions which is greater than $\sqrt{n}$ for the single logarithm).
See this paper for details.


In S/MIME, are the same certificates always used to sign and encrypt messages? My assumption is that S/MIME almost always utilizes certificates as follows:

My certificate can be used to allow people to encrypt messages and send them to me.
My certificate (the same certificate) is used by me to sign messages and send them.

Is there an RFC reference that specifies this is a requirement for S/MIME?
I'm scanning through RFC 5751 and not seeing anything jump out at me...

No, clients do not have to use the same certificates for signing and encrypting messages.
Actually, you already noted the reference yourself. Let me quote RFC 5751, section 2.5.3 on page 13:

2.5.3. Encryption Key Preference Attribute
The encryption key preference attribute allows the signer to unambiguously describe which of the signer's certificates has the signer's preferred encryption key. This attribute is designed to enhance behavior for interoperating with those clients that use separate keys for encryption and signing.  This attribute is used to convey to anyone viewing the attribute which of the listed certificates is appropriate for encrypting a session key for future encrypted messages.

(bold-italic emphasis mine)
As the reference states, clients can (but do not have to) use separate keys for encryption and signing.


Brute force, get AES keys by multiple plain-texts with their cipher-texts I know that the encryption is AES, and I have multiple plain-texts with their cipher-texts, I don't know the encryption mode (ECB, CFB, etc ...) actually, but I know that the keys and the IV Key (if it's used) are static not changeable.

  How can I get the keys, or is there are a way to encrypt a text with the same key, so I can get the cipher-text of any plain-text I want ? Is there any tool or service can I pay to do that ?

No. You are talking about a known plaintext attack against AES. There is no known attack, discovery of such an attack would be invaluable to there likes of MI6, FSB, and the NSA.


Using variable length CBC-MAC, can some block cipher with a fixed k be used as a cryptographic hash function? If a variable length CBC-MAC is used with a block cipher (a.k.a. pseudorandom permutation), does there exist a block cipher such that implementation of this CBC-MAC may be used as a cryptographic hash function, provided that k is fixed?

No, it cannot; you can find a preimage attack on it.

CBC-MAC on a two-block message $(M_0, M_1)$ (after padding) is defined as $E_k( M_1 \oplus E_k( M_0 ))$.  To find a preimage for a value $S$, you select $M_1$ with a valid padding pattern (because of the padding, we cannot select this block arbitrarily), and compute $M_0 = D_k(M_1 \oplus D_k(S))$; it is easy to see that the padding message $(M_0, M_1)$ hashes to the value $S$.

And, even if you cannot easily compute $D_k$, it is still easy to find second preimages...


Post-quantum hybrid encryption Assume the following simplified protocol:

seed = curve25519SharedKey(theirPublicKey, myPrivateKey)
sharedKey = scrypt(seed, salt, sufficientlyHardWorkFactors...)
cipherText = aes256(sharedKey, clearText)

Does using a slow-hash on the output of an asymmetric key-exchange offer any more protection in a quantum-computing era?  I know that quantum computing is supposed to make breaking diffie-hellman easy... what I don't know is exactly how easy.  Is the algorithm (greatly) diminished, or completely broken?

Does using a slow-hash on the output of an asymmetric key-exchange

  offer any more protection in a quantum-computing era?

No. $\:$ A quantum attacker would simply find seed even if you didn't use "a slow-hash on" it.

  Is the algorithm (greatly) diminished, or completely broken?

The algorithm will still be completely broken by quantum attacks. $\:$ Furthermore, your simplified

protocol would just have one more link (scrypt) that could potentially be broken by classical attacks.


Elliptic curves - operations in larger groups - performance According to my measurements and to this work, it seems that operations, for example scalar multiplication, are more expensive in larger groups. If I have, for example, an 80-bit elliptic curve and an 384-bit elliptic curve, then the difference is very big:

80-bit curve: 10ms per 1 multiplication on average
384-bit curve: 501ms per 1 multiplication on average

I don't know if it's related, but the method for multiplication is probably wNAF.

Question: Why basic operations are more expensive on larger groups?

There are many different flavors of elliptic curves and coordinate systems for them with different costs for computing addition or scalar multiplication.  You can find cost estimates for many of these at the Explicit-Formulas Database (EFD), and measurements from SUPERCOP at https://bench.cr.yp.to/.

Certain curves like Curve25519 in Montgomery form $y^2 = x^3 + 486662 x^2 + x$ were designed to admit fast $x$-restricted scalar multiplication, i.e. to compute $x([n]P)$ given $n$ and $x(P)$, as is sufficient for applications like Diffie–Hellman; software to compute it will consequently run much faster than software to compute scalar multiplication of a generic short Weierstrass curve of comparable size.  Certain curves also admit an Edwards or twisted Edwards form like $-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$, which also admits much faster addition formulas than generic short Weierstrass curves, but only those with cofactor at least 4 can have this form.

The cost estimates of the EFD are all written in terms of numbers of additions, multiplications, etc., in the underlying field $\mathbb F_q$.  Certain fields like $\mathbb F_{2^{255} - 19}$ are designed to admit constant-factor speedups for fast arithmetic in software by being just below a power of two, but largely, the number of bit operations to compute addition in $\mathbb F_q$ grows as $O(\log q)$, and to compute multiplication, $O(\log^2 q)$, or $O(\log^{\log_2 3} q)$ if you use Karatsuba's algorithm, etc.

There are no substantive shortcuts around these bit operation costs in general.  Of course, in special cases, curves may admit a fast endomorphism like Koblitz curves, FourQ, etc., which can be used to speed up scalar multiplication on those curves.

Finally, Hasse's theorem bounds the distance between the size $q$ of the underlying field and the size $\ell$ of the group, which is also the size of the scalar ring.  So for larger fields, the scalars may be larger (unless for some reason you're safely working in a subgroup), and to have larger scalars, the field must be larger.  Security is generically limited by the cost $O(\sqrt\ell)$ of Pollard's $\rho$ to compute discrete logs in the group, so if you want Pollard's $\rho$ to cost ${\sim}2^{128}$ bit operations you must choose a group with $\ell \sim 2^{256}$.


Why does Diffie-Hellman need be a cyclic group? Why is Diffie-Hellman defined on a cyclic group? Doesn't it work for any commutative operation which the inverse is hard to find?

Say Alice and Bob agree in a public prime $c$ and both choose a secret prime $a$ respectively $b$

Alice sends $ac$ to Bob and Bob $bc$ to Alice.

Alice then multiplies $a$ with bobs message $bc$ yielding $abc$
Bob then multiplies $b$ with Aice's message $ac$ yield $bac$

which are the same due to commutativity and associativity. Hence they now share a common secret $abc$.

It is hard for Eve to factorize $ac$ and $bc$ into its original primes $a,b,c$  and Eve hasn't got enough information to construct $abc$  so why isn't this a valid Diffie-Hellman key-exchange?

Diffie-Hellman operates in a cyclic group by definition: the elements $g, g^a, g^b, g^{ab}$ are in the cyclic group generated by $g$. Technically, a monoid is sufficient, but since cryptography mostly operates in finite structures, you get a group anyway.

In your example, you operate in the cyclic group $c\mathbf{Z}$, and as you were told in the comments, Diffie-Hellman is not secure in this group because an attacker knows $c$ and $ac$, and can thus obtain $a$, and from $a$ and $bc$ can obtain the secret $abc$.


Playfair Cipher + Vigenere Cipher? I'm researching cryptography for a school project, came across the above two ciphers, and something occurred to me. Would combining these two schemes give a considerably stronger encryption than either one individually?

Consider two encryption schemes: one in which only the vigenere cipher is used (which I'll call $E_1$), and one in which both the vigenere and playfair cipher is used ($E_2$).

When discussing $E_2$, assume all references to it's key will be referring to the key of it's vigenere cipher unless explicitly stated otherwise.

When trying to decrypt $E_1$, the first step is looking for repeated sequences of characters and recording their distance apart to help determine the length of the key, which is likely to be a factor of many of these recorded distances.

However, with an $E_2$ cipher on the same ciphertext, this won't work nearly as well. If E1 showed repetitions of odd length n, $E_2$ would show those same reptitions of length $n-1$ with either the final character or the first character missing, while even length repetitions would either be reproduced at length n or have both the end and the beginning cut off for length $n-2$. In addition, any given sequence will become one of two entirely different sequences based on where the beginning of the sequence falls at the start of a playfair pair or not.

This means two things:

Repeated sequences aren't quite as clear - particularly shorter ones (which are the most common): sequences of length 3 (notably the word 'the') for example, become one of two sequences of length two, which is considerably easier to form by chance (which is why repeated sequences of length 2 are often not used in vigenere cryptanalysis). Four letter repetitions suffer a similar fate - half the time, the playfair pass will instead make them into repeated sequences of length two as well.
If $E_1(P)$ produces n repeated sequences (a single repetition) of average distance m apart, $E_2(P)$ will, on average, produce 2 different repeated sequences, each with $n/2$ repetitions that are $2*n*$ distance apart. This means that the distances between the repetitions are significantly larger and could have significantly more factors, which would mean the length of the key is less certain to the cryptanalyst.

The short answer is yes. It would be considerably more secure.

But nowadays, classical encryption methods like Playfair and Vigenère are so easily broken by computer analysis that they offer next to no security whatsoever. Aiming for something "considerably more secure" than either of these is really setting the bar very low.

Specifically, although the combination of Playfair and Vigenère does reduce the frequency of repeated sequences, it doesn't get rid of them. So you still haven't eliminated the primary weakness of vanilla Vigenère.

For example, if your Vigenère key has length $n$, just one repetition of a word at an interval of $2kn$ places provides enough information to get started on an attack. You obviously don't know what the value of $k$ is, but there's nothing to stop you testing for key lengths corresponding to every divisor of $2kn$.

Even if your plaintext contains no repeated words whatsoever, you're still vulnerable to the same attack if the same word appears in more than one message. (Unless, of course, you use a different set of keys every time, in which case you may as well use a one-time pad.)

This system would also fail according to Kerckhoffs's principle:

  A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.


Is there another group structure that is suitable for RSA other than $U_{pq}$? I know that calculating the cardinality of $U_{pq}$ is infeasible and therefore it is extremely hard to break a code using Lagrange's theorem. But later on my studies i realized main principle of RSA can be generalized to any abelian finite group. Is there another group structure $G$ that is suitable for RSA (i.e. it is infeasible to compute $|G|$)?

Of course in such cases, we wouldn't be able to do padding, hence our algorithm would be deterministic and unsafe. But i am just asking out of curiosity.

For expressing my thoughts more formally:

Given a finite abelian group $(G, \cdot)$, every function $f:G \to G$,

$$f(x) = x^n$$
is an automorphism (structure-preserving permutation) of $G$ for $(|G|, n) = 1$. Since it is an isomorphism, it does have an inverse isomorphism $f^{-1} = x^m$ for $m$ being modular inverse of $n$ in modulo $|G|$.

So, summing up:

$$f: x \mapsto x^n$$
$$f^{-1}: x \mapsto x^m$$

We can treat each element of $G$ as a message. We can encrypt this message with $f$, we can decrypt resulting code with $f^{-1}$, as we did in RSA. All difficulty to break this algorithm is the difficulty of calculating $|G|$.

This is a generalization of the main principle of RSA. Is it suitable for a group structure other than $U_{pq}$?

The key point in RSA is the fact that inversion in modulo $|G|$ is hard, of course other groups are a priori okay to build a secure encryption scheme.

For example $U_{pqr}$, with $p, q, r$ large primes seems to be okay. But it will be probably less efficient (keys and ciphertexts will be probably larger for the same level of security).

Of course, it is not because the problem seems to be hard, that we can conclude with the same level of confidency that the RSA-problem-hardness. The RSA-problem has been particularly well-studied. And if you choose to change the group used, the risk to discover that "inversion in modulo $|G|$ is not so hard" is more important.


Consequence of a change on the Guillou-Quisquater Protocol In the Guillou-Quisquater Protocol, the prover convinces the verifier that he knows an $e$-th root of an element $y \in \mathbb{Z}^*_n$ ($p, q, e$ are primes, $n = pq$ and $e$ is coprime with $\varphi(n)$). The protocol between prover $P$ and verifier $V$ (see here for instance) is:

$P$ picks $r$ at random in $\mathbb{Z}^*_n$ and sends $a = r^e \mod n$ to $V$.
$V$ picks $c$ at random in $\mathbb{Z}_e$ and sends it to $P$.
$P$ computes $z = a x^c$ and sends it to $V$.
$V$ accepts iff $z^e = a y^c$.

What happens if $e$ divides $\varphi(n)$ and the protocol still succeeds (i.e. $V$ has received an $a$, sent back $c$, and get $z$ s.t. $z^e = a y^c$)? I don't think it still proves that $P$ knows an $e$-th root of $y$... It is even possible that $y$ doesn't have any $e$-th root (since $e$ and $\varphi(n)$ aren't coprime). But does it proves something (new) about $y$?

Yes it proves that $y \ne 1 \pmod{n}$ is not an $e$-th root. That is, no $x$ exists such that $x^e = y \pmod{n}$. In particular, if $e | \phi(n)$ then for any $x$ it holds that
$\left( x^{ \frac{\phi(n)} {e}} \right)^e = 1 \ne y$.

This probably means one last final conclusion designed as a homework.

Regarding GQ protocol: prover will be unable to pick an $r$ such that
$a = r^e \ne 1$.


Can the CRT speed-up Paillier decryption by more than a factor of two? In the Pailler cryptosystem, decryption goes $m\gets\displaystyle\left\lfloor\frac {\left(c^\lambda\bmod n^2\right)-1}n\right\rfloor\mu\bmod n$ with $\mu<n$ being a part of the private key just like $\lambda=\operatorname{lcm}(p-1,q-1)$ for $n=p\,q$.

The Chineese Remainder Theorem allows to speed-up this computation knowing the factorization $n=p\,q$, as follows:

Evaluate $x=c^\lambda\bmod n^2$ by the Chinese Remainder theorem, that is

$x_{p}\gets c^\lambda\bmod p^2$
$x_q\gets c^\lambda\bmod q^2$
$x\gets\left(q^{-2}(x_p-x_q)\bmod p^2\right)q^2+x_q$
note: $q^{-2}\bmod p^2$ can be precomputed.

Then evaluate $m\displaystyle\gets\left\lfloor\frac{x-1}n\right\rfloor\,\mu\bmod n$.

This speeds-up decryption by a factor of at most two (each of the first two modular exponentiations is manipulating values half as large as for $c^\lambda\bmod n^2$, and is thus at best four times faster). In RSA, the CRT gives larger savings (sometime approaching four), because the exponents $d_p$ and $d_q$ have about half the size of $d$.

Can we improve the savings obtained and exceed a factor of two?

This question is an attempt to compute $m_p=m\bmod p$ and $m_q=m\bmod q$, then use the CRT to get $m$. If the computation of $m_p$ could somewhat we performed mostly modulo $p$ or $p^2$, perhaps the savings would be improved.

Since CRT is an isomorphism computing $m_p=m\bmod q$ and $m_q=m\bmod q$ directly is possible. To see this in the formulas above replace the $\bmod n$ step with $p$ and $q$.

To the question, I don't know if working in $\mathbb{Z}_{p^2}^{*}$ and $\mathbb{Z}_{q^2}^{*}$ could let you compute $m_p$ and $m_q$ more quickly than simply doing the steps modulo the prime factors of $n$. One thing that could help is to reduce $\lambda$ by the order of $\mathbb{Z}_{p^2}^{*}$ (or $q^2$ respectively). The order is given by the Euler totient function of $p^2$ which is $\phi(p^2) = p(p-1)$. This helps when $p$ or $q$ is small but in general doesn't speed things up.

The only other comment I can make is the improvement you want would need to exploit some property of the group of elements of the form $x=c^\lambda\bmod n^2$ under multiplication. This is the group of elements of order dividing $n$. Its two nontrivial subgroups are the elements of order dividing $p$ and $q$.


HKDF entropy extraction I collect entropy from the following sources:

system_entropy = System provided crypto entropy stream (CryptGenRandom on Windows)
user_entropy = User-provided entropy - in a form of a byte stream of serialized random mouse movements, key strokes etc (this is manually entered by the user, similar to how TrueCrypt collects entropy)

To generate a key from these sources, is the following construct appropriate?

my_random_key = HKDF(salt, system_entropy || user_entropy)

Where HKDF is a RFC 5869 construct (both extract and expand steps, but since I don't use "info", just extract is sufficient also) based on HMAC-SHA256.

To my understanding, it should be perfectly fine to just append the user entropy to the system entropy, even under the assumption that the user entropy can be entirely controlled by an adversary, right? Because in that case, the adversary will just destroy the "user_entropy" contribution to the security of the key, but assuming the "system_entropy" is sufficient, then it's ok? In a sense, I assume the "system_entropy" to be already secure, but I want to provide "user_entropy" for additional hardening. So I just want to throw as much random junk at the HKDF as possible.

Yes, that should be secure. It seems however that your problem lies with the secure random number generator and that you are using a KDF to overcome those. Basically you are using a KDF as key generator; no keys are derived from another / master key.

It seems more obvious to use a DRBG / CPRNG (deterministic random bit generator / cryptographically secure pseudo random number generator - there are probably more names) and seed it with random values from the system and the user. After that you can just extract the key bytes, and you would still be left with a (fast) RNG that you can reuse / reseed - something you will likely need later on.

Many API's already provide these out of the box, and usually they are pre-seeded as well, so you may just have to add your user generated entropy to the state by mixing in additional seed data. Nothing stops you from adding HKDF + OtherInfo in addition to the DRBG of course, but that is not required.


Can someone explain the "three-for-two" trick used by the DGHV scheme authors to squash the decryption circuit? Can someone please explain the "three-for-two" trick used by the authors of the DGHV scheme (page 17) to squash the decryption circuit? I looked for resources on the same, but it looks like the authors coined this term.

A brief description of the "three-for-two" trick:

It is a technique that uses a constant depth circuit to transform three numbers of arbitrary bit lengths into two numbers that are almost 1 bit longer, such that the sum of the two output numbers is equal to the sum of the three input numbers.

Furthermore, the paper says that the total depth that it takes to reduce $k$ numbers to two numbers is $d \leq 2^{\lceil log_{3/2}k \rceil + 2}$. I don't get how we landed on this expression.

As far as I understand, the "three-for-two" tricks rely on the fact that one does not need to immediately propagate the carries along the whole adder circuit. You may have heard of the "carry-save-adder" method which consists in postponing the carry propagation to reduce circuit latency. For instance, when adding $a=0, b=1$ and $c=1$ (1 bit-integers), one will split the result into two new integers x and y : carry and output. Thus, one can compute $a+b+c$ as $(x << 1)+y = 2 \times x+y$. In this case, $x = 1$ and $y = 0$. While this example is given with 1-bit integers, we can extend the method to n-bit integers.

Given $a=(1001)_2$, $b=(0101)_2$ and $c=(1010)_2$ (where $(.)_2$ stands for binary notation), one can find that $x=(1001)_2$ and $y=(0110)_2$. Computing both $x,y$ requires $\mathcal{O}(1)$ circuit depth as it does not depend on $(a,b,c)$ bit-length. However, notice that computing $(x \times 2+y)=(10010)_2+(00110)_2=(11000)_2$ will require $n$ depth circuits if based on a basic "carry-ripple adder" (where $n$ is the bit length of given integers). Note there exists logarithmic adder.

About the $d<2^{\lceil\log_{3/2}(k)\rceil+2}$ property, it is related to the fact that one can apply the "three-for-two" trick as many times as necessary. For instance, given integers $(a_0, a_1, a_2, a_3)$, one will apply the trick to the first triple $(a_0,a_1,a_2)$ to obtain $(b_0, b_1)$. Thus it remains to compute the sum $(b_0, b_1, a_3)$ (first step). Using the trick one last time, one will obtain $(b_2, b_3)$.

Every single time one sees a "triplet", one can transform it into a couple. At every step, one can reduce the total amount of elements from $k$ to $k \times \frac{2}{3}$. Since then, it requires at most $\lceil \log_{3/2}(K) \rceil+2$ steps to reduce a list of $K$ integers to 2 integers. To illustrate this point, if $K=9$ and if one applies the trick once, one will obtain a 6-item list. If one apply it one more time, one obtains a 4-item list. It requires a last "trick" to obtain 2 elements that one can finally sum up using a regular adder.

Let $x_i$ be the i-th bit of $x = x_0+x_1 \times 2 + x_2 \times 2^2 +... x_{n-1} \times 2^{n-1}$. The $x_i$ computing part of the "three-for-two" circuit requires at least one multiplication (at least one AND gate / Multiplication gate). As the "trick" is chained, multiplications involved in $x_i$ will stack, doubling (that explains the power of two in the  $d<2^{\lceil\log_{3/2}(k)\rceil+2}$ inequality) the "noise" of the homomorphic encrypted text for every layer of the "chain". That is why the multiplicative depth is at most $d<2^{\lceil\log_{3/2}(k)\rceil+2}$.


Comparisons in zero-knowledge proofs There is already a great survey on how to do range checks in a zero-knowledge setting. A range check allows to constrain a variable to be in a certain range. Comparisons seem to be similar, but they are actually very different in that they're allowed to be false.

E.g. if we write a range checks like this:

0 <= n < c

we can be sure that validation will never succeed if n is not in the given range. However if we have something like

if 0 <= n < c then x else y

then validation is supposed to succeed regardless of whether n is in the given range or not (provided the prover did its work honestly).

A similar issue arises in other situations such as n /= 0. It is trivial to require n not to equal 0:

n * inv n = 1

(because only 0 doesn't have an inverse) however in order to compile

if n /= 0 then x else y

we need to make use of non-determinism and introduce an auxiliary variable.

So my question is: how to compile 0 <= n < c when it's not a constraint, but rather a regular expression that I can use as a condition in an if statement?

(This answer assumes a proving system that supports general arithmetic constraints, e.g. R1CS, over a finite field $\mathbb{F}_p$. It can be adapted to other settings but that may be non-trivial.)
Consider that a comparison $0 \leq n < c$ in $\mathbb{F}_p$ has negation $c \leq n < p$. So a constraint system for $b = (0 \leq n < c)$ can be essentially
$\hspace{1em}b: \text{boolean}. \text{ if } b \text{ then assert } 0 \leq n < c. \text{ if not } b \text{ then assert } c \leq n < p$.
It might not be obvious how to make the assertions conditional on $b$ or on $\text{not } b$, but there's a trick for that. Let's say we're using the the approach in appendix A.3.2.2 of the Zcash protocol spec for the assertions, so that the numbers we're checking are actually given as a bit representations. Then, for a plain range check, there would need to be an additional constraint $n = \sum\limits_{i=0}^{k-1} 2^i n_i$.
Instead, pick two integers $x$ and $y$, with bit representations $x = \sum\limits_{i=0}^{k-1} 2^i x_i$ and $y = \sum\limits_{i=0}^{k'-1} 2^i y_i$. Unconditionally check that $0 \leq \langle x_{k-1} \cdots x_0 \rangle < c$ and $c \leq \langle y_{k'-1} \cdots y_0 \rangle < p$. Finally assert:

$\left(n - \sum\limits_{i=0}^{k-1} 2^i x_i\right) \times b = 0$
$\left(n - \sum\limits_{i=0}^{k'-1} 2^i y_i\right) \times (1-b) = 0$

The first constraint here asserts that either $b = 0$ or $n = x$, in other words (given that $b$ is constrained to be boolean) $(b = 1) \Rightarrow (n = x)$. The second asserts that either $b = 1$ or $n = y$, in other words $(b = 0) \Rightarrow (n = y)$. So we can infer that $(b = 1) \Rightarrow (0 \leq n < c)$ and $(b = 0) \Rightarrow (c \leq n < p)$, as required. One of $x$ and $y$ will not be constrained, so we just pick it to be something for which the corresponding range check passes.
Note that some care is required to implement the range checks correctly given that at least one of $k$ and $k'$ will be close to the length of $p$, but that's orthogonal to the main question you asked I think. For the method in appendix A.3.2.2 it should be fine, since that method supports bit representations of arbitrary length.
There's probably a way to optimize this further by not doing two full bit decompositions, but I'm not seeing it right now.


Are developers expected to implement Diffie-Hellman key exchange themselves? I noticed that the GO standard library has some really nice functions for performing AES encryption / decryption in various modes.  However, I couldn't (yet) find anything for Diffie-Hellman key exchange.

I'm not sure if I should proceed by searching more carefully, switching to a different language with a more extensive crypto library, or trying to implement the key exchange protocol myself.

The protocol "seems" implementable:

Alice sends $g^a \mod p$ to Bob
Bob sends $g^b \mod p$ to Alice
We need to choose $g, a, b, p$ appropriately

But I'd bet that there are a lot of subtleties buried in that "straightforward protocol" (for example, we need some out-of-band mechanism to defend against man in the middle attacks).

Plus, one of the first lessons of crypto is don't implement cryptographic primitives yourself, and I don't know if this warrants an exception to that lesson.

Are developers generally expected to implement Diffie-Hellman key exchange themselves? If so, what are the primitives that I should be using, and where can I find a good reference for some of the subtleties that should be considered?

Look for a 'Key Agreement' functionality (see https://golang.org/src/crypto/tls/key_agreement.go), as many comments above suggested - if you're trying to establish a secure communication channel, the default TLS (SSL) would be good way to go.


Upgrade password hash in an existing system: Pbkdf2( salt , OldSha1Hash ) Background    [Updated]
Consider a situation where a website was created over a decade ago and user account password storage was done by storing SHA1(password) into the database.

It would be great to upgrade the system to use Pbkdf2(salt, password) with a large work factor of say 50000 for the password hashing using HMACSHA256 as the prf.  The resultant hash | salt could be stored in the database and used to validate the visitor when they return and supply a password.  This approach seems to be well regarded here on crypto.stackoverflow.com.

It would be great to be able to improved the hashing for all the existing accounts without needing users to reset their password.  So I'm wondering if the following approach is good from a security perspective.

  OldHash = SHA1(password)
  UpgradedHash = Pbkdf2(salt , OldHash )

  StoredInDatabase = UpgradedHash | salt

One desirable property of this approach is that all existing password hashes can be upgraded to using Pbkdf2, salt and a high work factor without needing to have the passwords reset.  All the new passwords could even be handled the same way just to keep all the hashes consistent.  So new passwords could work like this:

  Hash = Pbkdf2(salt , SHA1(password))
  StoredInDatabase = Hash | salt

Rational for Upgrading the Hashes
The need to upgrade the password hashes is because the SHA-1 hashes don't include salt and SHA-1 has since been reported as broken. The goal in upgrading the password hashes in the database is to reduce the likelihood that a hacker with access to the database of password hashes could obtain the corresponding passwords for those accounts.

Question
Does this seem like a security valid approach for upgrading the password hashing approach in an existing system?

Yes, mostly

But wait, isn't SHA-1 broken?

It is. SHA-1 has collisions found as of 2017. But this isn't important for our usage, since we only require that SHA-1 won't collide for our inputs. Difference is that with 2017 attack attacker knows plaintext and tries to find another plaintext that gives same hash, in our case attacker doesn't know anything (not even hash). And we can assume that SHA-1 won't collide for real-life passwords, since if this was case it would be very major breakage of SHA-1 (that would have been found earlier).

There is however one catch: SHA-1 will limit your security to 80bits, since it has 160bit output and birthday attack can "limit security" to half of output bits (in our case). This is in fact reason PKDBF1 was abandoned in favor of PKDBF2, but most passwords are far from 80bits in security.

Note: I didn't take any of other problems into account in my answer. Choice of PKDBF2 might be considered outdated by this point too. I personally would suggest Argon2 (but some would call it too new to be adopted). Also PKDBF2 doesn't have one input, as others noted, but I'll assume it's just overlook.