In order to answer this, you need to be sure to understand how garbled circuits actually work. I'll try to explain this from top to bottom:

The protocol

Let Alice and Bob be willing to compute securely a function $f(x,y)$ (in your example, it would be $f(x,y)=\min(x,y)$) while keeping their respective inputs $x$ and $y$ secret.

In order to do so, they will first model the function $f$ as a Boolean circuit, which is possible since there exists a Boolean circuit $C$ that calculates the output of $f$ for any function $f$ with fixed size inputs [1].
However, the way such a modeling is performed can depend on the function and will not be further discussed here.

Then Alice will garble the Boolean circuit:
for each wire $W_i$ of the circuit $C$, she randomly chooses two secret values $w^0_i, w^1_i$, where $w^j_i$ is the garbled value of the value $j\in \{0,1\}$ of the wire $W_i$.
Note that $w_i^j$ cannot reveal $j$ in itself, so Alice has to keep track of $i$ and $j$.
This has to be done for each and every input and output wires of every logical gates in the circuit, excepted for the circuit output gates which can be left ungarbled.

Then Alice also has to construct a garbled truth table (GTT) $T_i$ for each of the gates $G_i$ in $C$.
Those tables have to be so that given garbled values along its set of input wires, $T_i$ will allow to recover the garbled output of this $G_i$ and no other information.
This is achieved through encryption of the output values.
I will detail further the garbling of gates below.

Afterwards, Alice can translate each bit of her input into its corresponding garbled values on the circuit's input wires.
And then she can send the—now garbled—circuit where each gate is replaced by its GTT to Bob with her encrypted input.

