Proving one time pad is perfectly secret

First, be careful about case:

The uppercase letters denote random variables in some probability space.
The lowercase letters denote particular values in the domains of the corresponding random variables.

For example, if the probability space is $\Omega$, then $C\colon \Omega \to \{0,1\}^\ell$ is a random variable for the ciphertext in the one-time pad system, and $c \in \{0,1\}^\ell$ is a particular value of a ciphertext, which at some sample $\omega \in \Omega$ might be the value of $C(\omega) = c$.

The random variable $C$ is related to the random variables $M$ and $K$ by $C = M \oplus K$, which is the standard mild abuse of notation for random variables meaning that $C(\omega) = M(\omega) \oplus K(\omega)$ in any sample $\omega \in \Omega$.  Any fixed values $c$, $m$, and $k$ might or might not be related by $c = m \oplus k$, although if in some sample $\omega$ we have $C(\omega) = c$ and $M(\omega) = m$ and $K(\omega) = k$ then $c$, $m$, and $k$ are indeed related by $c = m \oplus k$.

For any fixed message $m \in \{0,1\}^\ell$, in the event $E = \{\omega \in \Omega \mathrel: M(\omega) = m\}$ where the message $M$ takes on the value $m \in \{0,1\}^\ell$, what can you conclude about $C$?  In other words, if for any $\omega$ we have $M(\omega) = m$, what can you say about $C(\omega)$?  Can you use this to eliminate $C$ from the ellipsis in $\Pr[\;\cdots \mathrel| M = m]$?

Next, if you have an equation about the random variable $K$ without reference to $M$, given an equation about $M$, recall the definition of independence of random variables and how it relates to conditional probabilities.  Finally, use the probability mass function for $K$, and you'll have an answer.


what does output parameters of lwe estimator stands for?

δ_0: the root Hermite factor required
β: the BKZ block size
d: the dimension of the lattice being reduced
m: the number of LWE samples used


Algorithm for factoring knowing RSA private key

May and Coron's result is a deterministic reduction from knowing a multiple of $\varphi(n)$, in this case $de-1$, to the factorization of $n$. This method involves lattice reduction and Coppersmith's algorithm.

But there is a much simpler probabilistic method to factor $n$ discovered by Miller, of the famed Miller-Rabin primality test. Suppose you are able to find a nontrivial square root of $1$, i.e.,
$$
x^2 \equiv 1 \pmod{n}, \quad x \neq \pm 1\,.
$$
Then $x^2 - 1 \equiv (x+1)(x-1) \pmod{n}$, and we find a factor by computing $\gcd(x \pm 1, n).$ But how do we find such a root? By exploiting the relation
$$
a^{\varphi(n)} \equiv 1 \pmod{n}\,.
$$
Let $t = \varphi(n) / \gcd\left(\varphi(n), 2^{\log_2(n)}\right)$ be $\varphi(n)$ with every power of 2 removed from it.
If we knew $\varphi(n)$ exactly, all we had to do was compute $a^{t} \bmod n$ for a random base $a$, and repeatedly square until we obtained a $1$—that value would be our $x$ as above. This will yield a factor depending on the order of $a$ modulo $p-1$ and $q-1$. This process naturally extends to any multiple of $\varphi(n)$, and in practice only a couple of bases are necessary to factor $n$.

Here's some Sage code that implements this:

def factor_from_d(n, d, e):
  kphi = d*e - 1
  # remove powers of 2 from phi multiple
  kphi = kphi // gcd(kphi, 2^int(log(n, 2)))
  while True:
    # random base
    b = randint(0, n)
    x = power_mod(b, kphi, n)
    # try to find a nontrivial square root of 1
    while x != 1 and x != n - 1:
      # found one!
      # x^2 = 1 (mod n)
      # x^2 - 1 = (x + 1)*(x - 1) (mod n)
      if x^2 % n == 1:
        return gcd(n, x + 1), gcd(n, x - 1)
      x = x^2 % n

p = random_prime(2^512)
q = random_prime(2^512)
n = p*q
e = 2^16 + 1
d = inverse_mod(e, (p-1)*(q-1))
factor_from_d(n, d, e)

Coming back to May and Coron, their algorithm is conceptually simple, but more complex to implement from scratch. Here we want to find a small root of
$$
f(x) = n - x \pmod{de - 1}\,,
$$
which is guaranteed to exist because $n$ and $\varphi(n)$ are relatively close together. This root is precisely $p+q-1 = pq - (p-1)(q-1)$. Having $p+q$, we can solve the polynomial $x^2 - (p+q)x + n$, which has $p$ and $q$ as its roots.

Using Sage's small_roots function, we can do this easily:

p = random_prime(2^512)
q = random_prime(2^512)
n = p*q
e = 2^16 + 1
d = inverse_mod(e, (p-1)*(q-1))

P.<X> = Zmod(d*e-1)[]
f = X - n
pq = ZZ(f.small_roots(X=2^513, beta=0.9, epsilon=0.1)[0] + 1)
disc = pq^2 - 4*n
(pq + isqrt(disc))/2, (pq - isqrt(disc))/2


"SHA-256" vs "any 256 bits of SHA-512", which is more secure?

SHA-512 truncated to 256 bits is as safe as SHA-256 as far as we know. The NIST did basically that with SHA-512/256 introduced March 2012 in FIPS 180-4 (because it is faster than SHA-256 when implemented in software on many 64-bit CPUs). SHA-224 is just as safe as using 224 bits of SHA-256, because that's basically how SHA-224 is constructed. What bits are kept (provided that's fixed) is immaterial to security, but for compliance to NIST specification, the left bits shall be kept.

As stated in this other answer, in the general case of a hash function only assumed to be collision-resistant or preimage-resistant, restricting its output can make it entirely insecure. A trivial example is the 512-bit function obtained by appending 256 zeros to the output of SHA-256, which is both collision-resistant and preimage-resistant, but trivially insecure when restricted to its 256 right bits.
The stated design goal of SHA-2 functions are preimage-resistance and collision-resistance: "The hash algorithms specified in this Standard are called secure because, for a given algorithm, it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest". Therefore, truncation of SHA-2 functions is not playing by the book.
Update: FIPS 180-4, which defines SHA-2 functions SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 and SHA-512/256, explicitly endorses truncation in its section 7: "Some application may require a hash function with a message digest length different than those provided by the hash functions in this Standard. In such cases, a truncated message digest may be used, whereby a hash function with a larger message digest length is applied to the data to be hashed, and the resulting message digest is truncated by selecting an appropriate number of the leftmost bits".
Truncation of SHA-2 functions is safe as far as we know. That's the very principle used to construct SHA-224 from a slight variant of SHA-256, as well as SHA-384, SHA-512/224, and SHA-512/256 from a slight variant of SHA-512 (the variant being to change the internal initialization vector, in order to avoid that the output of one function reveals bits of the output of another one).
The reason why SHA-2 functions can be safely truncated is that these functions have another unstated design goal, that they reach as far as we know, which is: being computationally indistinguishable from a random function, except for having the length-extension property¹ and being that particular function. That strong property is necessary to be able to use the hash with confidence in proofs of protocols made in the Random Oracle Model, and implies collision-resistance and preimage-resistance (the reverse is not true). Truncation (by keeping any fixed subset of their output bits) of a function indistinguishable from a random function also is indistinguishable from a random function (proof sketch: any hypothetical distinguisher for the truncated function is easily converted into a distinguisher for the original function, with the same effort and advantage).
The principle can be extended to any size; e.g. SHA-512 truncated to 128 bits is, as far as we know, as fine a 128-bit hash as can be (regardless of which bits we keep), and unquestionably much preferable security-wise to MD5 (another 128-bit hash, which collision resistance is badly broken). However, collision for an $n$-bit hash can be found in about $2^{(n/2)+0.33}$ hashes, little memory, and efficient parallelization (see Parallel Collision Search with Cryptanalytic Applications). Hence for 80-bit level security (which has sometime been considered an absolute minimum in the early 2000s, and is to be considered insufficient nowadays absent argument of the contrary), when collision resistance is necessary, we should keep at least 160 bits; and when only preimage-resistance is necessary, we should keep at least 80 bits.

¹ The length-extension property is that given the bitstring $H(m)$, the bit length $\ell$ of bitstring $m$ (but not $m$ itself), and any bitstring $s$, it's possible to efficiently compute $H(m\mathbin\|r_\ell\mathbin\|s)$ where $r_\ell$ is a short, efficiently computed bitstring depending only on $\ell$. Truncation of many bits removes the length-extension property. As noted in this other answer, the length-extension property is an undesired artifact, and the basis of attacks in some contexts; and SHA-512 truncated to 256 bits is safe in such contexts, when as SHA-256 is not.


As explained in a comment: A generic attack is one that works against all block-ciphers (with a given block and key size), without consideration about the structure of the block-cipher.

One generic attack for a block cipher of a given block size $b$ bits builds a dictionary of input/output pairs (e.g. from past plaintext/ciphertext), for a fixed key. When an input or output in that dictionary gets reused, the adversary gains an advantage. In many scenarios, that's expected after about $2^{b/2}$ blocks (less in ECB mode, more in CTR mode). Such attack works for any block cipher, including an hypothetical one implemented as a random permutation.

If we in addition consider the key size of $k$ bits, another generic attack, brute force key search, enumerates the keys. With at least $k/b+1$ input/output pairs, that's likely to find the key after about $2^{k-1}$ attempts.

Sometime we have a generic attack against a whole category of block ciphers sharing a common characteristic. For example, there's a generic attack against all Feistel ciphers, based on the fact that for any key, they implement an even permutation; this allows an adversary having built a dictionary of all input/output pairs except two of these, to deduce the remaining two with certainty. Another example (given in that answer) is an enhanced brute force key search removing most of the work associated to the first and/or last round in a Feistel cipher.


What is the correct way to implement PBKDF2 + AES CBC + HMAC?

