Modes of operation are generally supposed to be independent of the underlying block cipher. They generally have a proof of security showing that the security of a system using said mode reduces to the security of the block cipher. However some modes, such as CTR, don't work well with block ciphers of short length (aka, old ciphers) and can leak information. Popular modes of operation should work equally well with all modern block ciphers.

You wouldn't use RSA in a mode of operation. Typically, RSA might be used to encrypt an AES key and AES would then be used in a mode of operation on the data.
AES is more secure than DES. There are attacks that leverage weaknesses DES's inner workings, while AES stands strong. AES also uses a larger block size (128 vs 64 bits), and small block sizes themselves have inherent weaknesses. Also, DES should not be used by itself, if used it should be used as TDES (triple-iterated DES) and TDES is very slow in software. (That's not a security feature, but it is a pragmatic issue.)

The provided link does mention the block size and speed issues. (And I think it was implied that DES was inherently weaker than AES, given that the question also asked about TDES (that is, DES iterated 3 times, which doesn't have the same weaknesses as DES).)

Briefly on RSA vs AES: They fulfill very different roles. RSA isn't "better" than AES, just useful in areas AES isn't (aka, asymmetric encryption). Conversely, RSA is much slower than AES and has many more caveats in implementation than AES, meaning it's easier to screw-up.


Is OTP with homomorphic encryption trivial?

For encryption by a determinisitic function as suggested by the question's notation $e(k,a)$, "perfect security" as asked is not possible, because the homomorphic property allows to decipher many ciphertexts. In particular, if we know the encryption of $1$, we can use it to find the encryption of $2=1+1$, thus decipher the unique ciphertext for $2$, and that extends to every positive integer. Notice that One Time Pad encryption is not a deterministic function either (encrypting the same plaintext multiple times usually yields different results).

Here is a trivial scheme that is homomorphic and information-theoretically secure, in the sense that a ciphertext leaks nothing about the value it conveys, even to an arbitrarily powerful adversary.

Plaintext consists of $b$-bit bitstring, assimilated to integers in range $[-2^{b-1},2^{b-1})$ per two's complement. Everything is big-endian.
Key is a One Time Pad of $2^k\,b$ bits, enough for $2^k$ encryptions.
For encryption, it is consumed $b$ bits from the OTP/key, and these are added modulo $2^b$ with the plaintext. The ciphertext consists of that, followed with the encoding over $k$ bits of how many ciphertext(s) where produced previously.
Addition of two ciphertexts is the addition modulo $2^b$ of their first $b$ bits, followed by the concatenation of what remains.
Decryption takes the ciphertext, extracts the first $b$ bits as an integer, and from this repeatedly subtract modulo $2^b$ the $b$-bit integer at position $i\,b$ in the OTP/key, for each integer $i$ of $k$ bits parsed from the rest.

That matches all the question's explicit goals. Notice however that (as pointed by Ella Rose's comments)

Whether a ciphertext was generated by encryption (and then when in sequence) or homomorphically generated (and then how) is in clear in that ciphertext, and distinguishible from random, contrary to e.g. Paillier encryption where ciphertexts are computationally indistinguishable from random.
The homomorphic property creates a link between plaintexts when one is obtained homomorphically from another, and we correspondingly loose the information-theoretic property that leaking a plaintext leaks nothing about any other.

Extensions:

The limit of $2^k$ encryptions can be waived with a more complex encoding scheme for $i$, and of course an arbitrary-length key/OTP.
For some use cases, what follows the encrypted count can be compacted. For example, when adding vote counts, it makes sense to forbid adding the same encrypted count multiple times. That allows to use a bitmap of fixed size for what follows the encrypted count, and combine disjoint bitmaps with bitwise-OR. Regular bitmaps can be further compacted.


Textbook RSA signature forgery when e=65537

The quoted answer is about a question with

To verify, the receiver checks that $\sigma^e \equiv m \pmod N$. (…)
Given $m \pmod N$ but an unknown $m$ (…)

Thus in the context it does not necessarily hold $0\le m<N$ as in the textbook RSA signature scheme of the original article. Rather, the question considers an hypothetical signature system where $m$ can be larger than $N$, and the message is signed as an appendix $\sigma\gets m^d\bmod N$, sent independently of the message.
The line of attack in the old answer is ridiculously complex for this setup. Here is a simpler attack that works for any $e$, and if the receiver checks $0\le\sigma<N$ in addition to the question's $\sigma^e \equiv m \pmod N$.
The attacker

chooses $\sigma$ freely in $[0,N)$, including $0$, and $1$ and $N-1$ which would simplify computation.
decides $m_0$, e.g. ending with an 0x00 byte acting as a $C$ string terminator
if $N$ is $n$-bit, decides that $m_1$ [to me appended to $m_0$ forming $m=m_0\mathbin\|m_1$ ] will be a bitstring of $b=8\lceil n/8\rceil$ bit
computes $m\gets m_0\,2^b+((\sigma^e-m_0\,2^b)\bmod N)$.

I'll make an example with $N=$RSA-2048, $e=2^{16}+1$, $\sigma=3^{1291}$, message $m$ printing as the 15-byte A test message. in ASCII. Try it online!.

That said, the old answer was bogus, I fixed it; and the present question is right to state that with $0\le m<N$ (common in textbook RSA), an attack is possible for very small $e$ like $e=3$ but fails for $e=65537$ and usual size of $N$.


Tibor Jager (author to the first paper linked in question):

  "There is no implementation yet. Given that there are no really efficient Witness Encryption schemes yet, the construction so far is rather theoretical."


Merkle trees instead of the Sponge or the Merkle-Damgård constructions for the design of cryptorgraphic hash functions

Is there any reason why don't more cryptographic hash functions use a
  Merkle tree-like construction directly instead of just adding them as
  a way to allow parallelism to existing hash functions on top of the
  Merkle-Damgård or the Sponge construction?

The reason is that a Merkle tree comes with computation overheads that the serial hash functions do not have. Such a Merkle tree is less efficient if executed sequentially, compared to the latter. In fact, its memory usage is proportional to the height of the tree (For further information, see this paper which considers constructions on top of hash functions). Furthermore, if you want to use multithreading to provide a parallel implementation of your tree-based hash function on multi-processors/cores, you will have to cope with synchronization costs.

For software applications, it makes sense to favour general-purpose computers. If you are a cryptographer and you want to design a hash function, you will focus at first on security and sequential execution performance, and then on parallelism (as an option). Note that a sequential execution of the mode of operation does not prevent using a SIMD implementation for the iterated primitive.

  To my knowledge there are multiple Merkle tree-like structures that
  provably reduce the security of the whole construction to the one of
  the underlying primitive...

Sakura coding was proposed to allow anyone to construct his own tree-based hash functions, without worrying about security. For this purpose, this coding is assumed to be sufficiently flexible.

  It also happens that in order to exploit parallelism some hash
  functions have modes which make use of Merkle trees, such as the
  tree-hashing mode of BLAKE2 and ParallelHash (not a Merkle tree per-se
  but still).

You are considering that a Merkle tree is a classic binary tree-based hash function with depth in $O(\log n)$. Most people consider a Merkle tree as a synonym of hash tree, i.e. any "tree structure+hash of child nodes".  For instance, ParallelHash and KangarooTwelve that are based on trees of height 2 can be considered as a kind of Merkle tree. They are using trees of height 2 probably for a question of resource usage (and simplicity). If you are interested in parallel hashing with a focus on resource usage trade-offs, see again these propositions.


Is the AES-GCM encryption using the SHA256 hash of the plaintext as IV secure?

No, because in order to decrypt it you must pass along the SHA-256 hash too, and now you have leaked a public function of the original message, which an adversary can use to efficiently test a guess offline about what the original message was.

If you want a deterministic authenticated cipher, you might consider an existing construction like SIV that has been studied already.


Is a layer of classical encryption plus a layer of post quantum encryption equivalent to a classical/post quantum hybrid?

From your description, I am picturing your setup like this:

Outer encryption (server decrypts and re-encrypts):

client1 <----> server <----> client2

Inner encryption (server passed encrypted blobs on)

client1 <----server----> client2

Your question:

  Would it be accurate to tell our customers that a layer of classical public key based encryption covering a layer of post quantum public key based encryption is an roughly equivalent to replacing one layer of the encryption with a classical/post quantum hybrid?

I'm going to go with No. Reasoning: the idea of Classical+PQ schemes was born by considering two separate threat models:

The attacker has a quantum computer.
The attacker knows about a zero-day weakness in Kyber, New Hope, SIDH, wtv PQ crypto you choose. The risk if this is "high" because PQ schemes have not yet had the decades of public scrutiny we would like in a cryptosystem.

The goal of creating hybrids is to couple these two threat models by requiring an attacker to have access to both a quantum computer and a zero-day against the chosen PQ cryptosystem.

Let's see how your proposal stacks up:

An attacker with a quantum computer can successfully man-in-the-middle your classical outer TLS sessions. This doesn't give them access to plaintext messages, but is certainly a partial break of your system, and may have other security implications, for example if any usernames/passwords, or identifying information are sent over this TLS connection.
An attacker with a zero-day against your PQ crypto is not a direct attack, but it becomes a full break if they can compromise the server, or if you are worried about insider threat from your admins.

So it looks like your proposal isn't completely broken, but is certainly not what a customer would expect if you tell them it's a classical/post quantum hybrid, and is a weaker security model then replacing one or both layers with proper hybrid schemes.


How to select a good scale for letter frequency in a text?

You can compute a statistical distance measure between the observed letter frequencies in your candidate plaintext and the typical letter frequencies in English text.

There are a number of different ways to measure the similarity between two statistical distributions, and I'm not aware of any theoretical or empirical studies on which of them would be optimal for recognizing correctly decrypted plaintext.  However, in practice, the specific choice of distance measure seems to be of secondary importance compared to things like the amount of ciphertext available, knowledge of the nature of the plaintext, and the choice of which statistical features of the plaintext (e.g. individual letter frequencies, pair frequencies, vowel/consonant frequencies, etc.) to measure.

Thus, I'd suggest starting with something simple, like the total variation distance, which can be calculated simply by taking the difference between the observed and the expected frequency of each letter and summing their absolute values together, or the $\chi^2$-divergence, for which you need to sum the squares of the differences between the observed and the expected frequencies, divided by the expected frequency.

The full formulas also involve some constant factors that only depend on the message length, but for simple comparison purposes, the raw sums are enough.  The $\chi^2$ distance is particularly useful if you need to estimate the absolute likelihood of a message being generated according to some given (e.g. uniformly random) distribution, although this requires some additional steps that are not needed for simple ranking by relative likelihood.


The relationship between Auth Data and Plaintext can be compared with that of a network packet header and payload. Modern ciphers provide provision to "authenticate" additional data that's not encrypted so that more robust protocols can be designed. Of course, if you don't have header, you can pass an empty bit string to it.


a one-way function, which given an input would generate an output that is unique for that input.

A one-way function does not guarantee uniqueness of outputs.
The definition of a one-way function gives us that given an output $y = f(x)$, is hard to find any preimage $x^*$ of $y$ for which $f(x^*) = y$ holds.

Discrete logarithms and factorials are, as far as my knowledge goes, necessary to create one-way functions.

Factorials? You probably mean the factoring problem? I haven't head of any crypto that uses factorials.
We don't know if these are necessary.
Ciphers like AES are one-way, given that the adversary doesn't have access to the key: it's hard to find any plaintext that encrypts to a given ciphertext. However, we don't have a proof that these symmetric primitives are in fact secure.
Additionally, we don't even know if they are sufficient.
If P = NP, one-way functions don't exist. Neither DL nor factoring would be computationally hard problems.

That being said, is there a way to create random one-way functions, so that:
each of them would give the same output for the same input
and, each of them would be sufficiently unique to the others?

Is your first requirement, that the function is indeed a function? I.e. that whenever you supply an input $x$ to the function $f$ you will always obtain the same output?
If so, then yes - all one-way functions are functions.
As for your second constraint - you would have to specify some metric for sufficiently unique.
In the random oracle model, it is easy to construct such a function:
Given $H(\cdot)$, a function that behaves like a random function, we can construct a function family $H_s(x) = H(s \| x)$ (where $\|$ is concatenation and $s$ a random string $\in \{0,1\}^n$ for some length $n$).
Each of these functions $H_s(\cdot)$ will behave as a random function, is different from every other function, and will be hard to invert.
I'm not sure if I've answered your question fully, let me know if I should elaborate on some part or have misunderstood your question!


Complex Numbers on Elliptic Curves & Usage in Tate Pairing

Fix a field $k$.  Consider the polynomial $x^2 + 1$ in $k[x]$.  If $x^2 + 1$ is irreducible over $k$, then obviously the quotient $k[x]/(x^2 + 1)$ is also a field, of $\#k^2$ elements if $k$ is finite.  Note that $x^2 + 1 \equiv 0 \pmod{x^2 + 1}$, so $x^2 \equiv -1 \pmod{x^2 + 1}$; hence if we take any linear polynomials $f_0 = a_0 x + b_0$ and $f_1 = a_1 x + b_1$, we can work out the product modulo $x^2 + 1$ by the standard rules of arithmetic, substituting $-1$ wherever we see $x^2$:

\begin{align}
  f_0 \cdot f_1
  &\equiv (a_0 x + b_0) \cdot (a_1 x + b_1) \\
  &\equiv a_0 a_1 x^2 + a_0 b_1 x + b_0 a_1 x + b_0 b_1 \\
  &\equiv a_0 a_1 \cdot (-1) + a_0 b_1 x + b_0 a_1 x + b_0 b_1 \\
  &\equiv (a_0 b_1 + b_0 a_1) x + b_0 b_1 - a_0 a_1
  \pmod{x^2 + 1},
\end{align}

which, as it happens, is exactly the same arithmetic as for the familiar complex numbers, because $\mathbb C \cong \mathbb R[x]/(x^2 + 1)$ can be constructed exactly this way.  Drawing on the analogy, we name the indeterminate variable $i$ rather than $x$ for the polynomials in $\mathbb F_{11}[i]$ so that we can write $i^2 = -1$ in the field $\mathbb F_{11^2} \cong \mathbb F_{11}[i]/(i^2 + 1)$.


Disclaimer: I use Coq on daily basis...

  I have seen in some places that people use formal verification and/or computer-aided verification for cryptography.

To my knowledge, there aren't that many places that do such a thing.

First, let's define our concepts:

Formal Verification: The act of proving the correctness of algorithms with respect to a certain formal specification or property, using formal methods of mathematics.

Computer-assisted proof: A proof that has been at least partially generated by computer.

Some examples (in cryptography):

Verification of a Cryptographic Primitive: SHA-256 (paper)
Formal certification of game-based cryptographic proofs (PHD)

And some reading:

A gentle introduction to formal verification of computer systems by abstract interpretation (paper)
A Foundational Proof Framework for Cryptography (PHD)
Computer Verification in Cryptography (paper)
Probabilistic Relational Verification for Cryptographic Implementations (paper)

How does it work?

In formal methods (whatever the domain) there are two approaches:

Specification $\rightarrow$ Software
Specification $\wedge$ Software $\rightarrow$ Prove the software's correctness.

In most cases, the first method is the one used. Why? Because it is easier to start with a formal specification and then, incrementally, through proven steps, eventually get to the software (which is therefore proven). As an example, this certified compiler:

For example in the Method B, the process is the following:
$$DEFINE\ /\ SPECIFY \rightarrow PROVE \rightarrow  REFINE \rightarrow PROVE \rightarrow  \ldots \rightarrow IMPLEMENT$$

Formal verification uses the Hoare logic, a set of rules that allows us to reason about programs. It is based on sequent calculus and natural deduction. It relies on the Hoare triple:
$$\{P\}\ C\ \{Q\}$$
When the precondition $\{P\}$ is met, the execution of the command $C$ establish the postcondition $\{Q\}$. If the command $C$ goes from a state $s$ to a state $s'$.
$$C: s \rightarrow s'$$
Then you will have to prove:
$$\forall\ s\ s', P[s] \implies C : s \rightarrow s' \implies Q[s']$$
But we prefer the Hoare triple notation (lighter).

As an example, this is the rule for $SKIP$ (aka do nothing):
$$\frac{}{\{P\}\ SKIP\ \{P\}}$$

And this is the rule for the sequence :
$$\frac{\{P\}\ C_1\ \{Q\}\ \ \ \ \ \ \ \{Q\}\ C_2\ \{R\}}{\{P\}\ C_1 ; C_2\ \{R\}}$$
This notation is read as :
"If $\{P\}\ C_1\ \{Q\}$ (is $\text{True}$) and if $\{Q\}\ C_2\ \{R\}$, I can infer $\{P\}\ C_1 ; C_2\ \{R\}$.

A proof is therefore built from bottom to top : if you want to prove $\{P\}\ C_1 ; C_2\ \{R\}$, you will need to prove there is $Q$ such as $\{P\}\ C_1\ \{Q\}$ and $\{Q\}\ C_2\ \{R\}$.

Some readings on Hoare logic:

Background reading on Hoare logic (course)
Handout C2: Reasoning About Code (Hoare Logic) (course)
Software Foundation (self study course, highly recommended if you want to get into the domain).

The tools

In formal methods, there are two kinds of tools:

the fully-automated prover
the proof assistants

The first are mainly based on SMT (satisfiability modulo theories) such as Atelier B and Alt-Ergo.

The second ones are based on pure logic. You provide it with lemmas (helping theorems), and this will make sure that every step you do in your proof is right. It is a very thorough process, quite slow. But at the end you know how your proof works and that it is correct because you did not miss a hypothesis. The process, which can be frustrating, will make sure that the proof works.
The main proof assistants are the following: Coq,
Isabelle, Agda, Fstar and HOL.

The tools you mentioned (ProVerif, CryptoVerif) are not dedicated to cryptographic primitives, but protocol verification. I do not know them, so I will not comment. Other tools on the same subject do exist. For example:

CertiCrypt
EasyCrypt (tutorial)

And yes, they are based on Coq.

In C, in order to be able to verify your code matches your specification (such as what has been done for $\text{SHA-}256$), one need to extract the semantic from the code. This could be done using the Verifiable Tool Chain or Why3. The first one will provide you a Coq file from which you will be able to start your proofs. The second one, given C ASCL instrumented code, will use frama-c and try to prove the properties with the SMT provers named above. On failure, it generates goals and asks you to prove them with Coq.

In Cryptography (and Mathematics)

I already mentioned the idea of proving protocols (cf EasyCrypt et al.), for cryptographic proofs, the idea is basically the same. Specify using logic properties.

Coq example (trivial to prove by hand for a undergrad student):
$$\forall\ f g, f \text{ is injective} \implies g \text{ is injective} \implies g \circ f \text{ is injective}$$

Require Import Coq.Sets.Image.

Theorem injective_trans:
forall A B C (f: A -> B) (g:B -> C) (h:A -> C),
(forall x, h x = g (f x)) -> injective A B f -> injective B C g -> injective A C h.
Proof.
intros A B C f g h H_h_equal_g_f H_f_injective H_g_injective.
unfold injective in *.
intros x y H_h_x_y.
apply H_f_injective.
apply H_g_injective.
rewrite <- H_h_equal_g_f.
rewrite <- H_h_equal_g_f.
apply H_h_x_y.
Qed.

Here is a list of famous proven theorem in Coq.

Final words

Security bounds in Keccak has been proven with the aid of a computer. But their process was different: they exhaustively generated the trails and showed the properties. Thus it was computer aided, but not verified.

And finally, a recent paper from FSE 2016: Verifiable side-channel security of cryptographic implementations: constant-time MEE-CBC

As SEJPM pointed out, this paper is also another kind of approach (more game based). They created an analyzer that generated a cipher scheme that satisfied the AE scheme. However, I don't know whether they have proven their properties by hand or used a proof assistant (which might be possible given that they used Ocaml to code their analyzer).

You might also be interested in the course Gilles Barthe (EasyCrypt team) has done here.

I do not know if my answer has been helpful. I know it is not mainly focused on cryptography, but I hope it will give you a some idea of how things work.


If $m$ divides $N$, then you get the uniform distribution over $[m].$

Let $k=N-\lfloor N/m \rfloor m.$ Note that $k\geq 0,$ with $k>0,$ if $m$ does not divide $N.$ When you reduce $Z$ modulo $m$, due to wraparound, the smallest $k$ values $0,1,\ldots,k-1$ are "hit" an extra time, as $Z$ varies from $0$ to $N-1.$
Thus the probability distribution of $W=Z \pmod m$ is:

$P[W=u]=\frac{1}{N}(\lfloor N/m \rfloor +1)\quad w\leq k-1,$

and

$P[W=u]=\frac{1}{N}(\lfloor N/m \rfloor)\quad k\leq w\leq N-1.$

Now sum these values absolute difference with $1/(N/m)$ which is the value of the uniform distribution at each point.

For part 2, group via row or column for each marginal distribution and apply a similar technique, to get the individual distances. Now look at the joint taking care to scale correctly when you sum over the whole array for the statistical distance of the joint from the uniform.


What are Cryptographic Multi-linear Maps?

Ok, I will start with a cryptographic bilinear map.

Cryptographic Bilinear Map

A cryptographic bilinear map $e: G_1\times G_2 \rightarrow G_T$ as the name says is a map that is linear in both components, i.e., it holds that for all $g\in G_1$ and $h\in G_2$ and all $a,b\in Z_p$ (where $p$ is the order of all groups) we have that $e(g^a,h^b)=e(g,h)^{ab}$.

For cryptographic use we want a setting
where the discrete logarithm problem is hard in $G_1,G_2$ and $G_T$ (typically one requires also that variants of the computational Diffie Hellman problem are hard and the decisional Diffie Hellman problem may be easy in $G_1$ - that depends on the type of pairng, e.g., symmetric or asymmetric and w/o efficient computable isomorphisms from $G_2$ to $G_1$). Furthermore, we want $e$ to be efficiently computable and non-degenerate, i.e., if $g$ and $h$ generate $G_1$ and $G_2$ respectively, then $e(g,h)$ generates $G_T$ ($e$ which maps to $1$ in $G_T$ is useless).

For pairings there are various Diffie-Hellman like assumptions (bilinear Diffie Hellman assumptions), e.g., in the setting of $G_1=G_2$ and $g=h$ the bilinear CDHP states that it should be hard to compute $e(g,g)^{abc}$ given $g^a$, $g^b$ and $g^c$.

Groups $G_1$ and $G_2$ that we know today where we find such a pairing $e$ are (subgroups of) rational points on elliptic curves (or abelian varieties) over finite fields and the group $G_T$ is a subgroup of a multiplicative group of a finite field. The map $e$ thereby is a variant of the Weil or Tate pairing.

Cryptographic Multilinear Map

Now, a cryptographic multilinear map for $n>2$ is a $n$-linear map $e:G_1\times \ldots \times G_n \rightarrow G_T$, i.e., a map that is linear in all $n$ components. Essentially one requires the same as above but you want to have that it be $n$-linear, which basically means that $e(g_1^{a_1},\ldots,g_n^{a_n})=e(g_1,\ldots,g_n)^{\prod_{i=1}^n a_i}$ and that it is non-degenerate. As in the bilinear case we can also define multilinear CDHP etc (see for instance here).

Such cryptographic multilinear maps would be a very nice tool if they would work as in the pairing setting (as envisioned in the paper linked above). However, the recent constructions for cryptographic multilinear maps are based on tools from constructions of fully homomorphic encryption schemes (AFAIK there is a construction using ideal lattices and one over the integers) and there the encodings of the elements are noisy and thus are approximations of the ideal case and not that nice as within the pairing setting working with cyclic groups. Note that some papers simply assume the existence of a multilinear map that behaves like an extension from the known bilinear map setting with the associated Diffie Hellman assumptions  (although it is not yet known if such multilinear maps exist). Worth mentioning is the first candidate construction for indistinguishabiliy obfuscation that relies on a concept related to multilinear maps (which also yields functional encryption for circuits).


Would SHA1 be broken by sheer brute force, even if it had no weaknesses of its own?

Yes, it is now conceivable to find a SHA-1 collision by brute force.

The general method is outlined in Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999; free earlier version available from the first author's website; expands on an article presented at CACM 1994). It uses local search iterating hashing; when a distinguished value (say with a certain number of zeroes in low-order bits) is found, it is reported to a central location; enough findings lead to a collision. It is expected that less than $2^{82}$ hashes (and comparatively little extra work) are required to find a collision.

By May 2018, the bitcoin mining aggregate hash rate is reportedly $30\cdot10^{18}$ SHA-256d per second ($2^{81.1}$ per day), where SHA-256d uses two SHA-256, and SHA-256 is roughly as costly as SHA-1. The ASICs predominantly used for that can not be directly repurposed for a SHA-1 collision search: they use SHA-256d, not SHA-1; and as an aside they hash incremental values, rather than iterated ones. However the technology is there.

Thus the energy spent in a day of bitcoin mining is enough to find a SHA-1 collision by brute force, hypothesizing the same technology is used. The collision found would be a random one, with chosen prefix decided at start of attack, and could not be detected.

And it might well be that significantly less work would be enough to find a collision that evades detection using the current "fingerprint" method, by using specially crafted (but less efficient) differentials than used to find the first collision reported.


Actually you have a bug in your step of key generation, it should be $Q_A=d_A \times G$ and you want to have a point $G$ of large prime order $n$ such that the ECDLP is hard on the group.

The last check ensures that the public key $Q_A$ is a point of order $n$. If this is the case, then $Q_A\times n = (d_A \times G)\times n = d_A\times(n\times G)=d_A\times O=O$.

This check seems simply to rule out the generation of public keys that lie in a small order subgroup (and thus could be easy to break) - which makes no sense if you have a prime order group but can happen if you have an almost prime order group (you have subgroups of order of divisors of the cofactor). Just a mechanisms to check if the key generation did not generate such a key for you (it should not happen in practice that you generate such a keypair), but the implementation may be messy and you can check that with this test.


SHA256: Padding a 512 bits length message

Any message that is 448 bits or larger is padded beyond the block size, and runs a second iteration of the compression function. If messages beyond this limit excluding intervals of 512 bits seem to work correctly, it is probably a simple math error. If it was an endianness issue, all lengths greater than 1 would fail.

I assume you are using a byte oriented approach to the design, therefore the padding byte [80] starts the first block, followed by [00] valued bytes, followed by the 64-bit length [0000000000000200], making the block look like this:

80 000000000000000000000000000000000000000000000 0000000000000200


What is the maximum cofactor of elliptic curve used for ECDSA?

The X9.62 ECDSA standard does not specify a bound on permissible cofactors (though it only records how to validate cofactors up to about $\sqrt p/4$). The Certicom SEC1 document only allows cofactors up to $2^{t/8}$ where $t$ is the bit size of the field. In theory then, quite large cofactors might be in use somewhere. In practice people almost always preferred to use Weierstrass curves with cofactor 1 a) for efficiency and b) to avoid possible weaknesses with unverified parameters. I believe that all of the NIST standard curves have cofactor 1 for example. By contrast Curve 25519 allows a cofactor so that it can have a compatible Edwards curve representation (Edwards curves are more efficient and have better anti-sidechannel properties; their order over prime fields is always divisible by 4 however). Similarly Curve 448 has a cofactor of 4 and an Edwards form.
ETA: kelalaka points out that 25519 pre-dates Edwards curves; it was a happy coincidence that it was Edwards compatible.
In pairing-friendly cryptography larger cofactors can be quite common as there are very stringent conditions on the curve order. Such curves are however not generally used for ECDSA.


