Is it safe to use many nonces for XChaCha20?

Yes. Indeed, a "nonce" is a number used once. If you ever reuse a (nonce, key) pair, security breaks catastrophically. For a large chunked file, you can simply use the chunk number as the nonce, as long as you re-key after each file and can keep track of the count.
Libsodium's secretstream API does this internally. If possible, use that, as it's far safer than building your own construction.


Problem with LLL reduction on truncated LCG schemes

The lattice basis $L$ generates every point that is a solution to the congruence $a^{i-1} x_1 - x_i \equiv 0 \pmod{m}$. By definition, the reduced basis $B = \mathsf{LLL}(L)$ also generates the same solutions; it just has shorter vectors.

Now suppose we have a set of outputs $\mathbf{y} = y_i$ of the generator, which correspond to the most significant bits of the LCG multiplied by $2^s$, and we want to find $\mathbf{z} = z_i$ such that $\mathbf{y} + \mathbf{z} = \mathbf{x}$, where $\mathbf{x} = x_i$ is the reconstructed state. The key insight here is
$$
\begin{align}
& L \cdot \mathbf{x} \equiv 0 \pmod{m} \\
& B \cdot \mathbf{x} \equiv 0 \pmod{m} \\
& B \cdot \mathbf{x} = m \cdot \mathbf{k} \quad \mbox{(for some unknown $\mathbf{k}$)}  \\
& B \cdot (\mathbf{y} + \mathbf{z}) = m \cdot \mathbf{k}  \\
& B \cdot \mathbf{z} = m \cdot \mathbf{k} - B \cdot \mathbf{y}
\end{align}
$$

Now, because the coefficients in the reduced basis $B$ are small, we know that all the elements of $\mathbf{k} = k_i$ are small, and we can further deduce $k_i = \lfloor (B \cdot \mathbf{y})_i / m \rceil$, or in other words, $m \cdot k_i$ is the closest multiple of $m$ in relation to each element of $B \cdot \mathbf{y}$. Once we know $k_i$, this is a simple matter of linear algebra. Here's an example with Sage:

p = previous_prime(2^32)
a = randint(2, p)
s = randint(0, p)
X = [ a^(i+1) * s % p for i in range(4) ]
Y = [ x - x % 2^16 for x in X ] # high 16 bits
Z = [ x % 2^16 for x in X ] # low 16 bits (secret)

L = matrix([
    [  p,  0,  0,  0 ],
    [a^1, -1,  0,  0 ],
    [a^2,  0, -1,  0 ],
    [a^3,  0,  0, -1 ]
])

B = L.LLL()

W1 = B * vector(Y)
W2 = vector([ round(RR(w) / p) * p - w for w in W1 ])

Z_ = list(B.solve_right(W2))
print Z_
print Z


You are right, the success probability of a $q$-query quantum adversary is $\Theta(\frac{k(q+1)^2}{n})$. You can find a proof of the upper and lower bound in this paper.

The upper bound uses similar tools as for the optimality of Grover. The tricky part is that the proof of optimality for Grover's algorithm is given for the worst-case but I guess you and people in crypto in general are mainly interested in the average case complexity. So you need a more advanced toolkit.

The lower bound is more or less applying Grover and analysing its success probability for the average case.


If you want to learn about your new field, I strongly recommend you to read only section 3 of Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full MORUS, maybe skipping the proofs but definitely not the examples during the first reading.

Try then to solve your problem for at least an hour, before reading my solution below. (Hint: Apply Algorithm 1 (no need to program it) to your function $f$, and then Lemma 4 to the result of Alg. 1.)

As a self-contained answer would be much too long, I assume that the reader understood section 3 of the paper mentioned above.

