discrete logarithm equality for independent groups

Let me assume for simplicity that $q_1 \leq q_2$. You want to prove that the discrete log of $x_1$ in $G_1$ is the same that the discrete log of $x_2$ in $G_2$, and that this discrete logarithm seen as an integer is smaller than $q_1$. This suggests that you should rely on a zero-knowledge proof for a relation over the integers. The most natural method to do this kind of proofs is to work over a group of unknown order, as, intuitively, if the prover does not know the order of the group he cannot reduce the exponents modulo this order - and the relation should hold over the integers.

So, let $G$ be a group of unknown order where the discrete logarithm is hard (for example, the subgroup of squares of an RSA group). Let com$(\cdot)$ be a perfectly hiding integer commitment scheme over $G$ (e.g. the Fujisaki Okamoto commitment scheme). Let $s \le q_1$ be your secret exponent. In addition to $x_1 = g_1^{s} \in G_1$ and $x_2 = g_2^s \in G_2$, the prover sends a commitment com$(s) = c$ over $G$.

Let us take the protocol suggested by professor Lindell as a basis. Consider the following modification of this protocol:

the answers are not computed modulo $q_1\cdot q_2$, but they are instead computed over the integers. For this not to break the zero-knowledge property, the mask $r$ should be taken, say, 160 bits longer than $s$, so as to statistically mask $e\cdot s$ over the integers.
The prover proves knowledge of $s$ which is the discrete log of $x_1$ and $x_2$ and the value committed in $c$
The prover additionally proves that the value committed in $c$ is lower than $q_1$. The classical method to do so is as follows: both players compute $c’$ from $c$ and $q_1$, a value that commits to $s’ = q_1 - s$ (the Fujisaki-Okamoto scheme is homomorphic, it is essentially com$(m;r) = g^mh^r$). Observe that $s \leq q_1$ is equivalent to $s’ \geq 0$. moreover, by a classical result of Lagrange, an integer is positive if and only if it can be written as a sum of four squares. Therefore, the prover computes this decomposition of $s’$ into a sum of four squares (via the Rabin-Shallit algorithm), commits to them, and proves that $s’$ is the sum of the squares of these committed values. Such a protocol is known as a range proof and is described in several papers, e.g. this one.

Once this protocol is complete, the verifier is convinced that the prover knows an integer $s \leq q_1$ such that $g_1^s = x_1$ and $g_2^s = x_2$. One can refine the protocol to make it more efficient, but I tried to make the answer as intuitive as possible.


What does “invertibility of the cryptographic primitive” mean?

"Invertibility of the cryptographic primitive" is just a fancy way of saying "you can decrypt things encrypted with that key." All the first sentence means is "if you can recover the key, you can decrypt anything encrypted with that key." As the second sentence points out, there are conceivably attacks where you can decrypt things encrypted with a key but can't recover the key itself; the reverse is not true, because if you have the key you can use it to decrypt things.


Each one of your first two sentences has a mistaken premise: you're starting from some assumptions that aren't actually true.

DES does not use small PRPs for saving memory.  It doesn't use small PRPs at all.  The DES S-boxes are not PRPs.  The DES F-function is not a PRP.  A SPN does not use several small PRPs for saving memory.  A SPN doesn't use PRPs at all.  The S-boxes in a SPN are not PRPs.

A PRP does not necessarily require $\lg(2^n!)$ memory.  Actually, most PRPs have short keys that fully determine the encryption mapping, and the short key can be stored in much less memory.  That is in some sense the entire point of a PRP.

You might wish to restate your questions in a way that removes those implicit assumptions.  Also you might wish to review the definition of a PRP again, and read some more textbook material on PRPs to familiarize yourself with the concept a bit further.  Perhaps you are confusing a PRP with a random permutation (one chosen uniformly at random from the set of all permutations on $n$ bits).  If so, here's an exercise for you to ponder: how many permutations are there on $n$ bits?  Now what happens if the take the logarithm (base 2) of that number?


elements of $GF(p)$ are integers, while elements of $GF(p^n)$ are polynomials.Why the difference?

TL;DR: because integers modulo $p^n$ do not form a field.

Here's a pragmatic construction of $GF(p^n)$ useful for applied cryptography, including AES which uses the field $GF(2^8)$ extensively.

$GF(p)$ for prime $p$ is the field of arithmetic modulo $m$ for modulus $m=p$. Arithmetic modulo an integer $m$ works as integer arithmetic except that all results are reduced to the range $[0,m)$ by subtraction of $q\,m$ for some appropriate integer $q$. Arithmetic modulo $m$ keeps the usual properties of addition and multiplication: their are internal laws with associativity, commutativity, distributivity, neutral $0$ for addition and $1$ for multiplication, existence of an opposite (w.r.t. addition) for all elements. And, specifically when $m$ is prime, arithmetic modulo $m$ gains a property of rationals and reals that integers do not have: existence of an inverse/reciprocal (w.r.t. multiplication) for all elements except $0$. That additional property makes arithmetic modulo $p$ a field of $p$ elements, when arithmetic modulo a composite $m$ is not¹.

When we want to make a field of $m$ elements and $m$ is not prime, we thus can't use arithmetic modulo $m$. It turns out that there is an alternative construction if and only if $m$ is of the form $p^n$ with $p$ prime. That's $GF(p^n)$.

One way to think an element $A$ of $GF(p^n)$ is as a vector $(a_0,a_1,\ldots,a_{n-1})$ of $n$ elements $a_i\in GF(p)$. At least that gives us the right count of elements $p^n$, and we can define a well-behaved addition as
$$A+B=(a_0+b_0\bmod p,a_1+b_1\bmod p,\ldots,a_{n-1}+b_{n-1}\bmod p)$$
with the all-zero vector the neutral. But somewhat we need to define multiplication in such a way that $A\,B$ is also a vector of $n$ elements in $GF(p)$, and all except one elements have an inverse².

That's where polynomials come to the rescue. We assimilate $A=(a_0,a_1,\ldots,a_{n-1})$ to the (univariate) polynomial $a_0+a_1\,x^1+\ldots+a_{n-1}\,x^{n-1}$ of degree less than $n$ and coefficients $a_i\in GF(p)$. Notice that the rules of addition of polynomials with coefficients in $GF(p)$ coincide with our earlier definition of addition.

Now we pick a polynomial $M=m_0+m_1\,x^1+\ldots+m_{n-1}\,x^{n-1}+m_n\,x^n$ of degree³ $n$ with coefficients $m_i\in GF(p)$, and define the product $A\,B$ in our would-be field as
$$\underbrace{A\,B}_{\text{in would-be field}}=C=\underbrace{A\,B\bmod M}_{{\text{in polynomials with}\\\text{coefficients in }GF(p)}}$$
The right side means that $C$ is the⁴ polynomial with coefficients $c_i\in GF(p)$, of degree less than the degree of $M$ (hence of degree less than $n$, hence representable as a vector of $n$ elements in $GF(p)$ as desired), such that there exists a polynomial $Q$ with coefficients $q_i\in GF(p)$ with
$$0=C+Q\,M-A\,B$$
per the normal rules of addition and multiplication of polynomials with coefficients in $GF(p)$. That is
$$0=\sum_{0\le i<n}\left(\left(c_i+\sum_{0\le j<n}\left(q_j\,m_{i-j}-a_j\,b_{i-j}\right)\right)x^i\right)$$
or equivalently when we get back to vector notation rather than polynomials
$$\forall i\in[0,n),\ \underbrace{0=c_i+\sum_{0\le j<n}\left(q_j\,m_{i-j}-a_j\,b_{i-j}\right)}_{\text{in }GF(p)\text{, that is}\pmod p}$$
We've already seen that this construction of multiplication is an internal law. It's easy to show that it inherits from the field of arithmetic in polynomials with coefficients in $GF(p)$ the properties of associativity, commutativity, distributivity, and neutral the constant polynomial $1$, that is the vector $(1,0,\ldots,0)$. We have constructed a commutative ring with $p^n$ elements.

It can be shown that if (and only if) polynomial $M$ is irreducible, each element has an inverse, which completes the field properties. And it can be shown that there exits an isomorphism among the different fields that we obtain for different irreducible polynomials $M$, which is why mathematicians speak of the field $GF(p^n)$, rather than of the field $GF(p^n)$ obtained for a particular irreducible polynomial $M$, as practical cryptographers often do.

  Relation between extension fields and non-prime fields