You'll find there's a lot of splitting hairs regarding this topic, especially key derivation. But yes, your pseudocode is fine, although you may want to revise (0, 128) => (0, 127) and (129, 256) => (128, 255) ... (correct me if I'm wrong?). Also, you might want to implement a constant-time comparison function for verifying the mac.

  Have I derived the keys correctly, splitting them in half based on the
  output of the KDF?

This is fine. Some people would disagree. See here here and here for more in-depth discussion.

  Am I computing the HMAC correctly by combining the iv + cipher. Does
  it matter if I had done cipher + iv instead?

Yes, you're computing the HMAC correctly. No, the order of cipher + iv does not matter at all. If it's available to you, you might want to consider a mode like GCM, which takes care of encryption and authentication for you with a single key.


(Uniformly) Random Value when an element is picked with $\frac{1}{p-1}- \frac{1}{(p-1)^2}\ $ probability

$\mathbb{F}_p$ actually has p elements. Hence, an element would be picked uniformly at random if every element was chosen with probability $1/p$. Already if one element is chosen with probability $\frac{1}{p-1}$ this is not a uniform distribution anymore. Depending on the size of $p$ you can argue that the distribution is statistically indistinguishable from a uniformly random one.


As stated in the comments, dev/random already produces cryptographically secure random bytes which are perfectly adequate for use in encryption keys.  Running these bytes through another CSPRNG is completely redundant.

  As far as I've understood, one of the options to create cryptographically secure keys would be to gather entropy from /dev/urandom/ and then feed that data through the Salsa20 cipher.

A symmetric cipher such as Salsa20 by itself is not the correct cryptographic primitive.  You need a CSPRNG (such as /dev/random).

  But I am unsure about the next step, because that’s where search engines stop being useful to me. From what I understand, using the output Salsa20 generates doesn’t seem to be secure enough to be used as key material as-is. Am I correct? If, what would be the cryptographically correct next step after I've retrieved the Salsa20 output?

If you have some reason not to use dev/random (convenience, mistrust, etc), and you have some other strong (and I do mean strong, not just mouse-movements ala mega) source of entropy, then you should refer to one of the CSPRNGs defined in NIST Special Publication 800-90A.  You might be particularly interested in CTR_DRBG, which uses a block cipher internally (running in CTR mode, which is essentially a stream cipher like Salsa20).  You can find implementations of this in many languages.

Pro-tip: avoid Dual_EC_DRBG


What is the difference between a random oracle and a probabilistic algorithm?

Essentially a probabilistic algorithm is simply an algorithm that makes random choices (i.e., takes some random bits). So any algorithm that involves sampling random numbers or the like is a probabilistic algorithm.

A random oracle is a theoretical construct mostly used to analyze cryptographic schemes. It is an oracle that on all inputs gives a uniformly random output, but gives the same output each time its queried on the same input. Often this is used as a model of an idealized hash function. There is a more thorough description of it in the answer here.


Ciphertext notation where the ciphertext consists of two parts

$c = (U,V)$ means that the ciphertext is actually a tuple, made of two parts, $U$ and $V$. It is very common to have ciphertexts that are actually tuples of elements. In this particular case, this scheme is reminiscent to Hashed ElGamal, where ciphertexts are composed of two parts: $U$, which essentially encodes the randomness used, and $V$, which contains the message XORed with a hashed value.

Apart from that, note that, in general, a ciphertext never includes the key...otherwise, they would be trivially decrypted. The key or keys needed for decryption are separate values, and must be kept secret by the intended recipient of the ciphertext.


How can a lattice attack be applied to ECDSA signatures?

Sure you can do. There are many lattice attacks, using your second assumption, to ECDSA (which also applied to DSA). For instance see  Smart and Howgrave-Graham and Shparlinski and Nguyen. All the lattice attacks base on finding small solutions (for the ephemeral key $k$ and the private key $a$) to the signing equation $sk-ra\equiv H(m)\pmod q.$ If you have enough signatures (i.e. enough $k_i$) then you construct a linear system $\bmod q$ and then a suitable lattice and if you have enough bits from every $k_i$ and $a$ and enough messages you can solve the CVP problem. Also you can apply Coppersmith method to the signing equation.


You're wrong. This is a difference between TLS 1.2 and 1.3.
In 1.2 SignatureAndHashAlgorithm identifies only the algorithm (not curve) and hash. In 1.3 SignatureScheme does identify the curve for ECDSA, and the certificate OID for RSA-PSS. See the next to last para on page 44:

[1.3] ECDSA signature schemes align with TLS 1.2's ECDSA hash/signature
pairs.  However, the old semantics did not constrain the signing
curve.  If TLS 1.2 is negotiated, implementations MUST be prepared
to accept a signature that uses any curve that they advertised in
the "supported_groups" extension.

(although in 1.2 and lower before RFC7919, that extension was elliptic_curves not supported_groups!)
Wireshark is showing both decodes: the single, combined SignatureScheme name for 1.3, and the separate hash+signature names for 1.2, and only the latter apply in your case. This is arguably a bug: some other places this field occurs it could be ambiguous whether to use the 1.2 or 1.3 interpretation, but ServerKX can (occur and) contain this field only in 1.2 so it should have the 1.2 interpretation.
And the brainpool curves are designed so that standard (X9.62) ECDSA works with them. Edwards curves as such cannot, but (IINM) they can be converted to Weierstrass curves which can.


Meaning of Signature hash algorithm field in certificate

A typical X.509 certificate is the combination of data (including a public key $Pub_B$), and of a signature $Sig_A$ of that data, to be verified with an unrelated public key $Pub_A$. In order for the verifier to know which hash to use when verifying $Sig_A$, there is use for a field in said data specifying the hash used by $Sig_A$, and that's the purpose of signatureAlgorithm in said data. As RFC 3279 puts it:

  Certificates and CRLs conforming to RFC 3280 may be signed with any public key signature algorithm.  The certificate or CRL indicates the algorithm through an algorithm identifier which appears in the signatureAlgorithm field within the Certificate or CertificateList.

The signatures that will be verified with $Pub_B$ (produced with the corresponding private key by the certificate holder) use a hash (in your case, SHA-256) that may be different from the one used by $Pub_A$.

The signatureAlgorithm field remains useful after the signature $Sig_A$ is verified, since the trust we can have in $Pub_B$, and in anything signed using $Pub_B$, depends on how much we trust that hash.

Note: typical security "proofs" for digital signatures silently assume that a single hash is used in conjunction with a given key, and that the verifier knows which. It would therefore make a lot of sense that a certificate introduces $Pub_B$ only on the condition that it used to verify signatures in conjunction with a specified hash, or/and that by default that hash defaults to what was used in the certificate and is indicated by signatureAlgorithm; and I'm ready to bet that some PKIs using the X.509 certificate format do this.


General idea for storing public/private keys?

The requirements for storing public keys and private keys are quite different. Public keys need to be in a trust store in order to be able to trust them. Care should be taken that an attacker cannot replace them or trick the system into using a different trust store. Public keys - as the name implies - do not have to be confidential.

The requirements for private keys obviously do require confidentiality. Furthermore, the access to use the private keys should be restricted. Note that it is possible to open up access to use the private key while keeping them confidential; an example of this is storage of the private key in a smart card, which then offers a signing / decryption service.

The handling of public keys / certificates and private keys is known as key management. Entire books have been written about that subject so we won't be able to discuss all of them.

For storage in software a common method is to store the private keys in key stores. Examples of key stores are PKCS#12 key stores and PGP key containers. These containers are files for which the contents of the entire store and / or the key entries themselves are in turn protected by a passphrase.

For generic solutions I'd take a good look at PKCS#12 which is for instance used by OpenSSL. Mind that the default password handling may still require work (e.g. increasing the work factor for the decryption key that unlocks the PKCS#12 contents). Just choosing PKCS#12 is not key management on its own.

Symmetric (data or session) keys are often derived - using a Key Derivation Function or Key Agreement protocol - rather than stored.


Its depend on the protocol used. The last and more efficient is Groth16 that use only 3 curve points in its proofs. You can see the size of the keys and the  the proofs in the table 2 of Groth's paper. The computation complexity of the pairing depends of whats curve is used. In general ZoKrates/Ethereum and ZCash use the bn256 curve paramters and the pairing algorithm used in their package (at least in the golang's one) is the algorithm 1 of the miller ate pairings.

You see zk-SNARK is an amalgamation of various works and its complexity depends on the implementation that is evolving day to day.


Is it feasible to execute a range query over tokenized data?

Since I was specifically mentioned in the question, I'll take a stab at answering it.

First, note that the whitepaper was ghostwritten by a couple of marketing people. These (talented and lovely) marketing folks changed and simplified some terminology to match what is used in other marketing materials the company uses. This is pretty standard in industry, but it does sometimes result in things getting confused.

Here, the confusion is that two different kinds of tokenization are both being called "data tokenization". Regular old tokenization can support search because it is deterministic, but to preserve sort order you need to use a different tokenization algorithm. If you're curious you can read the details in this patent. The algorithm is more or less an embellishment on the BCLO order-preserving encryption scheme, but uses some clever tricks (which exploit the fact that you have all plaintext/ciphertext mappings available in the token database) to make token generation very fast. Otherwise, it has all the properties of the BCLO OPE scheme, which means that you actually can perform range queries on tokens.

Note, though, that the BCLO scheme has some very serious security drawbacks. Following a lower bound in a follow-up paper written by some of the same authors, a couple of recent works have found that the attack implied by this lower bound is devastating for security in basically any practical setting people actually care about. Perhaps more worryingly, these papers found that all OPE schemes (not just BCLO) that are efficient enough to deploy are vulnerable to serious attacks in practical settings.

If all you want to do is range queries, "more secure" approaches exist. The phrase "more secure" is in quotes because the extent to which they actually resist determined attacks is an open question right now. We know they resist existing attacks on OPE, but we don't know much else.

For example, last year a paper was published which showed that given enough queries, an attacker that only observes the amount of communication between a client and server (and no other leakage whatsoever) can fully recover plaintexts from any system which enables range queries on encrypted data. This attack requires a huge number of queries and is therefore not very practical, but there is some (not yet published) follow-up work which extends the attack to work with a very small number of queries. In systems with high query volume, this improved attack could completely recover the data in a matter of hours.


How does the key schedule of Rijndael looks for keysizes other than 128 bit?

Rijndael (the algorithm behind AES) is specified with block sizes and key sizes of  128, 160, 192, 224 and 256, in any combination of block and key size. (Thus, Wikipedia was wrong with the keysize has no theoretical maximum here, though one could invent extensions of the key schedule algorithm which allow longer keys. See below for details. I now fixed this wrong statement on Wikipedia, too.)

Of these 25 combinations, only the ones with a block size of 128 bit (16 bytes) and key sizes of 128, 192 and 256 bits (16, 24 and 32 bytes) are standardized as Advanced Encryption Standard. If you are using any of the other variants of Rijndael, you are not implementing AES.

For normal file encryption there is no reason to use any of the other variants, 128-bit key and block sizes are enough (when used with a reasonable mode of operation).

So, how does the key schedule look like?

(For the following, a column is a bundle of 32 bits (= 4 bytes).)

