Which concrete applications benefit from Oblivious RAM constructions?

There is a new paper on the topic, the paper is not publicly available yet; however, its slides are available at David Cash, Paul Grubbs, Jason Perry, Tom Ristenpart - Leakage-Abuse Attacks against Searchable Encryption
.

A short summary of the talk is available at Seny Kamara - Workshop on Encryption for Secure Search & Other Algorithms:

  David Cash also discussed inference attacks. In addition to standard inference attacks, however, he also described attacks where the adversary exploits more than leakage and, in particular, knows or chooses some of documents.  The findings were very interesting. One thing that came out of this study was that the IKK attack—while very interesting in theory—is not really practical. There are several technical reasons for this but I’ll leave you to read David’s paper when it appears if you are interested. This study also looked at a new class of schemes (not SSE/structured schemes) that have appeared in the literature recently and showed that they were vulnerable to adversaries who know and/or can choose documents (though to be fair they were not designed with that adversarial model in mind).


As SEJPM suggested, it's quite practical for the range of $e$ in question.

Here's an easier way than the Kangaroo method:

Set $\lambda \approx. 10^{7.5}$; the exact value isn't important, but the below works most efficiently if the approximation is close.
Compute $A_i = c m^i \bmod n$ for $i = 0 .. \lambda - 1$ using about $ \lambda$ modular multiplies
Store all the $A_i$ values in a fast lookup table (e.g. a hash table)
Compute $z = m^\lambda \bmod n$
For $j = 1 .. 10^{15} /\lambda$ compute $B_j = z^j \bmod n$, and check if the value $B_j$ appears anywhere in the $A_i$ list.

If we have $B_j = A_i$, then we know that $e = \lambda j - i$

Assuming $e$ is in the range $0 .. 10^{15}$, this will always find it, using about $2 \lambda$ modular multiplies; quite doable on a standard PC.


There are two problems that arise when you attempt to use a composite $P$:

The first is that the attacker can gain some information about the shared secret; he can't reconstruct the entire secret, however the goal of Shamir Secret Sharing is that the attacker obtains no information.  For a simple case, consider a threshold $k=2$ case where the attacker has the single share $(3, 0)$.  That is, the attacker knows that the polynomial is a linear equation $ax + s$, with $s$ being the shared secret, and with $3a + s = 0 \bmod 255$.  What the attacker can immediately deduce is that, whatever the shared secret is, it must be a multiple of 3 (because $3a + s$ is a multiple of $3$); this happens because $3$ is a divisor of $255$.

The second issue is that the legitimate reconstructors, with $k$ different shares, cannot necessarily uniquely reconstruct the secret.  For an example, consider that case $k=2$ and we have the two shares $(1, 0)$ and $(4, 0)$.  In this case, we know we have a linear equation with $1a + s = 0 \bmod 255$ and $4a + s = 0 \bmod 255$.

Unfortunately, there are 3 possible equations that fit this criteria:

$$0 x + 0 $$

$$85 x + 170$$

$$170 x + 85$$

It is easy to see that plugging in 0, 4 into each of these equations yields the values implied by the shares.

Hence, while we know that the secret is one of $\{0, 85, 170\}$, we have no idea which one it is.


What kind of numbers are needed for cryptography/security? Are those integers?

Bits. Simply have your TRNG generate random bits.

As mentioned in the other answer, the only difference between bits/hex/integers/etc is in the formatting and representation. It is almost certainly more appropriate and simpler to generate random bits than it is to rely on some process to generate a random integers in a given range.

How long should those numbers be? 10 digits, 100 digits?

256 bits is sufficient for any one user. You can take a 256-bits of uniformly random information and use it to generate an arbitrary amount of uniformly random information (for practical purposes) using a CSPRNG.

I read few articles about random numbers, but did I get it right, they are used to create hashes to create stronger encryption?

Random numbers are not required to create hashes

Typical hash functions are deterministic algorithms
Random numbers may be used as part of an input to a hash function, depending on context

Hashing is not related to encryption

The two are sometimes used in conjunction, but encryption is not (typically) built from hash functions

"stronger encryption"

Random numbers are required to securely use a cipher (e.g. for keys, IVs)
But the algorithms themselves such as AES and ChaCha are nigh unbreakable and so cannot be "stronger"


Attacks on LCG with "self-XOR" output function?

To answer my own question, after some research and experimentation I came up with a fast algorithm to break such constructions (in fact the approach below works even if the increment $C$ is unknown).

As a preprocessing step, find a set of $m$ small weights $\lvert w_i \rvert < W$ such that

$$\sum_{i = 1}^{m} w_i A^i \equiv 0 \pmod{2^{n/2 + k}} \tag{1}$$
where $k$ is some small integer defined later. Such a set of weights can be found rather efficiently (and in polynomial time in general) through lattice basis reduction, e.g. running LLL on the following lattice basis:
$$
\begin{bmatrix}
K A & K A^2 & \dots & K A^m & K \cdot 2^{n/2 + k} \\
1 & 0 & \dots & 0 & 0 \\
0 & 1 & \dots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & 0 \\
0 & 0 & \dots & 1 & 0
\end{bmatrix}
$$
for sufficiently large $K$, as shown by Lagarias and Odlyzko. In practice we expect such weights to exist when
$$m \log_2(W) \approx n/2 + k$$

Guess the lower $k$ bits of $X_0$, and use the LCG property to derive the lower $k$ bits of all $X_i$.

Use the $Y_i$ to obtain the lower $k$ bits of the upper half of all $X_i$. Denote $X^*_i$ as $X_i$ masked to only include those guessed upper bits, that is, $X^*_i = 2^{n/2} \times \mathrm{guess}$.

If we do some basic algebra we can notice that the congruence below follows from (1)

$$
\sum_{i = 1}^{m} w_i \left [ X_{i + 1} - X_i \right ] \equiv 0 \pmod{2^{n/2 + k}} \tag{2}
$$

Since the $w_i$ are bounded by $W$ and we know the most significant bits of the variables involved, we can approximate this sum using our $X^*_i$. In fact we can evaluate it to within $\pm 2 m W \cdot 2^{n/2}$. Compute:

$$
Z = \sum_{i = 1}^{m} w_i \left [ X^*_{i + 1} - X^*_i \right ] \bmod{2^{n/2 + k}}
$$
and let $\Delta$ be the difference between $Z$ and either 0 or $2^{n/2 + k}$, whichever is closest to $Z$.

If $\Delta \geq 2mW \cdot 2^{n/2}$, our guess to the lower bits of $X_0$ is certainly incorrect. Otherwise, it is correct with probability $1 - 2mW \cdot 2^{-k}$ (this makes some assumptions about the distribution of the $Y_i$, but works in practice).

Try all $2^k$ guesses against different windows of outputs $Y_i$ (adjusting accordingly, note that the relation (1) still holds even if you shift all exponents by a fixed constant) until all but one fail to pass the test in step 6. The final candidate guess will be the lower bits of $X_0$.

Repeat all steps, guessing successively higher bits of $X_0$ until the entire internal state is recovered.

This turns out to be very fast as $k$ can be set to be not too much larger than $\log_2{mW}$, for the probability of a false positive in step 6 to be sufficiently small, e.g. 0.5; if $k$ is too small then we extract no information.
Given the above, we should try to force $W$ to be as small as possible in step 1 to minimize the number of bits $k$ to guess, so that, for example, $W \approx 2$, $m \approx n/2 + k$ so $k \approx \log_2(n)$ showing that this attack should scale very well with $n$.
I've implemented this and it works well and successfully recovers the internal state as expected for $n = 128$.
Also it's possible to extend this to unknown increment $C$, the only thing that changes is we need to guess the lower bits of $C$ at the same time as the lower bits of $X_0$ to be able to perform step 2, and everything else stays the same; we recover $C$ and $X_0$ simultaneously through the same process.

References
This approach was adapted from techniques described in "Lattice Reduction: a Toolbox for the Cryptanalyst". This paper contains even more sophisticated techniques for attacking similar kinds of problems and is fairly readable.


What's the meaning of probabilities in differential privacy formula?

No, it means that the functions are chosen from some domain with some probability distribution. This is standard for randomized algorithms.

For simplicity, assume there are $N$ randomized functions $\mathcal{K}$ possible, and one choose one uniformly with probability $1/N.$

For example, if we restricted ourselves to polynomials of degree $\leq k$ over $GF(q),$ there would be $N=q^{k+1}$ such possible functions and we choose a function by uniformly choosing each of its $k+1$ coordinates from $GF(q)$, thus with probability $q^{-(k+1)}.$

