Let $J$ be the set of conspirators and $S$ the total set of shareholders.

In general you are correct, provided the polynomial $A'(x)-A(x)$ is not zero at $x=0$, where

$$A'(x)=\sum_{j \in J} y_j \prod_{k \in J:k \neq j}
\frac{ (x+W- x_k)}{(x_j+W-x_k)}
\prod_{k \in S \setminus J}
\frac{ (x-x_k)}{(x_j-x_k)},
$$
and
$$A(x)=\sum_{j \in J} y_j \prod_{k \in J:k \neq j}
\frac{ (x- x_k)}{(x_j-x_k)}
\prod_{k \in S \setminus J}
\frac{ (x-x_k)}{(x_j-x_k)}.
$$

The equation can be simplified into $$A'(0)-A(0)=0$$ by letting $x=0,$ into a polynomial in $W$ whose roots you have to avoid if you want to obscure the secret from the innocent shareholders.

Since the difference is a Lagrange polynomial  it is as secure as ordinary secret sharing so if you aren't in possession of $W$, its effect is uniformly distributed over the finite field.


Special equivalent key in symmetric encryption

Yes. Actually it is quite likely that there are quite a few such keys for block ciphers. That said, finding one takes a collision search which may take a lot of time, especially for ciphers with a large block size.

Proving that there are no other messages that permite to the same ciphertext may even be computationally infeasible.

It would not be a good property for a block cipher to have keys that are fully equivalent. It may not directly destroy all trust in the cipher but it would certainly raise a few eyebrows.


If double key DES is used then it is not very secure (63-80 bit security). If tree separate DES keys are used then you'd still have about 112 bits of security.

That's still not that much, but it would probably not be commercially viable to retrieve the keys of a sentinel using brute force as hacking the application itself is probably a lot more cost effective.

How secure the mode of operation is depends strongly on how the device is used. I'd strongly advice against using the device for anything other than (software protection and) licensing.

These kind of devices often use deprecated encryption that are just barely able to perform the task they've been designed for. When you are encrypting multiple blocks you may already go outside this framework.

That said, in principle the block cipher protects the key whatever mode is used. You'd still not be able to retrieve the key whichever mode you are using - outside brute force and attacking other locations that contain the key or key derivation information of course.


Proof of correctness of a homomorphic ElGamal sum

The question is not very clear about exactly what you want to prove and what is publicly known, but here's my answer, based on my best guess at what you mean:

Each party should publish $(R_1,S_1)$ and $(R_2,S_2)$.  They should also publish $(R_3,S_3)$.
Now anyone can verify that $(R_3,S_3)$ is a correctly-formed encryption of the sum of the messages corresponding to $(R_1,S_1)$ and $(R_2,S_2)$.  In fact, there is no need for any fancy zero-knowledge proof: given $(R_1,S_1)$ and $(R_2,S_2)$, anyone who is interested can re-compute $(R_3,S_3)$ on their own and verify that the result they obtained matches what was published.


Do not use raw RSA at all.

First simple attack starts when (plain ^ public_exponent) < n , i.e. when the message to be encrypted is small. Then there are more sophisticated attacks and forgeries as soon as 1 plain text and the corresponding cipher text are known, or even can be guessed. And then you have to review all possible attacks on RSA for the last 30+ years. No way.

Implement padding pkcs#1 named RSA-OAEP (based on MGF function, a variant of a feistel cipher).


Can one use a Cryptographic Accumulator to efficiently store Lamport public keys without the need of a Merkle Tree?

Yes, they can be used for that purpose.  The challenge in practice is exactly what you mentioned: if we're willing to trust number-theoretic assumptions, we usually don't need Lamport signatures.  Nonetheless, they can be used in this way.


AES and GOST 28147-89 "Magma" Comparison

I am trying to understand how AES is comparable to GOST

Except for them both being block ciphers, and relying on similar components (e.g. sboxes), there is actually very little similar to how they work internally.

GOST (Magma, as Squeamish points out, GOST is a fairly generic term) is a fairly straight forward Feistel cipher internally, where the block being operated on is split into two halves, and then one half is modified (based on the other half and the key); this is done 32 times.  Decryption is done by performing the cipher, but with an inverted key schedule.

AES, in contrast, is a Substitution/Permutation cipher; each round (except the last, which is slightly different) can be viewed as the concatenation of four operations, each of which operates on the entire block.  Decryption can be viewed as performing each of these suboperations in reverse (as each one is invertible).

  Like for parameters such as Bit shifting

AES doesn't have any explicit 'bit shifts'.  Now, one of the suboperations is called MixCollumns; in the forward direction, it involves a Galois multiply of the elements by 1, 2 and 3; I suppose you could look at multiplying by 2 and 3 as 'kind of' bit shifting, but that's a strained comparison IMHO.

  addition of the subkey to the input

Magma stirs in the subkey by xoring the input to the sbox (which affects the other side).  In contrast, AES xor's the subkey into the entire block.

  how S-BOX application in AES is different than GOST?

Magma uses the sboxes (8 different 4 bit to 4 bit sboxes) as a part of the Feistel function (to select the value that affects the other side).  In constrast, as one of the suboperations, AES applies the (single 8 bit to 8 bit sbox) sbox individually to each byte of the block (which implies that the AES sbox must be invertible).

  Why swapping of halves is not required in AES?

Because AES is not a feistel network.  Magma swaps halves, to make decryption easier (so that the decryption operation is precisely the same as the encryption operation, except that the key schedule is reversed).  AES uses a different method for doing decryption, and so it has no reason to swap halves.


Differential & linear characteristics for integer multiplication


They are both the same size, however they were created at different times during the factoring challenge, which is why one uses the bit size and the other uses the decimal size. They are created from different primes and are not directly related to eachother other than the fact they are both from the chllenge.

The first series of numbers in the challenge used the decimal size, of which 617 was the largest. Later they switched to the bit size, of which 2048 was the largest, and 576 was the smallest.

The decimal size numbers were last used in the challenge in 1997, and in 2001 the new set of challenge numbers with bit sizes were released.


In RSA, why does Alice's $N$ need to be relatively prime to Bob's $N$?

In RSA, the modulus is computed as $n=pq$ where $p$ and $q$ are prime. Given two moduli, if they have no primes in common, then the GCD is $1$ and they are relatively prime. If they share a prime factor, then the GCD will reveal that prime factor. Therefore, anyone who knows the two public keys can factorize the moduli and break security.


Why is diffie-hellman-group1-sha1 used instead of diffie-hellman?

This has been specified by the standard, steps 4 and 5 of the protocol described in RFC 4253:

  S generates a random number y (0 < y < q) and computes
    f = g^y mod p.  S receives e.  It computes K = e^y mod p,
    H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K)
    (these elements are encoded according to their types; see below),
    and signature s on H with its private host key.  S sends
    (K_S || f || s) to C.  The signing operation may involve a
    second hashing operation.
  C verifies that K_S really is the host key for S (e.g., using
    certificates or a local database).  C is also allowed to accept
    the key without verification; however, doing so will render the
    protocol insecure against active attacks (but may be desirable for
    practical reasons in the short term in many environments).  C then
    computes K = f^x mod p, H = hash(V_C || V_S || I_C || I_S || K_S
    || e || f || K), and verifies the signature s on H.

  This value (H) is called the exchange hash, and it is used to
  authenticate the key exchange.  The exchange hash SHOULD be kept
  secret.

  The signature algorithm MUST be applied over H, not the original
  data.  Most signature algorithms include hashing and additional
  padding (e.g., "ssh-dss" specifies SHA-1 hashing).  In that case, the
  data is first hashed with HASH to compute H, and H is then hashed
  with SHA-1 as part of the signing operation.

It then goes to define diffie-hellman-group1-sha1, just to show that SHA-1 is indeed the hash mentioned above:

  The "diffie-hellman-group1-sha1" method specifies the Diffie-Hellman
     key exchange with SHA-1 as HASH, and Oakley Group 2 [RFC2409] (1024-
     bit MODP Group).  This method MUST be supported for interoperability
     as all of the known implementations currently support it.  Note that
     this method is named using the phrase "group1", even though it
     specifies the use of Oakley Group 2.

So basically it is a hash over the parameters used for the key exchange. Without it the parameters may be changed by an attacker (the "active attacks" in the description) and the exchange would not be authenticated.


So if $M \approx 10^{20}$, and you have $4 * 10^{20}$ operations, why not just bruteforce it?

For more efficient solution, consider meet-in-the-middle technique. For all $1 \le a \le 4\sqrt{M} \approx 10^{20}$, make a hash table with values $a^e \mod{N}$. Then for all $1 \le b \le 4\sqrt{M} \approx 10^{20}$ check if $M^e/b^e \mod{N}$ is in the table.

Indeed, $M^e / b^e \equiv (ab)^e / b^e \equiv a^e \pmod{N}$ so it should be in the table (of course b must be invertible, otherwise it contains a factor of N and you can simply factorize N).

So total number of operations is $\approx 8\sqrt{M}$.


Homomorphic Encryption Notation Question

x is the plaintext and r is the randomness.


Disk/File modes of encryption and authentication

Beside XTS and CBC-ESSIV, are there any other modes of encryption that
  are commonly used?

No. Just look at software like Veracrypt (XTS only) or dmcrypt.

There was a third notable scheme for this purpose, LRW, but it's deemed not secure enough:

  The issues of LRW were:

  a) An attacker can derive the LRW tweak key K2
  from the ciphertext if the plaintext contains K2||0n or 0n||K2. Here
  || is the concatenation operator and 0n is a zero block.[3] This may
  be an issue for software that encrypts the partition of an operating
  system under which this encryption software is running (at the same
  time). The operating system could write the LRW tweak key to an
  encrypted swap/hibernation file.

  b) If the tweak key K2 is known, LRW
  does not offer indistinguishability under chosen plaintext attack
  (IND-CPA) anymore, and the same input block permutation attacks of ECB
  mode are possible.[4] Leak of the tweak key does not affect the
  confidentiality of the plaintext.