First, from the block size $N_B$ and number of rounds $n_r$ we calculate how much keying material we need for the round keys (it is $N_B · (n_r + 1)$.) The block size is then not needed any more for the key schedule. Calculate this in columns.  For example, in the case of 128-bit blocks and 160-bit keys, you are using 11 rounds, and thus need $4 · (11+1) = 48$ columns of round keys.

We write as many columns as there are in the key size - for example, for our 160-bit key, we would write these as

   k_0    k_1    k_2    k_3    k_4

These are the first five columns of the round keys (i.e. the first round key and one column of the second one). As the next step, we apply the non-linear function $f_1$ of the key schedule on $k_4$, and XOR ($\oplus$) the result with $k_0$ to get $k_5$:

                                     ┏━━━┓
   k_0    k_1    k_2    k_3    k_4 ─→┃f_1┃─╮
    │                                ┗━━━┛ │
 ╭──│──────────────────────────────────────╯
 │  ↓
 ╰─→⊕
    │
    ↓
   k_5

I described $f_i$ in an answer to another of your questions.

To generate the following round key columns, we simply calculate $k_n = k_{n-1} \oplus k_{n-5}$ (as the key size is five columns here), until we come to $k_{10}$, where we have to use $k_{10} = f_2(k_9) \oplus k_5$. We repeat this until we get to $k_{47}$ (as we need only 48 columns of round key material), then we can stop.

                                     ┏━━━┓
   k_0    k_1    k_2    k_3    k_4 ─→┃f_1┃─╮
    │      │      │      │      |    ┗━━━┛ │
 ╭──│──────│──────│──────│──────│──────────╯
 │  ↓      ↓      ↓      ↓      ↓
 ╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
    │   │  │   │  │   │  │   │  │
    ↓   │  ↓   │  ↓   │  ↓   │  ↓    ┏━━━┓
   k_5 ─╯ k_6 ─╯ k_7 ─╯ k_8 ─╯ k_9 ─→┃f_2┃─╮
    │      │      │      │      |    ┗━━━┛ │
 ╭──│──────│──────│──────│──────│──────────╯
 │  ↓      ↓      ↓      ↓      ↓
 ╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
    │   │  │   │  │   │  │   │  │
    ↓   │  ↓   │  ↓   │  ↓   │  ↓     ┏━━━┓
   k_10 ╯ k_11 ╯ k_12 ╯ k_13 ╯ k_14 ─→┃f_3┃─╮
    │      │      │      │      |     ┗━━━┛ │
 ╭──│──────│──────│──────│──────│───────────╯
 │  ↓      ↓      ↓      ↓      ↓
 ...........................................
 │  ↓      ↓      ↓
 ╰─→⊕   ╭─→⊕   ╭─→⊕
    │   │  │   │  │
    ↓   │  ↓   │  ↓
   k_45 ╯ k_46 ╯ k_47

So, it is just like the key schedule for an 128-bit key, but with one column more.

When we actually have to use the round keys for the encryption (remember, in this example the block size is 128 bits, i.e. 4 columns), we use $k_0 \dots k_3$ as the zeroth round key (i.e. before the first round), $k_4 \dots k_7$ as the first one, … and $k_{44} \dots k_{47}$ as the last one (after the 11th round).

The key schedule works similarly for other key sizes, but for key sizes larger than six columns (i.e. seven or eight - more is not specified), there is a second nonlinear function $g$ (a simplified version of $f_i$) after the first four columns in each row (see my previous answer for an example with 8 columns, i.e. AES-256).

To extend this idea to larger key sizes than 8 columns (256 bits), one would have to define what would happen with more columns - use a third nonlinear function $h$, use $g$ again, do nothing? This definition was not done by the designers, as 265 bits of key size seem to be enough for the rest of human history.

This whole key schedule can be done on the fly (i.e. while encrypting a block), and this is usually done on memory-limited implementations, who don't want to hold the whole 167 bytes (for AES-128) to 240 bytes (for AES-256) in memory. On "normal" implementations, you'll calculate the key schedule once and reuse it for each block (as you normally encrypt multiple blocks with the same key).

One can even calculate the key schedule backwards (starting with the last some columns, i.e. $k_{43}$ to $k_{47}$ in our example), which would be done for decryption on low-memory devices.


Why is a non-existence proof for ECC discrete log extremely unlikely?

Of course, "very unlikely" does not mean here that "the probability to find a proof someday is very small", this would make no sense. This informal statement usually means the following: the considered problem is (or can be reduced to) a long standing open problem, which was studied by many researchers. As a consequence, any problem A which has been studied for a very long time somehow became a "unlikeliness hypothesis": if solving a problem B can be reduced to solving A, then B is "as unlikely to be solved" as A is. In the case you mention, as ECDLP was intensively studied, finding a subexponential algorithm for ECDLP is itself a kind of "unlikeliness hypothesis". I do not know whether a subexponential algorithm for ECDLP would solve other long-standing open problems.

Regarding your question "On the other hand, can something be said about how likely it is to find a proper algorithm? Could such be very simple and it was just not discovered yet?", there is an additional remark that might be worth mentioning. Although we cannot prove formally than solving a problem is unlikely, we CAN prove formally that it is not "simple". Here, "simple" means "using methods that belong to a class of known proof methods".

There has been a large body of work that focused on the following task: take,say, ten important articles that proved interesting result. Extract some common features of the proof technique they relied on. Formalize the concept of proving something using a proof with those features - you get a class of proofs C. Then, prove that it is infeasible to solve the problem using a proof from the class C. In other word: if we want to solve it, we need radically new kinds of proofs. This was used to show, for example, that the question "does $P = NP$" cannot be solved using classes of proofs called "relativization proofs", and even proofs from the larger class of "algebraization proofs". Therefore, we have a quite formal way of saying that "solving the $P = NP$ problem is not simple".

Note that this last remark is quite generic, but I do not know whether it applies to the particular case of ECDLP - I do not know about proofs that a class of known methods cannot be used to have a subexponential algorithm. Yet, it gives an idea on how one would attempt to show that it is hard to come up with a subexponential algorithm for ECDLP:

design a restricted class of algorithms, if possible a useful one that captures interesting existing algorithms
prove that no algorithm of this natural class can solve ECDLP in subexponential time

There are proofs, for example, that algorithms that treat the underlying group as a generic group (with black box access to the group operations) cannot break the problem in subsexponential time. But this is a far too restricted class of adversaries; I do not know whether larger and less restrictive classes of adversaries have been studied, but I would bet that some have been.


Why the output of elliptic curve based cryptosystems is smaller than the ordinary public key cryptosystems?

But my problem is that we usually have long messages, so we have to partition it into several blocks and then encrypt it. Therefore, when we have a 2048 bits long messages we make around 12 blocks and then encrypt them.

No, that's not what we do in practice.  Instead, when we need to public key encrypt a large message, we pick a random symmetric key, encrypt that key with the public key algorithm (RSA or ECC), and encrypt the large message with the symmetric key (e.g. with AES-GCM or ChaCha20-Poly1305).  We then send the two ciphertexts as a joint message.

That has the advantage of being computationally far cheaper (as we need to perform one public key encryption/decryption operation, no matter how long the message is).

In any case:

  Now we consider this example with RSA. in order to use RSA for such a message, since its moduli can accept up to 1024 bits messages, we need only 2 blocks as the input(each one 1024 bits long).

Even if we were to use RSA in such a multi-block mode, we wouldn't want to divide the message into blocks, and use RSA in the straight-forward manner.  If we did, then

If the adversary had a guess to the plaintext, he could encrypt the plaintext with the public key, and see if he gets the ciphertext
If we happened to encrypt related messages (for example, the two 2 block messages $M_0 || M_1$ and $M_0 || M_2$), the fact that there are related would be obvious.

Because of these reasons, we have to add randomness whenever we RSA encrypt a message (or key).


It's rather hard to answer the full question, but I'll try and answer as best as possible.

You try to derive a data encryption key using the IV, because you think the IV may be overused.

NIST SP 800-38D section 8.3 states (for a probability of non-repeation of $2^{-32}$ ):

  The total number of invocations of the authenticated encryption function shall not exceed
  $2^{32}$, including all IV lengths and all instances of the authenticated encryption function with
  the given key.

Great, so unless you invoke GCM more than 4 billion times (short-scale), then you should be OK, and you may not need any special constructs.

Let's assume you don't want to limit the amount of GCM calls. In that case you to derive a key for each encryption. You can use a Key Based Key Derivation Function or KBKDF. Probably the best one you can use is HKDF. HKDF accepts a salt as well, and is able to generate as many bits from the input as needed. So you could use the following construct:

$salt = random()$
$seed = PBKDF2(salt, password, 256000, SHA2-256)$
$key = HKDF(seed, \text{"key"})$
$iv = HKDF(seed, \text{"iv"})$
$(ct, tag) = E_{AES-GCM-256}(key, iv, data)$
$output = encode(salt, (ct, tag))$

now say you don't want to perform those 256000 iterations for each file, and you want to encrypt/decrypt multiple files at a time, then you can do the following:

$salt = random()$
$seed = PBKDF2(salt, password, 256000, SHA2-256)$
$salt_2 = random()$
$key = HKDF(seed, salt_2, \text{"key"})$
$iv = HKDF(seed, salt_2, \text{"iv"})$
$(ct, tag) = E_{AES-GCM-256}(key, iv, data)$
$output = encode(salt, salt_2, (ct, tag))$

as HKDF can also use a salt. For each file, repeat steps 3 to 6.

A trick is to use just HKDF-expand and generate 512 bits for key and IV. Other, more simple KDF's such as KDF1 or KDF2 may also be used if HKDF is not available.

As for your scheme, I see some drawbacks.

the additional call to SHA-3 is spurious;
the IV of GCM is best set to 96 bits (12 bytes), but the XOR and encryption of the IV seems to suggest an IV of 128 bits;
the XOR'ing of key and IV is not a secure key derivation function;
the key length is now limited to the size of the IV or introduce additional complexities;
reusing the derived key for different, related algorithms is not recommended.

Here the combination of 3 and 5 is the biggest issue; you'd have to prove that the insecure key derivation doesn't hamper the security of the GCM algorithm. This is not something you should want to do.

As always, it may be advisable to use an existing protocol and library though; there are plenty secure ones available.


Is 1D Perlin noise cryptographically secure

First of all, the Perlin method requires a random number generator as input. It seems deterministic in nature by itself. So if the random number repeats with a given seed, then I suppose it should always generate the same stream. In that case it is insecure as it is predictable even without any particular attack. Besides that, if the seed is a predetermined value then it could be considered a constant in the derived MT algorithm, and it would therefore go against the Kerckhoff principle.