After Bob received the garbled circuit, since all input wires are encrypted and only Alice knows the mapping of the encrypted values and the real bits, Bob need to perform an oblivious transfer (I let you google that one, since it's not useful to answer your question) with Alice for each of his input bits, so that Alice can inform him of what encrypted values correspond to his inputs bits with knowing what are his actual input bits.

So it means that for each input wire, Bob will choose one amongst the two random strings $w_i^0, w_i^1$ which correspond respectively to $0$ and $1$, but without knowing the content of the string he does not choose.
And thanks to the properties of the oblivious transfer Alice cannot learn Bob's input.

Then Bob has all the needed values to compute the output of the circuit as I will discuss it below. Once he has done so, he can tell the output values to Alice.
So Bob was able to obtain the output of $f$ without revealing his input, nor knowing Alice's input, this means that Alice and Bob successfully simulated a trusted third party and performed thus secure MPC!

Garbling Logical Gates

The notion of garbling logical gates and their truth table is crucial.
Without loss of generality, I will only consider logical gates with two input wires and one output wire.
As I quickly explained above, for a given gate $G\in C$ and its input wires $W_0,W_1$ and its output wire $W$, Alice had to choose six different random strings, $w_0^0, w_0^1,w_1^0,w_1^1,w^0,w^1$ she assigned to each values of the wires in a one-to-one mapping, where $w_i^j$ represents the random string assigned to the value $j$ of the wire $W_i$.

Then in order to garble the truth table of $G$ in a way which would not reveal any information given two input values $w_0,w_1$ excepted for its output value $w$, not even the type of the gate, Alice can encrypt the output values $w^0,w^1$ using the garbled input values as keys, using a given symmetric encryption scheme $\mathbb{E}$.
I use the notation $\mathbb{E}_{k_0,k_1}(x)=\mathbb{E}_{k_0}(\mathbb{E}_{k_1}(x))$ to denote encrypting twice with two given keys $k_0,k_1$.
As an example, let us encrypt the truth table of the AND gate from Figure 1:
$$\begin{array}{c|c|c||c}
W_0 & W_1 & W & \text{Garbled value} \\ \hline
        w_0^0 & w_1^0 & w^0 & \mathbb{E}_{w_0^0,w_1^0}(w^0) \\
        w_0^0 & w_1^1 & w^0 & \mathbb{E}_{w_0^0,w_1^1}(w^0) \\
        w_0^1 & w_1^0 & w^0 & \mathbb{E}_{w_0^1,w_1^0}(w^0)\\
        w_0^1 & w_1^1 & w^1 & \mathbb{E}_{w_0^1,w_1^1}(w^1) \\
\end{array}$$

The GTT $T$ of the gate $G$ is then simply the set $\left\lbrace\mathbb{E}_{w_0^j,w_1^k}(w^{G(j,k)}) \mid j,k \in  \left\lbrace0,1\right\rbrace \right\rbrace$ of the garbled values, where $G(j,k)$ corresponds to the output of the gate $G$ under inputs $(j,k)$.

Evaluation of a garbled circuit

Once Bob has received the garbled circuit $C$ from Alice and obtained the garbled values of his input through multiple oblivious transfers, he can evaluate the circuit.

It is important to realize that a garbled circuit differs from a regular Boolean circuit.
In a Boolean circuit, semantic and syntax are basically the same: we are assigning to each wire two possible semantic values, namely True or False, which we will syntactically denote as a signal with 1 or 0 values respectively.

Those signals were public and the same signals were associated with every wire and anybody could tell from the signal what semantic value it held.
This changes in a garbled circuit, since the semantic values of each signal—excepted for the circuit's output ones—are now secret and the signals are now varying from one wire to another wire.

Thus, in order to evaluate the circuit, for each gates $G_i$ of the circuit, Bob can try and decrypt the values in the associated truth table $T_i$ using the gate's input values as keys. One of the entries in $T_i$ will then decrypt into the output of the gate.
Hence it seems necessary to have an oracle to confirm successful decryption of the entries of $T_i$, however a trick I'll detail right now called permute-and-point first used in [2] and then clearly explained in Phillip Rogoway's dissertation [3], allows to decide which entry of the GTT is to be decrypted given the garbled inputs, enabling faster computations and still preventing the evaluator to deduce anything from the order of the truth table's entries.

Permute-and-point

This trick works as follows: for each input and output wires $W_i$, Alice will concatenate a random bit $a\in \{0,1\}$ at the end of its garbled value $w_i^0$ and concatenate its inverse $b=\overline{a}=1-a$ at the end of $w_i^1$. So it allows to associate each of the 4 permutations of 2 bits to one of the entry of the GTT, without having any correlation between the bits and the values of the ungarbled truth table. So Alice can simply order the GTT according to the natural ordering and give it to Bob which will then be able to deduce which entry he should decrypt on a given input.
To obtain a nice representation of this trick, those bits can be seen as a pair of colors, as I depict them in Figure 2, in which we see how the truth table is modified to take into account this method.

Those modifications allow Bob to simply decrypt the entry whose index corresponds with the colors associated to its input wires and thus to obtain the output wire's value and its color, allowing him to further evaluate the circuit.

Example evaluation

Let us see how one could evaluate the garbled circuit represented in Figure 3 using the permute-and-point method we discussed above.
Let us assume that the semantic input values of $(W_1,W_2,W_3,W_4)$ are $(0,0,1,0)$, which means that the actual garbled input is $({\color{green}\bullet}{}w_1^0,{\color{red}\bullet}{}w_2^0,{\color{red}\bullet}{}w_3^1,{\color{green}\bullet}{}w_4^0)$ where the $w_j^i$ are the random values that Alice chose when she garbled the circuit, as seen above.
Let us also assume that Alice already provided her garbled input, say $(W_1,W_3)$, and that Bob already obtained his garbled input $(W_2,W_4)$ from Alice through two applications of oblivious transfer as described in the protocol part.

So Bob will begin by evaluating first the AND gate using the input $({\color{green}\bullet}{}w_1^0,{\color{red}\bullet}{}w_2^0)$, since it has the colors $ \color{green}\bullet\color{red}\bullet$
he will try and decrypt the third entry of the GGT of the AND gate, which works and thus provide him with the garbled value ${\color{green}\bullet}{}w_5^0$.

Then he can continue his evaluation with the second gate, which is the OR gate. He looks at its input $({\color{red}\bullet}{}w_3^1,{\color{green}\bullet}{}w_4^0)$ and try to decrypt the entry corresponding to $ \color{red}\bullet\color{green}\bullet$ with the keys $(w_3^1,w_4^0)$, it decrypt into the garbled value ${\color{green}\bullet}{}w_6^1$.

He can now decrypt the final XOR gate using the computed input $({\color{green}\bullet}{}w_5^0,{\color{green}\bullet}{}w_6^1)$, thus decrypting the $\color{green}\bullet\color{green}\bullet$ entry which provide him with the final result: "1".

And Bob does not know what was Alice's input, he just knows the final output "1" and the randomly generated strings $w_1^0,w_2^0,w_3^1,w_4^0,w_5^0,w_6^1$. He can still for example deduce from the circuit that the semantic values of $w_5^0$ and $w_6^1$ are opposed, however it does not allow him to reverse the garbled circuit up to Alice's input values. There are circuits where no privacy is assured, like for example a circuit computing the sum of the inputs, however in this example case, Bob—knowing his semantic input values—can simply restrict Alice's inputs to a subset of the possible inputs but cannot uniquely determine the actual Alice's input values.

Now, answering your question

You must model the function as a boolean circuit using fairly basic gates.
You must garble that boolean circuit.
You can then do the drawings.

Now, in the linked question the trickiest part is to "show that the simulated circuits are indistinguishable from the actual one", but since it is a really small circuit you can simply show it behaves correctly on all inputs.
If you want to do it more formally, you can see the proof the the Yao protocol by Lindell &  Pinkas, more specifically their claim 6.

Hopefully this should address all the problems you may have with garbled circuits... (Except if you want to dig into how to get better performance, since there are many more tricks to speed things up.)

Modeling the min function

The fastest way to model a boolean function is to draw its truth table, so in your case, you have 4 bits inputs, with the numbers $a$ and $b$ being 2-bits numbers $a_1a_2$ and $b_1b_2$ respectively, and you want as output the minimum $c$ of $a$ and $b$, where $c$ is constituted of two bits: $c_1c_2$.

So you can draw the truth table:

$$\begin{array}{c|c||c|c||c|c}
 a_1 & a_2 & b_1 & b_2 & c_1 & c_2 \\ \hline
 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 1 & 0 & 0 \\
 0 & 0 & 1 & 0 & 0 & 0 \\
 0 & 0 & 1 & 1 & 0 & 0 \\
 0 & 1 & 0 & 0 & 0 & 0 \\
 0 & 1 & 0 & 1 & 0 & 1 \\
 0 & 1 & 1 & 0 & 0 & 1 \\
 0 & 1 & 1 & 1 & 0 & 1 \\
 1 & 0 & 0 & 0 & 0 & 0 \\
 1 & 0 & 0 & 1 & 0 & 1 \\
 1 & 0 & 1 & 0 & 1 & 0 \\
 1 & 0 & 1 & 1 & 1 & 0 \\
 1 & 1 & 0 & 0 & 0 & 0 \\
 1 & 1 & 0 & 1 & 0 & 1 \\
 1 & 1 & 1 & 0 & 1 & 0 \\
 1 & 1 & 1 & 1 & 1 & 1 \\
\end{array}$$
And you can model your boolean circuit by taking the true values in the results and represent them as being a boolean expression:

For $c_1$:
    $$
\begin{array}{c|c||c|c||c|c}
 a_1 & a_2 & b_1 & b_2 & c_1 & {bool. expr.} \\ \hline
 1 & 0 & 1 & 0 & 1 & a_1 \land \overline{a_2}\land b_1 \land \overline{b_2}  \\
 1 & 0 & 1 & 1 & 1 & a_1 \land \overline{a_2}\land b_1 \land {b_2} \\
 1 & 1 & 1 & 0 & 1 & a_1 \land {a_2}\land b_1 \land \overline{b_2} \\
 1 & 1 & 1 & 1 & 1 & a_1 \land {a_2}\land b_1 \land {b_2} \\
\end{array}
$$
And for $c_2$:
    $$
\begin{array}{c|c||c|c||c|c}
 a_1 & a_2 & b_1 & b_2 & c_2 & {bool. expr.}  \\ \hline
 0 & 1 & 0 & 1 & 1 & \overline{a_1} \land {a_2}\land \overline{b_1} \land {b_2}\\
 0 & 1 & 1 & 0 & 1 & \overline{a_1} \land {a_2}\land b_1 \land \overline{b_2}\\
 0 & 1 & 1 & 1 & 1 & \overline{a_1} \land {a_2}\land b_1 \land {b_2}\\
 1 & 0 & 0 & 1 & 1 & a_1 \land \overline{a_2}\land \overline{b_1} \land {b_2}\\
 1 & 1 & 0 & 1 & 1 & a_1 \land {a_2}\land \overline{b_1} \land {b_2}\\
 1 & 1 & 1 & 1 & 1 & a_1 \land {a_2}\land b_1 \land {b_2}\\
\end{array}
$$

Now, you can express $c_1$ and $c_2$ as the OR of all their respective boolean expression, this method is called the boolean Sum-of-Product:
$$
\begin{aligned}
c_1= (a_1\land \overline{a_2}\land b_1 \land \overline{b_2})
\lor(a_1\land \overline{a_2}\land b_1 \land {b_2}) \\
\lor(a_1\land {a_2}\land b_1 \land \overline{b_2})
\lor(a_1\land {a_2}\land b_1 \land {b_2})
\end{aligned}
$$

And for $c_2$:
$$
\begin{aligned}
 c_2 = (\overline{a_1} \land {a_2}\land \overline{b_1} \land {b_2})
\lor(\overline{a_1} \land {a_2}\land b_1 \land \overline{b_2})\\
\lor(\overline{a_1} \land {a_2}\land b_1 \land {b_2})
\lor(a_1 \land \overline{a_2}\land \overline{b_1} \land {b_2})\\
\lor(a_1 \land {a_2}\land \overline{b_1} \land {b_2})
\lor(a_1 \land {a_2}\land b_1 \land {b_2})\\
\end{aligned}
$$

And you have a possible circuit for your function.

Now those expression are really ugly and you may want to simplify them, it is possible to convert them into nicer forms, like DNF (this is where Karnaugh maps can help). But I won't cover this topic.

For instance, $c_1$ can be rewritten as: $c_1=a_1 \land b_1$ and $c_2$ can be rewritten as:
$c_2 = (a_1 \land \overline{b_1} \land b_2) \lor (\overline{a_1} \land a_2 \land b_1) \lor (a_2 \land b_2)$

I haven't much resources to refer you to there, but a quick search led me to this page and that one, which even has a graphical representation of the circuits.

References

[1] Goldwasser, S., Micali, S., & Wigderson, A. (1987). How to play any mental game, or a completeness theorem for protocols with an honest majority. In Proc. of the Nienteenth Annual ACM STOC (Vol. 87, pp. 218-229). [PDF]

[2] Beaver, D., Micali, S., & Rogaway, P. (1990, April). The round complexity of secure protocols. In Proceedings of the twenty-second annual ACM symposium on Theory of computing (pp. 503-513). ACM. [PDF]

[3] Rogaway, P., & Micali, S. (1991). The round complexity of secure protocols (Doctoral dissertation, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science). [PDF]


The shorter the hash value the less effort for the attacker to brute force it. If the output is 16bytes then the attacker must spend $2^{128/2}$ "time" to find a collision. If it was 8bytes it would need $2^{64/2}$


How to compare one time pad security and efficiency with AES?

Answer 1:  If you are going to use a "one time pad", then $c1$ must be exactly the same size as $m$, so $c1$ must be 32 bits.  (Note:  Using a PRF and evaluating with the input of 0 is not a one-time pad.  It might be equivalent if you change $k_i$ every time, but then why bother with the PRF when you could use $k_i$ directly?)

Answer 2:  Since you specific it as a PRP (pseudorandom permutation), $c2$ must be 32-bits.  With a permutation, the size of the input matches the size of the output.  A PRP pseudorandomly maps each element of the possible input set to a single item in the output set.  So as with the first, $m$ and $c$ must be exactly the same size.

Answer 3: There isn't sufficient information about the rest of the system or usage to really comment on their security with the exception to say:  trying to make a "one-time pad" from other function almost always fails and anything that has only a 32-bit input can probably be trivially brute forced.


I think the notion you're secretly after is Verifiable Delay Functions.

They don't depend on a verifiable condition, they provide a way to ensure that no-one can compute them in a short time (even by massive parallelization).
They can be used during a synchronization step controlled by a smart contract.


What is the 'Version Incompatibility" Problem in TLS 1.1/1.2 and 1.0?

The problem is not as simple as just the version number, though according to Eric Rescorla, there are some of those. In my experience, most problematic implementations have a problem with ClientHello extensions, which were formally defined after TLS 1.0 was a standard. As such, some servers are hardcoded to expect ClientHello and no more data, which means they will choke on any TLS extensions being sent to them.

Since SSLv3 didn't have the notion of extensions, none of the implementations that I'm aware of send any extensions in their ClientHello. This causes usage of SSLv3 to succeed even against servers that fail on receiving TLS extensions. As such, because of browsers' desire to connect to any server, they try to connect with TLS and extensions and if that fails, they will fallback and try with SSLv3.

For browsers that support TLS 1.1/1.2, it is even more fallback logic, as it maybe that the server didn't accept 1.1, but accepts 1.0 just fine, so you have multiple cascading fallbacks.

So to sum it up - version number and TLS extensions handling are the two most common problems and yes, the above statements are all referring to these types of problems and the browser behavior.


Adding and multiplication in jacobian coordinates

Well, you can start with affine coordinate addition formulas, and simplify things as you go along. Here's an example for point doubling:

$$
\begin{eqnarray*}
\lambda &=& \frac{3(X/Z^2)^2 + A}{2(Y/Z^3)} \\
&=& \frac{3X^2 + AZ^4}{2YZ} \\
X_3 &=& \lambda^2 - 2X = \frac{9X^4 + 6AX^2Z^4 - 8XY^2Z^2 + A^2Z^8 }{4Y^2Z^2} \\
Y_3 &=& \lambda(X - X_3) - Y \\ &=& \frac{-27X^6 - 27AX^4Z^4 +36X^3Y^2Z^2 -9A^2X^2Z^8 +12AXY^2Z^6-8Y^4Z^3- A^3Z^{12}}{8Y^3Z^3} \\
Z_3 &=& 2YZ
\end{eqnarray*}
$$

Notice that $4Y^2Z^2 = (2YZ)^2$, and $8Y^3Z^3 = (2YZ)^3$, thus $Z_3 = 2YZ$. There are a lot of common terms here, so it's a relatively short computation once you combine those. The EFD website has spared us all much trouble by maintaining a record of most of the popular coordinates and worked out formulas.


Blowfish-448 Secure Key Generation Algorithm

I am using blowfish-448, until now the keys have been generated using
  a crypto random number generator full filling the 448bits vector.

This is fine assuming your cryptographic (pseudo-) random number generator is actually good. If this wasn't a valid strategy, this would have produced strong warnings about using Blowfish already.

  I read about exploit in case of weak keys and reflection keys attack.

Yes, there exist weak keys for blowfish, but hitting them when utilizing the full space has negligible probability (also it appears that they don't even break the full blowfish but rather a larger part than with normal keys).

  Mine concern is if the generation approach we are using is secure or
  if does exist a more secure way.

Yes, you really should migrate off Blowfish to AES. It will (most likely) be faster and likely more secure and you won't suffer from small-block attacks like Sweet32.


Are there any algorithms for which generating any zero-knowledge proofs is not practical?

The following is a fairly "boring" example, but likely works (I'll point out the specific assumption I'm making later). If you also feel its boring, it might help you refine your question so that the answer is more interesting.

Say you have some encryption scheme with security parameter $n$ (We may as well think of $n$-bit RSA, any example works). Say that encryption takes $T_E = O(f(n))$ time for some function $f(n)$.
Now consider some ZK proof of the statement you're interested in. Say that it takes $T_P = O(g(n))$ time to prove the statement, where the complexity depends on the security parameter chosen for encryption.

I'm going to assume that encryption is easier than proof generation, or formally $f(n) = o(g(n))$.
This seems fairly natural, but I'm not familiar enough with the particulars to know if it holds for all pairs of encryption schemes/proofs (although if it doesn't, one gets proofs 'for free' asymptotically for a particular encryption scheme, which seems odd).

We can then consider introducing another parameter $k$ (which is small compared to $n$), and look at the encryption scheme/proof system with security parameter $kn$.
I claim that the following two things should hold:

If $k$ is small enough, encryption with security parameter $kn$ will still be feasible on the devices you're imagining
As $f(n) = o(g(n))$, asymptotically proof generation will become infeasible before encryption does (as the complexity of proof generation grows "strictly faster").

So if we take $k$ large enough, we expect both encryption and proof generation to become infeasible. But as the asymptotic complexity of the two differ, we expect proof generation to grow infeasible first, so there should be some "intermediate values" of $k$ such that one can still encrypt, but cannot generate proofs.


How to improve long-term duration of standard checksum for authenticity purposes?

In this case, a simple change will improve robustness: include hashes produced by multiple functions. (This can be counterproductive if the hashed data is not fully public, because one hash being inverted would reveal the data even if the other hashes had resisted. But here the data is public so there's no loss of security in adding extra hashes.)

So for example, today, you should include (at least) both a SHA-256 (SHA-2) and a SHA3-256 (SHA-3) hash. (Or other sizes if you prefer, but today there's no strong reason.) One of the reasons why SHA-3 was chosen to be what it was is that it uses rather different techniques (a sponge construction, whereas MD5, SHA-1 and SHA-2 all used a Merkle-Damgård construction), so it's very unlikely that both will be broken at the same time.

You can find recommended hash lengths for a given duration of protection according to various authorities on keylength.com. Most are satisfied with a 256-bit hash for as long as they're willing to give recommendations for. My personal inclination would be to make an effective 512-bit hash by concatenation SHA-256 and SHA3-256.

The primary threat against your system is second-preimage resistance (not being able to tamper with a legal document after it was archived), but collision resistance is also a concern: someone could submit a document (e.g. a contract) with a prepared “trap” that allows them to craft a collision after the contract has been signed (e.g. “you owe us \$1 if you have a blue contract or \$1,000,000 if you have a red contract” — uh-oh). Hash functions seem to be more vulnerable to collision attacks, i.e. finding $M$ and $M'$ such that $H(M) = H(M')$, than to second-preimage attacks, i.e. finding $M'$ such that $H(M) = H(M')$. For example, collisions are known for MD5 and SHA-1, but nobody knows how to find a collision for a given message as opposed to a specially-crafted message (at least nobody who's said so publicly). Here are two things you can do to mitigate collision attacks:

The known techniques to generate collisions require taking the hash function through “near-collision” states which are extremely unlikely to occur naturally. So you can detect a probable collision attack when hashing a single message! This idea is due to Marc Stevens and an implementation for SHA-1 is available.
Crafting collisions for MD5 or SHA-1 requires a bit of “garbage” in the middle; that garbage can be hidden in some insignificant part of a complex format such as PDF, or in comments in a computer program, but current techniques don't allow crafting a collision between plain text English documents even with MD5. If you hash plain text¹ rather than (or in addition to) complex formats such as PDF, collision attacks will be easy to detect after the fact, unless our knowledge of how to craft collision makes significant leaps. If your input is not plain text, this does require a deterministic process to generate the plain text.

In the longer term, the only viable solution is algorithm agility: periodically re-hash the documents with newer hash functions. This can be combined with the need to verify and update physical supports. Paper can last centuries or more with proper care, but a magnetic tape or CD is unlikely to last so long; data needs to be transferred to new media every so often. That point in time is a good time to verify originals and re-hash them using up-to-date algorithm. Note that this requires access to the originals, which isn't the case for a plain medium-to-medium transfer; you might not want to do it on every physical transfer, but you should have a procedure for it.

Note that a hash only guarantees integrity, not authenticity. There's only one message with a given hash (as long as the hash function isn't broken), but anyone can produce this hash. Authenticity requires a signature: having a valid signature shows that somone holding the corresponding private key saw the document and was willing to endorse it (subject to the conditions under which the signer is willing to sign documents).

¹  Here, “plain text” means a pure text format (e.g. stragiht ASCII or Unicode), what MIME would classify as text/plain, not cryptographic plaintext as opposed to ciphertext.


Do low-entropy fingerprints actually make any sense?

Short key fingerprints are indeed vulnerable. But those are different from the short-authentication-string (SAS) used by ZRTP.

A simple SAS based protocol using one-time keys could look like this:

Alice sends a (collision resistant) hash of her public key to Bob.
Bob sends his public key to Alice
Alice sends her public key to Bob

The short authentication string is computed as hash of both public keys.

Bob can't deliberately influence the SAS because he doesn't know Alice's public key yet. Alice can't deliberately influence the SAS in Step 3, because she already committed to her public key, by publishing its hash in Step 1 before she learned about Bob's key.

Alice could abort the connection after step 2 or Bob after step 3, but that should display an error to the user and can't be pulled off too often.


What is the best way to put a backdoor in an encryption system?

Schneier's "A Self-study Course in Block-Cipher Cryptanalysis" is an excellent resource for what you are looking for. In particular, FEAL-4 would be a promising cipher to look at as it is breakable by almost every cryptanalysis technique.

One thing you will notice when going through Schneier's course (or when looking at cryptanalysis research in general) is that a lot of times it is helpful to restrict the block cipher by decreasing the number of rounds. Decrease the number of rounds enough, and every block cipher is probably breakable. This will teach you a lot.

Once you are familiar with standard cryptanalysis techniques, it shouldn't be too hard to come up with a cipher that is breakable (where you'll know how to break it).