(from https://en.wikipedia.org/wiki/IEEE_P1619#LRW_issue)

  Which could be the most secure mode?

Depends on your requirements.

Both modes:
If the attacker can monitor changes of the data made by you (sounds like the attacker stole your computer, added something between harddisk and mainboard and gave it back), or at least get multiple copies at different point of times:
The attacker can do some traffic analysis, eg. he/she can detect if some block changed back to some data it had in the past. Ie. if you have a block has A, you change it to B, and later back to A (the same block, not different ones), then the attacker knows that the current content was there in the past too.
There's no real protection against this, but as said above, the attacker needs to monitor changes. Just stealing the laptop or anything like that is not enough (and if you get it back, don't trust it anymore, as simple as that. There are thousands of things that could be done while you weren't watching, many of them worse than just sniffing encrypted content).

XTS:
An attacker with similar monitoring capabilites, and also the possibility of changing blocks too, can roll back changes.
With the same A-B-A as above, (of course) the attacker can change your A block back to the B it was before (without knowing the unencrypted content, but still).
Just as reminder, overwriting the ciphertext is always possible, resulting in garbage after decryption. But here, it's not garbage, it's your own outdated content.
Tree-like integrity/authentication schemes (see below) mitigate this, but to be acceptable fast it needs to be integrated in the file system.

CBC-ESSIV:
It's always possible to change specific bits in the plaintext (even without monitoring changes or anything), if the attacker is willing to destroy another block for each changed block (=half of the blocks).
Again, tree-like integrity/authentication schemes mitigate this.

...if you want my opinion, XTS+auth.

  what are good methods to prevent a malicious person from modifying the
  data?

What you should NOT do:
Take every 4096byte-block (or some size like that), use eg. 4076 byte for data and 20 for an HMAC. Because
a) it doesn't solve parts of the problems above (eg. for XTS, replacing a block with it's old content means the old HMAC is there too ... failed); and
b) it's a mismatch with what OS+programs usually want. If the OS reads 8192 bytes (2*4096), you need a third block because the first two contain 40 byte HMACs and just 8152 byte data. A 4096 block for 40 byte... Then, when the OS wants the next part of the file, you either need to read the same block again (even slower, because non-sequential) or implement some sort of caching, which gets very cumbersome.

What you should NOT do either:
Collect the HMACs in own blocks. 4096/20 is about 204, so each 204 data blocks are followed by one block full of HMACs.
a) This does not solve the replacement problem either (the attacker can just replace a chunk of 205 blocks), and
b) It's even slower, because for every block you read/write, you also need the hash block which is far away (non-sequential to it's best).

What you could do on block-only-level (more secure but still slow):
Start like the solution above (full hash blocks), but also insert a second level of hash blocks (err, MAC blocks) for each eg. 200 hash blocks, a third level for each 200 second-levels, and so on, until you have one top block.
With this, replacing single blocks or any larger parts always can be detected, unless the attacker changes everything, ie. the whole disk content, back to it's old content etc. (this part can't really be solved with crypto. It's like exchanging the whole hard disk with one containing your old data. To mitigate this, you need to store the top block securely outside if the hard disk).
Problem is, again, slow because of non-sequential access. And calculating where the X-th data block is becomes a bit cumbersome because of the levels.

It won't get more secure. But depending on what you want to do, the slowness problem can be solved too: Don't do it just with blocks, without knowing their purpose, but integrate the hash tree into the file system.
There's no need to fetch additional blocks for the hashes, because they can be in the same place where filenames etc. are stored too. And knowing what blocks belong to the same file, detecting the programs access patterns for proper caching, etc.etc., all can be applied to the hash part too.


Update: 20210403
TL;DR

If correct, the paper would affect the security of a wide range of RLWE systems, including all of the most commonly used variants.
However, the paper violates a "no go" theorem of a reviewed and established paper by Peikert.

