Post quantum security of the BLAKE family

There is no proof, there are only advancements. BLAKE2 is not completely MD, it is HAIFA which extends the MD to eliminate the problems and BLAKE3 is a parallel hash.
Quamtum collision attack costs
The best know generic quantum collision is the takes $\mathcal{O}(2^{n/3})$ time due to Brassard–Høyer–Tapp (BHT). It is usually advertised (even by the NIST) with only the time but we have other costs, too. BHT builds a huge table of size  $\mathcal{O}(2^{n/3})$ then runs the Grover's algorithm with the cost  $\mathcal{O}(2^{n/3})$ and this make a total cost $\mathcal{O}(2^{2n/3})$
None of the variants, including the Ambainis algorithm which has still cost around $\mathcal{O}(2^{2n/3})$, doesn't lower the cost barrier of the classical attack cost $\mathcal{O}(2^{n/2})$
We already know that there is a lower bound on number of queries a generic algorithm mus take $\Omega(2^{n/3})$
So there are no threats from QC that we can see.
Quantum Pre-Images attack cost
Grover's algorithm is the best generic algorithm with $\mathcal{O}$-time and doesn't use much space as the BHT or others. But the sequential evaluation of the hash function is the problem there. Even you evaluate one in a nano-second you can get at most $2^{54}$ in a year and you need $2^{64}$-year to find the pre-images. The other cost is not included. One can run Grover's algorithm in parallel, however, the advantage not the same as the classical one, you will get $\sqrt k$ speed up from $k$ machines.
Therefore if you have 256-bit output, you will be safe from quantum attacks for hash functions.

Collapsibility
Collapsibility is defined by Unruh as a quantum equivalent of collision resistance of hash functions.

2016, Computationally Binding Quantum Commitments

Informally, for cryptographic hash functions, collapseability requires an adversary that outputs a hash value together with a superposition of corresponding preimages is not able to tell if the superposition gets measured or not.

The result of Unruh is this

showed that there is a hash function that is collision-resistant and thus can safely be used in a classical commitment scheme, but is not secure when the commitment scheme is used in a quantum setting

so we have a one-way relation;
-Collapsability implies Collision resistance.
Fer showed that

He applied the approach to the Merkle-Damgård and sponge hash construction, proving that they are collapsing if the underlying compression function is.

Gunns and Manning showed that

Binary tree hash of fixed length is collapsing.
Variable Length tree hashing with Domain Separation is collapsing.


Other than the oddity/bug in final note, this seems to be a classical, speed-optimized implementation of standard DES (for what we see; there could be variations in the S-table content, exact bit twidling in permutation P, or key scheduling).

The code has:

IP, final permutation and IP-1 per Richard Outerbridge's method.
Pre-rotation by 1 bit before the round loop, undone afterwards, in order to  need no shift (rather than a 1-bit rotation) for SP8, and shifts counts that most are multiples of 8 (which excellent compilers for 8-bit CPU love).
Two DES rounds per partially unrolled round loop, so that the 8 loops perform 16 rounds.
Pre-computed 6-bit subkeys grouped as two 32-bits words (with 8 unused bits in each), merged in parallel for 4 S-boxes at a time. Correspondingly, it is applied subkeys on the input of expansion E.
Expansion E reduced to rotating the appropriate part of right or left into the low-order 6 bits, and masking to keep these bits before indexing the S tables. This uses that E is highly regular, and combines with E.
Permutation P merged with the S-boxes, which is the game-changing optimization of DES in software. SPj is DES's S-box j with expansion E (modified to account for the 1-bit pre-rotation) applied on the output, that is indexing SPj[x] yield E(SPj(x)), give or take the 1-bit pre-rotation. A table's output width thus grows from 4-bit to 32-bit. There's a data size penalty: S-boxes now eat 16384 bits of table rather than 2048.
Note: It is not used the size optimization that keeps the bitwise-OR of the eight 32-bit tables and extracts the bits with eight 32-bit masks, which used to be classical in heavily size-constrained CPUs.

Note: a variant does without fval, clarifying per my taste. I sneaked in some comments.

for ( round = 0; round < 8; ++round )
    {
    // apply E, subkeys, S and P for odd  S-boxes, rounds changing leftt
    work   = keys[keysi++] ^ ((right << 28) | (right >> 4));
    leftt ^= SP7[ work        & 0x3f ];
    leftt ^= SP5[(work >>  8) & 0x3f ];
    leftt ^= SP3[(work >> 16) & 0x3f ];
    leftt ^= SP1[(work >> 24) & 0x3f ];
    // apply E, subkeys, S and P for even S-boxes, rounds changing leftt
    work   = keys[keysi++] ^ right;
    leftt ^= SP8[ work        & 0x3f ];
    leftt ^= SP6[(work >>  8) & 0x3f ];
    leftt ^= SP4[(work >> 16) & 0x3f ];
    leftt ^= SP2[(work >> 24) & 0x3f ];
    // apply E, subkeys, S and P for odd  S-boxes, rounds changing right
    work   = keys[keysi++] ^ ((leftt << 28) | (leftt >> 4));
    right ^= SP7[ work        & 0x3f ];
    right ^= SP5[(work >>  8) & 0x3f ];
    right ^= SP3[(work >> 16) & 0x3f ];
    right ^= SP1[(work >> 24) & 0x3f ];
    // apply E, subkeys, S and P for even S-boxes, rounds changing right
    work   = keys[keysi++] ^ leftt;
    right ^= SP8[ work        & 0x3f ];
    right ^= SP6[(work >>  8) & 0x3f ];
    right ^= SP4[(work >> 16) & 0x3f ];
    right ^= SP2[(work >> 24) & 0x3f ];
    }

Off-topic note: The question's code contains the idiom >>> which is an indication that it is it Java (where this means logical shift right).
If so, some >> needs to be changed to >>>, at least in (right << 28) | (right >> 4) and similar, because in Java >> is specified to leave the high-order bit of (32-bit) int unchanged, which is not the intention.
On the other hand, if this is C, all int should be changed to unsigned, or better uint32_t, because using >> on a signed variable is not fully specified in C, giving results that depend on the compiler's mood.


I read the question as asking if $F$ can be a PRF, given that it is such that $F(k, F(k,0)) = 0$.

Assume you are given a black box that implements a function: given some input $x$, it outputs a result $y$, such that the same input $x$ always give the same output $y$. It is given that one of the following holds:

0: The box is a random oracle (equivalently: implements a Pseudo-Random Function); that is, the box outputs a random $y$ when given a new $x$, and otherwise outputs the same $y$ that it has output for that previously submitted $x$;
1: The box outputs $y=F(k,x)$ for some fixed unknown $k$, with $F$ your function such that $F(k, F(k,0)) = 0$.

You are free to use the box. Can you design an experiment to determine, with high confidence, which of 0 or 1 holds? If yes, what's that experiment? The definition of an experiment should include what input(s) it submits to the box under test, and what it performs with the box's output(s) and any other quantity that it manipulates in order to reach a decision/result that can be only be either 0 or 1. Such experiment would allow to recognize $F$ from a PRF, that is prove that $F$ is not a PRF.

More formally: you need to exhibit an experiment better than random at distinguishing 0 from 1, and prove that by showing it gives positive advantage (or, even more formally, non-vanishing advantage when the bit size of $F$ grows). The advantage (given by an experiment) is the difference between odds that the experiment concludes that 1 holds when 1 holds, minus odds that the experiment concludes 1 holds when 0 holds
$$Adv=\Pr[\,\text{Exp}(1)=1\,]-\Pr[\,\text{Exp}(0)=1\,]$$
where the parenthesis after $\text{Exp}$ contains the situation in which the experiment is run. Reversing 0 and 1 leaves the advantage unchanged.

Many texts define the advantage with an absolute value: this addition is only there to fix an experiment that guesses wrong better than random, and consequently to allow simplifying the description of experiments by only telling the principle used to make some decision, leaving the decision itself unspecified.

Defining the experiment clearly is the first step in a proof involving computing its advantage. In the context, experiment has alternate names: algorithm is more formal; I find adversary  more descriptive of reality, but it is known to create confusion with advantage.


Pollard's kangaroo attack on Elliptic Curve Groups

It turns out that, yes, the algorithm applies to ECDH. It can be found in 19.6 of Handbook of Elliptic and Hyperelliptic Curve Cryptography.

More details:

For both the tame and wild kangaroo, the ($i+1$)st hop that the kangaroo takes, $w_{i+1}$, is given by

$$ w_{i+1} = w_i \oplus (H(w_{i+1}) \otimes G) $$

Here, $H$ is a hash function, $\otimes$ is scalar multiplication, and $\oplus$ is point addition on an elliptic curve, and $G$ is a base point on the curve.

You can also compute the distance $d_i$ that each kangaroo travels after $i$ steps, with $d_0 = 0$ and $d_{i+1} = d_i + H(w_i)$.

If you want to search for a discrete log in an interval $[a,b]$, let the tame kangaroo lay $N$ "traps", one at each hop. Then set the wild kangaroo loose, starting at $bG$. The hope is that the wild kangaroo will hop into a tame trap. If their paths intersect, we immediately have a solution to the ECDLP.

In the Python code below is a really lame implementation of it the search. I assume there's an available hash function H. p is the prime of the elliptic curve group $\mathbb{E}(\mathbb{F}_p)$, a,b is the search interval $[a,b]$, y and basepoint are parts of the ECDLP to be solved: $y = t\otimes G$. $t$ solves the ECDLP, and the kangaroo search will probabilistically find it. $N$ is the number of iterations.

def kangaroo_search(basepoint, p, y, a, b, N):

  # setting the trap
  x_tame = 0
  y_tame = b * basepoint

  while N > 0:

    x_tame += H(yT) # scalar addition
    y_tame += H(yT) * basepoint # operations are on E(GF_p)
    N = N - 1

  assert y_tame == (b + x_tame) * basepoint

  # wild search
  x_wild = 0
  y_wild = y

  upper_limit = b - a + x_tame
  while x_wild < upper_limit:
    x_wild += H(y_wild)
    y_wild += H(y_wild) * basepoint # operations are on E(GF_p)

    if y_wild == y_tame:
       print "Victory!"
       return b + x_tame - x_wild

  # index not found
  return None


Certificate signature with SHA-1 and RSA: where do 1888 bits come from?

I think you don't quite understand how RSA signatures work (and why they are the size they are).

When generating an RSA signature, we follow a two-step process:

We take that hash of the message we're signing, and convert (and pad) it into an integer $M$ which is between 0 and $N$ (where $N$ is a large integer that specified by the RSA key)
We use the RSA private key, and convert $M$ into a signature $S$, which is also an integer betwen 0 and $N$

The resulting integer value $S$ is the signature.

From this description, it should be obvious that $S$ is essentially the same size as $N$.  So, how big is $N$?

Well, for the RSA keys that you use, it is 2048 bits long (which, in the context of RSA, means that it is an integer between $2^{2047}$ and $2^{2048}-1$).