A field $G$ is an extension field of $F$ when $F$ (or $F'$ with a trivial mapping to $F$) is a subset of $G$ and is a field under the same addition and multiplication laws that make $G$ a field.

When we restrict $GF(p^n)$ constructed as above to the set of constant polynomials (equivalently, the set of vectors of $n$ elements in $GF(p)$ with all expect the first set to zero), we are back to a subset of $p$ elements that matches $GF(p)$.

Otherwise said, $GF(p^n)$ is an extension field of $GF(p)$.

Notes:

¹ Arithmetic modulo a composite $m$ is only a commutative ring of $m$ elements, but not a field. Proof: if $m$ is composite, let $a$ be the smallest prime divisor of $m$. If $a$ had an inverse $x$ modulo $m$, we'd have $a\,x\equiv1\pmod m$, that is $\exists q\in\Bbb Z,\ a\,x=1+q\,m$. We can write $m=a\,b$ for some $b\in\Bbb Z$. Hence $a\,x=1+q\,a\,b$, hence $a\,(x-q\,b)=1$ in the ring of integers, which can't be since $a$ is prime. Hence $a$ has no inverse modulo $m$ when $m$ is composite. Since $a$ is not zero, one of the field requirement is not met.

² That's the hard part. In particular, the construction of the product as $A\,B=(a_0\,b_0\bmod p,a_1\,b_1\bmod p,\ldots,a_{n-1}\,b_{n-1}\bmod p)$ leaves multiple $A$ without an inverse: all those with at least one of their $a_i=0$ in $GF(p)$.

³ That's exactly degree $n$, otherwise said $m_n\ne0$ in $GF(p)$.

⁴ The polynomial $C=A\,B\bmod M$ is uniquely defined by the relation $0=C+Q\,M-A\,B$. That $C$ can be (and in practice often is) obtained by computing the product $A\,B$ as a polynomial with coefficients in $GF(p)$ of degree less than $2\,n-1$, and progressively reducing that product's degree from at most $n+j$ to less than $n+j$, by computing $q_j$ and subtracting $q_j\,x^j\,M$, with $q_j=d_{n+j}/m_n$ computed in $GF(p^n)$, and $d_{n+j}$ is the high-order coefficient of the progressively reduced product. To simplify that computation, it is customarily used $m_n=1$, that is $M$ a monic polynomial.


(AES in mind) How can we show two irreducible polynomials have a bit-wise linear isomorphism

To answer this question, we'll first want to step back and discuss what a finite field is, and what a representation is.

A finite field is a group of finite size (always $p^k$, for some prime $p$ and integer $k$, in this case, $2^8$), along with addition and multiplication operators, where certain identities are true (e.g. $a \times (b + c) = a \times b + a \times c$), see this link for the list.

It turns out that, given a specific size $p^k$, the field is essentially unique (in the sense that, if we have two different sets of the same size where they both preserve the identities, they will always be a mapping between the two sets which preserve both the addition and multiplication operations, hence those two sets are essentially the same.

This is nice, however we need a way to talk about these elements; what we do is assign the element names; for $GF(2^8)$, we have precisely 256 elements, and so we typically give each element a unique 8 bit name.  Such a way of assigning names is known as the 'representation'.

For $GF(2^8)$, there are a number of reasonable ways to assign these names, one such way is to select an irreducible polynomial, and compute the multiplication modulo that polynomial.  That is the approach that AES takes, with the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$.  Let us call this specific representation (which is a way of assigning names to field members) $A$.

However, that isn't the only way of assigning names; we could consider a different irreducible polynomial, say, $x^8 + x^4 + x^3 + x^2 + 1$.  That gives a different way of assigning names to field elements, that is, a different representation, we may call this representation $B$.

Now, we define $L$ to be the function that takes a field element (using the $A$ naming convention), and return the name of that same field element (using the $B$ naming convention).  It turns out $L$ isn't unique; we'll ignore that for now.  It turns out that $L$ is an isomorphism, as the field it maps from (the $A$ representation) and the field it maps to (the $B$ representation) are the same (because they're both different ways of given labels to the same underlying field).

It turns out that, if we just look at $L$ as a mapping between 8 bits to 8 bits, it is bit-wise linear.

In the $A, B$ representations I just gave, one such mapping is:

$$L(01) = 01$$
$$L(02) = 03$$
$$L(04) = 05$$
$$L(08) = 0F$$
$$L(10) = 11$$
$$L(20) = 33$$
$$L(40) = 55$$
$$L(80) = FF$$

Because $L$ is linear, it is easy to deduce $L(X)$ for any other $X$ not listed.

And, what $+_A$ means is the addition operation in the $A$ representation; that is, $X +_A Y$ takes the two field elements $X, Y$ (named using the $A$ convention), and evaluates to the field addition of those elements (also expressed in the $A$ naming convention.  Hence, when we say:

$$L(X+_AY)=L(X)+_BL(Y)$$

$X, Y$ are both arbitrary field elements (in the $A$ naming convention), and what we're saying is that the $L$ mapping preserves addition; that is, if we add two arbitrary elements $X, Y$ (in the $A$ representation) and then map the sum, we always get the exact same value as we would have if we first mapped $X$ and $Y$ into the $B$ representation, and then added them (in the $B$ representation).

We call out $+_A$ and $+_B$ because they aren't necessarily the same operation (actually, in this case they are, but not in general); $+_A$ assumes the inputs are in the $A$ representation, and $+_B$ assumes they are in the $B$ representation.

You asked for a numeric example, here's a simple one (using the $\times$ operator; it turns out that the addition operation isn't that interesting).

If we pick $X = 03$ and $Y = 05$, we have (on the left side):

$L(03 \times_A 05) = L(0F) = L(01) \oplus L(02) \oplus L(04) \oplus L(08) = 08$

(Note: we have $L(0F) = L(01) \oplus L(02) \oplus L(04) \oplus L(08)$ because of the bitwise linearity of $L$)

On the right side, we have:

$L(03) \times_B L(05) = (L(01) \oplus L(02)) \times_B (L(01) \oplus L(04)) = 02 \times_B 04 = 08$

That is, both sides come up with the same value.  This will always be true no matter what values we picked for $X, Y$


Why can't I break ElGamal encryption by brute-forcing the secret exponent?

For ElGamal to be secure, the 'discrete log problem' (which is, given $g$ and $g^x$, find $x$) must be intractable.  You give a generic way to attack the discrete log problem for a group with $n$ elements with something like $n$ steps (I say about because your approach isn't the simplest version of this type of attack; the simplest does take $n$ steps); hence for ElGamal to be secure, the size of the subgroup $n$ must be big enough.

If the security assumption of the adversary is that he cannot possibly perform $2^{128}$ computations, this immediately means that we need a group with at least $2^{128}$ elements or so.

That means that, in practice, this attack will not be practical, because (as you guessed) we'll pick ElGamal groups that are too large for the attack.

Two comments:

When I talk about the size of the group, what's actually important is the size of the subgroup generated by $g$; that is, the number of distinct values in $g^1, g^2, g^3, ...$.  When we're in a multiplicative group modulo a prime, the size of this subgroup can be considerably smaller than the size of the modulus.
It turns out that there are cleverer generic ways to attack the discrete log problem; because of these ways, it turns out that if our assumption is that the attacker can't do more than $2^{128}$ operations, the size of the subgroup needs to be at least $2^{256}$ elements large.


(Impossibility of?) Associative Pseudorandom Permutation

As mentioned by Meir Naor in the comments, what you are describing is impossible. The reason is that the associativity gives us leverage to distinguish the function from a random function. To do so an adversary $\mathcal{A}$ with access to an oracle that is either $f(k,\cdot)$ for a random key $k$ or a truly random function $g(\cdot)$ can proceed as follows:

Choose random $k'$ and $x$ and compute $y := f(k',x)$.
Query $y$ to the oracle and receive back $z$.
Query $k'$ to the oracle and receive back $k''$.
Compute $z':= f(k'',m)$ and check whether $z'=z$.
If it is output $1$, otherwise output $0$.

To see that $\mathcal{A}$ is a successful distinguisher for $f$ we want to analyse
$$\left|\Pr[\mathcal{A}^{f(k,\cdot)}(1^n)=1] - \Pr[\mathcal{A}^{g(\cdot)}(1^n)=1]\right|$$
and see that this difference is noticeably greater than $1/2$.

In the first case we have by the associativity of the function $f$ that $z=f(k,f(k',x))=f(f(k,k'),x)$. Further we have that $k'' = f(k,k')$ and thereby $z'=f(k'',x) = f(f(k,k'),x) = z$. Therefore we have $$\Pr[\mathcal{A}^{f(k,\cdot)}(1^n)=1] = 1.$$

In the second case we have that both $z$ and $k''$ are truly random independently sampled values in $\{0,1\}^n$. In particular $z'=f(k'',x)$ is some value that is distributed independently of $z$. Therefore we have that $\Pr[z=z'] = 2^{-n}$ (i.e., the probability that an independently randomly sampled $z$ takes any particular fixed value).
This means that
$$\Pr[\mathcal{A}^{g(\cdot)}(1^n)=1] = 2^{-n}$$
and we get
$$\left|\Pr[\mathcal{A}^{f(k,\cdot)}(1^n)=1] - \Pr[\mathcal{A}^{g(\cdot)}(1^n)=1]\right| = 1-2^{-n}$$
which is noticeably greater than $1/2$. (In fact it's only negligibly smaller than $1$.)

This shows that any fixed associative function is always distinguishable from a random function. Also note that this attack does not go away by just constraining $g$ to be a random associative function. This is because we are not simply checking whether the oracle is associative. We are specifically using the associativity of $f$ to check whether the oracle is $f$. In the case where $g$ is associative, the analysis gets a bit more complicated because $z$ and $z'$ are now no longer completely independent. But the attack still works.


How to create a decentralized secret ballot among a small group of people?

Electronic voting schemes constitute a big area of cryptographic research. The problem is complicated and multifaceted, and there are still no end-to-end secure schemes that provide desirable properties like verifiability and coercion resistance and that have good usability and performance for a large number of voters. See for example this survey from 2017 for the state-of-the-art. One scheme with implementation that's relatively popular is Helios (website)
 (Usenix paper, 2008), which foregoes coercion resistance, and instead mostly focuses on auditability in the case of malicious voting machines.

Ignoring implementation-related security and just focusing on the underlying cryptographic techniques, perhaps the simplest method for such a small election with the number of voters $n < 100$, would be to use a linear secret sharing scheme, e.g. Shamir's. In Shamir's scheme, we may share a secret value $s$ in some large enough finite field $\mathbb F$ among $n$ players by selecting a uniformly random polynomial $f \in \mathbb F[X]$ of degree at most $t$ such that $f(0) = s$, and sending the value of $f(i)$ to player $i$. The parameter $t$ determines how many players are needed to reconstruct a secret from the shares: given $t+1$ players, they may jointly reconstruct $s$ by using Lagrange interpolation on their shares, but at most $t$ players obtain no information about the secret.

Suppose the parties have access to pairwise secure channels, and can be trusted to follow the protocol exactly, and not cheat by for example submitting a faulty vote. Each voter $V_i$ records their vote as a vector $\mathbf x_i = (x_{i1}, \dots, x_{iN}) \in \mathbb F^N$ where $x_{ik} = 1$ if $V_i$ wants to vote for candidate $k$, and $x_{ik}=0$ otherwise. Of course, only one element in $\mathbf x_i$ is allowed to be 1, and the rest should all be 0. $V_i$ then secret-shares their vote with all the other voters (e.g. using packed secret sharing [FY92] if $N$ is small enough, or if need be sharing each coordinate in the vector separately). Let $[\mathbf x_i]_j$ denote the share of voter $V_j$ for the secret vote vector $\mathbf x_i$ of $V_i$.

Every voter $V_j$ now has $n$ shares $[\mathbf x_1]_j, \dots, [\mathbf x_n]_j$. Since Shamir's scheme is linear, the players may add their $n$ shares to obtain a valid share of the total election result $\mathbf x_1 + \dots + \mathbf x_n$. Hence, they may jointly reconstruct this value, and determine the election's winner.

A similar result to this may be obtained using additively homomorphic encryption (which Helios uses), and distributed key generation and threshold encryption. Of course, in this scheme voters can easily cheat without being detected, by for example setting $x_{ik} = 2$ and $x_{ik'} = -1$, and more machinery is needed to make this work in the actively secure case, but I hope it gives a rough idea.


Your understanding is correct. PKI would be the service that verifies that Bob's public key really belongs to someone named "Bob". As long as Alice trusts the certificate authority that certified Bob's public key, she can implicitly trust that the public key she sees really is Bob's, not Eve performing a MITM.

The internet is secured with web PKI, which is the network of Certificate Authorities that certify that a websites' public key really belongs to the domain it claims to belong to (for Domain Validation, or DV). It's far easier to trust a handful of CAs than it is to trust every single website you'll ever visit.


What is the shortest ciphertext size output by FHE?

It depends on whether you want to encrypt a single bit, or many bits.

If you want to encrypt a single bit, I think (disclaimer: I might be missing other schemes) that the shortest ciphertexts are achieved by the TLWE-based FHE of this paper (see also this paper on which it is based). According to their claim, the ciphertext expansion is "only" 10000 bits (i.e., encrypting one bit requires 10000 bits). This is because they can simply work with LWE-like ciphertexts, and then transform them when needed into a GSW ciphertext (which supports fully homomorphic operations).

If, however, you want to encrypt multiple bits, then any FHE scheme can achieve optimal rate of $1+o(1)$ using a standard hybrid encryption: an encryption of an $n$ bit plaintext $m_1, \cdots, m_n$ is $(\mathsf{FHE}(K), \mathsf{SymEnc}_K(m_1, \cdots m_n))$, where $\mathsf{SymEnc}_K$ is a secret-key encryption scheme with secret key $K$. To evaluate a function homomorphically on this ciphertext, simply homomorphically apply first the following circuit $C$ to $\mathsf{FHE}(K)$: $C$ has $E = \mathsf{SymEnc}_K(m_1, \cdots m_n)$ hardcoded in its description, and on input $K$, it outputs $\mathsf{SymDec}_K(E)$. Hence, this steps gives you $\mathsf{FHE}(C(K)) = \mathsf{FHE}(\mathsf{SymDec}_K(E)) = \mathsf{FHE}(m_1, \cdots m_n)$, from which you can then evaluate any function of your choice. The ciphertext size is then $n + O(\lambda)$, where $\lambda$ is a security parameter, assuming $\mathsf{SymEnc}_K$ has rate $1+o(1)$ (which is the case with every modern symmetric encryption scheme, e.g. AES).


How to handle modular arithmetic with regard to two's-complement negative numbers?

This answer answers Q1, as there may be merit other than just for calculating CRT RSA (e.g. the extended Euclidean algorithm).

Let's build it step-by-step.
First let's assume you've implemented the % operator for unsigned modular arithmetic in constant time, when you encounter a negative number x, we have the following:
x === -(-x)
Introducing the modulus p, and we have:
x (mod p) === p - (-x) (mod p)
Hence, the algorithm for negative numbers (in pseudo-code, not constant-time yet):
imod(x):
    x = -x
    x = x % p
    if x > 0: x = p - x
    return x

Now, we want to generalize it to apply to also positive numbers, here's the full code in C (constant-time this time):
uint32_t imod(uint32_t x, uint32_t p)
{
    uint32_t neg = -(x >> 31);
    uint32_t z;

    // conditionally negate x.
    x ^= neg;
    x += neg & 1;
    x = x % p;

    // test for 0.
    z = x;

    // Per suggestion by @fgrieu
    // The following code fragment involves:
    // 2 shifts, 4 bit-ops, and 2 additive ops.
    z |= z >> 16;
    z &= 0xffffU;
    z = -(1 ^ ((z ^ (z - 1)) >> 31));

    // In comparison, the following requires:
    // 5 shifts, 6 bit-ops, and 1 additive ops.
    /* z |= z >> 16;
     * z |= z >> 8;
     * z |= z >> 4;
     * z |= z >> 2;
     * z |= z >> 1;
     * z = -(z & 1);
     */

    neg &= z;

    // conditionally compute p - x.
    x = ((~neg & x) | (neg & p)) - (neg & x);
    return x;
}


Historical algorithm which is frequency analysis resilient

You probably mean the VIC cipher.

It can be set up in a way such that the initial substitution that also achieves fractionation through the use of a so-called straddling checkerboard is followed by a transposition or substitution step. These steps make the distribution of symbols in the cipher text more uniform than in the plain text.

An optional subsequent reverse substitution using the same straddling checkerboard leads to a cipher text that contains only symbols of the original alphabet.


There is no such proof, on the contrary it has been proven that SHA-1 does not possess the ideal 80 bit collision resistance. Rather it is down to around 61 bits of resistance, uncomfortably close to being practically exploitable, and even if no further weaknesses are found advances in computing power are almost guaranteed to make it reasonably practical within a decade or two.

This weakness is only to collision attacks, that is attacks where the attacker can construct two different data pieces that has the same hash value, and thereby break some security measure, in some use cases that is relevant and SHA-1 is therefore problematic, in other cases it isn't and we can afford to be a bit more relaxed about the use of SHA-1 as its pre-image resistance doesn't seem likely to drop to a critical level any time soon.

In any case though, for new applications you are best advised to avoid using SHA-1 and earlier, instead use for instance one of the SHA-2 functions.

As for the theoretical foundation, SHA-1 is a Merkle–Damgård construction, such a construction is proven to be a perfect hash given that the one-way compression function it is built on can give some similar guarantees. It was presumably for this reason that Merkle–Damgård constructions became popular, but ultimately it is the one-way compression function that is the critical part, the Merkle–Damgård proof only tells us that the much simpler container format is not borked. You can find loads of cryptanalysis reports for any popular hash function, but unless you are a pretty sharp mathematician with a lot of time to kill they are probably not going to be of any use to you.


How do I pick variable length passwords uniformly at random?

In practice, it is sufficient to pick a random password with the maximum allowed length.

Assuming that your alphabet has $n$ different usable characters, the total number of passwords of length up to $k$ is $$t(k) = n + n^2 + n^3 + \dotsb + n^k = \sum_{j=1}^k n^j = \frac{n^{k+1}-1}{n-1},$$ and thus the fraction of all passwords that have length less than $k$ is $$\frac{t(k-1)}{t(k)} = \frac{n^k-1}{n^{k+1}-1} \approx \frac 1n.$$

For example, assuming that your passwords are composed of printable ASCII characters ($n = 95$), all the passwords shorter than the maximum length make up only about $1/95 \approx 1.05\%$ of the total password space.

(In any case, if these "passwords" are meant to be memorized by a human, it's generally much more effective to use a passphrase selected by picking random common words from a suitable dictionary.  See diceware for a popular example implementation.  Depending on the size of the dictionary used, each such word can encode about 10 to 13 bits of randomness, whereas two random printable ASCII characters encode a little over 13 bits, but a single meaningful word is much easier for a human to remember than a pair of random characters.  Of course, such passphrases do end up being a couple of times longer than a random character sequence of equivalent entropy, but this is only a serious problem if you're running against some kind of a hard maximum length limit, in which case the existence of such a limit is the real problem.)


Convert affine to projective coordinates and vice versa in ECC?

Somewhere you seem to have made a small mistake. $39$ is already the inverse of $Z_{2Q}$. The correct value of $Z_{2Q}$ is $\mathbf{32}$.

For the long story, let us first go through the doubling formula one step a time:

if (Y == 0)                     # nope
 return POINT_AT_INFINITY
W = a*Z^2 + 3*X^2               # W = 0
S = Y*Z                         # S = 38
B = X*Y*S                       # B = 25
H = W^2 - 8*B                   # H = 15
X' = 2*H*S                      # X'= 22
Y' = W*(4*B - H) - 8*Y^2*S^2    # Y'= 31
Z' = 8*S^3                      # Z'= 32
return (X', Y', Z')

This leaves us with $2Q = (22 : 31 : \mathbf{32})$.

To compute the affine representation, we compute $Z_{2Q}^{-1} = 39$. Now the affine representation of $2Q = (XZ^{-1}, YZ^{-1}) = (22 \cdot 39, 31 \cdot 39) = (41, 5)$.


Could one build a symmetric encryption system that is competitive with the AES by randomly applying Toffoli-like gates?

It seems plausible that one builds a symmetric encryption system competitive with AES by randomly applying Toffoli(-like) gates as restricted in the question. I do not know that it has been studied.

Paraphrasing the question, it constructs a block cipher with 128-bit block and 128-bit key similar in function to AES-128 as follows:

number inputs as $b_i$ with $0\le i<128$ for block bits and $128\le i<256$ for key bits
repeat $r$ times

pick random distinct indices $i,j,k$ with $(k\ge128)\implies(i\ge128)\wedge(j\ge128)$
apply a random Toffoli-like gate to $(b_i,b_j,b_k)$

In the end, the result is the 128-bit $x_i$ with $0\le i<128$. The rule $(k\ge128)\implies(i\ge128)\wedge(j\ge128)$ insures that for any fixed key, the block cipher is reversible.

Seen from far away with blurry vision, there are similarities between this construction and AES-128: both are iterated permutation-substitution ciphers with reversible key transformation along the rounds, and 256 variables.  If we chose $i$, $j$, $k$ randomly until acceptable, a key bit is chosen as $z$ (the potentially changed bit) with odds about $1/5$, which grossly mimics AES spending significantly less computational effort on key scheduling than on data encryption.

I do not know the number of rounds $r$ making the block cipher secure; nor a technique to derive this. But I would not be astonished if it was markedly lower than $100000$.


How to make my hash more robust to the brute force?

I would recommend you use Argon2, which is both a slow KDF like PBKDF2, as well as a memory-hard function designed to improve resistance to GPUs and FPGAs like scrypt. You can select both the number of iterations and amount of memory used in Argon2, and they can be changed independently (unlike scrypt, where the memory and time difficulties cannot be modified separately, and high time implies high memory-usage). This can be done on existing password hashes to maintain backward compatibility, but I would suggest you convert the old scheme (PBKDF2 with scrypt) into one using just Argon2 as soon as a user next logs in and supplies their password.


Hash function as secure as one-time pad?

OTP requires 1) random key material as long as the message to be encrypted 2) no reuse of the key material or any part, ever 3) secure transmission of the key material between communicants 4) no key material becomes known to anyone ever.
And even then, OTP only guarantees that no other encryption will be harder to break. NOT that a message can't ever be recovered.

1) random -- for crypto purposes, random is very very hard, and very very tricky. We don't know how to do it, though we think some schemes are pretty good. There are many tests, but there are more ways to be non-random than there can be tests.

2) no reuse -- reuse makes an OTP worthless. The Russians did a little reuse in WWII and NSA was eventually able to read some of the traffic encrypted with reused key material. See Venona Project.

3) secure transmission -- NO ONE has solved the secure transmission of arbitrarily long material between nodes. There are Xerox machines, disk copiers, thumb drive copiers, ... Plus burglary (which can sometimes be covered up, leaving the sender making a very bad and completely insecure assumption),

4) no exposure of key material ever -- this requires a degree of fail safe control of the security of stuff well into the future. Humans aren't really compatible with this sort of thing.