Putting to the side the question of whether the paper is correct or not, there are RLWE instances that do not take place in power of two cyclotomic rings (although it is by far the most popular choice). For the NIST process it is worth noting that both CRYSTALS submissions (KYBER and DILITHIUM), FALCON and SABER all do use power of two cyclotomic rings. NTRU however uses $x^{509}-1$, $x^{677}-1$ and $x^{821}-1$, NTRUPrime does not even use a cyclotomic ring.
Thus even if the claims are met, they do not break all ring lattice systems, nor even all NIST ring lattice candidates.
(Technically the NTRU and LWE problems are distinct, though both are solved in practice by solving SVP/CVP instances, so I'll abusively elide the difference between RLWE and ring lattice instances).
The paper claims to break  decisional RLWE (distinguishing $(\mathbf a, \mathbf {as}+\mathbf e)$ from $(\mathbf a, \mathbf b)$ as opposed to recovering $\mathbf s$ and $\mathbf e$) in power of 2 cyclotomic rings. It then claims a quantum attack on a short sub-basis question. By section 5 of the LPR paper a decisional RLWE method would convert to a search RLWE method on cyclotomic rings (thanks to Mark and Chris Peikert for pointing out this reduction). This observation is not made in section 3.4 of Hao Chen's paper.
In terms of the distinguishing attack, the nub of the idea seems to be that we can find a sublattice $\mathbf L_2$ which contains both an ideal lattice $\mathbf Q$ that is dense enough that quite a few random elements end up in there and another sublattice $\mathbf L_1$ where error vectors have an elevated chance of appearing (e.g. the chance of an error vector appearing in $\mathbf L_1$ is twice the chance of a random vector appearing in $\mathbf L_2$). Then, if given a large collection of $(\mathbf a,\mathbf b)$ pairs from which we must guess the ones where $\mathbf b$ was generated from $\mathbf b=\mathbf{as}+\mathbf e$ we specialise to the subset where $\mathbf a\in \mathbf Q$. If generated via RLWE then $\mathbf{as}\in \mathbf Q\subset \mathbf L_2$ by the ideal property and $\mathbf e\in \mathbf L_1\subset \mathbf L_2$ with elevated probability, thus $\mathbf{as}+\mathbf e\in \mathbf L_2$ with elevated probability. If we therefore pick the $(\mathbf a,\mathbf b)$ pairs where $\mathbf a\in Q$ and $\mathbf b\in L_2$ and declare these to be RLWE instances, we would be more likely to be correct. Cyclotomic lattices do lend themselves to a wide choice of $\mathbf Q$.
However, lattices such as $L_2$ cannot exist for worst case error distributions. Section 5 of the Peikert paper linked in the TL;DR shows that if $\mathbf Q$ is dense enough to contain many $\mathbf a$, then the distribution of errors for worst case error distributions is smooth (i.e. does not have elevated probability) in $\mathbf Q$ and hence $\mathbf L_2$. Provably-hard ring LWE instances will usually have some reduction to worst case error distribution.
The "no go" observation is due to Chris Peikert and is largely taken from his twitter feed as linked in the paragraph above. Any errors and misrepresentations are due to me.


How can complexity be increased or decreased in AES?

This begs the question, why would you in any real-world circumstance wish to reduce the difficulty for an attacker to break your cryptosystem?

To answer your question practically, the only reasonable way I can think of to accomplish this is to simply reduce the entropy in the key. At 100%, all 128 bits of the key are used. At 50%, 64 bits of the key are used, and the rest set to some static value (e.g., 0). At 25%, 32 bits of the key are used, and so on.

That said, I want to reiterate that there is no reason I can possibly conceive of to support such a feature, outside of sheer curiosity.

Edit: Note that this will result in an exponential decrease in security, which maps well onto how cryptographers typically think of the security of a system. Modern ciphers like AES-128 so strong that a 100-fold reduction in difficulty to break still leaves brute force well outside the realm of conceivable human feasibility ($\frac{2^{128}}{10^{2}} \equiv 2^{121}$).


As I said above, I feel the question is bit off-topic here. However, there does not seem to be too good a place in SE for questions that combine mathematics and programming on VHDL, where target is obviously something cryptography related.
Most questions regarding FPGA are seen in electronics.stackexchange.com.

Montgomery reduction in Wikipedia is useful description of Montgomery reduction. The value of R you usually use is the same than word size used in processing. In your case, it could be $2^{256}$ or $2^{64}$ depending on how you implement the montgomery multiplier. If you have multiple $64*64$ bit multiplier units, you may want to use them in parallel, to perform large multiplications and/or montgomery reductions at once.

Assuming you had two multipliers available, one way around this would be using one multiplier for 64*64 multiply and another for montgomery reduction of previous 64*64 multiply, and thus R would be $2^{64}$. Then you would need to build 256*256 from e.g. 16 executions of 64*64 multiply. But, the algorithm, approach and processing pattern somewhat depends on how many multiplier you have available. Notice that you do not need to use rectangular size: you may build 128*64 montgomery step (from e.g. 4 multipliers) and you can use it to build 256*256.

The speed of different implementation decisions in the end depend on your target platform. Likely you need to design and implement appropriate benchmarks yourself.

Coming back to the original question. Overall, it is often most efficient to work locally i.e. inside one 64 bit / 128 bit word, i.e. to try to constrain each handling path to process word at time. (I.e. choice 2.)
Note: you cannot restrict all operations to work in 128-bits, but occasionally need to handle carries etc. concerns.

Advice

Or how to proceed in practice.

In case you are experienced with "ordinary" programming languages in addition to the HDL language you use (often verilog or VHDL), I would propose first trying to make functional model of the multiplier in one of usual programming languages and comparing the results against some existing big number multiplier code, because it may appear that it is not always completely straight forward to build correctly functioning processing step.

There may be inexpensive already existing design for your FPGA, available for licensing with reasonable cost. It may be superior option compared to doing it your self. (For SW implementations I also recommend using one of existing libraries, and in fact for HW this same choice usually exists as well.)

If side-channel attacks (such as timing) are considerable threat in your use, you'll need to carefully consider the side channels during the implementation. Standard "basic" implementation of montgomery reduction is not side channel free.


Counting the $\operatorname{XOR}$ of an Element over the Finite Field $\operatorname{GF}(2^q)$

Let $f=x^q+t$ be an irreducible polynomial, then

  $$\alpha\cdot \beta= (\alpha_{q-1},\dots,\alpha_0)\cdot(\beta_{q-1},\dots,\beta_0):
\bigoplus_{i=0,\alpha_i\neq0}^{q-1}\big( \alpha_i\cdot(\beta<<i) \oplus (\bigoplus_{j=1}^{i} \beta_{q-j}\cdot x^{j-1}\cdot t)\big).$$

With this formula, you can easily calculate XOR count of $\alpha$. Although there may be a simpler solution to answer your question.
Note that in this formula, several $\beta_ k$ may be xor with each other, which should not be taken into account in the XOR count calculation. For this, a $q\times q$ matrix can be used for implementation.

Edit: As an example, let $f=x^8+x^4+x^3+x+1=x^8+t$. Then
$$(x+1)\cdot \beta=\alpha_0\cdot (\beta_7,\dots,\beta_0)\oplus \alpha_1\cdot (\beta_6,\dots,\beta_0,0)\oplus \beta_7 \cdot t=(\beta_7,\dots,\beta_0)\oplus (\beta_6,\dots,\beta_0,0)\oplus (0,0,0,\beta_7,\beta_7,0,\beta_7,\beta_7)=(\beta_7\oplus \beta_6,\beta_6\oplus \beta_5,\beta_5\oplus \beta_4,\beta_4\oplus \beta_3\oplus \beta_7,\beta_3\oplus \beta_2\oplus \beta_7,\beta_2\oplus \beta_1,\beta_1\oplus \beta_0\oplus \beta_7,\beta_0\oplus \beta_7).$$
So, the XOR count of $x+1$ is $11$.


Isn't Socialist Millionaires vulnerable if Alice's and Bob's message are picked from a shared list?

The attack you are referring to is called an offline dictionary attack, which checks all possible values against a given transcript. However, the typical security notion for the socialist millionaires problem should forbid this attack. In fact, designing a protocol which is secure "except for offline dictionary attacks" is trivial: both players simply hash their input, with some public hash function, and exchange the outputs; if they are equal, then they own the same value; otherwise, they don't. Attacking essentially amounts to hashing all possible messages.

The protocol you describe is more complex, and it is in fact immune to such offline dictionary attacks; it's main purpose is essentially to avoid them. The error in your reasoning is the following sentence:

  He knows $h^{ab}$ and $h^{\alpha\beta}$ from two other DHKE's they did.  So Bob can raise one to the power of the other and get $h^{ab\alpha\beta}$.

This is not true: one can compute $h^{ab\alpha\beta}$ from $h^{ab}$ and $\alpha\beta$, or from $h^{\alpha\beta}$ and $ab$, but not from $h^{ab}$ and $h^{\alpha\beta}$. Computing $h^{ab\alpha\beta}$ from $h^{ab}$ and $h^{\alpha\beta}$ is equivalent to breaking the computational Diffie-Hellman assumption. In fact, under the decisional Diffie-Hellman assumption, $h^{ab\alpha\beta}$ is indistinguishable from random, even given both $h^{ab}$ and $h^{\alpha\beta}$. This is the observation that underlies the security argument for this protocol.


Why is it a security problem that two RSA moduli are not co-prime?

The public key is actually $(n,e)$ where $n = p \, q$: it's the modulus, which is the product of the two primes, that appears in the public key.

Suppose that you have two public keys $(n_A, e_A)$ and $(n_B, e_B)$ with $n_A \neq n_B$, and that $\gcd(n_A, n_B) \neq 1$. You have a common divisor of both $n_A$ and $n_B$. But $n_A$ and $n_B$ have only two divisors each, the two primes. Therefore $\gcd(n_A,n_B)$ is one of the secret primes of both keys, and the other secret primes are trivially $n_A / \gcd(n_A,n_B)$ and $n_B / \gcd(n_A,n_B)$.

This shows that it's critical that in an RSA key, both primes are unique.

Knowing a factor of the two totients may or may not reveal the private key. If the factor you have is $4$, that doesn't give you any information: $(p-1)(q-1)$ is always a multiple of $4$. If the factor you have happens to be $p-1$ or to let you find $p-1$, that's obviously a problem. But since the totient is not normally exposed anywhere, this isn't a common concern.


Is the one-time pad still perfectly secret if all-zero keys are excluded?

Yes your solution is correct; the flawed OTP scheme is no longer perfectly secret if there are fewer keys than messages.

Once you remove the all zero key the property
$$
\mathbb{P}[M=m|C=c]=\mathbb{P}[M=m],\qquad \forall m,\forall c,\quad(1)
$$
required for perfect secrecy will no longer necessarily


Is there an economic way to check if an eliptic curve point in jacobian coordiate is the same as a compressed point

Computing the $z^{-1}$ is very cheap. We can do this by Euclidean algorithm, and in logarithmic time. But you can set $z=1$ in projective coordination. This make computations easy($O(1)$ since $z^{-1}=1$), and with this representation you can see the equality of points evidently.

  Note that, instead of computing $y=b*z^{-3}$ you can check  $y*z^3=b$. In this state, you don't need to finding multiplicative inverse.

Also in powerful programs such as MAGMA, $z$ is equal to $1$, by default.


Can neural cryptanalysis be applied to AES?

No. Neuro-Cryptanalysis fails on serious ciphers, including DES and AES.
Sebastien Dourlens's Neuro-differential cryptanalysis of DES (in sections 5.4.2 and 5.4.3 of his 1996 mémoire) learns an S-box. Applied to Unix crypt (section 5.4.4), it memorizes passwords/hash pairs (by a training requiring "from several days to several years") and then merely performs a quick retrieval; something a hash table does routinely and quickly! Neither is relevant to cryptanalysis.
Mohammed M. Alani's Neuro-Cryptanalysis of DES and Triple-DES (in proceedings of ICONIP 2012) claims cryptanalysis of DES or 3DES from 2048 or 4096 examples in an hour of Matlab on a standard PC; but there is no indication that it recovers the key or is  otherwise capable of predicting more input/output mappings than supplied in training (even though the later is a stated objective). My guess is that - at best - it performs similar plaintext/ciphertext memorization thru training.

Update: there recently has been noteworthy progress in the field of neuro cryptanalysys, with Aron Gohr's Improving Attacks on Round-Reduced Speck32/64 using Deep Learning, in proceedings of Crypto 2019. It's further analysed by Adrien Benamira, David Gerault, Thomas Peyrin and Quan Quan Tan in A Deeper Look at Machine Learning-Based Cryptanalysis (eprint, March 2021).


ECDH and ECDSA in PGP with known public key

Sounds like a description of ECIES to me. ECIES is a hybrid cryptosystem that builds upon ECDH.

Basically: the static public key of the receiver is used together with an ephemeral key pair generated at the sender. The public key of the receiver and ephemeral private key of the sender are used to generate a "shared secret" using ECDH. This shared secret is used with a KDF to generate a session key. This session key is used to encrypt the message. Then the ephemeral public key is attached to the ciphertext. The private key can be safely destroyed.

To decrypt the same secret is calculated at the receiver using the static private key and the public key attached to the ciphertext. The KDF is applied again to generate the session key. Then the resulting key is used to decrypt the ciphertext.

As you can see, after encryption the sender isn't needed anymore. So this scheme can be used to encrypt static data such as files. The only thing the sender needs is a trusted public key to the receiver. This public key is for instance embedded in the PGP certificate of the receiver.


Encryption using static AES256 symmetric key vs ephemeral session key

What is the risk of using a static symmetric key for encryption vs a session key that changes each time?

Flexible access control: A big reason to use session keys is that it is easier to adjust your access control. It seems to me that the access for the files is not different. As long as that remains the case there is no direct need to use different keys to protect the data. However, with session keys you can make a different access control scheme without having to re-encrypt your data.
Access to the keys: remember that key management has a lot to do with the accessibility. It doesn't make much sense to use multiple keys if they are evenly vulnerable to attacks. However, patient information can get relatively large. It might be feasible to protect the master key better than the session keys that are required to decrypt large amounts of data.
Limitations of modes of operations and IV's: Modes of operation such as CBC do have limitations. If you would be encrypting large amounts of data then you might get into trouble in case the input of the block cipher repeats, as it would generate the same ciphertext block, and that would leak information to an adversary.
Forward secrecy: You already mentioned forward security, where the leakage of a session key doesn't compromise the confidentiality of data encrypted with other session keys.

What you could do is to encrypt the session keys with the master key. This may not feel more secure, but it does allow you keep the master key safe, possibly in a more secure system or device.

Another option that you could use is to use a key derivation function or KDF that derives session keys from the master key. That way the limitations of the mode of operation can be diminished. You may also use any kind of information rather than to use a specific IV. A KDF also solves the problem of the forward secrecy as you cannot derive the master or any of the other keys given a session key. This way you don't have to store any session keys; you don't however get the same flexibility as wrapping (encrypting) session keys.

  How good/bad is this setup in general? Any other problems I am overlooking in this setup?

That's a very broad question. I would not consider OpenPGP. Not so much because the protocol is bad, but it simply hasn't designed for this kind of operation. Furthermore, it is a rather old protocol which hasn't been updated to support the latest / greatest algorithms. More importantly, I don't thing the PGP method  of distributing keys does justice to a rather hierarchical setup used mainly at hospitals. X.509 may make a lot more sense.

RSA 2048 is not considered all that secure anymore, giving a security strength of about 112 bits. See keylength.com to see some comparable key strengths. Using it together with AES-256 gives you and your users a false sense of security. You may have to go for Elliptic Curve crypto and preferably an asymmetric Post Quantum Crypto algorithm to provide 256 bits of security. This may require long term security, after all.

With regards to algorithms, I think you should learn about new modes of operation such as AEAD modes of operation. Using AES-CBC is fraught with dangers; I would not consider CBC mode best of breed anymore.


Jean-Philippe Aumasson (the principal author of SipHash) has kindly
answered my question by email and acknowledges that he is unaware of
an efficient HashDoS attack against SpookyHash. This does not imply that
no such attack exists, only that he was unable to find one rapidly.


Do any probabilistic hashing algorithms have additive homomorphism?

The outputs must exhibit additive homomorphism such that some operation on $f(a)$ and $f(b)$ will equal $f(a+b)$.

Because $f$ is mandated to be nondeterministic, I assume that the requirement be that $f(a) \odot f(b)$ be some possible output $f(a+b)$ (for some computable operation $\odot$).

If so, there must be some further requirement; here's one $f$ function that meets the above requirements in a spectacularly unuseful way:

$f(x)$ is a nondetermanistic function that ignores the input $x$ and generates a random bit string of length $n$ (for a suitably large value of $n$).

Then:

For any input, there are $2^n$ possible outputs; if $n$ is large enough, this easily meets the 'trillions of possible outputs'
Examining the output does not allow the input to be deduced - obviously true.
There must be an operation on $f(a)$ and $f(b)$ that yields a possible output of $f(a+b)$ - for this, we can pick any arbitrary operation $\odot$ that maps two $n$ bit inputs to an $n$ bit output, and then we have $f(a) \odot f(b)$ is a possible output of $f(a+b)$.

Obviously, this function $f$ is unlikely to solve the specific problem you have in mind - what additional requirements are there?


AES-GCM ciphertext that deciphers under two keys

How can we exhibit an [AES-GCM][1] ciphertext, including IV and 128-bit authentication tag, and distinct keys $K_0$ and $K_1$, so that decryption succeeds for both keys?

It's quite easy (if you grok linear algebra in $GF(2^{128})$
Here's what you do:

You arbitrarily select the keys $K_0$ and $K_1$,  the nonce and the ciphertext/AAD (except for one block, which can be anywhere, including in the AAD); we'll assume that the one block is at indes $i$ (where the last block of the ciphertext is index 2, the next to last is index 3, and so on - this rather odd convention is related to how GCM works internally).

We then compute the GCM authentication key $H_0 = AES_{K_0}(0)$ and $H_1 = AES_{K_1}(0)$
Then, the tag for the message with $K_0$ can be expressed as:
$$C_0 + M_i H_0^i$$
where $C_0$ is a function of $K_0$, the nonce and the selected message, AAD blocks, and $M_i$ is the value we'll place into ciphertext block $i$.  One easy way to compute it is to insert a 0 where $M_i$ would go, and compute the tag as normal.
Similarly, the tag for the message with $K_1$ is:
$$C_1 + M_i H_1^i$$
So, to find $M_i$ so that they have the same tag, we equate the two, resulting in:
$$M_i = (H_0^i + H_1^i)^{-1}(C_0 + C_1)$$
(Remember, we're in $GF(2^{128})$; addition and subtraction are the same operation, so we usually express it as addition; in a different field, this would be written as $(H_0^i - H_1^i)^{-1}(C_0 - C_1)$)
Put that into the ciphertext, include the appropriate tag (computable by the above formula), and there you go.
This approach can be extended to finding a message that'll decrypt with $k$ different keys (by using $k-1$ free blocks).

Can that extend to the point that this nightmare of the same encrypted and authenticated ciphertext decrypting to two meaningful but wildly different documents holds (for some standard document/archive format)?

Not quite; the attacker can pick the ciphertext so that it'll decrypt under one of the keys to a chosen message (except for that one block); however that gives him no control over the other decryption.
By making a reasonable assumption on AES, it would appear provable that the attacker cannot do significantly better (at least for 96 bit nonces).  GCM translates ciphertext to plaintext (assuming a valid decryption) by the operation $P_i = C_i \oplus AES_k( N(i) )$, where $N(i)$ is the nonce and the block index combined).  Hence, the xor of the two decrypted plaintexts will be, for that block $AES_{k_0}( N(i) ) \oplus AES_{k_1}( N(i))$, and that wouldn't be controllable.
Nonce sizes other than 96 bits would be harder to analyze (as $N(i)$ now becomes a function of the key); however there wouldn't be an obvious approach to break that either.


How to find the inverse of a 3x3 MDS matrix

Your matrix contains 2 which is not an element of $\operatorname{GF}(2^8)$ unless it means $x$. In this case, we can use SageMath to find the inverse as
R.<x> = PolynomialRing(GF(2), 'x')
S.<y> = QuotientRing(R, R.ideal(x^8+x^4+x^3+x+1))
S.is_field()
S.cardinality()
y^8 + y^4 + y^3 + y + 1

A = matrix(S,[[1,y,y],[y,y,1],[y,1,y],])
A.inverse()

That produces this output
True
256
0

[                                  1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1]
[y^7 + y^6 + y^5 + y^4 + y^2 + y + 1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1                                   1]
[y^7 + y^6 + y^5 + y^4 + y^2 + y + 1                                   1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1]

The matrix written in standard binary representation is:
$$\begin{bmatrix}
  00000001 & 11110111 & 11110111 \\
  11110111 & 11110111 & 00000001 \\
  11110111 & 00000001 & 11110111
\end{bmatrix}$$


You benchmarked a highly optimized AES implementation against a reference implementation of CLEFIA:

 * NOTICE
 * This reference code is written for a clear understanding of the CLEFIA
 * blockcipher algorithm based on the specification of CLEFIA.
 * Therefore, this code does not include any optimizations for
 * high-speed or low-cost implementations or any countermeasures against
 * implementation attacks.

On top of that it's possible your phone's CPU has hardware acceleration for AES.


AES - Finite Field Multiplication on 8 Bit Platform

I. Polynomial representation
$b_7b_6b_5b_4b_3b_2b_1b_0$ represent the polynomial in $\operatorname{GF}(2)[X]$: $b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0x^0$ .
$\texttt{02}$ is $\texttt{00000010}$ thus $0x^7+0x^6+0x^5+0x^4+0x^3+0x^2+1x^1+0x^0 = x$.
$b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0x^0 \cdot x = $
$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0$
or $b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}$
that is equivalent to $b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1 = b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}$
II. Modulo reduction by $x^8 + x^4 + x^3 + x + 1$:
This leads to two problems:

you have a loss of information: you cannot invert the S-box (which would be anoying in the case of AES)
the upper bit does not fit into the byte

That is why there is the $\bmod m(x)$.

In the specification of Rijndael, we consider the bytes as polynomials. Byte addition is defined as addition of the corresponding polynomials. In order to define the byte multiplication, we use the following irredutible polynomial as reduction polynomial:
$m(x) = x^8 + x^4 + x^3 + x + 1$. (2.29, p.16)

Thus we will reduce $b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0 \mod m(x)$.
Remark that:
$x^8 + x^4 + x^3 + x + 1 \equiv 0 \mod m(x)$
by $a \equiv c \mod m \iff a - b \equiv c - b \mod m$ we have
$x^8  \equiv - x^4 - x^3 - x - 1 \mod m(x)$
because $-1 = 1$ in $\operatorname{GF}(2)$
$x^8  \equiv x^4 + x^3 + x + 1 \mod m(x)$
Thus (going back to our previous equation):
$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0 \mod m(x) = $
$b_7(x^4 + x^3 + x + 1)+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1= $
$b_7x^4 + b_7x^3 + b_7x^1 + b_7x^0+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1= $
grouping by power this leads to:
$b_6x^7+b_5x^6+b_4x^5+b_7x^4 + b_3x^4+b_7x^3 + b_2x^3+b_1x^2+b_7x^1 + b_0x^1+b_7x^0= $
in other terms:
$b_6x^7+b_5x^6+b_4x^5+(b_7 + b_3)x^4+(b_7 + b_2)x^3+b_1x^2+(b_7 + b_0)x^1+b_7x^0$
III. $\ll$ and $\oplus$
Addition over $\operatorname{GF}(2)$ is equivalent to a XOR ($\oplus$) thus we find the previous formula:
$b_6x^7+b_5x^6+b_4x^5+(b_7 \oplus b_3)x^4+(b_7 \oplus b_2)x^3+b_1x^2+(b_7 \oplus b_0)x^1+b_7x^0$
In the end the multiplication of $b_7b_6b_5b_4b_3b_2b_1b_0$ by $\texttt{02}$ can be seen as:
$(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus \texttt{000}b_7b_7\texttt{0}b_7b_7$
or with a conditional XOR:
$(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus b_7\cdot(\texttt{00011011})$


Hill cipher: How to find an unknown key of unknown size

Assuming that $2\times2$ matrix is used, and the encryption starts from the first letter of the plaintext, the key can be found by just calculating the "encryption" with size of $4$ plain- and cryptotext block.

For example, for CONV $\rightarrow$ SQZH, it would go as follows:
$$\begin{pmatrix}
2 & 14 \\
13 & 21
\end{pmatrix}\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}=
\begin{pmatrix}
18 & 16 \\
25 & 7
\end{pmatrix}\pmod{26}$$

Then solving for $a,b,c,d$, the key $K$ is found.
As here the plaintext matrix is invertible, one can compute

$$\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}=\begin{pmatrix}
2 & 14 \\
13 & 21
\end{pmatrix}^{-1}
\begin{pmatrix}
18 & 16 \\
25 & 7
\end{pmatrix}\pmod{26}$$


Function to polynomial equation in GF(2)

The formula
$$ d+e+ac+ae+bc+be+cd+de+ade+ace+abd+abc $$
is in algebraic normal form (ANF).
That is the unique representation of our boolean function with respect to the $\mathbb F_2$-basis $\{a^ib^jc^kd^le^m\mid i,j,k,l,m\in\{0,1\}\}$ of the space of boolean functions $\mathbb F_2^5\to\mathbb F_2$.
In particular, note "$+$" is exclusive or.

I do not think the Karnaugh map is very helpful in that case, since grouping the $1$ entries in the table becomes a bit tricky, and since you have to avoid negations. In the end, it works, but it's more involved than just drawing a few rectangles and reading off the right terms.

Instead, the algebraic description above provides an easy iterative method to compute the ANF. (See also this Math.SE post.)
Basically, the ANF for our function $f$ will look like this:
$$
f(a,b,c,d,e) =
x_0+
x_aa+x_bb+x_cc+x_dd+x_ee+
x_{ab}ab+x_{ac}ac+x_{ad}ad+x_{ae}ae+x_{bc}bc+x_{bd}bd+x_{be}be+x_{cd}cd+x_{ce}ce+x_{de}de+
x_{abc}abc+x_{abd}abd+x_{abe}abe+x_{acd}acd+x_{ace}ace+x_{ade}ade+x_{bcd}bcd+x_{bce}bce+x_{bde}bde+x_{cde}cde+
x_{abcd}abcd+x_{abce}abce+x_{abde}abde+x_{acde}acde+x_{bcde}bcde+
x_{abcde}abcde
\text,
$$
and we are interested in computing the unique coefficients $x_\ast\in\{0,1\}$.
To do so, we restrict the target function $f$: Setting enough variables to zero will simplify the above formula sufficiently to fully determine another coefficient.

To start with, we consider the "restriction" $f(0,0,0,0,0)$. By the above formula, this is just $x_0$.
Next, we consider $f(a,0,0,0,0)=x_0+x_aa$: Since $x_0$ is already known, $x_a$ may be recovered as $f(1,0,0,0,0)+x_0$ (modulo $2$ of course). The coefficients $x_b$ through $x_e$ are computed analogously.
For $x_{ab}$, consider $f(a,b,0,0,0)=x_0+x_aa+x_bb+x_{ab}ab$: The coefficients $x_0$, $x_a$ and $x_b$ are already known, so we can compute $x_{ab}=f(1,1,0,0,0)+x_0+x_a+x_b$. Again, $x_{ac}$ through $x_{de}$ work exactly the same.
Repeating this procedure will eventually yield all the coefficients.

In case you just want the result without going through the process manually, note that sage provides the relevant functionality.


Why use 256-bit symmetric encryption when the key is exchanged using asymmetric cryptography that only provides 112 bits of security?

As indicated with Ryan, the key size for RSA is not a configuration option of a TLS ciphersuite. The RSA key size is part of the authentication phase which is part of the TLS protocol, but it is not configured through the ciphersuite definitions. So the RSA_ ciphersuites and ECDHE_RSA ciphersuites do not specify any key size for RSA.

The AES key size is however a configuration option. This is because the AES keys are not static, they are session keys and session keys are ephemeral. They will be generated on each new TLS connection. To generate the right size AES key the size must be known beforehand, otherwise the key derivation cannot take place.

Usually you would link a 2048 bit RSA key with either AES-128 or 3 key triple-DES. However it's perfectly possible to derive AES-256 session keys using RSA-2048. It won't harm performance much either; AES-256 is only marginally slower than AES-128 using a software implementation (in hardware the difference may even be non-existent). So there is no penalty to using AES_256 in a ciphersuite. Allowing any AES ciphersuite - regardless of key size - may help (somewhat) with the establishment of a good ciphersuite - i.e. compatibility between client and server.

As indicated before, the RSA key may just be used to establish authentication. ECDHE or DHE may be used to establish the session keys to provide forward secrecy. So the strength of the keys used for confidentiality may be much higher then the key used for authentication.

As the authentication is required to happen in real time the strength of the authentication key may be significantly lower to the one used to provide confidentiality: it may be that an attacker can recover interesting information a long time after the connection as established (and eavesdropped). The authentication key may be revoked or be over the date of expiry a long time before that.

Then again, if you specify just AES_256 ciphersuites or put AES_256 above AES_128 ciphersuites you are basically lying to your users. You are offering a kind of protection that you cannot deliver due to the small key size used for RSA.

I would not feel comfortable doing so even when I would combine RSA with a ciphersuite offering forward secrecy.


Why would we use a Key Agreement Protocol if we already have a key between 2 entities?

Hint

Consider what would happen if an adversary somehow managed to recover the session key.

Spoiler

If they simply used the shared key as the session key directly, then an adversary who compromises the key can then compromise all future communications.

