How to detect if a protocol is vulnerable to a replay attack trying to impersonate?

In a pure replay attack, Eve acts as a genuine participant to the protocol with respect to the other. Therefore, having passively eavesdropped the protocol:
$$\begin{array}{lclcll}
\mathsf A&\to&\mathsf B&:&\mathtt{Hello}&\ \ \mathsf{[1]}\\
\mathsf B&\to&\mathsf A&:&B,K_{ab}\{B\}&\ \ \mathsf{[2]}\\
\mathsf A&\to&\mathsf B&:&A,K_{ab}\{A\}&\ \ \mathsf{[3]}\\
\end{array}$$
Eve impersonating Alice to Bob can be:
$$\begin{array}{lclcll}
\mathsf E(\mathsf A)&\to&\mathsf B&:&\mathtt{Hello}&\ \ \mathsf{[1a]}\\
\mathsf B&\to&\mathsf E(\mathsf A)&:&B,K_{ab}\{B\}&\ \ \mathsf{[2a]}\\
\mathsf E(\mathsf A)&\to&\mathsf B&:&A,K_{ab}\{A\}&\ \ \mathsf{[3a]}\\
\end{array}$$
where at $\mathsf{[3a]}$ Eve simply replays the value she captured from $\mathsf{[3]}$, and thus passes the implicit test by Bob at step $\mathsf{[3a]}$ that the received $K_{ab}\{A\}$ in the second part of the message deciphers to the $A$ in the first part, that Bob (wrongly) assumes is the identity of the other party.

And Eve impersonating Bob to Alice can be:
$$\begin{array}{lclcll}
\mathsf A&\to&\mathsf E(\mathsf B)&:&\mathtt{Hello}&\ \ \mathsf{[1b]}\\
\mathsf E(\mathsf B)&\to&\mathsf A&:&B,K_{ab}\{B\}&\ \ \mathsf{[2b]}\\
\mathsf A&\to&\mathsf E(\mathsf B)&:&A,K_{ab}\{A\}&\ \ \mathsf{[3b]}\\
\end{array}$$
where at $\mathsf{[2b]}$ Eve simply replays the value she captured from $\mathsf{[2]}$, and thus passes the implicit test by Alice at step $\mathsf{[2b]}$ that the received $K_{ab}\{B\}$ in the second part of the message deciphers to the $B$ in the first part, that Alice (wrongly) assumes is the identity of the other party.

This does not involve finding key $K_{ab}$ from plaintext $B$ and ciphertext $K_{ab}\{B\}$, which would be breaking the cipher, something assumed impossible in a replay attack.

