Could a collection of data be engineered to encrypt predictably using standard encryption algorithms?

What you're describing is a chosen-plaintext attack.  In this scenario the attacker (you, in this case) creates a specific plaintext for the cryptosystem to encrypt, in an attempt to manipulate it in specific way...In your scenario, to get it to give up information about the key.   Chosen plaintext attacks should not be possible in a semantically secure cryptosystem.  If they are possible, the system is broken, and should not be used.

So, to directly answer your question, no, this should not be possible, and certainly is not generically possible.   There may be specific implementations of crypto-ransomware that are flawed in a way that would make this possible, but you would have to specifically target an attack for that specific system, and it would be useless against any other, including another system flawed in even a slightly different way.


The theory is: don't try to write timing-safe code in JVM-languages or other essentially-interpreted-but-perhaps-sometime-compiled languages; rather

Use timing-safe libraries called from the comfort of the JVM-language. Typical example: in a JavaCard that passed Common Criteria evaluation to EAL5+ with AVA_VAN.5 augmentation, it is a safe bet that AES (when available) is timing-safe.
Avoid needing timing-safety in the first place when possible. Typical example: rather than attempting to compare an alleged 16-byte value to a reference 16-byte value in constant time, draw a fresh AES key, encipher the alleged and reference value with this AES key (with a constant-time AES implementation), then compare the results using any method at hand.
As a variant of the above, use countermeasures that make timing attacks less efficient, like blinding.

The above tends to work also against side-channel attacks beyond timing, e.g. power analysis.