As the Perlin method is not strictly made to be irreversible, I don't see how it would protect an insecure PRNG. For instance, I would expect that it generates certain maximum and minimum values for which the output of the random number generator can be established. If that happens for enough bits, then in the end enough state of the Mersenne Twister may be known to retrieve the seed, breaking any security present in the combination of the two algorithms.

Let's assume that the Perlin method at least leaks some information about the stream. In that case the question becomes: can you break the Mersenne Twister given enough output, even if that output is further apart? And that question I don't know the answer to; I would however not assume that it is impossible.

However, things will get worse: if the Mersenne Twister only uses a 32 bit seed and the Perlin method is indeed deterministic, then it is completely feasible to try all possible seed values and simply run the algorithms on them, comparing the output against known values. And as the 32 bit strength of the seed is nowhere near enough security, the algorithm would not just be theoretically but also practically broken as it would be easy to brute force the seed.

Practically this would require you to know the parameters of the specific Perlin noise generator as well, of course. Again, considering those secret would go against Kerckhoff's principle, so theoretically it would still not be secure even if those have enough strength to secure the implementation.


Using the same secret key for encryption and authentication in a Encrypt-then-MAC scheme

Brute forcing the key would hardly be an issue: 128-bit keys (assuming they have been properly generated) are in a space which is way too large to be successfully explored by brute force; and 256-bit keys (the kind you put in AES-256) are even more larger. Whether AES is "faster" than HMAC or not does not make such brute force more feasible: even if each key try was as simple as a simple bit flip, 128-bit keys would still be too large for any practical attacker.

Said otherwise, if "massively parallel brute-force attacks" are relevant, then your key is not properly generated (bad PRNG, bad key exchange algorithm, bad password-to-key derivation...), and that is your problem, not the reuse of the same key for both AES and HMAC. If you reach the point where the relative slowness of AES vs HMAC/SHA-1 is how you envision protection, then things have gone sour upstream.

Potential problems with using the same key for encryption and MAC would be structural; @Henrick's example is CBC-MAC, which is indeed identical to CBC encryption, except that you only use the last encrypted block as MAC. CBC-MAC works fine as long as you do not give to the attacker access to pairs (p,c): p is a plaintext block, c is the corresponding ciphertext block, for the key k which you use for CBC-MAC. But if you use the same key k for encrypting the data, then you are giving to the attacker a lot of such blocks.

With HMAC vs AES, no such interference is known. The general feeling of cryptographers is that AES and SHA-1 (or SHA-256) are "sufficiently different" that there should be no practical issue with using the same key for AES and HMAC/SHA-1. However, simply defining that "difference" with any kind of scientific rigor would be hard, and it is not a much explored security feature. So that's one of these constructions which can be qualified as "no urgency to fix it, but don't do it if you can avoid it". A much "safer" way (in the sense of: "we know what characteristics of the involved algorithms we are exercising") is to take your master key K, and derive from it, with a good one-way Key-Derivation Function, a sub-key for encryption and another sub-key for the MAC. This can be as simple as applying SHA-256 on K and splitting the 256-bit result into two 128-bit keys.

There are some MAC and encryption algorithms which intrinsically support sharing the same key. This is exactly what happens in GCM.


Can a Deterministic Signature Algorithm be paired with a Probabilistic Encoding Method?

First, some clarifications.

A randomised signature scheme is a signature scheme that produces randomised signatures, that is, if you sign the same message twice, you are not likely to get the same signature twice.

We can "derandomise" a signature scheme by replacing the randomness with pseudo-randomness generated as a function of the messaget to be signed and a secret key. The result is a deterministic signature scheme, where if you sign the same message twice, you will get the same pseudo-randomness and therefore the same signature. If the randomised scheme was secure and the derandomising was done correctly, the deterministic scheme will also be secure.

A padding scheme is a way to encode messages in one "format" as messages of a different "format", typically arbitrary bit strings as bit strings of length divisible by some number, or short bit strings as long numbers, or ... Usually, these schemes are in some sense injective, in that if you encode two distinct messages, you never get the same padded message.

A randomised padding scheme is a padding scheme that if you encode the same message twice, you are not likely to get the same padded message twice. Such schemes can sometimes be used to turn certain somewhat insecure signature schemes into secure signature schemes, typically by turning the message to be signed into a random-looking message that can be safely signed by the insecure scheme.

Now, the answer: Given the way we define "secure signature scheme", composing a secure signature scheme with any padding scheme cannot result in an insecure scheme (just a pointless scheme). So:

Derandomising DSA results in a deterministic signature scheme.
Since we believe DSA is secure, derandomised DSA should also be secure.
Since we believe derandomised DSA is secure, derandomised DSA composed with a padding scheme like PSS should also be secure (but pointless).

So the answer to your question appears to be yes.

However, one caveat. DSA involves a hash function: you hash the message and then the hash is included in some number-theoretic computations that results in a signature. The hash is an integral part of DSA. If you replace the hash with (say) PSS, you have not composed a secure signature scheme with a padding scheme, but modified a secure scheme. And when you modify schemes, the composition result I mentioned does not apply, and you may end up with something insecure.


inverse problem about scalar multiplication on elliptic curve

As Samuel Neves described in the comments it is trivially possible to obtain $P$ from $Q=[n]P$, given $Q$ and the integer $n$.

Simply compute $k=n^{-1} \bmod \ell$, with $\ell=|E(\mathbb F_p)|$ being the order (= the number of points) of the curve. $\ell$ is usually known.

Then, to obtain the desired point $P$, calculate $P=[k]Q=[kn]P$ and you're done.


Under the assumption that $m$ is unknown to the adversary, and random in $[0,N-1]$, then to the best of our knowledge, $m^e\bmod N$ does not reveal anything about any bit of $m$ to an adversary unable to factor $N$.

Update: in the above, "bit of $m$" is in the sense of binary digit of $m$ (for some integer $k≥0$, the value of $⌊m/2^k⌋\bmod 2$), not tiny amount of information. Revealing $m^e\bmod N$ does reveal information abut $m$; most notably the adversary knows the Jacobi symbol $\left(\frac m N\right)$ since that's also $\left(\frac{m^e\bmod N}N\right)$; and can test if an $x$ with $0≤x<N$ is $m$, by checking if $x^e\bmod N$ is $m^e\bmod N$.


How to find a collision with a given prefix and a known key in an AES ECB symmetric block cipher?

but my case is slightly different (and even easier) because what I search are two words $w_1$ and $w_2$ that, given a known prefix $p$, $\operatorname{hash}(p \| m_1) = \operatorname{hash}(p \| m_2)$ with $w_1 = p \| m_1$ and $w_2 = p \| m_2$ and $w_1 \neq w_2.$

Actually, if two messages differ only in the last 128 bit block, they will always hash to different values (and hence they will be no such collision).

That is because, when processing the common prefix, the two messages will have identical $S_{i-1}$ values; the resulting hashes will be:

$$AES_{S_{i-1} || S_{i-1}}( M_i ) \oplus S_{i-1}$$