Salsa20 in Davies-Meyer mode with a fixed key (message): is it one-way?

If you take a pseudo random permutation permutation you usually get a hard to invert PRF.

AES with its 128 bits is a bit narrow, but Salsa's 512 bits are certainly wide enough.

Commonly used compression functions are built from block-ciphers with similar techniques:

For example Davies–Meyer (used in popular hashes such as MD5, SHA-1 and SHA-2) uses:

$H_i = E_{m_i}(H_{i-1}) \oplus H_{i-1}$

The $\oplus$ operation prevents solving for $H_{i-1}$ given $m_i$ and $H_i$. Without this one-way operation a narrow-pipe hash-function would be vulnerable to meet-in-the-middle attacks.

With Matyas–Meyer–Oseas the $\oplus$ is even more crucial:

$H_i = E_{H_{i-1}}(m_i) \oplus m_i$

This construction directly relies on $\oplus$ turning a permutation into a one-way function for its pre-image resistance.

The only different between Matyas–Meyer–Oseas constructions and Salsa is that salsa is lacking the chaining value/block cipher key which it doesn't need.


Equivalent key size between HMAC and AES?

Well, there are two potential key recovery attacks against HMAC (assuming a reasonable hash function):

Brute force the key; that is, take a valid (Message, MAC) pair, and try every possible key, and look for a key that gives that MAC for that Message
Brute force the internal hashing state immediately after processing the IPAD/OPAD; here, you would take a valid (Message, MAC) pair, and try every possible key, and look for a key that gives that MAC for that Message

Now, for first attack would take $O(2^k)$ time (for a key size of $k$); the second attack would take $O(2^{2n})$ time (if the hash function had an internal state size of $n$ bits).

With realistic key sizes and hash functions, $2^k < 2^{2n}$; hence the best attack is an exhaustive search of the key space; this gives us the same approximate strength as AES for a given key size.


Applying Chinese RemainderTheorem and Paillier Homomorphic encryption

A working method for CRT-aided decryption in Pailler goes:

Evaluate $x=c^\lambda\bmod n^2$ by the Chinese Remainder theorem, that is

$x_p\gets c^\lambda\bmod p^2$
$x_q\gets c^\lambda\bmod q^2$
$x\gets\left(q^{-2}(x_p-x_q)\bmod p^2\right)q^2+x_q$

Then evaluate $m\displaystyle\gets\left\lfloor\frac{x-1}n\right\rfloor\,\mu\bmod n$.

The savings are by a factor of at most 2, rather than at most 4 for RSA, because the exponent $\lambda$ remains the same size, when its $d_p$ and $d_q$ have their size halved in RSA.

The question's method is broken where it goes from the following line to the next:

$\begin{align}
m&=L\left(c^{(p-1)(q-1)}\bmod n^2\right)\cdot\left((p-1)(q-1)^{−1}\bmod n\right)\bmod n\\
m_p&=L_p\Big(\left(c^{p-1}\bmod p^2\right)\cdot\big((p-1)^{−1}\bmod p\big)\Big)\bmod p
\end{align}$

Problems are:

Function $L_p$ is not stated. I work under the assumption that $L_p$ is to $p$ what $L$ is to $n$, that is $L_p(x)\displaystyle=\left\lfloor\frac{x-1}p\right\rfloor$. Also I assume $m_p=m\bmod p$.
The term $(q-1)^{-1}$ of the first equation mysteriously vanishes from the second.
Something on the tune of $L(x)\equiv L_p(x)\bmod p$ seems to be assumed  without justification.
The term $(p-1)^{-1}\bmod p$ (which BTW is always $p-1$) has mysteriously entered the input of $L_p$ when $(p-1)^{-1}$ was at the output of $L$.

Numerical experiments disprove the second equation (under the assumptions made in 1). If there is a way to repair it, I want to know!


Are post-quantum cryptographic ciphers *also* secure if the P=NP conjecture holds true?

Do the post-quantum ciphers also automag/tically address the 1st problem?

Not really, however to explore that in any detail, we need to explore what the 1st problem is.

If $P=NP$ is proven true, what does that practically mean?  Well, it might have absolutely no practical ramifications, or it might mean that virtually all known cryptographical systems can be trivially broken.

Why is this?  Well, for two reasons: one, if we know $P=NP$ is true, we know that any problem within NP can be solved in polynomial time; it doesn't say we know how it can do it.  If the proof of $P=NP$ doesn't give an algorithm (e.g. the proof shows that $P \ne NP$ leads to a contradiction), the knowledge that there is a polytime algorithm doesn't help us to solve any particular problem.

Secondly, even if we knew a polytime algorithm to solving an arbitrary problem within $NP$, it doesn't say that it runs in any sort of practical time.  If the algorithm runs in $O(N^{1000})$ time, it is infeasible to run against any realistic problem, and hence does not practically impact the security of any cryptographical system at all.

On the other hand, what $P=NP$ might mean is that there is a practical algorithm for solving any reasonably sized problem; by practical, I mean that it is feasible to run the algorithm against a reasonable sized problem.  If this were the case, all but a handful of cryptographical algorithms would be broken.

Here's why: known cryptographical systems are based on one of three security assumptions:

Informational security; the attacker literally does not have enough information to recover the plaintext; an example of this is One Time Pad (OTP)
Quantum security; the laws of physics prohibit the attacker from listening into the message without detectably disturbing in; Quantum Cryptography (QC) is in this category
Computational security; the attacker has all the information he needs; however recovering the plaintext would require more computation than he has; virtually all cryptographical systems are in this category

A practical way to solve an arbitrary $NP$ problem would invalidate everything in the computational security category, as everything in that category can be reduced to a series of $NP$ problems.  Hence, in the absolute worse case scenario, we'd be left with OTP, QC and not much else.

So, in summary, just saying $P=NP$ doesn't give us enough information about what the practical aspects would be.  However, 'post-quantum' algorithms, that is, algorithms that cannot be practically broken, even given access to the algorithms that can be run on a quantum computer, don't bring anything special to the table.

Now, you state that:

  Some of them are apparently based on $NP$-hard problems (such as the shortest vector problem) which means that these ciphers won't become vulnerable (even in theory) even if the $P=NP$ conjecture holds true.