One way to prevent pure replay attack is to make use of nonce, so that just replayed messages won't be accepted. That's the case in this protocol (the question's second one without $K_{ab}\{N_a,N_b\}$ in the last step)
$$\begin{array}{lclcll}
\mathsf A&\to&\mathsf B&:&A,K_{ab}\{N_a\}&\ \ \mathsf{[1]}\\
\mathsf B&\to&\mathsf A&:&B,N_a,K_{ab}\{N_b\}&\ \ \mathsf{[2]}\\
\mathsf A&\to&\mathsf B&:&A,B,N_a,N_b&\ \ \mathsf{[3]}\\
\end{array}$$

Alice choses a nonce $N_a$, sends it enciphered as $K_{ab}\{N_a\}$ as part of $\mathsf{[1]}$, that Bob extracts, deciphers yielding $N_a$ that he sends as part of $\mathsf{[2]}$, allowing Alice to extract and check it against the nonce she has chosen; this proves to Alice that some entity able to use $K_{ab}$ was involved in the exchange; and if Alice can rule out that this entity is herself (say, by not running more than one instance of the protocol at a given time), then that involved entity must be Bob (because there is no other entity sharing $K_{ab}$ and it is used only as the key of a cipher), thus the protocol is immune to impersonation of Bob to Alice running the protocol with Alice's role.

Also, Bob chose $N_b$ in $\mathsf{[2]}$, sends it enciphered as $K_{ab}\{N_n\}$ as part of $\mathsf{[2]}$, that Alice extracts, deciphers yielding $N_b$ that she sends as part of $\mathsf{[3]}$, allowing Bob to extract and check it against the nonce he has chosen; this proves to Bob that some entity able to use $K_{ab}$ was involved in the exchange; and if Bob can rule out that this entity is himself, then that must be Alice, thus the protocol is immune to impersonation of Alice to Bob running the protocol with Bob's role.

Notice that when Bob is a server allowing multiple concurrent connections, Eve can impersonate Alice to Bob. An attack goes as follows:
$$\begin{array}{lclcll}
\mathsf E(\mathsf A)&\to&\mathsf B&:&A,K_{ab}\{N_a\}&\ \ \mathsf{[1a]}\\
\mathsf B&\to&\mathsf E(\mathsf A)&:&B,N_a,K_{ab}\{N_b\}&\ \ \mathsf{[2a]}\\
\mathsf E(\mathsf A)&\to&\mathsf B&:&A,K_{ab}\{N_b\}&\ \ \mathsf{[1a']}\\
\mathsf B&\to&\mathsf E(\mathsf A)&:&B,N_b,K_{ab}\{N'_b\}&\ \ \mathsf{[2a']}\\
\mathsf E(\mathsf A)&\to&\mathsf B&:&A,B,N_a,N_b&\ \ \mathsf{[3a]}\\
\end{array}$$
where

In $\mathsf{[1a]}$, Eve gives any plausible $K_{ab}\{N_a\}$ even though she does not actually know the matching $\{N_a\}$; that can for example be an $\{N_a\}$ captured from a previous session, or (for many ciphers) any random bit string of the same size).
In $\mathsf{[2a]}$, Bob just does its job; Eve does not make the check Alice would have made about $N_a$.
In $\mathsf{[1a']}$, Eve mimics starting another simultaneous connection attempt, but sneakingly supplies $K_{ab}\{N_b\}$ of $\mathsf{[2a]}$ where the convention would be to supply $K_{ab}\{N'_a\}$
In $\mathsf{[2a']}$, Bob just does its job, and correspondingly returns $N_b$ that he has chosen and sent enciphered in $\mathsf{[2a]}$; again Eve makes no check.
In $\mathsf{[3a]}$, Eve uses the $N_b$ conveniently supplied by Bob in step $\mathsf{[2a']}$, and the check Bob makes of that $N_b$ passes.

The above proves the protocol is vulnerable, by exhibiting an explicit attack. Whether it is a replay attack is a matter of taste. Assuming yes: the question asks how this is detected. An answer is: because $\mathsf{[1]}$ and $\mathsf{[2]}$ can be abused to make Bob a decryption oracle under key $K_{ab}$ (that is, something that allows decryption of any message), and in the protocol considered in this section of the answer, the ability to decipher a message is what authenticates Alice to Bob.

As an attempt to prevent the above attack (likely: made for pedagogical reasons), the question's protocol
$$\begin{array}{lclcll}
\mathsf A&\to&\mathsf B&:&A,K_{ab}\{N_a\}&\ \ \mathsf{[1]}\\
\mathsf B&\to&\mathsf A&:&B,N_a,K_{ab}\{N_b\}&\ \ \mathsf{[2]}\\
\mathsf A&\to&\mathsf B&:&A,B,N_a,N_b,K_{ab}\{N_a,N_b\}&\ \ \mathsf{[3]}\\
\end{array}$$
has as a step $\mathsf{[3]}$ such that Alice forms $N_a,N_b$ and encipher it into $K_{ab}\{N_a,N_b\}$, that Bob deciphers and checks against $N_a$ he deduced from $K_{ab}\{N_a\}$ received as part of step $\mathsf{[1]}$, and against $N_b$ he has chosen. That's not a good idea: since Alice makes no extra check, and makes an extra use of $K_{ab}$, it can only make her more vulnerable to impersonation of Bob. And the protocol remains vulnerable to impersonation of Alice to Bob. Proving this is left as an exercise to the reader, but the following might help detect that:

It is not forbidden for a cipher that some public function $F$ is such that $F(X,Y,K\{X\},K\{Y\})$ always deciphers the same as $K\{X,Y\}$, and from a secure block cipher it is easy to construct a CPA-secure cipher with that property, with matching $F$ (including, that ignores its inputs $X$ and $Y$).
Even if we restrict to CPA-secure ciphers without that property, some are malleable (e.g. a block cipher in CTR mode), and that allows Eve to make good use of a passively eavesdropped step $\mathsf{[3]}$.


Is there a mental poker algorithm that does not rely on commutative encryption?

Yes, there are some other algorithms that do not rely on commutative encryption.

The Wikipedia page for Mental poker lists some other examples. It describes a non-shuffling poker protocol that uses homomorphic encryption. It has this caveat, though:

  However, the method needs all cards that have already been dealt to be known to all, which in most poker-style games would beat its very purpose.

So it's not practical.

There is also a very interesting paper titled How to Use Bitcoin to Play Decentralized Poker. The authors demonstrate how you could use secure multiparty computation with identifiable abort (ID-MPC) to play a decentralized game of poker.

(Use this Internet Archive link if the Mental poker page has been updated.)


Build a scheme that is CCA secure but not authenticated

Note that the goal of the adversary in the IND-CCA game is not to be able to output some valid ciphertext (i.e., a ciphertext that decrypts to something other than $\perp$), but rather to guess the secret bit $b$ on which the security game is parameterized (see the definitions here).

Since submitting a ciphertext of the form $1 || C$ to the decrypt oracle $D_K(\cdot)$ does not leak any information about the secret bit $b$,
this informally shows that the security of $(G,E',D')$ essentially boils down to that of $(G,E,D)$.

Stated more formally as a reduction: if some adversary $A$ could break the scheme $(G, E', D')$ (in the IND-CCA sense), then we can come up with an adversary $B$ that breaks the underlying scheme $(G,E,D)$. Namely, $B$ runs $A$ and whenever $A$ makes a call to its left-right encryption oracle $LR'_K(M_0, M_1)$, then $B$ responds with $0 || LR_K(M_0, M_1)$, where $LR_K(\cdot, \cdot)$ is the left-right oracle in $B$'s own game. When $A$ asks $0 || C$ to its decryption oracle $D'_K(\cdot)$, then $B$ responds with $D_K(C)$, where $D_K(\cdot)$ is the decryption oracle in $B$'s own game. Finally, if $A$ asks to decrypt $1 || C$ and $C$ as never been used before, then $B$ simply responds with $1$, otherwise $B$ responds with $\perp$. In the end, $B$ outputs the same bit as $A$.

Created in this way, $B$ perfectly simulates the oracles $LR'_K(\cdot, \cdot)$ and $D'_K(\cdot)$ for $A$, and thus wins its IND-CCA game against the underlying scheme $(G,E,D)$ with at least the same probability as $A$.

Incidentally, what you have noticed is that the scheme $(G,E',D')$ is not INT-CTXT secure. This security notion does ask the adversary to come up with some ciphertext that decrypts to something other than $\perp$. A standard result (shown in the paper linked to above) is that IND-CPA + INT-CTXT $\implies$ IND-CCA. So what your example shows is that the converse of this is not true.


Is there a way to break this encryption?

For the 3rd proposal, see my comment to the question for the issues/questions I have regarding there.

For the 2nd proposal, basically what you are proposing is using an IV with a stream cipher. The IV in this case being the hash of the file which would have to be shared in order to decrypt. In theory, it is a good idea. In practice, however, the track record is not very good. WEP used an IV with RC4, which led to a serious vulnerability. Furthermore, of the 34 stream ciphers submitted to eSTREAM, 10 were broken due to the way they used the IV during setup.

This shows that simply putting an IV and a password together is not necessarily better or even secure. You would need much stronger guarantees (for an example of a security proof for IVs in stream ciphers, see On the Security of IV Dependent Stream Ciphers).

So, to answer your question, in general, the construction is not secure. For specific stream ciphers, it might be possible to prove security.

One practical issue I see with this specific construction (even if a proper stream cipher is used), is that if I encrypt the same file with the same key twice, the ciphertext is the same. This leaks some information to an attacker, which is never a good thing.


Verification of identity by certification authority

First of all, as already mentioned in the comments, there is absolutely no mathematics or cryptography involved.

Independent of the model used, i.e., public key cryptography, identity based cryptography, or certificateless public key cryptography (as i summed up in my answer here), the identity verification must be established by other means.

In the wild (currently) only public key cryptography is widely used and PKIX (PKI based on X.509 certificates) is the predominant "standard". Here, the user who generates the key pair sends a certificate signing request (including the public key, identity attributes - which should be included - and a proof that the user holds the corresponding private key - which is established by signing the request) is sent to the certification authority. As already noted in the comments, the "proof of possession" of the respective private key is required to be sure that the user does not come up with the public key of some other user (for which he does not possess the private key).

Then, how the identity verification is done before issuing the certificate mainly depends on the purpose of the certificate, i.e., the corresponding private key.

For instance, many countries, as widely encountered across Europe, have deployed national electronic identity (eID) solutions, where the respective private key can be used to sign documents, and such signatures are equivalent to handwritten signatures. There, you typically have an explicit verification of identity, e.g., by showing up with your smart card (which stores the private key) at a certified registration authority or by offering an online service for activation and the activation code is then send by traditional mail (which you can only receive by showing an official credential such as a passport).

However, this practice is quite different for SSL certificates (which makes up the biggest part) or software signing certificates.

Hopefully, this answers your question and I did not miss anything that should be said.


Keccak padding implementation, and bit ordering

Both are correct, it is confusing because the summary page is discussing the state in terms of bytes, and the spec doc in terms of bits. The actual state for Keccak-1600 is built from 64-bit words.

During the transfer of the input message to the state, the bytes are essentially put into the words in reverse order, which now makes the summary page correct. This is related to the endianness of the specification and how the input message is placed into the state.

Here is an example of the first 576 bits of the input state of Keccak c=1024,r=576 AFTER padding for a simple message "test".

0000000174736574
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
8000000000000000

It can be seen that the 0x01 byte appended to the message precedes the message inside the first 64-bit word, and the final 0x80 byte occupies the highest bits of the final 64-bit word, exactly as how the 10*1 padding scheme says it should.

The resultant output digest after 24 rounds of permutation is:

1e2e9fc2002b002d75198b7503210c05a1baac4560916a3c6d93bcce3a50d7f00fd395bf1647b9abb8d1afcc9c76c289b0c9383ba386a956da4b38934417789e

I believe somewhere in the NIST submission document there is notation describing the bit/byte ordering, as NIST used a different bit ordering for the SHA-3 API.


Do the limitations of PRNGs apply to CSPRNGs when shuffling a list?

If, for example, the PRNG can only be seeded with $2^{32}$ bits, then it cannot possibly produce all the $52!$ distinct permutations. In addition, even if we could meet the 226 bits needed for a 52-card deck, the distribution may not be uniform.

This is true, but a good PRNG (even non-cryptographic) will give you a random sample from a uniform distribution. That means that until you get close to the square root of the seed size, your sampling will still look random. With a 32-bit seed you can easily go over that limit, but with larger seeds you will not.

  Yet, if we used a PRNG with the same seed, but continuously draw numbers from it, we could reach additional permutations.

Yes, but even then the state size will limit which outputs are possible.

  Now, suppose we switch and swap the PRNG with a CSPRNG. How do these limitations apply? In practice, they're seeded and reseeded frequently, depending on implementation, but this is generally done behind the scenes.

If you take a sequence from a CSPRNG that is longer than the state size, without reseeding in between, it cannot produce every possible output value. However, it is guaranteed to be indistinguishable from random.

For example, suppose you have a CSPRNG based on AES CTR. A single AES key will produce $2^{128}$ different 128-bit outputs, but as long as you see (significantly) fewer than $2^{64}$ you do not notice this. As long as the RNG is reseeded often enough and you do not use it enough that both keys and inputs would repeat (impossible in practice), you are fine.

So yes, there are $52!$ different ways to shuffle cards, but since there is no chance that you will look at them all, it is sufficient to generate deck orders from a set of e.g. $2^{128}$ that are themselves a random selection of all possible ones.


Question about variations on Vigenere cipher

Welcome to Cryptography Stack Exchange!
Your variation would not make cryptanalysis significantly harder.
Stepping forward through the alphabet by $n$ steps is the same as stepping backwards through the alphabet by $26-n$ steps and vice-versa. Thus the Vigenere stage S forward (+18) is the same as the variant H backward (-8). The net effect is that the encryption is equivalent regular Vigenere encryption with a garbled codeword and the same cryptanalysis applies. For example, if we used your variant Vigenere with the codeword EXAMPLE and the direction BFBFBBB it would look like Vigenere with the codeword WXAMLPW.
Your idea is related to the "variant Beaufort" of the Vigenere cipher where encryption was done by stepping backwards and encryption by stepping forwards.


Zk-SNARK against Sigma Protocols and for Secure Function Evaluation

Did I mix up too many categories together?

Yes :)

A ZK-SNARK is a method to let a prover demonstrate to a verifier that some statement is true (e.g. "this ciphertext encrypts a number between 3 and 5"), with the following properties:

correctness and soundness: (assuming the prover has bounded computational power) the proof is convincing if and only if the statement is true
zero-knowledge: the proof only leaks the information that the statement is true, nothing more
non-interactivity: the proof is a single message from the prover to the verifier
succinctness: the size of the proof is much smaller than the size of the witness for the statement (e.g. in my previous example, the "witness" could be the secret key of the encryption scheme), and verifying the proof is much faster than directly checking the statement, even given the witness.

A $\Sigma$-protocol is a zero-knowledge proof as well, but with very different properties:

unlike a ZK-SNARK, it is interactive (three moves)
unlike a ZK-SNARK, it is not fully zero-knowledge (but only honest-verifier zero-knowledge)
unlike a ZK-SNARK, it is not succinct

On the positive side, $\Sigma$-protocols exist unconditionally (ZK-SNARK require ultra strong assumptions) and do not need any trusted setup (ZK-SNARKs require a common reference string).

Now, regarding the many things you mentioned:

Fiat-Shamir is not a $\Sigma$-protocol, it is a technique to transform a $\Sigma$-protocol into a non-interactive zero-knowledge proof (NIZK). Note that $\Sigma$-protocol + Fiat-Shamir does not give a ZK-SNARK, because the NIZK is not succinct in general.
Pedersen commitments are not $\Sigma$-protocols, they are commitments - a "cryptographic box" in which you can put a message so that it stays hidden, but which cannot be opened to a different message. They are used a lot to construct the statements we want to prove with $\Sigma$-protocols in high level applications. Typically, you will put many secret values involved in the protocol in these "cryptographic boxes", and use $\Sigma$-protocols to demonstrate that these (hidden) values satisfy some relations.
ZK-SNARKs are not "used to delegate functions", but they are useful when you have a delegation scheme and want to make sure that the server was honest. However, we usually don't really care about the ZK part for this application; what we care about is the succinctness. Here is a typical example: there is a super complex function $f$, you have $x$ and want to compute $f(x)$, but it costs too much. So, you send $x$ to a powerful server, who computes $y = f(x)$ for you and send you the result. But you do not trust the server, so to convince you that the result is correct, the server also sends you a proof that the statement $y = f(x)$ is correct. Here, the core property for this scheme to be useful is that checking the proof should be much faster than computing $f(x)$ yourself (otherwise there would be no point in delegating the computation in the first place).

Note that $\Sigma$-protocols are not succinct, so they are useless for the application to delegation of computation. Secure function evaluation has also nothing to do with that. Secure function evaluation is used in delegation when you want to hide the input $x$ from the server (so the server should compute $f(x)$ for you without seeing $x$). This is an orthogonal problem; what ZK-SNARK solve is the problem of letting the server prove that he computed the right value. This can be done independently of whether the server is doing the computation "blindly" (using some secure function evaluation technique, e.g. homomorphic encryption) or in the clear. Hence, SFE and ZK-SNARKs are just completely different, both can be used to solve different problems related to delegation.

RSA accumulators and attribute-based encryption have nothing to do with all of that. If you have ZK-SNARKs, you can build accumulators, but that's it. RSA accumulators are just a specific type of accumulators, and one that does not use ZK-SNARKs. Attribute-based encryption is an advanced cryptographic primitive that might use other simpler primitives in some existing constructions, but in general it has no formal relations to ZK-SNARKs.


How should I manage Diffie-Hellman parameters on a Web Server?

I will address your question below, however I have a serious concern that I want to bring up first. I glanced at the $p$ used in ngx_ssl_dhparam, and it is not immediately obvious that it was chosen correctly.  Unless you know that whoever generated that value knew what they were doing, you should select a different value.

The security of DH depends on, among other things, the factorization of $p-1$.  If $p-1$ has a prime factor $q$ (and $g$ wasn't selected such that $g^{(p-1)/q}\equiv 1\  (\bmod p)$), then an attacker, seeing the DH public value $g^e \bmod p$, can determine $e \bmod q$ with $O(\sqrt{q})$ work.  This means that if $p-1$ has a number of moderately sized factors (which will often be true of randomly chosen primes), and $g$ wasn't carefully selected, then you'll be leaking a significant amount of information; quite potentially enough to make DH completely insecure.

In your case, we have $g=2$; this would appear to make it unlikely that $g$ was chosen to avoid small factors.  And, if $p$ were a safe prime, this would not be much of a concern (because safe primes have no small factors to $p-1$ other than $2$), however you stated (and I have not confirmed) that their specific $p$ is not a safe prime.  I do note that, with $g=2$, your group has $g^{(p-1)/2} \neq 1$, and hence you do leak at least one bit of $e$ -- if that were all you leaked, that would not be much of a concern; however it begs the question "what else is being leaked".

I haven't checked if your $p-1$ has small factors; unless you check (or you trust whoever generated it), I would strongly urge that you use a different value of $p$.  This specific value of $p$ might be secure, however I don't know that (and I suspect you don't either). When I am asked for recommendations for DH groups, I always send people to the IKE groups; those are all safe primes (and work well with $g=2$, not leaking even that one bit)

Now, to go back and answer your question: no, you shouldn't have to rotate the group parameters on a regular basis.  It turns out that solving the problem "given these $N$ DH exchanges over the same group, solve any one of them" is not actually any easier than "given this 1 DH exchange, find the shared secret".  That is, if the group is weak when you reuse it for DH, you shouldn't be using that group in the first place.

On the other hand, a 1024 bit value of $p$ is getting to be fairly small nowadays.  NFS has been used to factor a 768 bit value recently; it should not be that long before it could practically be used to solve 1024 bit DH problems (which would mean that your group could be broken, even if $p$ was chosen without any inherent weaknesses).  I would suggest you consider at least a 1536 bit $p$ (and preferably a 2048 bit value); from what we know, those should be secure for a number of years.

Update: I just double-checked; $p$ is indeed a strong prime, that is, $(p-1)/2$ is also prime.  Hence, the concerns I raised about $p-1$ having small factors do not apply; there is a 1-bit leak (because of the factor 2 of $p-1$), however there is no other leakage.

My concern about the size of $p$, and whether that would be secure long-term, still remain.  I'll leave in the comments about weaknesses that may arise with $p-1$ having small factors; even if they don't apply in this case, future readers may find it useful.


Pedantically, you always have an IV with AES-CTR; you need to start counting somewhere.  So, your question really is "do I need an explicit IV, or can I use an implicit all-0 IV"?

With AES-CTR, the important requirement for IVs is that you never reuse the same IV for the same key.  With ECIES, you'd reuse a key only if the sender used the same random number $r$ twice (and used that common $r$ to encrypt to the same public key).  Assuming that you never do that, that is, you always pick a fresh $r$ whenever you do a public key encryption, then you are correct, using an implicit fixed IV is just fine.


Difference between Constructor and Destructor terms

Now I think I know what are constructor terms and destructor terms.

  Constructors are used to build terms

means that there is no correspondent term to represent the application of a constructor to others terms. They are function symbols (like $enc$, to represent encryption) that are applied to other terms resulting in another (like $enc(m, k)$ to represent the encryption of $m$ using key $k$. The term $enc(m, k)$ is not in the list of terms $T$, so, it is a built term).

  Destructors manipulate the terms

as I thought, this sentence is not clear. In fact destructors are applied to other terms just like constructors, but they are interpreted and substituted by other terms. For instance, $dec$ is a destructor term that represents the decryption algorithm and $dec(enc(m, k), k)$ is reduced to the term $m$.

And finally, what I said about destructors in the question was not too wrong... As stated in page 18 of these MPRI notes: "Destructors are used to model the fact that some operations fail."

So, for instance, $dec(enc(m, k_0), k_1)$ fails if $k_0 \not = k_1$, and the process doing the substitution may block or treat the failure.

For instance, assuming $g$ is a destructor, the process

let $x = g(M_1 , ... , M_n )$ in $P$ else $Q$

bounds $x$ to the resulting of $g(M_1 , ... , M_n )$ and then execute $P$, or, execute $Q$ if $g$ fails.


Are XOFs and KDFs more usable than DRBGs?

I don't know what the rationale behind the designs in the NIST SP800-90 standards were—internal discussions may be obtainable by public records requests—but I can hypothesize a few reasons:

Backtracking resistance.  While SP800-90C does cover KDFs (like HKDF and SP800-108), and while sponges are available now, there's more work to be done in SP800-90A to attain backtracking resistance:

A mere KDF, e.g. HMAC with a counter, does not necessarily provide backtracking resistance on its own unless you iterate it (like HKDF-Expand could be construed to do, but only for each info parameter independently).  Although it's not too difficult to show that this is safe—the expected length to cycle in the iteration of a large uniform random function is only square root of large, and it can't be much different for a pseudorandom function—application developers aren't going to prove this themselves and auditors want guidance from a standard.
A mere sponge XOF, e.g. SHAKE128, does not provide backtracking resistance on its own: if the full state is ever compromised, then you can simply evaluate Keccak in reverse until you get all the old outputs.  There are various ways you could work around this, but there's no one obvious natural way.

Hysterical raisins.  NIST SP800-90A predated sponge constructions, so the tools at hand were:

pseudorandom permutations (block ciphers) like AES
variable-input fixed-output hash functions like SHA-256
fixed-input variable-output hash functions like Salsa20 or AES-CTR
public-key cryptography for making back doors

Although Salsa20 used the model of a random permutation $\pi$ in the form $x \mapsto \pi(x) + x$ to approximate a random function, which in turn was used in ‘CTR mode’ to approximate a one-time pad, the pervasive design principle of building everything out of a single permutation—like we see now with Keccak, in SHA-3 and KangarooTwelve and Kravatte and Strobe, and even with other permutations like Gimli in libhydrogen—had yet to reach prominence.
Cost of collision resistance.  There seems to be a much higher cost to collision resistance than to preimage resistance.  But DRBGs don't need collision resistance.  So, e.g., AES-CTR_DRBG can presumably be faster than HKDF-SHA256 or SHAKE128.  (Of course, you could use a much faster Keccak sponge like the 12-round KangarooTwelve or even the 6-round Kravatte but they're not among the SHA-3 functions.)
Avenue for Dual_EC_DRBG.  It seems implausible that NIST would choose to standardize DRBG interface and security requirements only to introduce a back door—it's so foundational for so much cryptography that standardization would be well within NIST's purview even without the back door.  But the prospect of attacking this foundation could have motivated NSA to push slightly harder for NIST to standardize it.

That said, you're unlikely to get the real answer unless (a) you file a FOIA request to get the internal design discussions, or (b) someone from NIST hangs out here.


What's efficient MPC protocol for determining if sum's bigger than y?

The answer is definitely yes. You should be able to do what you are looking for. The computation is very simplistic, so using existing MPC protocols will be efficient. Many of the existing protocols are able to evaluate a few blocks of AES using MPC per second, so this computation will be no problem.

Typically MPC works by translating your function into a circuit (either boolean or arithmetic). In the 2 party case, you are probably best off using Yao's approach. There are newer constructions that you could use and that would probably still be efficient, but they do use some heavy public key crypto and I'm not aware of any publicly available implementations. For Yao's approach, I'd recommend the MightBeEvil framework. I believe Yao's approach is most commonly (if not always) used with boolean circuits. Another option is Fairplay.

In the multi-party case (more than 2 parties), garbled circuits won't do (at least not with publicly available implementations). Your options here are really Viff and Fairplay-MP. Viff uses arithmetic circuit representations while Fairplay-MP uses boolean circuits. Viff has a specialized protocol from Toft for comparison to help mitigate some of the problems with comparison in arithmetic circuits (more on this in a moment).

Adversary Model
You don't mention adversary model in your post, but I thought I'd say a little on this. You have 3 choices in the literature: semi-honest (or honest-but-curious), covert, and malicious (or Byzantine). Fairplay, Fairplay-MP, and MightBeEvil all only support semi-honest adversaries while Viff has support for both. Theoretically any of Fairplay, Fairplay-MP and MightBeEvil could be made to support malicious adversaries, but they don't out of the box and would require significant work (not to mention publishing to make sure you didn't make any mistakes).

If you are not familiar with the difference, semi-honest assumes that corrupt parties will follow the protocol as specified and only use information gleaned during the execution to violate privacy. Malicious makes none of these assumptions (parties can deviate all they want from the protocol and will always be caught, caught with overwhelming probability). I am not aware of any implementations available publicly that support covert adversaries. FYI, a covert adversary is one who will deviate but doesn't want to be caught, so you only have to define the protocol such that the probability of catching a deviating adversary is high (as opposed to overwhelming).

Boolean vs Arithmetic
Both approaches have their strengths and weaknesses. In arithmetic circuits, addition is cheap but comparison is much more expensive. The opposite is true in boolean circuits. I believe that, for example, in the MightBeEvil framework, they have built in circuits for say a 32 bit adder but not a 2000 bit adder. Thus, input size will make a difference here. On the arithmetic side, you only have to define the underlying field large enough to support the input size. This will have an effect on performance, but not as large as in the boolean circuit approach.

Comparison in boolean circuits is relatively easy. Simply start with most significant bits and compare the bits using a single bit comparison operation. Scan from MSb to LSb, stopping when a difference is found. Whoever has the 1 bit in this case is the larger of the two. On the arithmetic side, things are more complicated which is why Viff uses a specialized protocol from Toft. For small input sizes, it probably won't make a huge difference.


Why isn't E' secure if it's built over a secure cipher?

Summarizing the answer from the comments:

what happens if E is a stream cipher? ~ Richie Frame
What if you use exclusive-or to combine the key stream instead of addition? ~ Ella Rose
So $c_i=m_i\oplus k_i\oplus k_i=m_i$, and it would be trivially broken. Thanks! I wouldn't come up with the idea of using a stream cipher nor modifying the one-time pad like this. ~ Daniel


Given partial key exposure and encryption oracle, can we recover full AES key?

No, there is no known easier attack than doing a brute force search on the unknown key bits.

In particular, if there were, then this show an attack on the standard (no key bits leaked) AES, because what an attacker could do is go through all possible $2^{8n}$ settings of those key bits, assume those, and run his 'less-than-brute-force' attack on the remaining key bits.  If this attack (when his guess for the 'known' key bits is correct) takes an expected time of less than the time taken to compute $2^{128 - 8n-1}$ AES evaluations, then the total time will take less than the time taken to do $2^{128-1}$ evaluations, that is, it shows that there is a faster-than-generic attack


What are the advantages of mutual private set intersection methods over finding the intersection of hashed lists?

Naive hashing protocol

Suppose Alice has items $x_1, \ldots, x_n$ and Bob has items $y_1, \ldots, y_n$. In the naive hashing protocol, they agree on a common hash function $H$, and Alice sends $H(x_1), \ldots, H(x_n)$ to Bob. Bob can compute $H(y_1), \ldots, H(y_n)$ and then calculate the plaintext intersection between these two lists.

Insecurity of naive hashing

First of all, there is nothing inherently symmetric about this protocol. Bob doesn't have to send $H(y_1), \ldots, H(y_n)$. If he doesn't, then Alice doesn't learn anything. I think two-sided output vs one-sided output is a red herring for this question.

The naive hashing protocol is vulnerable to the following kind of attack. Suppose that after the protocol is finished Bob learns of a special value $v$ that he couldn't have predicted before the protocol (e.g., the $x_i$'s and $y_i$'s are email addresses and he just learned the email address $v$ of an important person, which he didn't know before). Now Bob can test with certainty whether $v$ was in Alice's set, by checking whether $H(v)$ was among the values she sent. The protocol continues leaking information after it's over.

In the extreme case, the $x_i$ values can come from a small domain (e.g., phone numbers, SSNs) and Bob can simply do an exhaustive brute force attack to learn all of Alice's $x_i$'s.

Difference with secure PSI

The important property of real PSI protocols is that they prevent this kind of an attack, where one of the parties can check after the fact whether their opponent was holding some value. In a truly secure PSI protocol, if Bob wants to know whether Alice has an item $v$, he has to include $v$ in his set at the time of interaction. It should do him no good to speculate about $v$ after the protocol is finished. The PSI protocol leaks the intersection of $X \cap Y$ once, and no more information about $X$ and $Y$ is leaked thereafter.

Example / better mental model for PSI

A good way to think about PSI protocols is that they do the naive hashing protocol, except the common hash function $H$ is something that requires a secret key from both parties. Something like $H(x) = H_{\alpha,\beta}(x)$ where $\alpha$ is a key that only Alice knows and $\beta$ is a key that only Bob knows.  Since both parties contribute a secret key to the computation, you have to assume that Alice & Bob have a way of computing such an $H$ interactively, in a way that no one learns the inputs to $H$ -- only the outputs.

(Note: not all PSI protocols actually work this way, but this approach is secure and it gives the right intuition about PSI security.)

If Bob tries to do this after-the-fact attack, he will find that he can't compute $H(v)$ on his own. He doesn't have Alice's key to this $H$. This is why the computation of $H$ was interactive in the protocol. And, since the protocol has terminated, Alice will not agree to help compute $H$ on additional inputs.


Is unusual (non power-of-two) RSA key size more secure?

From this answer:

  The difficulty of factoring (thus, as far as we know, the security of RSA in the absence of side-channel and padding attacks) grows smoothly with $n$.

So, if factoring is the method of choice for breaking RSA, it doesn't seem like it really helps.


Flaw in the security definition of *Stateful* Authenticated Encryption?

Answering my own question since there haven't been any response.

In fact there is no flaw in the definition. Nor in my attack per se!

However, the entire point of this definition is to rule out non-stateful schemes (and stateful schemes that doesn't incorporate the state in a sufficient manner) as being secure. In particular, when the adversary asks for the decryption of $C_2$, the decryption algorithm is in state "1", not "2", i.e., expecting to receive a ciphertext created by an encryptor who was in the "1" state when he created it. Thus, if the stateful scheme is worth its salt, the decryption of $C_2$ better result in failure, i.e., $\perp$. Hence, it's no problem to return the "decryption" in $\mathsf{phase} = 1$ anymore, since it will not give the attacker any distinguishing advantage.

I mistakenly thought that this attack applied generically to all encryption schemes, but forgot that non-stateful schemes should fail this definition.


RSA: Given (e,c,d) is possible to solve?

No, it would appear to be a hard problem; being able to recover the plaintext allows us to recover $n$ (at least, for small $e$), and recovering $n$ would appear to be difficult.

Knowing $e, d$, we know that $ed \equiv 1 \pmod{ \text{lcm}(p-1, q-1)}$, or equivalently, $ed - 1 = \frac{k}{\text{gcd}(p-1, q-1)} (p-1)(q-1)$, for some integer $k$.

As both $k$ and $\text{gcd}(p-1, q-1)$ are likely to be small (and from $c$, we can get a rough idea about the size of $n$), we are likely to be able to have a plausible guess to $(p-1)(q-1)$.

However, to convert that to $pq$, we'll need to factor $(p-1)(q-1)$; while $p-1, q-1$ both a likely to have some small factors (allowing us to reduce the size of the problem a bit), however, it appears likely that there won't be enough small factors to reduce the size enough; performing a complete factorization won't be all that much easier than the original 'factor $pq$' problem...


Why was the winner of the AES competition not a Feistel cipher?

DES actually demonstrated that a Feistel structure was not a guarantee against attacks. In "academic" terms, DES is broken by both differential and linear cryptanalysis, because they require, respectively, $2^{47}$ chosen plaintexts and $2^{43}$ known plaintexts, whereas the DES key is (effectively) 56 bits. Of course, for practical attacks, we would brute force the key: computing the function $2^k$ times is vastly easier than obtaining $2^k$ known plaintext/ciphertext pairs (or, even worse, chosen plaintext/ciphertext pairs). But in the usual "academic" evaluation of security, both linear and differential cryptanalysis count as breaks.

Luby and Rackoff have demonstrated in 1988 that given "perfect" round functions, a four-round Feistel structure is secure. However, this proof has two practical issues:

It is relative to the output size of the round function, i.e. 32 bits for a 64-bit block cipher. For 128-bit security, blocks have to be 256-bit wide for the proof to actually apply; but the AES call for candidates requested 256-bit security with 128-bit blocks, not the other way round.
DES has amply demonstrated that concrete round functions cannot be assumed to be perfect.

So while the security provided by a Feistel structure was already quite well understood at that time (around 1997, when AES candidates were being designed), it was also quite known to be "suboptimal" in the following sense: to get the most out of the existing security proofs, you had to go to impractical block sizes or number of rounds. Indeed, many researchers were dissatisfied with the Feistel structure, and eager to explore new structures. The AES competition was at the right time to become a test bed for such novel designs, and the accumulated research has shown substitution-permutation networks (as used by Rijndael) to be valid competitors to Feistel structures.


RSA: Private key given public key, plain text, and cipher text with no padding?

No there is not.

First of all the key size needs to be bigger then the message otherwise RSA will not work

Remember one thing, if you have a public key you can have as many clear texts and cipher texts as you want. This is because everyone can use your public key to cipher a message. So if there was a method were by knowing the public key, clear text and cipher text you could discover the private key RSA would not be used. The question of whether the Padding is used or not is irrelevant. Knowing the public key you can cipher the messages using padding or no padding it is your choice. I am sure that in java you will have providers that implement RSA with no padding so you right now can get millions of clear texts and cipher texts from any public key.

Now why this can't happen:

$C^b = M\ mod\ N$

Being C the ciphertext, b the private key and M the clear text. Then you get

$b = \log_c M\ mod\ N$

And this is the problem. This is discrete log which is in NP. So you can't solve this in polynomial time even if you have infinite number of ciphertexts and clear texts


Randomness extractors from Bourgain’s breakthrough- applications?

...would it help in any way with the issues discussed here?

No, not really. There's always been a gap between myriad theoretical mathematical extractor constructs and those used in commercial validated TRNGs.  I honestly don't know why as that seems like an unlikely dichotomy, yet it demonstrably exists. The two should ideally converge to a common output entropy rate, but they don't :-(

Most creditable TRGNs are based on min. entropy extraction via the Left Over Hash Lemma: $  \epsilon = 2^{-(sn-k)/2}   $ where $s=H_{\infty}$per bit input to the extractor. This lemma is unaffected by Bourgain.

So no.


Request for review: known plaintext mitigation by rotation and xor encoding

For a secure cipher, the best attack is a brute-force key search: Iterate through all keys and try decryption until you find one where the result fits.

Having known plaintext in known blocks of the message helps, because then we need to only decrypt one block for most keys.

With your method, one might need to decrypt enough blocks to be able to undo the transformation ... this makes it a bit harder, but only by a small constant factor (depending on the number of blocks needed, at most the whole message will need to be decrypted).

As usually the key sizes for ciphers considered secure (like anything $\geq 128$ bit for a symmetric cipher) are anyways out of reach for brute-forcing even with known plaintext, your method doesn't help in practice.

With a non-secure cipher, or one with a too small key size, this could help to increase the costs (or time) of cracking for an attacker significantly, for example from using 5 million \$ hardware to 50 million \$ (in the same time), or from 5 hours to 50 hours (using the same hardware), assuming that in average 10 blocks instead of one needs to be tried.
But then, you are better of using a secure algorithm with a sufficiently big key size than trying arbitrary modifications of the plaintext combined with an insecure cipher.


LED and prince ciphers are designed for lightweight purpose (to save area, energy..etc) , They have no key schedule. Other ciphers that have no key schedule are Zorro, Midori, LS-designs (Fantomas & Robin).
The above mentioned ciphers use round constant addition for protection.


Why do a pair of interactive machines have a common input?

Interactive Turing Machines are used to model real-world parties that interact and perform local computations using some algorithms. So, why would they not have a common input? The common input simply capture the fact that both parties can start a protocol knowing some common value, which perfectly makes sense in any real-life application. In the definition of interactive proof system, we want to abstract out what it means to interactively prove a statement; so, the natural approach is to let both parties initially know the statement, and ask for one of the parties to prove it to its opponent. The question of how the statement became known to the parties is irrelevant to the question of building an interactive proof.

That being said, yes, you can trivially let one of the parties send the statement to the other party, and then prove its truth with an interactive proof system. Depending of the specific interactive proof system you consider, some might not require knowing the actual statement during the interaction (although it will be clearly needed by the verifier when executing his verification algorithm on the transcript). In this case, the proof could indeed be performed first, and the actual statement be sent later. But that's not the case of all existing proof systems.


How does one scale encryption strength upwards from 256-bit?

As @David Schwartz said, using something like 3AES should work to scale up the security (but see my comment on the meet-in-the-middle attack). But seriously, why would you even need 512-bits of security in a symmetric algorithm? According to the analysis on wikipedia it would take 50,955,671,114,250,100,000,000,000,000,000,000,000,000,000,000,000,000 years to bruteforce 256 bit AES (given a few assumptions on speed). I doubt you have any data that needs to be secured for that long.

As far as whether the CPU limits the security strength, it doesn't. There are libraries out there which provide "infinite" precision numbers (i.e., gmplib for c/c++, BigInteger and BigDecimal for Java, etc). For more on computing with large numbers, see chapter 14 of the Handbook of Applied Cryptography (HAC). Internally, these libraries use things like long long int or even plain int stored in an array. HAC has the algorithms.


Affine transformation in AES: Matrix representation

In literature there are 2 ways to show the affine transform for a given polynomial, and that depends on the location of the MSB in the input as a polynomial.

The polynomial representation of the full transformation, in the format of the original Rijndael paper, is:

$b(x) = a(x)(x^7 + x^6 + x^5 + x^4 + 1) + (x^7 + x^6 + x^2 + x) ~~mod~~ x^8 + 1$

Where $a(x)$ is the input polynomial, and $(x^7 + x^6 + x^5 + x^4 + 1)$ is the polynomial formula of the affine matrix. $(x^7 + x^6 + x^2 + x)$ is the 'vector' constant.

The original Rijndael paper and Wikipedia use the same representation of the affine transform matrix, so we will start there.

$$
 \begin{bmatrix}
y_0 \\
y_1 \\
y_2 \\
y_3 \\
y_4 \\
y_5 \\
y_6 \\
y_7 \\
 \end{bmatrix}=
 \begin{bmatrix}
1& 0& 0& 0& 1& 1& 1& 1 \\
1& 1& 0& 0& 0& 1& 1& 1 \\
1& 1& 1& 0& 0& 0& 1& 1 \\
1& 1& 1& 1& 0& 0& 0& 1 \\
1& 1& 1& 1& 1& 0& 0& 0 \\
0& 1& 1& 1& 1& 1& 0& 0 \\
0& 0& 1& 1& 1& 1& 1& 0 \\
0& 0& 0& 1& 1& 1& 1& 1 \\
 \end{bmatrix}
 \begin{bmatrix}
x_0 \\
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
x_6 \\
x_7 \\
 \end{bmatrix}+
 \begin{bmatrix}
1 \\
1 \\
0 \\
0 \\
0 \\
1 \\
1 \\
0 \\
 \end{bmatrix}$$

The rightmost column of the matrix top to bottom and the top row right to left is the start representation of the affine transform polynomial, the other rows/columns are simply rotations of the polynomial, since it is a rotational matrix. The vector constant top to bottom is the representation of the vector constant polynomial. Note $x_0$ is the LSB of the input.

The other representation is from The Design of Rijndael (page 36), to which you posted a link. You can see the matrix is the same, but rotated 180°. You can also see the input and output have their MSB locations flipped. Make note that addition and XOR in the field are the same.

$$
 \begin{bmatrix}
b_7 \\
b_6 \\
b_5 \\
b_4 \\
b_3 \\
b_2 \\
b_1 \\
b_0 \\
 \end{bmatrix}=
 \begin{bmatrix}
1& 1& 1& 1& 1& 0& 0& 0 \\
0& 1& 1& 1& 1& 1& 0& 0 \\
0& 0& 1& 1& 1& 1& 1& 0 \\
0& 0& 0& 1& 1& 1& 1& 1 \\
1& 0& 0& 0& 1& 1& 1& 1 \\
1& 1& 0& 0& 0& 1& 1& 1 \\
1& 1& 1& 0& 0& 0& 1& 1 \\
1& 1& 1& 1& 0& 0& 0& 1 \\
 \end{bmatrix}
 \begin{bmatrix}
a_7 \\
a_6 \\
a_5 \\
a_4 \\
a_3 \\
a_2 \\
a_1 \\
a_0 \\
 \end{bmatrix}+
 \begin{bmatrix}
0 \\
1 \\
1 \\
0 \\
0 \\
0 \\
1 \\
1 \\
 \end{bmatrix}$$

The bottom row of the matrix left to right and the first column bottom to top is the start representation of the affine transform polynomial, the other rows/columns are simply rotations of the polynomial. The vector constant bottom to top is the representation of the vector constant polynomial.


Diffie-Hellman computing public key with a large private key

On a calculator this gives overflow error, how am I supposed to calculate the public key when a private key is a large number?

A standard calculator cannot handle that, and we don't expect it. If you have a programmable one you can use square-and-multiply as in levgeni's answer. This, however, will fail when the calculator cannot handle integers (the modulus) larger than the calculator's word size.
There are better and easy approaches

Use WolframAlpha 5^7347 mod 10007
Use SageMathCell 5^7347 % 10007
Use Python's pow that takes a third parameters as modulus pow(5,7347,10007) and uses modular-square-and-multiply. Online


PBKDF2 for login key, scrypt for encryption key

Server shouldn't know plain password

If the user types their password into a web page in a browser, the server that hosts that web page always has the opportunity to see what password was entered.  There's no cryptographic mechanism that can prevent that (at this point in time).

To get around this limitation, you need to build a downloadable application instead (e.g. you could use NW.js and Cordova to package up HTML/JS/CSS into desktop/mobile apps).  If you don't do this, there's essentially no point in trying to hide the password from the server.  More about that in this article.

If you've done that (again, no point in continuing if you haven't), I would recommend against using a JS implementation of PBKDF2 or scrypt, if possible.  A JS implementation of either will be slower and force you to use a lower iteration count (since users will only wait so long).  Attackers will have access to a highly optimized C implementation, so this would give your attackers a significant advantage.  Note that most languages have wrapper libraries for C implementations of PBKDF2 or scrypt (e.g. node-scrypt).

To derive the keys, I recommend taking the following approach on the client:

Derive one 256-bit master key using scrypt (PBKDF2 is also acceptable).  Use security parameters that are as high as practical, but keep in mind that mobile devices might have a rough time.  I recommend using a unique salt for each user.
Use HKDF-SHA256 to derive a login key.  HKDF allows you to safely derive keys from a master key such that it is infeasible to determine the master key (or other keys) from the derived keys.  In the context or info parameter, use the string "server-login-key".  128 bits of output should be adequate.
Use HKDF again to derive an encryption key.  Be sure to derive the encryption key from the master key, not the login key.  In the context/info parameter, use the string "client-encryption-key".  Generate a key long enough to match whatever encryption algorithm you plan to use (e.g. 256 bits for AES256).

When storing the login keys on the server, be sure to treat them like passwords (store only the salted hashes).  You may use PBKDF2/bcrypt/scrypt here again, but it's not critical since the key has already been stretched.  Additional stretching is a good thing, but it won't help if the server is actually malicious.

An important difference between this and your design is that it invokes PBKDF2/scrypt only once, instead of twice.  This allows you to double the security parameter (i.e. one invocation with 2N iterations instead of two invocations with N iterations each).

If users don't have strong passwords, then the server will be able to crack the password based on the login key (dictionary attack), so give careful thought to this as well.

Note: The "Extract" step of HKDF is optional in this case because PBKDF2 and scrypt already output cryptographically strong keys, but it won't hurt.


W is 87 in ASCII, so
$$
87a+b\equiv064066\pmod{256256}.
$$

I is 73 in ASCII, so
$$
73a+b\equiv158368\pmod{256256}.
$$

Subtracting, you get
$$
14a\equiv-94302\equiv161954\pmod{256256}.
$$

Unfortunately 14 is not coprime to 256256, so you'll need to use other letters to figure this out. Once you get an equation of the form
$$
ma\equiv n\pmod{256256}
$$
you can solve for $a\pmod{256256}$ and then substitute to find $b\pmod{256256}.$

(In fact, you already have enough to solve with trial and error, but it's nicer to avoid that.)


hill cipher encryption way 1x3 plaintext matrix

Both representations are essentially equivalent.  If

$$
\begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix}
= \begin{bmatrix} k_{11} & k_{12} & k_{13} \\ k_{21} & k_{22} & k_{23} \\ k_{31} & k_{32} & k_{33} \end{bmatrix}
\cdot \begin{bmatrix} p_1 \\ p_2 \\ p_3 \end{bmatrix},
$$

then, equivalently

$$
\begin{bmatrix} p_1 & p_2 & p_3 \end{bmatrix}
\cdot \begin{bmatrix} k_{11} & k_{21} & k_{31} \\ k_{12} & k_{22} & k_{32} \\ k_{13} & k_{23} & k_{33}
\end{bmatrix}
= \begin{bmatrix} c_1 & c_2 & c_3 \end{bmatrix}.
$$

This is a special case of the general rule that

$$ c = K p \iff p^\top K^\top = c^\top, $$

where $M^\top$ denotes the transpose of the matrix $M$.


Yes for sure you can do that. Mapping this protocol to an elliptic curve setting is just like mapping DH key exchange to ECDH key exchange. In AugPAKE you work in a prime order $q$ subgroup of $Z_p^*$ and in the EC setting you use a prime order $q$ elliptic curve group.

Observe that in the EC setting a multiplication of group elements in AugPAKE is then point addition and exponentiation in AugPAKE is then scalar multiplication.


This paper answers your question most succinctly:

The size of a Winternitz signature is roughly $mn/w$ bits and signing roughly requires $2^wm/w$
hash operations, where $m$ is the bit length of the hash value to be signed, $n$ is the output length of
the hash function used in the scheme, and $w$ is the Winternitz parameter determining the tradeoff between signature size and signature generation time.

The reference paper here goes into detail on how the parameter $w$ is used in various algorithms.  Per the paper:

The parameter $w$ can be chosen from the set {4, 16}.
A larger value of $w$ results in shorter signatures but slower overall
signing operations; it has little effect on security.  Choices of $w$
are limited to the values 4 and 16 since these values yield optimal
trade-offs and easy implementation.

An example of the parameter being used is in Algorithm 5: WOTS_sign - Generating a signature from a private key and a message.
Section 2.2 of this paper goes into further detail about time-memory tradeoff.
Additionally section 4 goes into further depth with performance comparisons of different parameters.


Choosing an optimal generator for an irreducible polynomial over a binary field?

What you need is a primitive polynomial of degree $m$ (for using with $\operatorname{GF}(2^m)$).

This is an irreducible polynomial whose roots have maximal multiplicative order $2^m-1.$

There are tables of these, at least one is guaranteed to exist for each degree. Alternatively they can be found by randomised methods. Use a polynomial factorisation algorithm to get an irreducible of degree $m$, say $f(X)$  and then check that $$X^i \bmod f(X)\neq 1$$ for any proper divisors $i,~1<i<2^m-1$, of $2^m-1.$

If you know one such polynomial with a root $X$ then its roots are $X,X^2,\ldots , X^{2^{m-1}}$ each with multiplicity 1. By trying $X^u$ with $\gcd(u, 2^m-1)=1$ you may find a lower weight polynomial to enable efficient implementation, just write the new polynomial as
$$
f_u(z)=(Z-X^u)(Z-X^{2u})(Z-X^{2^{m-1}u})
$$
and simplify over $\operatorname{GF}(2).$

Edit: Error in last equation corrected.


Is it possible to decrypt only a portion of a gpg encrypted file?

Yes, it should be possible to decipher a chunk of a large RFC 4880 / OpenPGP file (without deciphering the bulk of what's before), assuming the (private or symmetric) key necessary for sequential deciphering is available, and the entity that prepared the enciphered file did so without using the file format's compression feature (even though using it is the default and most common). There is an attribute in the public key format allowing the recipient to require that compression is not used (see RFC 4880 section 13.3.1), thus what's asked should be possible.

However

The integrity of the separately deciphered chunk can not be ascertained; it seems that as a bare minimum, the file should be integrity-checked once (e.g. the signature by the alleged sender verified) before starting to decipher it as chunks.
There is a risk that some untested implementation (or one predating the OpenPGP spec) does not honor the "don't compress" flag correctly (that is, compress even though one of the intended recipients forbids). An option in this case would be to sequentially decipher then re-encipher the file without compression for future direct access.
Usual libraries implementing OpenPGP decryption are not designed with direct access in mind, and will need to be modified, as follows.

The general idea would be to process the beginning of the file as usual, up to the point where the symmetric key and algorithm used for encryption of the bulk of the data is known; then (when the chunk to decipher is not near the beginning of the file) seek to an appropriate location considering the block size (8 octets for 3DES, 16 octets for AES). OpenPGP uses a block cipher in CFB mode with a slight modification at the beginning, thus we must skip two octets and an appropriate multiple of the block size, then decipher as in normal CFB, using as IV the ciphertext block immediately before the ciphertext block containing the first octet of the chunk to be deciphered.

Note: In the above, "chunk" is used as in the question, for some large portion of the useful data in the file. And "block" designates the amount of data at the input and output of a block cipher; that's 16 octets (128 bits) for all variants of AES. RFC 4880 also uses "block" for that meaning, and occasionally others (e.g. in "block of text"). RFC 4880 consistently uses "packet" to designates a section of the file with a certain format; see section 4 for the general format of packets, section 4.3 for the various kinds, and section 5 for details. "Blocks" in the sense I use live in a Symmetrically Encrypted Data Packet.


Unknowingly, you've actually answered your own question in the title.

  transformations

Imagine if you put and hold your finger on one of the bits in a test message. Then encrypt.  After a long time and possibly some cramp, your finger will have passed through the transformation matrix and out into the cipher text. One bit in and the same bit out, albeit possibly in a different position.   You're only transforming the position of the individual bits. This is entirely linear and is called a transposition cipher.  Security to cryptanalysis is very low indeed, and breaking one by frequency analysis is demonstrated in https://crypto.stackexchange.com/a/1578/23115.

Contemporary encryptions require other properties such as the following introductory list:-

Unbiased output - As only a single bit is transformed, there will be no uniformity of output frequencies.  Your message pops out the other side, only bit shifted, with exactly the same biases it had originally.
Confusion and diffusion -  Each bit should affect the other bits to a degree.  Your finger should morph into many, or even non.
Constant execution time - Cryptographers make huge effort to ensure that an algorithm flows/executes in constant time. Having major parts of it under control of the key/attacker gives too much away.
Some would argue that a 1024 bit key into a 10,000 bit block state may be unnecessarily high. There's some wonderful discussion of the futility of brute forcing large keys at How much would it cost in U.S. dollars to brute force a 256 bit key in a year?

There's quite a lot more to cipher design than my examples, but they give some context to the degree of weakness of design. Sorry.  There's a much more comprehensive list that answers What are the qualities of a good block cipher? Begginner, Intermediate, Advanced, Expert?


No. A MAC guarantees unforgeability but not pseudorandomness. It is true that all MACs that I can think of right now are essential pseudorandom functions, but this does not mean that the MAC definition implies this. Indeed, it clearly does not.

So, conceptually, you need a pseudorandom function. You can assume that HMAC is a pseudorandom function. It is proven that CBC-MAC on prefix-free inputs behaves like a pseudorandom function. But this doesn't mean that it's always the case.


ElGamal: Multiplicative cyclic group and key generation

I'm not sure what level of explanation you are looking for, but from the very basics, subgroups work like this.

Consider concretely the example of working $\mod{p}$ where $p=11$. Next we have to find a generator $g$. Initially, any number $\{0,\ldots,n-1\}$ (or $\mathbb{Z}_p$ for short) is a candidate.

Below is a chart showing each $g$ value as a row, each $a$ value as a column, and the expression $g^a \mod{11}$ evaluated for each $g$ and $a$.

$
\begin{array}{c|ccccccccccc}
 g \backslash a & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
 2 & 1 & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6 & 1 \\
 3 & 1 & 3 & 9 & 5 & 4 & 1 & 3 & 9 & 5 & 4 & 1 \\
 4 & 1 & 4 & 5 & 9 & 3 & 1 & 4 & 5 & 9 & 3 & 1 \\
 5 & 1 & 5 & 3 & 4 & 9 & 1 & 5 & 3 & 4 & 9 & 1 \\
 6 & 1 & 6 & 3 & 7 & 9 & 10 & 5 & 8 & 4 & 2 & 1 \\
 7 & 1 & 7 & 5 & 2 & 3 & 10 & 4 & 6 & 9 & 8 & 1 \\
 8 & 1 & 8 & 9 & 6 & 4 & 10 & 3 & 2 & 5 & 7 & 1 \\
 9 & 1 & 9 & 4 & 3 & 5 & 1 & 9 & 4 & 3 & 5 & 1 \\
 10 & 1 & 10 & 1 & 10 & 1 & 10 & 1 & 10 & 1 & 10 & 1
\end{array}
$

Property 1: for each row (except the first), the numbers eventually reach $1$ and then repeat.

The first generator, $0$, is degenerate. We usually exclude it from consideration. $\mathbb{Z}_p$ without $0$ is denoted $\mathbb{Z}^*_p$.

The next generator, $1$, only generates the number $1$.

The next generator, $2$, generates $\{1,2,4,8,5,10,9,7,3,6\}$, which if you sort turns out to be each 10 elements of $\mathbb Z_p^*$.

The next generator, $3$, generates $\{1,3,9,5,4\}$.

Generators $6,7,8$ generate the same group as $2$ (just in a different order). Generators $4,5,9$ generate the same group as $3$. Generator $10$ generates $\{1,10\}$.

There are a lot of properties contained in this chart but the relevant one is to consider the order (number of elements) in each possible group. We saw generators with $1$, $2$, $5$ and $10$ elements. These numbers are not coincidental. Property 2: they are the factors of $p-1$ which is $10$ when $p=11$. This holds true for any $p$ that is prime.

Each of these smaller groups are called "subgroups" of $\mathbb{Z}^*_p$. Take the group generated by $3$: $\{1,3,9,5,4\}$. If you take any element of this group and multiply it by any other element $\bmod 11$, the result will always be one of the elements of this group. This means it is closed under multiplication or a "multiplicative subgroup." Property 3: If $p$ is prime, each subgroup will be multiplicative.

For the security of Elgamal, we essentially want both $p$ and the order of the subgroup $q$ to be large primes. This means $q$ should divide $p-1$. In the example $p=11$ and $q=5$. It is typical to set $p=2q+1$ (that is $(p-1)=2q$). For things other than Elgamal (like DSA), we might use $p=\alpha q+1$ for some $\alpha$ larger than 2 (e.g., so that $p$ will be 1024 bits and $q$ will be 160 bits). For $p=2q+1$, there will be subgroups of order $p-1$, $q$, $2$ and $1$ (the factors of $p-1$). Most generators will either have order $p-1$ (generating $\mathbb{Z}^*_p$) or $q$ (generating a group we call $\mathbb{G}_q$).

How do we find $\mathbb{G}_q$?

Find a $p$ that will have $\mathbb{G}_q$: we choose a random prime $q$, compute $p=2q+1$, repeat until $p$ is prime.
Find a $g$ that will generate $\mathbb{G}_q$ and not $\mathbb{Z}^*_p$ (or any other subgroup). Since groups end with $1$ and then repeat, we test if $g^q \mod{p}$ is equal to $1$. If it is, we have very likely found a generator of $\mathbb{G}_q$ (and very unlikely found something of order $1$ or $2$; we can check that $g^2$ is not equal to $1$).
The description of the group is $\langle g,q,p \rangle$ (you could compute $q$ from $p$ to save space in the description).

One final thing: look at the column with $a=2$. These are the quadratic residues of $\mathbb{Z}_p^*$. Property 4: When $p=2q+1$, they are the exact same group as $\mathbb{G}_q$. This means, by using $\mathbb{G}_q$, you don't have to worry about an adversary testing if certain numbers are quadratic residues or not (see @Jalaj's answer).


Understanding the length extension attack

SHA-1 processes data by 512-bit blocks (64 bytes). For a given input message m, it first appends some bits (at least 65, at most 576) so that the total length is a multiple of 512. Let's call p the added bits (that's the padding). The padding bits depend only on the length of m (these bits include an encoding of that length, but they do not depend on the value of the bits).

The padded message m||p is then split into successive 512-bit blocks, which are processed one after the other. SHA-1 uses an internal compression function (that's the traditional term); it also has a running state consisting of five 32-bit words. The compression function takes as input two values of 160 and 512 bits, respectively, and outputs 160 bits. The processing goes like this:

The running state is initialized to a fixed, conventional value (which is given in the SHA-1 specification).
For each input block, the compression function is evaluated, with as input the current running state, and the input block; the output of the function is the new running state.
The running state after processing the last block is the hash output.

So now, the length-extension attack. Suppose that you give me a hash value h, computed over a message m that is unknown to me. I know the length of m, but not its contents. Since I know the length of m, I can easily compute the padding p that you used. Then I imagine a message m', which begins with m||p; that is, m' = m||p||z where z is a sequence of bits that I can choose arbitrarily. I will now proceed to computing the SHA-1 hash of m', even though I do not know part of it (it begins with m, which I do not know).

When SHA-1 is computed over m', the latter is first padded with p', which depends on the length of m' (which I know). The resulting stream is m||p||z||p'. Then, the 512-bit blocks are processed one by one. I cannot do it for the first blocks, since I do not know m. However, I can imagine myself doing it. At some point, I would reach precisely the end of the p string (since the length of m||p is a multiple of 512). What would be the value of the running state at that point ? Well, that's exactly the hash value h that you gave me ! Therefore, I can stop imagining; I can start my SHA-1 computation of SHA-1(m') right at that point, at the beginning of z, using your hash value h as value for the running state.

That's the core of it. I can use SHA-1(m) to compute SHA-1(m'), a message which begins with the contents of m, and I can do that without knowing m. This property of SHA-1 (which applies to other Merkle-Damgård hash functions such as MD5 or SHA-256) is not in contradiction with the usual hash function security features (resistance to collisions, preimages and second preimages), but it shows that SHA-1 is not a random oracle.

What good can it do to the attacker ? Well, consider the following (flawed) construction for a Message Authentication Code: for a given key k and data to protect d, compute SHA-1(k||d) as the MAC value. This scheme breaks in the presence of the length-extension attack: if I, as an attacker, sees a MAC for a message d, then I can compute the MAC for a message d' which extends d -- and I can do that without knowing k||d (so, in particular, without knowing the key). This allows me to forge messages with a valid MAC.

The length-extension attack is the reason why, when building a MAC out of a hash function, we need something a bit more convoluted, namely HMAC (which is safe against it).


Using AES-256 or Salsa20, Poly1305 or GCM authentication should come at no to little additional cost if you are already using HTTPS. If your server is somewhat modern bandwidth cost is about 16 bytes per HTTPS data packet sent and a few hundred bytes (at most) of RAM and rather minimal performance overhead compared to the actual business logic running on the server. You shouldn't worry about this part.

The asymmetric part is the interesting one. As a server you'll have to generate 1 signature for TLS per handshake (so at most one per request) and SPHINCS-256 costs 43M cycles on Intel Kaby Lake CPUs which is about 20ms on a 2GHz CPU. Signatures are 41kB though which means the RAM overhead is probably about ~40kB per handshake and the bandwidth overhead is about the same. Now if you deliver 2MB of JavaScript anyways this will hurt less than if you're only using a very simple static website... I haven't found data on XMSS so won't comment on that.

As for McEliece, performance data suggests it needs about 2M cycles for decryption, which happens once during a TLS handshake, so about 1ms on a 2GHz CPU. However, the public key is 1.3MB which is usually transferred once per handshake. The actual ciphertext is only $n$ bits and so only a bit larger than a comparable RSA encryption. You may want to note though that modern TLS 1.3 doesn't support key transport (ie public-key encryption for key agreement) anymore.

So, in total we get an overhead of about 45M CPU cycles and about 1.4MB per TLS handshake which is about 23ms on a modern server CPU.


Duration for attacking Two-Key Triple-DES Encryption using all RAM ever built?

The original article rightfully neglects the cost of DES computations (there are less than $2^{90}$) and everything except memory accesses to its Table 1 and Table 2. I go one step further: considering that Table 1 is initialized only once and then read-only, it could be in ROM, and I neglect all except the accesses to Table 2. The attack requires an expected $2^{88}$ random writes and as many random reads to Table 2, organized as $2^{25}\cdot 24$-bit words.

The cheap PC that I bought today (of May 2012) came with 4 GByte of DDR3 DRAM, as a single 64-bit-wide DIMM with 16 DRAM chips each $2^{28}\cdot 8$-bit, costing about \$1 per chip in volume. Bigger chips exists: my brand new 32-GByte server uses 64 chips each $2^{29}\cdot 8$-bit, and these are becoming increasingly common (though price per bit is still higher than for the mainstream $2^{28}\cdot 8$-bit chips).

Two mainstream $2^{28}\cdot 8$-bit chips hold one instance of Table 2, and one 124-bit word can be accessed as 8 consecutive 8-bit locations in each of the two chips simultaneously (consecutive accesses are like 15 times faster than random accesses). One $2^{29}\cdot 8$-bit chip would be slightly slower.

Assuming DDR3-1066 with 7-cycles latency (resp. DDR3-1333 with 9-cycles latency), 8 consecutive access require at least $(7\cdot 2+7)/1066\approx 0.020$ µs (resp. $(9\cdot 2+7)/1333\approx 0.019$ µs). This is a decimal order of magnitude less than considered in the original article. For each instance of Table 2, that is 0.5 GByte, we can perform at most $365\cdot 86400\cdot 10^6/0.019/2\approx 2^{49.6}$ read+write accesses per year to Table 2 using mainstream DRAM. Thus with $n$ GByte of mainstream DRAM, and unless I err somewhere, the expected duration is $2^{37.4}/n$ years.

Based on press releases of a serious reference, there are less than $2^{31}$ PCs around, and assuming that my cheap PC is representative, that's $2^{33}$ GByte. Another way to look at that is that each 0.25-GByte chip cost about \$$1$; and the DRAM revenues in 2011 is less than \$$2^{35}$, thus enough for $2^{33}$ GByte (but notice that most of the revenue is from chips that are not optimized for cost per bit). I'll guesstimate all the RAM ever built is equivalent to at most $2^{35}$ GByte of mainstream DRAM for the purpose of the attack.

Thus at the end of the day, my answer is: the attack in the original article, updated to use all the RAM chips ever built by mankind to mid 2012 at the maximum of their potential, has an expected duration of at least 5 years; or equivalently has odds at best 20% to succeed in one year.

Update: as noted by the authors of the original article, "the execution time is not particularly sensitive to the number of plaintext/ciphertext pairs $n$ (provided that $n$ is not too small) because as $n$ increases, the number of
operations required for the attack ($2^{120-\log_2 n}$) decreases, but memory requirements increase, and the number of machines that can be built with a fixed amount of money decreases". By the same argument, our required amount of RAM is not much changed if we get more known plaintext/ciphertext pairs.


Transforming a key into a seed with the most entropy

What you're looking for is called a key derivation function, and more specifically a key stretching function.

A key derivation function takes some variable-size material and turns it into a fixed-size key in a deterministic way, such that calling the same function on the same input yields the same key, and the original material cannot be reconstructed from the derived key except by trial and error.

A key stretching function is a particular kind of key derivation function that adds an element of slowness. This is necessary when the input consists of low-entropy data such as a password. The legitimate user only has to calculate the result once, but an attacker who attempts to guess the password has to make the calculation once per guess, so the slowness hurts the attacker more than the legitimate user. Note that the function must be designed so that each attempt requires a complete new calculation: there is no work that can be factored between computing f(Hello) and f(Hellp).

In addition to taking the password as input, you should pass a unique label (a string that doesn't need to be kept secret), so that if you ever want to derive a different key from that password, you can pick a different label. The label should typically include at least the name of your application, the user name or ID, and a version counter. The label also needs to be unique in that nobody else in the world uses the same label, because if the same label is reused many times, an attacker could pre-compute stretched keys for common passwords for that particular label.

A key stretching function is also known as a password-based key derivation function. These functions are also what is needed to hash passwords (the salt in password hashing corresponds to the label in key stretching). Common choices are PBKDF2, bcrypt and scrypt.

Note that the stretched key will not have more entropy than the password, only as much entropy as the password. That's the best you can hope for. Making the stretching operation slow reduces the impact of brute force attempts, but it cannot eliminate them. If you produce a 128-bit key from a password that's chosen from a 4000-word dictionary, the resulting key still only has 12 bits of entropy — less if the password wasn't chosen randomly.


RNG failing Restart Tests by NIST SP800-22?

The test that fails seems to be the one in 3.1.4 (Restart Tests) of NIST SP 800-90B (2nd Draft), specifically 3.1.4.3 (Sanity Check - Most Common Value in the Rows and Columns), failing at

  546     If F is greater than U, the test fails.

It can not be concluded that a generator that fails this has no entropy at all. It could well be that it has some imperfection, but still outputs a fair amount of entropy, leaving it perfectly usable to seed a CSPRNG.

CAUTION: this test requires 1000 samples obtained by re-starting the source and collecting 1000 symbols. If the question's 106 bytes are generated by the hardware RNG without restarting it, then the test is abused (if it had succeeded that would be meaningless). But such abuse can not be why the test fails.

It is a common event that Output of RNG fails some Randomness Rest. That can occur for any combination of four causes:

Goof in use of Randomness Rest (or collecting Output of RNG, but here that's unlikely given that other tests have passed); like, the format, size.. of Output of RNG is not as expected by Randomness Rest with the parameters used. The possibilities are endless. This is diagnosed as for 3.
Bad luck. All useful randomness tests are expected to have some rate of false alarm, with a certain probability: the P-value, which any good test documents. Here my reading is that it is 1%. Assuming this, and if possible, re-run Randomness Rest with the same parameters, and a few fresh Output of RNG. If the next two tests fail, we can exclude bad luck with high confidence. Otherwise (that is, if some succeed), we can suspect bad luck (or 1.), and we should use a form sequential analysis to decide. As a rough approximation: run another 997 tests, compute the number of tests out of 1000 that failed (which should be in the order of 10), reject bad luck with high confidence if that's more than 27 (still suspect some issue and investigate thoroughly if that's more than 15).
Goof in Randomness Test (either it's implementation, or definition if that's a draft or has otherwise has not stood intense scrutiny). The general method to detect this is to run randomness test against files generated by a simple (thus hopefully correct and acceptably fast) CSPRNG (one is given below). The proportion that fails should be about the documented P-value.
Defective RNG. Conclude this after having eliminated all the rest.

Here is a simple generator of pseudo-random sequence:

// Simple generator of cryptographically secure pseudorandom sequence.
// The 64-bit block cipher TEA is used in CFB mode to encipher
// plaintext consisting of the block number.
#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>

// For a different sequence, change these arbitrary 32-bit constants,
// used as key for the TEA block cipher.
// Note: in David Wheeler and Roger Needham's TEA, each key has 3 other
// equivalents, as the high-order bits of K0/K1 and K2/K3 cancel out.
#define K0 0x7638d4f2
#define K1 0xabe32749
#define K2 0x56b81d0e
#define K3 0x4ed51d62

// output size, multiple of 8
#define OUTPUT_SIZE 1000000

int main(void) {
    uint32_t j, n, s, y=0, z=0;
    for( j=0; j < (OUTPUT_SIZE+7)>>3; ++j ) {
        s = 0;
        n = 32; do { // 32 pairs of rounds
            s += 0x9e3779b9;
            y += ((z<<4)+K0) ^ (z+s) ^ ((z>>5)+K1);
            z += ((y<<4)+K2) ^ (y+s) ^ ((y>>5)+K3);
        } while (--n);
        z ^= j; // CFB; makes short cycles virtually impossible
        // portably format in lowercase hexadecimal
        printf("%08"PRIx32"%08"PRIx32, y, z);
    }
    return 0;
}

// Generates one million octets expressed as two million characters
// in lower-case hexadecimal on standard output; when expressed in
// ASCII as two million octets, their hash per SHA-256 is
// d5b727ef6a9177c897b68085d60a7660f6f6b1dbf09cb7e91fe59da3a66d4e2d


Why do we need to go through multiple cycles in block cipher

First of all, I wouldn't rely on that book for information about modern cryptography.  It might be a fine reference for networking in general, however based on the example they gave, it would appear that they really don't know their crypto.  The example cipher they gave feels like something from the '90s.

Modern block ciphers use $k=128$; the issue with $k=32$ is that you tend to leak information about the plaintext after encrypting a few gigabytes with the same key; with modern networks, you can hit a few gigabytes easily.  In addition, key dependent sboxes have gone out of fashion; they are a bit expensive in hardware, they tend to leak timing data in software (due to caching), and the sboxes are sometimes not particularly strong against differential or linear cryptanalysis.

As for your question:

  Why do we need to process the text through n such cycles?

Consider the case where $n=1$, and you have two different plaintexts that differ in a single bit.  Then, if you look at the two parallel encryptions, the inputs for seven of the sboxes are precisely the same (because they only depend on inputs that have not changed), and so only one sbox (say, $T_0$) has its output changed.  That sbox has 8 output bits, and so when you go through the 64-bit scrambler, then you have 56 output bits that would always be the same, and 8 that are potentially changed.  This is far short of 'any input bit can potentially affect any output bit'.

There are more sophisticated things we can do for larger $n$; this simple reasoning shows that the $n=1$ case just doesn't cut it...


AES-CTR authentication salt+HMAC(ciphertext) OR HMAC(salt+ciphertext)

None of them. PBKDF2 should not be used multiple times or for large output. I would recommend to use an additional KBKDF such as HKDF.

function encrypt(msg, passphrase, iterationCount) {
    sessionKey, salt = newPBKDF2(passphrase, iterationCount)
    encryptionKey = HKDF(sessionKey, 'ENC')
    encryptionIV = HKDF(sessionKey, 'IV')
    hmacKey = HKDF(sessionKey, 'MAC')
    ciphertext = aesCTR(msg, encryptionKey, encryptionIV)
    authTag = generateHMAC(ciphertext, hmacKey)
    return salt + ciphertext + authTag
}

Iteration count should be set to high for passphrases. A good passphrase is still required.

As encryption already should be randomised to achieve CPA security there is no need for a salt input to HMAC. Note that replay attacks may still work if you reuse the passphrase, of course. You need to take care of that in the protocol definition.


Given a collision in a MAC function, is it possible to work out how the MAC function works and generate valid MAC values for any message?

No you would generally not be able to do this. If you find a collision without a key then it's just an indication that the output size is too small. Quite often the MAC depends on a block cipher or hash function. The latter is one-way by definition, the former is one-way unless you know the key.
It's of course a different proposition if you find a MAC collision because you found a weakness in the algorithm or the establishment of the secret key. If an attacker found a weakness it is very likely that the attacker already knows the algorithm. And yeah, if an attacker know the key the game is over. Finding another collision might still be tricky if the output size is large enough, depending on the algorithm used.
"could you find valid MAC values for a message without needing to know how it works". No, with the possible exception that length extension attacks may work, e.g. for CBC-MAC and CMAC. This would require the full output of the calculation though, so chances are that you will not find a collision for a cipher with a large enough block size (e.g. AES instead of DES).


How to find g in Factoring-Based Trapdoor Hash Function

There are several different ways to do this:

The most obvious way to do this, if you know $p$ and $q$, is to select random values $r$ relatively prime to $n$, and determine their order; that is, verify that none of $r^{\lambda(x)/(p-1)}, r^{\lambda(x)/(q-1)}, r^{\lambda(x)/2}$ are 1.  Since approximately three quarters of possible $r$ values do have order $\lambda(n)$, this is efficient (if not as efficient as the methods I show below).

However, this doesn't work if either you yourself don't know the factorization of $n$, or you need to demonstrate to someone else know doesn't know.

$t$ has order $\lambda(n)$ if $t, t-1, t+1$ are all relatively prime to $n$, and if $t$ is either a quadratic nonresidue mod p, or a quadratic nonresidue mod q (or both).

The easiest way to select such a $t$ is to go with the 'both' option; select a random $r$ and set $t = -r^2 \bmod n$ (and verify that $t+1$ is relatively prime to $n$); $r^2$ is a quadratic residue mod p (obviously), and as $p \equiv 3 \pmod 4$, if $r^2$ is a quadratic residue, $-r^2$ must be a quadratic nonresidue (and similarly for $q$).  And, if we select $r$ to be a nothing-up-my-sleeve number, so is $t$.  The only downside is that this process will generate only a third of the potential values.
Another approach is to select random $t$ values (where $t-1, t+1$ are relatively prime to $n$), and compute the [Jacobi symbol][1] to $t$ with respect to $n$; if it is -1, then we know that $t$ is a quadratic residue to one of $p, q$, and a quadratic nonresidue to the other; we don't know which, but in this case, we don't care.  Approximately half of the possible $t$ values will have a -1 Jacobi value and so this is also reasonably efficent (if a bit more work, in part because libraries that can compute the Jacobi symbol are a tad more rare).  And, this method will generate the two-thirds potential values that the previous method does not.

And, if it is critical that we generate a value which is strictly uniform (even if you don't know $p$ and $q$), you can use the $-r^2$ method with probability 1/3, and the Jacobi method with probability 2/3; that turns out to generate all possible values with uniform probability.

[1] https://en.wikipedia.org/wiki/Jacobi_symbol


Is there any function that does not suffers birthday problem?

If $f:\{0,1\}^m\rightarrow \{0,1\}^n$ with $n\geq m,$ then of course there are, the set of one-to-one functions, but such a function is not a cryptographic hash function, since it lacks the compression property. If $n<m,$ (or more generally if $|X|>|Y|$ for $f:X\rightarrow Y$), collisions will happen.


Proving that two points on elliptic curve are within range

The proof showing that,  given $G$ and $x \cdot G$ and a range $[A,B]$, $x$ is in the range $[A,B]$ is known as the range proof.
In your case, we can convert your statement as the range proof as, given $G$ and $H = xG - yG$, showing $x-y$ is in the range $[-z,z]$.

For example, the following papers (and a lot of papers) proposed efficient range proofs.

Jan Camenisch, Rafik Chaabouni, and abhi shelat: Efficient Protocols for Set Membership and Range Proofs (ASIACRYPT 2008)
Benedikt Bünz and Jonathan Bootle and Dan Boneh and Andrew Poelstra and Pieter Wuille and Greg Maxwell: Bulletproofs: Short Proofs for Confidential Transactions and More (IEEE S&P 2018)


Is multiplicative secret sharing secure?

Assuming that $p$ is prime, then you are in a cyclic group. Consequently, this is identical to considering the shares $s_i$ as "exponents" of a generator $g$ of $Z_p^*$.

Now we can write: $s_1 = g^{s'_1}, \ldots,s_{k}=g^{s'_{k}}$ and $s=\prod_{i=1}^{k} s_i$

Or we can view this as: $s = g^{\sum_{i=1}^{k} s'_i}$.

Consequently it looks like a perfect (= information theoretically secure) additive secret sharing scheme "in the exponent" to me.


Well, the first thing comes to mind is "what if your 'read-only location' isn't quite as read-only as you had hoped; if someone could modify your $f(i) \oplus k_i$ share, could they modify the reconstructed shared secret in a controlled way.

In your first example, I believe they could.  Let us assume that we are doing Shamir's Secret Sharing over the field $GF(2^k)$; let us further assume that the attacker has $N-1$ shares (where $N$ is the number of shares we need to reconstruct the secret).  Which his $N-1$ shares, he can reconstruct that, when you add in your share $f(i)$, the reconstructed secret will be $s = c \times f(i) + d$, for some values $c, d$ he can compute (and $\times$ and $+$ are over $GF(2^k)$.

Now, $c \neq 0$, and so this doesn't give him any information about what the secret is (given that he doesn't know your share).  However, if he wants to modify the secret, say, add $t$ to is, what he can do is modify your encoded share on the read-only location, replacing $(i, f(i) \oplus k_i)$ with $(i, f(i) \oplus k_i \oplus (t \times c^{-1}))$.

Then, when you reconstruct the secret, using his N-1 shares, and your modified share, you will decode your share as $F(i) + (t \times c^{-1})$ (remember, in $GF(2^k)$, addition and exclusive-or are the same operation); then, when you combine this decrypted share with his, you're come up with $c(F(i) + tc^{-1})+d = cF(i)+d + t = s+t$, resulting in the modified shared secret that the attacker selected.

On the other hand, by using AES to encrypt the share, the attacker cannot do any such tricks.  He can modify the share so that the shared secret becomes something else, however, he has no control over what that something else might be.


Validating that a hash is over a specific value for two hashes with additional (known but different) input

This is not probably what you had in mind; but this is easy to achieve with a slight expansion.

Let us assume we have a private, public pair, with private key $P$, and public $K$. We basically consider $P$ to your $M$, and take $K$ to be part of the public knowledge of the verification of the hash.

Then $H(M+X)$ is defined to be $\textrm{Sign}(P,\textrm{Hash}(X))$ for any desired hash algorithm. Let $C_i=\textrm{Sign}(P, \textrm{Hash}(T_i))$. Given the public $K$, one can then verify the legality of each $C_i$ (and of course, for publicly known hash-function, one can also calculate the hash of $T_i$ directly).


Problem with anonymously merging information from distributed sources

If you have a secret key (256-bits) shared between the two systems that see the entity identifiers, you can use HMAC-SHA256 to map entity identifiers to a random string.  Under the assumption that HMAC-SHA256 security is good (which is widely believed to be a reasonable one), this is just as secure as having generated a truly random mapping, but requires only communicating 256-bits instead of the full mapping.  If there are multiple rounds of this process of aggregation, you could use a different secret key or a different (public) nonce if it is not necessary for the aggregating system to know which entities are the same between rounds.

However, it sounds like the information associated with each entity will not be encrypted (since it needs to be processed in some fashion by the third system), and you therefore have to very carefully consider whether it may be possible to de-anonymize the entities based on their associated information.  There have been many cases of researchers de-anonymizing (http://en.wikipedia.org/wiki/De-anonymization) supposedly annoymized datasets.


Vulnerability of low value generated key

The chance that such a key is generated randomly is negligibly low. These 512 bits of security are for both the higher order and lower order bits. The chance of generating such a value is one in $2^{512}$ (each time you try, assuming that each value in the 1024 bit number is about equally valid). That means you can try forever before getting such a low value.

Just try and run your random bit generator and wait for it to generate 512 bits of zeros in succession. That's similar as guessing a 512 bit key. It is simply not going to happen. No such key exists or will exist if it was generated randomly.

As it is impossible to create such a key at random, there is very little reason searching for such a key either, or to limit the value to a minimum. That kind of effort is better put into making sure that the random bit generator is working correctly and to make sure that the key pair generation process isn't erroneous in itself.


can we use two different hash functions in single hmac?

This is exactly what was done in early versions of HMAC. Of course, there would be no reason to do this with an already broken hash function. Note that MD5 is completely broken and SHA1 is close to, so neither of these are great choices.


Extended Canetti-Krawczyk - Clean Session Definition

The first condition appears to state, that the adversary $\mathcal M$ would not be allowed to perform a man-in-the-middle attack on the test session between $\mathcal A$ and $\mathcal B$.

This is not correct. The eCK model does allow MitM attacks.
For some more background on formal AKE models see this question. To quickly recap, in an AKE model (including the eCK model) the adversary is assumed to control the entire network and can re-route, change, and drop message as it sees fit. In particular, this means that the adversary can do MitM attacks almost by definition. Then, to measure the adversary's ability to break the protocol, the adversary is given a Test session (a running instance of the protocol at some party, say $\mathcal A$) for which it is asked to distinguish its real session key from a random key. If the adversary can't do this, then we say that the protocol is secure. Notice in particular that the adversary can pick a Test session for which the adversary itself created all the messages it sent to the Test session (thus modelling a MitM attack). This is also true for the eCK model.
However, AKE models (including eCK) usually go beyond just MitM attacks, and also allow the adversary to obtain many of the secret values in the system too. This can include session keys derived by sessions other than the Test session itself, long-term keys held by the parties, and also the full internal randomness used by the sessions (the eCK model allows all three of these). However, once we start allowing the adversary these additional powers, certain unavoidable attacks start to become possible. It is this that the quote you refer to is about. In particular

$\mathcal A$ or $\mathcal B$ is an adversary-controlled party. This means in particular that $\mathcal B$ chooses or reveals both the long-term and ephemeral secret keys for the party and performs all communications and computations on behalf of the party.

deals with the following attack. Suppose the adversary picks the Test session to be at party $\mathcal B$ (communicating with a session at party $\mathcal A$). Now, using the powers granted to it in the eCK model, the adversary obtains the long-term key of party $\mathcal A$ as well as all the internal randomness used by the the running instance at $\mathcal A$. At this point the adversary has all the secret values that the honest session at $\mathcal A$ would use when communicating with $\mathcal B$, hence it can trivially impersonate $\mathcal A$ towards $\mathcal B$ allowing it to compute the same session key as the Test session (at $\mathcal B$). Thus it can trivially break the protocol. However, note that this attack is unavoidable given the powers the adversary is given. Thus, to make the eCK model meaningful, these trivial attacks need to be disallowed, and this what the restriction above does.
In summary, the eCK model allows MitM attacks, but since it also allows the adversary additional powers (such as obtaining certain secret values in the system), it must also impose some constraints on the adversary in order to account for the possibility of trivial attacks made possible by these powers.


Show that CPA-security implies security against plaintext recovery

Your solution is almost correct. Just don't forget to consider the following two cases: 1) $m_0$ and $m_1$ may be the same, then $A$ will have to guess the secret bit $b$ blindly; 2) $B$ may return the other message, e.g., $B$ happens to return $m_1$ when given $E_k(m_0)$, then $A$'s output will be wrong. Note that 1) and 2) occur with only negligible probabilities.