$$AES_{S_{i-1} || S_{i-1}}( M'_i ) \oplus S_{i-1}$$

These will be the same only if $AES_{S_{i-1} || S_{i-1}}( M_i ) = AES_{S_{i-1} || S_{i-1}}( M'_i )$, and because $AES_{S_{i-1} || S_{i-1}}$ is a permutation, that'd happen only if $M_i = M'_i$ (and hence we're hashing the same message, hence not a collision).

Now, if we are allowed to modify the problem (for example, if the two messages have different prefixes, if the 'word' inserted at the end is longer than 128 bits, or alternatively if the resulting hash is truncated to smaller than 128 bits), then it becomes easy.  However, as stated, it is impossible (not infeasible, but logically impossible).


Protocol that generates keys every 2 minutes using KDC

Look into the Signal protocol and its associated Double Ratchet algorithm. This changes DH keys after every message without much overhead. As no prime generation is involved in generating new DH keys, there is no expensive processing that would make this impractical. If you don't want to change as often as once per message, you can perform the ratchet once every n messages, or once every two minutes.

The Double Ratchet algorithm is designed to be what the designers describe as "self-healing". That is, if an attacker manages to transiently compromise the system at any point in time, they will be unable to retrieve any previous messages. Likewise they will not be able to decrypt any future messages. The protocol is fairly complex and must be in order to provide all the necessary security properties and recover from compromise. Simply regenerating your public keys every so often isn't always sufficient.

To improve security even further, you can also generate a new DH modulus from time to time, e.g. once a month. This does require generating new primes and can take a long time, but doing this makes precomputation attacks like logjam less feasible, even if attacking a non-export key becomes possible.


Complexity leveraging in case of exponentially many hybrids

You would have to be very careful with this. First, complexity leveraging is not an ideal proof technique and requires non standard assumption. But let's put that aside and assume that you are happy with assuming exponentially hard one-way functions. You still have to make sure that you get a meaningful result. The way to do this is to be extremely explicit about the running time of the adversary in Hybrid i as a function of the adversary's running time in Hybrid i-1. Then, you would be able to say at the end what the running time of the final adversary is. You may get: if the original A in Expt0 runs in time $n^c$ then the final adversary runs in time $n^c + n^{\log n}$ (which would be reasonable), but you may get that the final adversary runs in time $2^{n^c}$ (which would be meaningless). So, it depends on the exact reduction and running times.

In addition to the above, you would need to do the same with the distinguishing probability. Here also, you have to be really careful. However, I can't say how much this makes a difference, since it would depend on the proof. One immediate thing is that you would need to assume that the distinguishing probability is not just non-negligible but way below $2^{-\lambda}$ and you have to think about how reasonable this is.


How exactly was the finalist chosen in the NIST AES competition?

At the time of the competition (I can talk about it, I was there), there was a lot of discussion and various people showed arguments. However, there was never an official, publicly known "board of scores" with totals and definite rules, as the pictures you show seem to purport. It is possible that the NIST people did make something similar internally, but they certainly did not publish it. From the outside, the choice has been made by NIST in "some way" and they then provided qualitative reasons, not really quantitative. NIST never bound itself into following strict rules; they wanted to remain in control of the whole proceedings.

The picture still conveys the main reasons why Rijndael was chosen:

Its performance is nowhere bad. It was not the highest performer on every platform, but there was no platform where it would be abysmally slow, in contrast to almost any other candidate.
The "implementation difficulty" relates to features which, on some platforms, imply quite some work. For instance, RC6 requires a multiplier, which is hard on ASIC / FPGA (which translates to: it uses a lot of silicon space). MARS is very complex (many kinds of transforms piled up together) and implementers have reported that it took them quite some time to come up with working implementations, let alone optimized implementations. Twofish uses key-dependent S-boxes, which need RAM (bad for smart cards, bad for ASIC/FPGA). Rijndael was rather simple to implement (in retrospect, Serpent was better for that, especially if you want to implement the algorithm without lookup tables).

During the round conferences, where cryptographers who meet to talk about the AES candidates, some informal surveys were conducted, where people could give "scores" to candidates. While Rijndael did not necessarily elicit the best marks from everybody, nobody really hated it, so it looked fine as a future standard.

All of this, of course, depends on quite arbitrary assumptions on the usage context. NIST wanted an all-purpose block cipher, suitable to a large range of hardware platforms. If you target a specific system (e.g. for disk encryption on your PC), then this may point at another algorithm; for instance, RC6 is faster than Rijndael on a PC (except if the said PC offers the AES-NI instructions, of course).

The really good thing about the AES competition is not that it came up with a good, strong algorithm; what matters is that almost all candidates turned out to be good and strong. Among the 15 candidates, only two were "broken", and then only in an academic way. The trust we can have in AES comes from that: the AES competition proved that we apparently knew how to design algorithms that nobody else knows how to break (that's about as good as you can get with symmetric cryptography).


What is the format of the TLS extension field?

Section 7.4.1.2 of RFC 5246 defines the following ClientHello:

  struct {
      ProtocolVersion client_version;
      Random random;
      SessionID session_id;
      CipherSuite cipher_suites<2..2^16-2>;
      CompressionMethod compression_methods<1..2^8-1>;
      select (extensions_present) {
          case false:
              struct {};
          case true:
              Extension extensions<0..2^16-1>;
      };
  } ClientHello;

As you can see, you can add up to $2^{16}=65536$ bytes of extensions to your client hello in a list format as per section 4.3.


I think what you might be getting at is providing a signature that can only be verified by a particular party (i.e. who has access to the key).  Encrypting any normal hash value with the public key of the intended recipient would effectively do that.  The recipient could decrypt the hash with their private key and then re-hash the message to verify it.  Others would be left unsure of what the additional data represented.

However, if you're thinking of "hashing" the full message in a way that only the intended recipient reverse it, that is pretty much what defines encryption. And, as mentioned in the comments, public key cryptography handles exactly this use-case.

Either way, public-key cryptography seems to be what you're looking for, it's just a matter of how you want to deploy it.


Can hash functions improve a lousy PRNG?

Yes, you can certainly do this, and there has been a lot of theoretical work in the area. At a high level, what this is called is a randomness extractor (Wikipedia):

  A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed.

Dodis, et. al. study different practical constructions of randomness extraction, including using CBC-MAC, Cascade, and HMAC. Your proposal is most similar to the Cascade method they talk about. For which they say:

  In Section 4 we study the cascade
  (or Merkle-Damgard) chaining used in common hash functions such as
  MD5 and SHA-1. We show these families to be good extractors when modeling
  the underlying compression function as a family of random functions. However,
  in this case we need a stronger assumption on the entropy of the input distribution.

See the paper for the exact requirements. It has been a little while since I have thoroughly parsed that paper, but I believe that CBC-MAC and HMAC have better security guarantees (fewer assumptions).

Another paper you may be interested in is A model and architecture for pseudo-random generation with applications to /dev/random by Barak and Halevi. They present a construction which uses an extractor to build a PRNG. They note that their construction is similar to Fortuna. They do list some potential issues they see with the Fortuna construction that you may find interesting (depending on what you are really trying to accomplish). For their extractor in $\S$4.1, they describe some of the tradeoffs between using AES-CBC and HMAC-SHA1 and in the end state that:

  A candidate cipher for this implementation is Rijndael,
  which has a variant with 256-bit blocks. (This last alternative would probably be our choice if we
  had to actually implement a robust generator.)


Actually, there are Carter-Wegman MACs that work like this; of course, there the "hash" function is not a cryptographical hash function, but instead it is an almost-universal hash (with a key).

If we replace this almost-universal hash, well, we run into some potential problems.

The first one is the malleability of some encryption methods.  If we were to use, say, counter mode, then it would be easy to modify the message arbitrarily.  All one would need to do is compute the hashes of both the original message, and the modified one, and xor in both to the encrypted MAC; this modified MAC would decrypt to the hash of the modified message.  Carter-Wegman MACs don't run into this problem, because we assume that an attacker cannot compute the almost-universal hash function (because they don't have the key).

One way to attempt to get around this problem is simply use ECB mode, and encrypt only one block -- that is certainly not malleable.  This runs into the second potential problem -- hash collisions.  If we use only 128 bits of the hash, someone can find two plaintexts that share those 128 bits, obtain the MAC for one, and then he has found a valid MAC for the other message.  While clearly this isn't as severe as the first problem (where the attacker can generate a valid MAC for any message), it's still enough for us to be wary of this.  Again, Carter-Wegman MACs don't run into this problem.

So, it can potentially work; however we need to choose our encryption method carefully.


TOTP intermittently does not return the same code when generated within the same time step

If the time step is 30 seconds, there is a 2/30 = 1/15 probability that your starting time will be a different time step from the ending time two seconds later.


How does the certificate trust model work in detail?

A X.509 certificate contains the following information:

The name of the subject the certificate belongs to.
The public key of the subject. This public key corresponds to a private key. The subject is assumed to have exclusive access to this private key.
A reference to the issuer of the certificate (e.g. VeriSign or some other certificate authority). For a self-signed certificate, the issuer will be identical to the subject.
Some more fields, such as the validity period of the certificate, extensions that specify how the subject public key is supposed to be used, and various information the issuer decided to associate with the certificate.
A digital signature of the DER encoding of all of the above information.

If the RSA PKCS#1-v1.5 signature algorithm is used, the DER encoding is hashed using a specified digest algorithm, that digest is PKCS#1-v1.5 signature encoded, and a RSA private key operations is performed on that encoding using the issuer private key.

Server side, the server will obtain a server certificate by generating a key pair, keeping the private key strictly private, and sending its subject name together with the public key to a certificate authority. The certificate authority verifies that the entity that sent the public key also is properly identified by the subject name that was provided. If verified OK, the issuer issues a server certificate.

When a client connects using TLS (e.g. HTTPS), the server will send the server certificate as part of the initial handshake messages, and use the corresponding private key to generate or decode some part of the handshake (e.g. sign an ephemeral public key, or decrypt a key transport message), in such way that only an entity in possession of the private key, would be able to complete the handshake and end up with the same shared key as the client.

Client side, the browser will have a list of self signed root CA certificates corresponding to the certificate authorities the browser manufacturer has decided the client user should trust for server authentication.

When the client gets the server certificate handshake message, it typically verifies the digital signature (using the public key from the issuer certificate), and that the subject name of the certificate matches the domain part of the URI it is attempting to connect to. Additional verification, such as offline verification of the certificate validity period, and online or offline verification of the revocation status of the certificate, is also recommended.

If the server certificate checks out, the client extracts the public key from the certificate and uses it for completing the handshake. If the handshake completes OK and a shared secret integrity key gets generated, the information sent by the server from thereon will be authenticated to the client.


RSA: Is there a way to digitally sign a message without knowing the private key?


Should data encrypted in a database have a MAC?

Ideally yes, encrypted data in a database should be authenticated as well, along with the context in which the encrypted data appears as associated data—some subset of plaintext values like (not exhaustive):

A database instance identifier;
The database, schema, table and column names in which the encrypted data is stored;
The column names and values of unencrypted columns in the same row as the encrypted value.

The reason is that this protects against a privileged user—say, a malicious DBA—from cutting and pasting values around to change the interpretation that a client application will give to the data.  E.g., Eve the malicious DBA could take encrypted credit card numbers in the database and swap them in order to cause the system to charge the wrong person for things.

If you don't authenticate the values, or even if you just authenticate them minimally, with no associated data, you expose yourself to such attacks.  This is also true if you use too little associated data—for example, if you just use the row primary key as associated data, a malicious DBA might still be able to carry out the same attack by swapping everything else other than the ciphertext and primary key.

There are big downsides here, however, which is that the more thoroughly you authenticate the ciphertexts and their contexts, the harder you make it for honest users to work with the database unless you hand them the master key as well—which is of course very undesirable.  For example:

Suppose you include all the unencrypted columns in the same row as associated data for the ciphertext's authentication tag.  Well, now any non-identity update to the row's plaintext columns will cause the decryption to fail unless it also decrypts, reencrypts and authenticates the encrypted columns anew.  For insert-only databases this might not be a big deal, but if your application is heavy on updating existing rows then it can easily be a deal-breaker.
A very common operation in relational database management is to create custom views (logical or physical) that present a subset of the data from one or many tables to some user or application.  If some such views present them with encrypted data that they may want to decrypt, using associated data with the authentication can make things harder or impossible:

If table names are used as associated data, the decryptors must keep track of which column in the view came from which base table in order to decrypt it.  This defeats the data abstraction that views are supposed to afford their users.
If the views available to some user or application allow them to see a ciphertext column but not all of the columns that provide its associated data, the user won't be able to reliably decrypt the ciphertext.

So these are very serious obstacles that make extensive use of associated data a tricky proposition for databases.


So let's first recall how blinded RSA works:

Select primes $p=11$ and $q=19$, calculate the modulus $n=pq=209$, choose a public exponent $e=7$. Now calculate the signature exponent $d\equiv e^{-1} \pmod{(p-1)(q-1)}$ ($d=103, (p-1)(q-1)=180$).

Now let's go to the message-dependant processing:
A message $M$ is represented as the integer $m=16$ which is blinded by first choosing a random integer $r=13$ and then calculating $m'=m*r^e \bmod n$ ($m'=46$). Finally the signature operation is carried out using $s'\equiv(m')^d\equiv(m*r^e)^d\equiv m^d*r^{ed}\equiv s*r \pmod n$($s'=8$). Finally calculate $s\equiv s'*r^{-1} \pmod n$. For this you need $r^{-1} \bmod n$($r^{-1}=193$). This yields the signature $s=81$.


Why is using an authenticated AES mode better for in-place data protection?

For CBC mode, the issue boils down to the fact that you cannot detect if a man in the middle modified the message. The data is still confidential, the man in the middle cannot read it without the key, but they can modify it, and it still would be decrypted at the recipient.

Ideally you want to ensure data integrity. For CBC mode in particular, you can perform the CBC byte-flipping attack. Lets assume a message is encrypted, and you know a single block. You can convert that block into any block you desire, because of how CBC chaining works. The plaintext of the next block is xor'd with the ciphertext of the previous block. So by altering the previous blocks ciphertext, you change the block that the plaintext decrypts to. Thus in exchange for getting one block to decrypt to gibberish, an attacker can control what the next block decrypts to. This is undesirable. Hence Authenticated modes such as CCM and GCM are used.

An example use-case of GCM mode when sending data over the internet between a client and a server, such as in TLS. You don't want CBC byte flipping to be a possibility. You want to ensure that the data you decrypt is in fact what the person at the other end sent to you.

Also to your point about encrypted hard-drives, being able to have evidence of any data tampering is a desirable property. CBC byte flipping attacks would only be evidenced by file corruption when looked at through its respective program. Its possible that the tampered file could be rendered as valid.


Can we run a probabilistic function on ciphertext with Functional Encryption (or Attribute Based Encryption)?

There are ways to prevent Bob from having complete control over the randomness pool.  You could use some form of verified randomness, where your function $f$ checks that the random string is signed before executing.  This would work using, for instance, the NIST randomness beacon.  You could also contain within $f$ a PRNG, so Bob does not need to provide all the randomness but only a seed (which could actually be signed and provided by Alice or another trusted party).  But in the end, there is no way to guarantee statefullness between function calls, so nothing stops Bob from providing the same randomness to $f$ every time.  This is a fundamental issue I believe.


Padding None can be used with stream ciphers and AES-CTR in order to keep the ciphertext the same length as the plaintext. Padding zeros cannot always be reliably removed, and so should be avoided. Any of the others can be reliably removed and are fine for use.

Padding None leaks information about the length of the plaintext. Apart from that there is no security implication in the choice of padding. All padding gives the attacker is a partial insight into the contents of the last block. In effect this is a known plaintext attack.  If the cipher can't resist a known plaintext attack then the problem is with the cipher, not the padding.


From a theoretical perspective - speaking of general pseudo-random permutations (PRP, the theoretical model used for block ciphers) - no.
An examples: Let $F(k,m)$ be any secure PRP.
Then $F'(k,m)=\begin{cases}m&\text{if }k=0^n\\F(k,m)&\text{else}\end{cases}$ is a secure PRP as well as the chance of actually randomly picking $0^n$ is negligible. Of course once you use more chosen strings for the key - as you'd when swapping the inputs - this guarantee breaks down and you need further guarantees from your cipher for security to hold.
This is not a property known to hold for AES, but the AES key schedule is known to not be the most robust when not choosing random keys, so caution is strongly advised.
Also on a performance note: AES key generation is slow and would be required for each message block in this scenario, increasing the computational cost by 3-10x depending on the implementation.


What if using a block cipher as compression function in Merkle–Damgård?

One issue is that it would make finding preimages significantly easier; with $O(2^{n/2})$ time rather than $O(2^n)$ time.

Here's how you would do such a search:

Select $2^{n/2}$ distinct initial halves of the message, and determine the intermediate state for the hash after processing each message.
Select $2^{n/2}$ distinct final halves of the message, and starting with the target hash, compute hash state backwards, determining what the state would have to be at the start of the final half of the message to derive the target.
Scan through the two lists to find a common state.

Once you have a collision, the initial half and the final hash concatenated together will hash to the target.

Making the hash compression function noninvertible prevents this, as it blocks the second step.


Is SHA-1 safe for signing ECDHE parameters?

SHA-1 is still thought to be secure whenever collision resistance isn't required.

The hash is both used for signing certificates and ECDHE public keys. There's however a difference with regard to collision attacks. It is possible for an attacker to attack the collision resistance with certificates by getting their own certificate signed by a CA. In ECDHE however the attacker shouldn't be able to control the ECDHE public key parameters that are signed.

So, while I wouldn't recommend using SHA-1 in new applications if you can just as well use another hash, TLS is what it is and this kind of a cipher suite is still thought to be secure.


Public-private algorithm where it is not possible to recover public key from private key?

RSA as initialy described (R.L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in CACM, 1978) has this property that it is impossible to find the public key $(N,e)$ from the private key expressed as $(N,d)$. For modern parameters, pick random primes $p$ and $q$ in range $[2^{2047.5},2^{2048}]$, pick random $4095$-bit $d$ with $\gcd(p-1,d)=1=\gcd(q-1,d)$, compute $N=p\,q$ and $e=d^{-1}\bmod((p-1)(q-1))$, keep the private key $(N,d)$ and separately the public key $(N,e)$, but destroy $p$, $q$, and $(p-1)(q-1)$.

Note: While that original RSA system does not allow "to extract a public key from private key", it is still possible to test if public and private key match; that seems unavoidable for any public-key cryptosystem, be it for encryption or signature.

Modern RSA has $e$ (and often $p$ and $q$) in the private key, because

it is generally a feature that the public key can be extracted from the private key
having $p$ and $q$ allows to speed up private-key operation considerably
having $e$ allows to verify computations made with the private key, which is useful to guard against some attacks.

Also, modern RSA typically uses small $e$ (often $2^{(2^k)}+1$ for $0\le k\le4$) and that makes guessing $e$ and verifying the guess trivial.


Group for which computing inverse is hard

Not to my knowledge. However, there are braid group and other nonabelian group based cryptosystems proposed where the difficult problem is the conjugacy problem in a nonabelian group $G$, i.e., given $g$ and $h$ in $G$, determine whether they are conjugate. This means finding an $x$ in $G$ such that $$g=xhx^{-1}.$$

Clearly inverses play a key part in these systems. You can search eprint.iacr.org for some papers. One notable paper in this field is the one below:

Cheon, J. H., & Jun, B: A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem, CRYPTO 2003.

None of these systems have been widely adopted, however. One of their attraction is resistance to quantum computing based attacks.


Fully homomorphic encryption with polynomials

I missed some pitfalls?

The most obvious one is that the secret key $x_0$ is recoverable with a single known plaintext/ciphertext pair.  That is, if we know both $m$ and $Enc(m) = a_{p-2}x^{p-2} +\  ... \ + a_1 x + a_0$, then we know that $x_0$ is a root of the polynomial $$a_{p-2}x^{p-2} +\  ...\  +\  a_1 x + (a_0 - m)$$
Roots of polynomials modulo $p$ can be efficiently recovered; this will give us the value $x_0$ (and possibly a few other false hits).

The other practical issue is that your ciphertexts consists of $p-1$ values; unless $p$ is tiny (e.g. no more than $2^{40}$), then you have impractically large ciphertexts.


How HMAC is calculated for TLS AES_128_CBC_SHA

Does HMAC cover IV, padding and padding_length fields ?

As stated in 6.2.3.1, for stream and block ciphers,

The MAC is generated as:

  MAC(MAC_write_key, seq_num +
                        TLSCompressed.type +
                        TLSCompressed.version +
                        TLSCompressed.length +
                        TLSCompressed.fragment);

That is, the MAC is done on the plaintext (that's what TLSCompressed.fragment is, if you don't do compression).  The TLS header is prepended, but no other modification is done.  Hence, it does not include the IV, padding or padding_length.


Is $F'_k(x) = F_k(x) \oplus k$ a pseudo random function?

You won't be able to find a reduction since you need somehow to XOR $k$ with the output you would get from oracle queries to the PRF, and you can't do this. In fact, the answer is that this is not necessarily a PRF, meaning that I can build a (convoluted) PRF $F$ such that $F'$ is not a PRF.

Specifically, let $\tilde F$ be any PRF and define $F_k(x) = \tilde F_k(x)$ for every $x\neq \tilde F_k(0)\oplus k$, and define $F_k(x) = 0$ for $x = \tilde F_k(0)\oplus k$. I argue that if $\tilde F$ is a PRF then so is $F$. This is because the probability that the adversary $\cal A$ will be able to query $F$ on $\tilde F_k(0)\oplus k$ is negligible. Formally you can show this by constructing a distinguisher $D$ who has oracle access to either $\tilde F$ or a random $f$ and runs $\cal A$. Then, $D$ queries its oracle on $0$ and gets back a value (if it has $\tilde F$ then it will get back $z=\tilde F_k(0)$). Then, for every query $y$ that is made by $\cal A$, distinguisher $D$ computes $k' = y \oplus z$ and locally checks if this defines the function it has oracle access to. If it has $\tilde F$ and $\cal A$ makes this query, then $D$ will know it has $\tilde F$.

Now, given the above, observe that if we construct $F'$ from this $F$, then we can query $F'$ with $0$ and get back $y=\tilde F_k(0)\oplus k$. We can then query $F'$ again with $y$ and we will get back $F'_k(y) = F_k(\tilde F_k(0)\oplus k)) \oplus k = 0 \oplus k = k$, and so we have the key.