Does chacha20-poly1305 require new key for every encryption process?

You do not require a new key. You use a different initialization vector (IV) for every message.

As long as you use a different pair of (key, nonce) for each message you retain the confidentiality and integrity of messages. The nonce is the initialization vector.


There is typically no private key on the client side.
At a high level the process goes something along the lines of (this is a simplification, read the protocol specs if you want the fine details)
The client sends the server a "hello" message with info on supported protocols and ciphersuites.
The server chooses a cipersuite and protoocol version and sends the client details of the ciphersuite and sends it's certificate. The server is suppose to respect the clients ciphersuite preferences, but not all servers do.
The client validates the certificate using the certificate chain to decide whether it is talking to the right server.
The client and server agree a master shared secret for the session and the client validates that the server it is talking to holds the private key for the certificate. Theres a couple of ways this can be done, the simplest is that the client generates the secret, encrypts it using the server's RSA public key and sends it to the server which decrypts it using its private key. The downside of that approach is it doesn't provide "forward secrecy". An alternative approach, is to use ephemeral diffe-hellman key exchange (or it's elliptic curve variant) to agree on a secret and use RSA signatures to validate that the key really was agreed with your server (and not agreed with a man in the middle). Most modern clients prefer the elliptic curve diffe-hellman ciphersuites.
Session keys are generated from the master shared secret and encrypted communication begins using a symetric cipher and those sesion keys.


Does semi-honest adversary eavesdrop honest parties communication?

Typically in the MPC literature it is assumed that there are pair-wise secure channels between all parties. So I would say it is the latter in the case of your question.


Does failure of indistinguishability of encryptions imply lack of CPA-security?

Faliure of indistinguishablity of encryptions under a eavesdropper does imply faliure of indistinguishablity of encryptions under a chosen-plaintext attack. But the converse is not necessarily true (ex. OTP)
The aim of CPA-secure is not to decrypt previously unobserved ciphertext but to pass the distinguishability test after a set of (plaintext, ciphertext) observations.


How to provide partial confidentiality and full integrity for a protocol message?

Basically what you want is a authenticated encryption with associated data (AEAD) encryption scheme, of which there are several already available in various libraries.  So just see what is available on your system and use one of them.


Trying to understand the struct HkdfLabel from tls1.3 RFC8446

Section 3 explains the data structures and their representation as octet strings (or byte strings: this RFC uses “octet” and “byte” interchangeably). See in particular §3.1:

Multiple-byte data items are concatenations of bytes, from left to right, from top to bottom.

An HkdfLabel is the concatenation of 2 bytes for length (big-endian, see §3.3), 7 to 255 bytes for label, and 0 to 255 bytes for context. §3.4 explains the notation <7..255> it means between 7 and 255 bytes inclusive. The length of the HkdfLabel can therefore be anywhere from 9 to 514 bytes.
The length field in the HkdfLabel returned by HKDF-Expand-Label is the value that was passed as the Length argument. When it's called from Derived-Secret, this is the length of the hash in bytes (not bits) (§7.1: “Hash.length is its output length in bytes”).
The first 6 bytes of label are 74 6c 73 31 33 20, the ASCII encoding of "tls 13" (§7.1: “The labels specified in this document are all ASCII strings”).
"tls13 " + Label is the concatenation of a 6-byte string with Label. Since the result must be at least 7 bytes long, this effectively forbids empty labels, which I can't find stated explicitly anywhere. There is no padding or truncation. Note that once again, these are lengths in bytes (octets), not bits. The label must also be at most 249 bytes long to fit.
Context can be anywhere from 0 to 255 bytes


Is it possible to get the PGP public key from PGP message?

No, the PGP format doesn't contain the public key of the sender. But it does include a key ID of the key (pair) so that you know which private key to use to decrypt the message. It is rather easy to verify this by reading the OpenPGP specifications which defines the packet format(s) used. Or you can take a look using gpg --list-packets --verbose.
It is possible to lookup the public key (which in the case of PGP acts more like a certificate, containing more information than just the key value) using one of the various PGP servers. However, the use of these servers has become a problem in itself. Knowing the key ID is of little help if the key is not registered in a known key server or location (i.e. communicated out of band or kept locally).


Technically speaking, a side-channel attack by definition doesn't attack a KDF but a specific implementation of it. An example of an implementation would be the way macOS turns a user's password to a disk encryption key with PKDF2. A gZip application may execute the PKDF2 in a slightly different fashion.
The answer to your question is yes, because you can never know if a developer made a mistake, or something like that. If that isn't what you meant please clarify.


Is there any way to save Email encrypted in Database and used as normal later?

It looks like it is asked for deterministic symmetric encryption (and authenticated, because we can and should) in a decisively applied context. There are options for this, including some that can be built easily on top of primitives available now in most cryptographic libraries.
One would be: after normalizing the email (which is a difficult task of its own), build an IV from it using some MAC (HMAC-SHA-512 truncated to 128-bit will do¹), then AES-CBC² encrypt the email using that IV. In theory you need separate keys for the MAC and encryption, but with the stated algorithms disaster won't strike if you don't. Store the concatenation of IV and ciphertext with Base64 encoding in the database.
Decryption is just as normal for AES-CBC, and after decryption you can check the MAC.
Since the encryption is deterministic, you can search by encrypting again and searching the ciphertext (case sensitive).
That solves the problems of search, and protects in case of database leak only slightly³ poorly than normal encryption. But is does not solve two wider IT security issue:

securely storing the key(s)
preventing their abuse

Note: I have asked here if AES-GCM-SIV with fixed public IV would do.

¹ Using HMAC-SHA-256 could be less than academically correct for more than 128-bit key, but would most likely be OK in practice.
² With some standard padding like PKCS#7. AES-OFB would simplify padding, but is uncommon. AES-CTR would simplify padding too, and is common, but it's uncommon that a 128-bit IV can be used and that would be a problem here.
³ In the context, the loss of security due to use of deterministic encryption is that it allows comparison of emails in database dump(s), including between different users in the database, and between revisions including if a user changed email then went back to the original.


Mapping points between elliptic curves and the integers

I do not know of any general way to create the mapping you want (and if there was, it might turn into an efficient point-counting algorithm, which would be great), but you can do this on some curves.

Consider a prime $p$ equal to $2$ modulo $3$. In $\mathbb{Z}_p$, every value has a single cube root (because $3$ is then invertible modulo $p-1$). Then, look at the curve $y^2 = x^3+1$. For any value of $y$, $y^2-1$ has a unique cube root $x$, so there is a one-to-one mapping between non-infinity points on that curve and their $y$ coordinate in $\mathbb{Z}_p$. For completeness, map the "point at infinity" to the integer $p$, and you are all set: an easy bijective mapping between the $p+1$ curve elements, and the integers modulo $p+1$.

Moreover, this curve is pairing-friendly, with an embedding degree of only $2$ (because $p+1$ divides $p^2-1$). It also allows a distortion map so that you can have a symmetric pairing: if $\mu$ is a cubic root of $1$ distinct from $1$ (so an element of $GF(p^2)$, the field extension), then the mapping $m$ from $(x,y)$ to $(\mu x,y)$ is a morphism over the curve. Then you can define a pairing $e(P, Q)$, where $P$ and $Q$ are both points on the original curve (in $\mathbb{Z}_p$) as the Tate (or Weil) pairing computed over $P$ and $m(Q)$. This allows you to stay on the base curve as much as possible; only the pairing output will need the field extension.

Ben Lynn shows some details in his PhD dissertation (he calls that curve a "type B"). Note that since there is a pairing of embedded degree $2$, then discrete logarithm on the curve is "reduced" to discrete logarithm in the $GF(p^2)$ field; so, for proper security, $p$ must be at least 512-bit long.

Edit: A similar trick works for "type A" curves with equation $y^2 = x^3 + ax$ in $\mathbb{Z}_p$ for $p = 3 \mod 4$ and a constant $a$. For a given $x$, then exactly one of the three following situations occurs:

There are two distinct values $y$ such that $(x, y)$ is a valid point, and they are opposite of each other, so one is lower than $p/2$ and one is greater.
There is no valid $(x, y)$ point, but there are two valid $(-x, y)$ points for two distinct values of $y$.
$(x, 0)$ is a valid point, and so is $(-x, 0)$ (this one can happen only if $-a$ is a square modulo $p$).

So you can map the point $(x, y)$ to:

$x$ if $1\leq y \lt p/2$
$-x$ if $p/2 \lt y \lt p$
$x$ if $y = 0$

Then map the point of infinity to $p$, and you're done.


Convert homomorphically encrypted decimal number to homomorphically encrypted binary number

The question could be change to "How to evaluate mod $N$ under FHE". For CKKS scheme, there exist approximations for that: https://eprint.iacr.org/2018/153.pdf


Why does PHP crypt give this unexpected result

The algorithm called "bcrypt" (which is not the same as blowfish) accepts a salt up to 128 bits long. The bits are encoded similar to Base64, just using a different map from bits to characters. Thus the maximum length your encoded salt can be is 22 characters.

Your salt looks like anexamplestringforsalt. That's 22 characters long. Note that 128 bits divided by 6 (or $\log_2 64$) bits per character is actually 21 characters with 2 bits remaining.

Try replacing the final 't' with different characters. You will see that the result will always replace the 22nd character with one of . O e or u. The 23rd character and onward of the (actual 128-bit) salt are truncated, having no impact on the result.

The PHP crypt function, atleast for bcrypt version 2a, uses only the first 128 bits. Additional bits are silently ignored. When I look at the relevant PHP source code it seems like this is deliberate. (Whether this was originally intended or if this was added to keep backwards compatibility, I don't know.)

The "U" in anexamplestringforsaleU is actually part of the hash, not the salt.

The reason why the final character only may take on one of four values is because that is the number of values the final 2 salt bits can take on. The reason why it's limited to . O e or u specifically is because the final character of the radix-64 string encodes those last two salt bits as the most significant two bits of the radix-64-digit. The low four bits are all forced to zero. . O e and u correspond to radix-64-digit numbers 0, 16, 32, and 48 respectively.

The alphabet is reproduced below based on this source. (I split into four segments for sake of clarity.)

./ABCDEFGHIJKLMN
OPQRSTUVWXYZabcd
efghijklmnopqrst
uvwxyz0123456789

Notes:

Use the Password Hashing API instead of crypt. It's already installed by default, it has reasonable defaults, supports bcrypt and argon2, and can generate salts automatically. The crypt function is much more difficult to use correctly.

Look into using Argon2. It uses relatively large amounts of RAM as a means of making password cracking more difficult.

The correct verb to use to describe password stretching/verification algorithms is usually "hash" not "encrypt". Password hashing is a one-way process (only brute force can "reverse" it). Encryption uses a secret key and is reversible. crypt was deceptively named.

Blowfish and bcrypt are not the same algorithm. Bcrypt is merely based on Blowfish.


Suppose you know a way to distinguish a message encryption scheme of the form $$\operatorname{CTR}[E_k](n, m) = (E_k(f(n, 0)) \oplus m_0) \mathbin\Vert (E_k(f(n, 1)) \oplus m_1) \mathbin\Vert \cdots$$ for unknown $k$ from a uniform random string with probability better than you would get for CTR mode $\operatorname{CTR}[\pi](n, m)$ of a uniform random permutation.

Here $f$ is a standard injection from nonce/counter pairs to cipher blocks (say, $(n, i) \mapsto n \mathbin\Vert i$ on 96-bit nonces and 32-bit counters), $n$ is a nonce, and $m$ is a message $m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots$.  Note that there is always a generic birthday attack on CTR mode, so the premise is that you have a distinguisher with higher success probability than the generic birthday attack for the same number of queries to the oracle.

How could you use this to distinguish $E_k$ for uniform random $k$ from a uniform random permutation $\pi$?  You are allowed to feed in $f(n, 0)$ and throw $m_0$ into the mix if you know some $n$ and $m_0$ that lets you break $\operatorname{CTR}[E_k]$, for example—it is a chosen plaintext attack.


GoofyCoin question -- why pk, why not sk?

My question is, why does it say "signed by pk"... isn't the actual
  signing done using the "sk", and the verification done using the "pk"?

Yes. The actual signing is done by the "sk".

However, the signature is usually bundled with the public key which can be used to verify it. Thus it makes sense to more strongly associated the public key with the signature. Additionally it makes it trivial from a formal standpoint which public key to use for verification.

Furthermore, the mapping of public-key to private-key is 1:1 most of the time, making the choice of which key to use for indication here a matter of preference.


Yes. Iterating the hash like you do slightly increases the chance of collisions (as a hash function is not a random permutation, but an approximation of a random function): It is enough if two different passwords produce the same hash at any of the 100 steps, to produce the same final hash. (But as Thomas noted in a comment, the probability of collisions remains neglibly small.)

It is normally considered better to input the original password in the following iterations, too, this works against this effect: even if two different passwords give the same hash at step 39, at step 40 their hashes will be different again.

result = hash('sha256', result . usersalt . SITE_SALT . password);

On the other hand, iterating takes more time, and thus more computation power (both from you and a bruteforce attacker), which is good.

The bad news is that a fast hash like SHA256 is easily parallelizable, which means that the attacker can try hundreds of different passwords at a time on cheap hardware (like GPUs). Repeating the hash 100 times does not much here.

Instead, use a slow hash function which has some work factor parameter build in. One example is PBKDF-2 (which essentially does what you are doing, just with quite higher repeat counts), another example would be bcrypt (which builds on the key schedule algorithm of blowfish and needs about 4 KB of memory which will be constantly changed, thereby making implementation on standard GPUs ... inefficient), or the newer scrypt, where the needed memory is also depending on the work parameter (which means that you can only parallelize it if you have lots of memory available (and fastly accessible, too)).

Set the work factor so that the needed time is just acceptable for your users.


Do key collisions for symmetric ciphers exist?

The number of possible permutations of a block cipher are $2^n!$ where $n$ is the block size. A permutation maps all $2^n$ possible input blocks to $2^n$ possible output blocks. A key, with key space $2^k$ selects one of them. Although that's a huge number of keys, it is dwarfed by the amount of possible permutations.

Now it's not by definition impossible that the same permutation can be chosen by a key, but it is pretty unlikely. Such a key would be considered an equivalent key or - less specifically - a weak key. Many algorithms are designed to disallow weak keys. If it is possible to have the same permutation then it is likely to be present by design; you won't find one by chance alone.

Finding two keys that map a single specific plaintext to identical ciphertext or vice versa is much more likely. It depends on the block cipher details if this is anywhere near possible see this discussion on AES for more information.

For stream ciphers the question is somewhat more difficult. It probably suffices to say that the output of the stream cipher is determined by a key and an IV (sometimes fused into one, for instance in RC4). If the size of the key, IV and internal state of the stream cipher are large enough, you should not be able to find a large amount of repetition in the key streams generated for separate key / IV pairs.

It will be possible to find keys that generate small amounts of identical key streams. This is easy to see; about half of the keys should decrypt a single bit correctly. It may be impossible to determine if you'd have generated the correct plaintext though; you'd have to determine the two keys in advance.

The idea expressed above would also work for a block cipher in a streaming mode of operation such as CTR (counter mode).

These kind of questions have been asked, but they are tricky to find if you don't know the right terms - and probably even if you do.

Related is the question if algorithms contain back doors. In that case the attacker should be able to decrypt whatever the key value is though.

Deniable encryption is another somewhat related term.


The iPhone is built with encryption inserted automatically when writing to flash memory and decryption inserted automatically when reading from it. This happens with all files, all the time. There is no concept of "decrypting a file and then opening the decrypted file", as there would be on a PC.

No file can be decrypted without the proper key. Some files (such as the ones needed to start up the phone) are decrypted with a key that is always known to the encryption/decryption machinery. Other files are decrypted with a key that is only provided to the machinery once the phone has been unlocked.

That is why unlocking the phone is fast. All that happens is that an additional key is made available to the decryption machinery, so that it is able to decrypt files encrypted with that key.

All this is an over-simplification, since there are more levels of keys than this. The absolutely authoritative source, which is also remarkably easy to read, is Apple's own iOS Security Guide.


How do I prove that an encryption based on a multiplicative cyclic group is IND-CPA?

Here is how I would approach the proof (this is a sketch):

A proof with a similar approach can be found in the proof of Theorem 3.26 on p.89 of Introduction To Modern Cryptography.

Step 1) Prove that replacing $F_k$ with a uniform function $f$ only gives the adversary negligibly different advantage in the indistinguishability game. To do this, choose a distinguisher $D$ for the pseudorandom keyed function $F_{k}$. $D$ has access to an oracle that is either equal to $F_k$ or $f$. Have $D$ simulate a view of the indistinguishability game for $A$ by choosing random $i$ and having the oracle output either $f(i)$ or $F_k(i)$ ($D$ doesn't know which one). If $A$ is correct, $D$ outputs 1, otherwise $D$ outputs 0. Since $F_k$ is a pseudorandom function it follows that $A$ must win the game with the actual encryption scheme negligibly different amount than with the modified encryption scheme (where $F_k$ is replaced by $f$).

Step 2) Prove that the modified encryption scheme, where $F_k$ is replaced by $f$ is IND-CPA secure. This you can do via probability analysis. First by noticing that since $g$ is the generator of the group, every element in the group can be expressed via $g^{x}$ for an integer $x$. Therefore, since $f$ is uniform, $g^{f}$ is uniformly distributed in the multiplicative group $\mathbb{Z}_{N}^{*}$ . Next, since $g$ is the generator, and since $m\in\mathbb{Z}_{N}^{*}$, $m=g^{x}$ from some integer x. Therefore we can write $E(m, i, k) = m \times g^{f(i)} \bmod N = g^{x} \times g^{f(i)} \bmod N = g^{x+f(i)} \bmod N$. Since $f$ is uniform, $x+f(i)$ is also uniform and hence $g^{x+f(i)} \bmod N$ is uniform as well. Complete the proof by letting $q(n)$ be the upper bound of number of queries that $A$ can send to the Oracle of the indistinguishability game. The only way A has an advantage is if the same $i$ is used twice. if $i$ is uniformely chosen from ${\{0,1\}}^{n}$, then this probability is $q(n) \times 2^{-n}$ which is negligible.


Is H(k||length||x) a secure MAC construction?

This construction is not secure. It was proposed in this paper in a quick sentence for possibly fixing the insecure secret prefix construction from the other question: $\mathcal{H}(k||m)$. The author then proposes and analyzes an enveloping method: $\mathcal{H}(k_1||x||k_2)$.

An attack involving finding an internal collision applies to $\mathcal{H}(k||\ell_m||m)$. It is a bit complex, but if you are curious, it is "Proposition 4" in this paper (also see section 4.1, 1st paragraph). The authors also note that the construction involves additional assumptions on the hash function than the standard ones (collision-resistance, (second) preimage resistance). It is not as efficient of a break as the length-extension attacks on the other construction but it is theoretically a break relative to the security of HMAC.

I will also note that "unambiguously" encoding the length could be problematic. For example (using base 10 for readability), if I hash m=08 with length=2  and some k, then a length extension attack may find m=0896346218569465994320 which could be interpreted as length=20 and m=896346218569465994320. One fix to unambiguously delimiting the length from the message is to fix a certain number of bytes for the length, but you now no longer have a MAC that accepts arbitrary-length inputs.

In conclusion, the HMAC construction is very simple, accepts arbitrary length inputs, and does not rely on an encoding scheme to work.


Can RSA (theoretically) be used as a block cipher?

I can't see how RSA (assuming OAEP padding) can be used in normal block cipher modes. Its output is likely not pseudorandom, so it can't be used in CTR, OFB, or CFB mode. Its output is too large to be fed back in, so it can't be used in CBC mode. Using it in ECB mode would have the problem that blocks can be moved, duplicated, deleted, and replaced just like if you use ECB on a normal block cipher.

You're right about the CBC, OFB and CFB modes. Using RSA as drop in replacement will be troublesome anyway, because it would run into practical issues besides the security related ones already mentioned by fgrieu. Will the padding mode be compatible with such large block sizes? Will the implementations? What about buffers created to be about the same size of the plaintext input?

ECB in my opinion has the best cards. The main issue with ECB is that repeating plaintext blocks will be seen as repeating plaintext blocks by an attacker. This problem however is not present if you'd use RSA with e.g. OAEP padding. OAEP padding already has a random component, so you would not be able to see the repeating pattern.

You also state that ECB allows blocks to be "moved, duplicated, deleted, and replaced". This is however not just a property of ECB mode; it's a property of any mode that doesn't include integrity protection and authentication. You can simply remove this problem by authenticating the ciphertext with a digital signature - the asymmetric equivalent of a MAC. If you assume that you've distributed the full key pair to both parties you may even get away with using the same key pair as the padding would protect you against most if not all attacks.

Using RSA in ECB/OAEP mode of course has huge drawbacks with regards to performance, key management and overhead. It could also drain the secure random generator of the system. Furthermore, it seems that a symmetric cipher like AES is a whole lot more going for it with regards to security. So you'd probably downgrade your security level rather than upgrading it.

So yes, ECB is kind-of possible. If it wasn't you should not be able to encrypt multiple messages. Anybody implementing such a scheme would be considered out of hens mind by the cryptographic community though - and rightly so.

In the comments you further explain that

  ... but the idea is to use it similarly to how we use block ciphers today, as to avoid #1.

This would be impossible. Raw / textbook RSA is horribly insecure. You'd have to perform padding. Using the cipher in block mode of operation doesn't work. Furthermore, there is a problem with the highest bit of the input. With RSA you can deterministically encrypt something of size N - 1. N - 1 will not be on a bit boundary. That means that you'll always have a single bit of overhead. So even if it was possible to create a secure mode, you still could not use it as drop-in replacement.

ECB mode for textbook RSA is often used in textbook examples of RSA encryption with very small primes. After all of the above I hope I don't have to explain how horribly insecure that mode is; it breaks not just one but all of the rules.


What is the role of IV in Stream Cipher? Why is it needed and what is it's importance?

Take a cipher, any cipher, and suppose the key is used for multiple messages.

Suppose that two messages happen to be identical. If the ciphertext depends only on the key and the message, then the ciphertexts for these messages will be identical. This leaks information about the messages. There are scenarios where this doesn't matter, but conversely, there are scenarios where it matters. Therefore any cipher uses a nonce in addition to the key. In ciphers that use an IV (or something related such as an initial counter value), the IV is this nonce

The nonce must have at least the property that the sender never performs two encryption operations with the same nonce. (Encrypting distinct messages with the same nonce would leak the fact that the messages are distinct.) Depending on the role that the IV plays in the cipher, there may be additional constraints.

With a stream cipher, the effects of encrypting twice with the same key and without using a nonce are rather devastating. Write $M[i]$ for the $i$th bit of the message and $C[i]$ for the $i$th bit of the ciphertext; then $C[i] = S[i] \oplus M[i]$ where $S$ is the keystream. If $S$ only depends on the key, then an adversary who obtains two ciphertexts $C_1$ and $C_2$ obtains $M_1 \oplus M_2 = S = C_1 \oplus C_2$. Guessing one bit of one message automatically reveals the bit in the same position in the other message.

The remedy is to ensure that the same keystream is never used twice. This can be done by ensuring that the key is only ever used once, or by incorporating a nonce (an IV) in the way the keystream is derived from the key.


DHE parameters: which parameters need to be random each time?

TL;DR: $a$ and $b$.

For DHE in the multiplicative group modulo $p$, it is agreed on a large prime $p$ and an element $g$. This is typically long term, and there are standard public parameters, e.g. the 3072-bit MODP group of RFC 3526

After this, each time two parties A and B want a shared secret

party A draws a random $a$ and sends $h_A = g^a\bmod p$ and
party B draws a random $b$ and sends $h_B = g^b\bmod p$.
party A receives $h_B$ and computes $s_A={h_B}^a\bmod p$ and
party B receives $h_A$ and computes $s_B={h_A}^b\bmod p$.

If no message has been altered, $s_A=s_B$ and this is a shared secret $s$. It is typically used as input to a key derivation function or hash in order to generate some shared secret symmetric key(s).

More precisely, if the order of $g$ is a large prime (including when $(p-1)/2$ is prime and $g^{(p-1)/2}\bmod p=1$ and $1<g<p$), and $a$ and $b$ are uniformly random, independent, secret, and large enough, a passive adversary can not distinguish $s$ from a random element of the subgroup generated by $g$. Beware that the party sending its $h$ second can influence $s$ to some degree. Also, when $g$ is a generator of $[1,p)$ as in the question, the order of $g$ is $p-1$, thus even, and the Legendre symbol $\left(\frac sp\right)$ leaks. This is a consideration when using DHE without a key derivation function, discussed there.

The system was published by Withfield Diffie and Martin Hellman: New Directions in Cryptography, in IEEE Transactions in Information Theory, 1976, with some presentations in 1975. See this for how it was discovered but not published by Malcolm John Williamson, working for the GCHQ, in 1974.

Note: Nothing immediately disastrous happens if a single one of $a$ or $b$ is kept constant (making the corresponding $h_A$ or $h_B$ constant). However that static ephemeral setup is generally a bad idea for key exchange, because there remains no protection against a bad RNG on the side responsible for choosing the remaining random. Also, because it is used for a long time, the constant secret is more likely to leak, revealing all shared secrets. These are reasons why TLS 1.3 requires ephemeral ephemeral DHE (see this). When online key exchange is not an option, a secret must nevertheless be fixed: DHE becomes the first step of ElGamal encryption, with the static $h_A$ the public key for A, and $a$ the matching private key.

If we make both $a$ and $b$ static, the shared secret becomes a constant. That can still be useful (e.g. after a key derivation step with a random value), but this static static setup is hardly a key exchange protocol.

Note: In practice, in protocols like TLS, the exchange has extra steps in order to authenticate the parties using public/private key pairs, and guard against active attacks including Man in the Middle. This is Authenticated Diffie-Hellman key Exchange.

Note: the question says "each party computes its key", but $h_A$, $h_B$ are normally not considered "keys" in DHE. Only for static $a$ or $b$ are $h_A$ or $h_B$ said to be "public keys". $s_A$, $s_B$, normally the same, often are called the "shared key", although I prefer "shared secret", to distinguish from the output of a later key derivation step.


Must the ciphertext be longer than the key for symmetric encryption?

From the point of view of security, there is no problem with a key being longer than the ciphertext – 3DES has a 168-bit keysize and a 64-bit blocksize so for small messages it results in a ciphertext shorter than the key (at least without counting an IV).

However, in most block cipher modes the message gets padded up to a multiple of the blocksize, so a single 16-bit integer would result in at least 64 bits of ciphertext. That can get a bit inefficient if you have a lot of very small fields.


Would this hash functionality fall under pre-image resistance or collision resistance?

I do not want different inputs equalling the same output, only identical ones.

That is pretty much the definition of collision resistance:

  a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and a ≠ b.

Of course, no hash function can guarantee that the same hash values means the same input. Consider the case where you are hashing files up to 2 gb into 256-bit hash strings. So there are $2^{8000000000}$ possible inputs and only $2^{256}$ possible outputs. Many many possible files will map to each hash string.

So you can never guarantee that identical hashes means identical inputs, but you can rest easy that with a good cryptographic hash function, it is computationally infeasible for an attacker to build two inputs with the same hash (collision resistance), or to take a given input and find a second input with the same hash value (second pre-image resistance).


Does secure multiplication makes sense in the case of 2 inputs?

There is no way to avoid that a party infers knowledge about another party input by looking at the result and his or her input. This is not considered a security issue of the protocol.


Can DNA computing to solve elliptic curve algorithms using this method

TL:DR; The algorithm is working in parallel, however not practical due to the number of DNA strands requirements for safe-curves. Generic Discrete logarithm algorithms can easily beat this, [see here].

The algorithm

The algorithms work in theory. The authors use $Q =lP$ let change it $Q = [x]P$.

Their method, actually, is highly parallelized like any DNA algorithms. DNA algorithms are actually very good at parallelization.

Let call their algorithm amplify-and-double-and-add;

t1 = P / here t is tube

while x not found:
   t1.amplify()
   t2.amplifyWith(t1)
   t1.add(t1)
   if t1 contains Q
     return matched value
   t1 = pour(t1,t2)

As one can see, the algorithm actually calculates the intermediate values, too. The while loop requires $\lfloor(\log x)\rfloor +1 \in \mathcal{O}(\log n)$-steps. The addition is performed by the AddTwoNode algorithm that requires $O(n^3)$ extract operations, $O(n^3)$ append operations, $O(n^3)$ merge operations, and $O(n)$ test tubes for parallel adder for elliptic curve.

The $n$ is the extension number of the Binary Galois Field $GF(2^n)$  under consideration. Therefore for a curve like Edwards25519 we have $n=255$

$\approx 2^{24}$ extract operations
$\approx 2^{24}$ append operations
$\approx 2^{24}$ merge operations
$\approx 2^8 $ test tubes.

The private random key $x$ is also around 255-bit $\approx 2^{8}$. Then in total the amplify-and-double-and-add requires;

$\approx 2^{32}$ extract operations
$\approx 2^{32}$ append operations
$\approx 2^{32}$ merge operations
$\approx 2^{16} $ test tubes (?).

The notes from the conclusion of the article

  so it is feasible in theory and inspirits the development of DNA computing. This indicates that the elliptic curve cryptosystems are perhaps insecure if the technique of DNA computing is skillful enough to run the algorithms efficiently as discussed in this paper.

Considerations

DNA computing is started with Adleman's novel work, or see here. The Adleman almost has written all the steps clearly since they performed a real experiment. In this article, there is no experiment or any calculations about it. I've looked for but couldn't find one, either.

This work is clearly a theoretical work and doesn't calculate anything about the timings or amounts of DNA computing. For example;

For example, a PCR can take around 1 hour, and it's not clear how many iterations are required by the algorithm?
How scales this algorithm is not clear. Now in practice, a test tube can contain $2^{18}$ DNA strands
The number of required DNA strands is not explained/calculated. What is the last tube's requirement for the final step? We can simply say that, if it was good it was in the paper.
how much their algorithm is requiring for a curve like edwars25519 is not calculated.
The timing of test tube operations - Extract, Merge, Amplify, Append, and Append-head- are not given.
Written in 2008 and has only 18 citations according to Google Scholar. That is too low for real groundbreaking work.
The timings of their 7 algorithms are not given at least the current stage of the technology when the article was written. Adleman spent 7 days in the lab for a graph with 7 cities and took 54 seconds.

The required number of DNA strands

Let call $\text{D-SPACE}$ for the required DNA strands for the running of any algorithm. The amplify-and-double-and-add algorithms in any step calculates values between $[2^k,2^{k-1}]$, while $1<k\leq x$.

Let forget about the intermedia steps and concentrate on the last step. We need around $2^{555}\text{-D-SPACE}$ so that all values can appear in the tube to be matched with $x$. This amount is too bighugehumongous even a little less than than the number of particles in the universe; and that is $3.28 \times 10^{80} \approx 2^{266}$.

The Conclusion

Not practical due to the $2^{555}\text{-D-SPACE}$ for a curve Edwards25519 or even 128-bit curves.


A hash function that returns a value interpreted as integer

My guess is that the intention is to make an RSA-1536 (or Rabin) signature of name (as a string) and integer $i$ per Full Domain Hash. Thus I answer, form a crypto standpoint, a rephrasing of the question as:

How do I make a full-domain hash of the concatenation of a name (given as a string) and an integer, towards signing these per RSA-FDH.

In a nutshell, my recommendation is to make that as in RSA-PSS, but with a fixed salt.
An implementation of that could be

Express name and $i$ as a bytestring per ASN.1 Distinguished Encoding Rules (DER). This will avoid ambiguities of string concatenation (so that name foo and integer 10 won't have the same hash as name foo1 and integer 0), and normalize the integer (so that integers 00 and 0 will result in the same hash). Formatting could be as a SEQUENCE (tag 16) with name as UTF8String (tag 12) then INTEGER (tag 2). See Burton S. Kaliski's A Layman's Guide to a Subset of ASN.1, BER, and DER (RSA labs, 1993), which is enough for an implementer, except for the UTF8String type.
Apply to the resulting bytestring the EMSA-PSS transformation of PKCS#1v2.2 with SHA-256 hash, MGF1 with SHA-256 hash, $\text{emBits}=1536$, and fixed salt (e.g. 256 bits at zero). Part of that step includes hasing the input bytestring with SHA-256.
Convert the outcome to integer (per big-endian convention); this yields an integer as asked in the question.
Apply textbook RSA signature $x\mapsto x^d\bmod N$ (or the Rabin alternative).
Convert the integer outcome to a bytestring of $\left\lceil\text{emBits}/8\right\rceil=192$ bytes (per big-endian convention), yielding the signature.

Note: when targeting RSA, the combination of 2…5 is precisely signature per RSASSA-PSS of PKCS#1v2.2, and implementations of that should be reusable directly, if they have an input for the salt or for the salt-generating method.


If an RSA signature is sizably truncated, as is the case here, it can not be verified with the public key. Hence here (necessarily: deterministic) RSA signature is used as a secret-key MAC, and could (and IMHO should) be replaced by HMAC.

That said, no, there is no risk of leak of the private key, or even the lesser risk of the ability to sign. If there was, that would demonstrably be a break of the RSA signature scheme used.

More generally, given access to a black box that performs the textbook RSA private key operation $x\mapsto x^d\bmod n$, there is no known way that $d$ (or an equivalent) leaks, unless the black box has a side-channel leak.


A Mersenne prime is a prime number that can be written in the form $M_p = 2^n-1$, and they’re extremely rare finds. Of all the numbers between 0 and $2^{25,964,951}-1$ there are 1,622,441 that are prime, but only 42 are Mersenne primes.

The second sentence is wrong.

What they meant to say is that there are 1,622,441 numbers of the form they mentioned in the first sentence below $2^{25,964,951}-1$.

There are 1,622,441 primes below 25,964,951 and thus 1,622,441 numbers of the form $2^p-1$ (with prime $p$) below $2^{25,964,951}-1$. See Wolfram Alpha.

There are over $2^{500}$ primes with exactly $2^{512}$ bits, so there are plenty to choose from for our RSA keys.

Take a look at the Prime number theorem which tells you that there are approximately $\frac{n}{\ln(n)}$ primes below $n$.


Lack of usage of secrets in ZK Bitcoin ownership proof

Yes, $\Sigma$-protocol is described at section 4.1 of the paper referenced. This is a 3-move protocol, with the last message "response" computed from second message "challenge" and a secret. In particular, 4 responses are computed at step 1(d) of the protocol presented. Coin private keys $x_i$ held by exchange is the input for computing the last response, selected by binary mask $s_i \in \{0, 1\}: \; \hat x_i = x_i s_i$.


No, an attack against RSA without padding that let one recover messages does not, as far as we know, degenerate into leaking a working private exponent $d$, or factoring $n$. In fact, even unlimited access to a decryption oracle performing $c\mapsto m=c^d\bmod n$ for any $c$ will not allow that either.

To back up the above, see this survey by Dan Boneh where it is Open Problem 1.


This is basically the difference between e.g. the RSA_ ciphersuites and the DHE_/ECDHE_ ciphersuites in the TLS protocols. Currently the standardization moves towards ECDHE_ because it provides forward secrecy: even if you factor the RSA key you can still not decrypt previous transmissions.

Note that you don't have to MAC the session key before encryption with the RSA public key. You do however need to MAC your ACK with the session key so the client can verify the that you both have calculated the same session keys.

I'm saying keys because you should try and create at least session keys for sending and receiving. In addition you could create keys for session encryption, session authentication and possibly even the initial authentication, depending on the rest of the protocol.

You can forget all the text above if you study TLS, or if you use (D)TLS in favor over your own protocol of course. No need to climb an ice wall, somebody already dug a tunnel.


The author of ISAAC notes:

  I provided no official seeding routine because I didn't feel competent to give one. Seeding a random number generator is essentially the same problem as encrypting the seed with a block cipher. ISAAC should be initialized with the encryption of the seed by some secure cipher. I've provided a seeding routine in my implementations, which nobody has broken so far, but I have less faith in that initialization routine than I have in ISAAC.

No official seeding algorithm means no official keystream or key scheduling.

The first sentence of that quote is a red flag for security. If someone knows the algorithm well enough to provide an initialization algorithm then it should be him.

But I suppose he thought that his algorithm would run fine if random values were assigned to each of the 259 32-bit words required to store the state of the RNG. (There is insufficient evidence for that.)

I think that despite it being unconventional, it would be fine for an algorithm designer to say "these values all must be filled with numbers from a HWRNG or key-derivation function," but instead he talks about block ciphers and encryption. (Those next two sentences aren't absolutely technically correct, but perhaps, since it was invented in 1993, the language didn't exist at the time.)

The unofficial initialization algorithm has no key schedule. It does not use subkeys. Instead it alternates between adding one of eight 32-bit seed words to eight words of the RNG state and slightly mixing up those 256 bits in a loop. (Note that just because the seed is 256 bits doesn't mean this algorithm has 256-bit security.)

His implementation actually loops too many times, writing to memory that doesn't belong to the 256 word array he's using. That's called a buffer overflow and it has the potential to be really dangerous. (Which can be as bad as allowing attackers to run arbitrary code on your computer remotely.)

That's another huge red flag. Something you may forgive from a pure mathematician who had to learn programming just to create reference code. But definitely not something you expect from a professional programmer.

... But even if we knew none of that,

Don't use ISAAC!!!

Why?

There is insufficient evidence to believe that the algorithm is cryptographically secure.
It's much slower than modern encryption algorithms.
There is insufficient evidence to believe that the algorithm is cryptographically secure.
The amount of memory it uses is relatively large.
There is insufficient evidence to believe that the algorithm is cryptographically secure.
The author didn't provide evidence for why we thought has algorithm was secure. Merely that he didn't find any biases using empirical data.
There is insufficient evidence to believe that the algorithm is cryptographically secure.


Prefixing data before encryption for passphrase confirmation?

There is no risk if the attacker knows part of the plaintext. This doesn't help to recover the rest of the plaintext. Even if the attacker knows all the bits but one, with any decent encryption algorithm, the attacker cannot tell what the last bit is from the ciphertext.

After all, it happens all the time with known data formats. For example, if you download a web page over HTTPS, the attacker knows that the page begins with <html><head> or some such.

Note that even if you find the expected prefix, this doesn't guarantee that the rest of the data isn't corrupted: encryption guarantees confidentiality, but not integrity. You need either to use an authenticated encryption mode (which Crypto-js doesn't provide) or to also transmit a MAC of the ciphertext (encrypt-then-MAC).


Would you use HMAC-SHA1 or HMAC-SHA256 for message authentication?

Yes.

That is a semi-serious answer; both are very good choices, assuming, of course, that a Message Authentication Code is the appropriate solution (that is, both sides share a secret key), and you don't need extreme speed.

  How much HMAC-SHA256 is slower than HMAC-SHA1?

Those sorts of crypto performance questions are quite platform specific, and so it's hard to answer definitively.  In my experience, I've seen SHA-1 (and hence HMAC-SHA-1) be about 30% faster than SHA-256; Your Mileage May Vary, of course.

Of course, the obvious comeback is "how much is this performance delta important to you?".  That rather depends on how fast you're adding/checking integrity tags.

  Are the security improvements of SHA256 (over SHA1) enough to justify its usage?

To the best of our knowledge, there is essentially no security difference between HMAC-SHA256 and HMAC-SHA1; with a sufficiently long key, both are impervious to brute force, and with a reasonably long tag, both will catch any forged messages with the expected probability.  There is a known weakness to SHA1 that allows someone to compute a collision in less time than expected; there is no known way to apply that to HMAC-SHA1, and so there are no known methods of attack (other than, as I mentioned just now, brute force, and guessing the tags randomly).


No, partially known plain text won't help an adversary guessing what's unknown, when using AES-128 in any of its usual secure mode, such as the common CTR with random IV (caution: it might help when using ECB, or doing other goofs)

That extends to any modern cipher, and the more general (and often realistic) assumption that the adversary can choose part of the plaintext. All modern ciphers are designed with the explicit goal that the adversary can't tell anything about plaintext that it is not already known. This formalizes as IND-CPA, or IND-CCA1 (depending on what's assumed about what the adversary can do).

Addition: to some degree, a little known plaintext helps brute force attacks (aiming at finding the key by enumeration of the possible keys, which then allows full decryption), and attacks on implementations. However, AES-128 is currently very safe against brute force, thus this threat can be discounted. In the first paragraph, I have silently made the following assumptions:

The key was chosen at random, and is initially fully unknown to an adversary.
We discount the distant possibility of quantum computers usable for cryptanalysis.
The implementation is not attacked by side channels (timing attack, DPA..).


Looking for encryption algorithm not subject to known-plaintext attack with IV reuse

Well, your requirements sound pretty much like standard disk encryption ones.

Assuming you can assign IDs (0,1,2...) to each 4kiB sector implicitely.In this case you could simply use XTS-mode of encryption using AES.
You'd then iterate through the 4kiB block using the inner counter and iterate through all sectors using the outer counter.

This should give you best possible security, as the same plaintexts are mapped to different ciphertexts (because of the counters) and there's no keystream to break.

I hope this is a solution to your problem.


What are the practical implications of ciphertext distinguishability?

This isn't really a "hard" answer, but an attempt to give some intuition or motivation.

One can interpret indistinguishability as an overapproximation of the most common notions of security: Any system that is broken in a more practical way will also fail to meet indistinguishability, that is, all practically important security requirements are in fact subsumed by indistinguishability. It is therefore a sensible and defensive approach to require indistinguishability. This proceeding also agrees with the expectations one usually poses to a "good" system: It should be as close as realistically possible to Shannon's definition of perfect secrecy.

On the other hand, a system may well be distinguishable but do not admit any relevant attacks — however, in practice, distinguishing attacks are often the first sign that a system may be about to break in more severe ways. A potential reason for this could be the fact that the structure of a system needs to be well-understood by researchers to find such attacks, and then other weaknesses can become visible as well. I suppose the most prominent example is the RC4 cipher, which continued to accumulate more and more known biases (breaking indistinguishability) over time until it had to be considered insecure for practical purposes.


The only book I know of regarding Secure Multiparty Computation is Secure Multiparty Computation and Secret Sharing by Ronald Cramer, Ivan Bjerre Damgård and Jesper Buus Nielsen. Yet, I could hardly classify it as introductory.

This is its official site.


Hint: seen as a discrete logarithm problem, there's an attack of cost $O(\sqrt{\min(e_1,e_2)})$.

I see no improvement on the asymptotic cost without factoring $n$.

Update: I think it is rigorously provable that if one could solve this problem in polynomial time with sizable probability for proper choice of $n$ and random other parameters, then we could factor $n$. Proof is left as an exercise to the reader by the usual method: invoke the hypothetical algorithm solving the problem in a polynomial-time algorithm that factors $n$.


CMAC Generation : If input payload length is not aligned in 16 bytes, what are the possible side effects?

I hope you mean drawback caused by AES CBC-MAC which is resolved in AES-CMAC.

AES_CBC MAC if used properly with ISO padding technique should not result into a tag collision.

So AES-CBC MAC should look something like this.

In AES-CBC MAC if the last block is not  16 byte aligned (considering AES as PRF) then padding must be done to the last block.
Padding should be done based on ISO (bit padding, using binary one followed by zeros, e.g. $\texttt{100..00}$)
For ISO 1 indicates the start of the padding.
If the block is already 16 byte aligned then a dummy block (with ISO padding)
should be concatenated . After this only the tag should be calculated.

Let's see the collision situation:
last block say m is of 13 bytes. Hence as per ISO padding the block would become  $m\|\texttt{100}$ and then tag will be calculated.
What if there is a block called $m'$ which ends with $\mathtt{100}$ as the real data and if the dummy 16 byte block is not added then tag will be of same as with $m\|\mathtt{100}$.
This means that a collision can be created.

As per security two different data should not result in the same MAC with the same Key. Hence it can become insecure.

To overcome this, there is a solution in AES-CMAC where there is no need to add a dummy block if the it is already block aligned to the PRF (in this case it is AES then 16 bytes aligned).

In AES CMAC there are three keys ($K$,$K_1$ and $K_2$).
$K_1$ and $K_2$ are derived from $K$.
For the subkeys ($K_1$ and $K_2$ ) generation, please see section 2.3 (Subkey Generation Algorithm).

If the last block is not aligned (16 bytes in case AES PRF) then pad the last block as ISO padding . Encrypt it with AES and XOR the output with $K_1$ .
The tag is calculated on the XOR-ed output with the same key $K$.

Please see the image for padded case in AES-CMAC

If the last block is aligned (16 bytes in case AES as PRF) then XOR the output of the block with the $K_2$. The tag is calculated on the XOR-ed output with the same key $K$.

Please see the image for the non padded case.

Note: referenced from Professor Dan Boneh.


How key materials are generated in SSL V3 from master secret

You can use TLS 1.0 as guidance: it is the direct successor of SSL 3.0, so many things are quite similar, and in some respects TLS 1.0 is a bit clearer. In section 6.3 you will find the key generation process, with the exact sentence:

  To generate the key material, compute [...]
     until enough output has been generated. Then the key_block is
     partitioned as follows:

the important word being "partitioned".

For instance, if you are using 3DES as symmetric cipher and SHA-1 for the MAC, the "write keys" are 24-byte long each, the IV are 8-byte long each, and the MAC keys are 20-byte long each. So, a total of 104 bytes. The key generation function repeatedly invokes SHA-1 and MD5 on various elements; each round produces 16 additional bytes (that's the output size of MD5). You need 104 bytes, hence, you will need 7 rounds.

At the first round, you call SHA-1 over the concatenation of 'A' (a single byte of value 65), the master secret, the server random and the client random, in that order ('+' indeed denotes concatenation). This SHA-1 invocation yields 20 bytes. The concatenation of the master secret and the SHA-1 output is then hashed with MD5, which yields 16 bytes. These are the first 16 bytes of the key block.

For the second round, the processing is identical except that you use 'BB' instead of 'A' (two bytes of value 66 each). This produces the next 16 bytes of the key block.

You continue like this. Ultimately, you can potentially do 26 rounds (up to 'ZZZ...Z'; the SSL 3.0 specification does not define how to go beyond that). This would yield a total of 26*16 = 416 bytes. But if you need only the first 104 bytes, there is no need to compute the whole 26 rounds; just compute enough rounds to get the number of bytes you need.

Once you have your key block (104 bytes with 3DES and SHA-1), you split it into the needed key elements. The first 20 bytes go to the client write MAC key, the next 20 bytes for the server write MAC key, then the next 24 bytes for the client write key, and so on.


Given $C$, $M$ and all $k$ public keys, can an attacker tell with significant probability which public key was used to encrypt $M$ giving $C$ ?

Well, he can eliminate some of the possibilities (which means with $k=2$, he has a decent chance at finding the correct one).
There are two observations he can use:

He can eliminate all public keys $K_i$ for which $C \ge K_i$.  This is pretty obvious, but (if he is lucky) might eliminate some.

For each public key $K_i$, he can compute the Jacobi Symbols $\left( \frac{M}{K_i}{} \right)$ and $\left( \frac{C}{K_i}{} \right)$; if they differ, then he knows that $K_i$ is not the correct key.

This works because we're assuming textbook RSA, and textbook RSA always preserves the Jacobi symbol (which can be efficiently computed).  For an incorrect key, this test will disqualify it with probability circa 0.5, and so about half the incorrect ones will be eliminated.


Why can´t an attacker find the key if he has the plain text, the IV and the ciphertext?

After reading the chapter I was wondering, can an attacker compute my secret key if he has access to the IV, the plain text and the ciphertext.

No; or at least, there is no known way to do so.

If there was, well, AES would be considered "broken".

  Is this possible? If not why?

Well, the short answer is "a lot of really bright people have tried to come up with a way, and nothing occurred to them".

In AES, the plaintext is processed by the key in a number of steps ("rounds" is the terminology we use), stirring in the key each time.  Each step is easy to reverse if you know the key (hence AES is invertible, and so we can decrypt with the key); however the end product (the ciphertext) is a complex function of the key and the plaintext; it certainly isn't an obvious way to figure out what key was used.

Now, there are more advanced strategies that could be used (such as looking at the encryption of similar plaintexts, and see if that gives you information you can't get by looking at isolated plaintext/ciphertext pairs), however AES was specifically designed to foil such advanced strategies (and would appear to be successful in doing so)


Is it insecure to generate a key with your own public and private DH keys?

In traditional DH Key exchange, users A and B derive a common secret $g^{ab}$ from their respective key pairs $(pk_A=g^a, sk_A=a)$ and $(pk_B=g^b, sk_B=b)$. Aside from active attacks, the security of the scheme depends on the Computational Diffie-Hellman (CDH) assumption, since it is difficult to compute $g^{ab}$ from public keys $g^{a}$ and $g^{b}$.

If you perform the key agreement with yourself, you end up obtaining the secret $g^{a^2}$. The question now is if computing $g^{a^2}$ from your public key $g^a$ is difficult. The Square Computational Diffie-Hellman (SCDH) assumption says that, indeed, it is difficult. It can be proved that SCDH and CDH are equivalent for generic groups.


What informal indicators exist for estimating the computational infeasibility of cryptographic problems?

But, from a meta-cryptographic point of view, how do we justify the assumption that there doesn't exist any significantly more efficient algorithms, or any significantly better hardware?

From a cryptographic point of view, the best answer is usually modularity: we want to design schemes which can be based on "instantiation-oblivious" hypothesis (i.e., hypothesis that we can instantiate over a large variety of objects sharing some mathematical structure). For instance, we know that the discrete logarithm problem is hard in a generic group (a group with no additional structure). Therefore, if a scheme based on the discrete log is broken on a given structure, it will likely remain secure if it is instantiated on another group, with less additional structure (notwithstanding the advent of quantum computers, ofc).

From a meta-cryptographic point of view, once a specific system is deployed, our confidence comes essentially from two considerations:

How long has the underlying problem been studied
How many people are actively doing research in cryptography (both in academia and companies)

For example, the factorization problem already has a very long history, hence it seems more likely that our understanding of it is more advanced - put otherwise, there is less chance that we missed a simple approach that would allow for fast factoring. However, the second consideration remains probably the most important one. In the 90's, it was plausible for a powerful intelligence agency (such as the NSA) to hire enough mathematicians, and to give them access to a huge computing power, so as to be competitive with what the rest of the world could do. With the evolution of cryptography in the past decades, that does not seem plausible anymore. Thousands of researchers are actively working on cryptography, hence an agency could, at best, hire a very small fraction of these researchers. I see no strong reason to believe that all the best researchers could end up working for the same agency (especially since cryptographic research is spread worldwide). Assuming that the researchers an agency can hire are sufficiently representative samples among good researchers, this implies that the probability that a cryptographic breakthrough comes from a given agency is reasonably small. The same observation holds with respect to computational power: nowadays, even an agency as powerful as the NSA cannot mount cryptographic attacks that would require way more computational power than what, e.g., Google, Apple, or Microsoft have access to.

  How likely is it that a single small team, basing their research solely on the state of the public research and their own results, would come up with results years or decades ahead of everyone else in the field?

It is not impossible. It appeared in the past: Clifford Cock had essentially discovered  RSA five years before its introduction by Rivest, Adleman, and Shamir, while working for the GCHQ. In the 70's, the NSA had apparently already discovered differential cryptanalysis (see this post by Bruce Schneier), which could break many seemingly secure schemes, and was only 'publicly' discovered in the 90's. However, at the time, the amount of people working in this field was considerably smaller than today. Nowadays, the probability of such an event happening should probably be close to (number of people working for the agency)/(number of researchers working on area related to what the agency works on). Hard to precisely estimate, but likely small.

  Is it possible for large organizations to internally accumulate enough research, to give the researchers within that organization a significant head start over independent researchers in the field?

Again, it is not impossible, but it requires luck more than anything else. But that was assuming the question was about finding breakthrough results on cryptanalysis of deployed schemes. In fact, other types of attacks can be found, and they seem way more likely.

the agency can find an attack, not on a primitive, but on a protocol. Due to their highly complex structures, the landscape of possible attacks in considerably increased. Unlike cryptanalysis of primitives, breaking a protocol is not about finding advanced mathematical methods, it's only about thinking about something that people did not consider before. A good example of it is the recent logjam attack, or 3SHAKE. It is not completely unlikely that some agencies are already aware of attacks of this type that have not yet been publicly revealed.
Even more likely, the agency can directly find flaws in a specific implementation (either of a cryptographic primitive/protocol, or at a higher level). Those flaws are usually devastating, conceptually very simple, and seem considerably more easy to identify than, say, a new factoring algorithm (such flaws are discovered routinely). One can think for example about the recent heartbleed. Here again, it seems quite likely that some agencies are already aware of security issues that have not been yet publicly revealed.

  If "yes" on the previous question, are there ways to reliably tell if an organization has such significant amounts of secret accumulated knowledge? Is it possible to use the numbers of papers and patents the organization outputs, as a reliable indication that it doesn't have a strategy of accumulating knowledge only internally? What about flows of personnel between organizations, i.e. people changing jobs?

If the organization is small and keeps everything it does secret, there is no way to tell. Intelligence agencies will obviously not write patents or publish papers about their most critical discoveries. However, if the organization is small, it has also a very small probability of being the one from which a cryptographic breakthrough originates.

On the other hand, if an organization is large, then there is a standard way to know what it is working on: leakages. If the organization works with many people, on sensible subjects of crucial importance, something will end up leaking - human flaws are the only one that an agency cannot cope with. This happened with Snowden, and can happen again.

  What is the likelihood that an organization exploiting weaknesses it has found in cryptographic primitives, would be caught in the act? If the organization is only using the weaknesses for intelligence gathering? Does it matter if the weaknesses require passive attacks or active attacks to be conducted?

That completely depends on the particular scenario: it could be that an active attack will remain undetected, or that it will be detected with noticeable probability. In the field of secure computation, which an important and active research area in cryptography, this fact has been acknowledged by considering three types of adversarial behaviors: passive, covert, and active. Passive and active attacks are the types you already know; a protocol secure against covert adversaries can be broken by an active attack, but it is not possible to break its security without being caught (with good probability). The rationale behind this was that in practice, an important company/agency would likely want to attack cryptographic protocols, but cannot afford being caught when doing so.

If the weaknesses requires only passive attacks, and the agency is only gathering information, there is no way to tell (except internal leakages): a passive attack can be mounted offline, on the transcript of some interaction, hence there is no reason why anyone could discover about the outcome of the attack, unless that person is already part of the agency.


Encryption and decryption example using the Pohlig-Hellman Exponentiation Cipher

Using the Pohlig-Hellman cipher, you encrypt your message $M = 3$ using an encryption key $(e,n) = (7,11)$. The encryption is $C = M^e \mod n = 3^7 \mod 11=9$.

You decrypt with a decryption key $(d,n) = (3,11)$, such that $e\cdot d = 1 \mod (n-1)$. Since $3 \cdot 7 \mod (11-1) \equiv 21 \mod 10 \equiv 1$, this is satisfied.

So, to decrypt, compute $9^3 \mod 11 \equiv 3$, which was your $M$. You're done.

It looks like you are confusing the Pohlig-Hellman exponentiation cipher with the Pohlig-Hellman theorem used to solve a discrete logarithm problem. These are related problems.

You use the Pohlig-Hellman algorithm when you want to solve $g^x = h \mod p$, where $g,h$ are in a finite field $\mathbb{F}^*_p$, $g$ is a primitive root and $p$ is a prime. When $p-1$ factors into a bunch of small primes, you can solve several smaller discrete logarithm problems and reassemble $x$ from the solutions to those smaller problems via the Chinese remainder theorem.

Also, make sure you know why you're using this cipher in the first place.


Why does verifiable secret sharing with an honest majority require a broadcast channel?

By definition, VSS implies broadcast. As such, with $t\geq n/3$, it is not possible to achieve VSS (by the bounds on Byzantine Agreement).


The standard definition of a hash function is from arbitrary length bitstrings to a constant length bitstring. That is, there is only one input. Password hashes, like keyed hashes (MACs, more or less), have more than one input. There is no contradiction there, since password hashes are not cryptographic hashes - thought they may be built from cryptographic hashes like PBKDF2 (or even vice versa).

(Password hashes are called that largely for historical reasons. Normal hash functions used to be used for the same purpose, but that is not as good an idea.)

In practice, you will find notation where a hash function does have multiple inputs. That usually means that the inputs are encoded into one and then passed through the hash function. The encoding can be as simple as concatenation or it can add something extra to make inputs unique and prevent collisions.