If they derive the session key using the shared key, then an adversary who compromises the session key only compromises the current session.

Why not just use DH?

There are plenty of reasons - the first is probably to demonstrate the point above.

Secondly, DH is more computationally expensive then the pre-shared key technique.

Some real world protocols do in fact offer the ability to secure a communications channel via pre-shared keys.
A constrained device may not be able to afford the circuit size/power/time/bandwidth to use DH


Asymmetric algorithm for one time signing of small cleartext

One algorithm that is especially suited to one-use key pars is lamport signatures. Like many (all?) other signature functions, lamport signatures first hash the message to get it down to a size that is more reasonable to sign.

For this use case, if you are willing to have $n^{2}$-bit signatures and $2n^{2}$-bit keys (public and private), you can sign a $n$-bit (or less) message with only a one-way function, by skipping the hash message step and just signing the message directly.

This is nice, because the security of all hash functions and many other algorithms relies on one-way functions. Using such a simple algorithm also removes most attack vectors (the remaining one is the one-way function, which is still an attack vector with most (all?) complex signature schemes).

There are various ways to reduce the sizes required.


Well, the reason we add salt when hashing passwords is not to make a single hashed password stronger (it doesn't, except in a way I'll explain below), it's to fix up some weaknesses that appear when you have a collection of hashed passwords.

If the attacker somehow gets a single hashed password, then adding a salt doesn't really slow the attacker down (assuming that he gets the salt as well; since the salt is commonly stored with the hashed password, this is a reasonable assumption). Without the salt, the attacker can guess various passwords, hash them, and see if any of them hashes to the target value.  With the salt, the attacker simply includes that when he hashes his guesses, and so that doesn't make his job any harder.

However, if the attacker gets a list of hashed passwords, then adding a salt does make the attacker's job harder.  Without the salt, the attacker can guess various passwords, hash them, and see if any of them hashes to a value on the list; if he has a collection of 1000 hashed passwords, he has just checked 1000 passwords with a single hash.  On the other hand, if each hashed password includes a salt, and if each salt is different, then to check to see if a guessed password is accurate, he has to run 1000 hashes (with each hash using a different salt); this does make his job harder.

In addition, there are clever ways that an attacker can use to precompute hashes of various possible passwords (and store those in a manner that is considerably more compact than the list of hashed passwords).  Without salt, the attacker who has spent the time to create the table can quickly check if any of the hash passwords happen to be one of the ones he has precomputed.  It turns out salt interferes with those as well (because the salt is another thing that the precompute method would need to guess, and if the salt is of reasonable size, this is impractical).

Now, when I mentioned above that there is a way that a salt makes even a single password stronger, it's because of these precomputation methods.  It makes the use of a precomputed table impractical.  The attacker can still do a dictionary search on the hashed password, but he has to do the computation after he has obtained the hashed password (and he can't reuse that effort to attack anything else).

Finally, the other thing that salt helps with is to obscure whether two passwords happen to be the same.  Without salt, two identical passwords will hash to the same exact value, which an attacker that gets the hashed values can see.  Even if the attacker can't tell what the common password is, it may give him information that we don't want him to have (such as "User X" and "User Y" are the same physical person).  With salt, there is no such information leakage.

You also asked about salt length; from the above discussion, it should be obvious that we want salt values to be unique.  One easy way to make them unique is to choose them randomly, and make them long enough that collisions (that is, two passwords get the same salt) are unlikely.  In general, if we can expect to have $N$ different hashed passwords, we'll want at least $N^2$ different salt values (with more being better); 10 random alphanumeric characters does this nicely.  As for always picking the same salt length, well, since we assume that the attacker can see the salt values, we don't want the salt lengths to leak any information about the password.  Choosing the same length for all salts achieves this nicely.


Signature generation using hash function

The private key is actually the private exponent. Signature generation is modular exponentiation using the private exponent and - of course - the modulus. So you first hash a value for x using the hash function, giving you another value, say $h$. Now you perform the modular exponentiation on it and return the result. And that's all there is to it.
Note that you should not perform modular exponentiation by first perform exponentiation and then take the modulus: you can use the modulus in the intermediate steps (e.g. multiplication).
Do not think of signature generation as encryption with the private key. It only is similar in for textbook RSA, but otherwise that kind of comparison only hampers understanding of signature generation.


Collusions are not possible here since each user's private keys are randomized. As you can see in the Key Generation function, for each user a random value $r$ is generated and embedded into all his private keys. Therefore, if you try to use private keys from different users, you will not be using the same random $r$ during the decryption process, so it will fail.


Does AugPake not require key stretching?

It seems like there must be some form of rate limiting in order to
  slow down the search through such a limited set of possibilities.

There is. Due to the nature of AugPAKE an attacker can only try a single password per connection attempt with the server, meaning offline attacks against the handshake transcript are not possible. Thus if the connection-rate is limited, the search speed is limited accordingly as well, protecting even weak passwords, if something like 10 attempts per second and further penalties for bursts are implemented.

The fact that you can't guess anything from a passive view of the transcript is documented (and proven) in section 3.2.
Section 3.3 in turn talks about what active attacks can do and argues that even an active attacker can do no better than an on-line dictionary attack, which means one password attempt per connection.

  Could it improve security to use a key stretching algorithm such as
  pbkdf2/bcrypt/scrypt/argon2 on the password, or would that defeat the
  purpose/efficiency of the protocol?

It would certainly improve the security of the protocol to use a strong password-based key derivation function (PBKDF) in so far as it hardens the server's password database in the sense that a leak of the database isn't directly equal to "many, easy-to-break real-life password hashes". However this would also impose high loads on the clients of such a connection, which may be unfavourable, especially as there's no one-size-fits-all for password hashing given how different desktop computers and smartphones are, where the former needs maybe 100ms for something the latter needs 3s. This is very likely the reason why there's no such strong PBKDF in place here, as the designers decided that speed is more important than "security in case of database leaks".

This is also part of the security discussion of the document (section 3.5) which says that a protocol is secure against server compromise as long an attacker can do no better than running off-line dictionary attacks on the database.

  What prevents an attacker from brute forcing the weakest link in the
  chain?

The weakest link in the chain is the password database (which is secured using standard access control) or by the nature of the protocol, making guesses really slow and controllable.


No, your answers are incorrect by my reading of the description. The leftmost bit can't change, since only the other three bits are rotated. That does make for a pretty terrible s-box, but it's an exercise anyway...


Different literature padding for Merkle-Damgard

The customary (and secure) padding is the one you have been taught: at the end of the message add a single 1 bit, then just enough (possibly none) 0 bit(s) to reach the end of a block less the size devoted to the length (64-bit before the 512-bit limit for MD5, SHA-1, and SHA-256; 128-bit before the 1024-bit limit for SHA-512); then add the length (little-endian for MD5, big-endian for SHA-x).

The padding that you describe based on Hans Delf and Helmut Knebl is equally secure, but often uses one more block than the other.


Is HMAC-MD5 still secure for commitment or other common uses?

No, message commitment by disclosing its HMAC-MD5 with a key later revealed is no longer any secure, because of the ease with which MD5 collisions can now be found. There's however no compelling evidence that's insecure for messages constrained to belong in a small arbitrary set that no adversary can choose or influence. Still, whatever the constraints on the messages, the narrow 128-bit output width of HMAC-MD5 allows an attack with a relatively modest (and clearly feasible) $2^{65}$ evaluations of HMAC-MD5.

HMAC builds a PRF from a hash function $H$ with
Merkle-Damgård structure, message block width $w$ and output width $h$,
with $w\ge h$, as
$$\operatorname{HMAC}_H(K,m)=\begin{cases}
H\Big((K\oplus\text{opad})\mathbin\|H\big((K\oplus\text{ipad})\mathbin\|m\big)\Big) &\text{if $|K|\le w$}\\
\operatorname{HMAC}_H\big(H(K),m\big) &\text{if $|K|>w$}
\end{cases}$$
where $\text{opad}$ (resp. $\text{ipad}$) is the 0x5c5c5c… (resp. 0x363636…)
pattern with width $w$, and $\oplus$ is bitwise exclusive-OR with the
shortest operand right-padded using zero bits.

If the compression function used to build $H$ has suitable properties,
then for random unknown $K$ with $|K|\ge h$, the function $m\mapsto
\operatorname{HMAC}_H(K,m)$ is indistinguishable from random with
effort less than about $2^h$ evaluations of $H$. We have no compelling evidence that this does not hold for $H=\operatorname{MD5}$ (for which $h=128$, $w=512$). For more details see Mihir Bellare, New Proofs for NMAC and HMAC: Security without Collision Resistance, in Journal of Cryptology, 2015 (originally in proceedings of Crypto 2006).

When $H$ is MD5, or any $H$ that is not collision-resistant, the attack in the question renders insecure a commitment protocol where Alice

secretly chooses $m$ and $K$
computes and publishes $\operatorname{HMAC}_H(K,m)$ as a commitment of $m$
performs some action dependent on $m$ (like: offer a bet about the first bit of $m$)
later reveals $m$
reveals $K$, allowing a verifier to compute $\operatorname{HMAC}_H(K,m)$ on the $m$ Alice alleges, and compare against Alice's commitment.

Notice however that even with an ideal $H$, there's an attack with effort about $2^{h/2}$ evaluations of $H$, where Alice finds $m$ and $m'$ with $H\big((K\oplus\text{ipad})\mathbin\|m\big)=H\big((K\oplus\text{ipad})\mathbin\|m'\big)$; thus the mere output size of HMAC-MD5 limits its security level to a modest $2^{64}$ evaluations of MD5, in this protocol where $m$ is unconstrained.

On the other hand, I see no attack (much better than brute force on $K$) on the use of HMAC-MD5 (or HMAC with a non-collision-resistant $H$) in the variant of this protocol where Alice is constrained to choose $m$ in a small arbitrary set that no adversary can choose or influence, like $\{\text{“stone”},\text{“paper”},\text{“scissors”}\}$, as considered in the suggestion referenced in the question. Alice has so little choice on the messages that she must be clever in her choice of $K$, rather than $m$, in order to cause a collision. My intuition is that because $K$ enters twice in the computation of $\operatorname{HMAC}_H(K,m)$, with at least one execution of the compression function in-between (for heavily constrained $m$), finding a theoretical shortcut would be extremely hard, well beyond what the current cryptanalysis status of MD5 allows.


a) Is it safe to use K as a secret key? ("safe" meaning "as safe as using 32 random bytes"; it is assumed that K1, K2 and K are kept secret)

Although SHA-512 is not a KDF, and although it is required that the hash has properties that are not mandatory to be used as KDF, most people assume it is secure, yes.

  b) If an attacker gets his hands on K1 or K2 (but not on both), does he obtain any real advantage?

No, the attacker shouldn't gain advantage that way.

Kind of related is the security of KDF1 and KDF2. Hash should be considered a poor mans KDF. For a better KDF, use HKDF or just HKDF-expand.


Proving the possession of signature in zero-knowledge