Issues with Elliptic Curve Point Addition

All arithmetic operations in jacobianDouble should be in the finite field $\mathbb{F}_p$, i.e. all results should mod $p$, not plain integer arithmetics. Note division Y/2 is defined as $Y\cdot 2^{-1}$ where $2^{-1}$ is the multiplicative inverse of 2 modulo $p$.


There are two problems here. The first one is, that a PRG with an exponential output length can no longer be an efficient (i.e. polynomial time) algorithm, since it needs exponential time to even write its output.
The second problem is that any such algorithm is insecure. The distinguisher against a PRG receives a string $y\in \{0,1\}^{\ell(n)}$, that is either the output of the PRG, or a uniformly random string. It is required to be efficient, i.e. it must run in time polynomial in its input length. If the input length is exponential, say $\ell(n)=2^n$, then it can run in time polynomial in $2^n$. That is enough time to enumerate all possible seed values $s\in\{0,1\}^n$, compute $y':=G_n(s)$ and check whether $y' = y$. Since for uniformly random $y$, the probability that such a seed exists is (really really) negligible, this leads to a trivial distinguishing attack.


Possibility for same Private Key Generation in identity-based encryption

I assume $s$ and $b$ are the main master secret key components of two IBE servers.

If $s=b$, then $SK_{ID,s}=SK_{ID,b}$ provided that the curve parameters and the hash function $H$ are the same. Now, the question is what's the probability of two IBE servers generating the same master secret key components. This depends on the actual scheme and the field it is defined over.

In IBE, mostly pairing-based groups are used. We usually have $s,b\in \mathbb{Z}_{r}$ where the curve is defined over $\mathbb{F}_q$. For example, $r$ is set to be a solinas prime for Type A pairing in PBC. The default values for Type A pairing are $|q|=512$ and $|r|=160$. So, the probability of at least two of $n$ servers generating the same master secret key is essentially the Birthday Problem and can be computed as such:

$$\begin{eqnarray}
p(n) & = & 1 - \frac{r!}{r^n\left(r-n\right)!}\\
& = & 1 - \frac{\prod^r_{i=r-n+1}i}{r^n}\\
& = & 1 - \prod^r_{i=r-n+1}\frac{i}{r}
\end{eqnarray}$$

The probability is roughly $3\cdot 10^{-39}$ in your case. Here's the groovy script I calculated it with. The result is $3\cdot 10^{-42}$ under the assumption that $|r|=170$.


Proof of correctness of Exponential ElGamal

Yes,you got it wrong on this one. Most importantly, ElGamal is defined on a group in general, but you kind of mixed the additive notation with the multiplicative notation.

First, when writing ElGamal over a multiplicative group $(\mathbb{G},\times)$ as you did, we do not generally assume any additional structure on top of the group structure - hence writing $a^{r_1} + a^{r_2}$ does not make sense in general.

Second, in multiplicative notations, a ciphertext looks as follow: $c_1 = (a^{r_1},b^{r_1}\cdot a^m)$. You can write it $(r_1\cdot a, (r_1\cdot b)+(m \cdot a))$ if you want to use additive notations instead, but none of these notations will lead to the $c_3$ you obtained.

Hint for the solution: use the group operation to "merge" group elements, do not try to add up objects of the form $a^{r_1}$ and $a^{r_2}$, this will not lead you anywhere. Using multiplicative notation, you should make use of the following observation: $a^{m}\cdot a^{m'} = a^{m+m'}$.


AES in CTR mode, with a single key, and an IV derived from the plaintext

In the context, the IV is part of the ciphertext (as usual with AES in CTR mode). That part of the ciphertext leaks information about the plaintext including for one who does not know the AES key, which is bad in theory at least. This is because the (SHA-1) hash of the plaintext (or part of it) is the IV. In particular, an adversary can use a ciphertext to comfort a guess of the plaintext, by hashing the guess and checking if (the appropriate part of) that matches the IV.

One academic solution to the problem is a MAC of the plaintext, such as HMAC-SHA-256, with a secret key. This gives a short deterministic digest of the plaintext that does not leak any information about plaintext to adversaries not holding the key (beyond equality of two plaintexts, of course). That digest could be added as a prefix or suffix of the ciphertext obtained by AES-CTR or some other mode (authenticated encryption is a nice-to-have).

Using the same key for the encryption (authenticated or not) and the MAC is poor in theory, and could be disastrous with an AES-based MAC. However, with HMAC-SHA-256, the only foreseeable drawback would be that a key-recovery attack on HMAC (e.g. by some side-channel) would leak the encryption key; or vice versa.


From 2.4 of the paper available at https://www.krackattacks.com (emphasis added):

  The GCMP protocol is based on AES-GCM, meaning it uses
  counter mode for encryption, with the resulting ciphertext being
  authenticated using the GHASH function [28]. Similar to CCMP, it
  is an AEAD cipher, and secure as long as no IV is repeated under a
  particular key. In GCMP, the IV is the concatenation of the sender
  MAC address and a 48-bit nonce. The nonce is also used as a replay
  counter by the receiver, incremented by one before sending each
  frame, and initialized to 0 when installing the TK [1, §12.5.5.4.4].
  This normally assures each IV is only used once. As with CCMP,
  the TK is used directly as the key for both communication directions.
  If a nonce is ever repeated, it is possible to reconstruct the
  authentication key used by the GHASH function [43].

[28] is NIST SP800-37D  (the standard for GCM)
[1] is IEEE 802.11-2016  (the standard for, well, guess)
[43] is 2006 comments by Joux to NIST


What's the difference between trapdoor and encryption?

A trapdoor function doesn't have the security requirements of an encryption function. If you directly use a trapdoor for encryption you open yourself up to related key attacks, known plaintext attacks, malleability  attacks and a whole host of other attacks.

Trapdoor functions are used as a single piece of a larger encryption function that handles all these issues.


What is the difference between Module-LWE and Ring-LWE?

To quote [AD17]: "One way to informally view the MLWE problem is to take the RLWE problem and replace the single ring elements with module elements over the same ring. Using this intuition, RLWE can be seen as MLWE with module rank 1." For more intuition c.f. their introductory section, and for formal definitions c.f. §2.3 in that paper.

[AD17]: Albrecht and Deo, Large Modulus Ring-LWE $\geq$ Module-LWE.


Why would splitting a password output be better than separate HMACs for encryption/authentication key derivation?

Internally scrypt has a huge state space, from which it derives 256-bit output blocks using PBKDF2-HMAC-SHA2, so it's basically already doing what you suggest as 1., just with much larger inputs. Adding another level of HMAC on top will not help.

In general, you need to be careful when chaining hash functions like $H_1(H_2(x))$. Both collisions in $H_1$ and those in $H_2$ lead to collisions in the combined hash. With a 256-bit hash you are still safe, however, since even doubling collisions gives you plenty of security margin.

If both are secure, but just using scrypt is simpler, why not use what's simple? That makes it less likely there's a mistake.


Yes, this is easy enough to exploit.

Start by sending any 15-byte message $m$, and then 256 different 16-byte messages consisting of $m$ followed by each of the 256 possible values of the last byte.

One of the encrypted 16-byte messages will have the same first ciphertext block as the encryption of $m$.  Find out which, and you've found the first byte of the secret!

Now, can you figure out how to repeat this to find the second byte of the secret, and so on?

For the second task, start by figuring out the length of the secret prefix.  How would you do that?  (Hint: Try changing the first byte of your message and seeing which ciphertext block changes.  What does this tell you?  How would you figure out the length of the prefix more precisely?)


Signal Sender Keys: Why it works and which is the common key at the end?

There is no single or final group key. Each group participant has its own Sender key. Whenever a new member joins a group, it generates its own Chain key and Signature key pair. It combines the Chain key and public Signature key into a Sender key and distribute it to all the group participants using the pairwise direct messaging.

All the other group participants already have their own Sender key and they share it with the new participant through pairwise messaging. In this way, everyone keeps the Sender key of each other. Sender key is decomposed to Chain key and public Signature key once it is exchanged.

Now if a sender wants to send a group message:

It derives a Message key from Chain key as:

HMAC-SHA256 = (Chain key, 0x01)

And updates the Chain key as:

HMAC-SHA256 = (Chain key, 0x02)

It encrypts the group message with the Message key using AES256 in CBC mode.

It signs the message with its private Signature key.

Then it sends the message to the server. The server creates copies of the cipher text and sends it to every member. This is called server-side fan-out.

Upon receiving the message, group members use sender's public Signature key to verify the message, derive the Message key, update the Chain key the same way as the sender did, decrypt the message and delete the Message key.

Now if the sender wants to send another message, he will derive a new Message key from the updated Chain key. The earlier Message key is deleted.

The problem with this design is that it doesn't offer perfect future secrecy. If a Chain key of a specific group member is compromised any future message which is sent by that particular member will also get compromised. It is only using symmetric ratchet instead of using double ratchet as in pairwise direct messaging.

Computerphile has also made a good video on this - What's Up With Group Messaging?


But the "PBKDF2 generated key" seems to be 64 byte long

Sounds like the algorithm is actually PBKDF2-SHA512 or some other 512-bit has function, as PBKDF2 does NOT use AES as its PRF. Generally this is truncated down to 256 bits to use with your block cipher. I would check what you are using as the PRF, try replicating the master key by choosing different 512-bit hash functions until you get a match, then work onto decryption after.


Proving correctness of a decryption of a homomorphically summed ciphertext?

For exponential ElGamal this is quite easy if all singe ciphertexts are public (you mentioned they are on a public bulletin board). Lets call $(c_1,c_2)=(g^my^r,g^r)$ the ciphertext corresponding to the sum $m$ of all single encrypted messages after your homomorphic summing (with $y=g^x$ being the public key). The decrypting party simply provides a non-interactive proof of knowledge (signature of knowledge - $SoK$) of the private key $x$ (denoted $\alpha$ below), i.e.,: $$\pi \gets SoK\{(\alpha): c_1=g^mc_2^\alpha ~~\land~~y=c_2^\alpha \}$$
along with $m$ (this $SoK$ can be efficiently realised by converting the respective sigma-protocol to a non-interactive proof using Fiat-Shamir). Everybody can now check if homomorphically adding all ciphertexts yields $(c_1,c_2)$ and taking $(c_1,c_2)$ as well as $m$ and $y$ the proof $\pi$ verifies. If all this works out, then everybody will be convinced that the decrypting party behaves honest.

If you have a few million possibilities you can either use a pre-computed lookup table, brute force or by using some suitable, more sophisticated method to compute discrete logarithms, like Pollards lambda method (since you know where to search). Whats more suitable for you depends on your setting, i.e., how resource constrained are your entities, group setting, etc.

You may use a similar approach for any other additively homomorphic encryption scheme (such as Paillier).


Storing values under different keys (e.g. during key rotation)

ChaCha20 is a stream cipher, therefore, knowledge can be used. Let see what one can do.

  When it comes to key rotation, you'll need to store those encrypted values twice, for a short period of time (under the old and new keys).

This means that the attacker has a chance to see these $C_1 = P\oplus K_1$ and $C_2 = P\oplus K_2$. X-oring these two ciphertexts;

$$P\oplus K_1 \oplus P\oplus K_2 = K_1 \oplus K_2$$ results the x-or of the keys.

In other words, the attacker could get information about the X-or of new and old keys. As longs as the keys are select independently and uniformly from a good entropy source, this will give no information to the attacker.

Note that IV reuse under the same key will reveal information by crib dragging.

$$P_1\oplus K \oplus P_2\oplus K = P_1 \oplus P_2$$ this can ve exploited by crib-dragging.

  Could the encrypted secrets be stored in two files named after the hash of their keys? maybe sha256?

Using hash of the keys give additional information for the attacker. Today, or maybe in a foreseeable this cannot be exploited, however, don't do this. Just use the file name with .old .new extensions during the operation.

  Or could those file names (if known) be used in a malicious way? perhaps making it easier to determine the key values?

Already pointed above that the knowledge of the old and new file doesn't reveal the keys.

  An alternative would be to use the keys to encrypt a known plain-text value, and use that for the file names.

This is fine.


Perfectly secret cipher can leak about the key?

mikeazo's answer clearly covers what the question asks. However, I want to go further and answer this:

How much information does a perfectly secure cipher leak about the key?

Exactly all the excessive information of the key that does not help in finding anything about the message.

In simple words: if the key length is $k$ bits and the message is $m$ bits long then in case of a perfectly secure cipher by knowing the ciphertext you know exactly $(k-m)$ bits of the key.