When market pressure dictates otherwise, options are to make as few as possible relatively safe bets; and check them carefully when one has the luxury of knowing the actual targets. For example, when writing
// compare two byte arrays so that timing does not leak where a difference lies
public static boolean myEqualByteArrays[(byte[] a, byte[] b) {
    int j = a.length;
    if (j != b.length)
        return false; // arrays are not the same length
    int r = 0; // will stay zero until a difference is found
    while (--j>=0)
        r |= a[j] ^ b[j];
    return r==0; // true if and only if the arrays match
}

it is only assumed that

binary operations ^ and | are constant-time (& and unary ~ probably are, too, though we don't need that in this example);
loops won't be exited even when deep analysis of what follows shows that they can.

So far, if I have met anything breaking these assumption, I did not realize it!

Example of things that can't safely be assumed constant-time:

Any use of if, switch..
short-circuit operators && and ||
Logical not !
Array access (e.g. due to cache).
Integer multiplication (including by a constant): some CPUs have multiplication time dependent on one argument; examples include this and this 32-bit CPUs (kudos to the manufacturer for documenting it).
Division, of course (including by a constant).
Operations on larger data types than supported by the combination of the compiler, runtime, and hardware: conceivably, some internal carry might cause a data-dependent timing dependency even in + or -, e.g. of some 64-bit type internally using 32-bit variables. This a bit less to fear for variable addition than increment, which could be implemented or automagically over-optimized at runtime into: increment low half, and if not zero increment high half.
Shift: timing often depends on the shift count.
Right-shift by a constant shift: that can depend on the sign or high-order bit of the shifted argument (that is less likely with unsigned types; and in Java, it is less likely with the unsigned >>> operator than it is with the signed shift operator >>).
The selection operator ?: ; however, in Java, restricting to built-in signed 2's-complement 32-bit type int, a substitute for d = (a==0) ? b : c; might be
// compute the OR of all bits in  a  into the low-order bit of  d
d = (a >>> 1) | a;
d = (d >>> 2) | d;
d = (d >>> 4) | d;
d = (d >>> 8) | d;
d = (d >>>16) | d;
d = -(d&1); // duplicate the low-order bit of  d  over the whole  d
d = ((b^c)&d)^b; // select  b  iff a==0,  c  otherwise
and that technique could be extended to, say, constant-time point multiplication on an elliptic-curve over some binary field, if efficiency is truly secondary.


As CodesInChaos notes, a secure block cipher satisfies all the criteria in your question:

An $n$-bit block cipher is a (keyed family of) bijective function(s) on the set of $n$-bit bitstrings.
A block cipher can be used for symmetric encryption in any of several modes of operation.  In some of these modes (notably OFB and CTR) the block cipher effectively acts as a keystream generator for a synchronous stream cipher.
A block cipher can be used in several ways to construct a one-way compression function, which in turn can be used to construct a cryptographic hash function.  Indeed, most commonly used cryptographic hash functions are based on block ciphers.
A hash function constructed from a block cipher can certainly be used in the HMAC construction, but there are also several ways (such as CBC-MAC, OMAC and PMAC) to construct a MAC directly from a block cipher.
As noted above, a block cipher in CTR or OFB mode becomes a stream cipher, which is essentially the same thing as a cryptographically secure pseudorandom number generator.

Indeed, insofar as there exists a "universal building block" in modern cryptography, block ciphers are it.  Pretty much the only thing they cannot do is public-key cryptography.

That said, block ciphers certainly aren't the only possible building block.  For example, a cryptographic hash or pseudorandom function can be used in the Feistel / Luby–Rackoff construction to construct a block cipher, which can then be used to construct all the other things described above.


Is there a relation between security of rounds of DES and Luby Rackoff rounds?

Luby rackoff results are based on assuming the Round Function to be Secure Pseudo Random Functions.  Where as the round functions of DES are not that secure enough which needs more rounds (Triple DES needs 48 rounds )


Will SHA1 or Other Hash Functions Ever Contain Quotes

SHA-1 (and, in general, any modern cryptographical method) will generate an arbitrary bitstring.  The bit string 0x22 (the ASCII code for double quote) is as probable as any other bitstring.

You could attempt to detect (and escape) such byte values; another possibility is convert the bitstring into hex or base-64; those have a deterministic size, and may be a bit easier to place into the database.


I don't believe that it is possible given the requirements you've listed.

Let us consider an arbitrary $C, M$ that meets the requirement.  To reveal the entire database, what an attacker can do is compute $C(d,s)$ for every possible $d$ (about 4 million, as you said); then, he can use $M$ to compare that to every value you actually have - this reveals everything.

To make this a solvable problem, you need to modify some assumption somewhere.

One way to address this is to prohibit an attacker from evaluating $C$ himself; we can define $C(d) = HMAC_k(d)$ for some secret key $k$.  This is determanistic (and so $M$ is a simple bitstring compare; we're assuming that we want to publicly reveal precise matches anyways, and so that's not an issue).

Another way to address this is to prohibit an attacker from evaluating $M$ himself;. One way to do this is, for some large prime $p$ and generator of a large prime subgroup $g$, we can pick a secret exponent $k$; we'd publish $g$, $p$ and $K = g^k \bmod p$.  We'd define $C(d, s) = (K^s, g^{s+d})$; we can't check if a particular $C$ corresponds to a specific $d$ if the Diffie-Hellman problem is hard.  And, the comparison function $M( (K^s, g^{s+d}), (K^t, g^{t+b}))$ (which is the comparison of an encoded $d$ and an encoded $b$) would check if $(g^{s+d})^k \cdot K^t = (g^{t+b})^k \cdot K^s$; as $K=g^k$, this is equivalent to $g^{ks+kd} g^{kt} = g^{kt+kb}g^{ks}$ or $K^d = K^b$


What is the minimum recommended number of rounds for Argon2?

TL;DR: Yes, you probably should increase this, even though not by that much.

First, we need to identify the Argon2 variant in-use which is Argon2i for Passlib.

Now if we take a look at section 5.7 of the Argon2 specification, we will learn that there are some special attacks if only 1 or 2 rounds are used which is why you want the round value to be larger than that. Some might recommend to use something like 10 rounds.

In practice, I'd recommend following the same methodology as I laid out for Argon2d: Find out how much memory you can use, pick a lower bound for the round count (eg something like 5?) and then maximize memory usage within your time limit and perhaps tweak the time with the round number.


Possible to guess RSA public key $e$ using $n$ and $\phi$

Assume the public key $e$ is not known, how difficult would it be to
  guess the public key using $n$, $\phi$, $p$ and $q$?

$e$ can be chosen completely arbitrary and independently of the modulus and related variables ($\phi,p,q$). You can't learn anything about $e$ (assuming $d$ isn't given) only with the modulus given.

  Assuming we have $c_1$, $c_1 = m^e \bmod n$ is it possible to find out
  $m$ without knowing $e$ and $d$ ?

To recover $m$ you need to know $d$ (by the RSA assumption), so there's no way to recover $m$ without $e$ or $d$.

  From my point of view $ed = K*\phi(n) + 1$ it is difficult to guess
  $e$ and $d$ product. Will it fall into the factorization problem ?

You can arbitrarily choose either $e$ or $d$. The other one is a direct result of the above equation. You can't learn the $K$ either (how would you?) so even the ability to factor won't help you. Even if you'd know $K$ factoring the product would still be quite infeasible as this would be of the same size as the modulus, for which factoring is considered infeasible.

  Is this the only equation with $n$ and $\phi$ that involves $e$ and $d$ ?

Yes, this is the only RSA related equation involving, or rather this is the only equation: $ed\equiv1\pmod\phi$.

  Can we use some algorithm for guessing $e$ and $d$ ?

If you're lucky, you can indeed. $e$ usually takes the values $3,17,65537$ and if those don't yield the correct messages, you can still try each possible (small) $e$ value until you hit a good one. If $e$ is larger than $\approx 2^{40}$ you'll have a hard time finding this value.


Edit: Kolmogorov complexity is most useful as an asymptotic concept as $n$, the length of the string increases. This is addressed in the general answer below.

Specifically one should use $s=1,0,1,1,1,0,0$ as the output, as suggested in the comments. Then the length is $|s|=7,$ and the question becomes

  Is there a $c\geq 1,$ such that $K(s)\geq |s|-c$?

Since this string is woefully short, the answer is No, the program length would be too large, as pointed out in the comment by @PaulUszak.

General Answer:

Given any linear (or nonlinear) shift register of fixed length $L$ and its output sequence $(x_k)_{k=1}^n $, its Kolmogorov complexity is $o(n)$ (thus not Kolmogorov random) since the program which says essentially:

Let $i=1.$
Load register with $x_i,\ldots,x_{i+L-1}$
Compute output bit $z_i=f(x_1,\ldots,x_L)$ and output it
Compute state update bit $x_{i+L}=f(x_i,\ldots,x_{i+L-1})$
Update state to $(x_{i+1},\ldots,x_{i+L})$
$i\leftarrow i+1$
If $i>n$ Output $(x_1,\ldots,x_n)$ and Halt else Go to 2,

can  generate a sequence of arbitrary length $n$ while $L$ is fixed.

More precisely, since the set of all functions $f:\{0,1\}^L \rightarrow \{0,1\}^L$ has cardinality $(2^L)^{2^L}=2^{L2^L}$ we can specify $f$ with $L2^L$ bits.

The program, and its input, obviously have length $O(L)$ bits. So the program complexity in bits is dominated by the $f$ specification.

Thus as $n\rightarrow \infty$ there is no finite constant $c,$ such that

$$K(z_1,\ldots,z_n)=O(L2^L) \geq n-c$$
holds. Hence the output is not Kolmogorov random.


Why would you ever need Key exchange algorithms, when you can use public key encryption?

Why the need for key exchange algorithms?

Most of the time in practice you will probably use a secret key with a symmetric cryptosystem because of efficiency reasons. Especially if you have a large amount of data to send, doing a single key agreement via Diffie-Hellman and then using the resultant key with a symmetric cryptosystem will be take significantly less time than actually packaging the data up and sending it one chunk at a time via RSA. Performing a key exchange and then using the key for a symmetric cryptosystem is referred to as a hybrid cryptosystem.

Less time implies fewer CPU cycles

Fewer CPU cycles implies lower power consumption

Public Key Encryption implies ciphertext expansion

This results in slower transfer speeds for data in transit on a network
This results in more space consumed for data at rest on a storage medium

Key agreement algorithms such as Diffie-Hellman are sometimes simpler to implement than public key encryption schemes such as RSA.

When to use Public Key Encryption

Many PKE schemes offer homomorphic encryption. If you want homomorphic encryption, you probably can't opt for the hybrid cryptosystem and will need to package your message into the PKE ciphertext.

If you are operating in a constrained environment, depending on the nature of the constraints and environment it can possibly be better to simply use PKE directly instead of a hybrid cryptosystem. Such constraints might include:

Code size constraints
Data size/bandwidth constraints
Latency constraints
Compatibility constraints

What is most efficient will depend on the exact nature of the environment, constraints, and algorithms in question.


Is a 2 bit one time pad just as secure as a 128 bit one time pad?

Yes, they both satisfy perfect secrecy, but with a 2-bit OTP you can only encrypt a 2-bit message once.


The answer is both yes and no, as I explain below.
1. No, BBM92 is better (or at least, we initially thought so)
E91 was the initial idea which led to the more rigorous BBM92.
In the E91 paper, there is not actual security proof, ant the attack is not really specified: if the CHSH inequality is violated by only a few percents (say $S=2.05$), how many secret bits can Alice and Bob still share? With the techniques known in the early 1990’s there were no way to answer this kind of question. BBM92 was essentially a way to replace the Bell inequality with a more tractable entanglement witness, and to transfer the security proofs of BB84 to entangled state protocols. So in term of security, and practicality, BBM92 is much better than the E91 which is badly specified. And in practice, when a physicist says “E91”, he often actually means “BBM92”...
2. Yes E91 turns out to be better (because it is device independent)
To my knowledge, the first QKD paper actually using Bell inequality violation as an actual security parameter for QKD is the Barett, Hardy Kent paper of 2004 (arXiv/PRL). This was initially seen as a way to to perform QKD even if one does not trust quantum mechanics. This kind of protocols has now expanded to the domain of device-independent quantum cryptography, when one does not need to trust your devices to perform QKD. In this sense, variants of E91 can indeed be safer than BBM92.
Artur Ekert actually said of the latter development that it was “a very good example of when your ideas are more clever than yourself”.


Are ephemeral keys symmetric or asymmetric?

I think it is more common to explicitly name asymmetric key pairs ephemeral or static because it matters more on a generic, lower level algorithm description.

During key establishment, it matters a lot if keys are ephemeral or not. For instance, if you'd use static-static key agreement, then the agreed-upon key will always be the same, unless you explicitly mix in a random value. Only if the key is static will it also be able to provide entity authentication. Hence these schemes are described in a generic way of e.g. NIST Special Publication 800-56A
Revision 3: Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography which contains the following definition:

  A key pair, consisting of a public key (i.e., an ephemeral public key) and a private key (i.e., an ephemeral private key) that is intended for a very short period of use. The key pair is ordinarily used in exactly one transaction of a cryptographic scheme. Contrast with a static key pair.

If the terms are commonly used for DH keys within key agreement, then it is more likely that this will seep through to higher level protocol specifications such as TLS as well.

The main thing about ephemeral keys and ephemeral key pairs is that they are not pre-established, they are only established when required, and then discarded. This can be true for both asymmetric and symmetric keys. This of course also means that public keys cannot be trusted in advance. Pre-established keys / key pairs are also called static keys / key pairs.

Commonly you would expect ephemeral keys to be destroyed after a single use - storing them on persistent media is not expected.

Typical ephemeral keys are keys that are tied to a session in TLS. In there the E in DHE and ECDHE is used to denote ephemeral Diffie-Hellman authentication. Within TLS the client (EC)DH key pair is always ephemeral, so that one does not contribute to the E being present or not within the TLS cipher suite. Commonly however, the server's key pair is also ephemeral, so you get ephemeral-ephemeral key agreement to establish the symmetric master key and session keys. This scheme does not authenticate the server by itself.

Rather uncommonly, the server may use a trusted, static DH key pair where the public key is embedded in a certificate and the private key stored in the server. This is called ephemeral-static DH key agreement. In that case the DH key agreement will also authenticate the server.

Sometimes the ephemeral DH keys are also cached in memory for multiple sessions. This is more or less cheating; it's a dangerous performance hack (deriving key pairs is relatively expensive operation), which will have security related consequences.

The symmetric session keys in TLS are probably ephemeral keys. They are not called that way because well, they are already called session keys as they encrypt and/or authenticate the data in the session. As Dave commented, the master key may or may not be ephemeral, it depends on the protocol. However, these keys are used over multiple messages, so they are less ephemeral than an ephemeral DH key, which is only used for one key establishment.

Finally, ephemeral is a word, and the common meaning of words is written down in dictionaries (which pretend, in their arrogance, to define them). Let's take a look at the Merriam-Webster definition:

  Definition of ephemeral

  lasting a very short time, e.g. ephemeral pleasures
  lasting one day only, e.g. an ephemeral fever

When using these terms it is always a good idea to not deviate too much from the original meaning. However, it is of course possible that - for instance - a TLS session lasts longer than a day.

As for your question:

  If symmetric, can ephemeral keys be created based on a UserID or nonce?

It would be strange to create an ephemeral key from just a UserID, because that would always result in the same key. In that case the key value would not be called ephemeral. You can certainly create an ephemeral key from a nonce or combination of UserID and nonce, presuming that the nonce itself is ephemeral.

Neither of UserID or nonce sounds like a secret value, so you would not get any security properties from such a key. You can however use a static key, the user ID and (ephemeral) nonce to derive an ephemeral key:

$$\tilde{K}_{user} = \operatorname{KDF}(K_{master}, \mathit{UserID} \mathbin \| \mathit{nonce})$$

Note that the tilde above the ephemeral key is one way of showing that it might be ephemeral - different documents may use different notations and a tilde does not always mean ephemeral.


Using Montgomery ladder to calculate the coordinates

The Montgomery Curve is introduced by Peter L. Montgomery for speeding up the Pollard and Elliptic Curve Methods of integer factorization. Montgomery Curves are in the form $By^2=x^3+Ax^2+x$ and it is also represented as $M_{A,B}$.

Addition and Doubling Formulas of Montgomery Curves

Given Montgomery Curve $By^2=x^3+Ax^2+x$ and the point $P_1 = (x_1,x_1)$ and $P_2 = (x_2,x_2)$ than the addition and doubling, $P_3 = (x_3,x_3) = P_1+P_2$ as follows

Addition formula in Affine Coordinates: $(P1 \neq \pm P2)$

\begin{align}
\alpha & = (y_2 − y_1)/(x_2 − x_1)\\
x_3 & = B \alpha^2 − A − x_1 − x_2\\
y_3 & = \alpha (x_1 − x_3) − y_1
\end{align}

Doubling formula in Affine Coordinates: $(P1 = P2)$

\begin{align}
\alpha & =  (3x_1^2 + 2 A x_1 + 1)/(2 B y_1)\\
x_3 & = B\alpha^2 − A − 2x_1\\
y_3 & = \alpha (x_1 − x_3) − y_1
\end{align}

As usual, these are calculated from the geometrical meaning of addition.

Montgomery Ladder

The Montgomery Ladder is an algorithm to calculate $[x]P$ for a given scalar $x$ and a point $P$.

Represent $x$ in binary $x= x_0 + 2x_1 + 2^2x_2 + \cdots + 2^mx_m $ and let $m= \lfloor \log_2 x \rfloor$.

  R0 = 0
  R1 = P
  for i from m downto 0 do
     if xi = 0 then
        R1 = point_add(R0, R1)
        R0 = point_double(R0)
     else
        R0 = point_add(R0, R1)
        R1 = point_double(R1)
  return R0

Calculation

Now, $x=3 = 1 + 2\cdot 1$, i.e. $x_0=1$ and $x_1 =1$

$m= \lfloor \log_2 3 \rfloor = 1$. Therefore, we visit the loop twice.

since $x_i =1$ we will be always in the else case, or simply we run the below.

  1. R0 = 0
  2. R1 = P
  3. R0 = point_add(R0, R1)
  4. R1 = point_double(R1)
  5. R0 = point_add(R0, R1)
  6. R1 = point_double(R1)
  7. return R0

$R_0 = \mathcal{O}$
$R_1 = P$
$R_0 = \mathcal{O} + P = P$
$R_1 = P + P = [2]P$
$R_0 = [2]P+P = [3]P$
$R_1 = [2]P+[2]P = [4]P$
return $R_0 = [3]P$

The given Montgomery Curve $3y^2=x^3+x^2+x$ than it is $M_{1,3}$ so $A=1,B=3$ and $P=(9,8)$

$[2]P = (1,10)$ by the below simple sage math point doubling.

k.<a> = GF(11, modulus="primitive")
k.modulus()
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
alpha  =  (3*x1^2 + 2 *A * x1 + 1)/(2 * B * y1)
x3 = B * alpha^2 - A - 2 * x1
y3 = alpha *(x1 - x3) - y1
print x3
print y3

$[3]P = [2]P+P = (5,2)$ by the below simple sage math point addtion.

k.<a> = GF(11)
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
x2 = k(1)
y2 = k(10)
alpha = (y2 - y1)/(x2 - x1)
x3  = B * alpha^2 - A - x1 - x2
y3  = alpha * (x1 - x3) - y1
print x3
print y3

Notes :

One might say that we don't need step 6 since we are not returning it. Keep in mind that that is a need for protection from side-channel attacks.
This ladder algorithm from Wikipedia and it is not an optimal one. See The Montgomery Powering Ladder for a better version.
There is also a full coverage chapter "Montgomery curves and the Montgomery ladder" by Bernstein and Lange to further read.


I would advise against this.  When implementing slow-hashing (such as bcrypt or scrypt), it's usually recommended to select as high a work-factor as is tolerable (in relation to how much time the user is willing to wait, and/or how much strain you're willing to put on your server).  Assuming you're working within this constraint, using two distinct slow hashes would force you to halve the work-factor of each, potentially making one or both more susceptible to attack.