Hence, the RSA signatures you see are 2048 bits long, not because someone decided to pad out the hash an extra 1888 bits, but instead when they generated the RSA key, they decided to make that key 2048 bits long.  They didn't add 1888 bits to the hash because they thought 1888 was a nice number; instead, they extended the hash to 2048 bits because whoever generated the RSA key thought 2048 was a nice number.

Now, you might ask: why did they pick a key of that size?  Well, more than anything else, because that's a round number.  You can generate RSA keys of just about any size (however, too small keys can be broken, and too large keys just waste time), and practically speaking, there's little difference between an RSA key of 2048 bits and one of 2000 bits.  However, 2048 bits is what everyone expects nowadays, and so that's what everyone uses.

You asked for a reference about how the RSA padding process works; the one that immediately comes to mind is PKCS #1, which explains exactly how to generate RSA signatures (using several different padding methods).


No. Alice encrypted X by John's public key to have Y. e.g. Enc(key_John, X)= Y.
So the only work that John is able to do is decrypting Y by his private key to have X.

Generaly, first Alice here has encrypted X by John's key, then encrypted the result by Bob's key. Therefore both Bob and John have recieved: Enc(key_Bob, Enc(key_John, X))

So to get X again from Z, you must first achieve Y from Z( by decrypting Z via Bob's key), then achieve X from Y ( by decrypting computed Y via John's key). which means:

Dec(key_John, Dec(key_Bob, Enc(key_Bob, Enc(key_John, X)))

Note that each person only can decrypt the message which is encrypted by his key.


Why are some group representations much easier to compute discrete logarithm for?

Well, the group being isomorphic doesn't imply that the isomorphism is efficiently computable. If $G \simeq H$ via $\phi : G \rightarrow H$ and $\phi$ is computable, then indeed, DLOG is no harder in $G$ than in $H$ because you can transform the instance.

In the case you mentioned, we have $G = \mathbb Z/(p-1) \mathbb Z$ and $H = (\mathbb Z/p\mathbb Z)^\times$. A efficient morphism $\phi: G \rightarrow H$ is known, it called `fast exponentiation'. So DLOG is no harder in $G$ than it is in $H$. But computing a reversed morphism $\psi: H \rightarrow G$ seems harder...


Pulling information from the wikipedia entry on Salsa20:

eSTREAM selection
Salsa20 has been selected as a Phase 3 design for Profile 1 (software) by the eSTREAM project, receiving the highest weighted voting score of any Profile 1 algorithm at the end of Phase 2.[6] Salsa20 had previously been selected as Phase 2 Focus design for Profile 1 (software) and as a Phase 2 design for Profile 2 (hardware) by the eSTREAM project,[7] but was not advanced to Phase 3 for Profile 2 because eSTREAM felt that it was probably not a good candidate for extremely resource constrained hardware environments.[8]
Cryptanalysis
As of 2015, there are no published attacks on Salsa20/12 or the full Salsa20/20; the best attack known[3] breaks 8 of the 12 or 20 rounds.
In 2005, Paul Crowley reported an attack on Salsa20/5 with an estimated time complexity of 2165, and won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis".[9] This attack, and all subsequent attacks are based on truncated differential cryptanalysis. In 2006, Fischer, Meier, Berbain, Biasse, and Robshaw reported an attack on Salsa20/6 with estimated time complexity of 2177, and a related-key attack on Salsa20/7 with estimated time complexity of 2217.[10]
In 2007, Tsunoo et al. announced a cryptanalysis of Salsa20 which breaks 8 out of 20 rounds to recover the 256-bit secret key in 2255 operations, using 211.37 keystream pairs.[11] However, this attack does not seem to be comparative with the brute force attack.
In 2008, Aumasson, Fischer, Khazaei, Meier, and Rechberger reported a cryptanalytic attack against Salsa20/7 with a time complexity of 2153, and they reported the first attack against Salsa20/8 with an estimated time complexity of 2251. This attack makes use of the new concept of probabilistic neutral key bits for probabilistic detection of a truncated differential. The attack can be adapted to break Salsa20/7 with a 128-bit key.[3]
In 2012 the attack by Aumasson et al. was improved by Shi et al. aainst Salsa20/7 (128-bit key) to a time complexity of 2109 and Salsa20/8 (256-bit key) to 2250.[12]
In 2013, Mouha and Preneel published a proof[13] that 15 rounds of Salsa20 was 128-bit secure against differential cryptanalysis. (Specifically, it has no differential characteristic with higher probability than 2−130, so differential cryptanalysis would be more difficult than 128-bit key exhaustion.)

Salsa20 is about as secure and analyzed as one could reasonably ask for. It is one of the few alternatives to AES that a knowledgeable cryptographer could comfortably suggest for usage in the real world.


OFB mode and CFB mode error propagation in 64bits

First, approximately nothing in modern cryptography cares about the notion of error propagation in block cipher modes of operation—it is an archaic relic of the dark ages of crypto engineering that left us with hopelessly confusing concepts like ‘block cipher modes of operation’ thrust into the faces of hapless application engineers.  If you want to detect errors you should use authenticated encryption (unless you have a strong reason to suspect they will be uniform rather than malicious in which case an error-detecting code like a CRC is better).

So unless you're answering an exam question in a class that you might want to drop anyway, it's not likely to figure into anything in the real world.  There's hardly ever any reason to use CFB or OFB anyway: CTR is simpler and faster and more widely deployed as part of the authenticated encryption scheme AES-GCM.

Also, while the block size doesn't affect the answer to this question about CFB mode and OFB mode, you should never use a 64-bit block cipher (even if it has larger keys, like 3DES or Blowfish or IDEA; the block size, not the key size, is the problem) until you understand how bad it can be and why the badness is inapplicable to your needs.

That having been said…

The basic idea of CFB is to use the encryption of the IV as a one-time pad for the first block, and use the encryption of the first ciphertext block as a one-time pad for the second block, and so on: if the plaintext is $P = P_1 \mathbin\Vert P_2 \mathbin\Vert P_3 \mathbin\Vert \cdots$, then the ciphertext is $C = C_1 \mathbin\Vert C_2 \mathbin\Vert C_3 \mathbin\Vert \cdots$, where

\begin{align*}
  C_1 &= P_1 \oplus E_k(\mathit{IV}), \\
  C_2 &= P_2 \oplus E_k(C_1), \\
  C_3 &= P_3 \oplus E_k(C_2), \\
      &\vdots
\end{align*}

The basic idea of OFB is to use the encryption of the IV as a one-time pad for the first block, and use the encryption of the first pad block as a one-time pad for the second block, and so on:

\begin{align*}
  C_1 &= P_1 \oplus E_k(\mathit{IV}), \\
  C_2 &= P_2 \oplus E_k(E_k(\mathit{IV})), \\
  C_3 &= P_3 \oplus E_k(E_k(E_k(\mathit{IV}))), \\
      &\vdots
\end{align*}

What happens if, during transmission, $C_2$ gets replaced by $C'_2 = C_2 \oplus \varepsilon$ for some error pattern $\varepsilon$?  Then we will have $C' = C_1 \mathbin\Vert C'_2 \mathbin\Vert C_3 \mathbin\Vert \cdots$, which, on decryption, gives $P' = P'_1 \mathbin\Vert P'_2 \mathbin\Vert P'_3 \mathbin\Vert \cdots$.  Let's examine how $P'_i$ is related to $P_i$.

The equation for $P'_1$ depends only on $C'_1 = C_1$ and $\mathit{IV}$, so $P'_1 = P_1$ is unaffected, both in CFB mode and in OFB mode.
In CFB mode, $P'_2 = C'_2 \oplus E_k(C_1) = \varepsilon \oplus C_2 \oplus E_k(C_1) = \varepsilon \oplus P_2$.  Likewise, in OFB mode, $P'_2 = C'_2 \oplus E_k(E_k(\mathit{IV})) = \varepsilon \oplus C_2 \oplus E_k(E_k(\mathit{IV})) = \varepsilon \oplus P_2$.  So the same bits flipped in $C'_2$ from $C_2$ get flipped in $P'_2$ from $P_2$.
What about $P'_3$?  Find an equation for $P'_3$ from the relations above in CFB mode and in OFB mode, and see if you can figure out how $P'_3$ is related to $P_3$.
What about $P'_4$?  Does the answer change appreciably from the answer for $P'_3$?


Secret sharing over reals - constructing a (k,n) threshold scheme

This $(k,n)$ scheme works, but isn't very interesting.

Effectively, it is:

For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set.

For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $\binom{3}{2} = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 \bmod 1), (r_2, z-r_2 \bmod 1), (r_3, z-r_3 \bmod 1)$, and distribute to the three share holders the shares:

$$(r_1, z-r_2 \bmod 1)$$
$$(r_2, z-r_3 \bmod 1)$$
$$(r_3, z-r_1 \bmod 1)$$

It works, as:

For any set of $k$ share holders, they can reconstruct the secret, as there is a $(k,k)$ threshold scheme with those share holders with all the shares.  In the above example, the first two share holders jointly know both $z-r_2 \bmod 1$ and $r_2$, allowing them to reconstruct $z$.
For any set of $k-1$ share holders, they learn nothing of the secret; for any of the $(k,k)$ threshold schemes, there will always be at least 1 missing share, and so they can learn nothing.

It's quite straight-forward; the biggest issue is that this requires distributing $\binom{n-1}{k-1}$ independent values to each share holder; this is rather large if you're trying to implement a $(500,1000)$ access structure.


Optimizing SHA-256 implementation for fixed input prefix

You can't completely precalculate 1111, however, you can completely precalculate messages that have a length multiple of 512. The reason is simple, SHA-256 uses 512-bit message block per compression, i.e. the compression function of SHA-256 uses 512-bit message inputs and 256-bit previous hash values.
$$C:\{0,1\}^{256}\times \{0,1\}^{512} \to \{0,1\}^{256}$$
and
$$H_i= C(H_{i-1},m_i)$$ where each $m_i$ has 512-bit lenght and $H_0$ is the IV.

per comment below

To be honest, my input is 32-Byte ones || 32-Byte X || 32-Byte Y, what exactly do I have to precalculate with X is not constant?

32-Byte makes 256 bits, therefore you cannot completely precalculate one compression. However, still, you can pre-compute some rounds of the compression function it that helps;
The SHA-256 uses a block cipher with 64 rounds and each round uses the message as a key and you can calculate 8 rounds of the next compression call. The key $W_i$ for round $i$ is formed by the message words $M_t$ of the block is formed by;
$$W_i = \begin{cases}M_t^{(i)} & 0 \leq t \leq 15 \\
\sigma_0^{256} W_{t-2} + W_{t-7} + \sigma_1^{256}W_{t-15} + W_{t-16} &
16 \leq t \leq 63
\end{cases}$$
With the 32-byte you can precalculate only 8 rounds of the compression function. The Y has no such options since at the beginning of the rounds the previous hash value from the previous compression function is needed.

using $11..11$ as a full block:
There is one way, though not effective, one can calculate $H'=C(H_0,11..11)$. This will require padding. Now you can use this $H'$ as the $IV$ for the $\operatorname{SHA256'}$; That is
$$H_i= C(H_{i-1},m_i)$$ where each $m_i$ has 512-bit lenght and $H_0$ is the $H'$ then your real message becomes as
$$11..11 \mathbin\| padding_1 \mathbin\| X \mathbin\| Y \mathbin\| padding_2$$


Decrypting an encrypted text out of order

$\operatorname{ROT}(n)$ is also known as the Caesar cipher.

$\operatorname{ROT}(n)$ can be thought of as a character based stream cipher. It works because addition - the encryption method used - is commutative. In other words

$\operatorname{ROT}(x, \operatorname{ROT}(y, m)) = \operatorname{ROT}(y, \operatorname{ROT}(x, m))$.

Another well known commutative function is $\operatorname{XOR}$. It is used by the one time pad, but - more practically - also for block ciphers in streaming mode.

So you can encrypt using AES in CTR mode using two different keys in any order and get the same ciphertext. And decryption will work in any order as well.

Note that you should use an IV or nonce if you reuse the keys. Reusing a key stream generated from the key and IV breaks confidentiality. Together with $\operatorname{XOR}$ it breaks the scheme as you can XOR out the key stream.


(Whitebox Crypto) Using ChaCha20, is it safe to reduce the nonce length in a single block cipher?

Am I considerably reducing the complexity of finding the original key this way?

No. If key was only used as input of chacha20_block(key, counter=0, nonce) when preparing the lookup_tables, then finding the original key is demonstrably at least as hard as breaking chacha20 (the algorithm) in its intended usage.

  Am I increasing attack chances?

Depends comparing to what, and under what threat model. Most obvious issue: the nonce becomes predictable with sizable probability.

  I'm looking for ways to increase the nonce length without exploding the memory size.

If we stick to producing the same results as chacha20_block(key, counter=0, nonce), modeling that only as a strong PRF of nonce, then demonstrably memory size in bits is at least: number of possible nonces × output width in bits.

On the other hand, it is possible to increase the nonce length. One trivial way is to have a normal-width nonce with only the low-order bits changing.

With some increase in memory, it is possible to use arbitrary and normal-width nounces, and even to hide their value until use: in the black box store F(nounce) where F is a public PRF such that collision among actually used nounces does not occur (either make F wide enough to have little collisions for random nounces, or restrict actually used nounces to avoid collision); and at each use compute F(nounce) and use the output to decide which tabulated value should be output.

Note: I'm not seeing the whole thing as true white box cryptography, because the would-be box is so severely limited in what it can compute. It is more like a One Time Pad with true randomness replaced by strong-pseudo randomness generated by a cryptographically strong PRNG which key is known to only one side. I see nothing this can achieve that plain symmetric crypto with diversified keys does not also achieve, with the later having the advatage of not requiring massive storage.


Can we associate HMAC signed messages with each other?

To answer the new question, Mihir Bellare has proved that HMAC, applied to a Merkle–Damgård hash function such as the SHA-2 family, is a "privacy-preserving MAC" (PP-MAC) if the compression function of the underlying hash function is itself a PP-MAC.

Basically, the "privacy preserving" property means that even an attacker who gets to choose two equally long sequences of multiple (unique) messages, and submit them to an oracle who picks one of the sequences and returns the MACs of those messages (computed with a random secret MAC key) cannot tell with a non-negligible advantage which sequence the oracle picked.  (The actual PP-MAC game in the HMAC paper even allows the attacker to submit the messages to the oracle one pair at a time, and possibly adjust their later choices based on the returned information.)

As far as I know, no attacks have been published on any widely used reputable* M-D type hash functions that would contradict the assumption that their compression function is a PP-MAC.  This includes the SHA-2 family, as well as the obsolete SHA-1, and even the really obsolete and broken MD5 hash.  (Indeed, the collision attacks on MD5, which violated the assumptions of the old HMAC-MD5 security proof, were the original motivation for this new proof.)

As for SHA-3 (Keccak), it's not actually a Merkle–Damgård hash, so the standard HMAC security proof does not directly apply to it.  However, I do believe that the original Keccak paper itself asserts the PRF (and thus PP-MAC) security of HMAC-SHA3, as a corollary of its "flat sponge claim".

*) To some extent, this is a circular claim, since any hash function whose compression function was demonstrably not a PP-MAC would almost certainly be viewed with plenty of justified suspicion, even if this somehow failed to affect its collision or preimage attack resistance.


Is AES in CBC mode secure if a known and/or fixed IV is used?

Do not use a fixed IV. It can have seriously negative consequences. This is especially true for CBC mode.

That said, a random 128-bit IV stored in plaintext is typically what you want. The IV can be known to an attacker without breaking security.


Pre-Image Resistance of repeated, patterned SHA2-256 digests

Question 1: Does knowing the values $H_1, \dotsc, H_N$ and the length of common pre-image substring "Alpha" leak any information about "Alpha"?

Only in the sense that it enables an adversary to test a guess for what the string might be.  In particular, suppose the random variable $X$ has some probability distribution as far as you know.  Knowing what $H(X \mathbin\| i)$ is narrows down the probability distribution on $X$ a great deal—possibly even to a unique value—and enables you to test a guess which you might not be able to do without knowing $H(X \mathbin\| i)$, but there's no way known to search for what $X$ might be cheaper than brute force.

Of course, if $X$ is simply (say) uniformly distributed among the English names for Greek letters—Alpha, Beta, Gamma, etc.—then the brute force search is already pretty cheap!  Any security arises from a distribution with many more possibilities and much lower probabilities than $1/24$.

  Question 2: Would double-hashing make any significant difference to pre-image security? E.g.: $H_i = H(H(\text{“Alpha”} \mathbin\| i))$

No; at most, it would slightly raise the false positive rate for a search.


Proving that you have $k$ keys out of $n$ without revealing which keys they are

As I wrote in a comment, I believe your solution only works with some public-key schemes, because usually a full-blown public encryption scheme must include randomness to allow encryption of low entropy plaintexts without others being able to guess and encrypt. (Still, it would probably allow verification of key-ownership in some such schemes if access to the underlying primitive like unpadded RSA is assumed.)

A patched solution is for Bob to use Shamir Secret Sharing to share a symmetric key, which he uses to encrypt all the necessary information to reproduce the public-key ciphertexts. That is, he creates a symmetric key, computes the shares and encrypts them using each public key. He then encrypts both all the coordinates and the steps taken to encrypt them, including any randomness the schemes may use, using the symmetric key.

(He does not need to reveal any coordinates in plaintext, but should encrypt all the public keys if Alice does not know them. This means the scheme reveals to Alice which the other public keys were if she has the $k$-subset.)

Alice will be able to verify that the coordinates are on the same polynomial and that they were indeed encrypted using each public key.


Understanding why Semantic Security implies Message Recovery Security

The definition of semantic security we see in the Shoup book is better explained in his well-known paper Sequences of Games: A Tool for Taming Complexity in Security Proofs.
You must pay the very attention to their words on page 15 of the book:

Actually, our attack game for defining semantic security comprises two alternative "sub-games",
or "experiments" --- in both experiments, the adversary follows the same protocol; however, the
challenger’s behavior is slightly different in the two experiments.

So, the point here is that we consider two games: this is why sometimes the adversary $\mathcal{B}$ receives from the SSChallenger a c (that I'll call it here) "well formed"; this is the Game 1, or the game of message $m_1$;
Sometimes, c is only "semanticly" equivalent to an encryption of $m_0$ or $m_1$; let me call it "dummy c"; this is the Game 0, or game of message $m_0$.
Furthermore, after receiving a c", the adversary $\mathcal{B}$ passes it on to $\mathcal{A}$, the message recovery adversary. When that c is "well formed", the chance of the adversary $\mathcal{B}$ is equal to the chance of $\mathcal{A}$ guessing.
But when c is dummy, $\mathcal{A}$ cannot help, and $\mathcal{B}$ best chance is $1/|M|$.


How do we know if we have successfully decrypted something?

Given $d$ we can factor $n$ as follows;

compute $k=de-1$
choose random integer $g$ $1 < g< n$
$k$ is even with $k=2^tr$ with odd $r$ and $t\geq 1$
compute $x = g^{k/2}, g^{k/4}, \ldots,g^{k/2^t} \pmod n$ until $x>1$ and $y=\gcd(x-1,n)>1$

the either $p$ or $q$ is equal to $y$.

If there is no solution find another random $g$.

Looking for all possible $d'$s by this way will be costlier than factorization methods. However, if there is a non-gibberish that you found, you can try to factorize with your $d'$ to see that it is actually $d$.


A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem

First: Lemma 1 says that $||\mathbf{x}|| \leq \alpha q \sqrt{n}$ with overwhelming probability if $\mathbf{x}$ is drawn from the discrete Gaussian since $\frac{1}{2^n}$ is negligible.

Next, from properties of absolute values, $|a + b| \leq |a| + |b|$. So, leaving the $2$ out for now and writing $\mathbf{s_A}^T\mathbf{e_B}$ as $\mathbf{s_A}\cdot\mathbf{e_B}$:

$|\mathbf{s_A}\cdot\mathbf{e_B} + e'_A + \mathbf{s_B}\cdot\mathbf{e_A} + e'_B| \leq |\mathbf{s_A}\cdot\mathbf{e_B}| + |e'_A| + |\mathbf{s_B}\cdot\mathbf{e_A}| + |e'_B|$.

Now, for Euclidean norms, Cauchy-Schwarz says $|\mathbf{a\cdot b}| \leq |\mathbf{a}|\cdot |\mathbf{b}|$, so we have, for example, $|\mathbf{s_A}\cdot\mathbf{e_B}| \leq |\mathbf{s_A}| \cdot |\mathbf{e_B}| \leq  (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n})$, the last inequality coming from Lemma 1.

Let's tackle $e'_A$ and $e'_B$. I could sample a vector $\mathbf{e'}$ from $\mathcal{D_{\mathbb{Z^n},\alpha q}}$ and Lemma 1 would apply to it; if $e'_A$ is a member of $\mathbf{e'}$, it is certainly smaller than $||\mathbf{e'}||$:

$|e'_A| \leq ||\mathbf{e'_A}|| \leq \alpha q \sqrt{n} \leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n})$. Same for $e'_B$.

Thus I have four terms, all $\leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n})$. Multiply back in that $2$ and you have the result.

Edit

They do a similar procedure later on in Section 4, and explicitly write out norms, for future reference.


Use Microsoft word and digital certificates to notarize documents (USA)

I feel like the JPEG seal is the problem. why is it being used? the digital signature should be more than sufficient. the seal does nothing but complicate the whole process.

But lets assume you MUST add the seal. One solution is to keep them segregated. instead of appending the seal to the document, have both parties digitally sign the document. then afterwards have the notary edit the seal with the documents name and author name and date. then he can digitally sign that as well. sending both of these documents together as separate entities.

EDIT: on a side note, most notaries for any documents that I have used have a sort of cover letter they draft up stating they have indeed seen and verified the documents. This perhaps is the best place to put that seal. Since it already has the document name date and notarized author. A natural fit for the segregation method I stated earlier.


Does it make any difference when salting database passwords with Random vs SecureRandom?

I am telepathically inferring you're talking about Java here, in which:

Random is a linear congruential generator with a 48-bit seed and no security properties whatsoever, and
SecureRandom is some cryptographic algorithm whose documentation (archived 2019-03-23) is unclear about its security properties, with broken links and archaic references, but of which one might reasonably expect the following two standard properties:

indistinguishability from uniform random (or prediction resistance, next bit test): to anyone who does not know the seed, the output is indistinguishable from a uniform random string of bits; i.e., prior outputs do not help to predict subsequent outputs
key erasure (or backtracking resistance, or forward secrecy): even if the state is compromised, it does not help to recover past outputs

[edit: I just looked closer (archived 2019-02-22) and discovered that the one algorithm supported by SecureRandom does not, in fact, do key erasure at all—it just uses SHA-1 in ‘CTR mode’.  Nice, Java.]

In general, you should use SecureRandom by default unless you have measured an overwhelming performance concern arising from it.  In general, you might get in cryptographic trouble just from the use of Random.  In general, you will never get in as much cryptographic trouble just from the use of SecureRandom, unless loads of other people are in much deeper trouble already.  If you find yourself spending time wondering which one to use, but you haven't measured a performance impact, you are wasting time wondering and you should just use SecureRandom.

OK, you measured a performance impact?  If not, stop reading and go back to the previous paragraph.

What are the security requirements for salts in password hashes?

The purpose of the salt is to thwart multi-target attacks like rainbow tables that save effort by attacking many instances of the same hash simultaneously—that is, the same unsalted hash.  For example, if an adversary is trying to find one password $p_i$ given $\operatorname{MD5}(p_1), \operatorname{MD5}(p_2), \dots, \operatorname{MD5}(p_n)$, they can use a multi-target attack which costs only $2^{128}/n$ and which can run in time $2^{128}/n^3$ if parallelized $n^2$ ways, even though as a 128-bit hash function you might naively expect the cost of an attack to be about $2^{128}$ in the best case that the $p_i$ were chosen by processes with 128 bits of min-entropy themselves.

Using an independent function for each password, as in $(s_i, \operatorname{MD5}(s_i \mathbin\| p_i))$ where each $s_i$ is a distinct salt, thwarts this attack.*  Of course, it thwarts the attack only if everyone on the planet is using an independent function for every password; in other words, if anyone else uses the same salt, then a multi-target attack can still save costs for an adversary.

According to the documentation (archived 2019-04-01), Random is a linear congruential generator with a 48-bit seed.  This seed is so small that even if it were chosen uniformly at random, collisions would be expected after a few million choices, leading to identical salts produced for every output.  It is unclear how the seeds are chosen; it would not be surprising if it were chosen from the time of day and/or the process id, in which case similar applications run at similar times might choose the same seed.

There are cryptosystems where public values like initialization vectors absolutely must be unpredictable in advance, like AES-CBC.  Is it the end of the world to use Random for password hash salts?  No, but it would suggest that you're a too-cool-for-crypto hipster with reckless disregard for user security and/or your auditors' time, but with ample free time of your own to spend dying on hills on the internet.  You're not that hipster, are you?

N.B.:  You should not use MD5 for anything.  For password hashes, you should use argon2, which has exactly the same considerations for salts, but unlike MD5 can use your available resources—time before user expects a response, available RAM, and additional CPU cores—to raise the attacker's costs.

* Using a secret function like $\operatorname{HMAC-MD5}_k$ for a secret key $k$ instead of $\operatorname{MD5}$ can also help—here we sometimes affectionately call $k$ a pepper—but only if there is a meaningful security boundary between the password hash storage and the password hash verification; that's a story for another day.


Is the term "Elliptic Curve Discrete Logarithm Problem" a misnomer?

CodesInChaos has it correct, however since you're just learning, I think I'll lay it out rather explicitly.

When we have an abstract group, there are two ways of expressing operations in the group.

One way is writing the operation as if it were the multiplication operation, for example, if we apply the operation to elements $A$ and $B$ and the result is the element $C$, we would write this as $AB = C$, or alternatively (if we want to emphasize the operation) $A \cdot B = C$.  In addition, the act of performing the operation on $n$ copies of object $A$ is written as
$$\underbrace{A \cdot A \cdot ... \cdot A}_\text{n copies} = A^n$$
When we write a group in this format, we call it a "multiplicative group".

The other way to write the operation would be to write it as if it were the addition operation.  In our example where we apply the operation to elements $A$ and $B$ resulting in $C$, this gets expressed as $A+B=C$.  The act of performing the operation on $n$ copies of the object $A$ is written as
$$\underbrace{A + A + ... + A}_\text{n copies} = nA$$
When we write a group in this format, we call it an "additive group".

Now, the only difference between a multiplicative group and an additive group is how we choose to write it.  For some groups, we traditionally write them in multiplicative form, for other groups, we generally write them in additive form.

One such group that always gets written in multiplicative form is that group $\mathbb{Z}_p^*$, which can be viewed as a set of integers between 1 and $p-1$ where the group operation is $(A \times B) \bmod p$.  This is the first group where the problem "Given $G$ and $H$, it is difficult to find $n$ with $H = G^n$" was exploited cryptographically; because the analogous function in the Reals is called logarithm, as $n = \log_G H$, this problem was dubbed as the "discrete logarithm problem".

Now, we step to Elliptic Curve Groups; those groups are almost always written additively (I have seen it written multiplicatively, but it's rare).  So, the analogous problem is "given points $G$ and $H$, find $n$ with $H = nG$".  Now, if someone wanted to be completely consistent with the terminology, the obvious notational way to express this would be to write $n = H/G$ or this is a "point division problem".  This would appear to make sense, however no one ever uses this terminology.  Instead, everyone calls this the ECDLP problem, even though everything else done with elliptic cures is written additively.  This is inconsistent, but language is like that; if you want other people to understand you, you use the terminology that everyone else does.


Is it necessary to stretch/derive an AES key when I already have enough bytes from a 'cryptographically secure RNG'?

You're right. Unless the software is doing something very peculiar, which should be very apparent when reading the code and documentation, and I can't imagine what it could be, the salt generation and the application of PBKDF2 are unnecessary.

If you have 32 bytes from a cryptographically secure random generator, you can use these 32 bytes as an AES-256 key. A CSRNG is as good as it gets: it's uniformly random and non-guessable.

You would use a (“plain”, non-stretching) key derivation to obtain a key deterministically from some inputs which are not necessarily uniformly random, but have sufficient entropy. A typical case that requires a key derivation step is the output of a Diffie-Hellman key exchange algorithm: it needs to be deterministic so that both parties calculate the same secret key, and you can't use the output of the DH computation directly because it's a number with some mathematical properties and so it isn't uniformly distributed. Another case that requires key derivation is when you have some secret material of limited length (but enough so that it can't be found by brute force: at least 128 bits), and you want to construct multiple keys whose total length is more than the secret material.

A CSRNG takes an entropy source as input and applies a pseudorandom computation (CSPRNG: cryptographically secure pseudo-random number generator) to produce random output. A key derivation function (KDF) takes input and applies a pseudorandom computation to produce pseudorandom output. A CSPRNG and a key derivation function have fairly similar security properties: as long as the adversary doesn't see the secret input, even if the adversary sees part of the output, they can't figure out anything about the part of the output that wasn't given to them. It wouldn't make sense to just chain them. It can make sense to chain them in combination with some third thing, for example using a CSRNG to generate a public salt and a KDF to combine this public salt with a secret key to generate another secret key, or using a KDF to generate a seed for a CSRNG which then gets used by a subsystem that doesn't have access to the original KDF anymore.

A stretching key derivation function (such as PBKDF2) is useful when the input has low entropy. “Low entropy” means that the input is plausibly guessable through brute force. A CSRNG output has maximal entropy for its length, and 128 bits (16 bytes) is enough to put it well outside the realm of brute force guesses. (Quantum cryptanalysis might raise the bar to 256 bits in the future.) Key stretching is used for secrets that are short enough to be memorable, typically passwords or passphrases. The only reason why you'd need to apply key stretching to the output of a CSRNG is if this output was deliberately kept short to be memorized as a password (presumably in a form encoded suitably for humans, such as a string of printable characters or a list of words).

Taking 64 bytes from a CSRNG and passing them through PBKDF2 doesn't make any sense. Just use the CSRNG output as a key. The use of PBKDF2 isn't a direct security risk, but it hurts performance and it increases the attack surface. Beware that if the current software does this, it indicates that the authors didn't understand what they were doing and there may be other problems that are actually security flaws.


Correlation power analysis attack on Camellia

Camellia is 128-bit  Feistel block cipher and 128/192/256 key. The sbox is 8-bit register, hence there are 8 cells in F function . The correlation power analysis depended on hamming weight. Steps to be taken:

1. Build a matrix of all possible keys (256) on each cell, the matrix
size is 8*256=2048, then calculate the hamming weight ( I guess for
hardware implementation , the model is hamming distance)
2.  Collect power consumption traces during encryption process, the number of traces differ from experiment to other but usually range
up to 10000 traces.
3.   Calculate the correlation between the model and traces.
4.  the best coefficient indicates the possible correct key.
5.  To obtain the 128 key , you need to do the correlation for two rounds (first and second) since the sub key size is 64 bit , the
same applies for 192 (three rounds) and 256 (four rounds)

To answer your questions:

1.  Is this algorithm resilient to CPA ?

Non-masked implementation of cipher can be attacked by correlation power analysis.The implementation of the cipher plays a factor, Camellia has 4 8-bit sboxes , the cost of countermeasures implementation against CPA is high but securing against CPA , it does not mean it is secure against other types of Side channel attacks.

2.   If it does not, which correlation should I search for ? this algorithm is not intuitive like AES .

If I understand what you meants , the correlation is pearson , I think this
link might help you.


How to calculate active s-boxes from branch number?

Khazad has an $8\times 8$ MDS matrix $A$ used as the diffusion layer. The augmented matrix $[I|A]$ generates a $[n,k,d]=[16,8,9]$ MDS code over $GF(2^8).$ The implications are:

The minimum number of active Sboxes, i.e., the minimum branch number across 2 rounds is $9,$ the minimum weight of the MDS code.
MDS codes have a fully known weight distribution, so the full branch number distribution is also known, assuming a uniform input distribution into the Sboxes.

See here for the weight distribution. Briefly,
$A_i$ denotes number of codewords of weight $i$, thus also the number of occurrences of branch number $i.$ In this case
$A_0=1,$ and $A_i=0,$ for $1\leq i \leq d-1.$ The other nonzero weights are
$$
A_i= \binom{n}{i} \sum_{j=0}^{i-d} (-1)^{j}\binom{i}{j} \left( q^{i+1-d-j}-1\right),
$$
for $d\leq i \leq n.$

Here $q=2^8, d=9.$


Optimal compression ratio in compression function

You said ‘hash’, but you didn't say what properties you wanted.  For example, the ChaCha core $C\colon \{0,1\}^{256} \times \{0,1\}^{128} \to \{0,1\}^{512}$ is called a hash function and used in CTR mode to make a one-time pad $C(k, 0) \mathbin\| C(k, 1) \mathbin\| \cdots$ to encrypt a message under key $k$.  Poly1305 is called a universal hash function family and is used to make a one-time authenticator for a message under a single-use secret key, but is useless for encrypting messages.
Are you talking about building a variable-size collision-/preimage-/second-preimage-resistant unkeyed function $H\colon \{0,1\}^* \to \{0,1\}^n$ out of a fixed-size function $f\colon \{0,1\}^a \to \{0,1\}^b$?  That's one of the outmoded definitions of ‘hash function’ in cryptography—outmoded because there are other properties like (enhanced) target collision resistance, prefix-PRF, etc., that turn out to be at least as important in protocol design, and are sometimes summarized as indifferentiability from a random oracle.  And if that is what you're looking for, it's hard to imagine how $d$ could turn out to be anything other than a nonnegative integer.
But assuming that is what you're looking for, here are some comments on common values of $a$, $b$, and $d$:
The design principle of SHA-256 is to iterate a block cipher $E_k$ in Davies–Meyer form:

Break the padded message into 512-bit chunks $m_0, m_1, \dots, m_{\ell - 1}$.
Let $h_{-1} = \mathrm{IV}$ be the standard 256-bit initialization vector.
Compute $h_i = E_{m_i}(h_{i - 1}) \oplus h_{i - 1}$.
Reveal $h_{\ell - 1}$ as the hash.

Here a = 768 and b = 256, so d = 512.
The design principle of BLAKE2 is similar, except it uses a tweakable block cipher $E_{k,t}(m)$ instead of an ordinary block cipher, in HAIFA form, which fixes some potential pathologies of naive Davies–Meyer or Merkle–Damgård form, so that it goes beyond collision and second-preimage-resistance to simulate a random oracle in other dimensions.
The design principle of SHA3-256 is to iterate a fixed permutation $\pi$ in sponge form:

Break the padded message into 1088-bit chunks $m_0, m_1, \dots, m_{\ell - 1}$.
Let $h_{-1} = 0^{1600}$.
Compute $h_i = \pi(h_{i - 1} \oplus (m_i \mathbin\| 0^{512}))$.
Reveal the first 256 bits of $\pi(h_{\ell - 1})$ as the hash.

Here a = 2688 and b = 1600, so d = 1088.
Which is better—HAIFA or sponge?  It depends on whom you ask!  There's no evidence to suspect any weakness in BLAKE2 or SHA-3.  Maybe it's easier to make something faster out of HAIFA—certainly BLAKE2 is much faster than SHA-3.  Maybe it's easier to prove security reductions of compositions to primitives when the primitive is a single fixed permutation instead of a PRF made out of a PRP.
Note that in all of these compositions one of the basic components is a permutation—$E_k$, $E_{k,t}$, or $\pi$—but the fact that the component is reversible doesn't mean there's any security problem in the composition.  Knowing the first 256 bits of $\pi(s)$ for a random permutation $\pi\colon \{0,1\}^{1600} \to \{0,1\}^{1600}$ doesn't help you to guess a 256-bit secret $s$: you'd have to fill in 1344 bits you don't know, which is unimaginably harder than just guessing $s$ in the first place!


Product of Negligible and Non-Negligible Functions

I'm wondering if it's possible for the product of two non-negligible functions to be a negligible function?

Yes, actually; here is an example:
Consider the two functions:
$$P(x) = 1 \text{ if x is an even integer}, 0 \text{ otherwise}$$
$$Q(x) = 1 \text{ if x is an odd integer}, 0 \text{ otherwise}$$
Both $P$ and $Q$ are nonnegligible functions.
However $P(x)Q(x) = 0$, which is (trivially) a negligible function.


setting the MGF hash to a different value other than the regular hash with openssl for PSS signatures

Meta: since this is about using a tool not the underlying algorithm/math AIUI should be security.SE instead. If anyone can and wants to migrate feel free.

Per 1.0.2 source, -sigopt rsa_mgf1_md:name where name is the name of a hash available to EVP_getdigestbyname -- that is, implemented and not #if'ed out by default (MD2) nor manually.

For FIPS mode if relevant, I think you can set a non-FIPS hash but then the operation using it will fail, but I don't have a FIPS build set up to test.


Why do we get the following equation in case of a One Time Pad?

I'm not fully sure if the equation is correct, as I think $P[E_{k_i}(m_i)=c_i]=1$, as the encryption always produces a cipher text (which is what you formulated I think, as there's no definition of $c_i$).

If you change the $c_i$ to $c$ however you'd calculate the average probability that any message-key-pair encrypts to $c$.

I didn't take part in such a course yet, but this looks right as for the OTP the probability that a certain message encrypts to a certain ciphertext under a certain key is basically the same as the probability that any message using any key encrypts to this specific ciphertext. So this would mean that you can't derive any relations between ciphertext and plaintext because any plaintext-key pair could match your ciphertext. This sounds pretty much like perfect secrecy and hence like an OTP.

I hope this helps you.


As you suggest, you can speedup the exponentiation using pre-computed values. However, you will face the following problems:

the table with the precomputed values can become rather large, and
the table lookup is in general not constant time.

An example of how these problems can be addressed can be found in the Ed25519 implementation of Bernstein et al.; details are discussed on page 13 of their paper. They use a Brickell exponentiation with a standard trick to reduce the size of the table by 50%, and they use constant-time table lookup (where all possible values are loaded from memory and then combined with logical operations).

Note that because the cost of constant time table lookup is proportional to the size of the table, it is not efficient to represent the exponent as a series of larger chunks (e.g. 16bit->65536 elements in the table). It is more efficient to represent the exponent as a series of smaller chunks (e.g. 4bit).


If $((p-1)*(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)*(q-1)) = 1$

Is this true?

I'd generalize it, and replace $(p-1)(q-1)$ with $X$; that is, if $X-1$ is divisible by $e$, that is, if $X-1 = k \times e$ for some integer $k$, then $\gcd(e, X) = 1$. Is this true?  If it is, then your original statement is also true (because if it holds for all $X, e$, it also holds for all $X$ that is of the form $(p-1)(q-1)$ and for all odd $e$.).
As a further hint, we can also observe that $\gcd(e, X) = \gcd(e, X \bmod e)$ (that's the central observation that makes the Euclidean method for evaluating $\gcd$ work).
With that, it should be fairly straight-forward to proceed...


Is the tag in a MAC scheme a fixed size?

A MAC is a type of function, that returns an authenticator given a message and a secret.
The output length is a property of a function, not a constant for all MACs.
With constructions such as HMAC, the output length is directly dependent on the underlying hash function. Other constructions such as KMAC can produce an arbitrary long output.
And no matter what the output size is, an application can always truncate it if needed.
Of course, the shorter the MAC is, the less secure it becomes. If a MAC is used in an online protocol, and an adversary has very limited time and allowed attempts, forgery may not be practical even with a short MAC. If offline attacks are practical, you’d better size the MAC for 128 bit security. The maximum length of a message also plays a role. The shorter the messages are, the more difficult forgery is.
So, there’s no fixed size for MACs. It depends on the actual functions and in what context they are used.


Can cycle finding techniques reduce the memory usage of the MitM attack against 2DES and 3DES?

Let $b$ be the width of $E^{(1)}_{K_1}(p)$ and $D^{(2)}_{K_2}(p)$. For the block cipher DES that would be $b=64$, with $n=56$. I'll assume $n+4<b<2n-4$, which holds in this case and simplifies some approximations.

Let $w$ be the width of the function iterated. The question as worded proposes $w=n+1=57$, and thus finds collisions fast, but with $w<b$ only a fraction (like $2^{w-b}=2^{-7}$ with $w<b-4$) are such that they reveal $K_1$ and $K_2$ such that $c=E^{(2)}_{K_2}(E^{(1)}_{K_1}(p))$.

Let's first increase $w$ from $n+1=57$ to $w=b=64$. The collision condition is now precisely such that, when the discriminator bits are different, $c=E^{(2)}_{K_2}(E^{(1)}_{K_1}(p))$ where $K_1$ and $K_2$ are derived from the colliding inputs, and the common output is $E^{(1)}_{K_1}(p)=D^{(2)}_{K_2}(c)$. We expect a find of $(K_1,K_2)$ to have odds about $2^{b-2n}=2^{-48}$ to be the correct one, and that's determined with negligible extra cost, just as in the normal MitM.

I see no reason why the proposed method would not find collision with a usable discriminator bit as expected for a random function, at an expected cost of about $2^{w/2+1}$ evaluations of the function (only a little more with cycle-finding using distinguished points, given the modest $w$; I neglect that). So the expected cost in DES operations is like $2^{2n-w/2+1}=2^{81}$.

Using little RAM by the above technique thus comes at the price of making about $2^{n-w/2+0.4}=2^{24.4}$ times more evaluations of $E^{(1)}$ or $D^{(2)}$ than in basic MitM, which is expected to perform about $2^{n+0.6}$ evaluations (I'm discounting cycle-finding overhead).

Even though, this is an improvement over the obvious time-memory tradeoff for MitM on a memory-bound system, where we split the problem into (at most) $2^r$ runs with $r$ fixed bits in $K_1$, each using all available RAM for $2^{n-r}$ entries, for an expected cost dominated (for $r>4$) by $2^{n+r-1}$ evaluations of $D^{(2)}$ and searches of that in the table. With $r=n-w/2+2=26$, the two techniques make the same $2^{2n-w/2+1}=2^{81}$ number of DES operations, but the MitM makes as many accesses in $2^{n-r}=2^{30}$ values, while cycle-finding using distinguished points makes much less memory accesses (which are more costly than a DES is an ASIC), and requires significantly less memory.

The above calculation suggests to increase the width $w$ of the function we search collisions for, above $w=b$ considered above, up to something closer to $2n$ (this is possible if we have several plaintext-ciphertext pairs, but beware that when $w$ is not a multiple of the native block size we are not sure that the candidate $(K_1,K_2)$ found by collision really works for the full block forming $p$ and $c$ that we used, and when $w$ goes from $b$ to $b+1$ we abruptly need two block cipher operations per evaluation of the iterated function, rather than one; independently, the above cost calculations become invalid for $w$ approaching $2n$).

With that change, the proposed method seems closer to what's studied in section 5.3 on MitM in Paul C. van Oorschot and Michael J. Wiener: Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1), which seems to use $w=1.5b$ when applied to 2DES (section 6.3); that refines their earlier Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude (in proceedings of Crypto 1996).

So yes, cycle-finding techniques can reduce the memory usage (size, and number of accesses) of the MitM attack against 2DES. And it does so with a lesser increase of the number of cipher operations (which has an influence on time) than plain partitioning of the problem, which keeps the product $\;$memory size × cipher operations$\;$ about constant.

It remains that the expected number of cipher operations rises significantly above $2^{n+1}$ in the best (thus complex) improvements in the literature; it seems they are far from achieving what's quantitatively envisioned in this comment (much more RAM and/or DES operations is needed). The advantages (pointed by that comment) of cycle-finding with distinguished points hold:

Thanks to distinguished points, most DES computations need no memory accesses; this is the biggest cost saver when DES is implemented in ASIC.
Because collision detection is made only on distinguished points, the RAM requirement is much lower;
There is little communication required compared to basic MitM distributed on multiple nodes with memory (but more than for the obvious time-memory tradeoff of MitM, where the $2^r$ jobs are entirely independent, at the cost of computing all $D^{(2)}_{K_2}(c)$ in each job).

I wish I had a graph visualizing, on a $\log_2$ scale, the time complexity (in DES operations, and separately memory searches) and memory size achieved by the most obvious time-memory trade-off for MitM, and cycle-finding with a few parameterizations.


Creating a message authentication scheme

Doing this would not be secure.

If you truncate the SHA-1 to 64 bits before encryption, then anyone can find a collision in about $2^{32}$ tries (taking minutes on a desktop CPU), and by finding the encryption of one message hash also learn the other. Even a second preimage attack may be feasible.
If you use ECB mode to encrypt a longer hash, then the attacker can attack it "piece by piece", finding one hash value that collides with several block-aligned parts of earlier hashes. This is more difficult than finding a 64-bit collision, but much easier than finding a full collision.

The best you could hope for would be somewhere between 60- and 70-bit security (collision search on full SHA-1), but that would require better encryption/MAC on the hash, and would be more complex than simply implementing HMAC or CBC-MAC.

If the dongle can do (semi-)arbitrary things with 3DES and the PC can do arbitrary things, then I would recommend:

Using a longer hash, e.g. SHA-256, on the PC: $h = H(m)$
Using a block cipher-based MAC on the device on the hash: $t = M(k, h)$.

That gives you the weaker of:

the collision resistance of the hash (128 bits for SHA-256) and
the security of the MAC.

The block cipher based MAC could be e.g. CBC-MAC. That is simple enough and with SHA-256 you would only need to process four blocks on the device itself.


Alice will have computed

$y_{i} = m_{i}^{d} \,\mbox{mod}\, n$

and Bob will compute

$d_{i} = y_{i}^{e} \,\mbox{mod}\, n$

If Bob finds $d_{i} == m_{i}$ for every $i$, he will probably conclude that they were indeed signed by Alice. His conclusion however, is very unwise, since for this special case where $e=3$, the numbers $y_{i}$ can be easily forged by an attacker even if he does not possess the private key $d$ of Alice.


One of the simplest textbook example of steganography in a bitmapped image (as opposed to formats providing lossy compression such as JPEG), is low-order-bit steganography. In such system, the low-order bits of the pixel components (gray-scale or RVB or CYMK levels, typically stored as a binary number of 8 bits) are modified in some way to hold information; this is hardly visible to the eye (especially on natural images with some degree of noise).

In some systems, the hidden information is the low-order bits of the pixel components. In that case, it is often possible to conclude that the image contains a steganographic message (and get at it, unless it is encrypted before insertion). Detection is based on the fact that in natural images, the low-order bits are correlated with nearby bits (that is, the higher-order bits of the same pixel component, bits of any other color components of that pixel, and bits defining adjacent pixels). The stego replacing the low-order bits removes this correlation, and instead it is seen low-order bits exhibiting the statistical characteristics of those in the payload if uncompressed and unencrypted; or seemingly close to uniformly random and independent otherwise.

But there can be other ways, including XOR-ing the low-order bits of the base image with the hidden information, as in a stream cipher. In that case, we (and the intended receiver) need some information about the low-order bits in the base image. Possibilities include

somewhat get hold of the base image (that would typically apply to the receiver);
exploit some known/guessed/assumed characteristic of the low-order bits in the base image (like their aforementioned correlation with nearby bits).

Worth considering: perhaps few low-order bits are changed; this makes conclusively proving the use of stego much more difficult, but worsens the already large bandwidth requirement.

On the particular problem: we are given MOVIE.BMP (2764854 bytes), a BMP (short for bitmap) file on a web page with a message hinting at stego in the image. Webmasters almost never uses BMP files that large, especially for an image promoting a movie, where JPEG easily saves an other of magnitude on bandwidth usage. All this prompts at steganography on low-order bit, or similar.

The 2764854 bytes consists of a 54-byte header (14-byte BMP header and 40-byte BITMAPINFOHEADER) followed by 1280x720 RVB components of 3 bytes each. There is no extra data (a primitive form of steganography is to append the payload at the end of a file, where rendering programs typically ignore it). The header is unremarkable, except perhaps that the 8 bytes for the horizontal and vertical resolution are zero.

Since the image is promoting a movie, it is worth feeding it to a search engine accepting images, in hope to locate the base image used. We want a visually very similar image, such that when some common program saves it (or a crop/resize thereof) as bitmap, we get something extremely close to the bitmap in MOVIE.BMP. I tried a few of the first hits of two search engines, and two programs: a paint program bundled with Windows, and IrfanView. I used primarily the later, because it is the only of the two I found sometime leaving the horizontal and vertical resolution fields at zero; and also because it can save images into a simple text format (PPM-text) which eases comparison and analysis.

I quickly narrowed down on maxresdefault.jpg (118533 bytes) as remarkably close to the original: after conversion to BMP format using IrfanView, a file compare (with fc /b maxresdefault.bmp MOVIE.BMP) yields only 955 different bytes (list by the OP), and the differences all are in low-order bits. By contrast, the other program yields 88119 different bytes, with differences not limited to the low-order bit (lots of ±1 that change more than the low-order bit, and many ±2; that could be due to minor differences in the JPEG decompression, like using the lower precision arithmetic of SIMD instructions versus the FPU). Some other online images I tried, like IMG_0825.jpg (128356 bytes), yield the exact same 955 differences (ignoring the resolution field); others (including conversions of MOVIE.BMP to JPEG) give overwhelmingly more differences.

I so far conclude that

with good certainty, MOVIE.BMP was prepared from a JPEG image yielding the same pixel data as maxresdefault.jpg does;
the tool used for the JPEG decompression of that file uses algorithms yielding very close to the same result as the algorithms used by IrfanView, hopefully exactly the same;
likely, after the JPEG decompression, at most 955 low-order bits (and hopefully exactly that much) have been altered;
accidental variants in JPEG decompression code seem more likely to yield differences of ±1, then only ⊕1 as observed. That tends to comfort that indeed there is stego involved (but is far from proof).

I tried just a few more things, but basically I'm stuck:

In the (conjectured) base image maxresdefault.bmp, 1323359 out of 2764800 low-order bits are set (47.865%). 439 out of 955 bits flipped in MOVIE.BMP were previously set (46.0%), that's not a significant difference (a Pearson chi-squared test gives a two-tailed p-value 0.24).
I found no pattern in the addresses, pixel coordinates, or RGB planes where the flips occur.


How to securely store data? / How to securely encrypt a file?

Ask yourself if you even can securely store the user's data.
This includes to check that the user won't get sniffed by the root / admin
user.Also make sure that your implementation is secure.Employ
standard code review mechanisms, make sure that your implementation has
countermeasures against timing attacks (like against AES).Also make sure
that you use appropriate data types.Using a byte* allocated using malloc
usually isn't very secure. If your library provides mechanism for data
storage, use them! Your OS may also provide means to protect data
while in memory, for example the data protection API in Windows only relies
on the current user and can be used to conceal sensible keys in memory.
Reading Schneier's Cryptography Engineering may be a very good idea for you,
to ensure you don't have side-channel leaks.
Ask yourself what you can use to authenticate the user. The
options are (it is explicitely allowed and recommended to combine as
many of them as convenience and availability allow):

Passwords: Your user can supply a password or a passphrase. Do
not limit him in length of this, to allow him to use good and long
passphrases. This usually is a good choice, as it requires the user to know
something and this hence can not be lost like an usb-stick.
Keyfiles: Allow the user to provide keyfiles. These files may
look arbitrary, but should be rare. Allow the user to use the
(cryptographical) random number generator of your application to generate
strong keyfiles (of 64 bytes length or more). Examples for keyfiles are rare documents, like personal (word/) text documents or on-purpose generated files just containing random data (created using the application's random number generator).
Custom Hardware: If you are deploying in large scale you can force
the user to be required to use a tamper-resistand hardware device. This
device should support symmetric encryption with a device-held key.
User's Hardware: Allow the user to use his PKCS#11 or similar
smartcard or cryptographic token, which provides public key encryption, to
be used. Also allow the user to protect the key using the TPM (if
available)
OS data: Allow the user to make the decryption dependant on
something stored in the current OS, like the user credentials or OS
provided secure key storage.

Inspect what algorithms you have at your disposal. You'll need (at
worst) five classes of algorithms: Password-based key derivation functions,
encryption algorithms, modes of operation, message authentication codes and
cryptographically secure random number generators.At the time of
writing the following algorithms are recommended (in descending order). If
functionality is already provided more top-level don't use it.

Cryptographically secure random number generators:

Fortuna
An approved algorithm. This may either be the result of a
contest or some approved algorithm by some trusted institute (e.g. ANSSI,
NIST, BSI, ...). Avoid algorithms with "provable" security where the
institute provides the parameters, these parameters may be chosen on
purpose to get back-door access. For seeding use the cryptographically
secure random number generator of your OS. They are usually a bit
hidden.
Some "weak" standard approach. (i.e. run a blockcipher in CTR
mode and delete key and IV as soon as possible) Get the key and the IV
from the cryptographically secure random number generator of your OS.
They are usually a bit hidden.

Password based key derivation functions:

The winner of the PHC-competition. If there are multiple
winners, ask for the differences and use the one most suited for your needs.
scrypt
bcrypt
PBKDF2, using an efficient and secure hash function (on your
platform)
implement your own PBKDF2!

Ciphers:

The winner of the CAESAR-competition (2018+). If there are
multiple winners, ask for the differences and choose the appropriate one.
AES. Note: For data that needs to be confidential unti 2070 or
earlier, it is recommeded to use AES-128. In every else case use AES-192 or
AES-256.
ChaCha(preferred) or Salsa20.
One of the following three: Threefish, Serpent or Twofish
3DES with 3 keys. (needs 168 bits of keying material)

Modes of operation (this is obsolete for CAESAR-winners):

OCB (If the patent has expired)
GCM
EAX (preferred) or CCM
CTR, below this a message authentication code is required
(including)
One of the following: CFB or OFB
ECB, avoid at all cost, rather implement your own CTR!

Message authentication codes:

Poly-1305 using a standardized construction
HMAC, using a secure standardized hash function, preferably
SHA-3 or a member of the SHA-2 family. Encrypt the data first,
then authenticate the ciphertext!
implement your own HMAC!

Ask yourself on how to design the header. The header should contain:

The salt, a random 64 byte or more value that will be newly
chosen on each single creation of a new file. This will be fed into the
password-based key derivation function. The salt can be open, but may be
authenticated using the authentication mechanism.
The parameters for the password-based key derivation function.
These parameters need to be open. They should be chosen such that key
derivation needs approximiately 100ms to 1s on the target platform. A
value indicating the password based key derivation function used is
considered a parameter.
A nonce or an IV for the cipher / mode. This value should be chosen
at random and be stored openly.
The remainder of the header should be encrypted and
authenticated.The before-mentioned nonce/IV should be used along with
the key derived from the password using the password-based key derivation
function and the stored salt and parameters.
The master-keys for the data part of the file. These should be
random and maximal length. This is part of the encrypted part of the
header
A nonce / IV for the data part. This value should be random. This
value can (and should) be part of the encrypted part of the header.

The actual data is now encrypted using the above chosen
cipher/mode/authentication triple and the key/IV/nonce pair of the encrypted
part of the header.

Now some question that may arise:

Is it worth it to use multiple-encryption?No.The benefit
by double encryption is only 1-bit due to the meet-in-the-middle attack.
Streamciphers may be combined easier, but it is absolutely unneccessary as
all ciphers are unbreakable for the forseeable future (50 years+)
What authentication methods should I use?As many as possible,
but at least passwordYou need to have a very good reason not to use
passwords because everything else can be attacked with admin rights or can
be stolen.
You didn't mention the other four authentication methods in the header
part, how should I incorporate them?

Keyfiles: Assume that each keyfile has low entropy. That being
said, you can't really do alot against it. Derive a key from every keyfile
using some digest-expansion function and your favorite secure hash function
(SHA-2/3) and construct a big XOR consisting of all file's hashes and the
user's password. This would look like this: $Key = PBKDF(PW) \oplus H
(File_1) \oplus H(File_2) \oplus ...$, where $\oplus$ denotes bitwise XOR.
Custom Hardware: At the creation of the file let the device
generate a symmetric key that will be kept inside the device. Perform
everything up to the keyfile / password level (see directly above point) and
then send this to the device for encryption. The key being used doesn't have
to be unique for each file. It is suggest that one key is being used for all
files. It is also possible to add an identifier to the file to identify the
associated hardware key.
User's Hardware: Let the device generate an OpenPGP key or a valid
S/MIME encryption certificate. Send the key being the result of the step
directly above (or 2 steps above) to the device for decryption. It will
decrypt it and return the key used to decrypt the master-keys.
OS data: If you have user credentials (maybe some random strings),
hash them and incorporate them at the same time in the same way as the
keyfiles. If your OS provides you secure storage (or your TPM does), store a
key and pass it in as "keyfile", thus hash it and incorporate it in the XOR
step.

Should I use an open source library or some closed-source library?Open-SourceChances are very good that there aren't any security
issues in well-known open-source libraries, whereas closed source puts
restriction in regard of when you can use it, usually you have to pay to be
able to use and you can't usually inspect the code on your own to make sure
it's secure.
Why did you use XOR to include keyfiles?(relates to question 3)Convenience.If
you don't use something that is commutative, like XOR, users will run into
problem because files have to be supplied in the exact same order. This gets
even harder if files are just re-named but their contents are kept. And from
a security perspective this is no less secure as one basically constructs a
"stream cipher" with the password based key derivation function output, the
hashes of the keyfiles and the other outputs (TPM, credentials,...) which is secure as
long as one source is secure.


Practical attack on an impractical implementation of Rijndael (AES?)

What you're describing is a ciphertext-only attack on AES.
No, there's no (known) ciphertext-only attack on AES.

  Condition one: We know none of the weaknesses and similar plain-texts
  in these two blocks, I just mentioned, how easily could we discover
  it?

By the lack of an transmitted IV, an attacker can learn whether the two messages are equal and that no IV was used. He can't learn anything else about the relationship of the plain texts without actually brute-forcing the key.

  Condition two: We know everything I just mentioned above, apart from which bit is flipped and what the two plain texts and the key
  (let's keep it simple and make the key, only 128 bits). Can we
  discover much here? How do we go about it?

You can't learn anything about the plain texts you didn't already know without brute-forcing the key.

  ...since we've used Rijndael, so grossly incorrectly...

We have indeed, yes, however more advanced defensive measures (i.e. use of authenticated encryption and IVs) mainly protects you from more advanced attack scenarios, where the attacker can actually decrypt and encrypt arbitrary data under the challenged key to distinguish unknown plain texts.
The scenario you give however is even safe when using ECB mode, which are you doing. ECB mode is safe as long as all plain texts (under a given key) are different, your messages are different so they are secure. The only thing you can tell by observing ECB encrypted data is whether one block equals the other.


Why is the DES s-box non-linear? Why does it make the cracking of the cipher more difficult?

It is of course possible to write DES or any block cipher as a system of non-linear equations involving the plaintext bits, the ciphertext bits, and the key bits, which hold with probability 1.  In principle, cracking the cipher would then merely involve collecting enough linearly independent equations (e.g. from a couple different known plaintexts) and then solving the system.

However, for any typical block cipher the equations are going to be extremely high degree, involving preposterous numbers of terms.  Solving very high degree systems of equations with large numbers of terms is actually a very hard problem.  Which is to say, while systems of linear equations can be solved in polynomial time (e.g. with Gauss-Jordan elimination), solving systems of non-linear equations is NP-Complete and can take longer than the expected life of the universe to solve.

It is possible to reduce the degree of the system by clever use of intermediate or temporary variables (which also increases the number of equations).  In fact, you can make the system as low degree as quadratic.  But as it turns out, that doesn't help much - solving multivariate quadratic systems is still NP-Complete (this is called the "MQ" problem).

There have been a few papers in recent decades concerning "algebraic cryptanalysis" which purport to solve the specific systems of equations involved in certain ciphers in polynomial time.  The idea with these papers is that while MQ in general is very hard, the specific systems of equations associated with some block ciphers might be sufficiently structured and sparse as to be efficiently solvable by some clever technique or another.  However, none of the techniques thus far been convincing to the cryptographic community.


How to select parameters for elliptic curves not found in standards (Hessian, Jacobi Intersection, Jacobi Quartic, etc)?

Weierstrass models can be converted to Hessian and Jacobi models (where such models exist) and in the days before Edwards curves were considered for ECC-based on implementation and side-channel properties.
The conversion to Jacobi model seems to be covered on mathoverflow.
To convert to Hessian, compute the $j$ invariant in $\mathbb F_p$ and then solve
$$j=\frac{c^3(c^3+216)}{(c^9-81c^6+2187c^3-19683)}$$
for $c\in\mathbb F_p$ (if the corresponding degree 9 polynomial has a root in $\mathbb F_p$). Your curve is then birationally equivalent to
$$X^3+Y^3+Z^3=cXYZ.$$
The Handbook of Elliptic and Hyperelliptic Curve Cryptography section 13.1.5.b shows how to explicitly calculate the binational maps if you want to find the image of specific points on the Hessian.
Thus you could take a standard Weierstrass model (e.g. NIST P256, Curve25519) and likely convert it to an alternative form if you so wished.


Determine RSA modulus from encryption oracle

We have $E(x) = x^{65537} - k \cdot n$, for some integer $k$ (which will be different for different values of $x$), and the unknown modulus $n$, and hence $x^{65537} - E(x)$ will always be a multiple of $n$.

So, compute:

$$\gcd( 2^{65537} - E(2), 3^{65537} - E(3) )$$

That will be $n$ multiplied by some integer which is likely to be small...

As similar method (that doesn't involve computing on such large integers, and even works even if you don't know $e$) is to compute:

$$\gcd( E(2)^2 - E(4), E(3)^2 - E(9) )$$

How this works should be fairly obvious...


Is the output of ISAAC still secure if I take the 32 bit number mod 8?

Well, let's start with that N mod 255 doesn't convert number to 8bit byte, but a byte without highest possible value, 255. You were looking for either N mod 256 or N and 255 (somewhat known assembly trick to do some divides faster).

Now, if your source is cryptographically sound, then any amount of bits cut from it will be sound (except might collide faster). However this isn't case when cutting a value that isn't power of 2! In your example, let's assume we are cutting 8-bit values (0-255) to your N mod 255 (0-254). In this case we will get 1-254 with same probability, but we are twice as likely to get 0, and we will never get 255. This obviously makes skew in your data, which is usually combated by cutting last values that would cause such skew (in my example, we would reject 255 and draw value again).

Of course all above holds in your specific case of ISAAC.


The main difference between CFB-1(CFB) and CFB-8 is the size of shifting.
To understand this -
$C_i = top_x(res_{i-1})\oplus P_i$
$res_0 = Enc_k(IV)$
$res_{i} = Enc_k(shift_x(res_{i-1}\oplus P_{i-1}))$
$P_i = top_x(res_{i-1})\oplus C_i$
Note that in order to decrypt $C_i$, you will need $P_{i-1}$ which can only be found by decrypting $C_{i-1}$. Hence, this cannot be parallelized.
Here $x$ is the shift size which is 1 in CFB-1 and 8 in CFB-8.


Is there any reason not to use Single-Key EM with AES and a constant key?

This is considered in §6 of Bogdanov et al., who go on to devise an alternative 2-round AES-based Even-Mansour cipher—$\text{AES}^2$. The problem is, essentially, that 1-round Even-Mansour is only secure up to $2^{n/2}$ blockcipher queries, for an $n$-bit block. Specifically, a collision between $\text{SEM}_K(P) \oplus P$ and $E(P) \oplus P$ immediately reveals $K$ (cf. §4.2 of Dunkelman-Keller-Shamir).

In general, you want an Even-Mansour cipher targeting $n$-bit security to have block size $2n$. This is the case with, e.g., Salsa20 and ChaCha's core functions, which are Even-Mansour-like, target 256-bit security, and work on 512-bit blocks. Several permutation-based CAESAR candidates, such as Prøst or Minalpher, work similarly.


Security of authenticated encryption modes GCM & CCM

Regarding GCM mode and the uniqueness of the nonce, it should be noted that EAX mode and OCB mode also require unique nonces. One potential problem EAX mode has, which neither GCM or CCM have, is that it is hard to implement it in such way that you can guarantee that the probability of nonce collisions is zero; only that it is acceptably low. OCB mode has been revised a number of times due to attacks such as this one against one of the earliest versions of OCB mode.

Regarding the security of CCM mode, this paper provides a security proof that explains the use of a CTR-encrypted CBC-MAC, with the conjecture that it is stronger against birthday attacks, compared to an unencrypted CBC-MAC. Hence, as a consequence CBC-MAC-then-CTR-Encrypt is actually stronger than (naive) CTR-Encrypt-then-CBC-MAC. The security of EtA versus AtE is consequently a rather complex matter. Generally it is probably best to regard dedicated proofs for a specific mode, as trumping proofs for the generic compositions. The security properties of CCM are well understood, so I doubt many security experts rule against it just because it is not EtA. A better argument against CCM is that it requires two AES operations per block, while other AE modes only require one.


Where did Martin Hellman acknowledge Ralph Merkle's contribution to public-key cryptography?

The source of that quote is:

Hellman, M. E. (2002). An overview of public key cryptography. IEEE Communications Magazine, 40(5), 42-49.

That paper is currently available here:

http://professor.unisinos.br/linds/teoinfo/hellman.pdf

Here's the complete quote:

  The system I called the ax1x2 system in this paper has since become
  known as Diffie-Hellman key exchange. While that system was first
  described in a paper by Diffie and me, it is a public key distribution
  system, a concept developed by Merkle, and hence should be called
  "Diffie-Hellman-Merkle key exchange" if names are to be associated
  with it. I hope this small pulpit might help in that endeavor to
  recognize Merkle's equal contribution to the invention of public key
  cryptography. Space does not permit an explanation of the quirk of
  fate that seems to have deprived Merkle of the credit he deserves, but
  a quirk it is.


Do I need different encryption and decryption algorithms for each key?

You can use the same ones (which is good, because otherwise you'd run out of them pretty fast). In fact, when a cipher allows you to choose a key, that's basically the same as giving you a new pair of encryption/decryption algorithms for every key.

Usually, when designing a system that uses symmetric encryption, a small set of ciphers are used. For example, the popular NaCl library only uses Salsa20+Poly1305 and AES-GCM.


QKD - Does BB84 Protocol rely on a prearranged code?

Bob and Alice then take the correct configurations, and they convert those to a prearranged code, which could be, as an example, that a correctly guessed diagonal detector is 0, and a correctly guessed rectilinear detector is 1. This way an encryption key will be composed.

I believe that's where you got it a bit off.  A correctly guessed rectilinear detection is not a consistent 1; instead, they might have the convention that a horizontal polarization is 0 and a vertical polarization is 1; similarly, a 45 degree polarization might be 0 and a 135 degree polarization might be 1.

  If Eve listens on the public channel, and gets both Bob's measurements...

Eve most certainly does not get Bob's measurements.  Bob does tell the world (well, Alice, but we can assume Eve is listening in) what he set his detector to (whether it was on the horizontal/vertical setting, or whether it was diagonal), but Bob certain doesn't tell what the detector actually measured.

So, suppose Alice sends a rectilinearly polarized photon to Bob.  If Bob set his detector to rectilinear, he'll tell that to Alice (after the photon has been detected); Alice will tell Bob that his guess was correct.  Alice knows what polarization she sent, and Bob knows he measured it correctly; they both know whether it was a horizontal photon (a 0), or a vertical photon (a 1).  Which is it?  Well, neither Alice or Bob are telling.  Someone in the middle can't be sure (unless they tried to measure it themselves; in that case, there's a chance that they got the polarization wrong when they re-emitted the photon, and hence will introduce detectable errors).

My opinion: I don't personally think this QKD stuff is actually practical (that is, it doesn't solve any problem that can't be better solved using more traditional methods), however it can work.


Blowfish: hex digits of pi used for s-boxes?

Yes.  Blowfish's S-boxes serve a similar purpose as AES's S-box.

The P-array is used as part of the key schedule, to make sure that each round is different (this helps prevents slide attacks and related-key attacks).

I recommend you read the official specification of Blowfish and Wikipedia's article on Blowfish for more about the design rationale for Blowfish.

The use of digits of pi is a "nothing up my sleeve" number.

Bruce Schneier (the algorithm designer) wanted to use a random number.  For Blowfish, it basically doesn't matter what number you use, if it is random.  However, Bruce also wanted everyone to be able to see that he didn't somehow pick some very special choice of number that introduces a trapdoor.  The digits of pi are basically random-looking, and cannot be controlled by Bruce.  Therefore, they make a standard choice for a "nothing up my sleeve" number.

See also How to choose constants in a cryptographic function? and Wikipedia on nothing up my sleeve numbers.


Can physical object hiding be quantified with entropy?

If you can quantify it with a probability distribution, yes—any probability distribution has an entropy.

Here's an analogy: Suppose a line of 256 people each flip a coin, and put it in their left hand if it comes up heads or their right hand if it comes up tails; then they close both hands in a fist.  If you can't watch them flipping and placing the coin in their hands, you can't tell which hand each person has the coin in.  The probability distribution on your state of knowledge about where the coins are has 256 bits of entropy.

The fact that it's people playing the which-hand game instead of a CPU storing a 256-bit key in a register in silicon is immaterial; entropy is a property of the probability distribution characterizing your state of knowledge.


Schnorr proof of group with unknown order (but the prover know the order)

You are not wrong. This indeed does not work. The way out typically in these situations is to use a proof over the integers. There is quite a bit of work around zero knowledge over groups of unknown order. See Section 3.7 of this thesis by Geoffroy Couteau. Since he is active here, let's hope he weighs in.


Does Mersenne Twister generate homogeneous numbers?

I think the Mersenne twister satisfies the requirement for homogeneity, since it produces numbers that are equally distributed (with 32-bit accuracy) in up to 623 dimensions.

But in a cryptography context, it could hardly be described as "uniform", because you only need to observe 624 outputs in order to predict all the following values with 100% accuracy.

I would recommend using a cryptographically secure PRNG such as AES-CTR instead. This should provide you with at least 100 MB of random data per second.


Single Ciphertext which can decrypt with multiple keys

One trivial solution is to let the message be:
$$M = (c_{\text{Alice}}, c_{\text{Bob}}) = (Enc_{k_{pub,A}}(m), Enc_{k_{pub,B}}(m))$$
Whether this counts as a "single message" or not is difficult to say.
Even if it does, it has the (unfortunate) property that Alice/Bob can't distinguish between:
$$M = (Enc_{k_{pub,A}}(m), Enc_{k_{pub,B}}(m)),\quad M' = (Enc_{k_{pub,A}}(m), Enc_{k_{pub,B}}(m'))$$
for $m'\neq m$ (so an adversary could "encrypt" something different to each of them, and provided the underlying scheme is CPA secure neither Alice nor Bob will be able to detect the adversarial behavior).

If you want to reduce the communication overhead of your scheme, hybrid encryption (encrypting the private key under both public keys) is likely the best choice, because after this initial "setup" phase you can switch to solely symmetric crypto under this new key.
Symmetric crypto tends to have a lower communication overhead than asymmetric crypto (the term to look at here is the "rate" of the encryption scheme).

That all being said, it's unclear precisely what your threat model is, and even hybrid encryption could easily allow for an adversary to encrypt different keys under Alice/Bob's public keys (so they initially disagree on their secret keys).
How this could be leveraged to mount a larger attack I don't know, but without fixing a particular threat model it's difficult to discuss what security would even mean.


Let $(m,c)$ be a couple of a plaintext and its ciphertext, and $k_0=\{k_{0,1},\ldots, k_{0,16}\}$ and $k_1=\{k_{1,1}, \ldots, k_{1,16} \}$ are the two unknowns subkeys ($k_0$ is in fact the master key).

Including the MixColumns step, then the encryption is
$$
c = \mathrm{MC}(\mathrm{SR}(\mathrm{SB}(m \oplus k_0))) \oplus k_1
$$

If we apply the inverse of MC and SR, then it becomes
$$
\mathrm{SR}^{-1}(\mathrm{MC}^{-1}(c)) = \mathrm{SB}(m \oplus k_0) \oplus \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(k_1))
$$
For ease of notation, let $c' = \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(c))$ and $k'_1 = \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(k_1))$, then we have
$$
c' = \mathrm{SB}(m \oplus k_0) \oplus k'_1
$$

Suppose you know two plaintexts $m_1$ and $m_2$ and their respective ciphertexts $c_1$ and $c_2$. To get the byte $k_{0,i}$, you make a guess $\tilde{k}_{0,i}$ and compute
$$
\tilde{k}'_{1,i} = c'_{1,i} \oplus \mathrm{SB}(m_{1,i} \oplus \tilde{k}_{0,i})
$$
You do the same by replacing with $m_2$ and $c'_2$ ($m_1$ and $m_2$ should differ on every bytes) and if the obtained values $\tilde{k}'_{1,i}$ coincide, then the guess might be correct and $\tilde{k}_{0,i}$ is a candidate for $k_{0,i}$.

Other plaintexts/ciphertexts can be used to filter the candidates until one remains for each byte, or concluding with an exhaustive search.


Since you referring to the LWE variant of Stehlé and Steinfeld, I will try to give you an answer to your question in that context. Note that these results are a mere extension of the correctness condition in Lemma 3.7 from the revised version of the paper [SS13]. As I said in the comments, at the end it all depends on the choice of parameters ($n, \alpha, q$, etc), and additionally, on the number of additions you want to support.

In this scheme, ciphertexts are of the form $c = h s + p e + m$, where $h$ is the public key, $s$ and $e$ are sampled from a Gaussian distribution, $p$ is a public parameter, and $m$ is the message. Public keys are of the form $h = p g f^{-1}$, where $f$ is the secret key, and $g$ a random polynomial.

The correctness condition for one ciphertext is $||f \cdot c_i ||_{\infty} \leq q/2$. We want to check the conditions for decrypting correctly a sum of $k$ ciphertexts:

$c_{sum} = \sum\limits^k_{i=1} c_i = \sum\limits^k_{i=1}(h s_i + p e_i + m_i)$

Since $f h = f (p g f^{-1}) = p g$, then $f \cdot c_i = f h s_i + p f e + f M = p g s_i + p f e + f M$

Hence, we want to check whether $||f \cdot c_{sum} ||_{\infty} \leq q/2$, where:

$f \cdot c_{sum} = \sum\limits^k_{i=1}(p g s_i + p f e_i + f m_i) = \sum\limits^k_{i=1}p g s_i + \sum\limits^k_{i=1}p f e_i + \sum\limits^k_{i=1}f m_i$

Lemma 3.7 provides the following bounds:

$||pgs_i||_{\infty}, ||pfe_i||_{\infty} \leq 8 \alpha q n^{0.25} \omega(\log n)||p||^2 \sigma$

$||fM||_{\infty} \leq 4n||p||^2 \sigma$

Therefore, $||f \cdot c_{sum}||_{\infty} \leq 2k\cdot(8 \alpha q n^{0.25} \omega(\log n)||p||^2 \sigma) + 4n||p||^2 \sigma$.

Next, assuming that $n^{0.75} \leq \alpha q$, as in Lemma 3.7, we have that:

$||f \cdot c_{sum}||_{\infty} \leq 16 k \alpha q n^{0.25} \omega(\log n)||p||^2 \sigma + 4n^{0.25}\alpha q||p||^2 \sigma$

After some simplifications, we obtain the following bound:

$||f \cdot c_{sum}||_{\infty} \leq (16 k + 4) n^{0.25}\alpha q\omega(\log n)||p||^2 \sigma$

Note that when $k=1$, it produces precisely the same result than Lemma 3.7. Finally, similarly to Lemma 3.7, we have to initially assume that $ \omega( n^{0.25}\log n)\alpha q k ||p||^2 \sigma < 1$, so the correctness condition for the sum of $k$ ciphertexts holds.

A final note: these results, as the one from Lemma 3.7, are not tight, and depend heavily on the choice of parameters. My guess is that you can sum (much) more than $k$ ciphertexts, and still decrypt correctly.

References

[SS13] Stehlé, D., & Steinfeld, R. (2013). Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices. IACR Cryptology ePrint Archive, 2013, 4.