It may be that that's due to lack of secure DNS (confirmation anyone?)

So it turned out to likely be a warning about lack of DNS security.

  I also noticed that the signing algorithm is shown as a=rsa-sha1, and with the move to “Deprecate SHA-1” in other contexts, I'm wondering: how urgent this is for DKIM?

Not very urgent. Current attacks only put a dent in SHA-1 collision resistance, which requires generating a large number of messages to find a pair with equal hash values. That is only a concern whenever the attacker can both predict the data to be signed and influence some of it.

Typically, with DKIM an attacker can't get such a message signed. If you send an arbitrary message that gets signed by the domain, the attacker would need a second preimage attack to forge a change. The second preimage resistance of SHA-1 is still close enough to the expected $2^{160}$ to be completely unbreakable with current attacks.

There may be special cases where a collision attack could be possible, like if the attacker has access to an email account on a domain, but the messages are screened for spam before being sent. Then they could look for a pair of messages where one is innocent, the other spam; send the legitimate message; and copy the signature to the spam message. In this case the attacker would have to predict any header fields and the like that DKIM signs, so feasibility would depend on the setup.

Even if a collision attack was possible, it would take quite a lot of computational effort ($2^{61}$ or so).

  Am I correct in thinking that this would need to be done for each message an attacker wished to forge the signature for, without being able to re-use that work for the next message?

Finding multiple collisions is not that much harder than finding one. A generic preimage attack also becomes easier the more target messages you have. So the attacker could probably share some work if an attack was possible in the first place. However, it's not a key recovery attack, so every new forgery would need more work, yes.


collision resistant summarizer for long hash values

The answer is "any sane summarization function is about as good as any other; pick whichever is convenient"

To the best of our knowledge, SHA-256 acts pretty much like a random function (except for the length extension attack; that wouldn't apply here)

So, the output of SHA-256 is essentially a random 256 bit number; so, if we have a 128 bit hash function:

  Hash(M) = Summarize(SHA256(M))

then, as long as the Summarize function has $2^{128}$ preimages (of 256 bits) for each possible output (of 128 bits), it should be good.  Both the "use the first 128 bits" and "split the full value and XOR them" functions have this property.

Now, since you talk about collision resistance, you can find a collision with a 128 bit hash function with about $O(2^{64})$ effort, by the simple expedient of generating $2^{64}$ random strings and hashing them, and then looking for two hashes with the same value (and, in case you're hoping the memory requirements of this would save you, there are clever ways to reduce the memory requirements drastically without requiring that much more computation time).  As long as those random strings are longer than 128 bits, there's nothing a hash function can do to avoid a collision.  If you need stronger collision resistance than that, you need to rethink the problem.

Also, since I mentioned the length extension attack, I'll summarize it here:

If you hash the value $SHA256(M)$, and the length of $M$, then you can compute a string $A$ such that, for any string $B$, you can compute the value:

  SHA256(M | A | B)

You can compute this even though you know nothing more about $M$.

This wouldn't apply in this specific case, because for this to work, you need to know the entire $SHA256(M)$ output, and your summarize function will drop a lot (precisely 128 bits, actually) of that information.


What Is The Number of Active S-boxes over 5 Rounds of Fides AE cipher?

Your result is accurate: 25 active S-boxes is the best you can do in a 5-round trail. Here's an example for the 5-bit S-box variant, respecting the S-box constraints (and assuming I read the specification correctly):
$$
\begin{bmatrix}
\mathtt{19} & \mathtt{00} & \mathtt{1c} & \mathtt{1b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{1c} & \mathtt{00} & \mathtt{00} & \mathtt{1e} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{1b} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{1b} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{08} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\
\mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{02} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\
\mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\
\mathtt{02} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{06} & \mathtt{00} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1d} \\
\mathtt{00} & \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} \\
\mathtt{01} & \mathtt{00} & \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{03} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{03} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{06} & \mathtt{00} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1d} \\
\mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} & \mathtt{00} \\
\mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{01} & \mathtt{00} \\
\mathtt{03} & \mathtt{03} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{01} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1a} & \mathtt{00} \\
\mathtt{07} & \mathtt{03} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{01} & \mathtt{1d} \\
\mathtt{05} & \mathtt{0f} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} & \mathtt{1d} \\
\mathtt{04} & \mathtt{0c} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1a} & \mathtt{1d} \\
\end{bmatrix}
$$

So where does the 22 come from? Well, modeling the S-box and the linear layer exactly can be costly. Instead, we can represent each nibble by a single bit and use the branch number $4$ of the almost-MDS layer to obtain a lower bound of active S-boxes. That is, for each column of the state in MixColumns, we have
$$
\begin{align*}
\sum (x_i + y_i) &\ge 4d \\
d &\ge x_i \\
d &\ge y_i \,,
\end{align*}
$$
for dummy variable $d$, input and output variables $x_i$ and $y_i$.
Because this is an almost-MDS matrix, we also need to additionally ensure that the output is nonzero if the input is (as described here):
$$
\begin{align*}
4\sum y_i - \sum x_i &\ge 0 \\
4\sum x_i - \sum y_i &\ge 0 \,.
\end{align*}
$$

However, when one does this, it results in the looser bound of $\ge 18$ active S-boxes over 5 rounds, not 22! So it remains a mystery where the 22 came from. The same observations also apply to 6 rounds, and possibly above.


AES-CBC and IV -- Encrypting multiple blocks of a file with the same IV?

It is insecure to reuse the $IV$ with AES-CBC. At the very least, if the files have a common prefix, this will be revealed as a common prefix of the ciphertexts. For AES-CBC, the only way to ensure confidentiality is to use random $IV$s.

However, if you are not restricted to a particular CBC mode, the nonce-based Counter mode (CTR) might solve your problem. Each block is then encrypted with unique number (nonce) $N$ instead of $IV$. It does not have to be secret, moreover, it can be predictable (for example, it can be the block index).

Another option is to try modes of operation dedicated to small-block encryption.  XTS, which employs key-dependent tweaks instead of IVs and nonces, is a widely used example.


Proof that MAC and hash composition is insecure

Without breaking $F$, you can't: $S'$ is a PRF with almost the same security as $F$.

Let $k_1$ and $k_2$ be uniform random keys.  Let $F$ be a PRF, with advantage $$\operatorname{Adv}^{\operatorname{PRF}}_F(A) = \lvert\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]\rvert$$ for any distinguisher $A$, where $f$ is a uniform random function with the domain and codomain of $F$.  Let $H$ be an $\varepsilon$-almost universal hash family, so that $\Pr[H_{k_1}(x) = H_{k_1}(y)] \leq \varepsilon$ for any $x \ne y$.  (Without qualification, $\varepsilon = 1/|T|$ where $T$ is the codomain of $H$.)

Define $$S'_{k_1,k_2}(m) = F_{k_2}(H_{k_1}(m)).$$

Fix any PRF-distinguisher $A'$ for $S'$ making $q$ queries, and let $U$ be a uniform random function with the domain and codomain of $S'$.  We will bound the advantage of $A'$ at distinguishing $S'$ in terms of the advantage of another algorithm $A$ at distinguishing $F$ and the collision probability $\varepsilon$ of $H$:
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')
    &= \lvert\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]\rvert \\
    &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon,
\end{align*}
where $A$ is a PRF-distinguisher for $F$.  As long as $\operatorname{Adv}^{\operatorname{PRF}}_F(A)$ is small and $q$ is not too large, $\operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')$ is small too.