Of course, depending on the context, if time and resources are not limited, then your proposal is at best a buffer to dampen paranoia, but honestly I think scrypt is mature enough to be used exclusively.


What about using only XOR gates in homomorphic encryption?

As poncho comments, a homomorphic encryption scheme that only supports the XOR operation would not be fully homomorphic, i.e., it would not allow evaluation of all functions. However, you can try to optimize the implementation of a function in order to minimize the number of AND's at the cost of extra XOR's. This is not only relevant for FHE but also in secure multi-party computation (MPC), where the XOR operation can also usually be computed much faster than AND.

Optimizing the circuit of a function to include less AND's, and possibly more XOR's, is a well known technique to make FHE and MPC applications run faster. In fact people have made special compilers to automate this process. An example of such a compiler in the MPC space can be found in this paper (although by now there are probably better ones around).


Does Elliptic Curve Integrated Encryption Scheme (ECIES) provide IND-CCA2 security?

So the question is if ECIES gives by default IND-CCA2 security?

Yes it does. There's a proof in modern Cryptography by Katz and Lindell, but I'll leave that one to Yehuda to write an answer around. This answer will instead be based on DHIES (PDF) which is the generalization of ECIES and essentially does an ephemeral DH key exchange with the public key, hashes the shared secret and performs an encrypt-then-mac authenticated encrytion of the payload using the hashed secret.

The paper states the security bound as

$$\mathrm{Adv}^{\text{ind-cca-fg}}_\text{DHIES}(t,q,\mu,c)
\leq
\mathrm{Adv}^{\text{ind-cpa-fg}}_\text{SYM}(t,0,0)+
2\cdot\mathrm{Adv}^{\text{odh}}_{\mathcal G,H}(t,q)+
2\cdot\mathrm{Adv}^{\text{suf-cma}}_\text{MAC}(t,1,c,q,\mu)$$

with $t$ being the upper bound on the time complexity of the adversary and $q$ being the upper bound on the number of decryption queries and $\mu$ being the upper bound on the number of bits asked to the decryption oracle and $c$ being an upper bound on the length of the challenge ciphertext for the CCA experiment. $\mathrm{Adv}^{\text{suf-cma}}_\text{MAC}$ is the SUF-CMA security of the MAC and $\mathrm{Adv}^{\text{ind-cpa-fg}}_\text{SYM}$ is the CPA security of the symmetric cipher.

Now only remains $\mathrm{Adv}^{\text{odh}}_{\mathcal G,H}$ which is the advantage with which an adversary can distinguish $(g^u,g^v,H(g^{uv}))$ from $(g^u,g^v,R)$ with $R,u,v$ being randomly sampled from either the group or the hash output set. Additionally the adversary is given access to an oracle computing $\mathcal H_v(X)=H(X^v)$.

So if the above Oracle Diffie-Hellman (ODH) assumption is hard for the given group (and it should be for elliptic curves), and if the symmetric cipher and the MAC are secure, then ECIES is also secure.


Can somebody explain the major contributions of the tenants of the Gödel Prize 2013?

Joux's work is really summarized by this answer already on Crypto.SE. He discovered a way to generalize Diffie-Hellman to multiple (more than 2) parties. In particular though, he presented a single round protocol for key establishment between 3 parties. Something that until then was thought to be impossible.

Boneh and Franklin developed the first fully functioning identity based encryption (IBE) scheme. The premise of IBE is that your public key should be your public identifier (such as your email address) instead of simply a large number. Then, to say send you an encrypted email, the sender only needs to know your email address.  IBE has led to other really cool constructions such as functional encryption and attribute-based encryption. For more on IBE, see What is Identity-Based Encryption (IBE) and why is it “better”?


Visualization of Elliptic Point Addition

I think this is on-topic for cryptography, as this is a basic elliptic-curve related question that anyone interested in ECC will come across. Moreover, it is easily answered.

Although on the picture it seems that there is no third intersection point in the plane, there is one. Note that not the whole curve can be fit into this picture, since at some point we cut off the rest of the $x$ and $y$-axis. What remains unknown is what happens when $x$ becomes larger. Well, what happens is that slope of $E$ keeps increasing (resp. decreasing), going towards infinity (resp negative infinity). You can see this by considering the function $y(x)=\sqrt{x^3-\frac{29}{10}x+1}$, and always taking the positive (resp. negative) root. The derivative will go to infinity (resp. negative infinity) as $x$ goes to infinity.

Therefore if you want to continue the drawing of this curve, you have to extend the rightmost part by making it more and more vertical. If you also extend your line, you will see that they will intersect.