Following Algorithm 1, define $x'_0 := x_0+x_2$ then $x'_2 := x_2 + x_4$, and so on, and additionally (don't look at the $k'$ before you understood about the $x'$) $k'_0 := k_0, k'_{2i+1} = k_{2i+1}, k'_{2i+2} := k_{2i+2}+k_{2i}$ to clean up the linear term L  to get

$$f(x'_0, x_1, x'_2, x_2, \dots) = x'_0x_1 + x'_2x_3 + \dots + x'_{m-1}x_m + k'_0x_0 + k'_1x_1 + \dots + k'_nx_n,$$

in disjoint quadratic form, where $m=n$ if $n$ odd and $m=n-1$ if $n$ even.

Lemma 4 tells you now that kodlu is right in claiming that $f$ cannot be balanced if $n$ is odd, as all variables $x'_0, x_1, x'_2, \dots$ show up in some quadratic term (that are separated after the substitution).

Lemma 4 tells you also that for $n$ even, $k'_n = k_n+k_{n-2}$ being $1$ is equivalent to $f$ being balanced, as $x_n$ is the only variable not showing up in any quadratic term (that all are separated over the variables $x'_0, x_1, x'_2, \dots$).

For $n$ even adding $x_n$ to $f$ corresponds to replacing $k_n$ by $k_n+1$ making $k'_n=0$ and $f$ not balanced.

Adding then $x_0$ to $f$ corresponds to replacing $k'_i$ by $k'_i+1$ for all even indices $i$, in particular also for $i=n$ even, making $k'_n=1$ and $f$ balanced again.


What is the right notion of security to use for file encryption?

Yes. $\:$ NME-CPA is such a notion, and is equivalent to modifying the IND-CCA notion so that

$\;$ the adversary can submit more than one ciphertext simultaneously
$\;\;\;\;$ and
$\;$ the adversary can only submit ciphertext(s) one time
$\;\;\;\;$ and
$\;$ that time must be after receiving the challenge ciphertext
$\;\;\;\;$ and
$\;$ after submitting ciphertext(s), the adversary also can't submit any plaintexts

.


Yes, AEAD constructions always authenticate the nonce. If they didn't then the integrity and authentication of the resulting plaintext after decryption would not be ensured.

You can see the definition in RFC 5116: An Interface and Algorithms for Authenticated Encryption, section 2.1. Authenticated Encryption:

  The nonce is authenticated internally to the algorithm, and it is not
     necessary to include it in the AD input.  The nonce MAY be included
     in P or A if it is convenient to the application.

Not all AEAD ciphers may necessarily keep to the letter of this RFC (the inclusion of the authentication tag in the ciphertext is debatable if you ask me - I consider it a separate field). However, I haven't seen any AEAD cipher that doesn't authenticate the nonce by design.

You're writing that

  With a more "traditional" composition, like AES-CBC-then-HMAC, the nonce is obviously authenticated.

This is obviously not true. Yes, it is possible to design such a scheme and any competent cryptographer would not for get to authenticate the IV. There are even tries to standardize such a scheme, see e.g this scheme based on CBC with HMAC-SHA-1.

Less competent protocol designers are however free to shoot themselves in the foot when designing or implementing such a scheme. When using a well designed / reviewed / tested library and an AEAD scheme such mistakes are avoided.


A Deterministic Random Bit Generator (DRBG) would typically be used, when you have entropy input that is either

biased,
inefficiently generated, or
both of the above.

If you have a True Random Bit Generator that outputs unbiased bits efficiently, there is no apparent reason to use a DRBG in the first place. This is particularly true in case you require information theoretic security. Using a DRBG means you get pseudo random bits with computational security, typically expressed in the conventional way as 128-bits of security, 256-bits of security, etc.

This means that reseeding of DRBG, such as NIST SP 800-90A, should not be expected to be designed to address loss of entropy in the information theoretic sense, but only in a practical sense. It is done to reduce the risks (not eliminate the risks) associated with internal states being compromised through side channel attacks, etc.


What is the largest key size that could be carried by a shuffled deck of playing cards?

Any set of $N$ distinguishable objects can be permuted in $N!$ different ways, thus giving you the ability to represent $N!$ different keys, resulting in a representable keylength of $\log_2(N!)$ bits. For $52$ distinguishable playing cards, this would be $\approx 225$ bits.

However with the additional property, that each object can have two distinguishable states -- a card can be face up or face down in the deck -- we can encode one additional bit of Information per card, since for each permutation there are $2^N$ different configurations. For your $52$ playing cards with the two states "face up" and "face down" you can thus represent $52!\cdot 2^{52}$ many keys, or a key length of $277$ bits.


Partial decryption of large file in AES-GCM (or other modes)?

Sure, basically GCM is counter mode encryption with an authentication tag added. You can encrypt any part of the stream without issue if you know the key and the counter for that part. Obviously, you cannot check the integrity though, because the tag is the integrity of the entire file.

Basically, you only have to perform the top part of the scheme:


difference between the uniform and non-uniform probabilistic polynomial algorithms (ppt)

The non-uniformity needed for the proofs of security is in the distinguisher (in order to get advice as to which inputs the protocol breaks on in the reduction). However, if you are already assuming non-uniformity for the distinguisher, then you may as well assume it for the real adversary. But, if you assume it for the real adversary then you also need it for the simulator since the simulator needs to be as strong as the adversary in order to be able to run it.

The above is all true for the malicious case. However, in the semi-honest case, you still need non-uniformity for the distinguisher, but there is no adversary; the simulator just needs to generate the view of the semi-honest adversary in the protocol. For this, it suffices to use a uniform machine. Having said this, nothing would be lost by taking a non-uniform simulator; it’s just that we don’t need it to prove security of protocols (at least, I don't know of any protocol for semi-honest that requires a non-uniform reduction; if there is such a case, then they can just use non-uniform simulation, as I mentioned).


Is there a cryptographic function or system in which it becomes HARDER to break as time passes?

Any protocol with long-term security becomes harder to break after the protocol execution has finished.

In the Bounded-Storage Model, protocols become harder of break as [information about the

randomizer that's not stored by the adversary] is lost. $\:$ (This point is similar to minar's observation.)


salsa20 is invertible, useless in CTR mode?

Every paragraph ends with : "this operation is invertible", I suppose the whole salsa20 algorithm is.

The Salsa20 quarterround, and thus rowround, columnround and doubleround are invertible. However, the whole Salsa20 core is not because the initial state is added to the state after iterating the rounds (cf. page 6 in the spec).

  If I use salsa20 in bloc cipher CTR mode, this property does not seems mandatory to me, am I right?

If the whole cipher core was invertible, then a known plaintext attack would reveal the key. So not being invertible is a requirement, somewhere along the line.

  As such, any cryptographically-robust hash function (one-way only) could be used for CTR encryption?

This is correct. See, for example this question.

  Isn't it easier to design a robust hash than a robust cipher?

Maybe, but block ciphers are usually much faster than a hash function in CTR mode. Hash functions are optimized to consume data, not output it. Stream ciphers, OTOH, are occasionally even faster, like you can see if you compare Salsa20 and AES in software implementations.


Format Preserving Encryption - Generating coupon codes

That depends on what coupon codes are accepted rather than the details of the FPE. FPE is a pseudo-random permutation that depends on the key. If the attacker inserts any encrypted coupon code in the specified domain (in this case 20 digits) then it will with certainty result in a 20 digit coupon code after decryption.

So what chance is there that the coupon code is accepted? Well, it is exactly the same as a normal coupon code. If the coupon allows any 20 digit code then the likelihood of it being accepted is of course precisely one. Commonly though a coupon code also contains a method of verification. Then it depends on the verification method what chance there is of a random coupon code to be accepted.

Say there is one decimal check digit and a calculation that results in a uniform distribution given random input of the other digits. In that case the chances of generating a probability of generating a valid coupon code is of course one in ten.


This call for a few different answers.

First concerning any rainbow table or similar approach, nothing prevents you from defining $HH(x)=H(H(x))$ and then to apply the desired method to the composed function $HH$. Even if $HH$ has slightly different properties from a usual hash function (see below), this will still work fine. So you gain no additional protection here.
If you are concerned by collisions, you should be aware that the probability of collision is slightly higher with a repeated hash, indeed, a collision $HH(x)=HH(y)$ with $x\neq y$ may arise in two different ways (either $H(x)=H(y)$ or $H(x)\neq H(y)$ and $H(H(x))=H(H(y))$. This almost doubles the probability of collision for a given pair $\approx 2^{1-h}$ instead of $2^{-h}$.
If you want to consider a more theoretical approach, you should look at To Hash or Not to Hash Again? (In)differentiability Results for H^2 and HMAC (http://eprint.iacr.org/2013/382), which shows that $HH$ is not indifferentiable from a random oracle.


algebraic attacks for mixed operations (mod 2 and mod 256)

There is of course but because of carry bits there will be data-dependent "nonlinear" terms. If I do it for 2 bits you can get the idea. It gets unwieldy but you can easily write code to do it for longer bitlengths. The list below is an XOR table expressed as integers:

$$
\begin{array}{c|ccc}
\oplus & 0 & 1 & 2 & 3 \\
\hline
0 & 0 & 1 & 2 & 3 \\
1 & 1 & \color{red}0 & 3 & \color{red}2 \\
2 & 2 & 3 & 0 & 1 \\
3 & 3 & \color{red}2 & 1 & \color{red}0 \\
\end{array}
$$

while the table below is addition mod 4:
$$
\begin{array}{c|ccc}
+ & 0 & 1 & 2 & 3 \\
\hline
0 & 0 & 1 & 2 & 3 \\
1 & 1 & \color{green}2 & 3 & \color{green}0 \\
2 & 2 & 3 & 0 & 1 \\
3 & 3 & \color{green}0 & 1 & \color{green}2 \\
\end{array}
$$

Note that there are exactly 4 positions (in general for $n$ bits there will be $2^{n-1}+2^{n-2}+\cdots$ such positions) where the two operations differ, so relatively worse as $n$ increases) where the two differ. Can we express these positions in terms of integer properties?

The answer is: Let $x,y \in \mathbb{Z}_4,$ considered as an additive group. Then  the XOR operation on $x,y$ can be defined as

$$
x \oplus y = \begin{cases}
x + y + 2 ~(\text{mod } 4) &
\text{if }   x \equiv 1 ~(\text{mod } 2)
\text{ and } y \equiv 1 ~(\text{mod } 2) \\
x + y ~(\text{mod } 4) & \text{otherwise}.
\end{cases}
$$

The full answer has to do with the highest powers of $2$ dividing the two numbers within $\mathbb{Z}_{2^n},$ i.e., the subring and ideal structure.


How to build a difference distribution table?

Those tables are fairly easy to build conceptually but require quite some work to actually carry out.

Note that: The columns show the XOR for the in-going pairs and the rows show the number of pairs that had the specified XOR afterwards.

This pseudo-code generates the table:

InLength; // input length of the S-Box in bits
OutLengh; // output length of the S-Box  in bits
Table[In][Out]; // the table, In is the XOR of the in-going pair, Out is the resulting XOR, the table returns the number of occurences

// Initialize the table:
for(in = 0;in<2^InLength;in++)
{
  for(out = 0;out<2^OutLength;out++)
  {
    Table[in][out] = 0;
  }
}

// this makes us go through all the possible value of p1
for(p1 = 0;p1<2^InLength;p1++)
{
  // this makes us go through all the possible value of p2
  for(p2 = 0;p2<2^InLength;p2++)
  {
    XOR_IN = p1 XOR p2;
    XOR_OUT = SBOX(p1) XOR SBOX(p2);
    Table[XOR_IN][XOR_OUT]++;
  }
}

What this does is basically build each possible input pair of the S-Box, calculate its XOR, runs both through the S-Box and calculates the XOR of the result and increments the value at this position.

This table would be too complex to show here for AES as it would be a 256x256 table. For the actual AES S-Box refer to the Wikipedia article.


DSA: why using mod p mod q and not just mod p

Consider the function $f\colon \mathbb Z \to \mathbb Z$ given by $f(x) = g^x \bmod p$ where $g$ has order $q$ modulo $p$.  If $x \equiv y \pmod q$, then necessarily $f(x) = f(y)$, since by hypothesis $x = y + \ell q$ for some $\ell$, so

\begin{equation}
  g^x \equiv g^{y + \ell q} \equiv g^y g^{\ell q}
  \equiv g^y (g^q)^\ell \equiv g^y 1^\ell \equiv g^y
  \pmod p.
\end{equation}

Note that $f$ is merely a function from integers to integers, but this proposition shows that there is additional periodic structure to its input: $f(x) = f(x + \ell q)$ for any $\ell$.  So if we consider the coset $\overline x = x + q\mathbb Z = \{\dots, x - 2q, x - q, x, x + q, x + 2q, x + 3q, \dots\}$ of $q \mathbb Z$, $f$ is the same on every element of $\overline x$.  Thus we can think of $f$ as being defined on the quotient $\mathbb Z/q\mathbb Z$, the set of all cosets of $q\mathbb Z$, rather than on $\mathbb Z$.  More jargomatically: there is a unique natural $\overline f\colon \mathbb Z/q\mathbb Z \to \mathbb Z$ defined in the quotient $\mathbb Z/q\mathbb Z$ so that $f = \overline f \circ \phi_q$, where $\phi_q\colon \mathbb Z \to \mathbb Z/q\mathbb Z$ is the natural projection $\phi_q(x) = x + q\mathbb Z = \overline x$ onto $\mathbb Z/q\mathbb Z$.

In other words, even if we treat $x \mapsto g^x \bmod p$ as a function on integers, we can always break it down into two steps, the first of which is reduction modulo $q$.  So, whether you like it or not, if you are computing $g^x$ for integers outside $0 \leq x < q$, the function can still always be defined in terms of doing $x \bmod q$ first.

What's much weirder is not reduction modulo $q$—which as above is necessary if you're going to use the result as an exponent—but the chain of reduction modulo $p$ and then modulo $q$.  This was a point of contention in the provable security literature on DSA and ECDSA.  You could imagine computing $g^k \bmod q$ directly, but it wouldn't make a functioning signature scheme.  What you really want is a uniform random map from $\mathbb Z/p\mathbb Z$ to $\mathbb Z/q\mathbb Z$ which has no properties that an adversary could exploit.

It just happens that $h \mapsto (h \bmod p) \bmod q$ sorta kinda seems to work but as far as I know nobody has a good handle on why even in recent analyses like Fersch–Kiltz–Poettering 2016 (paywall-free), which models it roughly as a random oracle while tidying up nearly everything else about the long and sordid history of attempts to prove DSA and ECDSA security.


In interactive proofs, do we assume that the prover can always solve the problem?

No, but if the problem isn't known to be in promiseMA then

we do "assume that the prover can always solve the problem".

https://cstheory.stackexchange.com/questions/696/mip-with-efficient-provers

Graph isomorphism is trivially in NP, so for graph isomorphism, we just

"assume that the prover" has an isomorphism between the graphs.

Graph non-isomorphism is not even known to be in MA, so for graph non-isomorphism,

we do "assume that the prover can always solve the problem".


Words in “index of coincidence” in relation to the Vigenère cipher

Here $f_i$ is simply the number of times the character $i$ appears in the ciphertext of length $N$ and where $Z$ is the alphabet size.

If you had ciphertext ADCXU ZMDYZ DXZUM and which was derived from English plaintext then $N=15$  and $f_A=1,f_B=0,f_C=1, f_D=3,\ldots, f_Z=2.$


How to securely compute AES where the key is splitted across different servers?

If you only use secret sharing, then upon reconstruction the key could be stolen. Therefore, secure multiparty computation can be used. There are many different methods, depending on your setting. If you are interested in two-party computation with semi-honest adversaries then simple Yao works (e.g., http://eprint.iacr.org/2015/751.pdf); if you are interested in two-party computation with malicious adversaries and a single execution then http://eprint.iacr.org/2016/762.pdf is a good option; if you are interested in two-party computation with malicious adversaries and many executions then http://eprint.iacr.org/2015/987.pdf or http://eprint.iacr.org/2016/632.pdf; if you are interested in 3 party secure computation for malicious adversaries and with at most one party corrupted then http://eprint.iacr.org/2015/931.pdf is easy to implement but you can get much faster with http://eprint.iacr.org/2016/944.pdf; if you are interested in 3 party secure computation for semi-honest adversaries and with at most one corrupted then http://eprint.iacr.org/2016/768.pdf is by far the fastest; if you are interested in multiparty (more than 3 parties) and semi-honest then http://eprint.iacr.org/2011/257.pdf or http://eprint.iacr.org/2016/1066.pdf; if you are interested in multiparty (more than 3 parties) and malicious then http://eprint.iacr.org/2016/505.pdf. All of these are the state-of-the-art for their settings (but there are many other options) and the state-of-the-art is likely to change very quickly.


applying HKDF at both the client and the server

HKDF is deterministic, that is, given the same input; IKM (Input Keying Material), salt, and contextual info (these last two are optional, but recommended), and provided that the same underlying hash function is used (SHA256, for example), the output will always be the same.


Use cases for “online” authenticated encryption?

The usefulness of online AE (locally):
Assume you wrote a program that encrypt arbitrary files. Now further assume the user wants to view a movie, encrypted with this tool. The tool can now use the online-property to stream the movie in real-time as it uses online-encryption.

The usefulness of online AE (programatically):
Assume you want to process sensitive data. If your cipher supports online AE it can wipe the data after having written / read it an thus presents less attack surface.

The usefulness of online AE (network related):
Assume you stream a movie. You can now use the online AE feature to minimize the RAM needed (and thus give more RAM to the video decoder) and you can present the user with better loading times.

All in all:
Online-AE reduces memory usage and latency for applictions.


Let us consider this beautiful elliptic curve:

She is defined in a plane ($\mathbb{R}^2$).
1. From a plane to a projective space
For an affine plane $\mathbb{A}^2 = \{(x,y): x,y \in \mathbb{K}\}$, we can define its projective space as follow:
$$ \mathbb{P}^2 = \{(x:y:z): x,y,z \in \mathbb{K}\}\backslash(0:0:0) \sim $$
Where $\sim$ is the equivalence relation such that:
$$\sim : (a:b:c) \sim (a':b':c') \iff \exists \lambda. (a,b,c) = (\lambda a', \lambda b', \lambda c')$$

In other words, all the points on the same line going though the origin $(0:0:0)$ are equivalent with respect to $\sim$.

It may seem complicated so let us use some figures.
Here we have a projective space.

Each points on the same green line (passing through the origin) are equivalent due to the $\sim$ relation. Each points on the same orange line (passing through the origin) are equivalent due to the $\sim$ relation.
We can divide this space into 2 sets. The points with $z=0$ (in orange) and the points with $z \neq 0$ (in green).
Let us have a look at the green set. If we consider the lines (or equivalent points), one can remark that they all intersect the plane $\{z=1\}$ (See diagram below). Thus all the points in the green area have an equivalent into the  plane $\{z=1\}$.

The only points that does not satisfy this property are those which equivalence line is parallel to the plane $\{z=1\}$. In other words, the points where $z=0$.
Let us have a look at those points. Using the same principle as with the green space, one can see that each line going through the origin cut the line $\{z=0, y=1\}$. Therefore with one exception, all the points in the orange plane have an equivalent on the line $\{z=0, y=1\}$.

Note that the exception are the points parallel to the line $\{z=0, y=1\}$, in other word, the $x$ axis. Because they form a line, they are all equivalent with respect to $\sim$ therefore, they are all equivalent to $(1:0:0)$.

In the end, all the points in the projective space $\mathbb{P}^2$ have an equivalent in the plane $\{z = 1\}$ or on the line $\{y = 1, z = 0\}$ or to $(1:0:0)$.

2. Going back to the curve
In the projective space, the equation of the elliptic curve is:
$$y^2\ z = x^3 + a\ x\ z^2 + b\ z^3$$
(The degree of each term of the polynomial must be 3: $deg(y^2\ z) = deg(y^2) + deg(z) = 3$ etc.)
We can now represent the points of the elliptic curve in this space. Due to the equivalence relation of this projective space, we can just display those on the different subdivisions (plane $\{z = 1\}$, line $\{y = 1, z = 0\}$ and $(1:0:0)$).
for $(1:0:0)$ (point)
$(1:0:0)$ is not part of the curve as $y^2\ z = 0$ and $x^3 + a\ x\ z^2 + b\ z^3 = 1$
for $z = 1$ (plane)
This is the simplest form, by replacing $z$ by its value in the equation we get: $y^2 = x^3 + a\ x+b$. Therefore the representation of the elliptic curve will be the same as the one above but projected on the plane $\{z = 1\}$.
for $z = 0$
$$z = 0 \implies y^2\ z = 0 \implies x^3 + a\ x\ z^2 + b = x^3 = 0 \implies x = 0$$
The points that satisfy this equations are the one of the form $(0:\lambda:0)$.
Or $(0:\lambda:0) \sim (0:1:0)$ This is the missing point that can not be represented using the plane representation: the point at infinity $P_\infty$.
Thus, we can finally represent our elliptic curve in its projective space as bellow.

Remarks
As a quick reminder, here is what a curve really looks like in a finite field: not as smooth as one would expect...

$$y^2 = x^3 - 2 x + 1 \text{ over } \mathbb{Z}_{89}$$


Input existence proof for known partial input and hash

It depends on what exactly do you ask for:

You know such $r$ that $h$=$H(r||k)$ and want to provide someone proof that you know it or
You have only $h$, $H$, $n$ and $k$ and you want to check if $r$ exists

First case should be possible with something like zkSNARKs.

In second case there's no way to do it in polynomial time for any $H$ that is second-preimage attack resistant. Proof:

Let $n_a$ means bit length of $a$. We have some secret input $M$ and $h=H(M)$. Let's assume there exists algorithm $A(H, h, n, k)$, polynomial in terms of security parameter $n$, that :

  returns $1$ if there is $r$ such that $h=H(r||k)$ and $n_r=n-n_k$

  returns $0$ otherwise.

We can use $A$ to efficiently create collision with $M$ with the same length. In pseudocode:

  $M' = \{\}$

  for each $1\le i \le n$ do:
  $M'=A(h, n_M, 1||M')||M'$

After that you have $M'$ that satisfies $H(M')=h=H(M)$ and $n_{M'}=n_M$. So $H$ wouldn't be second-preimage attack resistant.

You can of course iterate through every value of $r$ and check if $h=H(r||k)$ but that takes $2^{n_r}$ steps (in case there's no such $r$).


What security do Cryptographic Sponges offer against generic quantum attacks?

Unless Keccak has structural weaknesses that I am not aware of, the answer is surprisingly neither 128 nor 256!
Gilles Brassard, Peter Høyer, and Alain Tapp describe a sort of quantum birthday attack in their paper "Quantum Cryptanalysis of Hash and Claw-Free Functions" that effectively works by creating a table of size $\sqrt[3]{2^b}$ (versus the $\sqrt{2^b}$ for the classic birthday attack) and then utilizes Grover's algorithm to find a collision.
While the classic birthday attack thus requires ${\mathcal O}\left(\sqrt{2^b}\right)$ time and memory, the quantum birthday attack only requires ${\mathcal O}\left(\sqrt[3]{2^b}\right)$ time and memory.
This means that to provide a $b$ bit security level against quantum adversaries, a hash function must provide at least a $3b$ bit output.
In your case of 512-bit Keccak, your security level would be $170\frac{2}{3}$.


Is there an efficient solution? Finding the number of matching items in lists with a threshold

There has been work on finding the size of the set intersection. I haven't read this paper, but this would be a good place to start your research: Fast and Private Computation of Cardinality of Set Intersection and Union.


Prove that the affine cipher over Z26 has perfect secrecy if every key is used with equal probability of 1/312

This would usually I think be more suited as a comment, but you were looking for guidance instead of a complete answer as it were, and I don't have enough reputation to comment.

I'd highly recommend Claude Shannon's introduction (the literal introduction, he developed the concept) to the question you pose. Here’s the paper (PDF) and the section is Part 10 on Pg. 679. The more broad statement of your question is Theorem 6, but he does (as he always does) an incredibly good job of approaching both the motivation for the theorem as well as the proof, the latter of which he gives in relatively informal way.


We can use the notation of the source document, except I will say we are trying to compute $ab = c$ (for $a,b,c\in\mathbb{F}_p$), so I can use $x$ as a variable when discussing polynomials.

Let $a_1,\dots, a_n$ and $b_1,\dots, b_n$ be $t$-out-of-$n$ secret sharings of $a, b$.
Recall this means that they're computed by taking random $t$-degree polynomials:
$$A(x) = \sum_{i = 0}^t \alpha_i x^i,\quad B(x) = \sum_{i = 0}^t\beta_i x^i$$
Where $A(0) = a, B(0) = b$ (so random subject to this condition).
The shares are then created by evaluating the polynomials on the points $\{1,2,\dots,n\}$.
In particular:
$$\forall i \in\{1,\dots,n\} : a_i = A(i),\quad b_i = B(i)$$
Now we want to compute the product.
The polynomial $C(x) = A(x)B(x)$ has the right constant term (as $C(0) = A(0)B(0) = ab$), but is too high of degree (as you mention).
Moreover the "shares" of $C(i)$ can be computed locally, as $C(i) = A(i)B(i) = a_ib_i$.

But $C(x)$ is degree $2t$ (as you mention). We want to find some other polynomial $\mathcal{C}(x)$ such that:

$\mathcal{C}(0) = C(0) = ab$
$\mathcal{C}(x)$ is degree $t$
Computing $\mathcal{C}(i)$ isn't "too expensive" (in communication) if you already know $A(i)$ and $B(i)$

What will we do then? The idea is to utilize that there are two different ways of representing degree $t$ polynomials:

Through their $t+1$ coefficients (this is the "obvious") way
Through the evaulation of them on (at least) $t+1$ distinct points

Either of these is enough information to uniquely reconstruct the polynomial.
The surprising thing is that you can convert from one to the other using a linear operation.

To see how we might establish this, recall that for an $n\times n$ matrix $D$ and vector $\vec{v} = (v_1,\dots, v_n)$, we have that:
$$(D\vec{v})_i = \sum_{k = 0}^{n-1}D_{i, k} v_k
$$

Note that this is similar to the expression:
$$A(x) = \sum_{i = 0}^t \alpha_i x^i$$
If we fix evaluation points $\{1,\dots, n\}$, then we have in fact that:
$$A(i) = \sum_{k = 0}^t \alpha_k i^k$$
This suggests setting $D_{i, k} = i^k$ and $v_k = \alpha_k$.
This is precisely what we'll do, by defining the Vandermonde matrix (with respect to the aforementioned evaluation points):
$$V = \begin{pmatrix}
1^0 & 1^1 & \dots & 1^{n-1}\\
2^0 & 2^1 & \dots & 2^{n-1} \\
\vdots && \ddots & \vdots\\
n^0 & n^1 & \dots & n^{n-1}
\end{pmatrix}$$
Note that:
$$V\begin{pmatrix}\alpha_0\\\vdots\\\alpha_{n-1}\end{pmatrix}
=\begin{pmatrix}
\sum_{k = 0}^{n-1} \alpha_i 1^i\\
\sum_{k = 0}^{n-1} \alpha_i 2^i\\
\vdots\\
\sum_{k = 0}^{n-1} \alpha_i n^i\\
\end{pmatrix} = \begin{pmatrix}A(1)\\
A(2)\\
\vdots\\
A(n)
\end{pmatrix} = \begin{pmatrix}a_1\\
a_2\\
\vdots\\
a_n
\end{pmatrix}
$$
So the Vandermonde Matrix precisely maps the "coefficient representation" of a polynomial to its "evaluation representation".
This ends up being extremely closely related to the Fourier transform. The Discrete Fourier Transform can be written as a Vandermonde Matrix, and the Fast Fourier Transform can be explained that it's Vandermonde Matrix is Toeplitz (and in fact circulant), so admits especially efficient representations and matrix/vector multiplications, but this is an ahistorical aside.

So, we have an (invertible) matrix that maps an $n$-dimensional "coefficient vector" representation of a polynomial to an $n$-dimensional "evaluation vector" representation of a polynomial.
For the moment, don't worry about how all of the people move around all the shares --- just make sure you understand how to do the computation.

We start with the "evaluation vector" representation $C(i) = A(i)B(i)$ for $i\in\{1,\dots,n\}$, which we can write as $\vec c = (c_1,\dots, c_n)$.
We convert this to the "coefficient vector" representation via $V^{-1}\vec{c}$.
This gives the coefficients of the polynomial $C(x) = A(x)B(x)$ as a vector.
While there are $n$ coefficients, as discussed before this polynomial (uniquely determined from $\vec{c}$) is of degree $2t$, so the higher-order coefficients are 0.

We can convert this to a degree $t$ polynomial via truncation.
Let:
$$P = \begin{pmatrix} I_{t+1} & 0\\
0 & 0\end{pmatrix}$$
Be an $n\times n$ block matrix, where $I_{t+1}$ is the $(t+1)\times (t+1)$ identity matrix.
Then $PV^{-1}\vec{c}$ will "drop" higher order coefficients, leaving a degree $t$ polynomial.
Importantly, it doesn't touch the constant term (so $\mathcal{C}(0) = C(0) = ab$ is preserved).

All that's left is to convert back to shares, so to convert from the "coefficient representation" to the "evaluation representation", again by using $V$.
Thus $VPV^{-1}\vec{c}$ will output the shares (of a degree $t$ polynomial) that you want.
Moreover, $VPV^{-1}$ can be precomputed by all participants in the protocol (it's just some $n\times n$ matrix. I could probably even write it out here, but won't).

This reduces the problem of multiplying shares to the problem of "computing a linear equation" of shares, which your source also discusses (at this link).
As this is getting long I'll leave the answer here, but if you don't understand the linear case I encourage you to ask a new question about it.


Security Level Estimate when Cascading/Compositing Ciphers?

First question

It depends upon the scheme.  It also depends upon what kind of composition you are talking about.  Triple-DES uses multiple encryption.  That's one kind of composition.  The approaches you talk about in your third and fourth questions are a different sort of composition.  They will have different security properties.

Second question

Yes.  If the operation forms a group, then using multiple encryption does not add security.

Third question

This provides only 128-129 bits of security, but not for the reasons you expected.  The reason is Diffie-Hellman with a 3072 bit modulus provides only about 128 bits of security; one can break Diffie-Hellman with a 3072 bit modulus using something like $2^{128}$ work (very roughly).  So, one can break two Diffie-Hellman exchanges using $2^{129}$ work (very roughly).  In other words, this does not add security.

This is not a practical weakness in practice, because in practice 128 bits of security is more than enough; no one is going to be able to perform a computation that requires $2^{128}$ work (not in my lifetime).  That said, this is a certificational weakness in the protocol, and no one would consider this to be good protocol design; it is rather crummy protocol design.

Fourth question

Same answer.

Final note

This is kind of silly.  Why don't you tell us the real problem you really have?  It sounds like your question is heading in the direction of crummy protocol designs.  Maybe if you tell us the real problem, we can help you find a better solution to the problem.


Why is TLS susceptible to protocol downgrade attacks?

Short answer: Because the browser developers have long thought interoperability to be more important than security and standard compliance.

Slightly longer answer: Some SSL/TLS server implementations do not negotiate the protocol version correctly, but terminate the connection with a fatal alert if the client attempts to negotiate a protocol version that the server doesn't support. This might happen at either of three steps in the handshake protocol:

When the server parses the client hello (which should contain the highest protocol version supported by the client). A correctly implemented server should store the client version value, even if it is not supported by the server.
When parsing a client key exchange message containing a RSA encrypted pre master secret (which should contain the highest protocol version supported by the client as the first two octets). This version field should be compared to the client version value above, and not to the negotiated version.
When verifying the client finished message (which should be a hash of all handshake messages, including the client hello which contains the highest protocol version supported by the client).

Now, if the server for some reason doesn't process these steps in accordance with the TLS 1.0, 1.1 or 1.2 standards, but one way or another e.g. requires the highest protocol version supported by the client to have a specific value, or to be no greater than the highest protocol version supported by the server, the client has two choices: Either fail the connection with an error message that is displayed to the user, or attempt to connect again with the highest protocol version disabled.

The exploit is possible if the client uses the second alternative (which e.g. Chrome does, but not IE 10). Even if the authentic server actually supports TLS 1.1 or TLS 1.2 and the authentic server actually does handle the client version value correctly, the MITM might exploit that the client doesn't know which server handles the client correctly or not, and inject alerts in both directions to get the client to reconnect using a lower version.

Edit: For completeness, I should add that I concur with @Thomas in his answer that this should largely be a non-issue, simply because:

Trivially, even under a MITM attack that exploits this behavior, neither the client nor the server will be able to negotiate a protocol version they don't enable, and
Neither the client nor the server should enable protocol versions that don't provide adequate security.

The underlying problem is not really that some clients negotiate the protocol version in a way that is not strictly supported by the standard, in order to be able to connect to servers that might or might not negotiate the protocol version in a way not strictly supported by the standard.

Rather, the problem might occur in situations where Carol might connect to multiple servers, but TLS 1.2 is only required for the connection to Sue, for all other servers SSL 3.0 is sufficient. Conversely, Sue might accept connections from multiple clients, but it is only the connection from Carol that requires TLS 1.2. Ideally, Carol and Sue should be able to rely on the protocol negotiation to ensure that TLS 1.2 automatically gets negotiated (and in such case they might, or might not, be vulnerable to the exploit), but correct implementations should really check that the TLS connection meets the minimum security requirements after it has been negotiated.


It might mean that any multi-stage cryptographic protocols – which require parties to store temporary data – could be weakened by exposure/tampering of this data. To ensure that does not happen, one needs to protect these intermediate chunks of data and (preferrably) the encryption process itself so that we can trust that, if the protocol finished successfully, it's results are to be trusted.

One of the ways to protect it, is to offload all computations to HSM – which is compartmented from your regular process memory and thus is less likely to be tampered when your server gets compromised.


Did non-military cryptography appear in the 50's and 60's only due to NSA leaks?

I won't answer your question up to every detail, as I would have to write a book to answer the pretty broad question to full length. But I'll give you some hints as it would be wrong to let you think that non-military cryptography has appeared in 50's and 60's only thanks to leaks from the NSA!

Before the 30's…

One of the earliest descriptions of encryption by substitution appears in the Kama-sutra, a text written in the 4th century AD by the Brahmin scholar Vatsyayana, but based on manuscripts dating back to the 4th century BC. The Kama-sutra recommends that women should study 64 arts, including "mlecchita-vikalpa" — the art of secret writing*, advocated in order to help women conceal the details of their liaisons.

All in all, "non-military cryptography" has been known to civilians for thousands of years!

Where "Modern" crypto came from…

As for "modern-day" encryption, I'll only add that in the 30's and 40's, things like the Enigma cryptographic machine series were available to the general public, but they were too expensive for the average working man. Even after WW2, most military cryptography still was not all too different from the substitution ciphers known from the past, which were - theoretically - also available to every civilian. As an example, you can look at the work of Claude Shannon, who worked for Bell Labs and not the military.

Shannon worked  at Bell Labs for several years. During his time there, he produced an article entitled “A mathematical theory of cryptography”. This article was written in 1945 and eventually was published in the Bell System Technical Journal in 1949. This is regarded to be the start of modern crypto… which is why Claude E. Shannon is considered by many to be the father of mathematical cryptography.

The (r)evolution of civilian modern crypto…

The cryptographic techniques and algorithms evolved in the 70's as computational power became available… and even "working class" civilians could afford computers. What leaked in those decades was nothing more than a hand full of different military cryptographic algorithms; but it's not as if there weren't any civilian cryptographic algorithms available at that time. As an example, you can look at the DES cipher you mention. DES was created by a research group at IBM, not the military.

Side-Note

Re-reading your question, I guess you don't know (or forgot) that it was not until the 1970s, when the US government started treating cryptographic algorithms and software as munitions and interfering with university research in cryptography, that cryptography was actually pretty "non-military"; especially from a research and development point of view. My answer to "Why are cryptography algorithms not exported to certain countries?" dives a bit more into this.

But generally it's a known fact that there has always been ample civil research and development of cryptographic algorithms and techniques and most military cryptography is based on and/or derived from such civilian research and development. An example of a modern crypto invention in the civilian area actually resulted in Bernstein v. US Department of Justice (which made it famous in the first place). Bernstein's "Snuffle" was not and never has been created, influenced, manipulated, or leaked by the NSA or the US government… nevertheless, if got hit hard by US legislation. So yes, there was influence by governments and their military… but they were not the ones who gave birth to modern civilian crypto. Shannon did that in '49 with his publication, and - just like thousands of years before - it's mostly civilians (especially academics and the likes) that invented and still invent modern crypto algorithms.

If you need more details, you should probably check Wikipedia's "History of cryptography" with a section called "Modern Cryptography". If that's not enough, maybe it's time to buy a book about crypto history. Wikipedia has a nice listing or related books at "Books on cryptography ~ History of cryptography".

Nota Bene

Last but not least, I would like to add that it should be clear that the NSA (since you explicitly mentioned them in the question) had no chance to influence crypto before November 4, 1952… as they were founded on that date.


Why is calculating the discrete logarithm harder than calculating the public key?

There are actually much more efficient algorithms to calculate the public key, such as the double-and-add method which calculates the public key in at most $2 \times \log_2(n)$ steps. For example, if $n = 11$, instead of calculating $P, 2P, 3P, ...$ up to $11P$, we can repeatedly double the current point or add $P$ to get to $11P$:

$$2P = P + P$$
$$4P = 2P + 2P$$
$$5P = 4P + P$$
$$10P = 5P + 5P$$
$$11P = 10P + P$$

This method has a running time of $O(\log(n))$, while a brute force attack has a running time of $O(n)$. For a $256$ bit key, the double-and-add method takes at most $512$ point additions, while a brute force search would take up to $2^{256}$ point additions.


What size should the HMAC key be with SHA-256?

The only rule for the key is that it should at least contain 256 bits of randomness. If the key is smaller you may not get the full security of HMAC-SHA-256. The full security of HMAC is basically identical to the output size. Unless you are trying to protect yourself against quantum computers you should be able to get away with a key that contains 128 bits of entropy though.
Here's the text from the HMAC standard captured in RFC 2104:

The authentication key K can be of any length up to B, the
block length of the hash function.  Applications that use keys longer
than B bytes will first hash the key using H and then use the
resultant L byte string as the actual key to HMAC. In any case the
minimal recommended length for K is L bytes (as the hash output
length).

So preferably the entropy of the 256 bit key should be condensed into 32 bytes. What you are talking about is probably the hexadecimal representation of those 32 bytes. If the key is too large it may affect performance and efficiency of the HMAC function. Many libraries only allow binary to be inserted using octets bytes anyway, so in that case it makes sense to hex decode the key before you use it.

HMAC uses a hash internally, which is defined for any bit string. This hash is used both for the key as for the value. So in principle you can feed it anything you want up to the maximum hash size (which you will never reach).
Definition from Wikipedia:
$ {\begin{aligned}\operatorname {HMAC} (K,m)&=\operatorname {H} {\Bigl (}{\bigl (}K'\oplus opad{\bigr )}\parallel \operatorname {H} {\bigl (}\left(K'\oplus ipad\right)\parallel m{\bigr )}{\Bigr )}\\K'&={\begin{cases}\operatorname {H} \left(K\right)&K{\text{ is larger than block size}}\\K&{\text{otherwise}}\end{cases}}\end{aligned}} $
Note the repetition of the key with regards to efficiency.


It would be hard to find a category of mathematics not related in some way to cryptography, here is a list of applied mathematics by subject area. Even very abstract mathematics could be future cryptographic tools waiting to happen:

"A large part of mathematics which becomes useful developed with absolutely no desire to be useful, and in a situation where nobody could possibly know in what area it would become useful; and there were no general indications that it ever would be so. "


Which answer is true regarding birthday attack on digital signatures?

A birthday attacks generates a pair of colliding messages $m, m'$. Because of the way the collision is generated, you can't predict either $m$ or $m'$. If $m$ is fixed, then you need to perform a second-preimage attack instead.

The only person in this scenario who can change $m$ is $S$. $R$ and the third party only receive a fixed message $m$, and have to generate a second preimage $m'$. This is not possible using a birthday attack.

Thus, the correct answer is B. (I) only.


How does IBM's 53-bit quantum computer compare to classical ones for cryptanalytic tasks?

How does it compare to classical computers, performance-wise, for cryptanalytic tasks?

Not at all - IBM's quantum computer cannot perform any nontrivial cryptanalytic task.

For one, 53 physical qubits far too few to do anything interesting; for example, implementing SHA-256 would take thousands of logical qubits.

For another, the qubits are not even close to be reliable enough.  The IBM quantum computer cannot do any quantum error correction - this means that, as it performs operations on the qubits, the errors pile up.  Any interesting cryptanalytic task requires us to perform millions (or more) of quantum operations; even a slight amount of error accumulation would overwhelm any result.


Galois Field ($2^{16}$) for encryption in place of $GF(2^8)$ in AES

The result would not be AES, but Rijndael  a generalization of Rijndael. The Rijndael originally was proposed with 1 block size (128 bits) and 5 key sizes (from 128 to 256 is jumps of 32 bits). In the standardization to become AES, only 3 were selected (jumps of 64 bits).

What makes block size to be 128? Each of the internal operations does its contribution. The wordsize is 8 bits (That's why the Galois Field has this size), and there are 4 columns and 4 rows. That makes $4*4*8 = 128$. The key sizes difference comes from the number of columns. Each extra column, as it has 4 rows, adds 32 bits. The AES adds 2 columns for each increment.

It is possible to play with this parameters, but you'll have to study individually to each of the Rijndael's operations what this change mean. Imho, the Pseudo Random generator (PRG) of the key expansion, I think will still be, at least, as valid as it is. The subBytes operation would experiment a size explosion that may affect the performance. Perhaps shiftRows and mixColumns would be the less affected. And don't forget how many rounds would be a good number.

As a summary, would this improve the algorithm? It can, if it comes with the appropriate adjustment of the other parameters. But then, if you implement it, you'll be away of the standard.


What does (block cipher) decryption parallelizable mean?

plaintext block can be recovered from two adjacent ciphertext block

You also need the key. For example, for CBC mode, to decrypt block $i$, you need ciphertext block $i$, ciphertext block $i-1$, and the key. You do not have to have made any calls to the cipher on any previous or future blocks in order to decrypt block $i$.

Contrast this with OFB which is not parallelizable. In order to decrypt block $i$, you need to have run the cipher on block $i-1$ first.

  if an attacker has access to your ciphertext, then couldn't the attacker just decrypt it easily by using adjacent ciphertext blocks

No, because the attacker does not have the key.

  I've know about C threading, is this related to it?

Threading is one way to parallelize. In theory, with CBC or any other parallelizable mode, you could decrypt different blocks in different threads, processes, or even different machines.


Computational indistinguishability with Example

For any $n \in \mathbf{N}$, let $X_n$ be a random variable which always equals $n$, and $Y_n$ be a random variable which equals $n$ or $n+1$ each with probability $1/2$. Then the probability ensembles $X = \{X_n\}_{n\in \mathbf{N}}$ and $Y = \{Y_n\}_{n\in \mathbf{N}}$ are not computationally indisinguishable. A possible distinguisher is an algorithm $D$ which, on input $(y, 1^n)$, outputs $1$ if $y = n$ and $0$ otherwise. We then have $\mathsf{Pr}[D(X_n, 1^n) = 1] = 1$ for all $n$ because $X_n$ always equals $n$. On the other hand, we have $\mathsf{Pr}[D(Y_n, 1^n) = 1] = 1/2$, hence
$$\left| \mathsf{Pr}\left[D\left(X_n, 1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n, 1^n\right) = 1\right]\right| = \frac{1}{2},$$
which is constant and thus not negligible. I can't think of any simple example of probability ensembles which are computationally indistinguishable, except trivially if they are identical or just assumed to be indistinguishable. Indeed, constructing probability ensembles which are non-trivially computationally indistinguishable is in a way what cryptography is all about...

Actually, here's an example (although it could reasonably be considered trivial as well). As above, $X_n$ always equals $1^n$. $Y_n$ is the output of the following algorithm on input $1^n$:

Throw $n$ coins.
If the coins are all $0$, output $0^n$. Otherwise output $1^n$.

Thus $Y_n$ equals $0^n$ with probability $2^{-n}$ and $1^n$ with probability $1-2^{-n}$. I claim that they are computationally indistinguishable. Intuitively, $X_n$ and $Y_n$ are identical except when $Y_n = 0^n$, but because this happens with negligible probability, no algorithm is able to distinguish them with non-negligible probability. (Note that this applies to all algorithms, not just PPT ones.)

Let $D$ be any algorithm, we want to estimate
$$\left|\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right]\right|.$$
We remark that, conditioned on $Y_n \ne 0^n$, $(X_n,1^n)$ and $(Y_n,1^n)$ are identically distributed: they always equal $(1^n,1^n)$. Hence,
$$\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\middle|Y_n \ne 0^n\right] = \mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right].$$
Using this, we obtain
$$
\begin{align*}
\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right]
  &= \underbrace{\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n = 0^n\right]}_{\ge 0}
     + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\
  &\ge \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\
  &\ge \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \middle| Y_n \ne 0^n\right] \cdot \mathsf{Pr}\left[Y_n \ne 0^n\right] \\
  &\ge \mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] \cdot \left(1-2^{-n}\right), \\