We will do this by the triangle inequality with the intermediate probability $\Pr[A'(f \circ H_{k_1}) = 1]$ that $A'$ returns 1 on a variant $f \circ H_{k_1}$ of $S'_{k_1,k_2} = F_{k_2} \circ H_{k_1}$, where a uniform random $f$ has been substituted for $F_{k_2}$.

Define the PRF-distinguisher $A$ for $F$ by $A(\mathcal O) = A'(\mathcal O \circ H_{k_1})$.  Then
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRF}}_F(A)
    &= \lvert\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]\rvert \\
    &= \lvert\Pr[A'(F_{k_2} \circ H_{k_1}) = 1]
           - \Pr[A'(f \circ H_{k_1}) = 1]\rvert.
\end{align*}
If $A'$ is a good distinguisher for $S'$, we will find that $A$ is a good distinguisher for $F$, unless $A'$ just got lucky finding collisions in $H$.
Now consider the $q$ queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ for the oracle $f \circ H_{k_1}$.

From queries to $H_{k_1}$ alone, of which we assume only the weak property of collision probabilities on two distinct inputs, an adversary could find a collision among three inputs with high probability—e.g., in a polynomial evaluation MAC $M_{r,s}(m) = s + \sum_{i=1}^{|m|} m_i r^{|m| - i + 1}$ the adversary could trivially recover the keys $r$ and $s$ from two distinct queries and find arbitrarily many collisions with probability 1 after that.

But since $f$ is a uniform random function, the only information $A'$ can learn from oracle access to $f \circ H_{k_1}$ is whether the queries collide in one of $H_{k_1}$ or $f$, or definitely do not collide in either.  The adversary can adaptively act on the information that queries might collide only if a collision actually occurs in $H_{k_1}$, which happens with probability at most $\varepsilon$ for any pair of inputs submitted.  Thus, to study $\Pr[A'(f \circ H_{k_1}) = 1]$, it suffices to set a bound on the probability that there is a collision at all.

Among the queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ to $f \circ H_{k_1}$, the event $C$ of a collision in $H_{k_1}$ has probability
\begin{multline*}
  \Pr[C] = \Pr[\exists i < j\colon H_{k_1}(x_i) = H_{k_1}(x_j)] \\
    \leq \sum_{i<j} \Pr[H_{k_1}(x_i) = H_{k_1}(x_j)]
    \leq \sum_{i<j} \varepsilon = \binom{q}{2} \varepsilon,
\end{multline*}
In the event $\lnot C$ that the queries do not collide in $H_{k_1}$, the distribution of each $f(H_{k_1}(x_i))$ is independent uniform random, identical to the distribution of $U(x_i)$.  Hence necessarily $\Pr[A'(f \circ H_{k_1}) = 1 \mid \lnot C] = \Pr[A'(U) = 1]$, so that
\begin{align*}
  \Pr[A'(f \circ H_{k_1}) = 1]
    &= \Pr[A'(f \circ H_{k_1}) = 1 \mid C]\,\Pr[C] \\
    &\quad + \Pr[A'(f \circ H_{k_1}) = 1 \mid \lnot C]\,\Pr[\lnot C] \\
    &\leq \Pr[C] + \Pr[A'(f \circ H_{k_1}) = 1 \mid \lnot C] \\
    &\leq \binom{q}{2} \varepsilon + \Pr[A'(U) = 1],
\end{align*}
and thus $\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1] \leq \binom{q}{2} \varepsilon$.
Summing up,
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')
  &= \lvert\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]\rvert \\
  &\leq \lvert\Pr[A'(F_{k_2} \circ H_{k_1}) = 1]
            - \Pr[A'(f \circ H_{k_1}) = 1]\rvert \\
  &\quad + \lvert\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1]\rvert \\
  &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A)
         + \binom{q}{2} \varepsilon,
\end{align*}
QED.

This follows the structure of the proof of Lemma 3.3 in:

  Shay Gueron and Yehuda Lindell, ‘GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte’, in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 109–119

Variants of the theorem appear in many earlier papers, including the MDx-MAC paper that preceded the creation of HMAC, and the HMAC/NMAC security papers.


Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure?

No.
If the claim was true, then there would be an extremely simple way to prove it: $10^{10}$ arithmetic operations is nothing. There are tons of 800-bit factoring challenges available online. The author could just solve them and include the factorization in the submission; the lack of such a straightforward validation should be taken as empirical evidence that the claim is, as of today, unsubstantiated at best.
Leo Ducas, one of the top experts in lattice-based cryptography (and especially in its cryptanalysis) has implemented the March 3 version of the paper. The preliminary experimental evaluations seem to indicate that the method cannot outperform the state of the art (quoted from here):

This suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21].

Personnal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well.

The corresponding Twitter thread is here.
Furthermore, this Twitter thread points to what seems to be a fatal mistake in Schnorr's paper.
(Warning: personal view) I'm also basing my conclusion on the fact that several top experts on SVP and CVP algorithms have looked at the paper and concluded that it is incorrect (I cannot provide names, since it was in the context of anonymous reviews). Of course, the latter should not be treated as clear evidence, since I'm not providing proof of this statement - please treat it simply as it is, a claim I'm making.
(This statement refers to the version of the paper which was initially uploaded, and whose eprint extracted abstract  contained a claim that RSA was "destroyed", together with the sample running times given in OP's question. Schnorr himself still claimed, after being asked by mail about the paper, that the latest version breaks RSA - and so does its abstract; with respect to this claim and given the lack of solved RSA challenge, I stand by my statement that it should be regarded as essentially unsubstantiated).
Among the potential issues (again to be treated with care, as pointers to help people willing to look further into where the paper might fail):

The proof of (5.8) does only show the existence of many smooth triples, but says nothing about the probability of successfully finding factoring relations.
The paper relies on the Schnorr-Hörner pruning strategy, which is known to be flawed.
No justification is given for the cost indicated for (3.2)


I will think more about a proof/counterexample for #1, but here is a counterexample for #2.

Let $\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec}$ refer to a CPA-secure encryption scheme with message space $\{0,1\}^\lambda$, and define the following modified scheme:

$\mathsf{KeyGen}'$: run $sk \gets \mathsf{KeyGen}$ and sample $m^* \gets \{0,1\}^\lambda$. The key is $(sk,m^*)$.
$\mathsf{Enc}'( (sk,m^*),m)$: if $m = m^*$ then output $\star$; otherwise output $(\mathsf{Enc}(sk,m), m^*)$.
$\mathsf{Dec}'( (sk,m^*), c)$: if $c = \star$ then output $m^*$; otherwise parse $c$ as $(c_1,c_2)$ and output $\mathsf{Dec}(sk, c_1)$

The idea is that $m^*$ is a special message whose encryptions are easily distinguishable. But the only way to learn $m^*$ is to query the encryption oracle.

Suppose you play the CPA game with pre-challenge queries. Make any query and the response will include $m^*$. Now choose as your challenge $m_0 = m^* \ne m_1$. You can determine $b$ exactly by seeing whether the challenge ciphertext is $\star$.

Suppose you play the CPA game without pre-challenge queries. With no information about the "magic" plaintext $m^*$ you will not be able to make $m^*$ one of the challenge plaintexts except with negligible probability. So the challenge ciphertext is a regular $\mathsf{Enc}$-encryption of $m_b$ and the game can be reduced to the CPA game for $\mathsf{Enc}$.

Update:
For #1 the best counterexample I can do is a stateful encryption scheme. It's a bit of a cheat but one could argue that the "right" definition of security for stateless encryption should also be the "right" definition for stateful encryption.

Let $\textsf{Enc}$ refer to a standard CPA-secure encryption, and define the following encryption scheme with internal state $st$, initialized to $\bot$:

$\textsf{Enc}'(sk,m)$: output $(\textsf{Enc}(sk,m), st)$; update $st = m$.

Every time you encrypt, you are also told the plaintext that was used in the previous ciphertext! So breaking CPA with post-challenge queries is trivial.  But with no post-challenge queries, things reduce to the CPA security of $\textsf{Enc}$ in a straight-forward way (the reduction already "knows" the plaintexts used for pre-challenge queries, so can add them on appropriately).


Homomorphic Encryption operation for regression

if you can generate the inverse of the matrix (X^T X), then can't you generate the cypher version of the identity matrix, and determine what E(1) is?

I believe that the point you're missing is that homomorphic encryption is probabilistic; there are lots of legal representations of $E(1)$.  The encryption process takes the plaintext (1 in this case), and some random values (we call them random coins); different values for the coins give you different ciphertexts.

Yes, you can generate values which you know is an encryption of 1 (in fact, they can be a lot easier than doing a full matrix multiply, if you have the public key, you can just take 1 and encrypt it yourself).

And, because there are many different ways of representing $E(1)$, just because you know one of them doesn't mean that you can recognize the others (in fact, we hope there's no such way, otherwise (as you implied) the whole system is broken).


Is the use of a 4-round Blake2b permutation in OPP justified?

4 rounds of Blake2b is essentially equivalent to 8 rounds of ChaCha in terms of complexity (a Blake2 round is close to a ChaCha double-round), and that has not yet been broken. Like Richie Frame wrote in a comment, NORX also claims to get away with 4 Blake2 rounds.

One reason ciphers get away with less is that in hash functions all inputs are known and (except for constants) under the attacker's control. In ciphers the key is secret and, unless you take into account related-key attacks and such, not under the attacker's control.


Why is Math.floor(Math.random()*9000) not secure in JavaScript?

According to this answer, math.random uses a Linear Congruential Generator (although it is not clear to me if that's on one specific browser, or on all JavaScript implementations).

In any case, a Linear Congruential Generator is known not to be secure, in the sense that, given partial output (which the Math.floor( 9000 * Math.random() ) operation allows), someone is able to reconstruct the initial seed, and from that, reconstruct the entire sequence.

In particular, if the browser uses the popular XORSHIFT128+ RNG, and you are able to deduce 128 lsbits from the underlying 32 bit outputs, you can reconstruct the initial state (by solving some binary linear equations).


The other answer correctly explains how we could make a modern stream cipher, with a public random IV at the beginning of ciphertext used (together with the key) in the setup of a keystream generator, restricted to the range $[0..35]$, and using addition modulo $36$ (Beaufort cipher) to encipher each character.

Here is a more detailed description of such a system, built from AES-128 in CTR mode. Encryption goes:

Randomly generate an IV of 12 bytes using 24 hexadecimal dice throws (some of the first hexadecimal digits can be replaced by a public message number, origin/destination if that's public, the date.., but enough randomness must remain so that the IV is unique with overwhelming odds); the IV will form the beginning of the ciphertext;
Initialize the counter $N$ to the IV followed by 32 zero bits (that will be a 128-bit quantity), and $\text{available raw keystream}$ to empty;
While there is a character $p$ to encipher, converted to an integer in range $[0..35]$ per some public table;

Repeat ..

If $\text{available raw keystream}$ is empty

(optional) stop with plaintext too long if the rightmost 32 bits of $N$ are all ones; that will occur after over 33 billion characters have been enciphered.
Set $\text{available raw keystream}$ to the 8 bytes formed by encrypting $N$ using AES-128 and an agreed secret key;
Increment (the low 32 bits of) the 128-bit $N$

Get the leftmost byte $b$ of $\text{available raw keystream}$, and remove it;

.. until $b<252$ (that's $2^8-(2^8\bmod36)$);
$b\gets b\bmod36$; that's our uniformly distributed keystream character in the range $[0..35]$;
$c\gets p+b\bmod36$, output that ciphertext character (converted per the public table);

Decryption works as:

Acquire IV as the beginning of the ciphertext, over the first 24 symbols;
Initialize the counter $N$ to IV followed by 32 zero bits (that will be a 128-bit quantity), and $\text{available raw keystream}$ to empty;
While there is a character $c$ to decipher, converted to an integer in range $[0..35]$ per the public table

Repeat ..

If $\text{available raw keystream}$ is empty

Set $\text{available raw keystream}$ to the 8 bytes formed by encrypting $N$ using AES-128 and the agreed secret key;
Increment (the low 32 bits of) the 128-bit $N$;

Get the leftmost byte $b$ of $\text{available raw keystream}$, and remove it;

Until $b<252$;
$b\gets b\bmod36$; that's the same uniformly distributed keystream character in the range $[0..35]$ that was used for encryption;
$p\gets 36+c-b\bmod36$, output that plaintext character (converted per the public table).

This is modern; academically secure from a confidentiality standpoint; and answers the question as worded; but has serious operational drawbacks:

The message is not authenticated; an adversary can replace the ciphertext by one that will decipher to another message, and if the original plaintext is known, the adversary can make the substitution decipher to whatever the adversary wants, without knowing the key.
That works, to a degree, with partial knowledge of the plaintext. If for example the adversary knows that a 19-character messages is of the form AMOLEFT123REPEAT123, and the digits are encoded to 0..9 in the public table, and the number encoded is in range [000..299], then increasing the 8th and 17th character of the ciphertext by 2 (modulo 36) will increase the transmitted number by 200, perhaps giving the impression that there is ample amo, when really there is shortage.
If the IV does not contain the date, there's an even simpler attack: replay an old message from a past day where the amo stock was high.
Any error in the IV makes the whole ciphertext undecipherable (that can be fixed by sending the IV thrice, a primitive form of Forward Error Correction).
Even an accidental error in the ciphertext can go undetected.
A slip in the ciphertext (loosing synchronization between sender and receiver) makes the message following the slip garbled (this can often be detected and largely fixed using the redundancy in the plaintext);
If the ciphertext is transmitted in morse code, even though it has (within the constant overhead of the IV) the same number of characters as the plaintext, it is significantly longer to transmit than the plaintext, because frequent symbols in the plaintext use short morse sequences, but that optimization is lost for the ciphertext.

Therefore, a good modern system (say, engineered to comply to rules of a contest or ancient treaty stating that messages must be sent using morse code by human operators, but not banning computers for anything else) will work quite differently:

The plaintext will be compressed as the first step of encryption. One possible way to do this is to use e.g. gzip, with constant public fixed prefix to the plaintext consisting of public dummy plaintext with the same characteristic as the real plaintext (same character set, frequent words and sentences), and the constant compressed header resulting from this suppressed from the gzip output; this will give fair compression, and adapt easily to any alphabet and usage pattern. A caveat is that using infrequent words and sentences in the actual plaintext will lower the compression ratio, which will be detectable to some degree from the length of the ciphertext.
The resulting compressed plaintext bytestream will be enciphered using a scheme also providing message integrity. If we stick to symmetric crypto, AES-GCM comes to mind. With integrity insured, replay can be made detectable by putting a sequence number (or UTC date/time) in the message. Or we could move to asymmetric crypto (with the advantage that if the enemy fully compromises a sending station, that still does not allow decryption); if done right (hybrid encryption), it will add very little overhead.
The resulting ciphertext will be re-encoded to morse code using a method optimized for the medium at hand (with frequency of output symbols inversely proportional to their transmission duration; thus more E encoded as " . " than there are 0 encoded as " — — — — — "), and providing some degree of forward error correction. Techniques like Hufffman or arithmetic coding, and Reed–Solomon error-correction (or some ad-hoc system), will be used.

All in all, even for short messages, the ciphertext will transmit faster than for the previous system, while insuring message integrity; and for large messages the ciphertext will transmit several times faster than the plaintext would have.


Cracking lowest plaintext bit in Padding oracle attack with PKCS#5

Why do all the implementations of this attack assume that the first success from Oracle means we got a 0x01 in the last byte from the oracle? Is it because the probability of getting a 0x02 in the last byte and the penultimate byte while only varying the last byte is lower?

Largely, yes.  Remember, our general assumption is that an attacker is happy with an attack that only works most of the time.  In this case, assuming that the attacker has no initial information about the plaintext block under attack, then a random C1 that causes us to have valid padding would correspond to an 01 padding byte with probability circa $1 - 1/255$ of the time.

In addition, if you find a C1 that might reveal the last byte, and might have a longer padding pattern, there's a very easy test; try C1 with the penultimate byte modified; the resulting decryption will still have valid padding if it had an 01 padding byte, and have invalid padding if it was anything else; hence it would be easy to catch.


i wanna help to understand why we divided by 32 and add 6 in this
  formula

AES is defined for three key-sizes: 128, 192 and 256 bit with 10, 12 and 14 rounds respectively. These round numbers have been tabulated originally (that is no continuous function was given) and why these were chosen is because they offered the optimal (or at least a very good) trade-off between security and performance.

Now if you want to turn these three points into a continuous function, you can do interpolation and this will return you the function you found: $$R=k/32+6$$

as clearly $10=128/32+6, 12=192/32+6$ and $14=256/32+6$.


This is rather implementation dependent.

If this is compiled code (and even slightly optimized), I would expect the compiler to perform 'constant propagation'; that is, it would notice that j always has the value of zero, and so remove j (and effectively replace all instances with 0); of course, those 0's would be subject to even more optimizations (for example, a statement of t := t + j may end up being omitted entirely).

If this is interpreted code, well, it might be possible (albeit unlikely); the interpreter would most likely place a 0 in the place where the current 'j' value resides; you might be able to disrupt that write and have it write another value (without disrupting anything else the interpreter is doing); I can't think that'd happen that often.

If it's JIT (just in time compiled) code, well, it's even more complex; you might disrupt the compilation process (that is, when the JIT compiler reads it, it reads something other than j = 0, and compiles it accordingly), or you might disrupt the execution process (which, depending on how much the JIT compiler tries to optimize, might look like either of the above two cases).

However, even at the best, I would be skeptical about the practicality of introducing a fault that has the sole affect of modifying j, and has no other changes.


Are interactive proofs more secure their non-interactive counterpart?

When turning an interactive ZK proof into a non-interactive zero-knowledge argument with the Fiat-Shamir transform, the following security issues must be taken into consideration:

Even if the interactive ZK proof is a proof system (meaning that it is statistically sound), the Fiat-Shamir transform produces an argument system (where soundness is only computational). In concrete terms, that means that you must in general increase the soundness error of the interactive protocol before making it non interactive. Consider for example an interactive protocol where a cheater has probability at most $2^{-40}$ of producing a convincing proof for an incorrect statement: this can be a perfectly fine security guarantee in many real-world situation. But as soon as you turn this protocol into a NIZK with Fiat-Shamir, the guarantee changes: now, you are only guaranteed that forging an incorrect proofs will take $2^{40}$ computation steps for the malicious prover. But performing $2^{40}$ operations is trivial on any standard computer, hence the scheme would be completely broken. Put differently, a NIZK will in general need to be less efficient than the corresponding interactive ZK proof, in terms of communication and computation, to achieve a sufficient security level.
Many interactive ZK proofs naturally satisfy non-transferability: if a prover interacts with a verifier and demonstrates that he knows some value, or that some statement is true, the verifier, even after seeing the proof from the prover, cannot in turn convince another party that he knows the value/that the statement is true. This is because the verifier can at best show the transcript to this other party, but by the zero-knowledge property of the protocol, this transcript could in fact have been generated easily without knowing whether the proof is true (put otherwise: if you know the challenge in advance, it's easy to forge a proof. How could the other party know that the verifier had not colluded with the prover and given him the challenge in advance?). In contrast, NIZKs are naturally transferable, since they are publicly verifiable. Sometimes, non-transferability is crucial: suppose you solve a million-dollar problem, and want to prove to someone that you've found the solution. Using a zero-knowledge proof allows you to convince him that you know the solution without revealing it; but you still do not want this person to be able to use your zero-knowledge proof to convince someone else that he knows the solution, since he could then just use your proof to claim the million dollar prize!
As pointed out by Martin Kromm, the Fiat-Shamir transform is not proven secure in the standard model under any known security assumption. It is only proven secure in an idealized model, meaning that the security guarantees it gives are, at best, heuristic indications that breaking it requires doing "something non trivial" with the underlying hash function. Concretely, NIZKs obtained with the Fiat-Shamir transform have never been broken as of today and seem relatively safe, but we have no proof of that, so one should be cautious.

As for the reasons to use interactive proofs over non-interactive proofs (besides the one above, that apply specifically to Fiat-Shamir): If you want an extremely efficient proof, where verification is super fast and the communication is very small, then this can be achieved using an interactive proof using standard and well studied assumption, such as collision-resistant hash functions (this paper), the discrete logarithm problem (this paper), etc. In contrast, if you want such an efficient NIZK, you either only have security in the random oracle model (using Fiat-Shamir), or must rely on exotic and poorly understood assumptions, such as the knowledge-of-exponent assumption.

As for complexity-theoretic discussions on NIZKs versus ZK proofs, I discussed the complexity-theoretic questions related to the round complexity of zero-knowledge proofs in this answer. There is also some discussion on the hardness of building NIZKs from standard assumptions (compared to the relative easiness of building interactive ZK from standard assumptions) in the introduction of my recent paper, which you might find relevant.


Any Supersingular Isogeny-based Diffie-Hellman (SIDH) key exchange recommended Curve Domain Parameters?

All 'good' implementations so far have used the same curve, but there is now variation in the underlying finite field, which affects the other base parameters of the public points for each party and the range of values for the secret scalars. The best reference as yyyyyyy mentioned is the NIST PQC submission for SIKE, which includes valid options for SIDH with some extra protocol stuff on top. The parameter sets in there are p503, p751 (the most studied one) and p964.


Timing Side Channel on error-correcting code

This may indeed leak information. If we can induce data dependent errors. If an attacker can induce a bit flip it won't help him, but it is actually more likely he could induce bits to be set by generating relevant interference.

If a bit was 1 to begin with the extra interference won't make it any more 1, but if it was 0 to begin with? setting it to 1 would be an error which needs correcting and you may be able to time this.
Just in general trying to create more set bits seems like a practical attack and with the timing of the ECC would allow at least (over repeated attempts) to assess the number of set bits.

A more complicated attack on which bit is set would require a great degree of control on the errors. Need much more information on the complete setup in order to confidently rule this out, but it seems more far fetched.


In MD5, the use of formulas with floating point arithmetic is limited to building 64 nothing-up-my-sleeves 32-bit constants. Most implementations use a precomputed table, for startup efficiency and portability.

Changing $\sin$ to $\cos$ would change the constants, but as far as we know would make the algorithm neither weaker nor stronger. That's the nature of nothing-up-my-sleeves constants.

There would be a problem with using $\tan$, because $\tan(11)\approx-225.95$, thus the input of floor would be 40-bit. We would need a floor variant with at-least 40-bit result, keep the low-order 32-bit part of the result, and ensure that $\tan$ is evaluated to at least 40-bit precision in the mantissa for portable values from an implementation to another¹.

MD5 has other arbitrary-looking formulas, operating on 32-bit unsigned integers assimilated to 32-bit vectors. These are optimized for their cryptographic properties, and changing them haphazardly stands high risk of weakening the algorithm (further than it is: its security goal of collision-resistance is not met).

¹ Incidentally: computing the MD5 constants using the built-in floating point arithmetic in the Arduino will fail to yield the correct table due to insufficient (non-conforming) precision of the double type there, and would cause the low-order 8 bits to be severely biased, with possible negative cryptographic consequences. The same effect causes many Arduino code using a GPS to be significantly less accurate than it should be. But I digress.


Decisional Diffie-Hellman: compute Legendre symbol of $g^{ab}$ from $g^a$ and $g^b$?

Because (I assume) $g$ is a generator, it is not a square (prove this), so its Legendre symbol is $-1$. And hence, the Legendre symbols of $g^a$ and $g^b$ leak the parities or $a$ and $b$. Hence they leak the parity of $ab$, which leaks the Legendre symbol of $g^{ab}$.


If I know an element and it's inverse, can I learn the modulus?

As said in the comments above, you have that $x \cdot x^{-1} = 1 \mod n $.
Another way to say that is $k \times n=(x \cdot x^{-1}) -1$

So no, you can't always find the exact value $n$ from $x$ and $x^{-1}$.

Take $x=12 \ $ and $x^{-1}=17$. You have $x \cdot x^{-1} = 204$.
So $n$ is a divisor of $204-1=203$, meaning, $ n \in \{29,203\}$ (other divisors are smaller than $\max(x,x^{-1})$ so they can't be $n$)

The only cases where you can find $n$ is when the only divisor of $kn$ greater than $x$ and $x^{-1}$ is $kn$ itself. In this case, $n=kn=(x \cdot x^{-1}) -1 $


Can a nonce be used to steganographically hide a message?

You can do this, although the implications are limited.

If you have a secret key, an algorithm, and a communication channel that can send bytes, you can send an encrypted message.
It doesn't matter what secondary uses (i.e. nonce) that data may have.  What matters is that they transmit the message.
Algorithms typically provide security proofs based on properties of the nonce.  If the nonce is indistinguishable from a random number, it can be used as if it were a random number.  If a nonce is not the product of two prime numbers, then it can be used as if it were not the product of two prime numbers.  As long as your "nonce" obeys these properties, whatever they are, it will be secure.

In general, this idea is as viable as any stenographic system which hides the content in a protocol.  Its validity depends greatly on a threat model.  Your adversary clearly has the ability to observe your encrypted traffic (or there would be no need for stenography like this).  Can they also require you to use specific algorithms?  If your approach was popular, you might run into issues where the adversary mandates an algorithm for nonce.  This algorithm may satisfy the proofs needed to ensure the underlying communications are secure, but be insufficient for use in your stenographic approach.  (for example, they might require you construct nonce from a merkle tree, and provide them the frontier of the tree at any time to prove you are using their algorthm.  This could decrease the bandwidth of your stenographic channel to any arbitrarially small amount)
The most likely issue would be an algorithmic proof of the underlying communication algorithm which depended on a property you no longer had.  For example, there are communication schemes which depend on the unpredictability of an initialization value to prevent replay attacks.  If your stenographic communications get cracked enough to start predicting the nonce on your future messages, you may become susceptible to replay attacks that you would otherwise be immune to.  This is a case-by-case thing, so you'd have to go into the specifics of your underlying message stream to see whether such an exploit might accidentally arise.


Is it possible to decrypt this message with partially known data?

The first 32 bytes seem to be the ASCII representation of a 16-byte hexadecimal string. Possibly an Initialization Vector (IV) or similar. That would leave us with 88 bytes remaining. My guess is that this encryption is made by some 128-bit block cipher (e.g., AES-128), using some mode of operation such as CTR or CBC. Note that 88 bytes is not a valid ciphertext size when using AES-128 and CBC mode, but maybe there are 8 bytes that are not part of the ciphertext.

It would be nice if you provide a textual version of the highlighted hexadecimal data.


Must a key for a HMAC-SHA256 digest kept secure?

My question: Is required to keep a key for HMAC-SHA256 secured or can I leave it with other user data as non-secure?

If your goal is integrity and you use a
HMAC, then it is mandatory to keep the key secret. A public key in HMAC would mean anyone can create valid tags for any message - and integrity is gone.

  When hypothetical opponent gets the key, is it possible from HMAC-SHA256 digest restore original encryption key?

No, it should be impossible to find the key from any HMAC value (that would contradict the security definition).


Should I use independent symmetric keys for each client should I use keys derived from a master key?

Yeah, sure, you can derive keys from a master key. This is often performed for schemes using symmetric encryption primitives. And yes, including the ID of the client is generally the way to do this.

SHA-256 is not a brilliantly secure KDF - but in general it will do. You'd better use a real Key Based Key Derivation Function though. Currently HKDF is all the rage, which uses HMAC underneath. HMAC in turn can be configured using a secure hash such as SHA-256.

When starting from a secure master key you can directly use HKDF-expand (skipping HKDF-extract) where available.

Note that transport security requires extra care. In general you may want to bold on perfect forward secrecy (ephemeral Diffie-Hellman) or other key derivation techniques that create session keys from your client keys. You may also need a form of authenticated encryption using HMAC or an authenticated cipher such as AES-GCM.


I hope this is not homework. It should be almost the same as proving $H_1=_cH_2$. Just let the distinguisher (that distinguishes $Com_1(m)$ and $R_1$) generate and append $Com_2(m)$ in both worlds. This can perfectly simulate the view of the distinguisher that distinguishes $H_0$ and $H_1$.


Analyzable in this case means "simple to study".

If your cipher consists of a small function that mixes a few things together, and then you repeat that often then your cipher is more easily understood and more easily fit into previous research knowledge than a overclomplicated large design. This is the case with Simon and Speck.

Being easy to analyze is a good property for a strong cipher. If people fully understand it and fully checked everything and still couldn't find a weakness then it adds confidence in the cipher. A more complicated design is more likely to have a "hidden weakness" - because more things can go wrong.


Does it negatively affect security to calculate a hash value of the ciphertext before MAC calculation? Like exchanging step 2. with this: HMAC-SHA256(SHA256(ciphertext)).

Technically, yes, but not significantly. In order to attack the scheme you propose, the attacker would have to be able to do at least one of two things: (1) Find an attack on the (standard) HMAC-SHA256 scheme; or (2) Find a collision for SHA256. Currently, the cryptographic community believes that one can safely assume an attacker can do neither of these things. (Contrary to what some may expect, an ability to do the second does not imply an ability to do the first.)

What security properties are offered by this construction in general -- because I don't understand, what about this construction is provably secure.

What do you mean by "this construction"? Do you mean Encrypt-then-Mac, or HMAC-SHA256?

If you meant Encrypt-then-MAC, David Cary provided a link to this question, and you might find the answers helpful. To summarize, one can prove that an attacker cannot learn information about the plaintexts (aside from their lengths), and cannot create a ciphertext that will pass the MAC integrity check. Here, attackers are assumed to have the ability to conduct chosen message attacks; that is, we assume that the attacker can convince or trick one of the parties into sending some messages of the attacker's choosing, and show that having this power is not enough for the attacker to "break" the scheme. (This is very conservative: in the real world, most attackers won't have this ability.) We also assume that the encryption algorithm and the MAC algorithm are themselves secure, and use independently chosen, random keys.

If you meant HMAC-SHA256, then see the second part of my answer to another question. Proving that HMAC-SHA256 has the properties discussed there requires making some (reasonable) assumptions about SHA256.

In both cases, the proofs are not "absolute". We need to make assumptions about the underlying algorithms, and the proof only shows that the probability of the attacker succeeding is very small, provided you don't do something like use the same key to encrypt petabytes of data.

Note:
In your question, you wrote Ciphertext = AES_K(Plaintext). But this is (almost always) wrong! AES can only work on 16-byte strings. To encrypt longer strings, you need to use AES inside of some mode of operation.


After a couple of hours of detailed study I've come to an answer.

As we all know the RSA algorithm works as follows:

Choose two prime numbers $p$ and $q$,
Compute the modulus in which the arithmetic will be done: $N = pq$,
Pick a public encryption key $e \in Z_n$,
Compute the private decryption key as $d$ such that $ed = 1 \bmod{\phi(N)}$,
Encryption of message $m$: $c = m^e \bmod{N}$,
Decryption of crypto message $c$: $m = c^d \bmod{N}$.

While these statements and equations can stand true for some fixed values of $p$, $q$, $m$, $e$, $d$ in order to define the RSA as a general cryptographic algorithm we must prove their generality for any message $m$ we wish to encrypt.

This is therefore the reason why the proof of the correctness of the RSA algorithm is needed.

Getting to the proof we can formalise it as follows:

Hypothesis:

$\gcd(p,q) = 1$
$N = pq$
$ed = 1 \bmod{\phi(N)}$

Thesis:

$ (m^e)^d = m \bmod{N}$, for all $m \in Z_n$

  NOTE:The important part is ^^^^^^^^^ the for all part...

Proof:

Being $m \in Z_n$ there are only two possible cases to analyse:

  1) $\gcd(m, N) = 1$

In this case Euler's Theorem stands true, assessing that
$$ m^{\phi(N)} = 1 \bmod{N}\text{.}$$

As for the Thesis to prove, because of Hypothesis number 3, we can write:

$$(m^e)^d = m^{ed} = m^{1 + k\phi(N)}\text{,}$$

furthermore

$$ m^{1 + k\phi(N)} = m\cdot m^{k\phi(N)} = m \cdot (m^{\phi(N)})^k,$$

and for Euler's Theorem

$$m \cdot (m^{\phi(N)})^k = m \bmod{N}$$

Proving that the thesis stands in this case.

  2) $\gcd(m, N) \neq 1$

In this case Euler's Theorem does not stand true any more.

For a result of the Chinese Remainder Theorem (check this SO question - Chinese Remainder Theorem and RSA - or just wiki it) it is true that if $\gcd(p,q) = 1$ then:

$$ x = y \pmod{p} \land x = y \pmod{q} \Rightarrow x = y \pmod{pq}$$

So by proving the following two statements we would have finished:

$ (m^e)^d = m \bmod{p}$
$ (m^e)^d = m \bmod{q}$

Because $\gcd(m, N) \neq 1$ one between $\gcd(m, N) = p$, and $\gcd(m, N) = q$ must stand true. I will demonstrate that both the above statements stand true in the case $\gcd(m, N) = p$, being it absolutely identical (by switching letters) to prove it for $\gcd(m, N) = q$ as well.

So let it be $\gcd(m, N) = p$, this implies that $m = kp$ for some $k > 0$ which means that $m \bmod{p} = 0$. By concerning the first statement we also have

$$ (m^e)^d = ((kp)^e)^d$$

which therefore results to be a multiple of $p$, and so it is equal to zero.

So the first statement becomes $0 = 0$ and is proven to be satisfied.

Concerning the second statement we have that Euler's Theorem results to be proved in $Z_q$, since $\gcd(m,q) = 1$, so:

$$ m^{\phi(q)} = 1 \bmod{q}\text{.}$$

This implies that we can write:

$$\begin{align}
 (m^{e})^d &= m^{ed} \\
&= m^{ed - 1}m\\
&= m^{h(p-1)(q-1)}m\\
&= (m^{q-1})^{h(p-1)}m\\
&= 1^{h(p-1)}m = m \bmod{q}.
\end{align}
$$

which definitively proves the second statement and theorem.


ZK proof of "element in subgroup" protocol

The simulator does not know $y$, but he does know $x$, and knows in advance which $b$ the verifier will pick. You already know the simulation when $b=0$. In the other case, when the simulator knows that the verifier will ask $b=1$, the simulator chooses $r$ at random and sends $a = \alpha^r/x$ instead of $\alpha^r$ to the verifier. Then, the simulator sends $z = r$. You can easily see that the check will pass: $\alpha^z = \alpha^r = (\alpha^r/x)\cdot x = ax = ax^b$.

EDIT: to complete a bit, the protocol you gave is honest-verifier zero-knowledge, which means that it is zero-knowledge as long as the verifier does not deviate from the specification. In this case, as the simulator is given the random tape of the verifier as input, he knows which $b$ the verifier will choose in advance.

If you want to handle a malicious verifier, to get a fully zero-knowledge protocol, the protocol must be modified, e.g. by asking the verifier to commit to his challenge before the start of the protocol (if you want more details on this point, feel free to ask).


Yes, we need symmetric cryptosystems, for many reasons; to give three of these:

We need a hash function to make most asymmetric cryptosystems secure (e.g. we simply do not have a secure signature system based on RSA without a hash), and current hash functions are (or are built from) symmetric cryptosystems.
All asymmetric encryption cryptosystems are bound to output ciphertext larger than the plaintext, and there are situations where this is a major drawback (e.g. bulk disk encryption).
The best asymmetric encryption cryptosystems we have around are some orders of magnitude slower/more energy-hungry than state-of-the-art symmetric ones; it turns out this worsens, badly, if we want to minimize the ciphertext expansion ratio by using huge parameters.

Note: Point 1 has the appearance of being sufficient to prove my assertion, but it is debatable to a degree: perhaps in this question we want the big picture only, and disregard the symmetric internals of all existing asymmetric cryptosystems; and/or perhaps we could devise asymmetric-based hashes (though these would be symmetric cryptosystems in disguise).
Also: we could live with 2, if there was not 3, which in the end is the real killer.


Roots of polynomial in Shamir secret sharing

If you have $t-1$ shares of an $(t,n)$ system, you have a chance at learning of the roots of the system... as long as some of your shares have a 0 for the $y$ coordinate.  You can't learn any other roots.

Demonstration that the possession of a share with a $y$ coordinate of 0 gives you knowledge of a root (and forgive me if this is too obvious):

A share in Shamir's scheme is a pair $(x, P(x))$, where $x$ is a nonzero coordinate, and $P(x)$ is the secret polynomial evaluated at that coordinate.  If the $y$ coordindate listed happens to be 0, we have $P(x) = 0$, which is pretty much the definition of $P$ has a root at $x$.

Demonstration that the attacker cannot learn any roots at locations other than the $x$ coordinates for the shares he has:

Consider what would happen if he could.  By learning of a value $x'$ which does not appear as an $x$ coordinate for any of the shares he has, and for which $P(x')=0$, he could treat that as another share $(x', 0)$, and use that, and his $t-1$ existing shares, and learn the entire polynomial.  We know he can't do that, and so he can't learn such an $x'$


Complexity to find an preimage of a hash function

For an $n$-bit hash with at least $n/2$-bit block size  (which is very common and includes MD5, SHA-1, SHA-2, SHA-512), using a round function as in the question, here is how to find a 2-block message $m_0\|m_1$ hashing to given $H$ with effort $O(n/2)$.

I note the Initialization Vector $H_{-1}$ in order to match the question's recurence $H_i=E_{m_i}(H_{i-1})$. Hashing $m_0\|m_1$ requires 3 rounds, with the third processing the padding block $m_2$, which is known, and the result $H_2=H$.

We compute $H_1=E^{-1}_{m_2}(H)$. This is possible since $E$ is a block cipher and allow decryption. Notice that would not be possible with $H_i=E_{m_i}(H_{i-1})\oplus H_{i-1}$ as in the Davies-Meyer construction (used in SHA-1 and SHA-2 with a small modification).

For $2^{n/2}$ incremental values of $m_1$, we computes and make a list of $E^{-1}_{m_1}(H_1)$. It is possible that we get some collision(s) there (probability about 39% that we get at least one), but unlikely that we get more than a few, thus we likely have just shy of $2^{n/2}$ distinct values in the list.

For $2^{n/2}$ incremental values of $m_0$, we computes and search in the above list $E_{m_0}(H_{-1})$. There is good probability (>63%) that at least a match is found.

A corresponding $m_0\|m_1$ (if any) is our message hashing to $H$.

Note: we can reduce the message size to one block and about $n/2$ bits.

As is, the attack uses $O(2^{n/2})$ memory. However, that can be reduced to practical using Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website).


what is the benefit of lcm in cryptography?

Regarding public key: In two prime RSA you often compute the secret key from the public as $d=e^{-1} \pmod {(p-1)(q-1)},\;$ but using $d=e^{-1} \pmod {\mathrm{lcm}(p-1,q-1)}$ may have some advantages.


Is CBC theoretically harder to brute force when compared with ECB?

As Maarten Bodewes already wrote in a comment, if you ignore the computational overhead of XOR, then there is essentially no difference in CBC and ECB for a bruteforce attack.

However, the question is actually mixing oranges and apples (and it is not obvious), because the security weakness of modes of operation has nothing to do with the underlying symmetric cipher - and a brute force attack has everything to do with the underlying cipher.

The problem is, that brute force attacks are a completely different scenario than what the different modes of operation try to achieve. In brute force you actually try out keys until you find the correct one. In cryptanalysis this is called a total break. The weakness of ECB compared to CBC is, that you can actually can achieve an easier goal of the attack: A distinguishing attack works on ECB and doesn't (with proper randomness, etc.) on CBC - under the assumption that the cipher is secure.

Btw, your 2. assumption is not needed. The IV is always assumed to be publicly known (and generated randomly for security arguments).


Why cryptsetup default KDF is PBKDF2 and not Argon2(id)?

The default version of LUKS simply does not support Argon2 because, unlike PBKDF2, it requires more parameters than the current header format is designed to store. The newer version, LUKS2, may not be default on your system, but it does support Argon2. This is just a matter of software support.

See also https://gitlab.com/cryptsetup/cryptsetup/blob/master/docs/on-disk-format-luks2.pdf


Use a Hadamard code via the fast Walsh Hadamard transform, it can correct up to $2^{n-2}$ errors for block length $2^n$ and is also locally decidable so you may not need too many code word coordinates.


Ring LWE: How can the secret be chosen from the "uniform distribution"?

You're right that essentially all schemes require that the secrets are small in a concrete sense.
While I'm not terribly familiar with the standard, I believe the tables in question were generated by the LWE Estimator of Albrecht et al. This page of its documentation states various secret distributions they support. I expect "uniform" corresponds to "bounded uniform", but I'm unsure of which particular bound was used to generate that table.


Distinguish between cipher-texts of text-book RSA and RSA/OAEP

We can distinguish between ciphertext of textbook RSA and RSA/OAEP when textbook RSA is misused and insecure; or with knowledge of the private key.

With knowledge of the private key, we simply attempt RSA/OAEP decryption. If it succeeds, we bet for RSA/OAEP (and that will hold except for a vanishingly small proportion of possible plaintext); otherwise we know that's textbook RSA (with certainty, unless there's another option).

With knowledge of the private key, we can still succeed by exploiting weaknesses of textbook RSA; for example:

If we can obtain ciphertexts for the same unknown plaintext enciphered twice, we can compare these ciphertexts. If they match, we bet for textbook RSA (and that will hold with overwhelming probability, unless the random number generator of RSA-OAEP is badly broken). If they differ, we know that's RSA/OAEP.
With knowledge of the public key (assumed in this and the next two bullets), if we know / suppose that the plaintext is a name on the class roll, we try to encipher all names on the class roll (that requires the public key, but by assumption that's known to all), and compare each result to the actual ciphertext. If any match is found, we know with near certainty that's textbook RSA; otherwise, we bet for RSA/OAEP (with odds depending on how confident we are that the plaintext is a name on the class roll).
As suggested in comment: if the ciphertext is an exact power of the public exponent $e$, we know for certain that's textbook RSA. Otherwise, we bet for RSA/OAEP (with odds depending on how likely it is that the plaintext $M$ is small enough that $M^e<N$).
If we can obtain actual ciphertext for a single chosen plaintext, that allows a test.

Also, if we know or can find the size limit for the plaintext, that's also revealing: Textbook RSA usually can encipher messages up to $\lfloor\log_2(N)\rfloor$ bits or $\lfloor\log_2(N)/8\rfloor$ octets; while RSA-OEAP has a much lower limit, $\lceil\log_2(N)/8\rceil-2-2h$ octets, where $h$ is the hash size in octets ($h=32$ for SHA-256).


Is there any pseudorandom function that outputs $n$ prime number of ring $Z_{N}$ where $N$ is Paillier public key

TL;DR: Any (pseudo-) random value from the desired range has a high chance of being invertible.

To understand this, first remember the criterion for a value $x$ to be multiplicatively invertible in $\mathbb Z_n$: $$\gcd(n,x)=1$$

Now remember how many such values exist, exactly: $$\varphi(n)=(p-1)(q-1)=pq-p-q+1$$

Now assume these non-invertible values are distributed somewhat uniformly over the set of all integers smaller than $n$. Then the chance that a value is invertible is exactly
$$\Pr[x\in \mathbb Z_n:\exists x^{-1}]=\frac{\varphi(n)}{n}=\frac{pq-p-q+1}{pq}=1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq}$$

Now remember that $p,q$ are large (otherwise the encryption could be broken), then $1/p,1/q$ and $1/(pq)$ are negligible and thus the probability of an integer being invertible is nearly 1.

As for constructing such values: Just generate bit strings of the appropriate size and discard them until they fit your limitations (e.g. $\leq n$), usually you will have to discard none or one integers this way.


Meaning of "Security can be reduced to a problem"

You are (mostly) right. Reductions are an algorithmic notion — $P$ reduces to $Q$ if the ability to solve $Q$ allows you to solve $P$. There are many ways to formalize this, but the one that you describe (using $Q$ as a subroutine/oracle to solve $P$) is the most common in cryptography (it is known as a Turing reduction).
I will notate this $P \leq Q$.

Note that reductions often have a little more detail than what you describe, specifically some bounds on the amount of resources that the reduction $R$ has access to.
If $R$ is all powerful then "hard languages" reduce to "easy languages", because $R$ can just ignore the subroutine/oracle it has access to and solve the problem directly.
This is seen as a boring formalization, so we generally want to force $R$ to be too weak to solve $P$ directly (having it be polynomial time is generally sufficient). This is mostly interesting when discussing properties of complexity classes under reductions though.

Now I'll quickly highlight that reductions are intrinsically about the existence of algorithms.
$P \leq Q$ can be interpreted as saying:

  If there exists an algorithm for $Q$, then there exists an algorithm for $P$

i.e. $P \leq Q$ can be parsed as the logical statement:

  $$ \exists \text{ algorithm for }Q\implies \exists \text{ algorithm for }P$$

With this in mind, let us look at the sentence you highlight:

  The security of a protocol $\Pi$ can be reduced to the hardness of $P$

What does it mean for a protocol to be secure? Normally "There doesn't exist an algorithm to break the protocol" (I will notate the problem of breaking the protocol $\Pi$ as $B_\Pi$. Similarly, what does it mean for a problem to be hard? "There doesn't exist an algorithm to solve the problem".
Ignore the word "reduced" in the above sentence quickly.
The goal of a reduction in cryptography is to prove "If the problem $P$ is hard, then the protocol $\Pi$ is secure", i.e. a statement of the form:

$$\not\exists\text{ algorithm for } P\implies \not\exists\text{ algorithm for }B_\Pi $$

This doesn't match up with our prior definition of reduction though.
We can look at the contrapositive of the above statement to get the equivalent statement:

$$\exists\text{ algorithm for }B_\Pi\implies \exists\text{ algorithm for }P$$

This is then written as $P \leq B_\Pi$.

Solving $P$ (complexity-theoretically) reduces to breaking the protocol $\Pi$
The inability to solve $P$ (i.e. hardness) implies to the inability to break (security) $\Pi$

We could read this later statement as defining a "cryptographic reduction" $B_\Pi \leq_{cr} P$, where this stands for a statement of the form:

$$ \not\exists\text{ algorithm for }P\implies \not\exists\text{ algorithm for }B_\Pi$$

But then this would be fundamentally dual to the complexity-theoretic reduction, i.e. we would have that $P \leq B_\Pi$ and $B_\Pi \leq_{cr} P$. Under this notion of reduction the authors' statement becomes correct, but it is the "reverse" direction that we expect from complexity theory.

This is all to say that for "reduce" in the sense of complexity theory, what they write is technically incorrect (but can be trivially fixed by appealing to the contrapositive). This is such a basic step that it is quite common to do it implicitly, but to formalize things in terms of complexity-theoretic reductions there is an intermediate step which must be made explicit.


How to interpret a formula from the handbook of applied cryptography

The comment by @SEJPM is correct, all those subscripted $n_0,n_{01}$ etc are nonnegative integers counting the occurrences of subsequences such as $0,01$ respectively.

So no problem with exponentiation.


Using Shor's algorithm to solve the discrete logarithm problem

Shor's method relies on a period finding routine on a quantum computer.

A function $f: (x_1, \dots, x_n) \mapsto f(x_1, \dots, x_n)$ is periodic, of period $(\omega_1, \dots, \omega_n)$, if $f(x_1 + \omega_1, \dots, x_n + \omega_n) = f(x_1, \dots, x_n)$ for all tuples $(x_1, \dots, x_n)$ in the domain of $f$.

Factorization problem  Given an RSA modulus $N = pq$, find primes $p$ and $q$.

Choose a random integer $a \in \mathbb{Z}_N$ (without loss of generality, we assume $\gcd(a,N) = 1$ —otherwise, this yields the factorization of $N$ and the factorization problem is solved).
Consider the univariate function $f: x \mapsto f(x) = a^x \bmod N$.
The period finding routine finds an $\omega$ such that $f(x + \omega) = f(x)$.  As a consequence, $\omega$ is a multiple of the order of $a$ modulo $N$.  Indeed, one has $f(x+\omega) = f(x) \iff a^\omega \equiv 1 \pmod N$.

If $\omega$ is a multiple of $\lambda(N)$ —where $\lambda(N)$ denotes Carmichael's function, then Miller's algorithm yields the factorization of $N$.  Otherwise, repeat the process with another $a$, get the period $\omega_a$, and update $\omega$ as $\omega \gets \operatorname{lcm}(\omega, \omega_a)$, until $\omega$ is a multiple of $\lambda(N)$.

[ A description of Miller's algorithm can be found in Cryptography: Theory and Practice by Douglas Stinson, http://cacr.uwaterloo.ca/~dstinson/CTAP.html ]

Discrete log problem Let $g$ be a generator of a group $\mathbb{G}$ of prime order $q$.  Given $y = g^k \in \mathbb{G}$, find the value of $k$.

Consider the bivariate function $f : (x_1, x_2) \mapsto g^{x_1} y^{x_2}$.
The period finding routine finds a pair $(\omega_1, \omega_2)$ such that $f(x_1 + \omega_1, x_2 + \omega_2) = f(x_1,x_2)$.
The solution to the discrete logarithm problem is then given by $k = -\omega_1/\omega_2 \bmod q$.  Indeed, one has $f(x_1 + \omega_1, x_2 + \omega_2) = f(x_1,x_2) \iff g^{\omega_1} y^{\omega_2} = 1_{\mathbb{G}} \iff g^{\omega_1  + k\omega_2} = 1_{\mathbb{G}}$ and thus $\omega_1  + k\omega_2 \equiv 0 \pmod q$.


What exactly are $K^3$ and $X^2$ here?

The notation $K^3$ where $K$ is the set of keys $k$ stands for $K\times K\times K$, that is the set of triplets $(k_1,k_2,k_3)$ with $k_1\in K$, $k_2\in K$, $k_3\in K$. When $K=\{0,1\}^n$ (the set of $n$-bit bitsrings), we can assimilate $K^3$ to $\{0,1\}^{3n}$ (mathematicians do this when there's a trivial bijection between two sets; here that's concatenation of bitstrings in one direction, and splitting into 3 equaly-sized bitstrings in the other).
Similarly the notation $X^2$ where $X$ is the set of blocks $x$ stands for $X\times X$, that is the set of pairs $(x_1,x_2)$ with $x_1\in X$, $x_2\in X$. When $X=\{0,1\}^b$, we can assimilate $X^2$ to $\{0,1\}^{2n}$.

Why has the key space been cubed and the block space been squared?

That must be the objective of the skipped construction. Increasing the keyspace is easy and there's one common example: 3DES cubes or squares the keyspace, leaving the blockspace unchanged. Increasing the blockspace is slightly trickier.
The cardinality of the key space is cubed: it goes from $2^n$ to $2^{3n}=\left(2^n\right)^3$. The cardinality of the block space is squared: it goes from $2^b$ to $2^{2b}=\left(2^b\right)^2$.


If I want Integrity and Authentication AND Non-Repudiation, can the Digital Signature be based on the MAC?

First of all, in a digital signature scheme that follows the hash-and-sign paradigm $Enc_{sk}(hash(m))$ the hash procedure is essential to "fit" the message $m$ in the public-key scheme domain: you cannot encrypt messages of any size with RSA for example.

The second important point is that a digital signature scheme is a bit closed to public-key encryption: because we consider an untrusted channel to communicate the public-key; another similarity is that the signer wants the signature to be publicly verifiable.

So, when we are using public-key cryptography, everything we do not want is to suppose a private/secure channel to exchange keys; you will need one if you want to use a cryptographic hash like a mac scheme. Furthermore, the signer has to exchange different secret keys with everyone who wants to verify the signature. Thus, creating distinct MAC tags: so, such a signature would no be publicly verifiable, but designated.

Another important point is that care must be taken when a cryptographic hash is chosen: HMAC wasn't designed considering collision attacks M. Bellare, New Proofs for NMAC and HMAC: Security without Collision-Resistance.
So, if you don't have a collision resistant mac scheme, what if a adversary can find another $tag'_i=mac(m_i)$, after consulting a polynomial number of $m_i, tag_i, Enc_{sk}(tag_i = mac(m_i))$, and so forging a signature?

BTW, unforgeability is a cornerstone security property of digital signatures schemes.

Last but not least important. by using only a mac scheme and sharing key, we don't have non-repudiation or authentication. If the singer and verifier share a secret key, how can we prove which one created a tag? So mac isn't enough: you also need a public-key scheme.

Well...the pros... I can't see anyone. Sorry.


What is universal composability guaranteeing, specifically? Where does it apply, and where does it not?

The different guarantees of security
In security proofs, you have several guarantees that you can obtain on the security of a protocol. The most famous are maybe the following:

game-based security
sequential composable security
general composable security (sequential + parallel composition)

Game-based security
The weaker guarantee that you can obtain is the game-based guarantee. Here, you specify a game, usually between a challenger and an adversary, and the goal of the adversary is to win the game. If no polynomially bounded adversary can win this game, you will say that the protocol is secure. The first problem of this model is that you can only specify a specific property that you want your protocol to respect, but it's very hard to think about all the possible properties that you would like your protocol to respect.
For example, let's imagine that you want to transmit a message between Alice and Bob, and make sure that Bob does not learn the message that Alice sent to Bob. Then, you could imagine the following game:

The challenger (playing the role of Alice), picks a random message $m$ uniformly at random over all the messages of length $n$ ($n$ being the "security parameter"). It encrypts the message and sends this cipher text $c$ to the adversary.
The adversary (playing the role of a malicious Eve), receives the cipher text $c$ and outputs a message $\tilde{m}$ to the challenger.
The challenger says that the adversary wins if $m = \tilde{m}$

We can then say that an encryption scheme is secure if no adversary can win this game with non negligible probability over $n$, i.e. if there exists a negligible function $f$ such that for all adversary:
$$\Pr[ m = \tilde{m} ] \leq f(n)$$
For simplicity, we will write that as:
$$\Pr[ m = \tilde{m} ] \leq negl(n)$$
This game seems pretty natural, however it is very imperfect. Indeed, it denotes the fact that no adversary can completely learn $m$ given $c$ when $m$ is sampled uniformly at random over all the messages of length $n$. But it may be completely possible for an adversary to learn lots of information about $m$! For example, it could be possible for him to learn the first $n/2$ bits of a message: just consider the stupid encryption algorithm that do not touch the first $n/2$ bits of a message, and perfectly encrypt with a one time pad the last $n/2$ bits. This encryption scheme is secure according to the above game, but nobody would claim that this scheme is completely secure since it reveals half of the message!
There is also another issue: in this specific game, the adversary has no way to choose the distribution used to sample $m$. For example, if you know that the messages exchanged are always YES or NO, and that the scheme is slightly buggy and maps all YES messages to the $0\dots 0$ string (while all other messages are perfectly encrypted), then this encryption scheme is nearly perfectly secure... but completely useless in practice. Due to that property, it means that you usually don't have any guarantee on the security of the protocol when it is composed into larger protocols, since the input usually come from other protocols that could be controlled by an adversary.
Then people tried to come-up with games that provides more guarantees (see CPA, CCA, CCA2 securities)... And this is just for encryption. Then for all others primitive (signature, delegated computation, authentication...) you need to redefine all the games that you want to have, and make sure that you didn't forget any property that may be crucial for the security of the protocol. The way I imagine games is a bit like some "lines" that you can draw to delimit the security of the protocol: it's nice to get a rough picture of the security of the game, but it's hard to be sure that you did not forgot any property to really cut down all possible attacks.

So to sum-up this section:
Advantages of game-based security:

proof are simple to do in this model of security

Drawbacks of game-based security:

it is harder to see quickly what guarantees we have on a protocol: games can be quite specific and tied to a specific form of attack
we usually don't have guarantees when the protocol is composed into other protocols

Sequential and parallel composability
Then, to avoid these issues, people started to define "simulation based" models of security, that could guarantee that the protocol can be securely used when it is composed into other protocols, or used at the same time as other protocols. Usually, you can compose protocol either:

one after the other: it's called "sequential composition"
at the same time: it's called "parallel composition"

Some models of security (like the standalone model) provides guarantees when the protocol are composed one after the other (i.e. under sequential composition) while other models of security target security under both sequential and parallel composition (i.e. "general composability"). It is the case of the Universal Composability (UC) model, but also of the Constructive Cryptography (CC) model (a.k.a. Abstract Cryptography model)).
All these models are quite similar in the spirit, and are "simulation based" (you will understand later why). I'll mostly focus on UC and CC here, but the standalone model is quite similar as well. Note that I don't want to enter into the details of how UC is defined in term of Turing Machine, channels... because I don't think it really adds anything important, and I think it is mostly confusing implementation details. Therefore both UC and CC models are very similar at that level of abstraction (for me CC is a kind of generalization of UC in which the computation model is not explicitly specified and can be instantiated in different manners, for example with Turing machines, but also with quantum machines...). So here, we will just assume that there are some parties and some oracles, and that if required they can communicate between each others.
So first, I like to see them as a "special case" of game-based models, except that we force the games to have a very specific shape that allows us to have stronger guarantees on the security, due to the addition of a simulator. So the two entities that we had before are still there:

the adversary that we defined in the game based-security section is now called "environment" (in UC) or "distinguisher" (in CC). The UC model also describe something that they call adversaries, but in practice it's possible to get rid of them by replacing them with so called "dummy adversaries", that simply forwards everything to the environment.
the challenger will be described later, and basically everything else will be part of the challenger

On top of that, the "games" will be described in a very special way. We will indeed introduce the Ideal Functionality (called "resource" in CC) that is supposed to be a perfect, ideal, version of our protocol, i.e. trivially/information theoretically secure version (NB: as pointed in the comments, the Ideal Functionality is more precisely our "definition" of security, i.e. we want to prove that our protocol is at least as secure as our Ideal Functionality, in the sense that if you can learn some information during the real protocol, you can learn equality interesting information in the ideal protocol. However, most of the time we are interested by Ideal Functionalities whose properties (i.e. which information is learnable or not from an attacker) are trivial to check, that's why I do this shortcut and say that the Ideal Functionality is "information theoretically secure". I elaborate more on that in the remark at the end of this post). Then we will say that a protocol is secure with respect to that Ideal Functionality if there exists a simulator that "disguise" the ideal functionality so that it becomes indistinguishable from the real protocol. That way, any attack that can be done in the real protocol (also called "real world") could also be done in the ideal protocol (also called "ideal world")... which is impossible because it's information theoretically secure!
Now, we have all the ingredients to define our "challenger": the challenger will toss a coin, and with probability $1/2$ it will let the adversary (i.e. the environment/distinguisher) interact with the real world, and with probability $1/2$ it will interact with the ideal world (composed of the ideal functionality + simulator). At the end, the adversary (i.e. the environment/distinguisher) needs to say to the challenger if it is interacting with the real world or the ideal world. The protocol is then said secure if no computationnally bounded adversary as a significant advantage in winning this game, i.e. if the probability of winning the game is $\leq 1/2 + negl(n)$.
For example, if you want to talk about a perfectly secure channel (that cannot be modified, by an eave dropper, and that leaks only the size of the message), you could define an ideal functionality as follow:

Where the left "interface" of the ideal functionality belongs to Alice, the right interface to Bob, and the bottom interface to a potentially malicious Eve. As you can see, it is very clear from the picture that no Eve can learn anything else but the size of the message $m$ given only access to the bottom interface.
Now, we want to say that our protocol is at least as secure (modulo the fact that we consider computational security) as this Ideal Ressource. So first, let's define our protocol. Here, for simplicity, we will assume that we already have an authenticated channel, i.e. that we have a protocol realizing the following ideal functionality:

and that on top of that, we also suppose that we have a protocol to distribute a secret key:

Then, the idea is just to encrypt the input $m$ (for example using the One Time Pad algorithm, or if you prefer you can try to see if it works with the AES-GCM algorithm) using the key $k$, and put the cipher in the authenticated channel. Bob will then be able to decrypt it:

Now, to prove the security, we need to find a simulator that disguises the ideal functionality into this protocol (for simplicity, here we consider Alice and Bob are honest, but in UC you need to prove that far all possible subsets of possible corrupted users, and you can define a different ideal functionality depending on who is corrupted/malicious). If we assume that $E_k(m)$ has the same length as $m$ and looks like a uniform random string (which is the case of the one time pad encryption), then the simulator is trivial: it just generates a random string of size $|m|$.

It is then easy to show for the one time pad that no environment/distinguisher can make the distinction between to two last pictures (i.e. between the real world and the ideal world), because for any $r$ we can find $k$ such that $r = m \oplus k$, and all these keys are equiprobable. If you consider AES or other encryption schemes, then you need to prove that if the environment/distinguisher can make the distinction between the two world, then you can use the distinguisher to break a hardness assumption.
Now, you may wonder why is it a strong security guarantee. The first thing you can see is that if you have an attack against the real world (say, you can extract $m$ having access to $E_k(m)$ on Eve interface), then you could do exactly the same on the ideal world: so you could extract $m$ having access to a random string completely unrelated with $m$. Or if you consider the block "environment/distinguisher + simulator", you managed to extract $m$ having only access to the size of $m$... Impossible no? ;-) So it means that there exists no attack that is possible in the real world but impossible in the ideal world, i.e. the the real world is at least as secure as the ideal world. We can therefore continue our picture like that:

Then, you see that the composability comes "for free". Indeed, if you can attack the protocol by running another protocol in parallel or sequentially, then you could integrate that protocol into your environment/distinguisher and use it to attack the first protocol directly.
And to answer the OP's question
After all that, I still didn't have answer directly your question. So first your question does not completely makes sense since you usually compare an ideal functionality with a real world protocol, while in your question you compare two real world protocols. But then, indeed, if Eve (or rather the environment/distinguisher) can break your weak encryption scheme (we can continue our above example), then it will be easy for it to recover $m$ given $E(m)$ in the real world, and check if indeed it corresponds to the $m$ given as input to Alice. Now, in the ideal world, if it inverts the message $r$, it will find a message $m'$, but it is very unlikely that this $m'$ will match the $m$ that he gave to Alice. So the environment/distinguisher can easily make the distinction between the ideal and the real world: it tries to invert the message he saw on the channel, and check if it matches the $m$ given to Alice. If it does not, it means that it is talking with the ideal world! So it is not possible to prove the UC security of an encryption scheme that is weak ;-) (so that answers your last questions: Does this not violate UC?: yes, it does violate UC. Is it even possible for something to be breakable yet indistinguishable: no)
So usually, UC proofs are considered much stronger than usual game-based proof. However, they are much more difficult to prove, and there exist quite a lot of impossibility results.
Also, a last comment: you say something like "take a weak AES with only a few rounds", and indeed since it's not secure, it cannot be UC. But then you may wonder "what happens if we add one round? And two rounds? And 10 rounds? When is it starting to be back to UC?". So usually people consider asymptotic security, i.e. they take a security parameter $n$ (it could be linked with the number of rounds of AES, the size of the key...), and see what happens when $n$ goes to infinity. Then, they say that the protocol is secure if the distinguishing probability is smaller than $1/2+f(n)$, for some functions $f$ that is negligible, i.e. converges to 0 faster than any polynomial. So it does not make sense to say that AES is UC secure if we fix the size of the key and the number of runs, since in constant time you can break it (maybe it's a huge constant, but still independant of $n$). But you could talk about the AC security of AES, where the number of runs is $n$ and the size of the key is $n$. The reason why we like asymptotic security is also because in that regime, if a task A is easy to do, and if a task B is also easy, then you can also easily do both tasks A and B, and even repeat them a polynomial number of times. While if you are not in the asymptotic regime, then you don't have this nice stability property: if task A can be done in less than 100 years on one computer (a life time), and if task B can be done in less than 100 years on one computer, then A and B may not be done together in less than 100 years on one computer.
I hope this will help you to grasp what is behind UC/AC!
A remark on computationally secure Ideal Functionalities (spoiler: not really better than game-based security)
Again, as pointed out in comments, our Ideal Functionality is more precisely our definition of security (i.e. the protocol is at least as secure as the Ideal Functionality). So in practice, one could prove that a protocol realizes a completely broken Ideal Functionality (so just saying "the protocol is UC secure" is not enough to claim the security of the protocol, one also must check that the Ideal Functionality is indeed meaningful), or we could choose to define our Ideal Functionality to "look secure", i.e. be only computationally secure (for example, one could imagine that the Ideal Functionality leaks some encryption). However, my claim is that this kind of computationally secure Ideal Functionality is not very helpful:

First, it is quite hard to quantify the security of a computationally secure Ideal Functionality. If we consider for instance an Ideal Functionality that leaks the encryption of a message, then the first question will be "what can I learn from this ciphertext". And then, you would need to argue why this leakage is fine, so you will need to define some games that are hard to win... There is therefore no clear benefit of using simulable security over game based security in that context, since instead of defining games to quantify the security of your protocol, you will need to define games to quantify the security of the Ideal Functionality (i.e. the problem is just shifted from protocol to Ideal Functionality). Note that if the Ideal Functionality is information theoretically secure, the security is trivial to obtain and games are not even really required since most of the time it is obvious to see what is possible or not.
It is very easy to define computationally secure Ideal Functionalities that are very specific to one given protocol (one trivial way to do that is simply to take the Ideal Functionality that corresponds to the protocol itself). But then, if your Ideal Functionality is too specific (for instance because it hardcodes a given encryption function inside...), the benefit of using composable security framework is mitigated: when you use your protocol as a sub-protocols in bigger protocols, since existing literature is unlikely to have considered your very specific functionality, you will need to do a whole security analysis from scratch for any such big protocol. Which is basically what you would have do in game based security.
I'm also not aware of a single paper that defines such computationally secure Ideal Functionality. Of course, I do not know all papers, but still, I guess it shows that people do not really consider them.
Finally, I think that an important interest of simulation-based security is to abstract the protocol as much as possible and improve its modularity: this is very elegant, and having computationally secure Ideal Functionalities goes against that abstraction.

The only advantage I can see to consider computationally secure Ideal Functionality is to provide a simpler overview ofthe requirements of a protocol, but I'm not even really convinced.
For all that reasons, I don't think that having computationally secure Ideal Functionalities is really better than having game-based security.
Note that there also exist cases in which is is impossible to have information theoretically secure Ideal Functionalities, but where it is possible to have computationally secure Ideal Functionalities and game based security. See for example this paper (disclaimer, this last paper is a paper of mine (and is quantum), See section 3.4 for the computationally secure, unsatisfactory, Ideal Functionality and for a short similar discussion). You should be able to derive similar results for most impossibility results, including the impossibility of UC-secure commitment protocols, I just don't think they even bother to define a computational version of the Ideal Functionality (which could be, for example, an exact copy/paste of any commitment protocol).


Your description is vague but there are two levels of HMAC'ing required: you compute a series of intermediate values A0, A1, A2 ... where A0 is the 'seed' (see next) and each following value is HMAC_hash of the previous, and HMAC_hash each A1, A2 ... concatenated with 'seed' (see next) and concatenate those to produce P_hash and truncate to the final result.

Note an important change of scope: 'seed' in the P_hash and Ai formulas is the concatenation of 'label' and 'seed' from the PRF call. For clarity I use 'lbsd' as the name for this 'combined' version of 'seed'.

I find Java convenient for test/prototype code like this because you don't need to fiddle with low-level pointers, offsets, and such like C much less assembler, leaving it much easier to see (and verify) the logic. I display the series of 'A' blocks (A0, A1, A2 etc) and the corresponding pieces of P_hash which I notate P1, P2 etc.

So with this code

//nopackage
import java.nio.ByteBuffer;
import java.util.Arrays;
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;

public class Cry46549 {
    public static void main (String[] args) throws Exception {
        // java Cry46549 hmacname <file_containing_secret_seed_output # label is constant

        byte[] secret = new byte[16], seed = new byte[16], label = "test label".getBytes("ASCII");
        System.in.read(secret); System.in.read(seed); int want = System.in.available();
        // WARNING only in test code, stream.available() isn't reliable

        byte[] lbsd = Arrays.copyOf(label, label.length+seed.length);
        System.arraycopy(seed,0, lbsd,label.length, seed.length);
        Mac mac = Mac.getInstance(args[0]); mac.init(new SecretKeySpec(secret,""));
        byte[] A = lbsd; dump("A0:", A); ByteBuffer bb = ByteBuffer.allocate(want+64);
        for( int i = 1; bb.position() < want; i++ ){
            A = mac.doFinal (A); dump("A"+i+":",A);
            mac.update(A); byte[] P = mac.doFinal(lbsd);
            dump("P"+i+":",P); bb.put(P);
        }
        byte[] R = new byte[want]; bb.flip(); bb.get(R); dump("result:",R);
    }
    public static void dump (String heading, byte[] a){
        System.out.println (heading);
        for( int i = 0; i < a.length; i++ ){
            if( i%8==0 ) System.out.printf("%04x", i);
            System.out.printf(" %02x", a[i]);
            if( i%8==7 ) System.out.println();
        }
        if( a.length%8!=0 ) System.out.println();
    }
}

and the data for the P_SHA256 case from your link, lightly edited and xxd-r'ed into convenient binary, I get the following output, with desired final result as you can see:

A0:
0000 74 65 73 74 20 6c 61 62
0008 65 6c a0 ba 9f 93 6c da
0010 31 18 27 a6 f7 96 ff d5
0018 19 8c
A1:
0000 9f 5b b1 29 e2 f8 0a a4
0008 7b 67 05 b3 3e 21 4c c5
0010 e5 09 f2 83 e8 7b 3b e5
0018 e1 da a7 44 92 27 7d a1
P1:
0000 e3 f2 29 ba 72 7b e1 7b
0008 8d 12 26 20 55 7c d4 53
0010 c2 aa b2 1d 07 c3 d4 95
0018 32 9b 52 d4 e6 1e db 5a
A2:
0000 fc 16 6a 08 80 91 f7 6f
0008 af 99 35 9a 69 93 8f 75
0010 c1 54 24 63 8f 61 38 46
0018 34 24 37 32 b6 28 72 7b
P2:
0000 6b 30 17 91 e9 0d 35 c9
0008 c9 a4 6b 4e 14 ba f9 af
0010 0f a0 22 f7 07 7d ef 17
0018 ab fd 37 97 c0 56 4b ab
A3:
0000 fe 5f 7d 49 75 e1 23 c0
0008 d4 33 a3 a2 61 b6 42 c0
0010 58 04 46 46 1a f0 88 f0
0018 c7 9f 43 45 72 a1 a1 a6
P3:
0000 4f bc 91 66 6e 9d ef 9b
0008 97 fc e3 4f 79 67 89 ba
0010 a4 80 82 d1 22 ee 42 c5
0018 a7 2e 5a 51 10 ff f7 01
A4:
0000 3e fb 20 52 e4 76 f9 6c
0008 64 8d ca 6d 2d 00 8f b9
0010 75 ef b6 a4 83 60 be ec
0018 fd 47 a8 51 2b e7 3e eb
P4:
0000 87 34 7b 66 71 5a 92 bf
0008 c6 21 f0 17 10 81 1a b3
0010 8f 71 0e 7b 33 2f 44 10
0018 9e 42 fd 63 e4 7f 62 c0
result:
0000 e3 f2 29 ba 72 7b e1 7b
0008 8d 12 26 20 55 7c d4 53
0010 c2 aa b2 1d 07 c3 d4 95
0018 32 9b 52 d4 e6 1e db 5a
0020 6b 30 17 91 e9 0d 35 c9
0028 c9 a4 6b 4e 14 ba f9 af
0030 0f a0 22 f7 07 7d ef 17
0038 ab fd 37 97 c0 56 4b ab
0040 4f bc 91 66 6e 9d ef 9b
0048 97 fc e3 4f 79 67 89 ba
0050 a4 80 82 d1 22 ee 42 c5
0058 a7 2e 5a 51 10 ff f7 01
0060 87 34 7b 66