Guillou and Quisquater (link) present a zero-knowledge proof of an RSA signature. Basically, the scheme is as follows:

Public knowledge: RSA modulus $n$, public RSA exponent $v$, preimage $X$.

Secret knowledge for prover: $A$, such that $A^v = X \mod n$.

$$
\begin{matrix}
\mathcal{P} & & \mathcal{V} \\
r \xleftarrow{\$} \mathbb{Z}_n^* \phantom{\mod n} & & \\
T \leftarrow r^v \mod n & & \\
 & \xrightarrow{\quad{}T\quad{}} & \\
 & & d \xleftarrow{\$} \{0,1,\ldots,v-1\} \\
 & \xleftarrow{d} & \\
 t \leftarrow A^dr \mod n & & \\
 & \xrightarrow{\quad{}t\quad} & \\
 & & t^v \stackrel{?}{=} X^{d}T \mod n
\end{matrix}
$$

In this diagram, $\leftarrow$ denotes assignment of a value to a variable and $\xleftarrow{\$}$ denotes uniformly random selection from a finite set.


Can multiple public keys lead to the same shared secret in X25519?

There are two independent sources of equivalent public keys for the X25519 function.

The first is rather simple: A public key is an integer u between $0$ and $2^{255}-1$ that represents an element of the finite field $\mathrm{GF}(2^{255}-19)$. Hence, for all $i\in\{0,\dots,18\}$, the integer $2^{255}-19+i$ represents the same field element as the integer $i$.

The second source of equivalence is a bit more specific.
In a nutshell, the X25519(k,u) function is defined as follows:

Clamp the secret key k, forcing bits $\{0,1,2,255\}$ to zero and bit $254$ to one.