Formally: By knowing a ciphertext which is ciphered using a perfectly secure cipher the uncertainty about the key is exactly equal to the uncertainty about the message.

Or using entropy function:

$$H(K|C)=H(M)$$

Where $H(K)$ is the entropy of the key, $H(C)$ is the entropy of the ciphertext, and $H(M)$ is the entropy of the message.

The equation above can be deduced from the following equations:

$H(M)=H(M|C)$, $H(M|C,K)=0$


How to calculate secret key size of a CP-ABE scheme

Different researchers use different notations for elliptic curve bilinear pairing groups. For symmetric pairing this can look like:

$e: \; \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$
$e: \; \mathbb{G}_1 \times \mathbb{G}_1 \rightarrow \mathbb{G}_T$
$e: \; \mathbb{G}_1 \times \mathbb{G}_1 \rightarrow \mathbb{G}_2$
$e: \; \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ (with $\mathbb{G}_1 = \mathbb{G}_2$ for symmetric and $\mathbb{G}_1 \neq \mathbb{G}_2$ for asymmetric)

All of the symmetric variants mean the exact same thing and only differ notationally.

Now, if a scheme is constructed from asymmetric pairing, there is nothing holding you back from instantiating the scheme with a symmetric pairing, other than possible security concerns and enabling attacks on it. So, theoretically we can calculate the size of the user secret key as $|SK| = 2|\mathbb{G}| = |\mathbb{G}|+|\mathbb{G}|$ instead of $|SK| = |\mathbb{G}_1|+|\mathbb{G}_2|$. Now you only need to use one group instead of two, which is a more compact notation, but not entirely true.

The authors of both papers that you referenced probably chose this notation in order to include everything in a single table, because the page width is limited and they can't severely change the font size, because they need to follow the template of the conference/journal.

Now, your question is why the authors of the ODG scheme calculated the size of the secret keys of the GSWV scheme differently than the authors of the GSWV scheme themselves.

Let's recap elliptic curve groups. We have an elliptic curve, such as $y^2 = x^3+a\cdot x+b$ where $a$ and $b$ are curve parameters, that is defined in two-dimensional space over some (prime) field. Each point on the curve, where the above equation holds, is represented by two elements, $x$ and $y$, from the underlying field.

If the field is a 160-bit prime-order field, then elements of $\mathbb{G}_1$ can be serialized to 320-bit as a concatenation of $x$ and $y$. But we don't necessarily have to store $y$, because if we know the curve, then we can simply calculate $y$ from $x$:

$$y = \sqrt{(x^2+a)\cdot x + b}$$

Example in code from jPBC:

protected void setPointFromX() {
    infFlag = 0;
    y.set(x.duplicate().square().add(field.a).mul(x).add(field.b).sqrt());
}

So, you can reduce the size of the serialized curve element by half, but then you would need to do additional calculations in order to reconstruct the curve element from $x$ in order to use it. It's a compromise. The authors of GPSW chose to optimize for size and the authors of ODG chose to optimize for speed (or simply to let their scheme look good).


Determining average number of hash calls to get a hash that begins with X

Assuming the output is uniformly random, the probability of any given bit being 0 is $\frac{1}{2}$. So the probability that $b_0,b_1,b_2...b_{14} = 0$ is ${(\frac{1}{2}})^{15}$.

On average, it will require $2^{15}$ calls to find a hash where the first 15 bits are 0.


Transforming Gaussian random $[0,1] $ numbers to uniform $[0,255] $

There is no such thing like a Gaussian distribution over [0,1]; this doesn't make any sense. So it is not clear what you have to begin with.

However, if you have independent random values, you can generate a random bit by taking two values A and B and comparing them. E.g., if $A<B$ you set the bit to 0, otherwise you set the bit to 1. A sequence of 8 such bits is then a (uniformly distributed) random byte.

PS: As correctly mentionned by Ilmari Karonen, if you have a non-negligible probability to have A=B, you have to check for this and if it happens you have to discard A and B.


Why does SHA2-224 use different IV's than SHA2-256?

The $\operatorname{SHA-224}$ is defined in the exact same manner as $\operatorname{SHA-256}$ with different initial values and the digest is obtained truncating the hash value, FIPS PUB 180-4 Page 23.
The different initial value provides domain separation. With domain separation  $$\operatorname{SHA-224}(m) \neq \operatorname{SHA-256}(m)|_{224}$$ where $|_{224}$ is the truncation. If the IV's would be the same then the truncated values would be the same as the initial bits of the full hash, breaking domain separation.
A nice definition of domain separation can be found Hashing to Elliptic Curves, ietf draft

Cryptographic protocols that use random oracles are often analyzed
under the assumption that random oracles answer only queries generated
by that protocol.  In practice, this assumption does not hold if two
protocols query the same random oracle.  Concretely, consider
protocols $P1$ and $P2$ that query random oracle $R$: if $P1$ and $P2$
both query $R$ on the same value $x$, the security analysis of one or
both protocols may be invalidated.
A common approach to addressing this issue is called domain
separation, which allows a single random oracle to simulate multiple,
independent oracles.  This is effected by ensuring that each simulated
oracle sees queries that are distinct from those seen by all other
simulated oracles.  For example, to simulate two oracles $R1$ and $R2$
given a single oracle $R$, one might define
$$R1(x) := R(\text{"R1"} \mathbin\| x)$$    $$R2(x) :=
 R(\text{"R2"} \mathbin\| x)$$
In this example, $\text{"R1"}$ and $\text{"R2"}$ are called domain
separation tags; they ensure that queries to $R1$ and $R2$ cannot
result in identical queries to $R$. Thus, it is safe to treat $R1$ and
$R2$ as independent oracles.

A random oracle is like a kind of hash function and the same concept applies to hash functions.
The initial values required to be a nothing-up-my-sleeve numbers to eliminate the suspicion of hidden properties, though that is psychological.
Similar to $\operatorname{SHA-224}$,

$\operatorname{SHA-384}$ is a truncation of $\operatorname{SHA-512}$ with different initial values.
$\operatorname{SHA-512/256}$ is a truncation of $\operatorname{SHA-512}$ with different initial values.
$\operatorname{SHA-512/224}$ is a truncation of $\operatorname{SHA-512}$ with different initial values.

As a side note; the truncation, naturally, provides resistance to length extension attack.


Do the session keys have the same value on both sides during TLS?

Do the "client write key" and the "server write key" have the same value, even though both keys are generated independently on both sides?

No, see the next answer.
For encryption keys this is less important as the message is MAC'ed anyway. However, within TLS 1.2 and before MAC-then-encrypt is used, which may expose some unwanted vulnerabilities. E.g. if the sender is vulnerable to oracle attacks, then you might use that to decrypt messages when the same key would be used. This shows that key separation is always a good idea, as padding oracle attacks were initially not envisioned.

(Same question) Do the "client write MAC key" and the "server write MAC key" have also the same value?

No, they are deliberately different so that you cannot have the senders have their own message being replayed back to them. Basically a KDF (the PRF in TLS 1.2 parlance) uses a different label for each key, which means that each derived key will only be dependent on the master key (using a one way function).

General question: Do the client and server arrive at the same results while generating the session keys?

Yes, that they do. But they simply end up with the same values for each specific key. The client and server derive identical master secrets, and then proceed to use the same labels for the specific keys. So both sides will have the "client write key", but the server will use it to decrypt the messages.


Can I pre-define the points in Shamir's Secret Sharing algorithm

With Shamir's secret sharing for the case of $k$ out of $n$, you construct a random polynomial of degree $k-1$, because $l$ points uniquely identify a polynomial of degree $k-1$.

The usual way to construct said polynomial is to uniformly choose coefficients $a_1$ through $a_{k-1}$ and setting $a_0=s$.

There is an alternative to that, where you choose $k-1$ points uniformly at random. The $k$th point is then $(0,s)$, you can compute the polynomial defined by those points and then compute the remaining $n-(k-1)$ points.
There is absolutely no difference between the two approaches.

So in summary: No that is not possible. You can freely choose at most $k-1$ shares. And also for the security to hold, those must be chosen uniformly at random.


Can the salting function complexity improve the hash robustness?

First, good password hashing functions like PBKDF2 and scrypt usually take the password and salt as separate parameters, meaning the user does not have to worry about this. However, with some algorithms they do and in any case the theoretical question is important.

Some of those methods you mention are clearly worse than others:

Binary OR would be particularly bad and I hope it is never used. Any position where the salt has a 1 bit would be 1 regardless of the password bit, so about half the entropy in the password would be lost. (AND would be the same, just with bits reversed.)
XOR is not as bad, but two different salt-password pairs can lead to the same password hash. That makes a parallel attack on many users' passwords easier than it has to be.
Some sort of addition (e.g. byte-wise) would have the same problem as XOR.

The normal method is to concatenate. It loses no entropy and produces a unique input into the hash function for every salt and password. There is really no advantage to doing anything more complex as the user, because that would effectively be just another part of the password hash.


Improving efficiency of an "encryption" algorithm based on a chaotic map

If you already use a proper cryptographic primitive such as SHA, why would you use the "almost snake oil" chaotic encryption mechanism?

It is impossible to prove any security properties for such maps beyond "passes randomness tests" since distributional guarantees are impossible to provide, unlike traditional cryptosystems.

Thus they offer no security advantage over traditional cryptosystems.


find the positions where $a$ and $b$'s bits differ: $c_i=a_i\oplus b_i=a_i+b_i-2a_ib_i$

compute partial or-sums: $d_{l-1}=c_{l-1},\quad d_i=d_{i+1}\vee c_i=a_i+b_i-a_i b_i$

isolate the first differing bit: $e_{l-1}=d_{l-1},\quad e_i=d_i-d_{i+1}$

the result is the corresponding bit in $b$: $\sum e_i b_i $


what is the order of the matrix after mixed column step in 192 bit AES?

The only differences between AES-128 and AES-192 are

the key scheduling is different
AES-192 has two more rounds.

There is no difference in any of the steps.

What you might be trying to look at is Rijndael with a 192 bit block size; there are differences in the shift row steps, which might be what you are looking at.  However, that has little to do with AES, which always has a 128 bit block size.


How many parties are needed to compute multiplication with BGW?

The BGW protocol has a semi-honest and a malicious version. For semi-honest, a simple honest majority is enough. In that case, 3 parties can run the protocol, with security against one (semi-honest) corrupted party. For malicious adversaries, BGW requires $t < n/3$ meaning that with one corrupted party, you need at least 4 parties; with up to two corrupted parties, you need at least 7 parties.