Actually, you misunderstand what $NP$-hard means; it doesn't mean that the problem is harder than an $NP$ problem; what it means is that if you can solve that problem, you can solve any problem in $NP$ (and so it is at least as hard as any $NP$ problem).  However, it doesn't state whether it goes the other way; if you can solve an $NP$-complete problem, you may or may not be able to solve your $NP$-hard problem.  In practice, we often dub a problem as $NP$-hard (and not $NP$-complete) if the problem is not a decision problem (that is, the answer to the problem isn't limited to "Yes" or "No"), and so pedantically not within $NP$ (and hence not within the set of $NP$-complete problems).


Do all TLS cipher suites using "ChaCha20-Poly1305" use Poly1305-AES?

Nope, AES is indeed replaced with ChaCha20 in TLS. The Poly1305 one-time key is generated pseudorandomly using the ChaCha20 block function.  The ChaCha20-Poly1305 TLS cipher suite spec draft uses the AEAD construction from RFC 7539, which defines exactly how this works:

The ChaCha20 and Poly1305 primitives are combined into an AEAD that
takes a 256-bit key and 96-bit nonce as follows:

o  First, a Poly1305 one-time key is generated from the 256-bit key
   and nonce using the procedure described in Section 2.6.

and Section 2.6 describes how the block function is used to generate the key:

o  The 256-bit session integrity key is used as the ChaCha20 key.

o  The block counter is set to zero.

o  The protocol will specify a 96-bit or 64-bit nonce.  This MUST be
   unique per invocation with the same key, so it MUST NOT be
   randomly generated.

Interestingly, the same 256-bit key and 96-bit nonce that are used to generate the one-time Poly1305 key are also used to produce the ChaCha20 keystream during the encryption step. This would be a security problem, except for this little detail:

o  Next, the ChaCha20 encryption function is called to encrypt the
   plaintext, using the same key and nonce, and with the initial
   counter set to 1.

Essentially, the first block (block zero) of ChaCha20 keystream output is used as the Poly1305 one-time key, while the remaining blocks are used in the actual encryption. This is critical: without this separation, an attacker could determine the Poly1305 key.

You might wonder why the Poly1305 paper used AES in the first place. Poly1305 was published in 2005, around the same time Salsa20 (ChaCha20's predecessor) was introduced. I suspect Bernstein chose AES since it was considered the "gold standard" at the time, and Salsa20 had not yet received significant attention from cryptanalysts.


Dinh, Moore, Russell have shown that the quantum algorithm (Quantum Fourier sampling) used to attack RSA and ElGamal does not work on McEliece-like crypto systems. (I think) this means, that there are no known algorithms on quantum computers that decrease the complexity of attacks on McEliece, and thus McEliece is just as safe post-quantum computers as it is now.


How can A pass a message to B, while preventing a third party from sniffing infos?

Server distribute respective private keys to A (PrivateKeyA) and B (PrivateKeyB) and stores their public keys (PublicKeyA and PublicKeyB) within it's database.
Now any of the user (eg A) generates a random session key (K) and encrypts this key with its own private key (PrivateKeyA). Since server has public key of A, it can decrypt the encrypted session key.
Now it encrypts the same session key (K) which it got from A with B's public key and sends it to B. Now since only B knows the corresponding private key, only B can decrypt the encrypted session key to deduce the key K.
Now A and B share a session key, which they can use to safely communicate with each other.

For exchanging session key the the algorithm  uses asymmetric cryptography and for communication it uses symmetric cryptography technique. The only thing to keep in mind is that either user must be capable of generating a good and strong random session key.


Does the value of the key array(T) have to be in this range [0-255] if yes could you please specify why?

Yes. RC4 operates on bytes. There are 256 possible values for an 8 bit (1 byte) number, that range from 0 to 255. RC4 treats the key as an array of bytes, so every entry in the key array is by definition in the range 0 to 255.

  Why did they use s[t] to generate the key and not the key array which is defined as t array in RC4?

Without seeing the RC4 code you are referring to, it is hard to tell what you mean. $S$ is a keyed permutation (where the key is $T$) of the bytes in the range 0-255. The T array may not contain all bytes since it is generated by the user. So, in order to make it so that the values output as the keystream can be the entire range of byte values, they have to use $S$ instead of $T$.

  I want to develop the RC4 algorithm to be more secure

Bruce Schneier once noted: "Again, I repeat the saying I've heard came from inside the NSA: 'Attacks always get better; they never get worse.'"

The most recent news on an RC4 attack had this to say: "The researchers said the only reliable countermeasure is to stop using RC4 altogether." (emphasis added)

A number of attacks on RC4 have been published in recent years, and, they are only getting better. A lot of folks are removing RC4 completely from older systems.

Important
I want to point something out that I hope you don't skip over. Any sort of system designed these days should be designed in such a way that it is not cipher specific. In other words, if you really want your system to be "more secure", you should design it in such a way that it can theoretically support any cipher. That way, if one cipher gets broken, your system can easily adapt to a new one that isn't broken. If you are willing to share more details about your system, I think we can help you design it in such a way that this is possible. Likely that will mean using existing standards, or only slightly modifying a standard to fit your needs.


Encrypt a file for random access but only after an initial read of the whole file

Yes, you can do that.  Start by generating a random key and encrypting the data under that key.  Now, you in turn encrypt that key with your password-derived key.  The twist is that you include the already encrypted file in your PBKDF.  So you generate a random key $k$ and then encapsulate it as $\mathcal{E}_{k'}(k)$, where $k' = H(PBKDF(\text{password}) \| \mathcal{E}_k(\text{file})$.  That way, to decrypt you have to read and hash the entire encrypted file to obtain the wrapper key, which gives you the key to decrypt the file itself.  Once you have that key you can do random access, but for each password attempt you have to read and hash the whole file again.


Given a private RSA key, how do we get the public key?

Yes, in general the private key is generated at the same time as the public key in RSA, first the $p$, $q$ primes, then $n = pq$, then the public exponent $e$ and finally the private exponent $d$.

If the private key is given as $(p, q, d$) then you can recover the public key easily. As long as you know the public exponent and $n$, you have the public key (and this means that if you cannot guess $e$, you need $d$ and the factorization of $n$, this is an instance of the RSA problem).

However, as @fgrieu points out, if the private key is stored as $(n, d)$ and $e$ is not conventionally chosen and unknown, then the public key is lost and cannot be obtained from the private key.

The opposite (private key from public key) is meant to be infeasible though.


Why Crypto++ library's AES definition is so fast

Actually, your numbers seem shockingly high at 2724 cycles for one block - even with the key schedule.
Crypto++ uses standard AES-NI for the encryption of blocks and for the key generation they use AESKEYGENASSIST for the SBox (unfortunately).
Ideally the expected performance would be (for their implementation, not for one with an optimized on-the-fly key expansion):

~783 cycles for the keyschedule (as estimated by llvm-mca)
1x 1 cycle for the initial XOR of the key
10x 4 cycles for AESENC/ AESENCLAST

So overall less than 1000 cycles.
Even if we assume AES-256 here, we shouldn't get beyond 1500 cycles for the actual operations. 2700 is massively off from that and suggests inefficiencies in feeding AES data.
Also note that this kind of test is highly unfair to the AES-NI hardware because it only really shines if you give it 4 or more independent AES operations to calculate in parallel (due to latency of 4 cycles per round instruction but the throughput of 1 cycle per instruction). Furthermore note that Crypto++'s keyschedule implementation is ... rather lackluster, and optimized implementations compute a round key in less than 20 cycles, so less then 200 overall for the entire cipher.
You can find the translated key expansion code here. You can look the performance of the instructions up either at Intel's site or in Agner Fog's tables.

A fairer comparison would probably take the best non-AES-NI implementation, a AES-NI implementation of AES and an optimized implementation of your cipher and put them up against each other in these categories:

CBC encryption of long messages - measures the cipher latency and long messages "hide" the key schedule cost
CTR encryption of long messages - measures the maximal throughput
(Optionally) Stand-alone keyschedule computations with one encryption (which is roughly what you measured) - with an implementation optimized for fast key schedules (aka not Crypto++ as it currently stands)


(Simple) Tool for analysing performance (speed in particular) of cryptographic hash function?

The performance can be configuration specific, so beware that any outcome is specific to a machine. Take care that you test on the right configuration(s).

The performance may also be specific to a certain input size. So test for specific amounts of data while keeping in mind that most hash methods operate on blocks (it doesn't make much sense to test 1 byte input and then 2 byte input, one block will be hashed regardless).

You don't need a lot more than a timer to measure such performance. First do x rounds of hashing just to make sure you are not left with startup flukes (hash code not loaded in cache of CPU yet). Note that this is specifically required when running on a VM. So for C / Linux it may not be that relevant - you can choose a smaller x.

Now let it run n rounds, divide by n.  Choose a large number for n. That's about it.

If you want to reuse existing code then you can simply reuse the openssl speed commands. Just look up what happens in the code for openssl speed sha256 and implement another one next to it or extract the code.


DES algorithm exhaustive key search 2^55 instead of 2^56

What you want  follows from the DES complementation property so only the remaining 55 key bits need to be brute-forced.


Is following MAC schemes formed by MAC schemes secure?

In the first case, $\Pi_3$ is not secure.

We can use $(m_1, m_2)$ and $(m_3, m_4)$ to query the adversary $A$.

$t_1||t_2 = A(m_1, m_2)$

$t_3||t_4 = A(m_3, m_4)$

The forged MAC would be $t_1||t_4: Verify(t_1||t_4, (m_1, m_4)) \rightarrow Accept$.

In the second case, $\Pi_3$ is not secure.

We can use $(m_1, m_2)$ and $(m_1, m_3)$ to query the adversary $A$.

$t = t_1 \oplus t_2 = A(m_1, m_2)$

$t' = t_1 \oplus t_3 = A(m_1, m_3)$

$t_f = t \oplus t' = t_2 \oplus t_3$

The forged MAC would be $t_f: Verify(t_f, (m_2, m_3)) \rightarrow Accept$.

Another way to break the scheme is to reverse the message pair. $Verify(t, (m_2, m_1)) \rightarrow Accept$.


$m ∈ Z_n \backslash Z^*_n$, RSA works but not secure

We know that $|\mathbb{Z}_n| = p\cdot q$ and that $|\mathbb{Z}_n^*| = (p-1)(q-1)$.

So $|\mathbb{Z}_n \backslash \mathbb{Z}^*_n| = (pq) - (p-1)(q-1) = pq - pq + p + q - 1 = p + q -1$. That number is approximately $2^{513}$ given your example prime sizes.

So, out of approximately $2^{1024}$ choices for messages $m$, quite a few are bad. That said, finding one of those is equivalent to factoring. The fastest known method for finding one of these bad messages is to first factor the modulus. Then you can trivially find one.

With just random guessing, each message is equally likely, so has a probability of $\frac{1}{2^{1024}}$, so the probability of finding one of these bad messages is $\frac{2^{513}}{2^{1024}} = \frac{1}{2^{511}}$.


Is using the same HTTPS cipher suite as Google a good idea?

But since I'm only running a small website, I'm not entirely convinced
  that what's good for Google is also good for me.

You're right with this assessment. Google has far more ressources for this than you probably have and this is why they can do things like roll-out ChaCha20-Poly1305 before it's standardized or the new post-quantum key exchange they're using, especially since they largely control development of Chrome which has an insanely large userbase.

  Are there any other ciphers that I really should allow, even though
  Google doesn't?

Yes.
For some reason, Google offers only ECDHE and (static) RSA cipher suites. While they reach the most people with this, you probably don't need to reach those ancient browser who don't understand either DHE or ECDHE (it's 2016, come on!). So the recommendation here would be to add the DHE variants of the cipher suites (although with lower priority than the ECDHE counter-parts).
Additionally you should consider adding (the now standardized) ChaCha20-Poly1305 cipher suite(s) into that list if supported by your TLS implementation, because of the high perfomance on mobile platforms.
Note though: If you can, disable parameter (as in the private key) re-use with the (EC)DHE cipher suites and generate your own DH parameters (and use them) once (using OpenSSL or something like that).

  Are there any ciphers in the suite above that I should not use? And if
  so, why?

Yes.
All the cipher suites that lack "ECDHE" or "DHE" in their name should be gone. Those are a) removed from TLS v1.3 anyways and b) if your server key ever gets leaked (heartbleed anyone?) an attacker can decrypt all the traffic that has ever been recorded while this key and these cipher suites have been used. This doesn't happen with the (EC)DHE suites and the property for them is called "forward secrecy".
Additionally you can (and should) drop the 3DES cipher suites because you don't need the backwards compatibility they provide (probably) and because they have quite a small block size, making them vulnerable to attacks like Sweet32.


The difference between “112 bits” and “128 bits” matters for compliance to certain standards, but not for security. Both are out of reach of current computing technology. Furthermore, 112 bits for RSA-2048 is an estimate based on current attack techniques. A disruption such as quantum computers that are useful at cryptanalysis would break both RSA and AES, but in different ways — RSA would be trivialised at any pratcical key size, while symmetric cryptography would only have its “bit strength” halved.

So either you have to comply to some strict standard, and then you need to do what the standard says; or you don't have to comply to some strict standard, and then RSA-2048 is fine for authentication (which is what it's used for here). This is true even if you're exchanging long-term secrets: to break the security of your VPN by attacking the RSA part, the attacker has to breach it live, to cause the client to accept a fake server. The use of ECDHE provides forward secrecy, so there's no way to reconstruct the plaintext from the ciphertext and the server's RSA key later (if the attacker managed to break RSA, or more realistically to obtain the key). If you are concerned about very long-term secrecy, switching to AES-256 is actually more useful than moving away from RSA-2048 (and then you should also check that you're using a stronger curve, at least P384R1).

However there's little reason to use RSA these days. Elliptic curve cryptography has generally better performance for the same security. Your default choice should be TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 (or AES_256 instead of AES_128, or SHA384 instead of SHA256, or CCM instead of GCM), sticking to widely-supported ciphersuites. EdDSA and ChaCha20_Poly1305 are also good choices if supported. RSA as used in TLS_(EC)DHE_RSA_xxx ciphersuites has better performance than elliptic curve methods on the client side (at the cost of worse server-side performance) if you're only authenticating the server, which is often the case on the web. But if the two sides authenticate each other, as is normally the case on a VPN, elliptic curves have better performance.


Decrypting two XORed compressed messages?

Update: a premise in the former answer did not resist the acid test of experiment. This whole answer was thus very wrong.

Thanks to daniel's comment for opening my eyes.


Is the RSA signature attack from Desmedt and Odlyzko practical?

TL;DR: Yes, on narrow or some ad-hoc deterministic RSA padding, which must not be used.

The Desmedt and Odlyzko attack on RSA signatures [DO1985] assumes a deterministic RSA signature scheme with appendix that, for RSA key $(N,e,d)$, signs messages $M$ with signature $S=(H(M))^d\bmod N$ for some public function $H$ with $H(M)<2^k$ and $k\ll\log_2(N)$, and verifies alleged signature $S$ by checking that $S^e\bmod N$ matches $H(M)$. The attack is computationally feasible for $H$ a $k$-bit cryptographic hash, up to at least $k=200$ [CNST2016], and I believe $k=256$, perhaps more. The size of $N$ and $e$ are almost immaterial.

The attack computes the signature of a message $M_0$ chosen by the adversary from the signature of many other messages $M_i$ chosen by the adversary, and the public key $(N,e)$. All theses messages must obey one constraint: be smooth; that is, have all their prime factors below a "smoothness" bound (except perhaps for one of two larger prime factors shared with other $M_{i'}$, $i'\ne i$ (these large prime and two large primes variants of the attack parallel similar variants in MPQS, see [LM1990] as used in the landmark [AGLL1994] ).

The basic attack combs many messages $M$ to find these such that $H(M)$ has all its primes factors below bound $B$, and forms a large sparse matrix with one line for each such $M_i$, one column for each prime $p_j$ below $B$, the multiplicity of prime $p_j$ in $H(M_i)$ at the intersection $c_{i,j}$, and significantly more lines than columns.

By Gaussian elimination or a method to the same effect, it is found coefficients $u_i\in\mathbb Z$ for each line, such that $\forall j,\;0=\displaystyle\sum_{i\ge0}u_i\,c_{i,j}$, and $u_0=-1$. It follows that $\displaystyle\prod_{u_i<0}H(M_i)^{-u_i}\;=\;\prod_{u_i>0}H(M_i)^{u_i}$, and thus $H(M_0)\equiv\displaystyle\prod_{u_i\ne0,\,i>0}H(M_i)^{u_i}\pmod N$.

By raising the later to the power $d$, it comes that the signature $S_0$ of $M_0$ can be obtained from the signatures $S_i$ of some of the other $M_i$, as
$$S_0\equiv\prod_{(u_i\bmod e)\ne0,\,i>0}S_i^{u_i}\;\;\prod_{(u_i\bmod e)=0,\,u_i\ne0}H(M_i)^{u_i/e}\pmod N$$

The Gaussian elimination can be directed to reduce the number of $S_i$ needed at the expense of needing more smooths; and that's easier for small $e$.

The attack is an existential forgery, but could be entirely practical if narrow deterministic RSA signature padding was used (contrary to all serious security guidelines). Consider an hypothetical automatic file timestamping server that upon receiving a file hashes it using SHA-384, then produces and signs using $S=(\operatorname{SHA-256}(M))^d\bmod N$ a message $M$ of the form:

At 2017-09-21 09:12Z I received a file which SHA-384 hash in base64 is RpzByokphjFifbPgFhR2vFnqbHvqA283Ud8sN0ic61fxd5hyQdXo3VofgkrSb0fz

The adversary wants a certain file backward time-stamped. S/he:

Searches suitable past dates and/or equally useful variations of that file such that the message $M_0$ that the server would have generated for that (variation of that) file has smooth SHA-256.
Generates many small files / future dates pairs such that the resulting $M_i$ have smooth SHA-256.
Conducts the Gaussian-elimination-on-steroids part of the Desmedt and Odlyzko attack, which yields a subset of the original $M_i$ she needs signed.
Obtains their signature by asking for a time-stamp of the appropriate small files at the beginning of the appropriate minute.
Succeeds! The signature for $M_0$ can be computed from the signatures obtained at the previous step, and authenticates $M_0$ as a backward time-stamp that the server has not and would not have produced.

Note: The attack does not require computing any hash preimage or finding any collision: all the $M_i$ including $M_0$ are determined from the file and date they are related to, then hashed using SHA-256, then this hash is tested for smoothness.

The attack requires relatively few computations of SHA-384, but many computations of SHA-256 and fast ways to test if they are smooth (smooths are rare). Most of the computational effort is there, I believe.

The attack is thwarted if either:

The hash is wide, ideally as wide as $N$ is; this is the exact strategy of RSA-FDH, is also used by RSASSA-PSS, and (in a bastardized and occasionally failing way) by ad-hoc RSA signature schemes.
The signer inserts something unpredictable into what it sign; this is the strategy of probabilistic signature schemes like RSASSA-PSS and ISO/IEC 9796-2 scheme 2, and their de-randomized variants. This is also used by some responsible Certification Authorities, which generate a random or otherwise unpredictable certificate serial number when using ad-hoc RSA padding like RSASSA-PKCS1-v1_5, or less than ideal hashes like SHA-1.

The Desmedt and Odlyzko attack [DO1985] is a sub-component of other attacks on wide deterministic RSA signature padding, including the first break [CHJ1999] of the (withdrawn) ISO/IEC 9796:1991, and the break [CNST2016] of ISO/IEC 9796-2 scheme 1 (aka 1997).

References:

[DO1985]: Yvo Desmedt and Andrew M. Odlyzko; A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985.
[LM1990]: Arjen K. Lenstra, Mark S. Manasse; Factoring with two large primes, in proceedings of EuroCrypt 1990.
[AGLL1994]: Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul C. Leyland; The magic words are squeamish ossifrage, in proceedings of AsiaCrypt 1994.
[CHJ1999]: Don Coppersmith, Shai Halevi, Charanjit Jutla; ISO 9796-1 and the new forgery strategy, circulated as an IEEE P1363 Research Contribution, 1999.
[CNST2016]: Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi, Ralf-Philipp Weinmann: Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures in Journal of Cryptology, 2016 (first version in proceedings of Crypto 2009); section 3 makes a modern exposition of the Desmedt and Odlyzko attack applied to RSA signature.


What are the potential (major) flaws in this security scheme?

One real problem is that lack of authentication between the two sides.  Here's one possible problem:

Alice generates an RSA keypair (we assume Alice is using proper random numbers)
Alice sends the public key as plain text to Bob.

Eve intercepts this message, and forwards on a message to Bob with her public key

Bob generates a 3DES session key: BA
Bob sends BA encrypted with [Eve]'s public key, together with a checksum of BA

Eve intercepts this message, and decrypts it with her private key, giving her the value of BA.  She then takes BA and the checksum, and encrypts it with Alice's public key, and sends that on to Alice

Alice receives and decrypts BA using its private key.
all following sensitive data is encrypted with BA and integrity is checked via the checksum.

That is, all sensitive data is encrypted by a key that Eve knows.  Furthermore, she can modify anything she wants.
In general, you cannot really have secure communication unless you know who you're actually communicating with.  In this case, Bob has no reason to believe that the public key he gets is from Alice, and not someone impersonating Alice.


In laymans terms, what exactly is a "One time pad"?

I'll answer your questions (1, ..., 4) first:

  1) Does that mean that if I encrypt the message Hello World with the key Password123 - that this would be considered a one-time-pad?

No. The one time pad (OTP) requires the key to be truly random - otherwise it's guessable. And encrypt is vague - this could be any cipher.

  2) What if I encrypt two different messages Hello World 1 and Hello World 2 with the same key Password123` - is this no longer a one-time-pad?

No - this is called a multi time pad and is crackable. And the OTP needs the key to be the same length as the message.

  3) What if I repeat the previous scenario with a small twist. Still encrypt two different messages with the same key, but introduce a salt Password123 + [SALT] - are we now back to being a one-time-pad? (keep in mind, I am assuming the salt is sent alongside the encrypted text).

The OTP doesn't take a salt, though I suppose what you suggest is plausible. If the salt is different for each message, than that avoids multi-time pads, but sending it with the message isn't particularly secure. Like sending half a password. Plus you still have the plaintext-key length problem.

  Does the strength of the cipher even matter as long as one unique key is used once to encipher/decipher one message. Would a one-time-pad using AES have the same strength as a one-time-pad using ROT?

The OTP is a cipher$^1$ in itself. You don't use AES or ROT. And that voids the rest of the question.

The original OTP was based of the Vignère cipher. In Vignère, the key fred with message plaintext means that the key isn't long enough. Therefore, it repeats and becomes:fredfredf. Then, it's encrypted with a vigénere square, and you have the ciphertext.

The old OTP is almost identical; the key must be random though. Truly random. And the same length as the ciphertext.

The modern OTP is much simpler:

$C_i = (P_i \oplus K_i)$

Now you might wonder: that's so simple! Why don't we use it all the time? It is, after all, unbreakable.

The answer is because of its keysize. For a 5GB message (or file) you need a 5GB key. See the problem?

As an afternote, read Crypto101 (https://crypto101.io). It's a work in progress, (some sections simply contain TODO) but it'll be beneficial for anyone interested in cryptography.

$1$: The one time pad's status as a "cipher" is argued about all the time. I use that term here because it gets the meaning across.


Can adding bad entropy to good entropy, make a system insecure?

If you have a variable with maximal entropy, and you combine it with an independent variable with less entropy using Xor or modular addition you will still have maximal entropy.

If you have two independent variables with low entropy and you combine them in the above fashion the result will be a variable with more entropy than either the original ones

If however the variables are correlated all bets are off. Even combining two maximal entropy variables may result in 0 entropy (constant variable ) when adding/xoring them.


Is it possible to trim some encrypted values under fully homomorphic encryption

As long as you can design a circuit to do it, then yes. There are a few ways to do this. One is to build a sorting network and output the highest $N-M$ values.


What are the practical limitations of Asymmetric encryption vs Symmetric encryption?

The advantage of asymmetric encryption is not security, it is capability. Asymmetric crypto provides completely different capability that you can't get with symmetric crypto. With symmetric encryption, you have to establish a key a priori. With asymmetric crypto, you can establish a key on the fly (granted you have to have trust in the public key, that it belongs to the party you want to interact with). With asymmetric crypto you often have digital signatures, establishing authenticity of data.

You mention the primary advantage of symmetric crypto in your question, speed.

So, to your questions:

  Why couldn't I do the same with Asymmetric encryption?

You could. You would first have to define how you are going to encrypt large amounts of plaintext. Do you build a > 1TB modulus? Absolutely not. Do you establish some sort of mode of operation? Sure, but then you have to prove security.

You also will likely want integrity checks like you would get with authenticated encryption or HMAC. How do you do that?

  what are the practical limitations of using Asymmetric encryption for bulk encryption?

Speed and the lack of trusted, well studied standards.


Reason(s) for using a KDF for encryption keys

The point of a KDF is to take a low-entropy input and significantly increase the amount of computational power (and thus time or cost) it requires to brute-force, hopefully to a level on-par with a truly random value.

If you're already using a 256-bit value generated from a CSPRNG, there is no need to use a KDF.

In fact, using a KDF can only reduce the security of your keys. If there are any collisions in your hash function for 256-bit inputs, the number of possible KDF-generated keys will be fewer than the number of inputs, and you have a smaller possible keyspace. On the other hand, it can't possibly increase security, because if you're using a KDF to expensively turn 256-bit keys into different 256-bit keys, attackers have no need to go through the KDF. They can just enumerate the 256-bit keyspace in the first place.


brute-force factors of numbers on my computer at home?

Take a look at the paper Factoring as a Service for what you can do using the cloud. In the introduction on page 2 they write where you can find their Software.


Connections between Instance Hiding and Fully Homomorphic Encryption

Here's what's common in both scenarios: Alice holds $x$ and wants to compute $f(x)$. A server Bob will help with the computation. Alice doesn't want Bob to learn $x$, so she sends some encoding of $x$ that hides $x$. Bob does some work and sends back a result from which Alice can infer $f(x)$.

The two settings differ on: (1) how Bob is allowed to help Alice with the computation, (2) what kind of guarantee Alice has about the privacy of her data $x$.

In the setting of the Abadi-Feigenbaum-Kilian paper, Bob must evaluate $f$ itself on the stuff that Alice sends to him. He is not allowed to compute some other thing related to $f$. This is quite a severe restriction! Also, this setting demands unconditional privacy against Bob.

In the setting of FHE, Bob doesn't literally perform the computation $f$ on what Alice sends him; rather, he performs the ``homomorphic evaluation of $f$ on a ciphertext.'' Also, Alice gets a privacy guarantee that is only computational.


Is using Ed25519 parameters in ECDSA safe?

ECDH is the same as what Curve25519 uses mathematically. The issue is that converting Curve25519 into Weierstrauß form is a bad idea, because it introduces issues relating to the potential failure of the addition law, which are difficult to address well. Keeping the curve in Montgomery or twisted Edwards form finesses these difficulties.

ECDSA has issues related to randomness and is slow. It will be secure, but Ed25519 has many advantages; especially with batch verification.


Reduction from signatures to encryption?

Let's first define a few things. Precise definitions are needed because your question is a bit ill-defined, and it seems that you are somewhat cheating.

Some definitions

Traditionally, we define a signature system as the combination of three algorithms:

G: key generation; given a "security parameter" t (e.g. the intended key size), yields a key pair (x, y) (x is the private key, y is the public key).
S: signature generation: given a message m (from a given space of messages M) and x, outputs a signature s.
V: signature verification: given m, y and s, outputs true or false.

It is supposedly infeasible to do forgeries, i.e., given y but not x, find (m, s) such that V(m, y, s) = true. Existential forgeries are "untargetted" forgeries where the attacker does not get to choose m arbitrarily.

On forgeries and "cheating"

Forgeries are bad, and a signature algorithm which accepts forgeries (existential or not) is considered to be broken. No "standard" signature algorithm accepts existential forgeries. In particular, RSA, as specified by PKCS#1, does not, even when using the "old style" v1.5 padding, which is deterministic: no method is known to generate a number s which, when raised to the public exponent, yields a proper PKCS#1 padding (beginning with 0x00 0x01 followed by eight or more 0xFF bytes). Moreover, the message m is first hashed, and even if you could find a s which produces, when exponentiated, a properly padded hash value, you would still be hard pressed to compute the corresponding m.

So, assuming that you want to apply your method on RSA, you are not talking about "RSA, the signature algorithm"; you need to remove the padding and the hash function, at which point you have the RSA core modular exponentiation, also known as "RSA, the trapdoor permutation". A trapdoor permutation can be used quite immediately for asymmetric encryption. In that sense you are "cheating".

@PulpSpy uses a different cheat, by assuming that he can publish the private key, and keep the public key secret. This may work with RSA, but only if the signature engine (the one which produces the signatures) accepts to work with a "private" key expressed as a raw private exponent and modulus, without knowledge of the modulus factors. "Normal" RSA implementation use the standard private key format, which includes the factors because this speeds up quite a bit private key operations (by a factor of about 4, thanks to the Chinese Remainder Theorem). Also, the "public" key needs to be kept secret, which implies a big exponent, not the usual 3 or 65537; there again, an existing RSA "verifier" implementation may refuse to work.

Rewriting the problem

I suggest the following definition of the problem: let (G, S, V) be a signature system. A key pair is generated; the key holder (Alice) maintains x (the private key) secret, in a box which computes S. The only way to use x is to execute S, which produces a signature on a given message m. The public key y is known by everybody, and Bob has some strong assurance that y is Alice's key through an unspecified mechanism (e.g. a certificate), but there is no other value which is thus unambiguously linked to Alice. Is there a way for Bob to use y in order to convey a confidential message to Alice ?

Note that clause about "no other value". If we allow Alice to publish other data, she could generate a transient key pair for an asymmetric encryption or key exchange algorithm, which Bob would just use (this is how it is actually done in S/MIME when the certificated key of a user is only for signatures). Correspondingly, we are after an asynchronous solution (Bob does all the job in one go, and only then sends the whole to Alice; otherwise, in an interactive protocol, Alice could "cheat" by sending a transient key pair).

For the interest of the exercise, we allow Alice and Bob to input precomputed hash values into S and V: no need to find messages m such that h(m) "works", we accept hand-crafted "hash values" which did not involve a hash computation at all.

With the question stated as above, there is now a good reason why this cannot work with signatures schemes based on a non-interactive zero-knowledge proof. A ZK proof is a protocol in which a prover demonstrates to a verifier knowledge of the solution of a given "problem". The protocol is said to be zero-knowledge because the transcript of the protocol is unconvincing: it is possible, without knowing the actual solution of the problem, to build a fake conversation between a "prover" and a "verifier", and there is no way to distinguish between a fake conversation and a real conversation with the true prover. In that sense, no information about the secret data leaks to the outside. A ZK protocol can be turned into a signature scheme: in a normal ZK protocol, the prover sends one or several commitments, then the verifier sends a challenge, to which the prover can respond in a way which is satisfying with regards to the committed values. It "suffices" to compute the challenge from the commitments using an appropriate one-way function, to make the protocol non-interactive; if a message is also used as additional input to the one-way function, then we have a signature algorithm.

This category of signature algorithm includes all the discrete logarithm-based signature schemes: ElGamal signatures, DSA, ECDSA, Schnorr... (they actually use a slightly weakened variant of ZK dubbed "computational zero-knowledge" because their ZKness is relative to the hardness of some operation, here the discrete logarithm).

The point of the ZK property is that producing the signature leaks no information about the signature key, except that the signing box knows it. For an asymmetric encryption or key exchange scheme, Alice must be able to extract at least one bit of extra information from is signing black box. Here, everybody knows that Alice owns the private key, and any signature generated by S will say nothing more. Therefore, there is nothing that Alice can do with S and what Bob sent her, that will yield any information suitable for a key exchange.

Rewriting this as a properly formal proof looks like hard work. So, right now, what I wrote above is merely "intuition". It means that I find it improbable that one could find a (non-cheating) way of turning an ECDSA-signing-box into a key exchange mechanism.


Only randomly generated components matter for passwords/passphrases.

  6 randomly generated symbols: lower/uppercase letters and numbers.

You have 26+26+10 possible characters, so 62.

The entropy of a password is $L\log_{2}N$, where $N$ is the number of possible symbols and $L$ is the number of symbols in the password. So you have $6\log_{2}62=35$ bits of entropy. You want a minimum of 80 to be considered reasonably strong.

This is ridiculously weak. For all practical purposes it's a 6-character alphanumeric password.


Does DTLS in WebRTC protect from active Man-in-the-Middle?

WebRTC uses DTLS-SRTP and according to RFC 5764 DTLS-SRTP supports certificates for both client and server.
However in the context of WebRTC the direct connection established between the users is established by dynamically downloaded software running in the browser.
In other words the user does not control the software so even if the software did provide him with ways to secure the connection it could be replaced by other software that does not.

This is the same problem as faced by all kind of web based mail encryption systems.

It's nicely treated in this RFC draft:

  In general, it is important to understand that unlike a
  conventional    SIP proxy, the calling service (i.e., the Web server)
  controls not    only the channel between the communicating endpoints
  but also the    application running on the user's browser.  While in
  principle it is    possible for the browser to cut the calling service
  out of the loop    and directly present trusted information (and
  perhaps get consent),    practice in modern browsers is to avoid this
  whenever possible.


The three-pass authentication protocol defined in ISO/IEC 9798-2 at 5.2.2. and it is defined as follows;

$\text{B}$ generated random $R_B$ and sends to $\text{A}$;
$$\text{B}\xrightarrow{R_B\|\text{Text1}}\text{A}$$
$\text{A}$ generated random $R_A$ and sends to $\text{B}$;
$$\text{B} \xleftarrow{\text{TokenAB}\;=\;\text{Text3}\|eK_{AB}(R_A\|R_B\|B\|\text{Text2})} \text{A}$$
$\text{B}$ generated random $R_A$ and sends to $\text{A}$;
$$\text{B}\xrightarrow{\text{TokenBA}\;=\; \text{Text5}\|eK_{AB}(R_B\|R_A\|\text{Text4})} \text{A}$$
$eK_{AB}$ is the encryption with the $K_{AB}$;

  What would happen if the last message in a three-pass authentication protocol was undelivered?

Whoever started the protocol, $\text{A}$ connects to $\text{B}$ by $\text{tokenAB}$.

If $\text{B}$ started then $\text{B}$ can send back the $\text{tokenBA}$ to $\text{A}$  for the agreement.
If $\text{B}$ doesn't send back the $\text{tokenBA}$, $\text{A}$ cannot decide it was actually $\text{B}$ or not. Since, anyone can send an $R_B\|\text{Text1}$ to $\text{A}$.

Old answer if the question was the Three-pass protocol of Shamir

It not verification of each other it is just message exchange.

From Wikipedia;

  In order for the encryption function and decryption function to be suitable for the three-pass protocol they must have the property that for any message $m$, any encryption key $e$ with corresponding decryption key $d$ and any independent encryption key $k$,  $$D(d,E(k,E(e,m))) = E(k,m)$$

i.e.

$$D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).$$

If the third, i.e. the last, is not delivered, the messaged won't be decrypted. He will have $E(k,E(e,m)))$ in his hand, but he cannot decrypt this because he doesn't know the key $d$ of the sender.

The receiver can use the Commutativity property to reach $E(e,E(k,m))$ but this won't help,too


AES CBC in need of multiple IV's, possible to avoid creating duplicate iv's by using resulting cipher text 16 bytes as next iv?

You can indeed avoid having an explicit IV for each chunk in favor of an implicit one, and using the previous encryption's last ciphertext block is indeed one way. But:

You almost certainly need authenticated encryption that provides not just confidentiality but also message authenticity. Read up on the EFail attack, one of whose causes is CBC-based encryption software that doesn't protect ciphertexts from tampering (or more precisely, does so in an inadequate fashion).
Once you add the message authenticity requirement, it becomes very hard to escape ciphertext expansion (ciphertexts longer than the plaintext) because the ordinary way to achieve it requires you to include a message authenticity tag for each chunk. You can tune the overhead by upping the size of each encrypted chunk, but that of course increases how much memory you need to encrypt/decrypt one.

Be aware that what you're trying to do carries countless pitfalls and that it's much less risky if you use a library written by cryptography experts or, at the very very least, copy one of their designs (and copy it successfully). For example, recent versions of the popular Libsodium library include an encrypted streams and file encryption module that's designed to safely perform precisely this sort of constant memory chunked authenticated encryption, but do it carefully:

  This high-level API encrypts a sequence of messages, or a single message split into an arbitrary number of chunks, using a secret key, with the following properties:

  Messages cannot be truncated, removed, reordered, duplicated or modified without this being detected by the decryption functions.
  The same sequence encrypted twice will produce different ciphertexts.
  An authentication tag is added to each encrypted message: stream corruption will be detected early, without having to read the stream until the end.
  Each message can include additional data (ex: timestamp, protocol version) in the computation of the authentication tag.
  Messages can have different sizes.
  There are no practical limits to the total length of the stream, or to the total number of individual messages.
  Ratcheting: at any point in the stream, it is possible to "forget" the key used to encrypt the previous messages, and switch to a new key.

  This API can be used to securely send an ordered sequence of messages to a peer. Since the length of the stream is not limited, it can also be used to encrypt files regardless of their size.

  It transparently generates nonces and automatically handles key rotation.

Your CBC-based approach won't achieve all of this.

That said, just for theory's sake, an alternative way of avoiding ciphertext expansion in CBC is to use a second key and ECB encryption to generate implicit IVs from a counter or nonce.  First you generate and share or derive two block cipher keys $k_1$ (for IV generation) and $k_2$ (for encryption), and a public nonce $\mathrm{IV}$. Then for each numbered chunk $m_1, \dots, m_n$, you encrypt each block this way:

$$
\begin{align}
\mathrm{IV}_1 & = \mathrm{AES}_{k_1}(\mathrm{IV} \oplus 1) \\
c_1 & = \mathrm{AES\text-CBC}_{k_2}^{\mathrm{IV}_1}(m_1) \\
& \vdots \\
\mathrm{IV}_i & = \mathrm{AES}_{k_1}(\mathrm{IV} \oplus i) \\
c_i & = \mathrm{AES\text-CBC}_{k_2}^{\mathrm{IV}_i}(m_i) \\
& \vdots \\
\mathrm{IV}_n & = \mathrm{AES}_{k_1}(\mathrm{IV} \oplus n) \\
c_n & = \mathrm{AES\text-CBC}_{k_2}^{\mathrm{IV}_n}(m_n)
\end{align}
$$

Since the recipient knows $k_1$, $k_2$ and $\mathrm{IV}$, and can also count, they can reconstruct the $\mathrm{IV}_i$ values without the sender having to transmit them.


If the last byte in the block is larger than the block size, that would generate a padding error in SSL 3.0.

SSL 3.0 padding is up to $BlockSize-1$ bytes of unspecified data, and one byte with the length of the padding (not including the length byte itself).  TLS 1.0 and above allow padding longer than the block size, and requires that each byte contains the length.  The POODLE attack is against 3.0 (after downgrading the connection).

In the POODLE attack, you need to arrange two things, the length of the message (plus MAC) is exactly a multiple of the block size, and the byte you want to find out is moved to be the last byte in a block.

If you substitute the padding block with the block with the desired byte, it will occassionally (1 in 256) decode to be 15 (for a 128-bit block size), and the message will be accepted (because the padding byte now leads to a correct MAC, which is at the end of the previous block).  If it isn't accepted, generate a new encrypted message and try again (which will randomly change what that last byte decodes to, from any or all of a new key, a new IV, or any changed fields in the plaintext).

If you take the last byte, XOR it with the last byte of the previous block's ciphertext, then XOR it again with the last byte of the ciphertext preceding the original location of that block, you'll get the correct value of that byte.

Repeat after manipulating the plaintext so that another (unknown) byte is in the last byte of a block (without changing the required padding amount).

An earlier version of my answer was describing a Padding Oracle attack against PKCS#7 style padding, which relies on being able to distinguish between a padding error and a MAC error, the POODLE attack distinguishes between error and no error.

With TLS, padding can be longer than one block, and the implementation shouldn't distinguish between padding and MAC errors, but it's still susceptible to timing attacks, even if it calculates a MAC after detecting a padding error.


Does SRP also authenticate the server to the client?

According to the Stanford page mutual authentication can be provided if both sides keep their secrets secret. Thanks mikeazo.


How does changing input size affect The Goldreich-Goldwasser-Micali Construction?

The input size and the key size need not have any specific relation. The security analysis of GGM goes through as long as the key size is equal to the seed size of a secure length-doubling pseudorandom generator, independently of the input size, which can be an arbitrary polynomial in the security parameter.

Since the depth of the GGM tree is exactly the input length, if you double the input length, you indeed double the depth of the tree. The security analysis remains identical: the only difference is the number of hybrids in the proof, but changing the number of hybrids by any polynomial amount does not harm security, since the adversary has negligible advantage in distinguishing any two hybrids.


How to find the order of a generator on an elliptic curve?

Due to the Pohlig-Hellman algorithm, the hardness of discrete logarithms is dominated by the largest prime factor $\ell$ of the group order $n$. In particular, one typically works in a subgroup of order $\ell$ of the curve group, since the additional factors $h$ in a generator's order would not significantly contribute to security.

In that, note that $\ell$ depends on the group order $n$: You cannot just decide for some order $\ell$ and then find a point $G$ of that order on an arbitrary fixed curve, since it general such a point will not exist. (However, there is  the complex multiplication method, which generates a new curve of given order.)
Therefore, steps 2 and 3 of the algorithm given in the question must be swapped: You first compute the curve group order $n$, factor it, and determine $\ell$ from the factorization. (And if $\ell$ is too small, you should start over with a new curve. For example, Curve25519 has cofactor $h=8$.)

Other than that, the algorithm is fine, except that you might want to check whether $G=\infty$ and start over in that case. However, this only happens with probability $1/\ell$, so it should never occur in practice for cryptographically-sized curves. (Moreover, you would compute and factor the group order only once and find a good $P$ afterwards, but this does not impact the expected runtime much as $P$ usually is good at the first try.)

Thus, we have the following algorithm:

Compute the curve order $n=\#E(\mathbb F_p)$.
Factor $n$ to determine its largest prime factor $\ell$. (Note that you do not need to fully factor $n$: If the remainder after removing a few "small" divisors is not prime, the cofactor is going to be too big anyway.)
Compute the cofactor $h=n/\ell$. If $h$ is "too big", start over with a new curve.
Choose a random point $P\in E(\mathbb F_p)$ and let $G=[h]P$.
If $G$ is the point at infinity, go back to choosing a new $P$. Else, $G$ has order $\ell$.


Is there any good reason to chain HMACs in this manner?

If you are asking if $M(M(M(k, C_1) C_2), s)$ has the same or better security as $M(k, C_1 | C_2 | s)$ then the answer is yes. You can see this as a double key derivation to calculate a new key from $k$ using the constants $C_1$ and $C_2$ as derivation data. Then the resulting key is used to MAC the final serialNumber. $M$ is of course HMAC, $C_1$ and $C_2$ are s and s1 and $s$ represents the serialNumber.

If you look at the HMAC construction you will see that the key elements are repeated in the hashing and there are multiple passes of the underlying hash, but the elements remain the same. If you only perform concatenation then you must make sure that there are no collisions for the concatenated elements (xy|z would be identical to x|yz).

Note that the code uses lossy character encoding (ASCII only represents a small part of the Unicode code set). It should be replaced with UTF-8. Currently the input must be validated beforehand to only contain ASCII, but using UTF-8 in the code would add a layer of defense.

So in the end the protocol is fine. It should however be clearly documented.


pwd-hash like algorithm which can be computed on paper

What you're after is fundamentally impossible. Password hashing algorithms are inherently slow. They're designed to be slow even on a computer. Otherwise they would not serve their purpose, which is to make brute force search infeasible. A fast password hash is a broken password hash. You cannot possibly get anywhere near the requisite level of slowness with manual calculation.

For anyone with a computer, given a site-specific password that is calculated from a master password by hand, it will be trivial to go try billions of potential master passwords until they find a matching one.

And having potential multiple matches won't save you, because there can't be many of them, otherwise the number of possible site-specific passwords would be ridiculously low.


Things already known to adversary before planning an attack

I think usually companies use very standard and popular schemes that are known already to the cryptographic community since using a totally unknown scheme might have a huge data leakage which the company was not able to discover.

Definitely. And remind yourself that implementing cryptography is hard as well. Self made schemes may have side channel attacks, data leaks and whatnot.

Quite often the algorithms that are used are known in advance. They are in design documents, leaks by developers, can be determined from the protocol configuration directly, are specified to certification agencies etc. etc. etc. So we simply assume that Kerckhoff's principle applies.

This is also why cryptographers don't take people seriously when they are confronted with a ciphertext without specifying the algorithm. Finding the algorithms is generally not the problem we're trying to solve.

  I think these things are usually fixed while implementing the model. And even if these things are known, for example S-box in DES is known, it still won't change the security of the scheme. But even if the company tried to hide the above functions, can it actually increase the security of the data?

The same applies as in the above.

  I think this is mainly the information that separates the user and the adversary. But can you tell what are the other things that are hidden in practical implementations?

Anything that is known as a secret. That includes keys, but also passwords, PIN, biometric data (where applicable). Besides keeping things secret, there are of course also other counter measures such as access conditions, number of retries and whatnot. A system never solely relies on cryptography, i.e. cryptography is never the solution, but it may be part of a solution.

  My assumptions are based on the quote that one should only use encryption schemes that are trusted by the cryptography community. Else there is a high probability that there can be an unknown leakage that an adversary can exploit.

Correct. As Bruce Schneier famously summed it up:

  Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break.

with a corollary from Cory Doctorow :

  any person can invent a security system so clever that she or he can't think of how to break it.


Relation between "P is not equal to NP" and "Existence of One-Way Function"

Why can we not conclude that if P ≠ NP, then there exists a one-way function?

Because so far no one has been able to prove this statement, see here.

The statement "if one-way functions exist, then $P \neq NP$" is an implication, which just goes one way. If we build the contrapositive, we get "if $P = NP$, then one-way functions don't exist".

On the list of logical fallacies, we can find:

Affirming the consequent, which is basically just building the converse (turning around the direction of the implication).
Denying the antecedent, which just is an inverse of both sides of the implication.

Those are (more or less) common errors regarding logic, and only the contrapositive does not change the actual meaning of the statement. Both inversion and conversion alone do not preserve the meaning - and thus are invalid if you want to prove a statement.

  Is there a polynomial time computable function that is hard to invert in the worst case and isn't one-way

Any NP-complete search problem gives you a candidate for that. That is exactly the difference between search problems in the class NP and one-way functions: The former are defined with regard to the worst-case and the later are defined for the average-case. This is also why NP-complete problems are less interesting in cryptography, where it can be not enough if only the worst-case of a problem is hard.


Is storing the hash of a key together with ciphertext encrypted with that key secure?

I think this is generally not a good idea, for two reasons.

First, do not generate a key as a hash of a passphrase.  Where possible, you should try to avoid deriving cryptographic keys from passphrases, as passphrases rarely have enough entropy to make a secure crypto key.  If you must derive the crypto key from a passphrase, then be sure to use PBKDF2 (or similar key derivation function), which is specifically designed to mitigate (but not eliminate) some of these risks, by making key derivation a slow process.

Second, if the key is derived from a passphrase, I do not recommend storing a hash of the key.  This may make it easier to mount exhaustive passphrase-search attacks, including facilitating construction of rainbow tables that map from the hashed-key to the original passphrase.  Instead, simply use authenticated encryption.

If you use authenticated encryption, there's no need to store a hash of the key.  You can tell whether a key is correct by trying to decrypt and seeing whether the decryption is authentic.  If it is authentic, you're good; if it isn't authentic, you've got the wrong key.

And you probably want authentication anyway, so this kills two birds with one stone.


Why is AES-SIV not used, but AESKW, AKW1?

No, AES-SIV is just newer. There are currently no published weaknesses (to my knowledge).

There are however a few practical inefficiencies:

the fixed locations of the SIV (/ authentication tag) can be a bit tricky to work with, as it means that the wrapped key data cannot be stored in the same place as the unwrapped key data;
it's a two pass protocol, which requires a bit more work.

The other wrapping methods have been standardized as well and are not broken in any significant way. So there is no big incentive to shift to SIV, even if it has the deterministic integrity protection property.

Many keys are stored in key stores rather than being wrapped individually (although combined approaches are used as well). A key store is likely to have no need for a deterministic algorithm such as SIV.

So it's an educated guess that AES-SIV is not implemented much due to lack of (commercial) interest.

Note that we're still in the process of moving out SHA-1 in favor of SHA-256. There is a very clear reason to do so, and SHA-3 is already out as well. The security field is not known for speedy transitions, even though it is just half a century old.

EDIT > 2yrs later: currently there seems to be a bit more interest to avoid the dire consequences of IV reuse for CTR mode and all authenticated ciphers (CCM, GCM, EAX etc.) that rely on it. That may speedup the use of AES-SIV and it's sibling, AES-GCM-SIV.


First of all, note that, SHA-256 operates on a minimum of 512-bit messages. The message is always padded to be a multiple of 512-bit ( see padding below). For double SHA256(SHA256(m)), after the first hash, the result is padded to 512-bit.

padding: The SHA-256 message format |L|1|0..0|message size in 64 bits|. L is the original message bits to be hashed, it is followed by 1, and many zeros except the last 64-bit so that the padded message is multiple of 512-bit, minimally. The last 64-bit is the message size. The maximal message that can fit into one 512-bit hash block is 447-bit.

So, if $x = \operatorname{SHA256}(m) $ the it will be padded as

| x 256-bit| 1 | 0000's 191-bit | 64-bit size of x) |

for the next SHA-256 calculation.

Now, the input-out space will be exactly 256-bit. In this case, we don't know it is one-to-one or not. The space is huge for calculations. If it is one-to-one then it will be a permutation, too. There are $2^{256}!$ permutations and there are $(2^{256})^{(2^{256})}$ functions. It will be amazing if it is a permutation. For simplicity, take 5-bit as an example, there are 32! permutations ~112-bit and there are $32^{32}$ functions ~161-bit. If we consider that the restricted SHA-256 is a randomly selected function then the probability of being permutation is around $\frac{1}{2^{50}}$. See a glimpse from WolframAlpha in a logarithmic scale.

  Since SHA-256 is supposed to be a one-to-one function

SHA-256 is not a one-to-one function. It is a one-way function i.e. you cannot revert it. Since the minimum input size 512-bit and the output size is always 256-bit, there is no way to be one-to-one.

  Would this be a bijective mapping? or Surjective mapping?

It would be surjective mapping.

  But if it is not injective, then SHA-256 cannot be one-to-one function for longer message (>256-bit input).

It is not one-to-one.

  Would SHA-256(SHA-256(x)) produce collisions?

If we consider that you are talking about hashing bitcoin public keys, it has 33 bytes compressed and 65 bytes uncompressed public keys.

If the key is uncompressed, it has 520-bit therefore by the pigeonhole principle there will be collisions.

If the key is compressed, it has 264-bit again therefore by the pigeonhole principle there will be collisions, the output is 256-bit.

Note that SHA-256(SHA-256(x)) will be still collision-resistant.

  Can such mapping be used, in any way, to break the SHA-256?

See this question Weaknesses” in SHA-256d? for the nice answer of FGrieu.


What's going on with the complicated implementations for map_to_curve in draft-irtf-cfrg-hash-to-curve?

It seems to me that it should be simple enough to map an integer/field element $u$ to a curve point by just using $uG$ with $G$ being the generator for the curve.

That is indeed simple; however using it would forfeit the security properties of cPace.
Here's why; cPace essentially works by having both sides map the secret password (and some nonces) to an elliptic curve point, and then having both sides perform a DH operation with the elliptic curve point.  The general idea is that if you are an active attacker who has a guess of the password (and that guess is wrong), you won't know the secret the valid system (who does know the password) will use, and so you won't be able to predict the shared secret (or even be able to recognize it).
However, here is what an attacker could do with your password hashing scheme; the attacker can pick a password, and implement the protocol assuming that password was correct; that is, he generates a point $H = hash(password)G$, generates a random value $x$, computes $xH$, sends that to the system under attack; that system sends a point $J$ (which is his $yH$ value) and you compute $xJ$; the system under attack then sends a message encrypted based on the secret he computed.
If the attacker's guess of the password were correct, then both sides will generate the same secret, and so the attacker can decrypt the message - no surprise there.  However, suppose the initial password guess was wrong.  Then, what the attacker could do is takes a second password guess, and compute $H' = hash(password')G$ and compute $x' = hash(password) hash(password')^{-1} x$.  Note that the values $x'H' = xH$, and so with this password (and modified $x'$) we would have sent the exact same DH public value; so, we can then compute $x'J$ (based on the point the other side sent), and use that to compute the shared secret and then decrypt the encrypted message - if he second guess to the password was correct, then that would work.
He can perform the same procedure to allow him to check every password in his password dictionary; this is a violation of the security properties cPace is supposed to have, which is that, after a single exchange, the attacker can learn whether one guess to the password is valid, and absolutely nothing else.
The map_to_curve procedures are designed to avoid this - given two points generated by two different passwords, you are unable to determine the relationship between the two (and hence the above attack does not work).