In particular, note that this means the clamped scalar $k'$ is a multiple of $8$.
Compute the scalar product $[k']P$, where $P$ is a Curve25519 point with $x$‑coordinate u.
Return the $x$-coordinate of $[k']$P.

Now Curve25519 has cofactor $8$, hence there exist nonzero points $Q$ of order dividing $8$. For any such point, the public key $P+Q$ is equivalent to the public key $P$: Since $k'$ is a multiple of $8$, we have
$$ [k']Q = [k'/8][8]Q = [k'/8]\infty = \infty $$
and therefore (using the distributive law)
$$ [k'](P+Q) = [k']P + [k']Q = [k']P+\infty = [k']P \text. $$

For a concrete example, the two public keys

629fb7d4a50e0339edfdfae1464fedb848dd35f25c5fecd3d3f5af61654a691d
b53677c430779b050cd6db7e1f4ca6735e07b30a61711f45a88e710790af772a

will, for every secret key, give identical shared secrets using X25519.


Isn't a simple Vernam cipher as secure as known symmetric key algorithms?

The standard random number generator, in languages like Java or Python, does not generate real random numbers but pseudorandom numbers determined by an initial seed value.  If an attacker can somehow guess or determine this seed value, they can reconstruct the entire sequence of pseudorandom outputs.

Furthermore, the default pseudorandom number generators in most languages are not cryptographically secure.  In particular:

The set of possible seeds is typically rather small; for example, the seed may be a 32-bit integer, meaning that an attacker only needs to test 232 different seeds to find the correct one.  On a modern computer, this can often be done in a few seconds.
Worse yet, the initial seed is often chosen based on some fairly easily guessable value, such as the system time.  If such a seed is used, and if you know roughly when a key was generated, you can narrow down the range of likely seed values significantly.
Even if the seed is chosen securely (i.e. completely unpredictably) from a set large enough to resists brute force guessing, the algorithms used to generate the pseudorandom outputs from the seed are typically not designed to withstand cryptanalytic attacks.  Thus, for many commonly used algorithms, the seed can be fairly efficiently reconstructed from the outputs.

The first two attacks above only require that the attacker has access to some ciphertext, and can try to decrypt it with keys based on different seeds and see for which seed the resulting decrypted data makes sense.  The last attack generally requires a bit more, namely that the attacker must know at least part of the keystream — but if the attacker has the ciphertext and can guess part of the plaintext, they can easily obtain the corresponding parts of the keystream.

Of course, if you created your key based on a pseudorandom number generator that did not have any of these weaknesses, then the scheme you describe would be secure.  Indeed, that is pretty much exactly what a synchronous stream cipher is.


Could this "symmetric RSA" scheme provide key compromise resistant communications?

Yes, this seems to make sense and it is a plausible solution. The KEM approach does not work, unless you use some tricks, like including a hash of the message in the KEM. (That could work, of course.)

Security goal

The type of scheme we are looking at consists of three algorithms $(K,E,D)$. The key generation algorithm $K$ outputs two keys, say $k_0$ and $k_1$. The encryption algorithm $E$ takes as input a key and a message and outputs a ciphertext. The decryption algorithm $D$ takes as input a key and a ciphertext and outputs a message or $\bot$.

We require that for any $(k_0, k_1)$ output by $K$ and any message $m$, $$D(k_{1-\beta}, E(k_\beta, m)) = m \text.$$

There are two goals here, confidentiality and integrity. You want messages encrypted with $k_\beta$ to be confidential to everyone who does not have $k_{1-\beta}$. And someone who does not have $k_\beta$ (but may have $k_{1-\beta})$ should not be able to create ciphertexts that look as if they were created with $k_{\beta}$.

Confidentiality

In the confidentiality game, the simulator generates a key pair $(k_0, k_1)$ and gives $k_1$ to the adversary. The adversary chooses two messages $m_0$ and $m_1$. The simulator flips a coin $b$ and creates a ciphertext $c^*$ as $E(k_1, m_b)$. The simulator sends $c^*$ to the adversary, and the adversary eventually sends $b'$ to the simulator. During the entire process, the adversary is allowed to send messages or ciphertexts to the simulator, and the simulator responds with the result of $E(k_0, m)$ or $D(k_0, c)$, respectively.

The adversary wins if $b=b'$. He should not win significantly more (or less) often than half the time.

Integrity

In the integrity game, the simulator generates a key pair $(k_0, k_1)$ and gives $k_1$ to the adversary. The adversary is allowed to send ciphertexts and messages to the simulator, and the simulator responds with the result of $E(k_0, m)$ or $D(k_0, c)$, respectively. Finally, the adversary sends a ciphertext $c^*$ to the simulator and the simulator decrypts it using $k_1$.

The adversary wins if the $c^*$ decrypts correctly and it was not created by the simulator. The adversary's success rate should be negligible.

Analysis Proposal

I would try something like OAEP+, but for simplicity, I would "personalize" the hash functions so that we can use different random oracles for the two senders. The confidentiality game looks a lot like the usual RSA-OAEP+ game, but you need to create ciphertexts for the recipient. This becomes much easier when you use separate random oracles.

I suspect it will work out. It may even be possible to "reduce" the security to that of ordinary RSA-OAEP+.


Why is the definition of Special-honest verifier zero-knowledge probabilistic?

The probabilistic nature is not specific to special-honest verifier zero-knowledge but that's what zero-knowledge is about. With zero-knowledge you want to formulate that such an interactive proof does not leak any
information besides the validity of the claim, as it is efficiently simulatable meaning that real and simulated transcripts are not distinguishable.

That a simulator produces accepting transcripts does not necessarily mean that this simulated transcript cannot be distinguished from a real interaction. Assume for instance an artificial simulator that always uses the same $a$ independent of the value $e$. So the transcript could be an accepting one, but one could distinguish transcripts coming from real interactions and simulated ones.


Generate RSA-2048 private key for a VERY fast decryption (don't care if it will be unsecure)


Do any Identity-based Encryption Systems support messaging between domains?

I've now spoken with representatives from two IBE vendors. The Voltage system allows "federation" by which one Voltage appliance can exchange system parameters with another Voltage appliance. It's not clear if this is done using RFC 5091, RFC 5408 and RFC 5409. The other vendor does not support such a mode of operation.


Probably, yes, just testing the first message is secure.

However, I've seen implicit authentication before in a protocol, and it is not nice to deal with it. Basically, you handle the handshake and report to the user of a library that the handshake has finished and the symmetric session keys have been generated: everything is ready to actually transport data.

If you remove the finished message from the handshake then you don't know that everything is alright. You now have to send or receive the message without knowing it should be OK. Now if you have an error then what are you going to answer to the client? Is it that the channel has become corrupted or that the handshake failed?

In this sense, an explicit verification that the handshake failed is much easier to deal with. After the handshake is verified you can simply notify that the channel has become corrupted if anything happens to it.

So yes, implicit authentication and verification of the handshake is possible. In practice, you really want to implement explicit authentication.

An odd situation is where you would send a byte valued 00 or 01 if a condition is true and nothing if a condition is false. In the false case no data record needs to be send: but that means that the handshake is never verified!


Where is my private key stored when I communicate to a website that uses SSL/TLS?

SSL does not generate a private key. What is generated is shared secret key between the client and server.This shared secret key is only valid till the session lasts. So, this shared secret key resides in the RAM. It is not saved in to the hard disk.


Hash function based on pseudorandom functions and security

Note that a PRP is a PRF for a large enough block size. Hash functions based on block ciphers will probably be of interest to you.

There are some general schemes for using block ciphers to build hash functions. You may want to investigate them and what requirements they have for the underlying block cipher. Unfortunately, the PRP model is a weak requirement for a block cipher, schemes that use block ciphers often use stronger assumptions (like the MDC-2 hash is built on block ciphers by using the Ideal Cipher model).

For a modern example, the popular SHA-3 hash contestant Skein is based on the block cipher Threefish. You could investigate if/what PRF or PRP models are used in the analysis of Skein and Threefish.


Is HTTPS secure if someone snoops the initial handshake?

The SSL and TLS protocols (on which HTTPS is based) are designed in a way that no attacker (neither a passive nor an active one) can read anything of the encrypted part (if the cryptographic assumptions hold - and if you don't use the NONE cipher, which does no encryption).

Of course, the attacker can read the negotiation part. But this part will not contain anything which is (with current known algorithms) usable for cryptanalysis of the rest.

There are several possible algorithms to negotiate a secret session key - which one is chosen depends on which protocol suites (= set of algorithms to use) the client offers and what the server selects from these. Then we use the exchanged key to encrypt the rest of the connection using a symmetric algorithm.

Some popular key exchange mechanisms are these:

Diffie-Hellman key exchange (DHE): Here both sides select random numbers a and b, calculate and exchange $g^b$ or $g^a$, and then both calculate $(g^b)^a = (g^a)^b$, which is the same value. An attacker does not see $a$ or $b$, only $g^a$ and $g^b$, and can't derive from this the values. (All these calculations are done in some group, the multiplicative group modulo a big prime number for "normal" Diffie-Hellman, or in an elliptic curve group for ECDHE.)

In the usual case of authenticated key exchange, afterwards the server signs some hash of all the negotiation data with his private key, which the client can then check using the public key. (This avoids active man-in-the-middle attacks, where the attacker negotiates one key with the server and another one with the client, then forwarding the data.) For anonymous connections there is no such step (and MITM is possible).
asymmetric encryption based (RSA key exchange): The client generates a random pre-master-secret, encrypts it using the public key of the server, and sends this to the server. The server can decrypt it an now both know the same pre-master secret.  Applying a hash on this gives the master secret used for actual encryption (and the MAC).

The problem is that a leak of the private key here compromises all past connections (where this key was used and which where registered), while with Diffie-Hellman only future connections are affected (where the attacker can launch a MITM-attack).

These are less often used, since they are not suitable for parties which have no previous consent of common data:

password based, for example the Secure Remote Password protocol: This works similar to Diffie-Hellman (i.e. it uses exponentiation in a prime group - but addition and multiplication, too.). The server has a password verifier $v, s$ (with $s$ once selected random, and $v = g^{\operatorname{H}(s,p)}$), the client has the password $p$.

To authenticate (and exchange a key), the client sends the user name and $A = g^a$ (where $a$ is random data), the server sends back $s$ and $B = k\cdot v + g^b$ (with $b$ random and $k$ some fixed parameter). Both calculate then $u = \operatorname{H}(A,B)$. Then the client calculates $S = (B - k\cdot g^{\operatorname{H}(s,p)})^{a+u\cdot x}$, while the server calculates $S = (A\cdot v^u)^b$. If the password is right, these are identical. To obtain the key itself, both calculate $K = \operatorname{H}(S)$.
Pre-shared key, as defined in RFC 4279: This is a bunch of algorithms based on some pre-shared secret key common between both parties. (Obviously this is of no use in the anonymous internet.)

The PSK method simply transfers some key identifier (which is not nearer specified - it will depend on the application, i.e. higher level protocol which is using this), and both then derive the master session key from this shared secret.

The DHE_PSK uses a Diffie-Hellman key exchange as described above, and this key is then hashed together with the pre-shared key to form the master session key.

For RSA_PSK the client sends an RSA-encrypted random data, together with the key ID - the pre-master secret is then formed from the decrypted random data, together with the pre-shared key.


In a hybrid cryptosystem is safe to send the encrypted key together with the encrypted message?

Yes it is safe.
Assuming you get everything else right(Proper encryption mode), proper padding, secure random key, proper key management and avoid problematic other usages of same key, etc...
You have to provide the encrypted key to the legitimate user, if you have two different transfer systems with independent weaknesses you could transfer separately but that is probably rare and RSA applied properly (e.g OAEP) is sufficient so the encrypted key will reveal nothing about the key to that without the RSA private key.


TL;DR: You want to use Argon2d here.

Even though Argon2 was standardized only somewhat recently, it is the result of the Password-Hashing Competition (2013-2015) and was a late re-design of Argon which also picked up ideas from a few other finalists. Since then there have been attacks on it, which caused the scheme to be tweaked to counter them better, this is why we have Argon2 v1.3 as the most current version, you may want to note that most of these attacks mostly weakened Argon2i and not Argon2d.

Now during the competition results came up that your defense against time-memory trade-off attacks will suffer if you make sure that your scheme is immune to the various kinds of side-channel attacks that people have come up with (which also includes more "crazy" stuff like leaked intermediate state). Because of this, it was decided that there should be two versions: Argon2i and Argon2d. One offering the best possible protection while trying its best to be immune against side-channel attacks (by using data- and password-independent memory access patterns) and the other dropping these requirements and all-out optimizing against such attacks (by using data- and possibly password-dependent memory access patterns).

Enough with the history now. Argon2d offers better protection than Argon2i at the expense of being more vulnerable to side-channel attacks. Now you have to ask yourself: Do these apply? No, not really. You said that you are on Android, which is not exactly known for high platform security, so if you have an attacker in such a privileged position to execute something like cache-timing attacks or similar attacks that try to exploit memory access patterns, your user has already much bigger problems anyways.
It's a similar logic as with AES: There are cache-based side-channel attacks, but these have never been observed in the wild, probably because other options are much easier, more relieable and equally as effective.
So the conclusion is: You want to use Argon2d.

So for whom is Argon2i? People who need to run applications on shared hardware or where timing attacks are a real thread. For example if you run a webserver in a public cloud on shared hardware. Then you have to be worried about who else is on the same CPU. And with webservers it's also easier to measure the timing of reactions and trying to deduce information from that.

The final hint that Argon2d is the way to go here, is the fact that KeePass (one of the open-source password managers) also has decided for Argon2d.


Yao's Millionaires' Problem without knowledge of plaintext

What you are asking for is impossible, because it would immediately break the cryptosystem.

Let's assume for a moment, that such a function exists and we know how it works. And we get a challenge ciphertext $c = enc(x)$. We know the public key, because it's public. And if we assume the set of messages to be $0,1,\dots,1000$, we then just encrypt $500$ and then apply the function to get $x \geq 500$. If it is true, we apply the algorithm to $c$ and $enc(750)$ and otherwise to $c$ and $enc(250)$. This is just a binary search, and this way we can efficiently find out what $x$ is - without knowing the decryption key. And that would mean, there is no security at all.


although it feels like base64, i see that each truncated line has at most 64 characters

It is base64 encoded. Remove the -----BEGIN OPENSSH PRIVATE KEY----- and -----END OPENSSH PRIVATE KEY----- and the new lines ("\n") and then you can parse as per
https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/usr.bin/ssh/PROTOCOL.key?annotate=HEAD . Quoting that file:

This document describes the private key format for OpenSSH.

1. Overall format

The key consists of a header, a list of public keys, and
an encrypted list of matching private keys.

#define AUTH_MAGIC      "openssh-key-v1"

    byte[]  AUTH_MAGIC
    string  ciphername
    string  kdfname
    string  kdfoptions
    int number of keys N
    string  publickey1
    string  publickey2
    ...
    string  publickeyN
    string  encrypted, padded list of private keys

2. KDF options for kdfname "bcrypt"

The options:

    string salt
    uint32 rounds

are concatenated and represented as a string.

3. Unencrypted list of N private keys

The list of privatekey/comment pairs is padded with the
bytes 1, 2, 3, ... until the total length is a multiple
of the cipher block size.

    uint32  checkint
    uint32  checkint
    string  privatekey1
    string  comment1
    string  privatekey2
    string  comment2
    ...
    string  privatekeyN
    string  commentN
    char    1
    char    2
    char    3
    ...
    char    padlen % 255

Before the key is encrypted, a random integer is assigned
to both checkint fields so successful decryption can be
quickly checked by verifying that both checkint fields
hold the same value.

4. Encryption

The KDF is used to derive a key, IV (and other values required by
the cipher) from the passphrase. These values are then used to
encrypt the unencrypted list of private keys.

5. No encryption

For unencrypted keys the cipher "none" and the KDF "none"
are used with empty passphrases. The options if the KDF "none"
are the empty string.


Random semantic security and bijective PRGs

There are a few fundamental problems with your approach:

When you use the construction $m \mapsto E(k,G(m))$ in the context of the standard CPA game, you are feeding adversarially chosen values into the PRG $G$. PRG security does not guarantee anything about PRG outputs in this setting. PRG security can only be applied when the PRG input is uniformly chosen, and used nowhere else in the system (in particular, it can't be known to / chosen by the adversary).
As you mention, decryption requires $G$ to have an efficiently computable inverse, which is incompatible with PRG security. The alternative is that $G$ has no stretch, which basically defeats the purpose of a PRG. If you relax the stretch requirement of a PRG, then even the identity function is a secure PRG in the sense of its outputs looking random. Clearly when you use the identity function in your construction, you haven't actually done anything to $\mathcal{E}$.

  Is there a different approach to building $\mathcal E′$ that gets around this potential security flaw?

Yes, but I don't know how to give a reasonable hint without trivializing the problem. You don't need to introduce any additional crypto primitives beyond the original scheme $\mathcal{E}$.


Cocks IBE Scheme: why is -a a quadratic residue mod n?

If $a$ is a nonresidue mod $p$, then since $-1$ is also a nonresidue mod $p$ by construction, $-a$ is a residue mod $p$. And likewise mod $q$, so $-a$ is a residue mod $pq$.


Is it enough to encrypt then sign when using symmetric-key encryption?

Well, it would depend somewhat on what your security goals are, but signing the message would enable the receiver to verify integrity: that the ciphertext that it got is precisely the ciphertext that the sender sent (at some point; you still may need to worry about replay).

However, you're assuming that you have a shared symmetric key to encrypt; is there a specific reason you don't use that to also perform integrity (either by using a combined mode operation, such as AES-GCM, or generating a Message Authentication Code using other key bits that you shared).  The one thing that using a signature buys you is the ability to prove to a third party that the message is authentic (and not something the receiver made up); is that important to you?


What is TPMFail attack and what are the countermeasures?

In short, TPMFail attack is black-box timing analysis of TPM 2.0 devices deployed on computers. The TPMfail team is able to extract the private authentication key of TPMS's 256-bit private keys for ECDSA and ECSchnorr signatures, even over networks. This attack successful since there was secret dependent execution in TPMs that causes the timing attacks. To mitigate this attack, a firmware update needed for Intel fTPM and hardware replacement for STMicroelectronics TPM is needed.

  How do the attacks work?

The attack is performed in three phases

Phase 1: The attacker generates signature pairs and timing information to profile of the given implementation fTPM or STM's. This is the pre-attack stage and the attackers know the secret keys and used nonces. This profile can be measured of-site. After the measurement, they have complete correlation information about the timing and secret nonce $k$ used in signatures. The bias is related to Leading Zero Bits (LZB).
Phase 2 With the timing on their hand the attackers target a system with the same TPM devices and collect signature pairs and timing information.
Phase 3 The attacker applies lattice-based cryptanalysis with filtered signatures to get biased nonces to recover the private key.

In more Details

The timing measurement Normally Intel fTPMs Linux kernel driver uses command response buffer in push mode. The driver checks the status after 20 milliseconds, if the calculation is not ready, the driver re-checks. It doubles the time for every check. This driver doesn't allow a perfect timing measurement, therefore, the TPMfail team developed their kernel driver to perfectly measure the timing. They collected 40000 ECDSA signature. They similarly build a driver for STM's hardware TPM.
Timing Analysis: They discovered that a bit-by-bit scalar point multiplication implementation that skips the computation for the most significant zero bits of the nonce. Therefore nonces with more leading zero bits are computed faster in TPMs.

On the below figure it is Intel fTPM's timing histogram. On the right a nonce depended software implementation. Comparing the figures leads to the information that Intel used a 4-bit fixed window during Fixed Window Scalar Multiplication.

In the left figure, there are 4 regions, the fastest one has nonces with 12 most significant windows are zero, next has 8, next has 4, and the slowest region has none.

The Lattice-based Cryptoanalysis

They used The Hidden Number problem lattice attacks. They used BKZ algorithm over the Sage. This attack recovers ECDSA nonces and private keys as long as the nonces are short. Since nonces are selected randomly half of them have zero in MSB, a quarter of them have two zeroes in MSB, etc. The side-channel will help to select the shorter nonces to apply the lattice-based attack.

The key recovery with attack models

System adversary a user with administrator privileges to extract the keys. The required signature for 12, 8, and 4 leading zeros for ECDSA

\begin{array}{|c|c|c|c|}\hline
\text{bias} & \text{need signatures} & \text{total sign operations} & \text{succes rate}  \\\hline
4-bit & 78 & 1248 & 92\text{%}\\ \hline
8-bit & 34 & 8748 & 100\text{%}\\ \hline
12-bit & 23 & & 100\text{%} \\ \hline
\end{array}

The time for collecting signatures on i7-7700 is 385 signature/minute. Collecting the 8784 signatures took less than 23 minutes. Once the data is collected the Lattice attack took 2 to 3 seconds! for dimension 30.

For Intel fTPM Schnorr signatures in 27 minutes 10,204 signature are collected with 8-bit leading zeroes. For 4-bit case 65 samples found from 1.040 signature in 1,5 minutes.

STMicroelectronics TPM ECDSA Key Recovery

They were able to recover the ECDSA key after 40,000 signature for 8-bit with 35 fastest signatures.
User level as before mentioned, in user-level the kernel driver checks the result, first in 20 micro seconds. This lead the below timing measure;

They collected 219,000 signatures that contain noisy 855 8-bit leading zeros. With filtering, they get 53 high-quality signatures with 100% recovery rate. They also look for the 4-bit case.
Remote adversary This is the weakest adversary in terms of capability. They set up a fast 1G network and requested 40,000 signatures to collect timing information. Although the timing histogram noisier, it still shows information about nonces with 4 and 8-bit leading zeroes. For the 4-bit case; 1,248 signatures are collected in less than 4 minutes and for the 8-bit case; the required signature is collected in 31 minutes.

They used this remote attack against StrongSwang, an open-source IPsec VPN implementation that is supported by modern OSes, including Linux and Microsoft Windows.

  What are the countermeasures.

countermeasures

The kernel driver can increase the delay time so that this doesn't leak information. However, this may require different levels with different TPM devices. Therefore this is no bulletproof.
Constant time implementation. This is the key to the attack point. With data depending calculation the TPMfail team is able to distinguish the calculations. Once calculations are done in constant time, the side channel will be harder. They have testest the patches and couldn't execute the attack anymore.
Using double size nonce and setting the high bit to 1 *

Patches

CVE-2019-11090. Intel issued a firmware update for Intel Management Engine (ME) including patches to address this issue on November 12, 2019.
CVE-2019-16863. STMicroelectronics updated version of their TPM product for verification and sent to authors. They tested and see that it is resistant. Since it is hardware it requires replacement.

Note: From authors:

  TPMs have previously suffered from vulnerabilities due to weak key generation. However, It is widely believed that the execution of cryptographic algorithms is secure even against system adversaries.

*Thanks to commentors. See :Why EdDSA held up better than ECDSA against Minerva. Minerva is also a smilar work on smart cards.


Can we use higher strength SHA along with lower strength RSA key in SSL?

In general, no, there is no security problem with using overkill that fits in your budget.

Maybe there are constraints in your application or protocol that would prevent you from using SHA-512 with 2048-bit RSA moduli, but we can't say without more details about your application or protocol.


Well, lets try to take a concrete example:

Suppose that you have a 142 bit message that you need to encrypt with CTR mode.  What do you do?

Well, you generate the first 128 bit block with AES; you take the first 128 bits of the message, exclusive-or the two, and that's the first 128 bits of the ciphertext.

Then what?  Well, you have 142-128=14 bits of plaintext left.  So, what you do is generate the second 128 bit block with AES; you then take the first 14 bits of that, exclusive-or that with the 14 bits of plaintext, and that gives you the last 14 bits of the ciphertext.  And, what do you do with the remaining 128-14=114 bits of AES output?  Well, you discard it -- you don't need it.

If the decryptor does precisely the same logic, he will transform the 142 bit ciphertext into the original 142 bit plaintext.

Does this make things clearer?


Can a PRNG with a fixed amount of entropy always be detected?

No, there is no reliable way to detect such shenanigans (through external testing), if the adversary is sufficiently sophisticated and has the power to embed backdoors in the hardware you are using.

If the PRNG is specified to be a deterministic algorithm, then in principle one can run the PRNG on a known key and compare its output against the output from an independent implementation.  NIST calls such a PRNG a "deterministic random bit generation" (DRBG) algorithm.  In effect, you can use black-box testing of it to check that it seems to be working correctly, under testing conditions.

However, there are some major shortcomings in this testing-based methodology for checking the PRNG implementation.  Just because the hardware works correctly under test conditions doesn't necessarily mean it will work correctly when you need it to.

One problem is that there's no way to verify that the hardware is actually deterministic.  For instance, the hardware might behave correctly almost all of the time, except that under certain special environmental conditions, it behaves incorrectly.  Those special environmental conditions might be arbitrarily hard to find during testing: e.g., the backdoor might be activated immediately after receipt of a network packet containing a magic 128-bit value (or some other "secret knock").  There's basically no good way to detect this kind of backdoor with black-box testing.  Therefore, in practice, if you're concerned about backdoors in the hardware, you're not gonna be able to verify that the hardware PRNG is secure merely through external testing.

This problem is not limited to PRNGs; this problem is universal.  This is true of all the hardware you use for computation.  If your CPU has a backdoor, you're hosed -- period.  There's no good way to verify that your CPU is free of backdoors, through external methods.  That's life.


Inner product with homomorphic encryption

You can use these schemes instead:

“Evaluating 2-DNF Formulas on Ciphertexts”, or
“A Simple BGN-type Cryptosystem from LWE”.

These schemes enable you to do addition, a single multiplication, and more additions. For inner product, that's all you need (encrypt each item separately, multiply pairs, and add all together).

Not everything needs FHE. In any case, somewhat HE would suffice since it's just a single multiplication.


What may be causing conflicts in Whirlpool implementation versions?

There is no difference.

The wiki page you referred to contains examples of hashes for all three versions of Whirlpool. For string "The quick brown fox jumps over the lazy dog", the current version should produce the following hash:

    B97DE512E91E3828B40D2B0FDCE9CEB3C4A71F9BEA8D88E75C4FA854DF36725F
    D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35

Let's create a file containing this string and test different implementations.

    $ openssl dgst -whirlpool quick.txt
    whirlpool(quick.txt)= b97de512e91e3828b40d2b0fdce9ceb3c4a71f9bea8d88e75c4fa854df36725fd2b52eb6544edcacd6f8beddfea403cb55ae31f03ad62a5ef54e42ee82c3fb35

    $ rhash -W quick.txt
    b97de512e91e3828b40d2b0fdce9ceb3c4a71f9bea8d88e75c4fa854df36725fd2b52eb6544edcacd6f8beddfea403cb55ae31f03ad62a5ef54e42ee82c3fb35  quick.txt

Both match the hash from the wiki.
Let's test the python implementation using this script:

    import whirlpool

    wp = whirlpool.new("The quick brown fox jumps over the lazy dog")
    hashed_string = wp.hexdigest()

    print(hashed_string)

The output is:

    b97de512e91e3828b40d2b0fdce9ceb3c4a71f9bea8d88e75c4fa854df36725fd2b52eb6544edcacd6f8beddfea403cb55ae31f03ad62a5ef54e42ee82c3fb35

Let's test the reference code from the Whirlpool home page by inserting the following lines at the end of makeISOTestVectors() function:

    const char* quick = "The quick brown fox jumps over the lazy dog";
    NESSIEinit(&w);
    NESSIEadd(quick, 8*strlen(quick), &w);
    NESSIEfinalize(&w, digest);
    printf("The hash-code is the following 512-bit string.\n\n");
    display(digest, DIGESTBYTES); printf("\n\n");
    fflush(stdout);

The output is:

    B97DE512E91E3828 B40D2B0FDCE9CEB3 C4A71F9BEA8D88E7 5C4FA854DF36725F
    D2B52EB6544EDCAC D6F8BEDDFEA403CB 55AE31F03AD62A5E F54E42EE82C3FB35

All implementations produce the same hash. Where did you found a mismatching version?


Correlate HMAC key and MAC without message

If I have a HMAC_SHA1 signature and a potential key, can I check whether this key could have produced this signature without knowing any of the message body plaintext?

No, there is no known efficient way.

Now, if you look at how HMAC works internally, then there will be (with high likelihood) will be values that cannot be produced by a specific key; that is, values which cannot be achieved by any message $M$.  This happens because the inner SHA-1 hash summarizes the message $M$ into a 160 bit value (in a key dependent operation); then it performs another key dependent operation t(the outer hash) to convert it into another 160 bit value.  This transform is unlikely to be invertible, and hence there are likely 160 bit outputs that cannot happen.

However, even though those impossible values almost certainly exist, we have no way of finding what these values might be, or whether if any specific output is one of those.

Also, a minor terminology note:

  If I have a HMAC_SHA1 signature…

In crypto, we tend to use the term 'signature' to refer to a public key signature operation (which HMAC is not).  Instead, we might call it an HMAC_SHA1 MAC (Message Authentication Code)


Relevance of Input and Ouput size of PRF on CTR mode

My solution

I think I've found a solution, there was a lack of comments/answers so I will post it as an answer in order to conclude this.

I'll begin with part (b).

Cycles in the counter must be avoided, that is, it must be ensured that ${\tt ctr}, {\tt ctr}+1,{\tt ctr}+2,\ldots$ never reaches ${\tt ctr}$ again. Notice that ${\tt ctr}\in \{0,1\}^{\ell_{\text{in}}(n)}$, so it must be ensured that the maximum block length $\ell(n)$ does not exceed $2^{\ell_{\text{in}}(n)}$. That's a constraint between ${\ell(n)}$ and ${\ell_{\text{in}}(n)}$. $\ ^{1}$

On the other hand, in the proof of the CPA-security of CTR mode the "birthday" term $2q(n)^2/2^n$ appears bounding the probability of a successful attack compared to guessing, where $q(n)$ is the maximum number of blocks (so $q(n) = {\ell(n)}/{\ell_{\text{out}}(n)}$).
This term must be negligible, and that is the restriction between ${\ell(n)}$ and ${\ell_{\text{out}}(n)}$.

Regarding part (a), I claim that there is not any constraint between $\ell_{\text{in}}$ and $\ell_{\text{out}}$ as long as $\ell(n)$ satisfies the conditions mentioned above. This can be seen by revisiting the proof and checking that it holds independently of the polynomials $\ell_{\text{in}}$ and $\ell_{\text{out}}$ (so yes, the ratio $\ell_{\text{in}}/\ell_{\text{out}}$ can be anything).

$^{1}$This is assumed in the proof of CPA-security on Katz' book when they say: the values $f({\tt ctr}^∗ + 1),\ldots,f({\tt ctr}^* + \ell^*)$ used when encrypting the challenge ciphertext are uniformly distributed and independent of the rest of the experiment