In this case the probability expression just means that
$$
\frac{\#\{\mathcal{K}: \mathcal{K}(D_1) \in S\}}{N}\leq
\exp(\epsilon)\frac{\#\{\mathcal{K}: \mathcal{K}(D_2) \in S\}}{N},
$$
and of course $N$ can be cancelled in the two sides of this equation. In general, the distribution may of course not be exactly uniform.


Answering the most general interpretation first, yes, it is possible for some piece of data to take the state to some known state. This is because the compression function that moves from one state to the next necessarily has collisions, because its inputs are larger than outputs. For most states you would expect a single block of data to be enough to take you to any state.

However, such a one-block sequence would not apply universally, it would take from one particular state to the desired state. Finding such a sequence for a particular predetermined (current, desired) pair would amount to a preimage attack on the compression function, which we cannot do in the case of MD5. Best attacks take close to the $2^{128}$ time that brute force does.

If you wanted a sequence that took you from any state to a known state, you would need even more computation. Such a sequence might exist, but it could be long: e.g. if with each block you could halve the possible states you would need $2^{127}$ blocks. A brute force approach would be completely infeasible even in comparison to the earlier attack. Even using the sequence could be infeasible.

Finally, the full state of MD5 is not just the current state vector that the compression function affects. There is also the total length processed (modulo $2^{64}$), which is used when finalizing the value. So you could not use a single "reset sequence" as a literal reset, because it would not take two different-length prefixes to the same full state. (If you had an "universal reset sequence" you could first pad the inputs to the same length, but you would still need to know the lengths.)


What would currently make the strongest https connection?

The cipher suite with the best theoretical security for TLS (v1.2) right now is clearly:

TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA384 with P-521
as the associated curve for the certificate and the key-exchange.
The arguments are simple:

ECDHE and ECDSA with P-521 both provide 256-bit security against forgery / key recovery attacks
AES-256 is the strongest possible AES instance you can get
CBC is the most resilient mode to IV-reuse (you only learn whether two messages share a common prefix)
SHA-384 implies use of HMAC-SHA-384 as the MAC which has a much higher "bit-length-protection" against forgeries than, say GCM

The arguments against it are clear as well:

The support situation is probably horrible, because P-521 isn't exactly the most wide-spread supported curve as is probably the ECDSA-CBC-SHA2 combination
This suite is prone to many (side-channel / padding oracle) attacks on CBC and authenticate-then-encrypt from the past

Note well: Because of these attacks I strongly recommend against using any CBC based cipher suite.

The cipher suite with the best practical security (and somewhat decent support) for TLS (v1.2) right now is clearly:

TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384 with P-384
Downgrade to TLS_ECDHE_WITH_AES_128_GCM_SHA256 with P-256 / P-384 for more supported systems (such as Firefox)

ECDHE and ECDSA with P-384 both provide 192-bit security against forgery / key recovery attacks, which is on the edge of "physically infeasible" and will likely remain unbroken until the rise of quantum computers, the support is really good here, because P-384 is part of NSA's Suite B and many people implemented it because of that
AES-256 is the strongest possible AES instance you can get
GCM is the mode which has seen the least amount of attacks, as predicable IVs are a non-issue and padding doesn't need to take place and authentication is built-in
GCM "only" provides 128-bit forgery security, but this is (a worthy / the) trade-off for a much better side-channel resistance


Looking for cryptographic secure hash algorithm(s) that produces identical root hash for differently sliced hash list

A Hash Tree is meant for that. A binary tree seems fit. I'll restrict the description to something directly derived from SHA-256 (256-bits output, 512-bit hashed per round).

A parameter n>0 is selected, defining a "superblock" size of n*512 bits. Say 8192 bits (1kB, for n=16); n=1 works, but a higher value improves computing efficiency markedly.
The file is padded as in SHA-256, and conceptually organized into m superblocks of that size (the last superblock's size might be shorter, but is mutiple of 512 bits; the padding might be in the last superblock, or span the last two superblocks).
The file is chopped in segments of consecutive superblocks, with the limit of segments on superblock boundaries. Each computation point is assigned a segment which it receives (or generates and pads).
Each computation point separately hash each superblock in its assigned segment, using SHA-256 less padding. Each superblock requires n hash rounds (except the last which may require less). Most of the rounds are performed here (exactly as many as for SHA-256 of the whole file), in a distributed manner.

All the hashes obtained at step 4 form the m leaves on top of a single overall binary tree with a 256-bit hash at each node, and structure independent of how the file was chopped. Each of the m-1 non-leaf node of the tree will be the hash, obtained with one round, of the 512 bits in the two nodes linked on its top-left and top-right. The bottom node of the tree will be the final hash. It will be independent on how the file was chopped at step 3, because the computation will be performed according to the same tree regardless of the chopping.

[drawing of tree needed]

All branches in the tree join adjacent levels, except on the right where the j+1th level from the top is skipped when the jth lower-order bit of m-1 is 0.
The computation point responsible for a segment computes the hashes for nodes which have all their leaves assigned to that segment, and must keep the others. This needs precise organization [and is left as an exercise to the reader; my earlier description was flawed].
Each computation point returns its partial result. That will include Ceil(Log2(k+1)) 256-bit hashes at most, for the partial hash of k superblocks. If the communication is centralized, the central point finishes the calculation, re-hashing according to the same binary tree as necessary. With decentralized communication, it is advantageous to aggregate partial results with a peer handling a segment of the file just before or after, which might allow to perform slightly more of the work.

Note: Computations can be interleaved to reduce storage requirements. There is a total of m-1 extra rounds in steps 5 and 6, an overhead of about 1/n, distributed in part.


It is of base $2$ since it is the number of bits needed to represent in binary form $n$.


Is EKE attackable by a brute-force password search?

Doing EKE over an EC group is a tricky (and is something that RFC6124 avoids).  The problem, as you note, is preventing an attacker from being able to determine whether a possible decryption is impossible (and hence he can remove that potential password from the list); that turns about to be considerably more involved than you would expect.

Even if you skip the first six bytes, well, the EC X and Y coordinates are not actually randomized (even though they look random); these coordinates are actually integers (if you're doing even-characteristic EC, field elements, don't worry about the distinction) which are related by an equation (perhaps $y^2 + ax = x^3 + b \mod p$) that's easy to check; this would easily allow an attacker to do a dictionary attack.

Now, all this can be handled; you can just use the X coordinate (ECDH still works just fine; however, your ECDH package might not support that), and you can deal with the problem that about half of the bit patterns are not possible EC X coordinates (and that's also easy to check); you could modify the encryption algorithm to deal with that as well.

On the other hand, all this is rather tricky for someone who isn't used to working with Elliptic Curves.  I would strongly recommend that you use either EKE using a MODP group (as RFC6124 has; don't forget you have you use the nonstandard generators that RFC6124 has), or go with SRP.


I assume your protocol is message oriented. You needn't repeat the IV, but need to supply a new one for every message.

This can be either:

a random string from a CSPRNG,
a concatenation of a random string (sent once per session, if you're traffic-savvy) and a message counter (can be omitted from the packet, too), or
a member of any other unique sequence of 'reasonably random' block-sized blobs.

For CBC mode, the IVs should be sufficiently random, e.g. output from (2) may be hashed.


How to defend AES against chosen-plaintext attack?

TL;DR: AES is safe against plain-text attacks.

If :

you do not reuse your IV
your IV are random
you use a correct mode of operation (not ECB...)

Then you are safe against such attacks (you need at least these 3 conditions to be met).

On a side note, IV can be public, it is not a problem.

Worth reading:

Why is CBC with predictable IV considered insecure against chosen-plaintext attack?
Why is AES resistant to known-plaintext attacks?
What is the difference between known-plaintext attack and chosen-plaintext attack?


The only difference between these is the nonce size (and, consequently, the internal counter size). The core function is exactly the same. They all offer the exact same security level if they are used as expected.

The trade-offs are described in the AEAD section of the documentation.

XChaCha20-Poly1305-IETF is the one that has the largest nonce size. This significantly reduces the risk of reuse, since it can be randomly chosen without any practical risk of collision. This can also be leveraged to build nonce misuse-resistant schemes.

Unless you specifically need compatibility with a different implementation that doesn't support the XChaCha20 version, this is the one you want to use in virtually all cases.

XChaCha20-Poly1305-IETF is very likely to become the function used by the high-level API in a future libsodium release. Which means that other variants will not be available any longer in minimal builds.

Since your use case appears to be encrypting large messages, the higher-level secretstream API is a better fit. It uses XChaCha20-Poly1305-IETF internally.


Can I make a PRNG that is secure even when state can be modified by user?

This is not secure.  There is a distinguishing attack that involves about $2^{41}$ invocations of the interface.

Define $f(x) = \text{MSB}_{80}(x) \oplus \text{LSB}_{80}(x)$.  Consider applying the following operation, which I'll call "Leap":

Call Read.  Call the result $d$.
Call Update $(0 \, || \, d)$ (i.e., call Update passing the 160-bit value obtained by concatenating 80 zero bits followed by $d$).

Notice that if $s$ is the state before a Leap operation and $s'$ is the state afterwards, then $f(s)=f(s')$.

The attack will involve applying the Leap operation about $2^{40}$ times.  If you examine the internal state $s_i$ after the $i$th Leap operation, it will satisfy $f(s_i)=c$, where $c$ is some constant that is the same for all of them (in fact, $c=f(k)$, where $k$ is the initial state).

Thus, each $s_i$ comes from a space of $2^{80}$ possibilities, and each $s_i$ is basically a random element from that space.  Now by the birthday paradox, once you have $2^{40}$ randomly chosen elements from a universe of size $2^{80}$, there is a pretty good chance that some pair of those elements will be the same.  This means we expect to find some indices $i,j$ such that $s_i=s_j$, i.e., where the state after the $i$th Leap operation is the same as the state after the $j$th Leap operation.

But of course the behavior of the PRNG is a deterministic function of the state.  Therefore, the behavior of the PRNG at time $i+t$ will be the same as the behavior at time $j+t$.  In particular, the sequence of outputs at times $j,j+1,j+2,\dots$ will be a repeat of the sequence of outputs at times $i,i+1,i+2,\dots$.

In other words, if you perform a bunch of Leap operations, the PRNG will enter a cycle and start repeating after about $2^{40}$ steps.  This is too fast.  It's something that a true-random generator would not exhibit.  It allows to distinguish the output of the PRNG from truly random, and to predict future outputs (assuming we continue to apply Leap operations).

By academic standards, this would count as a break of the PRNG, since $2^{40}$ operations is feasible.  By practical standards, it might not be an enormous risk, because it requires that the adversary has a way to alternate Read and Update operations and that the adversary has total control over all of the Update operations -- but it's still a break, by the standards that cryptographers use.

A possible fix would be to change your Update operation to

$$s \gets H(s,v).$$


Complexity of Gaussian Elimination over a Finite Field

The classic Gaussian Elimination algorithm is $O(n^3)$ runtime regardless of specific field and the Matrix, so in this case a finite field $F_q$ of order $q$ doesn't play a role in the complexity. This runtime is due to the fact that you are zeroing out entries in columns column-by-column to get into row reduced echelon form.
For matrices in $GL(n, q)$, the set of $n\times n$ invertible matrices in the finite field of $q$ elements, Andrén et al. in 2007, demostrated a striped Gaussian elimination in

On the complexity of matrix reduction over finite fields

which can shave off a $\log_q n$ factor by attempting to pick row operations that simultaneously zero out entries in multiple columns by using the finite field structure.
They proved that up to a constant factor this algorithm is best possible as almost all matrices in $GL(n, q)$ need asymptotically at least $\frac{n^2}{2 \log_q n}$ operations.
Demetres, in 2014 showed that the striped elimination algorithm is asymptotically optimal by proving that almost all matrices in $GL(n, q)$ need asymptotically at least $\frac{n^2}{\log_q n}$ operations.

The Asymptotic Complexity Of Matrix reduction Over Finite Fields


C# equivalent of openssl ecparam -name prime256v1 -genkey -noout -out

Your question is contradictory and incomplete, as well as being primarily about coding for a particular implementation, which is offtopic and apparently heading (slowly) for closure.

First, the output from openssl ecparam -genkey is NOT PKCS8 format (not either of them); it is the algorithm-specific format from SEC1 (available at http://www.secg.org)(*) including the public point (tagged context[1]) as well as the curve (context[0]). For P256/secp256r1/prime256v1 (in named form) this is 121 bytes in DER if the public point is uncompressed (as is default) and 89 bytes if compressed; in base64 these are 164 and 120 characters and in PEM they are 227 and 182 chars using LF for linebreak or 232 and 186 using CRLF.

Second, the output from that openssl commandline operation, like most others including the ones that are in PKCS8 format, is by default PEM. PEM is NOT just base64 of DER, as you coded; it is base64 of DER PLUS linebreaks PLUS header and trailer, which are important and among other things change the length.

Although I don't have dotnet set up to test, according to the source that BouncyCastle call does produce PKCS8 (unencrypted) 'wrapping' SEC1 (class ECPrivateKeyStructure is in Org.Bouncycastle.Asn1.Sec) with the
curve (which is redundant here) but NOT the public point (see currently line 142, and similarly 126 for ECGOST). That will be 80 bytes DER, 108 chars base64, or 164 or 168 chars PEM. BouncyCastle also has classes to write and read PEM although unencrypted PEM is simple enough you can do it by hand.

If you can specify more exactly what you want, or at least how (and by what software) the result will be used, and thus how it differs from what you have, this will probably be ontopic for StackOverflow or maybe security.SX (which does accept some how-to-code-crypto Qs).

(*) Ironically, secg is currently serving HTTPS with an invalid cert, and so is best accessed HTTP!


(I write $G_n$ for an abelian group of order $n$.)

Well, you can always embed $G_p$ into a group of order $pq$ as a subgroup, but that is probably not what you want.

Besides such trivial cases, this is impossible: The universal property of tensor products uniquely factors any bilinear map
$e\colon\ G_p\times G_p\to G_{pq}$
as
$$e\colon\;G_p\times G_p\twoheadrightarrow G_p\otimes_{\mathbb Z}G_p\xrightarrow{\bar e}G_{pq} \text;$$
note in particular that $\bar e$ has the same image as $e$.
However, since $p$ is prime, $G_p$ is cyclic and $G_p\otimes_{\mathbb Z}G_p\cong G_p$ via the map $a\otimes b\mapsto ab$; thus $\operatorname{im}e=\operatorname{im}\bar e$ has order dividing $p$.

This essentially shows that any such pairing $e$ is either degenerate or given by a pairing $G_p\times G_p\to G_p$ followed by an embedding.

Here is a more elementary proof, using only basic group theory and bilinearity:
Let $e\colon\ G_p\times G_p\to G_{pq}$ be a bilinear pairing and $g$ a generator of $G_p$. Since $e(g^n,g^m)=e(g,g)^{nm}$ for any $n,m\in\mathbb Z$, the element $e(g,g)$ is a generator of the image of $e$. But
$$e(g,g)^p=e(g,g)^p=e(g^p,g)=e(1,g)=e(g^0,g)=e(g,g)^0=1\text,$$ thus the order of $e(g,g)$ divides $p$. This implies (as $p$ is prime) that the image of $e$ is either trivial or isomorphic to $G_p$; in particular $e$ is never surjective.


How many hash collision will exist where the digest is a pre-image?

The expected number of 3-cycles in a random function on a large domain is $1/3$. More generally, for a random function on a set of size $n$, the expected number of cycles of length $\ell$ is asymptotically equivalent to $1/\ell$ as $n \to \infty$.

This result, along with a general approach to the combinatorical properties of random functions, can be found in the paper Random Mapping Statistics by Flajolet and Odlyzko (likely, the result has been derived elsewhere using different methods too).

Let me sketch how this result is obtained. Recall that the functional graph of a mapping is a set of components, each of which consists of a cycle to which trees are connected.

Let $t(z)$ be the exponential generating function for the number of (rooted) trees. It can be shown that (this is known as Cayley's formula)

$$t(z) = \sum_{n = 1}^\infty \frac{n^{n - 1}}{n!} z^n.$$

Since components are cycles of trees, the generating function for the number of components is

$$\log\left(\frac{1}{1-t(z)}\right).$$

Also, the generating function for the number of functional graphs would then be the exponential of the above. In order to count the number of cycles of length $\ell$, one can construct a bivariate generating function for the number of functional graphs in which the second variable "marks" $\ell$-cycles. That is, instead of the above generating function for the number of components, we define

$$\log\left(\frac{1}{1-t(z)}\right) + (u- 1)\frac{t(z)^\ell}{\ell}.$$

That is, the term (in the Taylor series in the variable $t(z)$) corresponding to cycles of length $\ell$ is multiplied by the marker variable $u$. The desired bivariate generating function at the level of the functional graph is then

$$\xi(z, u) = \exp\left(\log\left(\frac{1}{1-t(z)}\right) + (u- 1)\frac{t(z)^\ell}{\ell}\right).$$

One can see that the generating function for the sum of number of cycles of length $\ell$ over all functional graphs of fixed size can then be computed as

$$\Xi(z) = \frac{\partial\xi(z, u)}{\partial u}\Bigg|_{u = 1} = \frac{z^\ell}{\ell(1 - t(z))}.$$

It remains to determine the Maclaurin series coefficients of the above, at least for terms of very high order. This is possible by singularity analysis. We use the fact (by Proposition 1 in the paper of Flajolet and Odlyzko) that (as $z \to 1/e$)

$$1 - t(z) \sim \sqrt{2(1 - ez)}.$$

Hence,

$$\Xi(z) \sim \frac{z^\ell}{\ell\sqrt{2(1 - ez)}}.$$

The singularity analysis technique (Theorem 1 in Flajolet and Odlyzko) then shows that (with $\Xi_n / n!$ the coefficient of order $n$)

$$\Xi_n \overset{\star_1}{\sim} e^n\,\frac{n!}{\sqrt{2}\ell}\,\frac{\sqrt{n}}{n\Gamma(1/2)} \sim \frac{e^n n!}{\ell\sqrt{2\pi n}} \overset{\star_2}{\sim} \frac{n^n}{\ell},$$

where $\star_1$ is the actual singularity analysis and $\star_2$ follows from Stirling's approximation $n! \sim \sqrt{2\pi n}\, n^n/e^n$. In order to obtain the expected value of the number of $\ell$-cycles of a random function on a set of size $n$, it suffices to divide by the number of such functions ($n^n$): $\Xi_n \sim 1/\ell$.


Is there is a way to calculate the public key from the private key in pqNTRUSign algorithm?

I believe that the implementation's API doesn't allow you to derive the public key from the private key.  Instead, the model is that both are generated at the same time by the pq_gen_key function; you are expected to keep around the public key that returns.

Now, with NTRU, one could compute the public key from the private key.  In fact, that is pretty much how pq_gen_key works; it creates the ring elements $f$ and $g$ (which together essentially make up the private key), and then compute the public key from that.  It's just that they haven't bothered exporting that specific functionality.


In General: ZK protocols become insecure if computed concurrently; I think this is what you are referring to. If the protocol is run in parallel, an adversary could request a proof of two relationships and produce a witness for the first with the knowledge gained from the second prover-output. When run concurrently, this attack cannot be executed because the adversary cannot receive a second commitment on the same relation to learn/produce a witness for the first. As far as I know, there is no protocol that achieves concurrent security.


The noise is usually a small term added into the ciphertext while encrypting.

This term may be a small integer (if the scheme is based on integers) or a small polynomial (if the scheme is based on polynomials), etc.

How to decide if a term is small or not depends on the security and correctness properties of each system (for instance, a polynomial is typically considered small if all its coefficients are small).

This noise is added to guarantee the security of the cryptosystems and is sampled from a distribution of small terms (for instance, from a set of polynomials with coefficients in $\{-1, 0, 1\}$). Therefore, the noise is random. So, it implies that the HE scheme is probabilistic, but, in general there are other random values involved in the encryption process, so, I don't know if it is right to say the probabilistic property is due to the noise... (But I hope you got the point).

The decryption function does not work if the noise is greater than a certain maximum value (each scheme with each set of parameters used has its own limit) and the homomorphic operations increase the noise, that is the reason the number of operations is usually limited and there are several techniques to control the noise growth.

As an example, take the symmetric "toy-scheme" from Fully Homomorphic Encryption over the Integers:

the integer $p$ is the private key.
to encrypt a bit $m$ into a (big) integer $c$, we sample integers $q$ and $r$ and do $c = pq + 2r + m$.
to decrypt $c$ we do $c \mod p$, wich gives us $2r + m$ if $2r + m$ is smaller than $p$, then we reduce $\mod 2$, ending up with $m$.

Do you see that if $2r$ is bigger than $p$, then decryption will not work? (because reducing mod $p$ would not result in $2r + m$ in this case). So, this $2r$ is the noise in this scheme.

Note that taking $c_0 = pq_0 + 2r_0 + m_0$ and $c_1 = pq_1 + 2r_1 + m_1$, we have

$c_0 + c_1 = p(q_0 + q_1) + 2(r_0 + r_1) + (m_0 + m_1)$

which means a addition increases the noise. The multiplication also does so (take a look on the paper).

Therefore, since each operation increases the noise and there is a maximum acceptable value for the noise, the number of operations is limited.


Key space vs Cardinality of 1024-bit RSA

Definitions

In RSA, an encryption key is a pair of integers $(N,e)$ with $N$ the product of $m\ge2$ distinct odds secret primes $r_i$ (with $0<i\le m$), and $e$ is such that $\gcd(e,\lambda(N))=1$ where $\lambda(N)=\operatorname{lcm}(r_1-1,\dots,r_m-1)$ is the Carmichael function. It follows that $e$ is odd. Typically, other conditions are added, like $e\ge 3$ (because $e=1$ gives no security), or that each of the $r_i$ is large for some definition of that (because small $r_i$ can be easily found from $N$, and then are no longer secret). Other conditions are commonly added, and discussed later in this answer.

The most natural definition of encryption key space is the set of pairs $(N,e)$ matching the applicable conditions defined in a particular variant of RSA. The cardinality of the encryption key space is the number of elements in that set if it is finite, else the cardinality is $\aleph_0$ (the cardinality of $\mathbb N$ and all countable sets).

Strictly speaking, by the definition above, the cardinality of the encryption key space of 1024-bit RSA is $\aleph_0$, because we put no upper limit on $e$.

Counting classes of equivalent encryption keys

Different encryption keys $(N,e)$ and $(N',e')$ can be equivalent; that is encryption with $(N',e')$ (including with random padding, which is necessary to make RSA encryption secure) can always be reversed by using a decryption key $(N,d)$ corresponding to $(N,e)$. This occurs when one of the following holds:

$N=N'$ and $e\equiv e'\pmod{\lambda(N)}$;
for degenerate keys $e\equiv1\pmod{\lambda(N)}$, $e'\equiv1\pmod{\lambda(N')}$, and the bitsize of $N$ and $N'$ such that padding remains compatible; with the two common PKCS#1 paddings, that's when $\lceil\log_2(N)/8\rceil=\lceil\log_2(N')/8\rceil$.

We can thus use an alternate definition of encryption key space where we assimilate equivalent encryption keys (technically: by considering an element of the set as being an equivalence class of the equivalence relation among $(N,e)$ pairs that we just defined).

Now, for $k$-bit $N$

there are $2^{k-2}$ odd $k$-bit integers, thus no more possible $N$;
for each $N$ we have exactly $\varphi(\lambda(N))$ equivalence classes of encryption keys (where $\varphi$ is the Euler totient function), thus less than $N/4$.

There are thus less than $3\cdot2^{2k-6}$ equivalence classes of $k$-bit encryption keys, about $2^{2043.6}$. This bound could be slightly improved with a better estimate of $\varphi(\lambda(N))$, and removing those $N$ that are either prime or not square-free.

Conditions commonly added to RSA keys

$m=2$ (that is $N$ product of two primes, as in the original RSA paper); this is also mandated by FIPS 186-4. In that case, customarily, we note $p=r_1$ and $q=r_2$.
$\lceil\log_2N\rceil=k$ for $k$ in some limited set, that is $N$ has an exactly prescribed bit length (because that's good for interoperability); FIPS 186-4 mandates $k\in\{1024,2048,3072\}$, with $k=1024$ deprecated.
Bounds on individual primes $r_i$, such as $2^{(k-1)/m}<r_i<2^{k/m}$ (this insures condition 2 for any choice of the $r_i$; helps interoperability of private keys in CRT format; and gives protection against some factorization algorithms). FIPS 186-4 mandates that.
$e\ge e_\text{min}$. Typical values are:

$e_\text{min}=3$ (because that's the fastest secure value of $e$ for RSA using good padding); that's mandated by PKCS#1.
$e_\text{min}=2^{16}+1$ (because that's less insecure than $e=3$ when insecure padding is used, and other debatable reasons); FIPS 186-4 mandates that.

$e\le e_\text{max}$. Typical values are:

$e_\text{max}=e_\text{min}$, which fixes $e$, simplifying things.
$e_\text{max}=2^{16}+1$ (this is the most common $e$ around, and I know no reason to use a larger one).
$e_\text{max}=2^{2^l}-1$ with $l\in\{5,6,7,8\}$, because that puts an end to using ludicrously large $e$ that waste time, energy, and memory. FIPS 186-4 mandates it with $l=8$.
$e_\text{max}=N-1$; that's mandated by PKCS#1. Notice that with this definition, there are always equivalent keys.

Each $r_i-1$ and each $r_i+1$ is known to have a large prime factor, for some definition of large. The rationale is to render some simple factorization algorithms hopeless, and for moderate $\max(\log_2r_i)$ without such requirement it could make sense for an adversary to attempt using these algorithms on each one of a great many $N$, rather than using equivalent effort trying to factor a single $N$ using better algorithms. When $k=1024$, FIPS 186-4 mandates this, with large defined as $>2^{101}$; when $k=2048$ (resp. $k=3072$) this becomes an optional requirement, and large becomes $>2^{141}$ (resp. $>2^{171}$).
For $m=2$, it is common to require that $|p-q|>\Delta$. The only benefits are a simple counterargument to someone pretending that Fermat factorization can factor $N$, and catching a few of the many things that can go wrong in an implementation. FIPS 186-4 sets $\Delta=2^{k/2-100}$.
In addition to condition 6, there might be some upper bound on how large the largest (known) prime factors of $r_i-1$ and $r_i+1$ are. Refer to FIPS 186-4 which has several options in this regard.
In addition to the requirement that each $r_i-1$ has a large prime factor $u$, it has been recommended that $u-1$ has a large prime factor; see this question.
One of many particular key generation algorithm might be specified/used, which will put arbitrary constraints on the $r_i$. For example, algorithm B.3.4 of FIPS 186-4 specifies a deterministic algorithm to generate $N$ from a random seed of exactly $security\_strength$ bits, which (by reference to NIST SP 800-57) must be $80$ (resp. $112$, $128$) when $k=1024$ (resp. $2048$, $3072$).

Evaluating cardinality for a common set of requirements

As example I'll use $m=2$ (cond. 1), $k=1024$ (cond. 2), $a<p<b$ and $a<q<b$ with $a=2^{(k-1)/2}=2^{511.5}$ and $b=2^{k/2}=2^{512}$ (cond. 3), $e=3$ (cond. 4 and 5).

The density of primes near a large $x$ is about $1/\log(x)$, it varies little for $a<x<b$, thus the number of primes in range $]a\dots b[$ is about $t=(b-a)/\log({a+b\over2})\approx2^{501.8}$. Of these, a proportion of about $e-1\over e$ can be used given the requirement $\gcd(e,\lambda(N))=1$. Given that $p\cdot q=q\cdot p$, the cardinality is thus about $(t{e-1\over e})^2/2\approx2^{1001.3}$.

Different key generation requirements can yield vastly different cardinality. For example, the cardinality for 1024-bit RSA with fixed $e$ using algorithm B.3.4 of FIPS 186-4 (see req. 10) is at most $2^{80}$ (and close to that if the seed can take all possible values).


I'd confidently go for "first N bytes". It's quite universally recognized that the output of practical cryptographic hashes are bitstrings or bytestrings; where a bytestring starts is subject to little ambiguity; and how to count starting from that is unambiguous.
That's not to say that an error is impossible. In particular, the MD5 output is 128 bits that internally are 4 words of 32 bits, and MD5 words are to be converted to bytes per little-endian convention. That has caused headaches including to researchers working on MD5, see this anecdote. And later hashes often used with HMAC (e.g. SHA-1, SHA-256 and SHA-512) use big-endian.
Note: even though HMAC-MD5 is still standing strong when the key is secret, is the small speed gain compared to HMAC-SHA-256 or HMAC-SHA-512 worth exposing a design to criticism?


I believe that it is not, but I could easily be wrong.
... I'm having trouble reaching the conclusion of my contradiction

The problem is you can't show that contradiction, because there isn't any. As a rule of thumb for homework questions: If it becomes clear that you can't prove your initial assumption, consider that your intuition was wrong.
Here are some pointers how you can show that $G'$ is in fact a PRG, in a proof by contradiction:

Let's assume $G'$ is not a PRG, and that means a distinguisher $\mathcal{D}$ exists.
The input for $\mathcal{D}$ is one element either uniform random or of the form $x||(G(y)\oplus x)$, and then it has some non-negligible advantage $\epsilon$.
We want to build a distinguisher for $G$. So as input we get one element, which is either from a uniform random distribution or from the image of $G$.
In general, if $a$ is uniform random, then $a \oplus b$ is also uniform random -  this is true as long as $b$ is independent of $a$. This includes fixed $b$ as well as $b$ drawn independently from any distribution.


How to prove that a hash or an encrypted message was obtained from a plaintext that has a certain pattern?

You are correct that a normal hash can't do what you want.  They are designed to not leak any information about the message, so given just the hash output you can't determine if the message has any particular structure.

You can use format-preserving public key encryption on your messages to produce outputs that have the same structure as the inputs no matter what that structure is.  In this way, you have defined a permutation on your legal messages so every output has a pre-image.  In fact, the person running the game doesn't even need to know the answer in order to start a round.  That is, they can set a target value without picking a solution and hashing it.

In practice, this can be easier for some message types than others.  For your permutation example, there's a natural way to map messages to the range $[0, n!)$ so that it's simple to determine if a value is legal.  On the other hand, since your message space ($40! \approx 2^{160}$ bits) is so much smaller than the block size of a reasonable ECC key, it will take a lot of encryption operations to produce a legal message.

Maybe you can use another one-way function like $f(x) = g^x \mod p$ with a $p$ close to the number of valid messages.


What is difference between meet in the middle attack and man in the middle attack?

These are completely different things:

Man-in-the-middle is an active attack to a cryptographic protocol, where the attacker is, effectively, in between the communications of two users, and is capable of intercepting, relying, and (possibly) altering messages. In this case, the meaning of "in the middle" is direct: the attacker is in the middle of two communicating users.
Meet-in-the-middle is a type of cryptanalytic attack that uses some sort of time-space trade-off to drastically reduce the effort to perform a brute-force attack (e.g., transforming an attack that requires $2^{128}$ time into one that takes $2^{64}$ time and $2^{64}$ space). In this case, the name of the attack comes from the expression "let's meet in the middle", which means "to make a compromise". It may also refer to a type of attack over certain block ciphers, where the attacker decompose the problem in two halves and proceeds on each part separately.

The biggest difference between these attacks is that the first one is interactive (i.e., the attacker must participate in the communication), while the second one isn't.

The confusion may come from the fact that certain protocols could receive both type of attacks. For example, in your question you are talking about the Diffie-Hellman key exchange:

A Man-in-the-middle attack to this protocol is exactly the one you describe
A Meet-in-the-middle attack focus on extracting a private key by finding the discrete logarithm using some time-space trade-off (e.g., baby-step giant-step algorithm)


The security of the Diffie-Hellman protocol relies on the decisional Diffie-Hellman assumption. This assumption, in turn, requires the discrete-logarithm problem (DLP) to be hard. In an earlier line of works, heuristic quasi-polynomial algorithms were shown for fields with small characterstic [J,BGJT,GKZ]. A proof (for expected run-time) was recently given by Wesolowski and Kleinjung [WK]. In particular, it was shown that DLP in $\mathbf{F}_{p^n}^\times$ can be solved in (expected) time $(pn)^{O(\log{n})}$. In light of these attacks, the Diffie-Hellman protocol should be avoided in fields of small characteristic.

[J] Joux, A new index calculus algorithm with complexity L(1/4+o(1)) in very small characteristic

[BGJT] Barbulescu et al., A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic

[GKZ] Granger, Kleinjung and Zumbrägel, On the discrete logarithm problem infinite fields of fixed characteristic

[WK] Wesolowski and Kleinjung Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic


Msieve & Yafu - RSA Exponents and bruteforcing

The fact that public exponent $e$ is $17$ does not help. The standard attack against RSA keys generated correctly (except for the small size of their public modulus $N$) is to factor $N$. That's the only input of the factoring task, which is where overwhelmingly most of the effort goes.

$e$ is involved only in preparing the final form of the private key, which is easy: the code to prepare the private key from $e$ and prime factors $p$, $q$ of $N$ is in anything that generates an RSA key in the desired format. For the  $N(n,d)$ format, a working $d$ is $e^{-1}\bmod((p-1)(q-1))$ and that's a one-liner in Python: d=pow(17,-1,(p-1)*(q-1)).

At 512-bit, GNFS is the algorithm of choice and the two usual bottlenecks are sieving and the matrix step. Multiple CPUs definitely help for sieving. For the matrix step, it's complicated, but a machine with large memory is required.

Have a look at CADO-NFS for an implementation.

It is disputed if GPUs are useful at factoring, and I have yet to find any account of actual use at 512-bit.

If you have multiple $N$ with some generated by a defective process, there might be special attacks computing the GCD for pairs of $(N_i,N_j)$, $i<j$. When one is found that is not $1$, that trivially factors $N_i$ and $N_j$. It's worth trying if the "long-shutdown videogame" was using a poor key generator, even more so in a CTF context. There are improvements to this, both computational and to extend the class of exploitable weak generators; see this.


How to generate a bilinear group of prime order p for key generation

Bilinear group in question is expected to be strong enough, and this depends on group order $p$. Namely, group order should be large enough. So, $\lambda$ is order size in bits. That is, size of the binary representation of order. Order of the group, or maybe just size of the order should be known before generating the group. Notation $1^{\lambda}$ is there to say SETUP() accepts a bitstring of size $\lambda$.


Cryptanalysis of a feedback shift reigister with an S-box

why is this cryptosystem "keyed by the contents of the S-box" ?

It means that the content of the S-box is assumed secret, and part of the key (in addition to whatever part of the initial state is not a given).

  How to decrypt the ciphertext if we know the S-box ?

My reading is that what's shown is the keystream generator of a stream cipher, that gets combined by XOR with the plaintext outside of the drawing. We have to guess that, as in a Fibonnaci LFSR, the keystream is what's output on the right, so that the first 32 bits of the keystream are the initial state per some untold convention on bit order, likely the same as in reference material by the same author on Fibonnaci LFSR.

To decipher, the legitimate user would need to know the initial state, and repeatedly extract the right 4 bits and do three independent things with these:

XOR these with 4 bits of ciphertext to decipher 4 bits of plaintext
push these (not the ciphertext nor plaintext) on the left of the LFSR, removing them from the right
feed these in the S-box, and get 4 S-box output bits, that must be combined with XOR into the 4 bits that the above shift has moved on the right of the LFSR, and that the next step will extract.

  What does "information contained by the S-box" mean ?

That means the effective key length that the S-box represents, equivalently the entropy¹ necessary for coding an S-box (that is fully describing the input to output dunction that it implements). If there is a total of $s$ possible distinguishable S-boxes of equal probability, that's $\log_2(s)$.

  How does the invertibility of the S-box affect the bits of information it contains?

Invertibility of an S-box means that no two distinct combination of the $i$ input bits yield the same combination of the $b$ output bits. By the pigeonhole principle it implies $i\le b$ (this is the case here: we have $i=b=4$). This invertibility restricts the number of S-boxes, thus $s$ changes.

¹ If we knew how the keys are turned into an S-box (which is not the case here), we could compute the probability $p_j$ of each distinguishable S-box, and the Shannon entropy could be computed as
$$\displaystyle-\sum_{j\text{ with }p_j>0}p_j\,\log_2(p_j)$$


Your analysis is mostly correct, yet it ignores the reasons CBC has lost favour. CBC requires padding. And we have seen multiple practical attacks on the padding.

Nounce reuse in CTR is indeed much worse than IV reuse in CBC (which is bad enough).

I've seen implementation where the sender sends a full block length nonce(e.g 128 bit) and how he split it up is up to sender. receiver need not verify the bottom part starts with an appropriate number of trailing zeros. In fact the protocol could work even if we start each message with a fully random nonce with no trailing zeros and increment it.


As far as I know, there's no fundamental obstacle that would prevent you from implementing any crypto algorithm you want in JavaScript, whether on the server or the client side.
Compared to an optimized implementation written in C or assembly, JavaScript implementations of low level crypto primitives like block ciphers or PRNGs are likely to be slow and hard to secure against side channel attacks (although there are ways to do that, especially if you know the CPU and interpreter the code is going to run on), but they'll still work.

The big problem with doing crypto in JavaScript on the client side is that, unless you use a secure channel like HTTPS to deliver the code to the client, you have no guarantee that the code the client receives and runs is the same as the code you sent from the server.  And if you do use HTTPS, you might as well just use it to send the data securely to the server, without any need for doing client side JavaScript crypto.

(That said, there are some rare cases where doing crypto even in client side JavaScript might make sense.  For instance, in some cases, you might want to require the client to submit a proof of work before requesting an expensive operation from the server in order to guard against denial of service attacks.  Alternatively, some expensive crypto operations, such as key stretching, can be safely and usefully offloaded to the client entirely (although you should still hash the client-submitted key with a conventional hash function before using it).

However, in both cases, the slowness of JavaScript crypto implementations provides an unwelcome advantage for attackers, who would presumably not run the actual JavaScript but instead reimplement the algorithm in a faster language.  This is one use case where the proposed Web Crypto API might actually be useful, by providing access to fast native crypto primitives from JavaScript.)

In any case, the issues with secure code delivery don't apply to server side JavaScript, since there's no untrusted network over which the code would need to be sent.  However, the performance issues with doing low-level crypto operations in JavaScript are certainly still present, unless your server JavaScript interpreter provides some API to let your JavaScript code make use of fast native crypto primitives.


Is there an algorithm to hide text in another text, while preserving the meaning of the latter?

I think you can embed message $A$ into message $B$ with simple $LSB$, but you will have message $B'$ and maybe  alter the meaning. If you want the message $B'$ to retain the original meaning, you should design $B$ to do that.


Is the identity function a one-way function?

It is not one-way because there is an efficient algorithm which inverts it with probability $1$; namely an algorithm which simply outputs its input.

The fact that we "know the function" is implicit in that no restriction is placed on how the algorithm is "devised", it is only required that such an algorithm exists.


How is a "SHA256 reduced by X of Y rounds" built?

Taken from the OpenBSD implementation of the SHA-2 family at their CVS, where the function SHA256Transform() is used to apply a number of rounds to each block of input. It splits this into the first 16 rounds, and then the remaining ones. A reduced-round implementation of SHA-256 would simply have fewer rounds. This makes the hash significantly weaker.

The transform function:

void
SHA256Transform(u_int32_t *state, const u_int8_t *data)
{
    u_int32_t   a, b, c, d, e, f, g, h, s0, s1;
    u_int32_t   T1, W256[16];
    int     j;

    /* Initialize registers with the prev. intermediate value */
    a = state[0];
    b = state[1];
    c = state[2];
    d = state[3];
    e = state[4];
    f = state[5];
    g = state[6];
    h = state[7];

    j = 0;
    do {
        /* Rounds 0 to 15 (unrolled): */
        ROUND256_0_TO_15(a,b,c,d,e,f,g,h);
        ROUND256_0_TO_15(h,a,b,c,d,e,f,g);
        ROUND256_0_TO_15(g,h,a,b,c,d,e,f);
        ROUND256_0_TO_15(f,g,h,a,b,c,d,e);
        ROUND256_0_TO_15(e,f,g,h,a,b,c,d);
        ROUND256_0_TO_15(d,e,f,g,h,a,b,c);
        ROUND256_0_TO_15(c,d,e,f,g,h,a,b);
        ROUND256_0_TO_15(b,c,d,e,f,g,h,a);
    } while (j < 16);

    /* Now for the remaining rounds to 64: */
    do {
        ROUND256(a,b,c,d,e,f,g,h);
        ROUND256(h,a,b,c,d,e,f,g);
        ROUND256(g,h,a,b,c,d,e,f);
        ROUND256(f,g,h,a,b,c,d,e);
        ROUND256(e,f,g,h,a,b,c,d);
        ROUND256(d,e,f,g,h,a,b,c);
        ROUND256(c,d,e,f,g,h,a,b);
        ROUND256(b,c,d,e,f,g,h,a);
    } while (j < 64);

    /* Compute the current intermediate hash value */
    state[0] += a;
    state[1] += b;
    state[2] += c;
    state[3] += d;
    state[4] += e;
    state[5] += f;
    state[6] += g;
    state[7] += h;

    /* Clean up */
    a = b = c = d = e = f = g = h = T1 = 0;
}

The round macros are declared as follows:

/* Unrolled SHA-256 round macros: */

#define ROUND256_0_TO_15(a,b,c,d,e,f,g,h) do {                  \
    W256[j] = (u_int32_t)data[3] | ((u_int32_t)data[2] << 8) |      \
        ((u_int32_t)data[1] << 16) | ((u_int32_t)data[0] << 24);        \
    data += 4;                              \
    T1 = (h) + Sigma1_256((e)) + Ch((e), (f), (g)) + K256[j] + W256[j]; \
    (d) += T1;                              \
    (h) = T1 + Sigma0_256((a)) + Maj((a), (b), (c));            \
    j++;                                    \
} while(0)

#define ROUND256(a,b,c,d,e,f,g,h) do {                      \
    s0 = W256[(j+1)&0x0f];                          \
    s0 = sigma0_256(s0);                            \
    s1 = W256[(j+14)&0x0f];                         \
    s1 = sigma1_256(s1);                            \
    T1 = (h) + Sigma1_256((e)) + Ch((e), (f), (g)) + K256[j] +      \
         (W256[j&0x0f] += s1 + W256[(j+9)&0x0f] + s0);          \
    (d) += T1;                              \
    (h) = T1 + Sigma0_256((a)) + Maj((a), (b), (c));            \
    j++;                                    \
} while(0)


A lot of modern cryptography is based on some mathematical assumptions and aims to achieve what is called Computational Security. That means that the adversary (Eve) could get some information about the plaintext with a negligible probability and the adversary is modeled as someone with bounded computational power, storage and bounded time.
So all the (encryption) schemes are dimensioned in sort to achieve such level of security: that means that all mathematical elements are chosen to be large enough to make the best known attack feasible in a reasonable amount of time.

Even if this is a weaker notion of security, this assumption on the adversary is easy to accept in practice.

Other approach exists: Information theoretic Security or Perfect Security

So coming back to your solution based on a big table, if the scheme is correctly dimensioned the table you are supposed to use to attack the scheme would be so large that it cannot be stored in a (very very) large disk or to be (too) long to be generated.


Malicious DH parameters without using composite numbers

[Update: See this answer to another question for an example of a back door that can't be detected, but can probably be excluded by demanding a rigid process like RFC 2412 as was used for all the RFC 3526 groups.]

If there were a known way to put a back door into Diffie–Hellman parameters, it would be excluded by standard criteria for selecting them.  poncho's answer to the question you cited provides some examples of criteria we normally use and how to test them and what goes wrong if you don't; there are a couple more references in an answer I wrote.

For finite-field DH, there's little reason to use anything other than the RFC 3526 groups, which use a modulus of the form $$2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi \rfloor + c)$$ where $c$ is the smallest nonnegative integer making this number a safe prime congruent to 7 modulo 8.

For elliptic-curve DH, there's little reason to use anything other than X25519 or X448 except perhaps in exotic applications where essentially the same security criteria might be applied to maximize other performance objectives.


How much data can I encrypt with RSA before I need to change the key

The reason that you won't find much is that RSA is generally not used for bulk encryption, instead hybrid encryption is used.

For RSA using PKCS #1 v1.5 padding you generally don't want to go above $2^{31}$ but hopefully significantly fewer iterations. This is because of the birthday bound on the random padding used. If the random padding is identical to an earlier random padding then you can distinguish if a message is identical to a previous message.

Of course, this would assume you use all the 245 bytes of the possible payload, leaving you with significantly less than 1TB to encrypt. How much less depends on the risk you want to take with regard to duplicate ciphertext values. Note that if you would use less then 245 bytes for payload, then the number of padding bytes increases. If you would use only 237 bytes of payload then the random padding is about 128 bits and you would not have any problems with repeated ciphertext anymore.

If you just use hybrid encryption: encrypt an random AES data key with full padding then the amount of times RSA can be used is virtually without limit. To be more secure you should look at hybrid encryption with OAEP padding and preferably an authenticated mode for AES such as AES-GCM. For larger messages this will be more efficient (regarding CPU and ciphertext expansion - not to mention the taxation of the RNG) as well as more secure.


How do Quadratic Residues work and how do they relate to Diffie Hellman?

Can someone explain Quadratic residues to me in english?

A value $x$ is a Quadratic residue modulo $p$ if there exists a value $t$ for which $t^2 \bmod p = x$.

That is, we take $t$, square it (that's the Quadratic part), and then take it modulo $p$ (that's the residue part, that is, the part that's left over after removing all the multiples of $p$), and that gives us the value $x$.  If such a process can give us $x$, we say that $x$ is a Quadratic Residue.

For example, $2$ is Quadratic Residue modulo $7$ (because if we start with $3$, square it, and then take that result modulo $7$, we end up with $2$); however $3$ is not (can be verified by computing $1^2 \bmod 7, 2^2 \bmod 7, 3^2 \bmod 7, …, 6^2 \bmod 7$)

Also, in this answer, I have been careful to always say "Quadratic Residue modulo $p$"; obviously, the same value $x$ can be a Quadratic Residue modulo some prime $p$ and not modulo another prime $q$.  Normally, you'll see the statement "$x" is a Quadratic Residue"; they mean modulo something, but that something is implicit (as they are working in a specific group, which should be obvious from context).

Important facts:

If $p$ is a prime greater than 2, then some of the values between $1$ and $p-1$ will be Quadratic Residues modulo $p$, and some will not be.  In fact, precisely half of those values will be and half will not.
If $p$ is a prime, then $a \times b \bmod p$ will be a Quadratic Residue modulo $p$ if either both $a$ and $b$ are Quadratic Residues, or both are not.
If $p$ is a prime, it turns out to be simple to check where $x$ is a Quadratic Residue mod $p$.

  And how are they incorporated in Diffie-Hellman?

Mostly, it's not.  If the Diffie-Hellman generator $g$ is not a Quadratic Residue modulo $p$, then given $g^a \bmod p$, we can determine whether $a$ is even or odd; given $g^a \bmod p, g^b \bmod p$, we can determine whether $g^{ab} \bmod p$ is a Quadratic Residue modulo $p$ or not.  On the other hand, we generally perform Diffie-Hellman using a generate that generates a large prime subgroup; such a generator will always be a Quadratic Residue modulo $p$, and so examining the values $g^a \bmod p, g^b \bmod p$ doesn't tell us anything.

  Is there a difference in using them vs cubic residues?

If $p$ is a prime where $p \equiv 2 \bmod 3$, then cubic residues modulo $p$ are uninteresting; all values $x$ are Cubic Residues modulo $p$.

If $p$ is a prime with $p \equiv 1 \bmod 3$, then a third of the values between $1$ and $p-1$ will be cubic residues modulo $p$, and two thirds will notbe.  On the other hand, the same Diffie-Hellman logic applies; if $g$ generates a large prime subgroup, then $g$ will be a cubic residue modulo $p$, and so will $g^a \bmod p, g^b \bmod p, g^{ab} \bmod p$ as well...


Finding the AES key with access to the function

No. What you have access to is called an oracle. It is an entity that encrypts or decrypts arbitrary data with a given secret key. A modern and secure block cipher like AES remains secure from key recovery even in the face of an encryption or decryption oracle. If it was not, the cipher would be considered fatally broken. The best-known way to recover the key with what you have is exhaustive search (brute force).


How to retrieve the plaintext of a substitution ciphertext?

I think frequency analysis is the preferred approach for breaking substitution ciphers. The more ciphertext you have, the better it is. My suggestion would be to do the following:

First, you compute two probability distributions:

a distribution that contains the probability of the symbols in a reference text of the same language and technical area than then expected message.
a distribution that contains the probability of the symbols in your ciphertext.

Once you have these distributions you have a significant knowledge. Instead of trying all possible permutations in brute force, you can now try the most probable ones first. For each permutation, you can check if the probabilities of the symbols in the ciphertext correspond to the probabilities of the symbols in the reference text.

The Kullbach-Leibler (KL) distance is often used to measure the similarity of two probability distributions. You will ideally start your search with the permutation that minimizes the KL distance and then proceed to permutations with a higher KL distance.

For each permutation you then substitute the symbols accordingly and you check if words that frequently appear in your reference text are also found in the decoded text. You keep the best solution which has the most matches, and you continue the search.

The probability to find a better decryption will decrease the longer you search. So you can just stop after some time. You have to decide when exactly the algorithm will stop, but here again you have the probabilites and the KL distance to help you make this decision.


Verifying DER encoded DSA/ECDSA signature with extra content?

I don't think there's an exact "correct" behaviour in this case.
It would be up to the implementation to decide, since the spec is only concerned about the DER encoded portion.

If your implementation parses the input as it moves along only, and doesn't concern itself with the overall size, then it would work fine.

Having said that, I believe the best practice is always to verify input boundaries, and in this case, that would mean the trailing extra bytes should get caught. If they have no business being there, then they shouldn't.

There can be security or crypto implications if there's a bug in the parsing of the input.


On-the-fly computation of AES Round Keys for decryption?

This self-answer is heavily based on comments by Paŭlo Ebermann.

When performing AES decryption with on-the-fly computation of AES Round Keys, there is no choice beyond running the key schedule forward to the last Round Key (the first used when deciphering). The structure of the key schedule creates enough non-linearity and diffusion at each of the 10 steps that no shortcut is practicable. One step comprises 4 SubBytes transformations, 16 XORs of 8-bit quantities, some rotations of all the 16 bytes of the Round Keys, and the doubling of the byte Rcon in $\operatorname{GF}(2^8)$, in a manner such that what's produced by a byte XOR goes thru SubBytes on the next step, and non-linearly influence all the 16 bytes after 4 steps. Even halving the number of steps to reach the last Round Key would be extremely hairy, to the point of being counterproductive.

There are however two implementation variants:

If about 160 bytes of additional temporary RAM are available, the Round Keys can be stored as they are computed, and re-used during the decryption.
Otherwise (and memory is often tight in a small micro-controller, or unavailable in hardware), each of the 10 steps can easily be reversed. The only remote difficulty is the un-doubling of the Rcon; it can be implemented using a small ROM table, or as Rcon=((0x00-(Rcon&0x01))&0x8D)^(Rcon>>1). As pointed by Craig McQueen in comment, the reversal of the key schedule uses the direct AES SBox.

Hardware implementations typically do 2; both options are justifiable in software.


Why do elliptic curves require fewer bits for the same security level?

The best algorithm for computing discrete logs in a well-chosen finite field $\mathbb Z/p\mathbb Z$, where the safe prime $p$ has no structure that can be exploited by the special number field sieve, is the general number field sieve, or GNFS for short.  The GNFS costs $L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$ bit operations, where $L = e^{n^{1/3} (\log n)^{2/3}}$ and $n = \log p$.  If we treat the $o(1)$ term as zero, to raise this cost above $2^{128}$ we need to pick $n$ so that $$2^{128} \leq e^{1.92999 n^{1/3} (\log n)^{2/3}}.$$  Solving this in closed form is a pain involving the Lambert W product log function, but if we restrict our search to $1024 t$-bit primes $p$ so that $n \approx 1024 t \log 2$, we find the smallest bit size is $1024 t = 3072$.  If we allow merely raising the cost above $2^{112}$, we can make do with $1024 t = 2048$.

\begin{equation}
\begin{array}{cc}
\text{modulus bit size} & \text{GNFS cost: $L^{1.92999}$} \\
\hline
1024 & 2^{87} \\
2048 & 2^{117} \\
3072 & 2^{139} \\
4096 & 2^{157}
\end{array}
\end{equation}

Caveat: There may be batch optimizations like there are in the NFS for factoring[1].  So these may be optimistic overestimates when the adversary has a large number of targets to attack simultaneously.  There are also other reasons—performance, storage costs, and side channel security—to prefer elliptic curve groups over finite fields, but that's a topic for another question.

In contrast, the best algorithm for computing discrete logs in a well-chosen elliptic curve group of order $\ell$ is essentially a generic algorithm for finding discrete logs in an arbitrary group, namely Pollard's $\rho$ algorithm, with merely small constant factor speedups for elliptic curves, and costs $\sqrt{\ell \pi/4}$ curve additions, which will require hundreds of bit operations apiece.

The square root cost means that if we want the cost of an attack to be $2^\lambda$ then we need to choose a group of prime order $(2^\lambda)^2 = 2^{2\lambda}$.  By Hasse's theorem, the order of the curve group over a coordinate field of order $q$ can't differ from $q$ by more than about $\sqrt q$, so we need to choose a curve over a finite field with about twice as many bits as we want bits of security $\lambda$.  Some curves like NIST P-224 are chosen to have groups of prime order, while others like Curve25519 are chosen to have groups of composite order $h \ell$ for small cofactor $h = 8$ and large prime $\ell$ so $\ell \approx q/h$.

\begin{equation}
\begin{array}{cccc}
\text{group} & q & {\approx}\ell & \text{$\rho$ cost: $\sqrt{\ell \pi/4}$} \\
\hline
\text{NIST P-224} & 2^{224} - 2^{96} + 1 & 2^{224} & 2^{111} \\
\text{Curve25519} & 2^{255} - 19 & 2^{252} & 2^{125} \\
\text{edwards448} & 2^{448} - 2^{224} - 1 & 2^{445} & 2^{222}
\end{array}
\end{equation}

In brief, there are much cheaper algorithms for computing discrete logs in the finite field $\mathbb Z/p\mathbb Z$ than for computing discrete logs in the elliptic curve $E(\mathbb F_q)$, so we need to choose $p$ much higher than $q$ for the same security.


is it unsafe to AES encrypt using multiple modes?

When combined with your comments, I can say this is unsafe in the sense that it is highly advised against "rolling your own encryption."
It looks to me like you are layering multiple encryption methods together without too great of a concern for understanding the attacks made against them.  Is this secure?  Maybe.  In theory, we designed these algorithms sufficiently well that your outermost layer provides you enough protection.  Of course, in that case, all your layering really isn't making you more secure.
In general, it is recommended that you use one algorithm, the way it is typically used.  Then, if you identify a particular attack vector you care about which isn't handled by that algorithm, you can look at a careful layering.  For example, you specifically want a slow algorithm for hashing the key.  You then may layer PBKDF2-256 onto your process in order to achieve that specific goal.
In theory, AES was well designed enough that you can get away with layering, and the strength of the encryption you have is at least as strong as the outer layer.  However, if you are layering encryption schemes without thinking through the threat model carefully, you could get unlucky and break a key feature of one layer with a feature of another.  Its not the layering that's the issue, but rather the mindset that layering makes it stronger that is the issue.  This is not always provably the case, and it puts you at risk for future decisions you might make, thinking you are making the product stronger.
A test you can give yourself: If I want to do X in cryptography, do I see any commercial or open source libraries doing X?  If not, that's a sign that what I'm doing is unorthodox and may not be as secure as I think it is.


Currently there is (at least) one paper in the lattice literature regarding speeding up lattice basis reduction with Grover search: A Faster Lattice Reduction Method Using Quantum Search. Indirectly, there have also been a few theoretical improvements to subroutines of lattice basis reduction, such as speeding up solving exact SVP with quantum search.

In practice though, the current fastest method in high dimensions is probably BKZ, using lattice enumeration with extreme pruning as the exact SVP subroutine. For this combination of methods, I do not believe anyone ever came up with a significant speedup based on Grover searching, as both methods do not involve a straightforward search over a long, predefined list.

Remark 1: Grover searching generally leads to a decrease in the time complexity for solving a hard problem from $T$ (classically) to at least $\sqrt{T}$ (quantumly). With $T$ scaling exponentially in the lattice dimension, this means we need to increase the lattice dimension by at most a factor $2$ to maintain security. Commonly such improvements in the runtime are not considered a "break" of the scheme.

Remark 2: All of the security estimates for cryptography are just that: estimates. There is no proof that no (classical or quantum) algorithm can quickly solve problems which we now presume are hard to solve. We just don't know any fast ways to solve these problems. So we do not know with certainty that cryptography is secure, classically or quantumly.


The infinite garble extension makes sure that if a ciphertext block is changed that this block and each block after it doesn't decrypt correctly. The way that additional plaintext is affected when the ciphertext is changed is called error propagation. Error propagation over large parts of the plaintext is mainly interesting if you want to combine it with some MDC: Manipulation Detection Code. Then the MDC can be used to verify integrity of the plaintext.

Nowadays we simply encrypt-and-authenticate using CBC + MAC or an authenticated cipher. Error propagation is of little use if you're already verified the ciphertext for integrity and authenticity. Hence you won't find too many mentions of these (computationally intensive) modes of operation; they are mainly used for niche problems where using an authentication tag isn't the right solution.

With most other modes there is a limited amount of error propagation. With CBC and CBF only the same plaintext block and the next plaintext block will not be the original plaintext. With CTR mode only the modified bits are affected; there is no error propagation.

There is also Bi-IGE which does the same, but in two directions: every plaintext block will be changed even if just one bit of ciphertext is changed. So each bit of plaintext is flipped with a 50% possibility (and at least 1 bit with 100% certainty, but that's inconsequential).

More information can be found in my question and the resulting answer about MDC / IGE.


The question seems that it could be implying that you actually intended to ask about probability of any given index not colliding, as opposed to the probability of every index simultaneously not colliding. If this is the case, then the answer is trivial: Two outputs of any PRF, even at the same index, are independent random variables by definition and therefore collide with probability $\frac{1}{n}$.

However, in the case that you really do mean the universal notion, the situation is just slightly more involved: Any PRF with an output size $a$ (in bits) and an input size $b$ has this property with probability approximately $1-2^{a-b}$.

To see this, let $\rho$ denote the probability that the desired property holds, and take the codomain to be of size $\alpha n$ where $\alpha$ is a constant.

$$\rho = \Pr(\forall i \in [0, n]: PRF(k_1, i)\neq PRF(k_2,i))$$
Assuming the values are i.i.d:
$$\rho = \Pr(PRF(k_1,i) \neq PRF(k_2,i))^{n+1}$$
Assuming the values are uniform:
$$\rho = \left(1-\frac{1}{\alpha n}\right)^{n+1}$$
Taking the limit as $n\to\infty$:
$$\rho \approx e^{-1/\alpha}$$
Which is within 5% of the true value when $n \geq 32$ and $\alpha \geq 1$. We assume $\rho = 1-\frac{1}{z}$ and solve for $\log_2\alpha$, which is by definition the number of output bits minus the number of input bits:
$$e^{-1/\alpha} = 1-\frac{1}{z}$$
$$\alpha = \left(\log\frac{z}{z-1}\right)^{-1}$$
$$\log_2\alpha = -\log_2\log\frac{z}{z-1}$$
Which is always within half of one bit to the true value, as long as $z \leq e^n$. We simplify again with another convenient approximation:
$$\log_2\alpha \approx \log_2 z$$
Which is at worst one half bit below the true value. Since the probability of your condition holding is determined by $z$, and $\alpha$ is the ratio between the cardinalities of the output and input domains, the probability of your condition holding is approximately proportional to the size of the output domain divided by the size of the input domain. $\square$


As @kelalaka pointed out OTP is not “differentially secure”. In addition it has the property, like all additive ciphers which work by modular addition of a keystream, that the keystream and the plaintext have symmetric roles.

What I mean is your suggestion to add the string $b$ to the key $k$ is essentially equivalent to the weakness resulting from reusing plaintext as in VENONA.

The constant $b$ is visible to differential attacks, such as crib dragging. In this case, it is the keystream that is differentially deficient.


Does double hashing increase resistant against first preimage attacks?

Define $g(x)=h(h(x)).$ If the original preimage attack has complexity $C,$ and success probability $p$ then depending on what kind of structural properties of SHA256 it uses, you should be able to use the same principle and have complexity $2C=O(C)$ at the cost of reduced success probability $p^2.$

After all the preimage of $y$ under $g$ is just the preimage of the preimage of $y$ under $h,$ and if the original attack works it should not depend on some deep properties of $x$ but only the properties of the hash function $h$.

In particular, it should work to find the preimage of $z=h^{-1}(y)$ when you apply it to $z.$

It's up to you whether you call this an "improvement" or not. It's very marginal if we operate in a regime where success probability is nearly $1.$

There is the convention in computer science that a randomized algorithm is deemed to be successful if its success probability $p$ obeys $p\geq 2/3,$ so you can read the above comment in this light.

CoDomain Issue: As in the comments, we can only use the preimage $h^{-1}(y)$ as input to the next stage if it falls into the hash output space. This is more tricky; if we assume $h$ behaves like a random function on its codomain then each output $y$ will have no preimages with probability roughly $e^{-1},$ and otherwise an average of $1/(1-e^{-1})$ preimages with the highest possible number likely to be around $\log(n)/\log\log(n)$ where $n=2^{256}.$ So the complexity of a preimage attack restricted to the codomain will be comparable to the regularly assumed complexity of an arbitrary preimage attack under the random oracle model which is that to be successful with probability $q$ you need to try $q n$ random inputs.

See the report (search on http://cacr.uwaterloo.ca/): Stinson, D.R., Some Observations on the Theory of Cryptographic Hash Functions CACR Research Report, September 12, 2002.


HMAC-SHA1( secret key ) with header of a transmitted file

It's probably better to use a KBKDF as that doesn't need a key as input. You can use the KDF as key check value or KCV. If you use a block cipher based KBKDF from NIST SP 800-108 then you could reuse the AES algorithm to calculate the KCV.

You could however also make it easy for yourself and use a SHA-1 or SHA-2 over the key as KCV.

Note that the PKCS#11 method allows for calculating a KCV by encrypting a block of all zero's; this method should not be used.


Where can I find test vectors for ciphers?

For any of the algorithms approved by NIST you can usually find the test vectors in the Cryptographic Algorithm Validation Program (CAVP)  - for instance for 3DES in appendix B and AES in appendix C. Test vectors are usually found in one of the appendixes or later sections of the documents.

For any others you should first look to the standard documents, preferably RFC's - for instance for RC4. If the standard documents do not contain test vectors then take an addition look at the company or organization; they often would have a separate document with test vectors. Some standards, such as the PKCS standards may also be referenced or copied by other standards, so if you cannot find it in one document you may want to look for copies. In general, cryptographic competitions require the submitter of proposals to include test vectors.

If you cannot find it that way you will have to rely on Google, or a forum such as this one. Or you could take a reference implementation and test your implementation against that. If that is not available, try and generate them yourself from the leading implementation.

Official test vectors are not always available, even in this day and age. If they are, they may not be complete in the sense that they would cover all possible code paths. Never just test against test vectors and think your implementation is sound or secure if they succeed; provide good coverage and remember to test your own corner cases.


The only requirement posed to the nonce in the "Security Model" paragraph of the crypto_box documentation is uniqueness for each pair of communicating parties. In fact, the documentation explicitly recommends incrementing nonces starting from zero (which an attacker could easily brute-force) or random nonces (which need to be transmitted together with the ciphertext anyway).

Therefore, sending the nonce publicly should be secure (unless some underlying primitive is broken, of course).


You're barking up the wrong tree.
To answer the stated question, OpenPGP doesn't support or use RSA-PSS, at least not yet. For RSA signature, EMSA-PKCS1-v1_5 from PKCS1, referenced as rfc3447 (which republished PKCS1v2.1) and actually copied for your convenience into rfc4880 13.1.3 (though without the precomputed DigestInfo encodings), is the hash and padding together. Other PGP signature algorithms don't use padding (or only trivially). And it's not just the CLI; PGP protocols and formats are the same for all modes of GPG.
But your padding is fine; it's the hash that's wrong. In your posted message-and-decode, the signature given is a valid v1_5 signature for the SHA512 hash
89 6e e3 83 f0 24 e7 ba 4e 12 87 36 bd dd 55 fb 1d 8e 20 b0 f2 72 c6 3c e3 53 29 23 47 41 28 c9 b7 f4 51 ea 39 cd 1c ae ee 29 c2 e4 d4 13 fb 05 dd 89 bd 6b f7 20 76 63 95 f5 f8 b7 79 b2 d1 1b
-- or to be exact, since the v1_5 signature scheme includes hashing, it is the signature for data with that SHA512 hash. However, as shown in your previous Q&A, the correct hash for this publickey is 2f 9b ad fd 89 90 e9 34 f3 15 c6 9c c5 8e 45 12 47 29 fe ab e6 18 a2 e2 71 fb bf e1 9e 20 10 8a 86 ea d9 dd 5b 87 58 87 45 85 98 2a 68 14 e9 e2 ef 9e b6 07 12 1d 9b 7c 15 8f 58 79 c2 92 c5 e9. The former value is in fact the SHA512 hash of the latter, aka the hash of the hash. Probably you have given the hash value as data to a signing mechanism that both hashes and signs its input -- as v1_5 signature implementations usually do, so they can ensure the same hash is applied to the data as is encoded in the DigestInfo. In particular a mechanism named 'SHA512-RSA-PKCS' almost certainly applies the hash (SHA512) AND pads and modexps the result.
To fix your actual problem, you should give the data not the hash as input to the signing mechanism, and not change anything relating to padding in any way.


Leak-proof protocol: is such a thing possible?

It doesn't work without further restrictions.

For simplification, let's assume Alice encrypts a bunch of files but doesn't have to send all of them to Bob. She can still decide to re-order the files or leave out some.

Then she can encode the secret shared key between Alice and Bob in the least significant bits of the ciphertexts without changing the files. She is only rearranging them so that Eve can extract the key. But if Bob checks the integrity of each message, it holds.

If more files are transmitted than the keylength, this works. Otherwise, more than one bit has to be encoded in less messages. And in order to get enough decryptable ciphertexts more files might have to be encrypted.


Yes, you can do that as long as you promise to not to use the hash for any other purpose that would be compromised if the shorter hash would leak. However, if you  need fewer than 128 bits then you might as well use SHA-3 and truncate that; it depends on the purpose if SHAKE128 is better than, say, SHA-3-256; they both depend on the same underlying sponge function after all.

Note that neither SHAKE128 or SHA-3-256 output any characters. They generate binary bits or - for most implementations - bytes. The hexadecimal characters that you're showing are just a representation of those bytes.


Yes, an additional bit permutation of pseudo-random data from a secure Pseudo-Random Number Generator is secure, subject to the condition that this bit permutation is independent of the key material of the PRNG and of any data derived from that (including the pseudo-random data).

An argument is that if this permutation is public, the adversary can do/undo it at negligible cost and is back to the original problem of breaking the PRNG (with no usable information, given the sated condition); if this permutation is secret, its addition can only be an additional complexity for the attacker (given the stated condition). That could be formalized.

If the stated condition is not met, a counterexample can often be found. For example, if the permutation is chosen from the output of the original PRNG so as to put all the 0 bits first, then the output is weak. Same if the permutation is part of the key of a cipher, with the cipher ending in that permutation, and the cipher transformed into a PRNG by using counter mode.


Difference Between PEM vs P12 vs CRT vs JKS vs keystore vs PKCS vs x509 certificates

I got some information from Wikipedia,
In cryptography, X.509 is a standard defining the format of public key certificates.

**Certificate filename extensions**

There are several commonly used filename extensions for X.509 certificates. Unfortunately, some of these extensions are also used for other data such as private keys.

.pem – (Privacy-enhanced Electronic Mail) Base64 encoded DER certificate, enclosed between "-----BEGIN CERTIFICATE-----" and "-----END CERTIFICATE-----"
.cer, .crt, .der – usually in binary DER form, but Base64-encoded certificates are common too (see .pem above)
.p7b, .p7c – PKCS#7 SignedData structure without data, just certificate(s) or CRL(s)
.p12 – PKCS#12, may contain certificate(s) (public) and private keys (password protected)
.pfx – PFX, predecessor of PKCS#12 (usually contains data in PKCS#12 format, e.g., with PFX files generated in IIS)
PKCS#7 is a standard for signing or encrypting (officially called "enveloping") data. Since the certificate is needed to verify signed data, it is possible to include them in the SignedData structure. A .P7C file is a degenerated SignedData structure, without any data to sign.[citation needed]

PKCS#12 evolved from the personal information exchange (PFX) standard and is used to exchange public and private objects in a single file.[citation needed]

https://en.wikipedia.org/wiki/X.509


MAC providing sender authentication (follow up question)

The statement you copied from the other question is incorrect. A MAC does authenticate a message (would be a rather stupid name, otherwise). If you have verified a MAC, you can be sure that the message was sent by anyone knowing the secret key. This is slightly weaker than the authentication done by a digital signature, because there are usually more parties in possession of the key.

  This triggered a question, what if the key used for the MAC came from
  an authenticated key agreement?
  [...]

Your logic is correct. That is exactly what most secure network protocols (like TLS or SSH) do.

  A second question, is there a security reason why then not to use the
  public and private key pair to calculate digital signatures on the
  messages? Instead of using the MAC?

That has performance reasons. Public Key operations are slower, need more memory and the output size is larger, compared to their symmetric counterparts.


Is this a correct way of use symmetric encryption?

What you did seems fine for verifying the key is correct.

However, unless AES256_encrypt uses an authenticated mode of encryption (in which case the whole exercise would be unnecessary), there is nothing that prevents an attacker from modifying the message. And depending on the mode of encryption used, that can even compromise the privacy of the message.

It would be best to use authentication. For example, you could calculate an HMAC over the data. That immediately proves that the HMAC key is correct if the message authenticates. To prove the AES key is correct as well you can derive them both from the same base key, e.g. a = HMAC(k, 'auth'), e = HMAC(k, 'enc') and then use key a for an HMAC over the ciphertext and e for AES encryption.


What is the flaw in this model for homomorphic encryption?

The last paragraph of Section 2.3 of Gentry's "easy" intro to homomorphic encryption, I believe, contains an important result which applies to your model.

  Researchers [1, 8] showed that if $\mathcal{E}$ is a deterministic fully homomorphic encryption scheme (or, more broadly, one for which it is easy to tell whether two ciphertexts encrypt the same thing), then $\mathcal{E}$ can be broken in sub-exponential time, and in only polynomial time (i.e., efficiently) on a quantum computer.

Where 1 is Algorithms for black-box fields and their application to cryptography and 8 is Quantum algorithms for some hidden shift problems.

Since your isomorphism is deterministic, this would most definitely apply. Granted, just because it can definitely be broken in sub-exponential time does not mean there is no hope (RSA can be broken in sub-exponential time), you are going to have to give a very good hardness proof to get anyone to use your system.


repeatedly hashing result and using reverse sequence as RNG secure?

A: No, an attacker can not guess an earlier number. That would amount to a preimage attack for the hash. S/he can not even gain a sizable advantage towards such guess. Arguments (not proofs)

Assuming $\text{secret}$ is full-entropy, the first hashing causes a sizable entropy loss ($0.827\ldots$ bit, see this), and each further hash causes a further entropy loss, but by an heuristic argument, after $k$ iterations, only $\approx\log k$ entropy is lost, thus plenty enough remains (for SHA3-224 and a million millions iterations, >195 bits).
Because it is added a counter rather than a constant, the $N_i$ falling into a short cycle becomes next to impossible, rather than very improbable.

B: The first number disclosed $N_k$ should come with it's index $k$, so that verification of the next number disclosed $N_{k-1}$ is possible by checking $N_k=\text{SHA3}(N_{k-1}+k-1)$ without guesswork on $k$. You can't manipulate the sequence once $N_k$ and $k$ have been shared with others. If you could, that would break the collision resistance of the hash.

Without $k$ published you would have a narrow possibility of fraud: on the second day you can publish $N_{k-1}+j$ and pretend $k$ was $j$ less than it really is; you wont be caught until the next day, and can't be caught if $j=k-1$.

Note: you could manipulate the $N_i$ when choosing the secret, e.g. so that $N_{987}$ is odd; and of course you know all the $N_i$.


Can a attacker compute a hash from another hash of the same plaintext (both using different salt)?

Imagine two PBKDF2-SHA-512 hashes of the same password are generated. Each has individual salt. If an attacker had one hash and the salt of both hashes, would he be able to compute the missing hash or would he gain a significant advantage guessing it?

No. The idea of a hash is that it is impossible to reverse a hash. You can of course guess the hash then both outputs can be calculated, but having two different salts will not give any advantage to an attacker.

Note however that by performing PBKDF2 twice you are giving some advantage to an attacker, who only need to perform PBKDF2 once to verify correctness of a guess. Basically your advantage compared to the attacker is reduced by a single bit.

This is why you could also use PBKDF2 once and then create two values using a KBKDF such as HKDF(-expand) twice with two different labels. KBKDF's such as HKDF do not perform key strengthening so the work factor implied by PBKDF2 doesn't need to be performed twice on the server.


Apply the $\pi^{-1}$ to all the blocks. Then put them under each other so we get colums of length 4 in this case. Then read out left to right, up to down instead (zig-zag).


How to attack Oblivious Transfer from a malicious sender that can deviate from the protocol

I want to show that a malicious sender (Alice) can attack this protocol if it can deviate from it, namely, send a wrong RSA key pair, and learn the secret bit $b$.

You can, in fact, show this (or, rather, the OT would require a ZK proof by Alice that $\gcd(e, \phi(N)) = 1$)

However, I don't exactly understand how sending such an invalid input $e$ helps.

If $\gcd(e, \phi(N)) > 1$, then not all values $z$ have $e$th roots, that is, sometimes there won't be a value $y$ with $y^e = z$.  And, if you know the factorization, this is easy to test.
So, when Alice gets the value $v = (x_b + k^e) \bmod N$, she can compute $v - x_0$ and $v - x_1$.  The correct one will be an $e$th root; the wrong one will likely not be - if it is not, then she will then know $b$.
One issue that Alice will run into is that, in this case, she would not be able to unambiguously recover $k$; this would prevent her from being able to complete the protocol. However, the damage has already been done.


RSA: Derive modulus from known ciphertexts encoded with same keypairs

Here is the hint you requested:

We know that we have $m_1^e - c_1 = k_1n$ for some integer $k_1$
We know that we have $m_2^e - c_2 = k_2n$ for some integer $k_2$

So, given that we know the values $k_1n$ and $k_2n$, how can we recover the common $n$ value?  Hint: look at the $\gcd$ function...


Is there a variant of Merkle tree with no traceability from root to leaves?

Merkel trees already allow you to decide how much you reveal. To prove presence of one leaf, you reveal it and the commits along its copath.

If your documents contain enough entropy then you do not need salts. If the documents do not, then you may prepend each document with a salt I.e. $\text{hmac}(\text{secret} \| \text{index}, \text{message})$.

The intermediate nodes do not need salts.

To avoid leaking the number of documents you can fix the copaths length to $\lceil\log_b(N)\rceil$. This adds an additional $N - b^{\lceil\log_b(N)\rceil}$ zero-sized documents as additional noise. $b$ is the number of branches per depth (usually $2$). The padding should be uniformly shuffled with all documents, not ordered or appended to the end. The $\text{index}$ identifier is the position from root-to-leaf left-to-right after flattening the tree. I.e. $[0], [1, 2], [3, 4, 5, 6]$.


Since no-one else has mentioned this yet, I guess I should point out that it is possible to use public key signature schemes like (EC)DSA to generate software registration keys.  For example, Microsoft apparently uses this for their product keys.

Basically, you embed the public key in your program and keep the private key, which you'll use to sign whatever information you want to tie the activation code to; this could be just a fixed string, but it could also include things like the name of the user or information about the computer they're using, depending on what kind of registration system you want.

The problem, as you correctly suggest in your post, is choosing a signature length long enough to be reasonably secure while short enough for users to type in.  If you could have your users type in 64 random characters (out of a repertoire of 32 each), you'd be fine with a total signature length of 320 bits — but in practice, even 30 characters is a nuisance to type.  Of course, if you're doing the registration online, you could just give the user a block of text to copy and paste.

Anyway, if your software is free anyway and you don't care about security, much simpler schemes (like woliveirajr's suggestion) will do just as well.  But if that's the case, why make your users go through the nuisance of registration in the first place?


How can I control the output of a hash function to output to specific data according to similarity?

Well, if the question is 'how do we select inputs to a cryptographical hash function so that the outputs are within a specific range', well, you're pretty much limited to:

Rejection methods -- that is, you hash the input with some salt, and if the resulting hash value isn't in the range you want, you keep on trying different salt values until it is.  For example, if you want the MSBit of the hash to be zero, you keep on trying different salt values until you find a hash with has an MSBit of zero.
Postprocessing methods -- that is, you hash the input as usual, and then map it into the range you want.  For example,if you want the MSBit of the hash to be zero, you simply take the result of the crpytographical hash function, and set the MSBit to zero.

If you're looking for a more efficient method of selecting hash inputs to constrict the hash output, well, they're not known to exist for cryptographical hash functions.  In fact, if there was a large, easily computable subset of inputs that generated a biased hash output, that would imply a cryptographical weakness of the hash function.  For example, to find a collision in the hash function, one could just take inputs from the subset, and hash those; if there was a bias in the hash outputs, one would find a collision with probability $0.5$ with a number of hashes strictly less than $1.17741 \cdot 2^{N/2}$ attempts (where $N$ is the size of the hash function); this is a weakness (although a small one if the bias is small, or it takes a large amount of computation to find elements in the subset).