Special Honest Verifier Zero-Knowledge is a particular case of Honest Verifier Zero-Knowledge; that is, if a protocol satisfies SHVZK, it satisfies HVZK. SHVZK has been introduced to simplify discussions about $\Sigma$-protocols. In $\Sigma$-protocols, HVZK is typically proven as follows: fix an arbitrary challenge $e$, and show that it is possible to efficiently generate a random transcript $(c, e', a)$ for a $\Sigma$-protocol, conditioned on $e = e'$. If such a simulator can be exhibited, then the $\Sigma$-protocol is clearly HVZK. The term SHVZK refers to $\Sigma$-protocols where this particular condition holds.
Note that similarly, the term special soundness is generally used to refer to a sufficient property for the soundness of a $\Sigma$-protocol (typically, that given two transcripts $(c,e,a)$ and $(c,e',a')$ for the same $c$, it is possible to extract a witness efficiently), which is typically satisfies by most $\Sigma$-protocols. Each time, "special XXX" simply means "a specific notion which is sufficient for XXX".


Are collision-resistant hash functions even possible? [see description]

Collision resistance relates to how difficult it is to find a collision, not the total lack of collisions.  In other words, a hash function $H(x)$ is collision resistant if and only if all attackers given reasonable computational resources (probabilistic polynomial algorithms) have only a negligible chance of finding two messages, $m_0$ and $m_1$ such that $H(m_0)=H(m_1)$.

Note that this is not an information theoretic type of security - an attacker given unlimited computational resources will always be able to find a collision (or as many collisions as desired).  It is possible to get information theoretic security from something like a one-time MAC (where even an unlimited attacker has only a negligible chance of devising two messages with the same MAC tag), but that relies on a secret key used only once, whereas in a hash function nothing is secret.


Primality test in GPG/RSA or extract numbers of private key

GPG (1.4.21) does not use an elliptic curve primality test. It uses 5 strong pseudoprime tests, with the first to base 2 and the others to a random base. For factors large enough that the key is secure, odds that a composite creep by chance are entirely negligible in practice (for a quantitative estimate see appendix F.1 in FIPS 186-4). Also, the mere fact that an RSA key allows decryption of messages, or generation of signatures that verify, is a fair probabilistic primality test of its factors.

To dump a private key not protected by a passphrase under gpg 1.4.x, use
gpg --export-secret-key -a "john doe" | gpg --list-packets --debug 2

For a key version 4 algo 1, the factors of the public modulus are skey[3] and skey[4].


What are the dangers of using CPU clock drift for generating random data?

A TRNG is never used instead of a CSPRNG. They serve different purposes. A TRNG is used to seed a CSPRNG. A CSPRNG alone isn't enough to generate random data since it's reproducible. A hardware entropy source alone isn't enough to generate random data because all entropy sources have biases.

For any purpose that's related to security or cryptography, a random generator (CSRNG) is built by seeding a cryptographically secure pseudorandom generator (CSPRNG) with an entropy source, which is some physically obtained unpredictable, secret input. The CSPRNG whitens the entropy source.

The CSPRNG turns a small amount of data (typically a few thousands of bits) into an effectively endless stream of bits, and ensures that all the bits are independent. More precisely, a CSRNG must have the property that if an adversary sees all the output bits except one (but does not get to see the RNG's internal state), they have no clue what that hidden bit is: it could be either 0 or 1 and the adversary can only guess with a chance of success that's extremely close to $1/2$ — no more than $1/2+2^{-N}$ for a CSRNG with $N$-bit quality (e.g. $N=128$). A CSPRNG guarantees that property provided that its seed is sufficiently “varied”, in that the adversary can't guess the seed with a chance of success that's better than about $2^{-N}$.

A discretization of a physical phenomenon always has biases: some sequences of bits are more probable than others, due to characteristics of the physical phenomenon or to measurement errors. Using this as input to a CSPRNG destroys all the correlations between successive bits. The CSPRNG also has other benefits, including the ability of combining multiple phenomenons, with the safety that combining sources together never weakens the result (even if one of the sources turns out to be partially or totally known to the adversary, the quality of the resulting RNG is still at least as good as the other sources).

Now the real question is, is clock drift (jitter) useful as an entropy source? The answer is yes, it is used in practice. Fast Digital TRNG Based on Metastable Ring Oscillator by Vasyltsov et al. (2008) gives an overview of work in that domain in §2.

If you're an application writer, that's not something you need to care about. Entropy gathering is done by the operating system.

If you're a system integrator, you have to take care that your system has proper entropy sources. All modern PC processors (RDRAND) and smartphones (running iOS, Android or Windows) have hardware RNG (using phyiscal phenomenons that differ from chip to chip). Embedded devices are a very varied breed, some have good entropy sources, others don't; clock drift is often irrelevant in this realm because there aren't enough distinct clocks (unless one has been provided for the very purpose of generating entropy through drift, in which case the manufacturer will generally provide a some firmware or driver code to perform the required measurements).

Measuring clock drift is not trivial. You need to make sure that you're reading data from clocks that aren't synchronized. You need to give the system enough time to get initialized and then for the clocks to get out of synch. You need to beware of environmental parameters; for example some clocks may be effectively unpredictable at sufficiently high temperature but completely predictable at lower temperature. A good hardware RNG will provide a quality estimate. Statistical tests on an entropy source can sometimes help figure out whether it's operating correctly, but often the types of biases depend on the physical construction of the source and tests need to take this physical construction into account in order to be effective.


Are this recommendations from Colin Percival correct?

First off, it sounds like you already have an opinion and should talk to Colin directly.

My take is, at least at the time, he was very much in favor of tried-and-true (and easy, relatively) encrypt-then-mac schemes.  Namely, he advocated CTR+HMAC.  This is easy and known to be secure.  You pay for it a little by deriving more key material than otherwise needed, by more expensive computations, and by more algorithms.  None of those things matter to most users in most settings.

In 2010 Poly1305, related AE schemes, and EdDSA were less well-known, less well standardized (which often serves as an implementation aid), and less widely implemented than good old AES-CTR and SHA2-256 (and RSA).  Again, these are me casting about to explain Colin P. when in fact you could just ask him if you so desire.


In order for a collision to happen "by chance", about $2^{80}$ hashes need to have been computed. If 1000 hashes were computed every millisecond, then this would take 38,334,786,263 years. So, I doubt that this has happened by chance.

Having said that, I would be very surprised if large government organizations do not already have SHA collisions (using better collision finding algorithms).


No, it is not better. To send the salt encrypted, one would need a key and IV (another salt) to encrypt it. This adds unnecessary complexity as the security of the ciphertext does not depend on the salt being kept private. So, encrypting the salt adds negligible security yet adds a fair amount of complexity. Keeping things as simple as possible is often a good rule of thumb.


I've searched about this problem these two days, considering the paper cygnusv mentioned, and finally after reading the problem related to the pqc implementation, I guess that's the condition which is not formally mentioned in NTRU papers. And this condition
$$q > p(6d + 1)$$
must be true in order for the probability of unrecoverable messages to be less than $2^{-80}$.


Can I use modulo $n^2$ arithmetic where $n=p \cdot q$ for ElGamal encryption?

To completement the answer of SEJPM, note that ElGamal should not be used directly over the ring $\mathbb{Z}_{n^2}$ (more precisely, over the multiplicative group $\mathbb{Z}_{n^2}^*$), because it is insecure here. To be more precise, it is still one-way, which means that if you get an encryption of a random plaintext, it's hard to recover the plaintext. However, it is not IND-CPA secure anymore, because the IND-CPA security property of ElGamal reduces to the Diffie-Hellman assumption - but the Diffie-Hellman assumption does not hold over $\mathbb{Z}_{n^2}^*$. Intuitively, the reason behind this is that computing the Jacobi symbol is easy, and given $(g^a, g^b)$ where $a,b$ are some exponents, and $g$ is some element of $\mathbb{Z}_{n^2}^*$, it holds that

JacobiSymbol$(g^{ab}) = $ JacobiSymbol$(g^a)\cdot$JacobiSymbol$(g^b)$

which allows to break the decisional Diffie-Hellman assumption with non-negligible probability (with probability 1/2, this relation will not be satisfied with a random tuple, while it is always satisfied for a Diffie-Hellman tuple).

This can be fixed by working into proper cyclic subgroups of $\mathbb{Z}_{n^2}^*$ where elements have all Jacobi symbol 1 - the DDH assumption is believed to hold over such groups, so ElGamal should be secure. However, note that it will be far less efficient than standard ElGamal over prime order groups, and should only be used if it is part of a larger system where you really need to use the specific structure of $\mathbb{Z}_{n^2}$.


are there more efficient methods than HMAC to achieve convergent encryption?

The answer depends on how you define ‘convergent encryption’ and what threats you're hoping to defend against.  Here are two broad options that you might mean:

You're a storage service and you make lofty promises about encryption to your users, but you also do deduplication between unrelated parties.  (Maybe you abuse the term ‘zero-knowledge’; it's trendy among such companies!)  You just want to prevent an adversary from

recovering a plaintext they don't know, or
forging a plaintext for deduplication so that some hapless user who tried to store a file would get the forgery when they later try to retrieve it.

This is a very weak notion of security, but it roughly corresponds to, e.g., Dropbox, who presumably save a lot of money by deduplicating files unrelated people have shared many times, and who presumably earn a lot of brownie points by preemptively checking files for known child pornography and notifying the authorities (of course, exactly the same technique applied to subversive imagery would serve the interests of an authoritarian government, but we won't talk about that).

So you use $H(m)$ as the encryption key, and maybe $H(H(m))$ as the deduplication index, like Tahoe-LAFS does (without convergence secrets).  In this case, you need a collision-resistant hash function $H$—otherwise an adversary could find a collision between a benign file $m$ and a file $m'$ full of child pornography, and then persuade the victim to try uploading $m$.  There are no shortcuts.  Sorry.  If you really need to squeeze performance out of it, some collision-resistant hash functions are cheaper than others—see eBASH for fair performance comparisons on a wide variety of hardware.
You, or you and a small group of friends, have secrets that you can use to encrypt files, and you want to do deduplication among your (and your friends') files.  You want to prevent an adversary who doesn't know the key from even confirming a hypothesis about what files are stored, and, of course, from fooling you into accepting forged files.

What you need to derive the convergent encryption key and deduplication key is a pseudorandom function family: the output must be indistinguishable from uniform random to anyone who doesn't know the secret key.

SHA-256 is expensive mainly because you it pays for collision resistance, and while HMAC-SHA256 is a perfectly respectable and widely available PRF, you're still paying for that collision resistance when you use it.

Here are a couple of alternatives:

A cheaper PRF like Kravatte, which is based on 6-round Keccak, in contrast to the 24-round Keccak used in SHA-3.  There aren't a whole lot of widely available options here: most work in this area goes into short-input PRFs or collision-resistant hashes.
Pick a universal hash family $H$ with bounded collision probability, such as Poly1305, and a short-input PRF $f$, such as ChaCha or Salsa20 (or HChaCha or HSalsa20, slightly cheaper).  Then build a long-input PRF as follows:

\begin{equation*}
    F_{k_1,k_2}(m) := f_{k_1}(H_{k_2}(m)).
  \end{equation*}

That is, loosely, use $H$ to compress the message with low collision probability, and then use $f$ to scramble it.

Universal hash families like Poly1305 are considerably cheaper to compute than SHA-256 or any other collision-resistant hash functions, and can be vectorized effectively.  Poly1305 implementations are widely available, e.g. in NaCl/libsodium as crypto_onetimeauth_poly1305.

If the collision probability of $H$, that is $\Pr[H_{k_2}(x) = H_{k_2}(y)]$ for $x \ne y$, is at most $\varepsilon$, and if the best PRF-advantage against $f$ is $\delta$, then the best PRF-advantage against $F$ is at most $q^2 \varepsilon + \delta$ where $q$ is the number of messages you handle under a single key (proof).

For Poly1305, $\varepsilon = 8\lceil L/16\rceil/2^{106}$ for messages up to $L$ bytes long, so with Poly1305 and ChaCha, if you store—or if the adversary tries to forge—up to a billion megabyte-long files (a petabyte of data), the advantage of the adversary at distinguishing any of the convergence keys from uniform random strings will be at most about $2^{60} 2^{16} 8/2^{106} + \delta = 2^{-27} + \delta$.  If the adversary puts additional computational power to it, that only raises $\delta$—but unless they can break ChaCha, the additional computational power will pale in comparison to what they need to guess your 256-bit key.

This technique is part of how the deterministic authenticated cipher AES-GCM-SIV works—the output of $F$ is used both as an authentication tag and to derive a per-message subkey to encrypt the message.  (Of course, AES-GCM-SIV uses GHASH, not Poly1305, and AES, not ChaCha, so it's good for hardware implementations and bad for software implementations.)


Is solving a modular linear equation a hard problem when the coefficient is not an invertible element?

Calculate $g = GCD(a, n)$ and $n^\prime = n / g$. If $b \not\equiv 0 \pmod g$, then there is no solution.

Divide whole equation by $g$ giving you $a^\prime· x_0 = b^\prime \pmod{n^\prime}$ and solve for $x_0$. Then solutions for $x$ are $x_0 + k· n^\prime$ for $k = 0, 1, ..., g-1$.


Why use $(r,s)$ instead of $(r,s^{-1})$ as DSA signature?

Well, it's been an entire day, and no one has given an authoritative answer; I'll throw in my guess as to why the people designing DSA made the choices they did.

With DSA, there are three operations that are relevent to this discussion:

A: do precomputation of a signature (without seeing the message being signed)
B: given a precomputed signature and a message, generate the actual signature
C: verify a signature.

Standard DSA and your variant DSA perform exactly the same operations, except that standard DSA computes a modular inverse during steps A and C, while your variant computes it at step B.

It is true that standard DSA does two modular inverse, while your variant does only one; however, that may not be the only factor.

If we look at step B, we see that the operations involved at quite cheap (a single modular multiplication and addition); if we were to include a modular multiplication operation there, we would increase the cost of that operation by a large percentage.  In contrast, steps A and C are already expensive (involving a modular exponentiation or point multiplication); including a modular inverse only slows down those operations by a small percentage.

That is, DSA has the property that, with precomputation, generating a signature is extremely fast.  Your variant significantly reduces this advantage; the DSA designers designed to keep this advantage, even at the cost of increasing the total computation required.

Now, you may disagree with the above logic; in fact, people have proposed a DSA-variant exactly like what you suggest.


The answer is that just because your algorithm is polynomial time doesn't mean it's fast.

The paper Algorithms for the Approximate Common Divisor Problem claims in section 3.1 that a lattice dimension $>800$ "should be large enough to prevent any practical lattice attack".

As a completely non-rigorous yet enlightening demonstration, we can compare the complexity of a brute-force the noise" approach with the lattice-based methods for $(\lambda^5,\lambda^2, \lambda)$-GCD.

The "brute-force the noise" approach involves $\mathcal{\tilde O}(2^{\frac{3}{2} \rho })$ multiplication/remainder operations on numbers with $\approx \gamma$ bits, where $\mathcal{\tilde O}$ is the usual notation hiding poly-logarithmic factors. So let's say it takes time $\propto \gamma \cdot 2^{\frac{3}{2} \rho } \sim\ \lambda^5 \cdot 2^{\frac{3}{2} \lambda } $.

The SDA lattice algorithm using fpLLL (aka $L^2$ lattice reduction) takes time $\mathcal{\tilde O}(\gamma^2 \cdot t^5) \sim \lambda^{25}$, where $t$ is the dimension of the lattice.

Let's compare these two asymptotic results for the choices of parameters in the paper Fully Homomorphic Encryption over the Integers with Shorter Public Keys. (See below for more details.)
At the "small" level, the time estimation for "brute-force the noise" is $6 \cdot 10^{16}$, and for SDA is $4 \cdot 10^{25}$.
At the "large" level, the time estimation for "brute-force the noise" is $7 \cdot 10^{24}$, and for SDA is $2 \cdot 10^{34}$.

So we'd need the coefficient hidden in $\mathcal{\tilde O}$ to be a billion times smaller for SDA than for "brute force" for lattice reduction to be practical -- and we just don't have that.

However, I cannot justify the "rule-of-thumb" asserted in Fully Homomorphic Encryption over the Integers and used in Fully Homomorphic Encryption over the Integers with Shorter Public Keys that LLL takes time exponential in $t$.

Experimentally, the runtime will appear to be exponential until your sizes  are large enough that the asymptotic behavior dominates.

Note that the reason for the inadequacy of LLL is not because it only gives an exponential approximation to the shortest vector. As Nyugen notes in Predicting Lattice Reduction:

  The most important fact is that asymptotically, all the algorithms known seem to only achieve an exponential approximation factor as predicted by theory, but the exponentiation bases turn out to be extremely close to 1, much closer than what theory is able to prove.

Furthermore, Algorithms for the Approximate Common Divisor Problem examine this limitation and find that the only effect is to require a mild increase in the number of samples (and hence the lattice dimension). This is because increasing the lattice dimension increases the size of the second shortest (independent) vector in the lattice. If the ratio between the sizes of the target vector and second shortest vector is sufficiently small, then LLL will find the target vector.

We can see this concretely for the parameters in the paper Fully Homomorphic Encryption over the Integers with Shorter Public Keys.
At the "small" level, $(\gamma, \eta, \rho) = (.86 \cdot 10^5, 1632, 24)$.
Ignoring the exponential approximation factor tells us we need $535$ samples. Accounting for it yields $546$ samples.
At the "large" level, $(\gamma, \eta, \rho) = (19 \cdot 10^6, 2652, 39)$.
Ignoring the exponential approximation factor tells us we need $7272$ samples. Accounting for it yields $9042$ samples.

Thus, for heuristic analysis of the lattice-based algorithms applied to AGCD, we can get away with pretending that LLL solves the Shortest Vector Problem.


Is AES-256 over AES-128 weakening the original encryption?

Obviously, as long as the AES-128 (TLS) channel is keyed independently from the AES-256 (file encryption), the TLS encryption cannot damage the file encryption.

Let us consider what would be true if it could.  If that somehow did weaken the file encryption, this would allow this attack on an encrypted file – he could take that encrypted file, and send it through his own encrypted TLS link.  He can then use the records from that encrypted link, and exploit the weakness to attack the file encryption.

Since he can do that, any weakness that would apply to the combination would also apply to the file encryption alone.  We don't believe that there's anything wrong with the file encryption (assuming that the AES-256 key is randomly chosen), hence there isn't anything wrong with the combination.


Why use indexing for searchable encryption?

It is mainly to make the search operation more efficient. In searchable encryption, mostly invert index is used. It is a data structure that stores mapping from words to documents or set of documents i.e. directs you from word to document, e.g. something like:

word 1: {doc1, doc2, doc3}
word 2: {doc1, doc3}
word 2: {doc1}

The earliest searchable encryption scheme searches data by sequentially scanning through all encrypted documents. This is not scalable. For example, if you have 10 document and each has 10,000 words in it, then you need to scan through 100,000 encrypted words. For each encrypted word, the comparison operation is cryptographic and is slow (compared to that in plaintext). If you have a large amount of data, you probably will get your results hours later after you submitted your query.
However, the number of distinct words in the documents probably is not very big (say 5,000), and does not increase with the amount of your data. Therefore, using indexes is a natural choice because now you only need to search through the index, and perform comparison operation in the number of distinct words (or even less) to find which entry in the index corresponds to your query, and then you can find the list of documents that contain the word you queried by retrieving and decrypting the list (this part requires additional cryptographic operations, with the number linear in the size of the list). But anyway, this is more scalable and allows searchable encryption to handle very large datasets.
Nowadays, mainstream searchable encryption schemes all use some sort of indexes. Of course, the index structure and cryptographic comparison operation vary greatly from scheme to scheme, but the core idea is to make the search time sublinear in the size of encrypted data.


Does preimage resistance and/or collision resistance imply the infeasiblility of finding fixed points in hash functions?

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hash functions.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise.}\end{cases}$

This function is just as preimage-resistant and collision-resistant as SHA-256 is, yet it holds that $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$, is almost as easy and is left as an exercise to the reader.

Per comment: a good general purpose cryptographic hash function is essentially a random function, and wide, with no special case like in the above counterexamples. We have no efficient algorithm to exhibit a fixed point (if there is one, which has probability $1-1/e\approx63\%$) for such functions. Essentially, we must compute the function at $O(2^k)$ points where $k$ is the width. Therefore, there can't be a good general purpose cryptographic hash with a known fixed point. And that extends to all general purpose cryptographic hashes that I know, including those which collision-resistance or preimage-resistance is seriously broken.


How can I tell which curve a given ECDSA implementation uses? (P-521 or something else)

Signatures make sense only if there is a verifier somewhere, and the verifier uses the public key, which is public. The public key will normally include the unambiguous specification of the curve. If the public key does not include such a specification (e.g. a closed system where both signer and verifier know a priori the curve), then you can still infer things:

A public key is a curve point $(X,Y)$ which fulfils the curve equation $Y^2 = X^3 + aX + b$ where $a$ and $b$ are part of the curve definition. This allows you to match the public key point with some standard curves.
If point compression is used, you might have only the $X$ coordinate. You can still match that with standard curves, because $X$ is part of the base field on which the curve is defined. If you find a $X$ which is a 521-bit integer or not much smaller (e.g. no smaller than 500 bits) then chances are high that the curve is P-521. Although it could be a custom non-standard curve of the same size.
If you only see the signature themselves, then you can still try to match that to standard curves. An ECDSA signature is a pair of integers $(r,s)$, where both $r$ and $s$ are in the $1..q-1$ range, $q$ being the size of the curve. There again, if both $r$ and $s$ are in the 500 to 521 bits, then chances are that the curve is P-521, because $r$ and $s$ would be too large for the smaller curves (the previous ones are 401-bit only), and it would be very improbable to obtain both values below 521 bits if the curve is B-571 or K-571 (the next ones, among the standard curves).


For this particular type of attack, the best it can do is attack 10 rounds of DES, with 2^50 time complexity and 2^20 plaintexts.


No for this scenario where the message is statically sized, using a HMAC is not required. You can use a sufficiently strong hash such as SHA-2 or SHA-3 instead if you must.

That said, it would probably be more neat to use a HMAC or even KDF. The advantage is that these algorithms do take input keying material as a separate parameter. This might be interesting if you want to keep the pepper secret; you could store it in a hardware device and use it for HMAC, for instance.

Currently you are using the hash as poor-man's KDF. So if you can spare a few cycles you might go for a more luxurious option like HKDF (which is based on HMAC).


Need help understanding this exercise's solution

OK, so this takes a bit of guessing, but I'm assuming the following:

A is the identity of A, which can be used to select the right public key of A;
Kxa() is a signing operation (with message recovery) that signs the random Ra and a tag Ts which is used as proof;
Kya() is an encryption operation with the public key A, so that the session key Ks is kept confidential;
Kxb() is a signing operation (with message recovery) that signs the random Ra together with session key Ks;
Ks(M) is message encryption with the established session key Ks.

The general idea seems to be to perform authentication of both parties and session key establishment for message transport security.


How do you prove an encryption scheme is IND-CPA or IND-CCA?

As SEJPM said in his comment: one proceeds by contrapositive, first suppose that such an adversary with an unfair advantage exists and use that adversary to break a well known assumption, e.g.: the adversary can be used to factorise a large composite integer (as defined in RSA).

As of today, we have no efficient algorithm to factorise large composite integers, even after years of research spent trying to achieve this. So from this it is safe to assume that the problem is hard, and that no such adversary exists. The scheme is IND-CPA or IND-CCA secure, because if it was not, an adversary breaking the scheme will break this well known problem.

The next step is to proceed by transforming an instance of the well known problem (a composite integer to be factored) into an instance of the scheme, if the adversary is able to break the scheme with a non-negligible advantage, it will also inadvertently solve the hard problem, this is a contradiction as we have assumed the problem to be hard.


Does repeated xoring of the (same) key K lower the entropy of K?

If I take a strong key K of length $n$ taken from a good source of randomness, it will have $n$ bits of entropy and will be independent of anything else (not derived from it).

If we later Xor it with a weak password K* for instance or something else we still have the same $n$ bits of entropy.

Each bit is still uniformly random and independent of each other. Even if K* bits were biased and correlated.

It is easy to see with an example. If we Xor a random key with all zeros, we get the same; if some bits are 1, it's just a negation, and negating a uniformly random bit is still uniformly random. Also, correlated bits won't make a difference. If I negate every other bit, or follow some other pattern, it makes no difference.

However if you XOR with something dependent on the key, all bets are off, and you could end up with 0 entropy, for instance, by Xoring with itself.


Zero-knowledge proof of knowledge without replay

"She knows" has a definition: an extractor algorithm should exist that produces the witness $x$ while talking to the proving party in place of verifier. For zk-SNARK from Christian Lundkvist in the medium post you referenced, the protocol is non-interactive and the "proof of knowledge" is derived from the "knowledge of exponent assumption", not from the extractor algorithm. It seems there's a consensus that both definitions are good enough.

My point is, a non-interactive "proof of knowledge" is very different from an interactive one. It seems it was a design choice that zk-SNARK proofs should be verifiable by everyone without interaction.

There's a chance with a designated verifier (introduced in late 80s). As a setup, the potential verifier sends some hash $t$ to prover and runs this protocol to show he knows the witness $s$ for that additional hash: $H(s) = t$. The prover then runs a protocol to show his knowledge of either one of two preimages ($s$ or $x$).
This could mean a circuit representing equations:
\begin{gather*}
  z (1 - z) = 0 \\
  H(zs + (1 - z)x) = zt + (1 - z)y
\end{gather*}
It follows only that a verifier that keeps his $s$ secret can be assured original statement $H(x) = y$ is true.

Make a protocol interactive again :)


Can ChaCha20 be repurposed as a general purpose permutation function like Gimli?

There is a library called Monocypher* that heavily utilizes derivatives of ChaCha and Salsa. (Plus Poly1305, X25519, and Ed25519.) The algorithms it uses, XChaCha20, Blake2b, and Argon2 all use different permutations but those permutations are all extremely similar.

I don't know if any Salsa variant's permutation can be used as is. It certainly would be risky to decrease the round count by much. I'm not aware of published analysis of any variant used as a stand-alone permutation.

If ChaCha's permutation function (with 20 rounds) is a secure public permutation, then we know the algorithm ChaCha20 is secure. But if we know ChaCha20 is secure, that doesn't mean we know the permutation is secure. One reason why ChaCha20 is so robust (and therefore why it can get away with few enough operations to make it fast) is because of the algorithm as a whole, not just the permutation. The only thing you can qualify as attacker controlled inputs in ChaCha20 is the IV. Message bits (plain- or ciphertext) have zero influence in ChaCha20's permutation function. This is a smaller attack surface than what's possible with block ciphers, hash functions, and public permutations. All of which have security properties that ChaCha20 doesn't need to have. The permutation it uses wasn't designed to be one-size-fits all, so we don't have much evidence yet to say it's safe for general-purpose permutation use.

One property of the ChaCha permutation is that it does not use round constants. It's also an ARX (add rotate xor) construct. It has a trivial fixed point $P(0) = 0$. Which results from

Addition: $0 + 0 = 0$
XOR: $0 \oplus 0 = 0$
Rotation: $0 \text{ rotate-by } k = 0, \forall \space k$

The presence of a fixed point in a randomly chosen permutation function is to be expected. Finding one a permutation on a large block size is a harder problem if it requires brute force. This known fixed point might be a problem for some (but not all) applications. For Salsa, Chacha, Blake 1 and 2, their respective permutations are used with a portion of their input bits fixed to a non-zero constant so it isn't a problem there.

In the Gimli paper I found (ctrl-f) a reference to round constants, so I'm pretty sure it doesn't have a zero fixed point.

The number of rounds you use of a ChaCha-like permutation function obviously has an effect on security. It seems like even the algorithms that use less than 20 rounds probably are still safe. But that likely has a lot to do with how the permutations are used in addition to the robustness of the permutation itself. I can't tell you if 20 rounds are safe enough for all or most general purpose permutation uses, if you can safely decrease them, if you need to increase them, or if increase the number of rounds will help.

The safe answer to your question is no.

And although it doesn't seem like it, this is a sort of "Should I implement my own crypto?" question. I've considered the same idea. Breaking two secure constructs into pieces and recombining pieces Frankenstein's monster style doesn't make the end result secure.

* I'm aware of the project but haven't looked into it. It's probably safest to use NACL, but I can't and shouldn't endorse any option.


Entity authentication protocol by encryption

In general, no, this is not safe, and in the cases where it is safe it's wasteful.

The safe (but wasteful) cases are those where you're already using an Authenticated Encryption with Associated Data (AEAD) scheme or applying a Message Authentication Code (MAC) over the ciphertext. It's wasteful since those both have their own authentication systems, but safe since it prevents a MITM from modifying the ciphertext in transit.

Without authentication the MITM can simply modify data in the ciphertext beyond the start of $N$, ie anything in $ID_{B}$. This won't affect $N$ at all in any of the commonly used modes (either a direct stream cipher or a block cipher in CTR or CBC mode). There are some caveats to my statement, eg if $N$ is not a multiple of the underlying block size in CBC or CTR mode then data out to the next multiple of the block size needs to be preserved by the attacker, but since you didn't specify anything about the cipher used for encryption I'll go with the most general case.


How to find the inverse of f(x) in NTRU key generation?

$\newcommand{\Z}{\mathbb{Z}}$This somewhat oblique notation $F_q(x) = f(x)^{-1} \pmod q$ means that $F_q$ is the inverse of a unit element $f$ in the quotient $(\Z/q\Z)[x]/(P)$ of the polynomial ring $(\Z/q\Z)[x]$ by the ideal generated by some monic irreducible polynomial $P$ with integer coefficients.  $P$ is a system parameter presumably defined in an earlier slide.  Given $P$ and $f$, you can compute $F_q$ with the extended Euclidean algorithm.

The notation is presumably chosen because we variously map the same polynomial expressions with integer coefficients of $P$, $f$, and $g$ into three different polynomial rings, $\Z[x]$, $(\Z/q\Z)[x]$, and $(\Z/p\Z)[x]$ at different times.  It wouldn't be quite right to say that $f$ is an element of $(\Z/q\Z)[x]/(P)$, because in the next sentence $f$ will be an element of $(\Z/p\Z)[x]/(P)$ instead.  Saying $a(x) = b(x) \pmod q$ means we are taking the base ring of the polynomials $a$ and $b$ to be $\Z/q\Z$ for that equation.


Unsure of syntax used in Searchable Encryption

$\mathcal{M}$ is the domain of the inverse trapdoor permutation $\pi^{-1}$. For example, if $\pi^{-1}(m)= m^d \bmod N$ implemented using RSA, then $\mathcal{M}=Z^*_N$. The domain/range of $\pi$ and $\pi^{-1}$ are all $\mathcal{M}=Z^*_N$.

Generate a random big integer in $Z^*_N$ (roughly from range 1 to $N$) should be fine (there is a negligible probability of getting something not in $Z^*_N$, but since it is negligible we don't care).


How many rounds is needed to implementing Schnorr Non-Interactive zero-knowledge protocol

No, sending both parts of the proof together does not create any additional risk.

Notice that at the end of the protocol, Victor knows the same set of values, regardless of whether it has been split into two rounds or not. So whatever he would be able to achieve in "one-round" version, he can still achieve after the second round of the two phase protocol.


Where can I find Secp256k1 ECDSA test vectors?

I don't unfortunately know a good set of preexisting test vectors for this curve. Instead I decided to advice you how you can generate them yourself. Hope this helps.

Some (fairly recent) OpenSSL versions are familiar with secp256k1 curve. You may use e.g. OpenSSL's command line tool openssl's commands ecparam, ec, dgst to generate key pairs, parameter files, and ECDSA signatures using the curve.

If you do some scripting, you can even create files that appear similar than the the ECDSA test vectors from NIST/CAVP.

On the other hand, if you do not wish to force specific value for $k$ for testing  or use deterministic variant of ECDSA signing (see RFC 6979), then you may be better of trying this:

Validate your verification function with some pregenerated test vectors (containing both correct and incorrect signatures). Note: Remember to generate the vectors using some independent implementation (possibly e.g. OpenSSL).
Validate your signature function for compatibility with your verification function.


Since the numeric constant in the exponent is approximately $1.923 $ the expression for the average number of iterations, say time complexity $T$  given by
$$T=\exp \left( \left(\sqrt[\leftroot{1}\uproot{0}3]{\frac{64}{9}} + o(1) \right) (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}} \right)$$
is proportional to (for $n$ large enough so that $o(1)$ term is negligible)
$$T\propto \exp \left(1.923 \times  (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}
\right)$$
which is upper bounded as (ignoring a multiplicative constant in front)
$$T\leq \exp \left(2   (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}  \right)=T_0^2.$$

Clearly $T$ is polynomial/exponential if and only if $T_0$ is.

Now consider the more general expression
$$f(\alpha,n)=\exp \left(  (\ln n)^{\alpha}(\ln \ln n)^{1-\alpha}
 \right),\quad \alpha \in [0,1],$$
and note that when $\alpha=1,$ $f(1,n)=\exp(\ln n)=n,$ hence it is exponential in the bitsize $\log_2 n$ of the input $n.$

Also note that when $\alpha=0,$ $f(0,n)=\exp(\ln\ln n)=\ln n,$ hence it is polynomial in the bitsize $\log_2 n$ of the input $n.$

However we have $T_0=f(1/3,n)$ with $\alpha=1/3$ above so the complexity we have is a linear combination in the exponent of polynomial and exponential complexities. This is referred to as subexponential but superpolynomial complexity.


You will always need to have some way of identifying the other party, be it a pre-distributed key or out-of-band procedures as you are describing. There is no purely digital method that can do this without some kind of shared knowledge.


Is there a complete list of Signature Algorithm names?

You can find a list in the bouncyCastle source code for Asn1SignatureFactory, here:

https://github.com/kerryjiang/BouncyCastle.Crypto/blob/master/Crypto/x509/X509Utilities.cs

In addition to that, you can list all registered SSL-digest-methods with the following C-Code:

#include <openssl/evp.h>
#include <openssl/objects.h>
#include <stdio.h>

void my_callback(const OBJ_NAME *obj, void *arg)
{
  printf("Digest: %s\n", obj->name);
}

int main(int argc, char *argv)
{
  void *my_arg;
  OpenSSL_add_all_digests(); //make sure they're loaded

  my_arg = NULL;
  OBJ_NAME_do_all(OBJ_NAME_TYPE_MD_METH, my_callback, my_arg);
}

The callback receives objects of type OBJ_NAME:

typedef struct obj_name_st {
    int type;
    int alias;
    const char *name;
    const char *data;
} OBJ_NAME;

You can look up the associated EVP_MD* via EVP_get_digestbyname().
This method finds a lot of things, many of which you probably don't want:

$ ./a.out
Digest: ripemd160WithRSA
Digest: ssl2-md5
Digest: sha384
Digest: sha224
Digest: SHA224
Digest: md4
Digest: sha512
Digest: RSA-SHA256
Digest: DSA-SHA
Digest: sha1WithRSAEncryption
Digest: MD5
Digest: MD4
Digest: ssl3-sha1
Digest: ripemd160
Digest: sha
Digest: SHA384
Digest: SHA1
Digest: ssl3-md5
Digest: sha256
Digest: sha384WithRSAEncryption
Digest: SHA512
Digest: DSA-SHA1-old
Digest: dsaWithSHA1
Digest: ecdsa-with-SHA1
Digest: whirlpool
Digest: RSA-RIPEMD160
Digest: rmd160
Digest: RIPEMD160
Digest: RSA-SHA1-2
Digest: RSA-SHA1
Digest: dsaWithSHA
Digest: md5WithRSAEncryption
Digest: DSS1
Digest: RSA-MD5
Digest: dsaEncryption
Digest: ripemd
Digest: md4WithRSAEncryption
Digest: DSA
Digest: sha512WithRSAEncryption
Digest: SHA
Digest: dss1
Digest: RSA-SHA224
Digest: RSA-SHA512
Digest: SHA256
Digest: md5
Digest: RSA-SHA384
Digest: sha1
Digest: sha224WithRSAEncryption
Digest: RSA-SHA
Digest: shaWithRSAEncryption
Digest: sha256WithRSAEncryption
Digest: DSA-SHA1
Digest: RSA-MD4


Is it safe to encrypt data by simply randomizing chunks based on a permutation?

This is called a transposition cipher. It is the kind of thing that was commonplace before the invention of the computer, and some people were really good at breaking that in mere minutes (e.g. Edgar Allan Poe). In all generality, breakage is done by backtracking (wrong hypotheses on permutation elements leading to "impossible digraphs" that cannot occur in normal text).


As far as I know, unknow key-share (UKS) attacks are mostly related to key exchange protocols.

Presentation
An UKS attack on an authenticated key exchange (AKE) protocol is an attack whereby an entity $A$ ends up believing he shares a key with entity $B$,and although this is in fact the case, $B$ mistakenly believes the key is instead shared with an entity $M \not = A$.Since the adversary $M$ doesn't obtain the shared secret key, he can't modify or decrypt the messages between
$A$ and $B$. However, $M$ can take advantage of the entities' false assumption about the identity with whom they share the key.

Example on authenticated Diffie-Hellman
Let's say $A$ and $B$ want to perform an AKE.
$1. \hspace{2cm} A \longrightarrow M(B):\hspace{0.3cm} Cert_A, g^a, S_A(g^a)$
$2. \hspace{2cm} M \longrightarrow B:\hspace{1cm} Cert_M, g^a, S_M(g^a)$
$3. \hspace{2cm} B \longrightarrow M:\hspace{1cm} Cert_B, g^b, S_B(g^b)$
$4. \hspace{2cm} M(B) \longrightarrow A:\hspace{0.2cm} Cert_B, g^b, S_B(g^b)$
where $M(B)$ denotes $M$ masquerades as $B$ and $S_X$ denotes a signature using the private key given in $Cert_X$.
So at the end of the protocol, $A$ and $B$ share the secret key $g^{ab}$ but $B$ mistakenly believes that this key is shared with $M$ and not with $A$. Note that $M$ does not know the shared secret key $g^{ab}$.

Answers

I am having trouble finding many resources out there to help.

I posted something some months ago about UKS attacks on KEA protocol, maybe it can help you.
Also, an interesting paper about UKS attacks helped me a lot to understand it.

Are their any other ways to prevent these types of attacks?

As mentioned in the paper cited above, there are different ways to prevent UKS attacks:

(A) Certificates of both entites should be exchanged prior to the
key    agreement protocol.
(B) CA should issue certificates whith checking that each entity
possesses a private key corresponding to its public key.
(C) Identities of the sender and intended receiver as well as
flow    numbers should be included in the messages being signed.

In my opinion, (C) is the most important one.

What other nefarious things could M do in this scenario? Is it ever practical to alter the ciphertext before sending to B to change the
meaning of the message in some way?

A famous hypothetical scenario where an UKS attack can have damaging consequences is the following:

Suppose that $B$ is a bank branch and $A$ is an account holder.
Certificates are issued by the bank headquarters, and within each
certificate is the account information of the holder. Suppose that the
protocol for the electronic deposit of funds is to exchange a key with
a bank branch via an authenticated key agreement protocol. At the
conclusion of the protocol run, encrypted funds are deposit to the
account number in the certificate. Suppose that no further
authentication is performed in the encrypted deposit message (which
might be the case to save bandwith). If the UKS attack is successfully
launched, then the deposit will be made to $M$'s account instead of
$A$'s account.

Hope it helps.


The point is that you will only be able to reconstruct the seed if you know every single bit of maskedSeed and maskedDB and you will be able to decode the message only if you know every single bit of the seed and maskedDB.

If an attacker gets only a single bit of maskedDB wrong, feeding it to the MGF will yield a totally different result and will not allow him to reconstruct the seed.

If only a single bit of maskedSeed is incorrect, the reconstructed seed will also contain a single incorrect bit and again, feeding it to the MGF will lead to a totally different value and it will not be possible to reconstruct the original message.


Hardwired secret key in public / private key encryption

“Hardwiring” an input into a (say, Boolean) circuit usually means taking a circuit $C$ with two inputs $x\in\{0,1\}^n$, $y\in\{0,1\}^m$ and then fixing the inputs corresponding to $y$. This gives the circuit $C_y$ that for every $x$ returns $C(x,y)$ [AB]. Thus, hardwiring is more about circuits and has nothing to do with encryption schemes.

In the example of multi-input functional encryption, the circuit $\mathsf{G}_f$ can be seen as a function that takes a master secret key and $n$ ciphertexts as input. By hardwiring a particular $\mathsf{MSK}$, you are fixing the first input to the circuit $\mathsf{G}_f$ to this $\mathsf{MSK}$.

[AB]: Arora and Barak. Computational Complexity: A Modern Approach.


How can we compare an encrypted number with a normal number?

If this is not performed under the encrypted version of the plaintext on the semi-honest party there is a problem.

Assume that there is a method $f(m,c)$ return $T$ if the values are same and $F$ if the values are not same. So you can compare a plaintext with a ciphertext.

With the same way you did, an attacker can test any number to reveal the value.

   for i in range(plaintext):
       if F(i,c):
          break

So this must be as follows;

negate the value,
encrypt it with the Paillier,
Sent it to the server.
the server calculates the summation,
the server returns the result.

If there are more than one k-means on the server, and, actually, you are trying to perform

SELECT * FROM table WHERE key_mean = query

you need to apply a different method.


Does hash_df use binary or an ASCII hexadecimal representation for numbers to be passed to the hash function?

In step 4.1 of the algorithm:

Counter is expected to be a 1 byte binary value
no_of_bits_to_return is a 4 byte bigendian binary value
input_string is a variable length binary value
$||$ is concatination (just like you guessed)

So, Hash(&bytearray) would be appropriate.

The trickiest part is the 'no_of_bits_to_return' -- that's bigendian (and so a value of 24 would be represented by the four bytes 0x00 0x00 0x00 0x18), which is the opposite of how the most common processors internally represent a 4 byte value.

Now, if you were to convert to (say) ASCII hex first, well, it probably won't affect the security of the algorithm; however, it won't be the HASH_DRBG algorithm, but something else.


Describing Discrete Logarithm Assumption

Should $a$ be chosen from $\mathbb{Z}_p$ not $\mathbb{Z}^*_p$ ? After
  all, $p$ is the order of $G$, so we should be able to pick any element
  from $G$?

Yes, $\mathbb Z_p$ should be used as there is not reason to require that the $a$-th root needs to exist for arbitrary elements.

  Is $\in_R$ a common notation? I've also seen $\leftarrow_R$. Does it
  make sense as something that says we are picking $a$ uniformly at
  random?

$\in_R$ is somewhat common, as are $\gets_R$ and $\stackrel{\$}{\gets}$, ideally you will pick one notation and clarify its meaning in a dedicated "notation" section or you just embed the relevant clarification into the wording, e.g. "Select $a\in_R\mathbb Z_p$ uniformly at random".

  Instead of $a$, should I say that we choose $h \in_R G$? That is,
  choose a random group element rather than a random exponent?

The definition from the Introduction to Modern Cryptography by Katz and Lindell uses a random group element here, but given that $g^x$ is a random group element for random choice of $x$ and that $g$ is a generator, so there exists exactly one $x$ for each group element, I'd say these definitions are identical.

  Should the probability be equal to $negl(n)$ or $\leq negl(n)$? Does
  it matter, and why?

As $\operatorname{negl}(n)$ is any function that grows slower than any polynomial it doesn't matter whether $=$ or $\leq$ is used. However $\leq$ would seem more natural, as you are essentially "bounding" the probability to be negligible and $\leq$ immediately conveys this bounding aspect to the reader instead of hiding it behind the definition of $\operatorname{negl}$.

Just for the fun of it, here's the definition from the aforementioned Introduction to modern Cryptography by Katz and Lindell (2nd edition):

$\newcommand{\opn}{\operatorname}\newcommand{\mc}{\mathcal}$

  The discrete-logarithm experiment $\opn{DLog}_{\mc A,\mc G}(n)$:

  Run $\mc G(1^n)$ to obtain $(\mathbb G,q,g)$, where $\mathbb G$ is a cyclic group of order $q$ (with $||q||=n$), and $g$ is a generator of $\mathbb G$.
  Choose a uniform $h\in\mathbb G$.
  $\mc A$ is given $\mathbb G,q,g,h$ and outputs $x\in\mathbb Z_q$.
  The output of the experiment is defined to be $1$ if $g^x=h$, and $0$ otherwise.

  Definition 8.62 We say that discrete-logarithm problem is hard relative to $\mc G$ if for all probabilistic polynomial-time
  algorithms $\mc A$ there exists a negligible function $\opn{negl}$
  such that $\Pr[\opn{DLog}_{\mc A,\mc G}(n)=1]\leq\opn{negl}(n)$

The book priorly defines $\mathcal G$ to be a function generating a group and $||\cdot||$ to be the bit-length of a number.


The attack you describe (at least insofar as I understand it) is essentially a type of related key cryptanalysis, which is a valid but very strong attack model that is not always accepted by cryptographers as showing serious weaknesses in a cipher.  In terms of the plausibility of such an attack, the general idea is that if the expanded key (consisting of all the round keys) is stored or transmitted insecurely then it might be possible for an attacker to alter them in some particular way, even if she cannot simply read them directly.  The alterations to the rounds keys would induce the cipher to behave differently in a way that enables the attacker to deduce bits of the key.

This scenario might seem to stretch credulity a little too much, which is why not all cryptographers are concerned about related key attacks.  However, weaknesses in a cipher under related key attacks can often inspire breaks under the more conventional one-key model (e.g. Biham's 'key schedule' related-key cryptanalysis of LOKI inspired slide attacks, and differential related-key cryptanalysis techniques aided the development of biclique cryptanalysis).  We also may be interested in the strength of a cipher when it is being used as the core of a hash function, where the attacker can directly control the 'key' input.

You do have to be a little careful about with the type of "key alteration" you propose (i.e. transposition of round keys).  So long as the attacker is restricted to just transposing round keys that should be fine.  But if the attacker is given more fine-grained control, to the point where she can transpose individual bits of the round key, then that is much too strong of a capability to grant her, because not even an Ideal Cipher can resist an attacker with that ability.  Related key attacks are only really "interesting" (in the sense of revealing a structural weakness in a particular cipher) if an Ideal Cipher can in principle be secure against them.


Allowing the user to choose the hashing formula at the registration

This doesn't sound like a good idea. As CodeInChaos already pointed out, choose one good password hashing scheme like scrypt or bcrypt and go with that

The reason why what you proposed isn't so great is that you'll give the user the choice between a few good password hashing options and the work of an attacker is at best multiplied by the number of options you proposed.

By doing that it's also unlikely that a bad password hashing will make its way into the list and the users picking that one will be at the attacker's mercy.
Lastly I don't think it's a good design to leave security relevant choices up to the user.

How should an average user know better than the designer of the system what's good for him ?


How can I securely encrypt the same message multiple times?

No, "RSA with some random bits added" does not suffice. There have been attacks against many of bad padding techniques for RSA. Instead a known secure mode of operation is required. The most well known secure mode is RSA-OAEP.

The earlier RSA with PKCS#1 v1.5 padding may also be secure, but it has a well known attack against it called the Bleichenbacher attack. More to the point, there is also a million messages attack which shows one example what kind of attacks is possible if you just "add some random bits" to a message.

Note that the security argument of RSA-OAEP was under serious scrutiny. This has weakened but not broken the security proof for RSA-OAEP, which had to be adapted to the new situation. Furthermore, implementation mistakes may allow attacks against RSA-OAEP.

This is why there are some proponents here for RSA-KEM. Here RSA simply encrypts a random number in the range $[0, N)$, which is then fed into a key derivation function or KDF, which in turn creates a secret key which can be used for symmetric encryption. This is a rather elegant scheme which is provable secure, just like OAEP.

Note that the security proof for RSA-OAEP and RSA-KEM assumes that the RSA trapdoor itself is secure. However, that's something that cannot be proven - we just assume it is secure because it withstood all attempts so far.


No, wrapping the data key set seems a good idea to me. It's pretty standard and should even work with e.g. hardware modules.

Note that your old ciphertext would still rely on the security of your old secret (password) when you choose this scheme! If $Enckey$ is ever guessed it can be confirmed by decrypting (the first part of) your ciphertext.

There is a more efficient way: you can simply calculate the difference on bit level using XOR between the keys calculated from your old and new secret. Then store that difference with the ciphertext. So retrieve the old key simply XOR with your newly created key to retrieve the older key.

This is more efficient CPU-wise and may require fewer bits (if CBC padding is used). I'd still go for your current scheme though. The XOR method is less flexible and will expose your new master key if any of the data keys is ever leaked.

Notes:

I would not request too much output from PBKDF2, rather use another KBKDF such as HKDF to split off multiple keys from the derived key;
PBKDF2 requires an iteration count (work factor) as configuration parameter, which seems to be missing;
HMAC can be configured to use SHA-1, but it isn't SHA-1 and SHA-1 doesn't take two input parameters;
you could consider using SIV to encrypt your keys, in that case you don't need a second authentication key or IV;
you might consider storing a random salt with the ciphertext;
a fully random data key set for each separate encryption is more secure;
addition 1: if you do not use an IV when encrypting the keys then it is easy to spot which ciphertext was encrypted with the old keys.


Why not generate the authentication key from the key and nonce in GCM?

So, why not derive $H$ from $K$ and $N$ (the nonce).

Well, if you are asking why the original GCM designers made that specific design decision (CodesInChaos point is valid, but software implementations weren't actually considered in the original design):

A critical goal in the GCM design was that it be hardware pipeline friendly; that is, you could process the message in a 10-14 stage pipeline (where each AES round was a separate pipeline stage), and that there are minimal wasted steps.  Doing some additional computation before you could process the initial AAD data would cause a break in the pipeline, and so violate this goal.
It wouldn't help.  If the $H$ value was derived from an $N$ and $K$ pair, then if you repeat an $N$ value, you still repeat the $H$ value (and hence leak that $H$ value).  What your idea would mean is that the attacker would have to repeat the $N$ value to forge (as the attacker wouldn't know the $H$ value for any other $N$); however that is not a practical issue for attackers, who can freely pick the $N$ value for their forgeries.


ECC algorithm pollard's $\rho$ complexity

When we say an algorithm is 'exponential' or 'polynomial', when mean that the running time is bounded by an exponential or polynomial function of the size of the input in bits.  That is, the input of the function is not $p$, but $\log p$.  And so, $O(\sqrt p ) = O( e^{1/2 \log p})$ is bounded by an exponential in $\log p$.

Also note that the Wiki article is not talking about the Pollard rho algorithm applied to ECDLP, instead it is talking to Pollard rho applied to factorization.  For the Pollard rho applied to factorization, the time it takes is a factor of $p$, where $p$ is the smaller factor; hence, (because the factors are approximately the same length) $\sqrt p$ is roughly $n^{1/4}$ (with the $polylog(n)$ factor coming into place because Pollard rho isn't perfectly efficient in this scenario).


From the paper:

  I selected (A − 2)/4 as a small integer, as suggested by Montgomery, to speed up the multiplication by (A − 2)/4

The smaller the value (A-2)/4 is, the faster is the multiplication by that value (which is required by the point doubling formula).

So basically the curve was found by incrementing the A value, restricting to the values where (A-2)/4 is an integer, until it generates a curve with order $4n$ or $8n$ where $n$ is prime (and some other criteria described in the paper: the twist order should be in the same format; and $n$ should be larger than $2^{252}$ so that the private key can be generated by simply randomly filling a byte buffer and not having to bother with the case where the private key is equal to the curve order).


Is a random length-extension worth the effort?

The short answer is no.

I'll assume $SHA256_d(M)$ is $SHA256(M)$ when $d=0$, else $SHA256(SHA256_{d-1}(M))$.

$SHA256_1$ is protected against length extension attacks.

The only sizable benefit that I see in parameterizing $d$ is that it allows tuning a slow down of the computation intended as a protection against brute force attacks. However there are more flexible primitives for that purpose, like PBKDF2 or Scrypt, and Scrypt is considerably safer for similar slowdown.

Leaving $d$ unknown to improve security is almost pointless. An adversary can have a rough figure about $d$ by a variety of side channels, e.g. duration of the computation. And an adversary knowing $SHA256_d(M)$ but neither $d$ nor $M$ is annoyed by a factor of less than 4 by not knowing $d$ if she knows that $M$ is in her dictionary. She does as follows:

Chooses a small starting $n>0$ per some guess of $d$, or just $n=1$.
Computes $SHA256_n(X)$ for all the $X$ in the dictionary, comparing the known $SHA256_d$ with the $SHA256$ obtained at each of the $n$ steps, proclaiming success (with high probability) if there is a match.
Having ruled out all values of $d$ up to $n$, she doubles $n$ and continues at 2.

If she happens to have enough memory (as much as needed to store as many hashes as entries in the dictionary) she can store the last result obtained for each entry at step 2, and reuse that later; the penalty falls to a factor of less than 2. Update: further, with the same memory, increasing $n$ by $1+\lfloor Log(n)\rfloor$ at step 3 makes the penalty factor become arbitrarily close to 1 as $d$ grows (this can be tuned-up for low $d$ by changing the constant and the base of the logarithm).


Understanding simplification steps when solving complicated equations in Galois Field

All these operations are in a finite field, in particular, a prime field with modulus $p = 2^{255}-19$.

So, for example, $4/5$ is not $0.80$, but $4$ times the inverse of $5$ modulo $p$ (i.e. the number that, when multiplied with $5$, results in the remainder $1$ when divided by $p$). In particular, $1/5$ is $11579208923731619542357098500868790785326998466564056403945758400791312963990$ (because that times 5 is equal to 1 when reduced modulo $p$). The same applies to multiplication, addition and so on - everything is modulo $p$.

The final result is correct, as demonstrated by this Sage code:

sage: F = GF(2^255-19)
sage: xx = (F(1)-(F(4)/F(5))^2) / (F(-1) + (F(121665)/F(121666))*(F(4)/F(5))^2)
sage: xx.sqrt(all=True)
[15112221349535400772501151409588531511454012693041857206046113283949847762202,
 42783823269122696939284341094755422415180979639778424813682678720006717057747]


Merkle tree (dm-verity) with SHA-256 vs. SHA-1

SHA-1 is measurably faster and I would like to know if its insecurity is still there, when used in a Merkle tree.

Yes, the insecurity is still there. Any collision in the underlying hash function can be used to produce a collision in the root of the Merkle tree.  A quick example:

Suppose our SHA-1 Merkle tree has two leaf nodes, $a$ and $b$, and that we know a SHA-1 collision such that $\text{SHA-1}(m_1) = \text{SHA-1}(m_2)$ but $m_1 \neq m_2$.  The root hash of the Merkle tree will be $h = \text{SHA-1}(\text{SHA-1}(a) \| \text{SHA-1}(b))$.

We can create two different trees with the same root hash by setting $a$ to $m_1$ in one tree, and $a$ to $m_2$ in the other (and keep $b$ the same for both trees).  These trees will have the same root hash: $\text{SHA-1}(\text{SHA-1}(m_1) \| \text{SHA-1}(b)) = \text{SHA-1}(\text{SHA-1}(m_2) \| \text{SHA-1}(b))$, because $\text{SHA-1}(m_1) = \text{SHA-1}(m_2)$.  In other words, an attacker can swap out a block in the bottom of the tree without the root node "noticing".

The use of a Merkle tree will not protect against problems in the underlying hash function's collision resistance.  I wouldn't recommend using SHA-1 if security is an important consideration here.

Normally, I would recommend using BLAKE2.  It (well, its predecessor) was a finalist in the SHA-3 competition (i.e. it's secure), and it's faster than both SHA-1 and MD5.  Unfortunately, I don't know if it's available in dm-verity.


In short

BGV (the one you linked), FV and GSW.

More details

The scheme you have linked is known as BGV and I would say that it is the most important. There is a public implementation on Github.
If the application can run in parallel, then BGV is probably the best current choice, because its plaintext space can be view as a product of rings, which gives the user the ability to encrypt several values in a single ciphertext. Then, a single homomorphic operation is actually equivalent to several plaintext operation in parallel.

The FV is another scheme with that feature and is the one that SEAL implements now.

If the application can't take advantage of the parallelism, then, I think the best choice nowadays is the so called FHE over the Torus, or TFHE.

Since you asked for influential papers, it is worth noting that TFHE is based on FHEW, by Miccianco, which is based on a paper by Sheriff Peikert, which is based on (this highly influential paper) GSW, again by Gentry.

Also, YASHE had an efficient version that was implemented by SEAL before, but it turned out to be insecure.


Privacy and Integrity in Public Cryptography

Signing and encrypting together is not secure in this method, at least in the way most would perceive security. For example, Bob would likely interpret this message as being sent from Alice to Bob. However, Alice may have sent it to Charles who decrypted and re-encrypted the signed message under Bob's public-key. In order to do this securely, you need to add the sender's and receiver's identities inside (the signature with Alice's key should contain Bob's identity, and the encryption with Bob's key should contain Alice's identity). In addition, you need to use CCA-secure encryption. In short, this isn't so simple and you need to check the details in order to determine if it's secure. This topic is called "SignCryption" and you can look it up for more information.


If cryptographic hashes are completely unique, could they theoretically be used to transfer data?

No.

They can be used to identify data you've stored elsewhere.  For example, you can probably find a preimage under MD5 for 6f5902ac237024bdd0c176cb93063dc4 by searching the web, and it might even be meaningful English text.  And you probably won't find more than one preimage.

This is the idea of content-addressed storage, which is widely used, e.g. by Tarsnap—although it would be a mistake to use MD5 or SHA-1 for content-addressed storage, because collisions are readily available to anyone who wants them, which have hilarious effects on systems doing just that.

But even if you had a practical preimage attack on MD5—say, an array of quantum computers large enough to run Grover's algorithm—it would give you a preimage, but not necessarily (and probably not) the preimage I have in mind that you'll find with a web search.  Instead, it would probably give you 128 or 192 or so bits of gibberish.  And if you ran it for longer it would probably give you many such blocks of gibberish, long before finding anything that resembles English text.

If the messages you want to transmit cover only a small subset of all bit strings, and are structured with a distribution you know something about, you could invent a better compression scheme for it.  Maybe if there are few enough messages with convenient enough structure, you could compress them into 128 bits.  This depends on specific information about the distribution of messages, and it depends on having no more than $2^{128}$ pigeons to stuff into holes.

But a preimage-resistant cryptographic hash function like MD5 would be about the stupidest compression scheme imaginable, because not only was it designed without knowledge of your distribution of messages, but it goes to great lengths to obscure the original message and to make ‘decompression’ as hard as it can so that the best way is to guess a possible original message and check it.


Brute force, get AES keys by multiple plain-texts with their cipher-texts

No. You are talking about a known plaintext attack against AES. There is no known attack, discovery of such an attack would be invaluable to there likes of MI6, FSB, and the NSA.


Viability of using One-Time-Pad + HMAC in low-volume IoT communications

Two points adding to Raoul's answer are:-

To generate a HMAC you need a key, and this key will have to be stored within the meter.  If there's a key, traditional encryption can be used if you can somehow generate IVs.  Or don't generate them and accept that repeat readings will be transmitted as repeat cipher text.  This probably isn't a particularly serious issue for water consumption. Although, a static reading suggests the occupants are on holiday and the house is unoccupied. So this is an example of information leakage.
You compare OTP distribution to traditional key distribution.  That might be true but have you considered the office end?  This application of a OTP is about the worst possible kind.  OTPs do not perform well in many to one transmissions.  There will have to be a huge one time pad at the receiving station to decode readings from (100k+) meters. And how will you decode the reading if the meter ID is encrypted?  If you use an IP address as an identifier, that can be intercepted so what's the point of encrypting the meter ID?  And what happens if you roll out more meters?  More OTP material has to be stored, interwoven with existing OTP material and subsequently tracked at the base office.

In summary, this is not the most appropriate scenario for a OTP. But, it you only had one meter (for lets say a home automation system), OTP is perfect as it eliminates all the cryptographic code /testing issues.  Assuming of course that you can estimate the required pad size as Raoul suggests.