But, good hash algorithms (and we are not SURE any of ours are good enough, there's been a poor track record) can be claimed to produce an unpredictable (and so random) string when fed with a suitable input. Sadly, they are deterministic.  Feed a hash algorithm abcd... more than once and you'll get out the same hash. Which means that the unpredictability of hash algorithms is dependent on unpredictability in their inputs.  Not a good thing, people being people. But, if you use some CSRNG for the inputs, why bother with the hash algorithm? If the CSRNG is defective, so will be the randomness of the hashes you produce.

But even if you, foolishly, hand wave away these issues, nearly all hash algorithms produce a shortish bit string.  Say, 128 bits, or 256, or some such. So you could send a message, using one of these hashes as the OTP key material, 128 or 256 bits long.

I wouldn't bother in practice, and wouldn't touch it with a ten foot pole for a theoretical study.  Too much contingency, too much dependence on things athat are out of anyone's control, ....


Are there any practical use cases for performing homomorphic operations on encrypted Strings?

I believe you're talking about homomorphic encryption. It allows to have operations on encrypted data.

A simple use-case example:

Sometimes data has to be kept confidential (i.e. names, address, ... ). It could be that you want to perform computing on data but you're missing the computational power to do so. So you're outsourcing this computation to someone else (cloud computing), but now you have a problem with privacy and confidentiality, because in this case the data has to be handled confidentional.

That's where homomorphic encryption is useful. You encrypt the data and afterwards an untrusted server can perform computation on this data. After the computation you can decrypt the data again and a third party has not gained any knowledge of the data.

Examples in the case of strings:

You have a database with tables and you would like to add a new row with data. The database can be encrypted and hosted by an untrusted server (we're looking over the fact that this is maybe a bad practice). You can encrypt the data and add it to the database.
You want to compare a lot of data (strings), for example you want to be sure that database A ($D_a$) has exactly the same data as the database B ($D_b$). You can compare the data with homomorphic encryption by an untrusted third party. After the comparison you know if $D_a = D_b$.


Is there a crypto function that would take 1 second to run?

The are already many solutions for this. See for instance Argon2, Lyra2, scrypt.
They allow you to tune the number of iterations so that it takes needed time on particular device (CPU, GPU) to compute a hash.


Practical brute-force attack on 128 bit encryption

n is the exponent. So when n is doubled from 64 to 128 it doesn't mean that you have to try twice as many values. It means that you have to try $2^{64}$ times the amount you were already trying (as $2^{128} = 2^{2\times64} = 2 ^{64+64} = 2^{64}\times2^{64}$).

It is required to only search half of the key space on average (if average is the correct term here, this is not something you are likely to repeat), but that means that the search should cover $2^{128}/2 = 2^{128-1} = 2^{127}$ on average.

So in the end it comes down to the difference between $2^{128/2}$ as used by the birthday attack (which is not applicable) and $2^{128} / 2$ which is the average amount of tries required by a brute force attack.

For an indication how the time scales with the number of bits, take a look at the stats of the RC5 72 bit challenge and compare it with the stats of the RC5 64 bit challenge that you probably referred to.

Birthday attacks are indeed not applicable to encryption. Collision finding - for which the Birthday attacks are used - are in itself not directly applicable to attacks on ciphers.


Should a company ever implement a (recent) published cryptographic protocol

So, should a company ever implement a published protocol for a commercial product?

Yes, if it's something that really adds value for your users. No if it's about saving 4 signature bytes and 112 CPU cycles.

  And if so, what guidelines should they follow?

Publish the source code, at least for the crypto part, so it can be peer reviewed.
Hire experts in the field as consultants to review the implementation.

Both of the above points will help make a strong case for adoption to clients who may have conservative attitudes to security.


Should I be concerned about padding oracle attacks if the lifespan of my key is ~1 minute?

A Padding Oracle attack due to my use of CBC Cipher Mode

CBC in and of itself does not directly result in a padding oracle. It is when you abuse the padding after decryption to decide whether or not decryption was successful and then communicate (maybe not even directly) the results of that padding check.

Based on your comment that

  The connection is terminated and the key discarded as soon as decryption fails.

it sounds like you are likely using a padding check to determine whether or not decryption has failed. If that is incorrect let me know.

Should you be worried about this?

Definitely. The fact that your keys are short lived perhaps makes it so that the current incarnation of your software is not exploitable (I'm not convinced that it isn't exploitable), but it is vulnerable at the very least. What happens when you are no longer available (say left the company this code is written for or stop working on the open source project this code is written for) and someone else changes the keying requirements. They may very easily change them in such a way that the software is now exploitable since the vulnerability has persisted.

In our world, it is much better to just fix the problem and not let it turn into something that can be exploited down the road.

How can you fix it?

The best approach is to use message authentication codes. I suggest you read Should we MAC then encrypt or encrypt then MAC. Basically, you can either switch to an authenticated encryption mode (look at your crypto library to see what is supported) or add a MAC after encrypting with CBC using HMAC. Please read Why can't I use the same key for encryption and MAC? while you are at it.


Standard basis representation of elements in binary field

Your basis is the polynomial basis.
The terminology basis comes from adopting a finite extension $F=\mathbb{F}_{q^m}$ of the finite field $K=\mathbb{F}_{q}$ as a vector space over $K$. We can see that the extension as the dimension of the vector space so we need $m$ elements to form a base.

Polynomial Basis
Let $K$ be a degree $m$ extension of the finite Field $F$ and let  $\alpha$ be a root of a primitive polynomial of degree $m$ then the powers of $\alpha$ (defining elements) forms a polynomial basis. $$\{1,\alpha,\alpha^2,\ldots,\alpha^{m-1} \}$$
Example: Let $\alpha \in \mathbb{F}_8$ be a root of an irreducible polynomial in  $x^3+x^2+1$ in $\mathbb{F}_2$. Then, $\{1,\alpha,\alpha^2\}$ is a polynomial base. With this base the 8 elements of the extension field can be represented as;
$$\{0,1,\alpha, \alpha +1, \alpha^2, \alpha^2+1, \alpha^2+\alpha, \alpha^2+\alpha+1\}$$
When we talk about the multiplicative cyclic group $F^*$ of the field $F$, the element zero is excluded $$F^*= F \backslash \{0\}.$$
In this example;
$$\mathbb{F}^*_8= \{1,\alpha, \alpha +1, \alpha^2, \alpha^2+1, \alpha^2+\alpha, \alpha^2+\alpha+1\}$$
In this multiplicative cyclic group, there are elements $g$ such that $F^*=\langle g \rangle$

Normal Basis
Let $K = \mathbb{F}_q$ and $F = \mathbb{F}_{q^m}$. Then a basis of $F$ over $K$ of the form $\{\alpha, \alpha^q, \ldots, \alpha^{q^{m-1}}\}$, consisting a suitable element $\alpha \in F$ and its conjugates with respect to $K$, is called a normal basis of $F$ over $K$

Note: these two are not the only basis that we can form, these two is the well-known basis.


Are timing attacks exploitable if each key is used only once?

Yes.

Let's a thought experiment and not limit this to AES-GCM.

A very trivial example:

$M = \{0, 1\}$ (a one bit message)

$K = \{0, 1\}$ (a one bit key)

$E(m, k) = m \oplus k$

Let's say with this implementation the computation takes 100x as long if $k = 1$. Running this function only one time will give you a pretty good idea what k is based on how long it takes.

Again, this is just a trivial example meant for a thought experiment as to why you wouldn't necessarily need the encryption process to go more than once.

Another case might be that the plaintext has a series of repeated texts. All of which will be computed against the same key. This can be (not always) similar to computing a single plain text several times.


What methods would they use?

Since WW2, we know the security of Enigma machines was weakened by the reflector, resulting in two problems:

No difference between en- and decryption, which means that if K ↦ T, then T ↦ K.
No letter can be encrypted by itself because electricity can not travel the same way back, which results in a reduction of encryption alphabet.

Also, history has shown that Enigma had another security problem: the contradiction to Kerckhoffs' principle "The security of a system should not depend on the privacy of the algorithm. It should only be based on the secrecy of the key.".

Enigma got it wrong because:

Security of Enigma depended on wiring of rotors,
Wiring was part of algorithm and not part of key, and
Wiring never changed from 1920s until 1945.

(source: https://www.infsec.cs.uni-saarland.de/teaching/SS07/Proseminar/slides/maurer-Enigma.pdf)

Since you're asking about today, I will therefore assume the fact that we know about the internal workings of Enigma since WW2.

Based on your assumptions and the known Enigma weaknesses, one of the well-known attacks to break Enigma is using the Index of Coincidence (short: IC), a statistical measure of text which distinguishes text encrypted with a substitution cipher from plain text.

Let's put Enigma into the formula: $IC = \frac{{\textstyle \sum_{i=0}^{25} } f_i(f_i-1)}{n(n-1)}$ where $x_1,...,x_n$ is the string of letters and $f_0,...,f_{25}$ the frequency of the letters in that string. For a random string that boils down to $IC ≈ 0.038$ and for a natural language $IC ≈ 0.065$.

I'll skip the details and simply give you some raw numbers while summing up how IC can be used for an attack on Enigma:

Find the rotor order
Trying all rotor orders and positions searching highest IC takes $60*26^3 ≈ 2^{20}$ operations.
Approximation to rotor start positions
Starting with a rotor order from step $1$ and $w$, trying all rotor positions and ring positions for 1st ring only, again searching highest IC. That takes $26^4 ≈ 2^{19}$ operations.
Find ring and rotor start positions
We have the 1st ring and 1st rotor start positions, approximations
for other rings and starting positions from 1 and 2. First search positions for the 2nd ring and rotor, then use the same procedure for last remaining rotor. This will take $26^2 ≈ 2^9$ operations.
Find the plug settings
We have the rotor order, position and ring positions. Now we can use IC as statistical test again, deriving of the trigram information of the underlying language.

  how fast/ how easily could they do it?

Generally, that's hard to say without having any specific information about available resources you are assuming an attacker would have.

A single computer might take a little while depending on how old it is (in terms of CPU power), but things like distributed networks will probably make you cry by successfully attacking Enigma in a few blinks of an eye. If you happen to have any specific computing setups in mind, you can take the provided number of operations mentioned above and simply do the related maths to calculate the related speeds.

And last but not least - to answer the title of your question too...

  How cryptographically secure was the original WW2 Enigma machine, from a modern viewpoint?

Totally insecure. The weaknesses described above provide ample proof to that claim.

On the other hand, we can't really compare today with the situation during WW2. They used machines that were mainly mechanical (eg: Bletchley Park Bombe), while we have computers with powerful CPUs. WW2 cryptanalysts  would probably have killed to get their hands on such a futuristic "wunder Maschine" which we use to do simple things like surf the internet.

Nota Bene: If you're interested in the maths behind Enigma, you might want to check on "The Cryptographic Mathematics of Enigma" by Dr. A. Ray Miller, The Center for Cryptologic History – National Security Agency.

The above publication certainly provides more insights related to the internals and maths behind Enigma than the usual NSA "freebee" stuff (PDF) which tends to restrict itself to talking about the history instead of cryptography.

Edit: The last two links are now offline and seem to have been removed from the nsa.gov website. As they are still available via web.archive.org, the links have been updated point there.


Choices of $q$ and $f$ for RLWE-based constructions

Why use $f(x) = x^{2^n} + 1$?

This is a very special polynomial called a "cyclotomic" polynomial. Cyclotomic polynomials are very interesting, and I recommend reading up on them separately  (wikipedia). One very useful property is that the $m^{th}$ cyclotomic polynomial has roots that are all the $m^{th}$ primitive roots of unity. For any $n \geq 1$, the polynomial $f(x) = x^{2^n} + 1$ is the $(2^{n+1})^{th}$ cyclotomic. Power-of-two cyclotomics are even more convenient because they allow for much faster NTT algorithms (see Cooley-Turkey style optimizations, where having a power-of-two length is important for the recursive structure of the algorithm). Here is a nice paper on NTT optimizations.

Where does CRT come in?

This will also answer your third question, since $q$ need not be prime, and this is necessary to implement CRT optimizations. The problem that arises with RLWE-based secure computations is that the modulus $q$ must grow to be much larger than the typical machine word, which is usually 64 bits. Since $q$ need not be prime, we can use a modulus $q$ that is the product of many small primes $q = \prod_{i=0}^{\ell-1} q_i$. CRT makes use of the following isomorphism:
$$ \mathbb{Z}_q \cong \mathbb{Z}_{q_0} \otimes \mathbb{Z}_{q_1} \otimes \ldots \otimes \mathbb{Z}_{q_{\ell-1}} $$
This is what allows the implementations to work with each $q_i$ separately instead of the full $q$. This also allows for parallelization. For more information on this isomorphism and how it's useful in RLWE implementation, I recommend this paper.


Calculating the amount of zero bits to be appended to the message

If you have an implementation of an integer modulo operator, then

$$k = (447 - l) \bmod 512$$

should be the right solution. If your modulo operator can return negative results, do this:

$$k = ((447 - l) \bmod 512 + 512) \bmod 512$$

This seems simpler than using your division and flooring.

That said, you actually don't really need the number of zero bits for the padding, but you need to know how many 512-bit (e.g. 64 byte) blocks to hash. These then will be filled by:

the data
one 1 bit
a number of 0 bits (between 0 and 511, to fill the block)
the length, encoded as a 64-bit number.

We need just enough ($b$) blocks to have space for the data and the length (and the one 1-bit):

$$ b = \left\lceil \frac{l + 1 + 64}{512} \right\rceil $$

If you hash only data in whole bytes (as usual), the formula becomes

$$ b = \left\lceil \frac{l_8 + 1 + 8}{64} \right\rceil, $$

with $l_8 = \frac l8$ the length of the data in bytes.


As long as the two primes are large and random, and ideally approximately the same size, they will be suitable for a secure implementation of RSA. For an $n$-bit RSA key, it's generally safe to generate two $n/2$-bit random primes. As long as the two primes are generated randomly using a cryptographically-secure random number generator, they can be used securely. The difficulty comes in quickly and accurately determining whether or not an integer is prime, but luckily there are probabilistic algorithms like the Miller-Rabin primality test which are quite effective when run a sufficient number of times.

The most common method of generating random primes involves generating a large, random odd integer and checking if it is prime. If it is not, then it is incremented by two and checked again. This repeats until it is prime. Note that this method does not find perfectly-distributed primes. It is biased towards primes with large gaps between it and the previous prime. However, there are no known ways to exploit this bias and it is believed that none exist. The alternate, slightly slower method of finding primes is to generate a random odd integer and check it for primality. If it is not prime, then rather than adding two and checking again, a new independent integer is generated and checked for primality.

If you want to use a standard for prime generation, consider FIPS 186-4, which should be safe.


Why is $H(k\mathbin\Vert x)$ not a secure MAC construction?

The word "secure hash function" usually means (for a function $H$)

Preimage resistance: Given a value $h$, it is hard to find a message $x$ so that $h = H(x)$.
Second preimage resistance: Given a message $x$, it is hard to find a message $x' \neq x$ such that $H(x) = H(x')$.
Collision resistance: It is hard to find two messages $x$, $x'$ such that $H(x) = H(x')$.

For a secure MAC function $M$, we want:

Unforgability: Without knowing the key $k$, it is hard to find a message $x$ and authentication tag $m$ such that $m = M(k, x)$, even if given some other such valid message-tag pairs (which are not allowed as answers).

Unfortunately, defining $M(k,x) = H(k \mathbin\Vert x)$ for a secure hash function does not guarantee that the MAC function is unforgeable.

In fact, with the hash constructions used in practice (i.e. the Merkle-Damgård construction without a finalizing round, used in MD5, SHA-1 and the SHA-2 family), it is quite easy, given a valid pair $(x,m)$, to create an $(x', m')$ which is still valid:

To create a hash with Merkle-Damgård, the message is padded to some block size, and then each block in sequence is feeded to a compression function, which updates an internal state. The final state is then output as the hash.

So, $H(k\mathbin\Vert x)$ is the state of the hash machine after inputting $k\mathbin\Vert x\mathbin\Vert\mathit{pad}_x$. If we set our hash machine to this state, and then input arbitrary other data $y$, followed by another pad $\mathit{pad}_y$, we reach the state $m' = H(k\mathbin\Vert x\mathbin\Vert\mathit{pad}_x\mathbin\Vert y) = M(k, x\mathbin\Vert\mathit{pad}_x\mathbin\Vert y)$.
Forgery is done, with $x' = x \mathbin\Vert \mathit{pad}_x \mathbin\Vert y$.

This also works with the full-width variants of SHA-2, i.e. SHA-256 and SHA-512. For the truncated variants of SHA-2 (SHA-384, SHA-224, SHA-512/224 and SHA-512/256) this attack doesn't work, as the output is not the full hash state. (Though for a length extension attack only the truncated bits would have to be guessed, so the security is a bit less than expected from the output size.)

The HMAC construction is not suspectible to this attack, as the secret key $k$ is applied both before and after the main message, which makes the internal state non-reconstructible.

HMAC does not guarantee unforgability for general secure hash functions, either, but it has a security proof for the Merkle-Damgård construction, if the internal compression function is collision-resistant.

SHA-3 (Keccak) is based on a different model: we have a quite big state into which both key and message are mixed, and which is then further mixed to output the hash. The state itself is never output fully. Because of this, length extension needs state recovery, and the capacity (the hidden part of the state) should be big enough that this is not feasible (as well as guessing the key).

The paper On the security of the keyed sponge construction by the Keccak team analyzes the security of this construction.


OK, let's go over them:

Fail-Safe Defaults: this is the most important one, as a CRL doesn't provide on-line information and may not be available or out-of-date;
Economy of Mechanism: a CRL may contain information about many certificates, so the mechanism isn't as economic as it could be;
Complete Mediation: CRL's are public info while complete mediation is about access control and therefore this rule is not applicable;
Open Design: well, CRL's are an open standard as well - as part of X.509 and the derived RFCs, so it complies;
Separation of Privilege: privilege separation is not on topic here, both CRL's and OCSP's are generally performed by the same entity;
Least Common Mechanism: possibly the ASN.1 parser is shared with the X.509 certificate, but if the ASN.1 parser of the certificate is broken then you're already in trouble, I don't see how it applies here;
Psychological Acceptability: I guess nobody complains if certificate is refused because of a CRL and certainly nobody complains if it isn't, so this isn't really applicable.

Note that OCSP - the online certificate status protocol - does provide a positive way of knowing if a certificate is valid at that time or not. However, you still face the same issue if the OCSP server cannot be reached. Generally the certificate should not be accepted, but this is often configurable. Besides that, OCSP requires a higher availability of the service.

I'd hazard that the private key could be known to be exposed while the CRL is still valid is the biggest issue; without an online protocol it certainly doesn't comply fully with Fail-Safe Defaults.

However, your professor should not leave you guessing; ask your professor what was meant!


complete functionality for fair multiparty computation

The functionality that this paper refers to when speaking about "fair decryption" is probably the "fair reconstruction" functionality from [GIM+10].

In secure computation we say some cryptographic primitive is complete if we can use it to implement any ideal functionality (in some setting). One can think of complete primitives as the sufficient requirements for secure computation. For example, we know that one can securely compute any desired functionality if one has access to oblivious transfer as a building block.

Roughly speaking, [GIM+10] shows that fair reconstruction is complete as follows:
All parties first execute any unfair secure computation protocol that outputs (non-malleable) secret shares of the output.
The parties then run the fair reconstruction function, which returns the reconstructed secret.


Yes, Pailler encryption can be generalized to the product of more than two (distinct) primes, much like in multi-prime-rsa. We just have $N=\prod p_i$ with $i\ne j\implies p_i\ne p_j$. Each $p_i$ must be secret and uniformly random in some large interval. It we want to use $g=N+1$ as the generator (which is common) without an explicit check of its order, it remains enough to ensure that $2\min(p_i)>\max(p_i)$. For $n$ primes, choosing $p_i$ as a random prime in $(2^{1024-1/n},2^{1024})$ ensures that, and that $N$ is exactly $1024\,n$ bits, and may simplify code using the last section's speedup by making all the primes standard-sized. For a working random prime generator and reasonable $n$, odds of hitting two equal factors or enabling a Fermat factorization remain negligible.

For the other steps of key generation, and for decryption, it is enough to compute $\varphi(N)$ or/and $\lambda(N)$ correctly:

$\varphi(N)$ is the product off all the $(p_i-1)$
$\lambda(N)$ is the Least Common Multiple off all the $(p_i-1)$

There's noting special to do for encryption; in fact there is no way to recognize from the public key if $N$ is the product of two or of more large primes.

If we want a speedup at decryption, we have the option to compute $c^{\lambda(N)}\bmod N^2$ (which is where most of the computation effort is spent) by computing $c^{\lambda(N)}\bmod{p_i}^2$ separately for each $p_i$, and using the Chinese remainder theorem to obtain the final result. That works like there, except

for the moduli $r_i$ there, we use ${p_i}^2$
for their reduced exponents $d_i$, we use $\lambda(N)\bmod\lambda({p_i}^2)$, that is $\begin{align}
d_i&=\lambda(N)\bmod(p_i(p_i-1))\\
&=\left(\frac{\lambda(N)}{p_i-1}\bmod p_i\right)(p_i-1)
\end{align}$.

The speedup obtained by using the CRT is by a factor about $n^2/2$ (with classical mulmod algorithms of cost proportional to the square of the number of bits); that's about half the speedup in multiprime RSA, because in Pailler the exponent $\lambda(N)$ has about half as many bits as the modulus $N^2$, whereas in RSA the exponent $d$ has about as many bits as the modulus $N$.


Find the generators of multiplicative group of units efficiently?

For any $g$ in the set $\mathbb Z_p^*=\{1,2,\dots,p-1\}$, consider the function $F_g$ over that set defined by $F_g(x)\;=\;g\cdot x\bmod p$. Since $p$ is prime, by Fermat's little theorem, iterating $F_g$, starting from $1$, $p-1$ times, cycles back to $1$.

By definition, $g$ is a generator of $\mathbb Z_p^*$ if and only if that cycling does not occur before these $p-1$ iterations. The smallest $k>0$ where the cycling occurs divides $p-1$ (that $k$ is the order of $g$). Proof sketch: if that $k$ did not divide $p-1$, $k'=(p-1)\bmod k$ would be a smaller $k'>0$ for which the cycling occurs.

It follows that we can test if some $g$ not divisible by $p$ is a generator of $\mathbb Z_p^*$ by checking if $g^k\bmod p\ne1$, with $k=(p-1)/q$ for $q$ each of the distinct prime factors of $p-1$.

Here, for $g$ each of the integers in list $L$, we check if $g\bmod p\ne0$, and $g^{(p-1)/2}\bmod p\ne1$, and $g^{(p-1)/p_1}\bmod p\ne1$, and $g^{(p-1)/p_2}\bmod p\ne1$, and $g^{(p-1)/p_3}\bmod p\ne1$. In the affirmative, and only then, $g$ is a generator of $\mathbb Z_p^*$.

Additions:

Computing $g^k\bmod p$ is feasible with a modest computer, and common, for integers of many thousands of bits: $2\log_2(k)$ modular multiplications are enough to compute $g^k\bmod p$; see modular exponentiation.
If the list $L$ was not a given, we could try $g$ at random (or small primes by increasing orders, which is slightly more efficient than trying small integers by increasing order). If all the primes dividing $(p-1)/2$ are large (which is the case here), nearly 50% of candidates will work, thus a search won't be too long.
Often, we want a generator of a subgroup of order one of the large primes dividing $p-1$, say $p_3$; we can get that as $g'=g^{(p-1)/p_3}\bmod p$.


Concept of hashing a group of data and validating if a value exists within the group

It sounds like you're describing a Bloom filter.

Note that they're designed to allow false positives (but not false negatives). They can be good to quickly check whether a value might be in a certain set worthy of a more computationally-expensive check. Imagine that you are scanning a large body of text word by word, there is a set of key words you're looking for, and there are more key words than fit in RAM. You can create a bloom filter out of all of the key words that fits in RAM. Whenever you find a word that passes the bloom filter, that means the word might be a key word, so you can then double-check the word against your list of key words on disk. This saves you from having to access the disk for every word you scan.


Safety of encryption when knowing part of the content

If you use any reasonably standard modern encryption scheme, there's no need to worry. Ideally you should be using authenticated encryption like AES-GCM.
In modern cryptography we generally require an encryption scheme to at least have IND-CPA security to call it secure. IND-CPA stands for "indistinguishability under chosen plaintext attacks".
This security notion is defined as a game between a challenger and the attacker. The challenger chooses a key for the encryption scheme. The attacker can then query any ciphertext of their choice to the challenger and receives an encryption that plaintext. Eventually, the attacker outputs two challenge plaintexts $m_0,m_1$, the challenger flips a random bit $b$, and gives an encryption of $m_b$ to the attacker. The attacker can continue to make queries as above and eventually has to guess which message was encrypted. In an encryption scheme that is IND-CPA secure an efficient attacker can essentially do no better than guessing randomly.
The attack you are worrying about is much much weaker than what we consider the minimal security required of an encryption scheme. Any sane implementation of AES-CBC, AES-CTR or a modern stream cipher like Salsa/Chacha would be secure in this sense. (Even 3DES in CBC or CTR mode is fine, though horribly slow.)
In practice malleability of ciphertexts is often an issue, which is why it's generally advised to use "authenticated encryption", which prevents any modifications of the ciphertext.


To start with, it's certainly not a bad idea to avoid SHA-1 when other algorithms exist, which do not have the SHA-1 weaknesses to anyone's knowledge.

The security of SHA-1 depends on how you're using it. The vulnerability is what's known as a collision vulnerability: an attacker has the ability to create two input strings with the same SHA-1 hash with less computational power than it should take him for a good hash function. However, he does not get to freely pick what either of those input strings is, and he does not necessarily have the ability to feasibly find a string whose hash matches that of any particular string.

If the attacker has any control over anything you're willing to sign, collision attacks might be exploitable. The classic example is two PostScript files; one is a letter of recommendation for an employee named Alice, the other a security clearance for Alice, and they hash to the same MD5 value. Alice presents file 1 to her boss, and then affixes that signature to file 2, now having obtained a security clearance. Likewise, with TLS certificates, security researchers made 2 colliding-under-MD5 certs, one a legitimate one and one a CA one, got the former signed by a real CA, and that signature was valid for the latter. What these have in common is that someone is signing off on something that they did not entirely create. If that describes what you're doing, you should certainly not use SHA-1.

If you entirely create the files you're signing, it's probably fine for now; in that case, the only person who could exploit a collision attack is you, and you're the person who doesn't need to exploit it (you could just sign whatever you want). Also, as far as anyone's aware, no one yet has the hardware to exploit the collision attack (that's likely at least a year off, and more till it's cheap enough for non-high-value targets).

But honestly, why risk it? Just use SHA-2 instead. CryptSignMessage supports it as well, it looks like.


AES-256-CBC with random IV - storing same plaintext as same ciphertext

I often read that it is a weakness to have the same ciphertext for the same plaintext, but I was wondering if this weakness is no longer present if you use a random IV each time to encrypt the data.

The weakness is still present. It would be mitigated if, for equal plaintexts, you generated different random IVs when encrypting. Using different IVs for equal plaintexts would then yield different ciphertexts.

Why would you want different ciphertexts? Consider the scenario where you have a database with two columns, a VARCHAR username and a BOOLEAN has_some_horrible_disease. Suppose you encrypt the has_some_horrible_disease column for privacy purposes using the scheme you describe. One day an attacker compromises the database and has access to all the data. Suppose the attacker knows that username "johnsmith" has a value of "true" for has_some_horrible_disease (this is not farfetched, all they have to do is e.g. create an account and set their data to the target values).

The issue is that you just leaked the has_some_horrible_disease values for every single user! Why? Because the encrypted value for user "johnsmith" is the same for every other user who has has_some_horrible_disease set to "true". In other words there's a 1-to-1 mapping from encrypted value to cleartext value. If you used a random IV this would not be the case, every value in has_some_horrible_disease would be unique to that row (with extremely high probability).


What should the size of the private exponents in Diffie-Hellman key exchange for TLS be?

Diffie-Hellman exponents need at a size at least twice the security level.

So for elliptic curve DH you need the same size as the underlying field. For example 256 bits for P-256.

For finite-field DH you still need twice the security level as exponent, but significantly larger fields. For example for an 80 bit level you need 160 bit exponents and a ~1024 bit field.


You wrote in the comments:

  no, I am only interested in the MAC generation using Poly1305 with a key that is always been freshly generated for each execution of the MAC function. The key is derived using an HKDF with a shared DH key and a random value for each execution (e.g. a nonce).

In the same RFC that you mention it is written (quoting Bernstein's paper):

  The original article ([Poly1305]) is titled "The Poly1305-AES
     message-authentication code", and the MAC function there requires a
     128-bit AES key, a 128-bit "additional key", and a 128-bit (non-
     secret) nonce.  AES is used there for encrypting the nonce, so as to
     get a unique (and secret) 128-bit string, but as the paper states,
     "There is nothing special about AES here.  One can replace AES with
     an arbitrary keyed function from an arbitrary set of nonces to
     16-byte strings."

Now you've got HKDF, which is a keyed function, a nonce and an output which can be made 16 bytes. I say: go for it, but don't use the key for anything else, including ChaCha20 encryption or worse, calculating another authentication tag.

Just for reassurance: do please use SHA-256 or better for HKDF. Then it should be just as secure.

Do remember that you're now in unchartered territory. That means using libraries to implement this kind of functionality will be harder, compared - for instance - to just using the AAD of a ChaCha20/Poly1305 cipher to calculate a MAC.


Mitigating the damage when a signing key is stolen

A standard solution is to have keys with limited validity keys and a separate, possibly offline long term key signing key. The signing server holds only one key, so even a total comprise of the server won't reveal future keys.
Before the active key expires, the server gets a new key signed by the master key and starts using it.
We also use certificate revocation lists. If we suspect a key has been compromised before the end of it's validity we not only switch to a new key we publish a revocation of the previous key publicly signed by the leaked key or master key. Verifiers can check this list before trusting a signature.

This setup works rather well with https protecting communications. But is less suitable for signing docyments where you will want document signatures to remain valid for a long time. Even after a key expires or is revoked.
Blockchain works welll here and relies on hash functions rather than assymetric ciphers. If you publish a chain of hashes of everything signed with it's time stamp it is difficult to back date a signature as it isn't in the chain. Making many copies of this around the internet or even use an existing blockchain is one way to make such records tamper resistant. You could simply sign the tip of the chain with current active key. And allow an interactive verifier to get high confidence on old documents because you essentially keep resigning everything you signed in the past.


According to Introduction to Modern Cryptography by Katz and Lindell, in the section titled Security of DES on page 218 in the second edition.

  After almost 30 years of intensive study, the best known practical attack on DES is still an exhaustive search through its key space... Unfortunately, the 56-bit key length of DES is short enough that an exhaustive search through all $2^{56}$ possible keys is now feasible.

They go on to say (a few paragraphs down):

  The insecurity of DES has nothing to do with its design per se, but rather is due to its short key length... Since DES itself seems not to have significant structural weaknesses, it makes sense to use DES as a building block for constructing block ciphers with longer keys.

So I would say that yes, the main limitation of DES is the key size.

That book goes on to state the secondary cause for concern as the short block length of 64-bits.


Yes, it can make some sense, and I've seen it in practical use. But beware that you can only encrypt very small plaintext and that's only after you make adjustments to the MGF-1 scheme to use a smaller hash (the leftmost bits of an existing hash, for instance).

For a generic cryptosystem you could use a large (512 bit) curve and use hybrid cryptography to get around the small payload size. But for a generic cryptosystem you are much better off using ECIES to accomplish the same thing.

I would only use El Gamal / OAEP if the ElGamal encryption has specific properties that you want to use.


Rock-paper-scissors over network, how to protect from cheating server?

If they don't trust the server they sure shouldn't send any money. The "trusted" third party is used to solve the problem of participants who don't trust each other. So by definition, your problem can only be somewhat mitigated, not solved completely.

I'm not sure what you mean by "provably fair". If the server can't prove he cannot cheat, it's not provably fair.

One way to do that is to award the bet to the remaining player if one leaves the game for any reason. Now if the server decides to keep the money by becoming unresponsive, Alice will know not to trust that server in the future, instead of keep losing money to it.

Another is to start communicating with Bob before the game begins and agree on a server at random. Now the probability of a server ripping off Alice is equal to the probability of Bob colluding with that server.

Lastly rock-paper-scissors doesn't depend on some input from the server, so the server can't prove fairness ahead of time.


Pseudo preimage for a hash made from a cipher

This problem reduces to a standard preimage attack: if the solution can be found faster than with  $2^l$ trials, then a full preimage can be found faster than $2^n$. The latter problem is considered difficult for iterated hash functions based on the Miyaguchi-Preneel construction, as the latter is difficult even when the IV is not fixed.


Is this RSA signing and verification process secure?

Comments already pointed out, that encryption and signing are not the same and should not be exchanged deliberately. Of course in practice specifically for RSA, not PKE in general, and only in the textbook variant (no padding), encrypt/decrypt are bascally the same operations as sign/verify: For all of them, you just do modular exponentiations; and the defining properties of the keys (the product of the public and private exponents equals $1$ modulo $\phi(N)$) are analogously.

But considering your algorithm, there are flaws. First, your algorithm for signing is actually this:

Hash the message
"rsa_encrypt"the hash with a private key

First, if we interpret "rsa_encrypt" just as modular exponentiation, this is still just textbook-RSA without any proper padding , which is vulnerable to certain attacks and usually the padding scheme PSS is recommended. (also see wiki)

And then you have the implicit assumption, that your function call actually is the plain modular exponentiation: If you call "rsa_encrypt" from a cryptographic library, are you actually sure that it is just the modular exponentiation? It could e.g. already have soem kind of padding in there, which might be unsuitable for signatures. Or did you implement the function yourself? Because then of course there is the old saying "don't implement crypto yourself" (and the question doesn't sound like homework), and for good reasons any proper cryptographic library will offer separate methods for signatures and encryption. In the implementation details, there are quite a lot more differences when it comes to side-channels, performance improvements, etc.

I would recommend, try to get rid of your current primitives, and use a cryptographic library instead, which gives you proper signature algorithms. Other than that, you are e.g. generating the random key for the symmetric part of the hybrid encryption. You shouldn't have to do that manually, because it is another possible weakness (you have to ensure that you're using a proper CSPRNG). But most cryptographic libraries should also have that functionality.


Can we calculate the "previous hash value" in the SHA256 compression function with a known message block and final hash?

Can we compute the intermediate hash $H_n$ using just the fully known final message block, and the final hash output $H_{n+1}$?

No, that's computationally infeasible. The only known way to find $H_n$ is when we know all (or enough of) the message, which allows to directly compute $H_n$ in the forward direction (or use brute force search of a small unknown fraction of the message, validating a guess by checking if the final $H_{n+1}$ matches).
The reason we can not compute $H_n$ is that the Davies-Meyer round function $(H_n,M_n)\mapsto H_{n+1}$ restricted to fixed known $M_n$ is computationally difficult to invert.
That follows from its construction as $H_{n+1}\gets E(\text{key}\gets M_n, \text{block}\gets H_n)\boxplus H_n$ where $E$ is a public block cipher and $\boxplus$ is a group operation¹ on $\{0,1\}^{256}$ (256-bit bitstrings).
If some fairy told us the output $X$ of $E(\text{key}\gets M_n, \text{block}\gets H_n)$, and since we know $M_n$ and $H_{n+1}$, we could find $H_n$ in two ways:

by using the decryption function $D$ matching $E$, with $H_n\gets D(\text{key}\gets M_n, \text{block}\gets X)$
by inverting $X\boxplus H_n\mapsto H_{n+1}$ to find $H_n$ from the known $H_{n+1}$ and the $X$ given by the fairy.

But we have no fairy, and there is no known way out of this chicken-and-egg problem. That's even provable under a model of $E$ as an ideal cipher. That's by design of the Davies-Meyer round function.
Also: it is likely that for a sizable fraction of the final hash $H_{n+1}$ and message size (equivalently, values of $M_n$ ), the known relation $H_{n+1}=E(\text{key}\gets M_n, \text{block}\gets H_n)\boxplus H_n$ leaves several possible values for $H_n$.

¹ $\boxplus$ happens to be addition of 256-bit bitstrings ignoring carry bit between blocks of 32 bits.


Is it possible to perform a meet-in-the-middle within a block cipher?

Meet-in-the-middle attacks can indeed be used for block cipher (but also hash function) cryptanalysis. As mentioned in the question, this goes back to Diffie and Hellman's analysis of DES. However, when applied to primitives, one typically uses more sophisticated techniques. Since the literature around this topic is very extensive, I won't go into the details of all techniques but I'll instead try to provide the main references.

The first four sections of this answer discuss variants of the classical MITM attack. These attacks are the most similar to the attack on 2DES that you refer to.
Probably the most interesting aspect of classical MITM attacks is their low data complexity, which makes them attractive from a practical point of view. There are some exceptions to this, though (bicliques being the most notable).

The last section, however, argues that the general MITM idea is even more widespread in cryptanalysis. That is, many statistical attacks are supplemented with a phase that can reasonably be called a MITM step. A good example of this is the Demirici-Selçuk attack.
Here, the data requirements are usually larger.

Basic MITM attack

The classical MITM attack is easy: one splits the cipher in two parts with independent keys, say $K_1$ and $K_2$. For each guess of $K_1$, compute the intermediate state by evaluating in the forward direction. Similarly, the intermediate states are computed for each guess of $K_2$ by evaluating in the backward direction. The candidate keys are those for which the intermediate states match.

The main issue with this simple approach is that, after a few rounds, it is likely that too many key bits must be guessed in order to obtain the intermediate state. (Leading to a blow up of time and memory requirements.) Of course, the key schedule plays an important role here. For example, MITM is typically useful in block ciphers with a small block size but a larger key size.

The basic MITM attack has been applied to DES itself (so not just 2DES), and several improvements have been introduced since. For example, you can take a look at Improved Meet-in-the-Middle Attacks on Reduced-Round DES by Dunkelman, Sekar and Preneel (INDOCRYPT 2007). Some dedicated tricks are used there; more advanced and generic variants are discussed below.

3-subset MITM

A common improvement over the basic attack was introduced by Bogdanov and Rechberger at SAC 2010.
In these attacks, one splits the cipher into three parts. For each guess of the key bits that are involved in the second and third part, one matches the forward and backward guesses but this is done based on only part of the state (partial matching). This makes it possible to cover additional rounds in the middle part. The downside is that partial matching leads to more false-positives, so you end up with a larger list of key candidates.

The recent attacks on GIFT by Sasaki that I mentioned in the comments are based on this 3-subset technique. In addition, he uses the "splice-and-cut" and "initial structure" techniques that originated in preimage attacks on hash functions (see next section). That work uses MILP modelling to optimize such MITM attacks on GIFT. The reason I mention it is because the simple structure of GIFT makes it a good introduction to such attacks.

Influences from hash function cryptanalysis

The use of MITM techniques to find preimages of hash functions goes back a long time, at least since Lai and Massey (EUROCRYPT 1992) (and probably earlier). For example, this technique is used in Leurent's preimage attack on MD4 from FSE 2008.

Soon after, a number of improvements were proposed by Aoki and Sasaki. In particular:

The splice-and-cut technique, introduced at SAC
2008,
with applications to MD4 and MD5.
Initial structures (as a generalization of local collisions) at EUROCRYPT 2009.

They also applied these techniques to reduced SHA-0 and SHA-1 at CRYPTO 2009. There are also several follow up works here, such as the additional improvements of Guo et al. with applications to SHA-2.

Generally speaking, this so called "splice-and-cut framework" led to major improvements in preimage attacks on hash functions. Of course, these attacks are about message recovery as opposed to key recovery. Nevertheless, the same principles can be applied to block ciphers.

The biclique, due to Khovratovich, Rechberger and Savelieva, is another tool that was initially introduced for preimage attacks. In these attacks, bicliques replace initial structures.
Bicliques were also (famously) used for key-recovery attacks on full-round AES, see the ASIACRYPT paper by Bogdanov, Khovratovich and Rechberger.

Other variants

Other variants that are worth mentioning are multidimensional MITM attacks (as mentioned in the question, some information can be found on Wikipedia), all subkeys recovery and sieve-in-the-middle attacks.

The all subkeys recovery attack is a way to deal with more complex key schedules. This is due to Isobe and Shibutani.

A sieve-in-the-middle attack is a generic improvement due to Canteaut, Naya-Plasencia and Vayssière, CRYPTO 2013. The idea is to replace (partial) matching by a sieving process which discards invalid transitions for a middle S-box. The middle S-box can be a superbox, so you can gain e.g. 2 rounds in many ciphers.

MITM as a general idea (including Demirici-Selçuk)

The first/last round trick as used in linear and differential cryptanalysis is basically a kind of MITM attack. At least in some cases, the number of rounds for which partial subkeys are guessed can be quite large, so that one essentially divides the cipher in three parts and performs matching in the middle using e.g. a linear approximation. Of course, here, there are again a bunch of specialized techniques.

Usually, the most significant part in such attacks is finding the right statistical properties as opposed to the key guessing part. This sets them apart from the MITM attacks described above and hence they are not usually referred to as MITM attacks.

A good example of an attack that is universally referred to as a MITM attack, but which doesn't belong to one of the MITM attacks described in the above sections, is the Demirici-Selçuk attack.

The basic DS-MITM is an attack on the AES based a 5 round distinguisher. Note that this distinguisher is not really a (simple) square attack. Rather, it's an extension of a 4 round distinguisher due to Gilbert and Minier which in turn extends the classical integral/square distinguisher for 3 rounds of the AES. The 5 round distinguisher is extended to 7 or 8 rounds by partial key guessing. I won't go into the details (this should probably be a different question).

Just to give a glance of the importance of this attack, here's a brief chronological overview of follow-up research on this topic:

Some improvements are given by Demirici et al. in Improved
Meet-in-the-Middle Attacks on AES at INDOCRYPT 2009.
Dunkelman, Keller and Shamir presented improvements in Improved Single-Key Attacks on 8-round AES at ASIACRYPT 2010. They introduce multiset tabulation, differential enumeration (main improvements) and key bridging.
Derbez, Fouque and Jean gave further improvements at EUROCRYPT 2013 in Improved key recovery attacks on reduced-round AES in the single-key setting.
Other imrovements by Derbez and Fouque at FSE 2013 in Exhausting  Demirci-Selcuk Meet-in-the-middle Attacks Against Reduced-round AES.
Li, Jia and Wang (FSE 2014) use use key-dependent sieving to obtain a better 5 round distinguisher (leading to improvements in the 9 round attack).
The latest (from 2016) improvement that I'm aware of is due to Li and Lin and extends to 10 rounds (note: this is for AES-256).

The DS-MITM attack also applies to other ciphers. For instance, this paper from ASIACRYPT 2018 uses constraint programming to automate the process with applications to several lightweight ciphers. Not all of the extensions (in particular differential enumeration) are automated though.


It depends on what you think of as an alternative.

If you think of the scheme where you do not use $M$ as a modulus, but the keys a picked as:
$$
k \leftarrow \{1, \ldots, M-1\}
$$
Encryption:
$$
C = d + k
$$
Decryption:
$$
d = C - k
$$
Then the scheme is insecure. One way to see this is to note that we have $C \geq d$. So the ciphertext communicates the information that $d \leq C$.

You could also think of a scheme where there is no $M$ at all:
$$
k \leftarrow \mathbb{Z}
$$
Encryption:
$$
C = d + k
$$
Decryption:
$$
d = C - k
$$
This would be secure, however, it would be impossible to implement because there is no way to sample $\mathbb{Z}$ (the integers) uniformly at random (think about it, how would you do that?).

So you see $M$ is really quite essential to the scheme.


What is the best algorithm for compressing a hash?

What's better? Displaying more information than 4 bytes will be more secure mathematically speaking. However, it is unlikely that people will check all those bytes. Those bytes are more for identification than for authentication / security anyway. You could use a different alphabet than hexadecimals, say base 64, but I'd argue that that would be harder to remember, especially if more than 4 bytes are used.

For the 4 bytes it doesn't really matter. They only represent somewhat over 4 billion possibilities (using the short scale) and generating the same 4 bytes will be easy whatever hash function is used. The switch from SHA-1 to SHA-256 is about the full hash used internally.

The switch to SHA-2 is important in my opinion. Or it is at least important enough to make the switch. I haven't been swayed by Linus arguments yet, but that's mainly because I don't have a full overview of the vulnerabilities. However, I haven't seen a good argument why there wouldn't be an attack possible either. And the difference in speed really isn't worth to taking any risk.

A note about the wording: taking the first 4 bytes from a hash is not compression. Compression (as in the common meaning, such as the DEFLATE used by zip archives) is performed over all the bits, and tries to pertain some essential (or for lossless compression all of the) data. As explained in the comments below, compression of the output of a hash is an act of futility.

In cryptography compression has a different meaning. But the output must also depend on all the input bits.

Anyway, just removing the rightmost bytes from a hash is not the same thing.


Does security under ROM imply exactly what?

If you can show a reduction of a security property of your protocol to the security of a hash function is the standard model, you do not need the random oracle assumption. So a proof in the ROM does not have any general (positive) meaning in the SM; hence why it is controversial. About the only general thing you can say is that some (arguably highly contrived) protocols that are secure in the ROM are insecure in the SM with a concrete hash function.

The value of a ROM proof is that it still narrows the range of attacks possible on a protocol. Unlike an unproven protocol where it could break in any number of ways, a ROM protocol will only break if the hash function does not live up our theoretic expectations of it. Further, no "natural" protocol that is secure in the ROM has ever been broken.

There is a good discussion in Katz-Lindell. Basically their conclusions is, a ROM protocol is better than no proof. A SM protocol should be preferred up to a reasonable decrease in efficiency.

A RO needs to return the same output value if queried on the same input. That is essentially why quantum randomness does not work.


Multiple XML files and known-plaintext attack

First, don't use AES directly.  AES itself is a pseudorandom permutation family, and if you don't understand what that means, then it's not a good fit for your application.

What you should do is use an authenticated encryption scheme (with associated data), or AE(AD) scheme for short.  Popular examples are AES-GCM, NaCl crypto_secretbox_xsalsa20poly1305, and AES-SIV.  Then pay attention to the security contract so that you understand what your obligations are in the application, and what security properties it affords you in exchange:

With AES-GCM, you are obligated (a) to choose a secret key uniformly at random, (b) to provide a unique 96-bit nonce for each message you want to encrypt, and (c) to never reuse the nonce with the same key.

The nonce must be derived from context, e.g. a message sequence number, or stored alongside the message, so that the decryption side of your protocol knows it.  You must not pick the nonce at random, or you must use the key for no more than than $2^{32}$ messages.  Messages must be no longer than one terabyte, $2^{40}$ bytes.

In exchange, you are guaranteed that an adversary without knowledge of the secret key learns nothing about the plaintext of each encrypted message (even if they know all but a single bit of the plaintext, the ciphertext does not inform them of that single bit) and cannot forge ciphertexts you did not already furnish.  If you reuse a nonce, all is lost.

(The exact bound on the safe number of messages is squishy.  A panel of crypto nerds could litigate endlessly over what the limit should be.  Do you want to play games with squishy balls of crypto you don't understand, or just play it safe?)
With NaCl crypto_secretbox_xsalsa20poly1305, you are obligated (a) to choose a secret key uniformly at random, (b) to provide a unique 192-bit nonce for each message you want to encrypt, and (c) to never reuse the nonce with the same key.

The nonce must be derived from contxt, e.g. a message sequence number, or stored alongside the message, so that the decryption side of your protocol knows it.  You may pick the nonce uniformly at random.  You may encrypt up to $2^{64}$ messages each of up to $2^{72}$ bytes apiece, which is more bytes than you will ever have in your lifetime even if you never bother to chew.

In exchange, you are guaranteed that an adversary without knowledge of the secret key learns nothing about the plaintext of each encrypted message (even if they know all but a single bit of the plaintext, the ciphertext does not inform them of that single bit) and cannot forge ciphertexts you did not already furnish.  If you reuse a nonce, all is lost.
With AES-SIV, you are obligated to choose a secret key uniformly at random.  You may additionally supply a 128-bit nonce, even at random.  You must not use the key for a total of more than $2^{48}$ bytes.

In exchange, you are guaranteed that an adversary without knowledge of the secret key learns nothing about the plaintext of each encrypted message (even if they know all but a single bit of the plaintext, the ciphertext does not inform them of that single bit) except that if the nonce is repeated or not supplied, the adversary will learn when a message is repeated or not.  You are also guaranteed that the adversary cannot forge ciphertexts you did not already furnish.

(The limit on bytes here is also squishy.  What have we learned about squishy balls of crypto?)

There are other considerations about the AES ones versus the XSalsa20/Poly1305 choice: software implementations of AES and GCM are either vulnerable to cache-timing attacks (vast majority), or unusably slow (you are not likely to encounter these); guaranteeing that you can rely on a hardware implementation of AES and guaranteeing that your software stack uses the hardware implementation of AES that is available is a nontrivial auditing task.


Does knowledge of equal exponents decrease security?

This answer aims to show that the security does not decrease.

Let me explain it as a game. $\mathcal{D}$ is the challenger who asks $\mathcal{A}$ to solve a 2-hint DL problem.

$\mathcal{D}(\mathcal{G})$ samples $r$ and sends $(g_1,g_2,g_1^r,g_2^r)$ to $\mathcal{A}$.
$\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$ is supposed to answer $r$ correctly with a non-neglibigle possibility.

First, let me formalize "the discrete log from one to another is unknown".

There is a group $\mathcal{G}$ and a public generator $g_1$. $\mathcal{D}$ chooses $g_2$ as follows:

Samples $s\in\{0,1,...,\mathsf{ord}(\mathcal{G})\}$, where $\mathsf{ord}(\cdot)$ means the order of a group.
Computes $g_2=(g_1)^s$.

Then, let me introduce the basic DL game, which consists of another challenger $\mathcal{D}'$ and another adversary $\mathcal{A}'$.

$\mathcal{D}'(\mathcal{G})$ samples $r$ and sends $(g_1,g_1^r)$ to $\mathcal{A}'$.
$\mathcal{A}'(g_1,g_1^r)$ is supposed to answer $r$ correctly with a non-negligible possibility.

In groups where DL assumptions are believed to hold, a probabilistic polynomial-time $\mathcal{A}'$ cannot answer with a non-negligible possibility of getting it correct.

Now, we say $\mathcal{A}'$ is winning if it can output the correct answer with a non-negligible possibility.

So, we know there is no $\mathcal{A}'$ winning in $(\mathcal{D}',\mathcal{A}')$ game.

Now, if there is a PPT adversary $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$ that can play $(\mathcal{D},\mathcal{A})$ game with a non-negligible possibility of winning.

Then, there is a winning $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$.

We can construct a winning $\mathcal{A}'(g_1,g_1^r)$ from this winning $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$ as follows:

Samples $s\in\{0,1,...,\mathsf{ord}(\mathcal{G})\}$.
Computes $g_2=g_1^s$.
Computes $g_2^r=(g_1^r)^s$.
Outputs the answer of $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$.

Then, if $\mathcal{A}$ is winning, $\mathcal{A}'$ is also winning.
This contradicts the fact that there is not winning $\mathcal{A}'$.

So, such $\mathcal{A}$ does not exist.
In other words, there is no PPT adversary that can break your construction.

I think this answer also shows that it cannot be used to reduce the number of rounds for attacking.


Operation modes of block ciphers how are used?

DES would be the box in your diagram that's labeled "Block Cipher Encryption", and it participates in the encryption mode you show in two ways: the output is XORed with the plaintext, and the output is used as the input to the next block's use of DES (the second "Block Cipher Encryption").

In this mode, you're using DES to generate a sequence of random blocks based on the IV and key, so it's operating as a stream cipher (which means you must NEVER use the same IV and key more than once, in other words you need to use a new unique IV for each new set of message blocks as long as the key stays the same). OFB turns a block cipher such as DES into a stream cipher.

The requirements for an IV can be different for different modes, as are the consequences of re-using an IV with the same key.

Using the "raw" encryption algorithm on each block is known as ECB, Electronic Code Book.  The reason you don't normally use ECB is that any time you encrypt the same block with the same key, you'll get the same output.  This can easily yield a lot of information about the message, something that you don't want.  There's a nice image showing how much information can leak using ECB mode in the Wiki link above.

The different chaining modes have different requirements, before using one you need to understand what the pitfalls, advantages and drawbacks are.  In particular, most of the modes need to have some form of message authentication to prevent an attacker from changing parts of the encoded data.  The way to do this with the common chaining modes is called a MAC, a Message Authentication Code.  An example of a MAC is called HMAC (Hash-based message authentication code)(which, itself, is a mode of operation using some underlying hashing algorithm).

The problem with not using any message authentication (which is not the same as authenticating WHO you're talking to) is that an attacker can do many nasty things, depending on the chaining mode.  This can lead to them being able to change messages or determine part or all of what's in a message.