\end{align*}
$$
hence
$$\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right] \le \underbrace{\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right]}_{\le 1}\cdot 2^{-n} \le 2^{-n}.$$
On the other hand,
$$
\begin{align*}
\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right]
  &= \underbrace{\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n = 0^n\right]}_{\le \mathsf{Pr}\left[Y_n = 0^n\right]}
     + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\
  &\le \mathsf{Pr}\left[Y_n = 0^n\right]
     + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\
  &\le \mathsf{Pr}\left[Y_n = 0^n\right]
     + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \middle| Y_n \ne 0^n\right] \cdot \mathsf{Pr}\left[Y_n \ne 0^n\right] \\
  &\le 2^{-n} + \mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] \cdot \left(1-2^{-n}\right), \\
\end{align*}
$$
hence
$$\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right] \ge \underbrace{\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right]}_{\ge 0}\cdot 2^{-n} - 2^{-n} \ge -2^{-n}.$$

(For those studying the book of Katz-Lindell, this is similar to Exercise 7.1.)


How does one measure the decrease in security, if any, of RC4 when mapping to a specific range of values?

By discarding values 252 to 255, you effectively avoid introducing any new bias; the generic method is expressed in many places, e.g. this article (page 3). To generate random values between $0$ and $d-1$ (inclusive) from a PRNG which produces bit, you do the following:

Choose an integer $r$ such that $2^r \geq d$.
Obtain a $r$-bit word $x$ from the PRNG.
Compute $t = \lfloor \frac{x}{d} \rfloor$.
If $d+td \gt 2^r$, go back to step 2.
Output $x - td$.

Your proposal is equivalent to the algorithm above with $d = 36$ and $r = 8$ (you work with 8-bit words, colloquially known as "bytes").

There are trade-offs about the choice of $r$, which depend on what the hardware and software can do. On an 8-bit CPU with very little power, using bytes is certainly efficient, but involves either doing a division (which will be expensive in CPU time) or using a lookup table with 256 entries (so 256 bytes of ROM -- probably tolerable, since RC4 itself requires 256 bytes of RAM, and RAM is much more expensive than ROM). Speaking of which, RC4 is not necessarily the best choice, performance wise: there are other stream ciphers worth considering.

Note that even though your method does not introduce any bias, you still have the shortcomings of RC4, namely some detectable biases in the raw output (nothing lethal in practice, but enough to give the willies to academic cryptographers), and the absence of any IV, which means that you need a new key for every generated stream (if your messages are consecutive and serialized, you can consider them all as parts of a single big stream, but each new session / reboot MUST imply a new key; otherwise that's the infamous "two-times pad").

36 is for letters and digits; for general messaging you might want to add a few signs for spaces and basic punctuation (at least a word separator).


Where are the ChaCha20 test vectors/examples?


What are possible caveats when generating a group for use as parameters for Diffie-Hellman key exchange?

One requirement that you don't have listed is that the generator $g$ needs to generate a subgroup that's of a large prime order; here's what can go wrong if that is not true:

If the order of $g$ (which we call $q$) has a factor $r$, then the attacker can, hearing $g^x$, determine $x \bmod r$ in $O(\sqrt{r})$ time.  If $r$ isn't large, this immediately implies that you're leaking data
Worse yet, if the order $r$ is smooth (has no large factors), that makes the DLOG problem easy.

One strategy is, as mandragoe suggests, is look for a prime $p$ with $(p-1)/2$ prime as well.  There is certainly a lot to like about this strategy; you can use (say) $g=2$, which can make the computation easier (and if the order of $g$ happens to be $2q$, all that means is that the attacker can learn the lsbit of your DH private values, which really doesn't tell him much, and you can avoid even that by making sure that $p \equiv 7 \pmod{8}$.

On the other hand, it is also a comparatively costly option, as looking for a value $p$ that meets both conditions means going through a lot of candidates.  Now, if you're doing this computation only rarely (say, once a day), that's really not that big of a deal; however if you're coining a fresh group for every exchange, it is certainly more expensive that you need.

An alternative approach is:

Search for a 256 bit prime $q$
Once you have that, scan through 2048 bit values $kq+1$ for a prime; when you find it, call it $p$
For $g$, select an arbitrary value $x$ (2 works), and compute $x^k \bmod p$; if that value is not 1, use it for $g$.

The order of the generator $g$ will be $q$, which is a sufficiently large prime that we don't need to worry about attacks that take $O(\sqrt{q})$ time.

The expensive operation is the search for $p$, which is no more expensive than any other prime search for that size.


Let the modulus is $n$, the message $1< m < n$. In your textbook RSA the signature is $$s = m^{d} \bmod n,$$ where the $d$ is the private key.

Let the target signature be $s' = s^{-1} \bmod n$ and $m' = m^{-1}$

Let expand $s' = s^{-1} =  (m^{d})^{-1} = (m^{-1})^{d}$

Therefore $s'$ is the signature of $m'$.

That is one of the many other reasons that we never use textbook RSA in practice. We should you RSA-PSS or RSA-FDH for signatures.


Generating DH key with specific bit-length

Sure thing. You'd lose up to one bit of security, but that's generally acceptable.


Are checksums essentially non-secure versions of cryptographic hashes?

Are checksums basically toned-down versions of cryptographic hashes? As in: they are supposed to detect errors that occur naturally/randomly as opposed to being designed to prevent a knowledgeable attacker's meticulous engineering feat?

That is one way to look at it. However, hash functions have many purposes. They are also meant to be one-way (an attacker cannot know the preimage without guessing), for which there is no parallel with checksums.

  So, essentially they are non-secure versions of cryptographic hashes, one could say? Thus for the same reason, these checksums are "cheaper" to compute than cryptographic hashes? (e.g. CRC32 vs SHA-256)

Due to their different requirements, checksums are not just "worse, but faster hashes". They are meant to prevent particular kinds of errors. Cyclic redundancy check can detect e.g. all 1-2 bit errors in short inputs, as well as some other common classes of errors in typical applications (e.g. bursts errors). This is better than a truncated cryptographic hash of similar length would be able to do.

A cryptographic hash truncated to 32 bits can easily collide with two inputs that differ in only one or two bits, whereas a CRC won't. The CRC is geared towards reliably detecting error patterns that commonly occur in transit, so it will do better on those kinds of errors and worse on others. The short hash does optimally over all inputs, and as a result does worse than CRC on the inputs CRC is good at dealing with.


Is it possible to determine the symmetric encryption method used by output size?

You can try to determine the block size by modifying each byte of the input data, starting from the last one.

A typical block cipher implementation will mix the change into all other bytes in the block, and usually also to all following blocks, but not to blocks that come before it.

So if you observe e.g.:

 Plaintext      Encrypted
 0000 0000      2348 1234
 0000 0001      2348 4292
 0000 0010      2348 9823
 0000 0100      2348 2149
 0000 1000      2348 6785
 0001 0000      8173 1437

you could be quite certain that it is a block cipher with 4-byte blocks.

For comparison, in typical applications of a stream cipher, only a single byte would usually change. If it is a stream cipher, you can obtain the keystream by encoding 000...0000, because it sounds like it doesn't have a random initialization vector.


Authenticated Encryption with smallest Overhead (Input and Output)

It (GCM) requires a 96-bit IV which is usually split into a 32-bit explicit nonce and a 64-bit counter.

GCM uses a 96 bit IV internally, but the size of the IV is actually configurable (implementations may vary, of course).

From the specification:

  $1 ≤ \operatorname{len}(IV) ≤ 2^{64}-1$.

however, the same specification also indicates:

  For IVs, it is recommended that implementations restrict support to the length of 96 bits, to promote interoperability, efficiency, and simplicity of design.

  Q: The authentication tag has to be 128 bits long (according to Ferguson). Thus, the total overhead is 196 bits.

The size of the authentication tag is also configurable, ranging from 64 bit to 128 bit in 8 bit increments. The shorter tag is just the leftmost bytes of the full 16 tag, so you can basically allow any size tag. The problem with GCM is that the security of the algorithm quickly diminishes for shorter authentication tags. Other algorithms will fare better.

  The bit length of the tag, denoted $t$, is a security parameter, as discussed in Appendix B. In
  general, $t$ may be any one of the following five values: 128, 120, 112, 104, or 96. For certain
  applications, $t$ may be 64 or 32; guidance for the use of these two tag lengths, including
  requirements on the length of the input data and the lifetime of the key in these cases, is given in
  Appendix C

  But what about other algorithms such as CCM or EAX, etc.? Can they use shorter IVs or are they also secure with 64-bit authentication tags? Do they have other vulnerabilities that affect the overhead?

Most authenticated ciphers - including CCM and EAX - are based upon CTR. They just require a nonce, which you can even send in a single byte or even bit, depending on the number of messages. You should study the specific API's how the IV is interpreted. CCM is a bit special in the sense that it also specifies the packet format, although that format is configurable with regard to various sizes.

CCM and EAX depend on (AES-)CBC-MAC and (AES-)CMAC respectively. These constructions are less vulnerable to smaller authentication tag sizes. Both are considered secure when used correctly.

  If there are more authentication encryption algorithms that require the some amount of overhead which is the one with the least computational effort?

There is always OCB mode. It has one block cipher operation per plaintext block and configurable output size. It is also patented and not available for military use (which means you get into a IP rights minefield if you use it).

Currently there are efforts on the way to use the the Keccak sponge for single pass authenticated encryption. That's still under construction though.

Finally there is SIV mode. SIV mode uses a synthetic IV calculated from the plaintext, which doubles as authentication tag. This means that, as long as your plaintext is unique, the calculated IV is unique and the mode is CPA secure and authenticated. SIV is however two pass, two full passes over the plaintext are needed during encryption. This means it is not online as many other modes.


Idea for user/pass hashing to prevent rainbow tables, would it work?

The goal for salts is that they be unique to each account and that they be values highly unlikely to appear in a rainbow table. Here, if usernames are unique then so are the salts. Since hash values are long and random, they won't be in rainbow tables. So hashing the username looks like it provides a good salt value to the extent that usernames are unique in your system.

If you're storing password hashes, you should probably be using bcrypt to do so. Bcrypt is a hashing scheme, but it's more flexible and is designed to mitigate more of the typical password attacks than just rainbow tables. For example, your scheme defeats rainbow tables but it doesn't prevent a brute-force attack where the target's username is known, whereas bcrypt also takes that attack into consideration.

So you have a good salt and your scheme will thwart rainbow table attacks. But good password verification schemes should strive for more.

As a non-cryptographic aside, for flexibility I would recommend not hard-coding the salt derivation in the scheme, regardless of what hashing scheme you choose. Derive the salt in the beginning and then store it separately in the database. This way the salt can be updated or changed if necessary. (Also, no one has to go look at code to figure out how it's generated.) If you choose not to store the salt in the database, then you can never change an account's salt should the need arise and you also have to have to update the password hash if the username ever changes.


Can I base a public-key cryptosystem only on a hash algorithm?

There is actually a system for hash based signatures being standardized, see here.
Hou have described a system where the public key is derived from the private key in such a way that the private key cannot be recovered from the public key. However, it is unclear what operations you can perform with the public key that can only be reversed by persons having the private key. Without such operations the derived public key is useless.
Public keys and private keys do need to have a mathematical relation so that they can be used for encryption / decryption, key agreement or signature generation / verification. Such schemes are based on a specific mathematical problem such as the discrete logarithm problem (DLP) or the RSA problem - factorization of a number that is a product of two or more prime numbers.


Triple DES has been standardized by NIST as DES-EDE. So the EEE versions are usually not present in cryptographic libraries. Using them is not advisable for this reasoning alone. Hardware will not have support for EEE and DDD operations. fgrieu already pointed out the answer by Poncho for theoretical reasons why NIST chose DES-EDE but that's ancient history; everybody just uses DES-EDE where DES is still used.

Two key triple DES is not faster than three key triple DES. There are 3 iterations of DES per block. The number of operations is identical.

Two-key 3DES only provides a security of about 80 bits (for a key size of 112 without parity or 128 bits including parity), while three-key triple DES is still at 112 bits (for 168/192 bits key size). For generic legacy applications NIST currently advises three-key 3DES (that is, DES-EDE, see above). Two-key 3DES has been deprecated, it does not offer enough security for most purposes.

Neither of these modes should however still be used. Three-key triple DES is not broken, but it has weak keys, offers too little security for the key size used, has a small block size (problematic with counter mode and modes providing authentication) and provides lackluster performance.

You should use AES or a modern stream cipher instead. AES is a faster, 128 bit block cipher with key sizes of 128, 192 and 256 bits that provide approximately the security provided by the full key size. AES has authenticated modes such as GCM and EAX that also provide integrity and authenticity on top of the confidentiality that may be achieved if the right mode / implementation is used.

TL;DR: Use three-key triple DES (DES-EDE) only for legacy applications. You are better off rewriting the application to use AES, especially if the applications still use two-key triple DES.


How can AES-like block cipher without non-linear component be broken?

Since the sbox is affine, you can view $s(v)=mv+b$ where $m$ is a 8-by-8 matrix and $b$ and $v$ is a dimension 8 vector over $F_2$. I will show you how  to find $m$ and $b$ in Pari-GP. If it is not clear how to use that combined with the description of AES to create an even bigger linear equation and solve, ask.

Write $\mathbf{0} =(0, 0, 0, 0, 0, 0, 0, 0)$.
Note that $s(\mathbf{0}) = b$, so all that is left to do is find
$m$. Define
$$l(v) = s(v) + s(\mathbf{0}) = mv + b + m\mathbf{0}+b=mv + b + b = mv$$
Note this is a linear function:

s(n) = sbox[n+1] \\ pari-gp is 1-indexed
l(n) = bitxor(s(n), s(0))
a = 10
b = 37
print(  bitxor(l(a),l(b)) == l(bitxor(a,b))  )

will output 1 (True in Pari-GP). To find out what the matrix is,

m = matrix(8, 8, {j}, {i}, {
    ei = 1 << (i-1);
    ej = 1 << (j-1);
    bitand(s(ei), ej) == ej
})

print(m)

which outputs

[1, 0, 0, 0, 0, 1, 0, 1;
 0, 0, 0, 1, 1, 0, 0, 1;
 1, 1, 0, 1, 1, 0, 1, 0;
 0, 0, 1, 0, 0, 1, 1, 0;
 0, 1, 1, 0, 0, 1, 1, 1;
 1, 1, 1, 0, 1, 0, 0, 1;
 0, 0, 1, 1, 0, 1, 1, 0;
 0, 0, 1, 0, 0, 1, 0, 1]

Note that because of how the indices work it is a little weird to read. The 128-th entry in your sbox, which corresponds to the vector $(0, 0, 0, 0, 0, 0, 0, 1)^T$ is 179, and the last column is $(1, 1, 0, 0, 1, 1, 0, 1)^T$ and binary(179) = [1, 0, 1, 1, 0, 0, 1, 1].


You are correct: OCB2 was only named so after the fact. Confusingly, it was named OCB1 in the original 2004 paper.
You can find the OCB2 naming on the paper that introduces OCB3, The Software Performance of Authenticated-Encryption Modes:

Integrated AE schemes were invented to improve performance of composed
ones, but it has not been clear if they do. In the only comparative
study to date [31], McGrew and Viega found that their composed scheme,
GCM, was about as fast as, and sometimes faster than, the integrated
scheme OCB [35] (hereinafter OCB1, to distinguish it from a subsequent
variant we’ll call OCB2 [34]).

Another instance of the name transitioning is in two papers of Minematsu. The first one, Improved Security Analysis of XEX and LRW Modes at SAC 2006, refers to the mode as the original OCB1; a later paper written in 2008, Generalization and Extension of XEX* Mode, already refers to it as OCB 2.0.
Finally, a patent filed by Rogaway in 2005 refers to the mode as OCB 2.0, which is presumably where the name change happened first.


Identity-based proxy re-encryption using different system parameters

This concept is called inter-domain identity-based proxy re-encryption. In this case, the notion of "domain" implies a separate KGC and a set of system parameters.  There are a couple of schemes doing this:

Tang, Q., Hartel, P., & Jonker, W. (2008, December). Inter-domain
identity-based proxy re-encryption. In Information Security and
Cryptology (pp. 332-347). Springer Berlin Heidelberg. Han, J.,
Susilo, W., & Mu, Y. (2013). Identity-based data storage in cloud
computing. Future Generation Computer Systems, 29(3), 673-681.


My question is once the key exchanged has taken place what symmetric algo is used?

Well, that is negotiated between the client and the server (and that negotiation takes place along with the key exchange).
TLS 1.2 had a rather long list of symmetric algorithms that the client and server could choose from; in TLS 1.3, they trimmed it back significantly, currently the options are AES-GCM, ChaCha20/Poly1305 and AES-CCM.


Calculating private keys in the RSA cryptosystem

The public key is $K = e = 53$, already given. $n$ (the modulus) must also be given, so you could say that $(e, n)$ is the actual key.

The private key is $d$ which must satisfy $d * e = 1 \mod \phi(n)$.
So you're looking for $d$ for which $(53 * d) \mod 43200 == 1$. A quick brute-force search (with such small numbers it's not a problem) reveals that $17117$ satisfies this equation.

Now $N=43733$, and you're guaranteed that $(M^e)^d = (M^d)^e = M \mod n$.

Your message is $M=19985$:

$19985^{53}  \equiv 17195 \mod 43733$
$17195^{17117} \equiv 19985 \mod 43733 $

This shows that you can encrypt using the public key and decrypt using the private key.
The opposite also works (for signing the message):

$19985 ^{17117}  \equiv 125 \mod 43733$
$125 ^{53} \equiv 19985 \mod 43733$

There are better ways to find $d$ from $e$ if you know $\phi(n)$. But if you don't, you're in trouble, because you need to factorise $n$ to do that.


Why nobody considers counter re-keying as a standard Block Cipher Mode?

A tweakable blockcipher where the tweak is set to a counter, and the plaintext gets encrypted directly has the same properties as your idea.

When these properties are desired, you can use either a specialized tweakable blockcipher such as threefish, or you turn a normal blockcipher into a tweakable blockcipher.

When using AES, a typical choice is XTS, which has higher performance and avoids related keys. Such a mode is useful for disk encryption, TrueCrypt is a prominent example using it. And it's documentation has a description of XTS

I believe the encryption part of OCB can be viewed as a tweakable blockcipher as well.

These modes achieve the same thing as your idea, while avoiding the downsides(performance, related keys), so it's not surprising that rekeying isn't used to construct tweakable blockciphers.

If you don't use AES, but a cipher with a fast re-keying and no related key vulnerabilities, you can simply concatenate key and counter, which is pretty similar to your idea. I believe this would work with the blockcipher underlying BLAKE. Threefish treats key and counter almost the same way, so you can view as using the concatenation of key and tweak as its key.

Another downside of your mode is that it allows a multi-target attack on the key:

When you encrypt a constant file of n blocks (say a zero initialized file), a brute-force attacker can recover your key with $2^k/n$ operations where $k$ is the size of the key, so you should use larger keys, probably 160+ bits or so.

The attacker encrypts the fixed and known plaintext block with varying keys and compares it against all the know ciphertext blocks. This comparison is O(1) using a hashtable. Each attempt has a $n$ in $2^k$ chance of succeeding, since there are $n$ targets. Thus the cost of the attack is $2^k/n$ invocations of the blockcipher.


AES with shuffleBytes instead of shiftRows

AES ShiftRows operations ensures that each new column contains one byte from one of the 4 old columns. Thus it achieves Full diffusion in 2 rounds.

You are right that there could have been other arrangement / shuffle of bytes to meet this criteria too. But if we analyze AES design, we will find that speed and memory requirement on all types of platforms were also given due attention in designing AES components. For example

MixColumn Matrix values are kept to minimum possible, like 01,02 and 03, which are fastest to implement as 01 is element itself, 02 is just left shift by One 03 is Exclusive OR of 02 and 01
Only one Sbox was used for substituting all state bytes
RCons in key schedule were kept minimum possible with simple in values.
The Shift Rows in 32 bit processor is just (i*8) left rotations of ith row where i=0,1,2,3. In case of 8bit processor, the first row elements remain unmoved and others are shifted based on index.

so if you try to do random permutation or some fixes shuffle bytes, you will end up needing more resources/time on some or all platforms.

But if you dont plan to run you AES variation on all platforms, then you can introduce your own platform specific operation (offcourse security of which still needs to be vetted by experts)


What are limitations of Universally Composable (UC) framework?

"Simulation-based security" is a very general notion. UC security is much more specific - it refers to a simulation-based security proof in the UC framework. As such, simulation-based security encompass the UC framework, which is a particular case of it, and there is no general transformation from any primitive with a simulation-style security argument to a UC secure primitive.

One of the main limitations of the UC framework is that it's strength - arbitrary composability features - also gives rise to strong impossibility results: many important cryptographic primitives are provably impossible to realize with UC-security in the plain model, hence one must rely on trusted setup assumptions, such as the common reference string model, to build protocols in the UC framework.

Arguably, a second limitation is the relative complexity of the framework, which is not so easy to understand and master in depth - although there are now countless examples of proofs in the UC model to look at, as well as simplifications of the model such as simple UC.


The following is more or less a copy-paste of a comment I made on the related ArsTechnica thread. Indeed, StackExchange is probably one of the better places to debate this.

A few reminders first:

there are approximately $p$ elliptic curves over the finite field of integers $\pmod{p}$;
of these curves, only those with (almost) prime order are of cryptographic interest (I will write only about prime order, for simplicity): there are approximately $p/\log p$ such curves;
among these prime curves, there are some known conditions which happen rarely and make the curve insecure;
the "Suite B" generation procedure is basically: pick some seed $\sigma$ (randomly or maliciously; assume that it is malicious), hash it with a cryptographic hash function (and more particularly, a preimage-resistant hash function), and derive curve parameters from this.

The largest class of "subtly weak" curves (with prime order) that we know is the set of supersingular curves, which has a size of about $\sqrt{p}$ and therefore a probability of occurrence of $1/\sqrt{p}$ (neglecting the logarithmic factor). So finding one via the Suite B generation procedure, even in the malicious case, should take about $\sqrt{p}$ tries - which, coincidentally, is exactly as long as solving ECDLP in the first place. (Besides, this class is easy to detect anyway, but that's not the point).

So any useable (by the NSA) class of weak curves would need to be much (= exponentially) larger than this; this is, much larger than all known classes of weak curves.

Then: if such a class exists, then how does the NSA exploit it? Because of hashing, (assuming SHA-1 to be preimage-resistant, which seems plausible), they cannot have inserted backdoor info in the curve: any trap that they use is computable from the curve itself without knowing the seed $\sigma$. This means that such a backdoor is available to any good mathematician (no need to steal NSA secrets!).

So the Suite B curves can be considered as dangerous only if you believe all three following conditions:

there exists a class of curves which is exponentially larger than all known classes of weak curves;
NSA knew about this class 20 years ago, but nobody else has been able to discover it since then;
they deliberately published, and use for themselves, a curve which they know to be weak to anybody else.
I personnally do not believe either (2) or (3), and tend not to believe (1) either. This is why I still believe P-256 to be safe.

Actually, even the DUAL_EC_DRBG scandal makes a strong case that both the P-256 curve (vs. ECDLP) and SHA-1 (vs. preimage computation) are probably safe: if the NSA had had, at the time of the DUAL_EC_DRGB parameter generation, a mean to either compute a SHA-1 preimage OR an elliptic curve discrete logarithm, then they would have been able to publish the seeds $\sigma_P, \sigma_Q$ for both points $P, Q$ while still knowing the discrete logarithm $\log(Q)/\log(P)$. They would have gained the same powers of prediction of the DRBG without leaving such a mess.

Of course, the preceding paragraph does not rule out that the whole DUAL_EC_DRBG scandal could have been deliberate misinformation from the NSA, and that Snowden could be a double agent. But this is leaving the crypto domain for the tinfoil-hat domain...

So why did NIST not use a verifiable method for generating the "Suite B" curves? Again, this is only borderline crypto, but my opinion on this is: nobody asked them to at the time, and it is only post-DUAL_EC_DRBG that we, the crypto community, have matured enough to require verifiability in all published parameters (which is a good thing, but does not mean by itself that P-256, or even worse, ECC in general, is broken!)


Is it necessary for the Rijndael polynomial to be primitive?

Is it necessary to choose a primitive polynomial for an S-Box?

Actually, it is not necessary (and, as the polynomial they actually use in AES, $x^8 + x^4+ x^3 + x + 1$, is not primitive, and so it's a good thing that it's not necessary).

The polynomial must be irreducible (if it isn't, the multiplication operation isn't invertible in general, and hence you don't get a field); however it can be shown that the selection of the polynomial doesn't actually affect the security of the cipher; for any irreducible polynomial, you can adjust the affine transformation within the sbox, the mix column transformation, and the rcon constants within the key schedule to come up with an equivalent cipher (equivalent in the sense that an attack on the modified cipher translates into an attack on the original AES).

  In other words, Is it necessary for the feild to be of full order(255) for a S-Box?

If you mean that there must be a field element with (multiplicative) order 255; well, yes, any representation of $GF(2^8)$ will have precisely 128 such elements.  However, a polynomial being primitive will imply that the element with representation 02 will have such an order; with the standard AES representation, it doesn't.


Should we MAC-then-encrypt or encrypt-then-MAC?

I'm assuming you actually know all of this better than I do. Anyway, this paper neatly summarizes all these approaches, and what level of security they do or don't provide. I shall paraphrase it in English, rather than Mathematical notation, as I understand it.

Encrypt-then-MAC:

Provides integrity of Ciphertext. Assuming the MAC shared secret has not been compromised, we ought to be able to deduce whether a given ciphertext is indeed authentic or has been forged; for example, in public-key cryptography anyone can send you messages. EtM ensures you only read valid messages.
Plaintext integrity.
If the cipher scheme is malleable we need not be so concerned since the MAC will filter out this invalid ciphertext.
The MAC does not provide any information on the plaintext since, assuming the output of the cipher appears random, so does the MAC. In other words, we haven't carried any structure from the plaintext into the MAC.

MAC-then-Encrypt:

Does not provide any integrity on the ciphertext, since we have no way of knowing until we decrypt the message whether it was indeed authentic or spoofed.
Plaintext integrity.
If the cipher scheme is malleable it may be possible to alter the message to appear valid and have a valid MAC. This is a theoretical point, of course, since practically speaking the MAC secret should provide protection.
Here, the MAC cannot provide any information on the plaintext either, since it is encrypted.

Encrypt-and-MAC:

No integrity on the ciphertext again, since the MAC is taken against the plaintext. This opens the door to some chosen-ciphertext attacks on the cipher, as shown in section 4 of Breaking and provably repairing the SSH authenticated encryption scheme: A case study of the Encode-then-Encrypt-and-MAC paradigm.
The integrity of the plaintext can be verified
If the cipher scheme is malleable, the contents of the ciphertext could well be altered, but on decryption, we ought to find the plaintext is invalid. Of course, any implementation error that can be exploited in the decryption process has been by that point.
May reveal information about the plaintext in the MAC. Theoretical, of course, but a less than ideal scenario. This occurs if the plaintext messages are repeated, and the MACed data does not include a counter (it does in the SSH 2 protocol, but only as a 32-bit counter, so you should take care to re-key before it overflows).

In short, Encrypt-then-MAC is the most ideal scenario. Any modifications to the ciphertext that do not also have a valid MAC can be filtered out before decryption, protecting against any attacks on the implementation. The MAC cannot, also, be used to infer anything about the plaintext. MAC-then-Encrypt and Encrypt-and-MAC both provide different levels of security, but not the complete set provided by Encrypt-then-MAC.


How to determine the order of an elliptic curve group from its parameters?

There is a rather deep polynomial-time algorithm for counting the $\mathbb F_q$-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A. O. L. Atkin). It is based on two core ideas:

The number of points is closely linked to a functional equation
$$ \varphi^2-t\varphi+q = 0 \qquad\in\operatorname{End}(E)$$
that the Frobenius endomorphism
$$ \varphi\colon\;E\to E,\;\begin{cases}\mathcal O&\mapsto \mathcal O\\(x,y)&\mapsto (x^q,y^q) \end{cases} $$
satisfies in the endomorphism ring of $E$. If $t\in\mathbb Z$ is chosen such that this equation holds, it is called the trace of Frobenius and one can show that
$$ \#E(\mathbb F_q)=q+1-t \text. $$
(The reason $\varphi$ has anything to do with point counting is that it leaves exactly the points with coordinates in $\mathbb F_q$ invariant.)
For odd $l$, there exist division polynomials $\psi_l\in\mathbb F_q[x]$ which vanish precisely on the $x$-coordinates of the finite $l$-torsion points of $E$. Therefore, one can compute $t\bmod l$ by checking for which $k\in\{0,\dots,l-1\}$ the functional equation $\varphi^2-t\varphi+q=0$ holds modulo $\psi_l$. Computing modulo $\psi_l$ greatly improves the complexity (compared to expanding the terms without any reduction). Having computed $t\bmod l$ for a sufficiently large (according to Hasse's theorem, $\prod_{l\in L}l>4\sqrt q$ is enough) set $L$ of odd primes, the Chinese remainder theorem can be used to reconstruct the trace of Frobenius $t$, thereby yielding the number of $\mathbb F_q$-rational points $\#E(\mathbb F_q)$ on $E$.

Of course, there are implementations of (the improved variants of) this algorithm in most computer algebra systems. Using sage, the number of $\mathbb F_{p^n}$-rational points of an elliptic curve
$$ y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 $$
defined over $\mathbb F_p$ can be computed as:

EllipticCurve(GF(p), [a1, a2, a3, a4, a6]).cardinality(extension_degree = n)


What is the difference between “secp…” and “sect…”?

The sect curves are curves over a binary field. From SEC 2: Recommended Elliptic Curve Domain Parameters (chapter 3):

  The example elliptic curve domain parameters over $\mathbb{F}_{2^m}$ have been given nicknames to enable them to
  be easily identified. The nicknames were chosen as follows. Each name begins with sec to denote
  ‘Standards for Efficient Cryptography’, followed by a $t$ to denote parameters over $\mathbb{F}_{2^m}$ , followed by a
  number denoting the field size $m$, followed by a $k$ to denote parameters associated with a Koblitz curve
  or an $r$ to denote verifiably random parameters, followed by a sequence number.

While the secp curves are over fields over a prime field - or $\mathbb{F}_p$ in mathematical representation. Please read elliptic curve tutorials to understand the difference between the calculations for prime and binary fields.


Is Googles Envelope Encryption the same as Hybrid Encryption?

Hybrid encryption refers to an implementation of a public-key encryption interface by the composition of a public-key primitive to encapsulate a symmetric key that's used with a symmetric algorithm to encrypt the actual messages.  The motivation is that public-key primitives don't perform nearly as well as symmetric ones, so this hybrid encryption optimizes performance by minimizing the use of the former.

In the sense that the Google cloud (and AWS) use the term envelope encryption, there's a difference both in the mechanics and the motivation:

Envelope encryption doesn't require the use of public key cryptography; normally instead it uses symmetric Key Encryption Keys (KEKs, also often labeled "master keys") to encrypt also symmetric Data Encryption Keys (DEKs).
The motivation is not performance like it is with hybrid encryption, but rather key management. Google and AWS promote envelope encryption in connection with their Key Management System services (KMS) that generate and managed master keys internally, and are designed not to allow export of said keys, but rather to require clients to submit messages to the service for decryption/encryption. The intended use of this is that the KMS manages your KEKs, and the clients ask it to encrypt and decrypt DEKs with it. And the point of this is to avoid an architecture where you deploy a copy of the same symmetric master key to lots of hosts in your network, increasing the risk that this key will be exposed by a compromise of one of the servers.

So there is a similarity in that short-term symmetric data keys are getting encapsulated with some sort of long-term key, but what sort of long-term key is assumed is different, and the goal of the constructions isn't the same.


GCM mode of operation with long-term keys

There are two parts to AES-GCM: AES and GHASH.  This can completely ruin the security of both of them.  AES is not designed to resist related-key attacks, so you're in hot water already if you derive multiple keys like this.  Not only does GHASH not resist related-key attacks, but it has a particularly simple structure that illustrates how bad things can get if you make this mistake.

GHASH authenticates a series of messages $m_1, m_2, \dots, m_\ell$ with a long-term key $k$ and a per-message key $s_i$ by $m_i \mapsto \operatorname{GHASH}_k(m_i) + s_i$.  Note that xor, $\oplus$, is just addition in the field $\operatorname{GF}(2^{128})$ that GHASH works in, and for a single-block message, $\operatorname{GHASH}_k(m_i) = m_i \cdot k$ is just multiplication, so the authenticator is simply $m_i \cdot k + s$.

Suppose the sender authenticates a (say) one-block message $m_0$ under $k$ with $r_0$ and a one-block message $m_1$ under $k$ with $r_1$.  That is, suppose you use $k \oplus r_0$ instead of $k$ for one purpose and $k \oplus r_1$ instead of $k$ in another purpose.  Then the adversary learns the authenticators $a_0 = m_0 \cdot (k + r_0) + s$ and $a_1 = m_1 \cdot (k + r_1) + s$.  By the advanced cryptanalytic technique of subtraction, the adversary will find $$a_0 - a_1 = (m_0 - m_1) k + m_0 r_0 - m_1 r_1$$ which they can easily solve for $k$ and forge messages under any nonce $r_i$ of their choice with wild abandon.


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

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

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


If you write $\mathbb Z/n\mathbb Z$ first as $\mathbb Z/p\mathbb Z\times \mathbb Z/q\mathbb Z = \mathbb F_p\times\mathbb F_q$, and then $\mathbb F_p$ as $\mathbb F_p^\times\cup\{0\}$ (and the same for $\mathbb F_q$), then you see (using the discrete logarithm) that taking the $b$-th power in $\mathbb F_p^\times$ corresponds to multiplying by $b$ in the cyclic group $\mathbb Z/(p-1)\mathbb Z$, where $b$ is coprime to $p-1$ by assumption.

If $p-1 = \prod_i p_i^{e_i}$ is the prime power factorization of $p-1$, then you get $\mathbb Z/(p-1)\mathbb Z = \prod_i \mathbb Z/p_i^{e_i}\mathbb Z$ and you have to investigate what multiplication by $b$ (coprime to $p_i$) does to $\mathbb Z/p_i^{e_i}\mathbb Z$.

Writing $\mathbb Z/p_i^{e_i}\mathbb Z = \cup_{j=0}^{e_i} p^{e_i-j}(\mathbb Z/p_i^j\mathbb Z)^\times$ you'll see that you have to determine only the order $o$ of (multiplying by) $b$ in $(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$ (as it gives the order of $b$ in $(\mathbb Z/p_i^j\mathbb Z)^\times$ for all $j\le e_i$ --- slight caution is necessary for $p_i=2$ as only for odd $p_i$ one has $(\mathbb Z/p_i^j\mathbb Z)^\times = (\mathbb Z/p_i\mathbb Z)^\times\times \mathbb Z/p_i^{j-1} \mathbb Z$, whereas $(\mathbb Z/2^j\mathbb Z)^\times = (\mathbb Z/2\mathbb Z)\times \mathbb Z/2^{j-2} \mathbb Z$ for $j>1$). Multiplying with an element of order $o$ in a group of order $g$ gives $\frac{g}{o}$ cycles of length $o$.

Now you have to assemble everything again using either the product structures or disjoint unions.

If you were just interested in the order of the permutation, take just the least common multiple of all group orders at the level of $(\mathbb Z/p_i\mathbb Z)^\times$ and $\mathbb Z/p_i^{e_i-1} \mathbb Z$ (don't forget to do the same for $q$ and beware of $p_i=2$).


(Re-)Using deterministic IV in CTR mode / How to: deterministic AES

I cannot prove that your scheme is secure, but as far as I know, a non-cryptographic hash function would work fine as there is an infinite number of inputs to any given hash, making it impossible to bruteforce all but the shortest messages (which would be an issue for short messages, you may want to append some sort of 128-bit padding).

However, that said, 128-bit block ciphers begin to lose security after $2^{64}$ blocks, as the number of collisions increase. In CBC mode, subsequent blocks use the previous block as an IV. If two blocks have the same output, that means that the two previous blocks XORed together will equal the two plaintexts XORed together.


How are keys mapped to cipher texts in block ciphers with large block sizes?

A block cipher is a family of permutations.
$$F:\{0,1\}^k\times \{0,1\}^b \to \{0,1\}^b$$
That's it!. A key $k \in \{0,1\}^k$ represents one of the permutations of the family. A permutation is an invertible map $$P:\{0,1\}^b \to \{0,1\}^b.$$ The above is a permutation from $2^b$ elements to itself ( the input space of a block cipher). Therefore every element is mapped. Since a key represents a permutation from the block cipher's permutations, then every plaintext is mapped to some ciphertext.
There are $2^n!$ permutations, however, usually, we have $2^{64},2^{128},2^{256}$ etc. keyspace. With the Stirling formula $$2^{b}! \approx \sqrt{2\pi 2^{b}} \bigl(2^{b}/e\bigr)^{2^{b}}.$$ Plug this into AES-256
$$2^{256}! \approx \sqrt{2\pi 2^{126}} \bigl(2^{256}/e\bigr)^{2^{256}} \!=  \sqrt{2\pi 2^{256}} e^{-2^{256}} \bigl(2^{256}\bigr)^{2^{256}} \ggg 2^{256}$$
So, practically there is no way to represent all possible permutations.
What we want that the block cipher must be is indistinguishable from a random permutation. That is not an easy job, since even after 20 years no one yet showed that AES is a PRP, but we believe that it is.

I guess what I'm trying to ask is, if it's impossible to map a specific key to a specific, unique ciphertext value, what does it actually map to if I just pick 32 random bits? It seems that each possible key would have to map to multiple ciphertexts.

If you select a random key or any key of the block cipher, start from encryption the all-zero plaintext to the all-one plaintext. Since the key selects a permutation then each will be a different ciphertext value.
You can see this also in this way

The input of the block cipher is processed regardless of its input value and mapped (encrypted) to a ciphertext. Since the block cipher needs the decryption, i.e. the reverse map, then every ciphertext mapped back to the plaintext that $$m = D_k(E_k(m))$$ under the same key.

Multiple values are not possible since we have a permutation. Even it is not a function, remember a function can have only one value in the range.

An educative example:
Consider the block cipher $$F:\{0,1\}^2\times \{0,1\}^3 \to \{0,1\}^3$$ that has 2-bit keyspace and 3-bit block size. The number of possible permutations is $2^3! =40320$ and note that it is not the power of 2. Consider the below permutation as one of the permutations selected by the one of the keys $k_1,k_2,k_3,k_4$ of the block cipher.
$$P = \begin{pmatrix}0& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\7 & 2 & 4 & 0 & 3 & 5 & 6 & 1 \end{pmatrix} \text{ and }$$
As we can see, with the permutation;

All inputs of the cipher is mapped to one
They are mapped 1-1 by the nature of the permutations that make the inverse permutation possible.


is OPE able to produce different cyphertext for same plaintext?

Boldyreva et al.'s scheme is not randomized. However, there is a folklore way to "randomize" it by choosing randomly from the range gap in the last recursive step of the algorithm. It's not clear what security improvement this buys you, though, since it only really randomizes the last few bits of the ciphertext.

There are schemes meeting a randomized version of Boldyreva et al.'s IND-OCPA definition (q.v. Kerschbaum, CCS'15) but they require large client storage.