Decoding AES with Base64 cyphertext and key

Yes, it is AES. The ciphertext decrypts to

user: part4, password: 97531
{{{

PS: after some experiments I was able to decrypt it using the OpenSSL command line:

openssl enc -d -aes-128-ecb -in cipher.txt -out plain.txt -nopad -nosalt -K 10EABCFF45E05EBB7AF9A228DD31F216 -iv 0 -base64

I converted the key from base64 to hex first.


Collisions in the cyclotomic knapsack function

Thanks for the question!  You are correct that there is a bug here.  Indeed, the sentence "choose $\mathbf{b}_i$ s.t. $\ldots$" makes no sense: the LHS is in $H$, but the RHS may not be.  Fortunately, there is a simple fix which guarantees $\mathbf{y}'_i \in H$. (This must have been what we intended in the first place, based on how the rest of the proof goes; see below.)

The fix: the proof of Theorem 5.1, Item 1, second bullet, should read: Let $\mathbf{y}'_i = \mathbf{y}_i \bmod \mathbf{B}'$ (not $\mathbf{B}$), where $\mathbf{B}'$ denotes an arbitrary basis of $\mathcal{L}(\mathbf{B}) \cap H$.  (Such a basis is easy to compute by linear algebra.)  That is, we sample a Gaussian over $H$, and mod it by a lattice contained in $H$.  So, we clearly have $\mathbf{y}'_i \in H$.

Similarly, in the proof of Claim 5.2 ("Notice that $\mathbf{y}'_i \ldots$") we care about $D_{H,s} \bmod \mathcal{P}(\mathbf{B}')$, not $\mathbf{B}$.  (Indeed, it doesn't make sense as currently written: Lemma 2.7 requires modding by a lattice contained in $H$.)

It looks like the rest of the proof goes through as written.

Let me also mention that subsequent works manage to avoid all this cumbersome "bookkeeping" associated with subspaces etc., by working with rings defined by irreducible polynomials (or more generally, in number rings).  See, e.g., Lyubashevsky-Micciancio ICALP 2006, Peikert-Rosen STOC 2007, and Lyubashevsky-Peikert-Regev EUROCRYPT 2010/JACM 2013.


Hashes or ciphers with all rounds executed in parallel?

Rounds in block ciphers, and in the inner compression or sponge function of a hash, are run sequentially for a security reason: it increases diffusion, which is necessary for security. Examples include the 10, 12 or 14 rounds of AES-128, -192 or -256; and the 64 or 80 rounds of SHA-2. We just do not know how to make a secure cryptographic primitive operating on a moderate-sized block that's secure, deeply parallel, and not very much more costly than what we use today.
Parallelism can and is used at a higher level. One of the virtues of CTR is that parallel implementations compatible with sequential implementations is easy. That applies to AES (in multi threaded implementations or parallel hardware), ChaCha, Gimli (which are amenable to SIMD implementation). Modern hashes often have a provision for parallel implementation using Merkle hash trees (often, just two-levels; e.g. ParallelHash of NIST SP 800-185), but that's at the cost of increasing complexity of non-parallel implementations, which I think is part of why it so far did not catch up in daily practice.


To answer your question: yes, GMAC does have niche applications where it performs better than either HMAC or CMAC; however it might not make sense for you.

First of all, you are correct in that GMAC requires an IV, and bad things happen if a particular IV value is reused; this rather rules out GMAC for some applications, and is a cost even for applications that can live with it.

So, is there any application for GMAC where makes it worth paying this cost?  Well, yes, there is; in hardware, you can do GMAC considerably faster than either HMAC or CMAC.

Suppose you have a stream of data running at 40,000,000,000 bits per second (that's 40Gbps) at we need to integrity-check.  Even with aggressive hardware, neither HMAC nor CMAC can deal with data at that rate; GMAC can.

Now, that's very much a niche application; I rather suspect you'll never run into that yourself.  I believe you're really asking "does GMAC make sense for what I'm doing"

Well, I can't give you a direct answer to that (partially because I'm not exactly certain what it is you're doing).  However, it would appear to me that the only thing that GMAC buys you in your scenario is simplicity (you have a GCM implementation; GMAC is GCM with everything going into the AAD) and consistency (that way, the encryption and authentication-only cases are handled similarly). I cannot tell whether these advantages are worth the costs of GMAC, or whether you're better off tossing in (for example) an HMAC implementation to handle the authentication-only case.


Is it safe to split the output of PBKDF2?

It's secure as the bits are unrelated. It is not secure because it removes a bit of security by giving advantage to an attacker.

PBKDF2 has indeed been defined to generate a dynamic amount of key material. The bits of the output are independent of each other, and having any part of the output doesn't give you any information about the rest of the output values. So $k_0$ and $k_1$ are unrelated because PBKDF2 is indeed a pseudo random generator. Great.

However, PBKDF2 has also a design problem: if you require more than the output of the hash function (in this case SHA-256) then it requires you to perform all the iterations again to calculate the next block of output. This is problematic as an adversary may not need to perform those calculations themselves.

For instance, if the attacker just needs to compare against a value encrypted with $k_0$ then the adversary doesn't need to calculate $k_1$: just calculating and validating $k_0$ is enough to guess the password. You, on the other hand, need $k_1$ so you will have to perform all that work without gaining any advantage from it. As the adversary only needs half the work, obviously you lose one bit of secure. And, as your keys are both the exact output size of the hash function, you've inadvertently made it easy for the adversary.

There are a few ways around this. First of all, you can use a more modern function such as Argon2 (check for secure Argon2 configurations first). Secondly, it is possible to use the output of PBKDF2 and derive two keys from it using a key based key derivation function or KBKDF such as HKDF, e.g. k0 = HKDF(k, "Enc") and k1 = HKDF(k, "Auth").

Finally, you can "hack" PBKDF2 by using SHA-512 and have it deliver 512 bits, which you can split. That's solution obviously doesn't scale well, but it is useful if the other options are not available to you, and it is very simple to achieve; you just have to change the hash function after all.


Let $q$ be given by $\:$ for all $n$, $\: q(n) = 1 \;\;$. $\;\;\;\;\;$ For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$,

$\frac{p-\kappa(|x|)}{q(|x|)} = \frac{p-\kappa(|x|)}1 = \:p\hspace{-0.04 in}-\hspace{-0.04 in}\kappa(|x|) \: \leq \: p\hspace{-0.04 in}-\hspace{-0.04 in}0 \: = \: p \: \leq \: 1 \;\;$.

For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$:

Since $\: x\in L_R \:$, $\:$ there exists $y$ such that $\; (x\hspace{.02 in},\hspace{-0.02 in}y)\in R \:\:$. $\;\;\;\;$ Let $w$ be a minimum-length

example of that, and let $K_w$ be the oracle machine that immediately outputs $w$ and then halts.

Since $K_w$ ignores its input and halts, $K_w$ runs in expected polynomial time.

Since $K_w$ outputs $w$ with certainty and $w$ is a witness, $K_w$ outputs a witness with certainty.

In particular, its probability of outputting a witness is at least $\frac{p-\kappa(|x|)}{q(|x|)}$.

Therefore the given Validity condition holds.

Conclusion: $\:$ That book's Validity condition is trivial.


Is it possible to have multiple RSA private keys?

You are wrong in assuming that any $(\phi * k + 1) / e$ gives modular inverse of $e$ modulo $\phi$; actually if $e$ and $\phi$ are coprime the modular inverse $d \in [0..\phi-1]$ such that $de = 1 (\mod \phi)$ is unique, and only a single $k \in [0..e-1]$ gives the modular inverse.

As an example consider $(p,q) = (5,11)$, $\phi= 4\cdot 10 = 40$. Let us choose $e=3$, coprime with $\phi$: $gcd(3, 40) = 1$; then $d=e^{-1}(\mod 40) = 27$.

Using your expression:

$(k = 0) : 0$ (wrong)
$(k = 1) : (40 + 1) / 3 = 13$ (wrong)
$(k = 2) : (40\cdot 2 + 1) / 3 = 27$ (got it, $27 * 3 \mod 40 = 1$)

But the choice of decrypting exponent is indeed not unique. To obtain the minimal decrypting exponent one should use $d^\prime=e^{-1}(\mod lcm((p-1),(q-1)))$ instead of $d=e^{-1}(\mod (p-1)(q-1))$. For the above example, $lcm(4,10) = 20$ and $d^\prime=7$, which is less than $d=27$ and so a better (faster) decrypting exponent.

As a sanity check, let us encrypt/decrypt number $8$:

encryption:  $8^3 \mod 55 = 17$
decryption using $d=27$:  $17^{27} \mod 55 = 8$
decryption using $d^{\prime}=7$:   $17^{7} \mod 55 = 8$

Any $d=7+k\cdot 20$ where $k = 0, 1, 2, ..$ is a valid decryption exponent for the above example.


Multiple AES/ECB encryptions of different data with same key all end with same pattern

ECB is possibly the wrong choice for your application, you more likely want CBC or some other mode.  See https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_Codebook_.28ECB.29 in particular the picture of the Tux penguin for an example of why ECB does not work with duplicated data.

So now the question is why you would have duplicated data at the end of your output.  This is because of the way the padding is working.  You said you were using PKCS5Padding and it, by design, always adds a full extra AES block at the end of the of input.  (You can see https://en.wikipedia.org/wiki/Padding_%28cryptography%29 but that doesn't appear to cover PKCS #5, but maybe this is useful What is the difference between PKCS#5 padding and PKCS#7 padding )

It appears you are working in Java, and so I coded up a quick little bit of Java test code, to demonstrate what is happening:

encryptData(secret, cipher, "A123456789012345678901234567890", "First Example");
encryptData(secret, cipher, "B123456789012345678901234567890", "Second Example");
encryptData(secret, cipher, "C123456789012345678901234567890", "Third Example");

Which produces this output:

First Example(32 bytes)
0000: CE F9 BF 06 1B 70 5F E5 C2 E7 2D 49 E3 BE A1 EC
0010: D6 E7 45 DE 6B 05 F5 FB 95 87 FC DD EE 57 40 FC
Second Example(32 bytes)
0000: 5F 5F 8E EE D8 FC F9 55 AD EA 5F 76 D8 5D FD C1
0010: D6 E7 45 DE 6B 05 F5 FB 95 87 FC DD EE 57 40 FC
Third Example(32 bytes)
0000: 26 27 23 96 82 39 3D D0 9C DF 51 83 0F A7 20 F6
0010: D6 E7 45 DE 6B 05 F5 FB 95 87 FC DD EE 57 40 FC

As you can see, all three different inputs produce the same output for the last block of:

0010: D6 E7 45 DE 6B 05 F5 FB 95 87 FC DD EE 57 40 FC

When I re-run the code, making the changes necessary for CBC mode (with a preset IV instead of a random one), the output changes to this:

First Example(32 bytes)
0000: 77 F7 51 60 59 F4 54 3C 31 9B F4 C6 72 1C C8 63
0010: C0 D9 32 35 49 93 A7 BA B1 6D 65 EC 66 7D 3C 98
Second Example(32 bytes)
0000: FE B8 B2 1F B9 56 73 AF 61 B3 50 9E DC 69 F3 C6
0010: 1F 5C F0 40 FD 1D 30 D0 CA 5C 0F 06 1B 2E 89 67
Third Example(32 bytes)
0000: 6E 85 6A 02 CA 0B E4 33 E3 29 47 D9 B5 C0 86 01
0010: AE A0 AA 22 1F 12 E5 6A 10 31 9D 0F 99 8F 9A 6E

Here you can plainly see the blocks are all very different.

I have posted the code examples for each case into a pastebin.  They rely on some library code to dump the bytes to hex, but I don't think you need that code for your own work, so I didn't worry about including it, and it would be easy to replace.

 ECB: https://pastebin.com/FSbJ5AfE
 CBC: https://pastebin.com/PP8c44J4


EdDSA (Ed25519) is any random number sufficient for a good private key?

Yes.

In order to understand why, you need to understand how the public key is computed.

The secret key is a scalar. A fixed base point is multiplied by that scalar, and no matter what that scalar value is, you will always end up with a point in the same group as the base point.

You may want to avoid an all-zero secret key but the key space is so large that if the scalar comes from a PRG, this is not something you have to worry about.

The order of the group is 2^252 + 27742317777372353535851937790883648493. The secret should be considered modulo that value. Any secret key between 0 and that value will produce a unique public key.

The secret key can be a uniform value in that range but applications usually just generate a 256 bit key, which doesn't make any practical difference.

Note that most Ed25519 implementations mask the lower 3 bits ("clamping"). So 1 will produce the same public key as 2 or 3. This is a simple way to prevent small-subgroup attacks.
But once again, most applications usually just generate 256 random bits, and don't really have to care about this.


Schnorr groups allowing fast modular reduction, vs GNFS

TL;DR

There are no standards or RFCs that use this idea.
There is a slightly improved number field sieve attack on your example number based on back of the envelope calculations (see below).
Your proposed generator would be fine.
The follow on proposal should not admit special polynomials for $\ell\ge 768$.

The back-of-the-envelope generic attack
To attack a general 3072-bit prime number, one could use the method of Joux and Lercier to construct polynomials $f_\alpha(x)$ and $f_\beta(x)$ with a common root modulo $p$. A good choice seems to be $f_\alpha$ of degree 5 and coefficients 0,+1,-1 and $f_\beta$ of degree 4 and coefficients around 614-bits. One can then test $\mathcal N(a+b\alpha)$ and $\mathcal N(a+b\beta)$ for $0\le |a|,b\le 2^{65.5}$ for both being $2^{65.5}$ smooth (here $\mathcal N$ denotes the norm down to $\mathbb Q$). The largest numbers would be roughly, 327.5-bit and 876-bits and a quick Dickman-$\rho$ calculation in SageMath says that there's a $2^{-65.332}$ chance of them both being smooth and you should be able to get more smooth numbers than primes below the smoothness bound. You then solve a roughly $2\times\pi(2^{65.5})$ variable sparse linear algebra problem (where $\pi(n)$ denotes the number of primes up to $n$) and then and subsequent problem are significantly less work. The work of $2^{131}$ smoothness tests and the large linear algebra problem are not totally out of whack with the usually quoted 128-bits of work.
The back-of-the-envelope for your prime
Your prime admits the polynomial pair
$$f_\alpha(x)=x^9-2^{15}cx^8-64$$
$$f_\beta(x)=x-2^{342}$$
where $c$ is your 230-bit constant. One can then test $\mathcal N(a+b\alpha)$ and $\mathcal N(a+b\beta)$ for $0\le |a|\le 2^{46.5}$ and $0<b\le 2^{76.5}$ for both being $2^{61.5}$ smooth. The largest numbers would be roughly, 693.5-bit and 418.5-bits and SageMath says that there's a $2^{-61.197}$ chance of them both being smooth. Thus again you should be able to get more smooth numbers than primes below the smoothness bound. You then have a roughly $2\times\pi(2^{61.5})$ variable sparse linear algebra problem etc. This is roughly $2^{123}$ smoothness tests and a commensurable linear algebra problem. Your problem is therefore perhaps 8-bits easier than a typical 3072-bit prime. This is much less degradation than other SNFS attacks, and might be tolerable depending on circumstances.
ETA: In re the follow up question. The smallest degree for which special polynomials could beat the J-L pair seems to be 4. A generic blob of 768 or more bits at the head of your 3072-bit number should mean that there is no special polynomial of degree 4 or more. Taking $\ell<768$ might still be secure in some cases, but the analysis starts getting fiddly.


RSA code giving result after more than 10 minutes

What we've got here is a so-called naive implementation, which doesn't consider time complexity of power-then-modulo operations involving large integers. I'd recommend you to read up on square and multiply, exponentiation by squaring, binary exponentiation, for a bit of context. Typical naive implementations have O(2m) complexity, while optimised versions could achieve only O(m).
If you replace the commented-out code with the uncommented, you'll get significant execution speed improvements:
# ctt = pow(no, e)
# ct = ctt % n
ct = pow(no, e, n)
...
# dtt = pow(ct, d)
# dt = dtt % n
dt = pow(ct, d, n)

See Python built-in function docs for more details of what I've done.
Please note I did not verify reminder of your algorithm.


Are there public $p$ and $q$ numbers for use in DSA?


This is, as you guessed, an incorrectly encoded key.  I suspect that OpenSSL ASN.1 decoder is written to assume that the modulus (and other parameters) is always positive, and so interprets them as if they were (that is, interprets them as if the leading 00 byte was there); hence it just happens to work.

Now, what do you do about it?  Well, if it's basically working for you, I suppose there's no urgent need to "fix" it.  On the other hand, what you're using isn't standard ASN.1; if you need to give the private key to someone else (or even update the version of OpenSSL you're using), it might stop working.  I'd personally suggest that you track down who generated the key, and tell them to fix their ASN.1 encoder.


the decryptNode function for leaf nodes in CP-ABE

Since $H$ is a hash that projects into $\mathbb{G}_0$, one must be able to write $H(i)$ as $g^z$ for some unknown $z$, because $g$ is a generator of $\mathbb{G}_0$.

\begin{eqnarray*}
\text{DecryptNode(CT,SK,}x\text{)} & = & \frac{e(D_i, C_x)}{e(D^{'}_i, C^{'}_x)} \\
& = & \frac{e(g^r\cdot H(i)^{r_i}, g^{q_x(0)})}{e(g^{r_i}, H(i)^{q_x(0)})} \\
& = & \frac{e(g^r, g^{q_x(0)})\cdot e(H(i)^{r_i}, g^{q_x(0)})}{e(g^{r_i}, H(i)^{q_x(0)})} \\
& = & \frac{e(g^r, g^{q_x(0)})\cdot e(g^{z r_i}, g^{q_x(0)})}{e(g^{r_i}, g^{z{q_x(0)}})} \\
& = & \frac{e(g, g)^{r{q_x(0)}}\cdot e(g, g)^{z r_i {q_x(0)}}}{e(g, g)^{r_i z{q_x(0)}}} \\
& = & e(g, g)^{r{q_x(0)}}.
\end{eqnarray*}

The last step works because $e(g, g)^a\cdot e(g, g)^{-a} = 1$.


TLS ciphersuite without mode of operation

It is a security issue in the sense that it likely shows that somebody doesn't know what he is doing.

TLS_ECDHE_RSA_WITH_AES_256_SHA is not an officially supported cipher suite name (internet search results too quickly degenerate for that). It probably is present in misconfigured OpenSSL servers. I presume it will default to CBC for the actual security. It is extremely unlikely to use ECB mode as that has never been a supported mode, and it would need to somehow ignore the IV if it was to be used.

Just make it the only possible cipher suite on a test server, then connect to it with a client. You'll probably find out that it is actually the CBC ciphersuite TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA with ID {0xC0, 0x14}. The ID is what is actually communicated during the handshake; the name of the ciphersuite is just what you find in the configuration parameters of the server.

It is not possible to just make up a name for a ciphersuite: it needs to resolve to an ID to be communicated within the handshake. In developers language: the ciphersuite name is an enumeration. Unfortunately OpenSSL has the nasty habit of using their own names and patterns for allowing / disallowing enumeration values.

I'd prefer a TLS 1.2 specific GCM ciphersuite and SHA-256 or SHA-512 over that particular ciphersuite.


What is the direct connection between LWE and GapSVP?

Taking $n$ LWE samples, the associated vector $\mathbf{b} = (b_1, \dots, b_n)$ can be written as $A\mathbf{s}+\mathbf{e}$ with $A^T = (\mathbf{a}_1 | \dots | \mathbf{a}_n)$ and $\mathbf{e} = (e_1, \dots, e_n)$ a small noise vector. The vector $A\mathbf{s}$ could be interpreted as a lattice point in the lattice $\mathcal{L}(\mathbf{a}_1, \dots, \mathbf{a}_n)$, with unknown coefficients defined by the secret vector $\mathbf{s}$, and $\mathbf{e}$ is small so $\mathbf{b}$ is pretty close to this lattice point. This corresponds to a CVP/BDD-style problem, where you want to find the closest lattice vector to $\mathbf{b}$ in this lattice.

Finally, Kannan's embedding technique shows how to translate CVP instances to (Gap-)SVP instances. Quoting Hanrot, Pujol, and Stehle, at the end of Section 4:

I'm not sure if this is also how Regev reduces GapSVP to LWE, but it's probably the most intuitive way to see how CVP-style problems and SVP-style problems are usually related.


This would work, but note that your weakening verification (slightly). Instead of only $(C_1,k_2)$ being a valid signature, now also $(-C_1,k_2)$ is valid. If you want to do signatures by only using $x$-coordinates you can use the qDSA signature scheme, which indeed saves a few bits in the signature size and public key.

There is actually a more serious compression of Schnorr signatures, which I think is quite common. It is already described in Schnorr's original paper. Instead of having a signature $(C_1,k_2)$ we use $(e,k_2)$, where it actually suffices to have relatively small $e$ (say 128 bits for 128-bit security level). Now we can verify by computing $\bar C_1 = [k_2]G - [e]C$ and checking that
$H(\bar C_1\,||\,M) = e$.

This leads to a 48-byte signature as opposed to a 64-byte one, so saves significantly more than a bit. A downside is that you cannot batch-verify signature anymore, though I don't know if that's actually used in practice.


How can we reduce indistinguishability-from-random to other security notions?

Let $E_k$ be a cipher with a uniform random key $k$ unknown to the adversary.  Actually this can be any pseudorandom function family; its invertibility is not relevant in the chosen-plaintext attack model.  It might keep state, or it might be randomized; filling in the details of state and/or randomization is left as an exercise for the reader.  There are a few different ways to quantify attacks against $E_k$, usually phrased in terms of a random decision algorithm $A(\mathcal O)$ defined on an oracle $\mathcal O$ that may involve $E_k$.

Left-or-right indistinguishability.  We define the oracle $\operatorname{LOR}(P_0, P_1) := E_k(P_b)$ where $b$ is a secret fair coin toss unknown to $A$, and the adversary wins if $A(\operatorname{LOR})$ returns $b$.

That is, the adversary will submit a series of message pairs $(P_0, P_1)$, and our oracle always returns the encryption $E_k(P_0)$ of the left message, or the encryption $E_k(P_1)$ of the right message, and the adversary has to figure out which way it is.  The left-or-right advantage is $$\operatorname{Adv}^{\operatorname{LOR}}_E(A) := \bigl\lvert\Pr[A(\operatorname{LOR}) = b] - 1/2\bigr\rvert.$$  We measure the distance from $1/2$ because any answer given by $A$ that is independent of the oracle, and therefore of $b$, will always succeed with probability $1/2$; what's interesting is how much better $A$ can do by taking advantage of the oracle.
Real-or-random indistinguishability.  We define oracles $\operatorname{Real}(P) := E_k(P)$ and $\operatorname{Rand}(P) := E_k(\tilde P)$, where $\tilde P$ is an independent uniform random message of the same length as $P$, and we will quantify how well the adversary can tell them apart.

That is, the adversary will submit a series of messages $P$ to the oracle, and the oracle might return the ciphertext $E_k(P)$ for each message, or might return the ciphertext $E_k(\tilde P)$ of random gibberish $\tilde P$ of the same length as each message instead.  The real-or-random advantage is a measure of how well the adversary can distinguish these two oracles: $$\operatorname{Adv}^{\operatorname{ROR}}_E(A) := \bigl\lvert\Pr[A(\operatorname{Real})] - \Pr[A(\operatorname{Rand})]\bigr\rvert.$$

These two security notions are essentially equivalent, since the best advantage against one is at most double the best advantage against the other, as shown in Bellare–Desai–Jokipii–Rogaway 1997.  There are other slightly weaker notions of security, like find-then-guess, which I usually just call IND-CPA, and semantic security, which is equivalent to find-then-guess but usually more of a pain to prove theorems about.

Note that in the left-or-right and real-or-random settings, the adversary is always given real ciphertexts of partially unknown messages.  LOR/ROR indistinguishability implies nothing about the shape of ciphertexts—ciphertexts could be written in pig-Latin encoded in KOI8-R, or in Navajo binary, as long as the adversary can't tell two ciphertexts apart.

We can instead consider the difficulty of distinguishing ciphertexts from uniform random bit strings as in Rogaway's CRYPTREC evaluation:

Indistinguishable from uniform random.  We define the oracle $F(P) := \tilde C$ where $\tilde C$ is an independent uniform random bit string of the same length as the ciphertext for $P$, and we will quantify how well the adversary can tell $E_k$ apart from $F$.

That is, the adversary will submit a series of messages $P$ and get either the corresponding ciphertext $C = E_k(P)$ each time, or get an independent uniform random bit string each time.  The indistinguishability-from-uniform-random advantage is: $$\operatorname{Adv}^{\operatorname{PRF}}_E(A) := \bigl\lvert\Pr[A(E_k)] - \Pr[A(F)]\bigr\rvert.$$  (Called ‘PRF’ here because this is essentially the same notion as for pseudorandom function families.  In Rogaway's manuscript, it's called ‘ind\$’ because cryptographers apparently like to mark randomness with \$ signs.)

It is very easy to concoct a cipher that has left-or-right/real-or-random indistinguishability but is trivially distinguishable from uniform random: if $E'_k$ has LOR/ROR indistinguishability, define $E_k(x) = E'_k(x) \mathbin\| 0$ and you get a trivial distinguisher of the ciphertexts from uniform random bit strings, even though $E_k$ obviously still has LOR/ROR indistinguishability.  So clearly left-or-right/real-or-random indistinguishability does not imply indistinguishability from uniform random.

How do we show that indistinguishability from uniform random implies left-or-right and real-or-random indistinguishability?  Since left-or-right indistinguishability is equivalent to real-or-random indistinguishability, proving the result for ROR implies the result for LOR.  We will show that the real-or-random advantage of an adversary to distinguish true ciphertexts from ciphertexts of uniform random plaintexts is at most the sum of

the adversary's advantage at distinguishing the true ciphertexts from uniform random bit strings, and
a related adversary's advantage at distinguishing the ciphertexts of uniform random plaintexts from uniform random bit strings.

Let $A$ be a putative real-or-random distinguisher.

Note that the oracle for a real-or-random distinguisher is syntactically like the oracle for a uniform random distinguisher: it takes a plaintext, and it returns a ciphertext-length bit string.  So we can just as meaningfully evaluate $A(\operatorname{Real})$ and $A(\operatorname{Rand})$ as in the real-or-random setting, and $A(E_k)$ and $A(F)$ as in the uniform random setting.
By definition, $\operatorname{Real} = E_k$, so $A(\operatorname{Real}) = A(E_k)$.
Note that if $A(\operatorname{Rand})$ submits the plaintexts $P_1, \dots, P_n$ to its oracle, what it gets back are the ciphertexts $E_k(\tilde P_1), \dots, E_k(\tilde P_n)$ where the $\tilde P_i$ are independent uniform random plaintext bit strings.  So running $A(\operatorname{Rand})$ is equivalent to running $A'(E_k)$ where $A'(\mathcal O)$ works exactly like $A$ but queries $\mathcal O(\tilde P_1), \dots, \mathcal O(\tilde P_n)$ where $A$ would query $\mathcal O(P_1), \dots, \mathcal O(P_n)$.  That is, $A(\operatorname{Rand}) = A'(E_k)$.
Similarly, if $A(F)$ submits the plaintexts $P_1, \dots, P_n$ to its oracle, what it gets back are the ciphertexts $\tilde C_1, \dots, \tilde C_n$ where the $\tilde C_i$ are independent uniform random ciphertext-length bit strings.  It could just as well have submitted $\tilde P_1, \dots, \tilde P_n$ to its oracle, as $A'(F)$ would do, since $F$ ignores the input.  That is, $A(F) = A'(F)$.

We can combine these facts with the triangle inequality to set the desired bound:

\begin{align*}
  \operatorname{Adv}^{\operatorname{ROR}}_E(A)
    &= \bigl\lvert\Pr[A(\operatorname{Real})] -
         \Pr[A(\operatorname{Rand})]\bigr\rvert \\
    &= \bigl\lvert\Pr[A(\operatorname{Real})] - \Pr[A(F)]
       + \Pr[A(F)] - \Pr[A(\operatorname{Rand})]\bigr\rvert \\
    &\leq \bigl\lvert\Pr[A(\operatorname{Real})] - \Pr[A(F)]\bigr\rvert
       + \bigl\lvert\Pr[A(F)] - \Pr[A(\operatorname{Rand})]\bigr\rvert \\
    &= \bigl\lvert\Pr[A(E_k)] - \Pr[A(F)]\bigr\rvert
       + \bigl\lvert\Pr[A'(F)] - \Pr[A'(E_k)]\bigr\rvert \\
    &= \operatorname{Adv}^{\operatorname{PRF}}_E(A)
       + \operatorname{Adv}^{\operatorname{PRF}}_E(A').  \tag*{$\square$}
\end{align*}


Can you give me a summary of cryptographic hardness assumptions?

One of the links in the comments points to this paper, which has a very extensive list of various hardness assumptions used in cryptography. At the end of this post is an addendum that includes problems not found in the mentioned paper. The following is basically the table of contents from the paper:

Discrete logarithm problem

DLP: discrete logarithm problem
CDH: computational Diffie-Hellman problem
SDH: static Diffie-Hellman problem
gap-CDH: Gap Diffie-Hellman problem
DDH: decision Diffie-Hellman problem
Strong-DDH: strong decision Diffie-Hellman problem
sDDH: skewed decision Diffie-Hellman problem
PDDH: parallel decision Diffie-Hellman problem
Square-DH: Square Diffie-Hellman problem
l-DHI: l-Diffie-Hellman inversion problem
l-DDHI: l-Decisional Diffie-Hellman inversion problem
REPRESENTATION: Representation problem
LRSW: LRSW Problem
Linear:  Linear problem
D-Linear1:  Decision Linear problem (version 1)
l-SDH: l-Strong Diffie-Hellman problem
c-DLSE: Discrete Logarithm with Short Exponents
CONF: (conference-key sharing scheme)
3PASS: 3-Pass Message Transmission Scheme
LUCAS: Lucas Problem
XLP: x-Logarithm Problem
MDHP: Matching Diffie-Hellman Problem
DDLP: Double Discrete Logarithm Problem
rootDLP: Root of Discrete Logarithm Problem
n-M-DDH: Multiple Decision Diffie-Hellman Problem
l-HENSEL-DLP: l-Hensel Discrete Logarithm Problem
DLP(Inn(G)):  Discrete  Logarithm  Problem  over  Inner  Automorphism Group
IE: Inverse Exponent
TDH: The Twin Diffie-Hellman Assumption
XTR-DL: XTR discrete logarithm problem
XTR-DH: XTR Diffie-Hellman problem
XTR-DHD: XTR decision Diffie-Hellman problem
CL-DLP: discrete logarithms in class groups of imaginary quadratic orders
TV-DDH: Tzeng Variant Decision Diffie-Hellman problem
n-DHE: n-Diffie-Hellman Exponent problem

Factoring

FACTORING: integer factorisation problem
SQRT: square roots modulo a composite
CHARACTERd: character problem
MOVAd: character problem
CYCLOFACTd: factorisation in Z[θ]
FERMATd:  factorisation in Z[θ]
RSAP: RSA problem
Strong-RSAP: strong RSA problem
Difference-RSAP: Difference RSA problem
Partial-DL-ZN2P: Partial Discrete Logarithm problem in Z∗n
DDH-ZN2P: Decision Diffie-Hellman problem over Z∗n
Lift-DH-ZN2P: Lift Diffie-Hellman problem over Z∗n
EPHP: Election Privacy Homomorphism problem
AERP: Approximate e-th root problem
l-HENSEL-RSAP: l-Hensel RSA
DSeRP: Decisional Small e-Residues in Z∗n2
DS2eRP: Decisional Small 2e-Residues in Z∗n2
DSmallRSAKP: Decisional Reciprocal RSA-Paillier in Z∗n2
HRP: Higher Residuosity Problem
ECSQRT: Square roots in elliptic curve groups over Z/nZ
RFP: Root Finding Problem
phiA: PHI-Assumption
C-DRSA: Computational Dependent-RSA problem
D-DRSA: Decisional Dependent-RSA problem
E-DRSA: Extraction Dependent-RSA problem
DCR: Decisional Composite Residuosity problem
CRC: Composite Residuosity Class problem
DCRC: Decisional Composite Residuosity Class problem
GenBBS: generalised Blum-Blum-Shub assumption

Product groups

co-CDH: co-Computational Diffie-Hellman Problem
PG-CDH: Computational Diffie-Hellman Problem for Product Groups
XDDH: External Decision Diffie-Hellman Problem
D-Linear2:  Decision Linear Problem (version 2)
PG-DLIN: Decision Linear Problem for Product Groups
FSDH: Flexible Square Diffie-Hellman Problem
KSW1:  Assumption 1 of Katz-Sahai-Waters

Pairings

BDHP: Bilinear Diffie-Hellman Problem
DBDH: Decision Bilinear Diffie-Hellman Problem
B-DLIN: Bilinear Decision-Linear Problem
l-BDHI: l-Bilinear Diffie-Hellman Inversion Problem
l-DBDHI: l-Bilinear Decision Diffie-Hellman Inversion Problem
l-wBDHI: l-weak Bilinear Diffie-Hellman Inversion Problem
l-wDBDHI: l-weak Decisional Bilinear Diffie-Hellman Inversion Problem
KSW2:  Assumption 2 of Katz-Sahai-Waters
MSEDH: Multi-sequence of Exponents Diffie-Hellman Assumption

Lattices

Main Lattice Problems

SVPγp:  (Approximate) Shortest vector problem
CVPpγ:  (Approximate) Closest vector problem
GapSVPpγ:  Decisional shortest vector problem
GapCVPpγ:  Decisional closest vector problem

Modular Lattice Problems

SISp(n,m,q,β):  Short integer solution problem
ISISp(n,m,q,β):  Inhomogeneous short integer solution problem
LWE(n,q,φ):  Learning with errors problem

Miscellaneous Lattice Problems

USVPp(n,γ):  Approximate unique shortest vector problem
SBPp(n,γ):  Approximate shortest basis problem
SLPp(n,γ):  Approximate shortest length problem
SIVPp(n,γ):  Approximate shortest independent vector problem
hermiteSVP: Hermite shortest vector problem
CRP: Covering radius problem

Ideal Lattice Problems

Ideal-SVPf,pγ:  (Approximate)  Ideal  shortest  vector  problem  /  Shortest polynomial problem
Ideal-SISf,p q,m,β:  Ideal small integer solution problem

Miscellaneous Problems

KEA1:  Knowledge of Exponent assumption
MQ: Multivariable Quadratic equations
CF: Given-weight codeword finding
ConjSP: Braid group conjugacy search problem
GenConjSP: Generalised braid group conjugacy search problem
ConjDecomP: Braid group conjugacy decomposition problem
ConjDP: Braid group conjugacy decision problem
DHCP: Braid group decisional Diffie-Hellman-type conjugacy problem
ConjSearch:  (multiple simlutaneous) Braid group conjugacy search problem
SubConjSearch:  subgroup restricted Braid group conjugacy search problem
LINPOLY : A linear algebra problem on polynomials
HFE-DP: Hidden Field Equations Decomposition Problem
HFE-SP: Hidden Field Equations Solving Problem
MKS: Multiplicative Knapsack
BP: Balance Problem
AHA: Adaptive Hardness Assumptions
SPI: Sparse Polynomial Interpolation
SPP: Self-Power Problem
VDP: Vector Decomposition Problem
2-DL: 2-generalized Discrete Logarithm Problem

Problem Details

The full paper provides details about each assumption. Here is an example entry:

CDH: computational Diffie-Hellman problem

Definition:  Given $g^a, g^b ∈G$ to compute $g^{ab}$.

Reductions:

CDH $≤_{p}$ DLP
DLP $≤_{subexp}$ CDH in groups of squarefree order.

Algorithms: The best known algorithm for CDH is to actually solve the DLP.

Use in cryptography: Diffie-Hellman key exchange and variants, Elgamal encryption and variants, BLS signatures and variants.

History:
Discovered by W. Diffie and M. Hellman.

Remark:
A variant of CDH is:  Given $g_0,g_0^a,g_0^b ∈G$ to compute $g_0^{ab}$. This is $\equiv_{p}$ CDH.

References:

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on
Information Theory, vol.  IT-22, No.  6, Nov.  1976, p.  644-654.
U.M.  Maurer  and  S.  Wolf,  Diffie-Hellman  Oracles,  Proceedings  of  CRYPTO  ’96,  p.
268-282.
D. Boneh and R.J. Lipton Algorithms for Black-Box Fields and Applications to Cryp-
tography, Proceedings of CRYPTO ’96, p.  283-297.

The complete text is far too long to copy paste here, but this provides a pretty good example of how extensive and thorough it is.

Addendum: Unlisted Problem(s)

The following problem(s) were not listed in the above reference:

MIHNP: Modular Inversion Hidden Number Problem
AGCD: Approximate Greatest Common Divisor
SIP: Small Inverse Problem

Subset Sum/Knapsack problem

Subset Sum problem

$(0, 1)$ knapsack problem (The standard version of the problem)

Bounded knapsack problem
Unbounded knapsack problem
RMSS: Random Modular Subset Sum

Note about parameters

Hardness assumptions only hold when parameterized correctly. Inappropriate parameters can lead to easily solved instances of hard problems.


What are the memory requirements for this type of search if the hash function has an output length n bits?

The naive approach

A naive algorithm for a research of collision is the following:

choose $x_1$
compute $h(x_1)$
Choose $x_2 \gets x_1 + 1$ ($x_2$ takes the value $x_1 + 1$)
compute $h(x_2)$ and verify if it matches $h(x_1)$
if it does not, do $x_2 \gets x_2 + 1$
go back to step 4, repeat and rinse.

How much memory do we need for this algorithm to work?
Well we need to store only $x_1$ and $x_2$. You can also store $h(x_1)$ in order to not compute it each time.

So if $h$ has a $b$ bits inputs, you need... $2 \times b$ memory to find your collision ($b$ for $x_1$ and $b$ for $x_2$).
This is the memory requirement for THIS search algorithm.

However this algorithm is clearly inefficient. Assuming the output of your hash function is $n$ bits. You have $2^n$ hash possibles. This will lead to an average of $\frac{2^n}{2}$ tentative... Clearly not feasible with a complexity of $O(2^{n-1})$.

The multi-target attack

In the previous attack we targeted a specific or fixed value ($x_1$). A more advanced attack consist of storing all the previous attempts and each time you try a new value of $x_2$, thus the multi-target.

The algorithm is the following:

consider an empty list $lst$.
choose $x$
add $x$ to $lst$
Choose $x' \gets x + 1$
Check if there is $x \in lst$ such that $h(x') = h(x)$
Add $x'$ to $lst$
Compute $x' \gets x' + 1$
go back to step 5, repeat and rinse.

I will let you guess the memory requirement for this algorithm.

In term of complexity, if you consider a list of $2^m$ elements, the complexity of this attack is $O(2^{n-m})$.


How to check a file was encrypted (really & correctly)

If you can't get access to the key for at least some sample uses, there's no way to be sure. For example, it's impossible to distinguish AES-128 from AES-256 if you don't have access to the key. That's true of any encryption method: without knowing the key, you can't distinguish the ciphertext from random data of the same length.

A professional auditor would normally get access to some test keys, if they can't normally access those keys through some administration interface.

You can make a statistical test, but all this will tell you is that the encryption is not completely botched or skipped.

If your vendor is not completely dishonest and they claim to have used AES, they probably did use AES. A far more common problem than not using AES is using AES wrong. Here too, you can't be sure that they got it right, but you can at least check for some common problems.

Check how the length of the ciphertext varies depending on the length of the plaintext. The ciphertext should include an initialization vector and an authentication tag, each of which normally adds 16 bytes. If the ciphertext is not 32 bytes larger than the plaintext, something is probably wrong, but there are cases where it can be ok (e.g. for disk encryption where the sector number is used to build unique IVs and no threat requires authentication).

Pass the same inputs in different conditions and make sure that the resulting ciphertexts are completely different. If you can arrange to encrypt multiple messages with the same key, make sure that identical messages result in completely different ciphertexts. This validates that initialization vectors are generated, if not correctly, then at least non-stupidly.

If there's a way for you to submit modified ciphertexts, do that and check that they are rejected with a generic “invalid ciphertext” error, rather than a specific error due to invalid content. This validates that authenticated encryption is used. There are threat models where it's ok not to have authentication, but you need to tread very carefully.

Two things that you definitely cannot know by looking at the output is whether the keys are generated and stored securely. (As opposed to e.g. using a non-cryptographic random generator to generate keys, and writing a copy of the secret keys to an unprotected location.) You can only audit this by looking at the behavior of the system.


iOS Data Protection: What is the Input of the LFSR?

According to this source, which looked at it in detail, and they also implemented tools to do it, it works as follows (roughly):

Every protected file has a metadata entry that contains its encrypted per-file key, and this per-file key is encrypted with its corresponding class key; the metadata also contains information about the protection class of the file. The metadata field itself is also encrypted, with the EMF-key. The file data itself is encrypted only with the per-file key, and the IV is implicit, i.e. not part of that data (quoting from this followup on iOS 5):

  To compute the IV for a block in a file data fork, the input to the IV
  generator is now the block offset in the file fork (instead of the
  block LBA on iOS 4), and the resulting IV is then encrypted (AES128)
  with the "IV-key" to give the actual IV. The "IV-key" is unique
  per-file and computed using the following formula:

  IV-key = SHA1(filekey)[:16]

This is probably to ensure that if different file-system blocks in a file are identical (maybe blocks of 0) the IV's used for those blocks are entirely different (they used to be just the block LBA on iOS 4 fed through an LSFR). The IV generator (from the block offset) is still the same LSFR though (and its source can be found among the mentioned tools).


LUKS: decrypting with master-key rather than with passphrase

Normally, you don't provide the master key directly. The master key is protected by a key encryption key. All storage encryption systems work this way.

There is no way to change the master key without re-encrypting all the data. Using a master key that's stored in a form wrapped by a key encryption key allows changing the key encryption key without re-encrypting the data. It also allows having multiple key encryption keys.

You propose not using a key encryption key and using the master key directly. This is always weaker than using a key encryption key, unless the mechanism for processing the key encryption is flawed. In your proposal, you propose to remember the master key (128 bits or more). If the master key is ever compromised, you've lost. Instead, suppose that you remember a passphrase with as much entropy as the master key (a random passphrase chosen in a space of 128 bits or more). Then you are protected against all the attacks that you would be protected against if you'd remembered the master key, and more.

The attack you're concerned about is someone finding a copy of the master key encrypted with an old, weak passphrase. If you want to protect against this attack, don't use a weak passphrase! If you only use a strong passphrase then there won't be anything lying around that was made by a weak passphrase. Storing the master key encrypted with a passphrase that's as strong as the master key itself is not a risk. The passphrase can even be weaker because it goes through a strengthening function (PBKDF2 or Argon2).


The protocol is formally known as BB84 protocol.

Your "assumption" are conditional probabilities, and they should be calculated, not "assumed". For example, let Alice sends bit $0$; what is the probability that Bob receives bit $0$? Bob has 2 equally likely choices: either his basis coincides with the Alice's basis or not; in the 1st case Bob receives $0$ bit with probability $1$, in the 2nd case Bob receives $0$ bit with probability $1/2$. So the conditional probability that Bob receives $0$ bit given Alice sent $0$ bit is
$$ P_{X,Y}(0,0|X=0) = 1/2\cdot 1 + 1/2\cdot 1/2 = 3/4$$

Since Alice sends $0$ and $1$ bits equally likely,
$$ P_{X,Y}(0,0) = 1/2\cdot 3/4 = 3/8$$
and this I believe is one of the 4 probabilities that should be inserted into the Joint Entropy Formula


What's the difference between it and Enigmail?

They're using different signature / encryption standards.
The Thunderbird built-in uses S/MIME which relies on the CA PKI.
Enigmail implements OpenPGP which relies on the web-of-trust and TOFU.

  Are they both equally secure or is the other more secure and reliable?

It depends.
There's a lot of configuration going on under the hood with OpenPGP and S/MIME and depending on the settings both formats can be (in)secure. The rest of security just depends on personal preference and actual usage. The security part relies on whether you can be bothered to actually get your own key signed and sign other people's keys with OpenPGP and whether you trust the CA model with S/MIME. If you don't mind your encrypted message to be put into an attachment then there's no issue with S/MIME and if you do mind, OpenPGP can put it encoded into the message.

  As I understand it, one do need to have CA or S/MIME from a third
  party to use that secure feature from Thunderbird?

Yes and No.
You don't need to get a certificate from a centrally trusted CA to use S/MIME. You may as well roll your own CA and install it to all recipients or just use a self-signed certificate that needs to be explicitely trusted by other parties.
However, if you are not a company targeting internal emails only with S/MIME, you really should get an S/MIME certificate signed by a trusted CA, because otherwise other people have no guarantee that you're actually the one (or the even the address) who you claim to be.

  Is it advisable to use that than Enigmail or can I combine the two?

In theory, yes, in practice though it depends on the user-interface and the implementation to see whether nested encryption is possible. Nested signatures are no problem at all. Using both in the sense of "I write to Phil using Enigmail and to Bob using S/MIME", this is no problem at all.


What about using AES-ECB with random IV?

No, this is not a secure way of encrypting.  Specifically, it does not meet the requirements for indistinguishability under chosen plaintext attack (IND-CPA), a basic security definition for encryption.

According to IND-CPA, no attacker should be able to win the following game:

The attacker selects two equal-length plaintext messages.
The defender picks one of those plaintexts at random
The defender encrypts that plaintext and provides the ciphertext to the attacker
The attacker wins if it can determine which of the plaintexts was used

Here's a winning strategy for an attacker facing your scheme:

Let plaintext message 1 consist of a single block containing only zero bits.
Let plaintext message 2 be any other single-block message.
If the defender returns a ciphertext where the two ciphertext blocks are equal, then the attacker knows that plaintext message 1 was selected; else, the attacker knows that plaintext message 2 was selected.

Here's why this works:

In plaintext message 1, $P_1 = 0^n$ (i.e. $n$ zero bits), where $n$ is the number of bits in a block.
This means that $M_1 = M_0 \oplus P_1 = M_0 \oplus 0^n = M_0$,
so $M_1 = M_0$.
ECB mode produces ciphertext blocks $C_i = E_k(M_i)$, and $E_k$ is deterministic, so the ciphertext blocks will also match ($C_1 = C_0$).

In plaintext message 2, this equality will not hold: $P_1$ has at least one non-zero bit, so $M_1$ and $M_0$ will differ in at least one bit, resulting in different ciphertext blocks ($C_1 \neq C_0$).


Quadratic residuosity problem reduction to integer factorization

Factoring $\longrightarrow$ square roots.
Computing square roots modulo a prime $p$ is easy: if $p \equiv 3 \pmod 4$ and $a$ is a quadratic residue modulo $p$, then $a^{(p + 1)/4}$ is a square root of $a$ modulo $p$; for $p \equiv 1 \pmod 4$, you can use Cipolla or Tonelli–Shanks.

Computing square roots modulo a composite of known prime factorization is easy: compute square roots modulo each factor separately and combine with the Chinese remainder theorem.
Square roots $\longrightarrow$ factoring.
It is well-known that an oracle $S$ for finding square roots of random elements of $\mathbb Z/n\mathbb Z$ can be used to make an efficient algorithm to factor $n$: pick $x$ at random, and if $y := S(x^2) \not\equiv \pm x \pmod n$, then $\operatorname{gcd}(x \pm y, n)$ is a nontrivial factor of $n$ since $y^2 \equiv x^2 \pmod n$ so $n \mid x^2 - y^2 = (x + y) (x - y)$, and by hypothesis neither $x + y$ nor $x - y$ is congruent to zero modulo $n$.
Factoring $\longrightarrow$ quadratic residuosity.
Deciding quadratic residuosity for a prime modulus $p$ is easy: just compute the Legendre symbol $(a|p) \equiv a^{(p - 1)/2} \pmod p$ and see whether it is 0 or 1.

Deciding quadratic residuosity for a composite modulus of known prime factorization $n = pq$ is easy: $a$ is a quadratic residue modulo $n$ iff it is a quadratic residue modulo $p$ and a quadratic residue modulo $q$, which can be computed by the respective Legendre symbols.
Quadratic residuosity $\stackrel?\longrightarrow$ factoring.
We don't know!

If you could find a way to factor $n$ using a decision oracle $D$ for deciding whether random elements of $\mathbb Z/n\mathbb Z$ are quadratic residues, you could publish it in a top-tier conference, because the state of the art to my knowledge is that such a reduction is known only in the generic ring model.


Why does it matter for a signature scheme to be without random oracles?

A "random oracle" is essentially a perfect hash function. It's a device that takes a message of any length and maps it randomly to a message of a fixed length such that the same input always produces the same output. Random oracles don't exist. For algorithms that require them, cryptographic hash functions are used instead. However, cryptographic hash functions are not really random oracles and any flaws in the hash function could translate into vulnerabilities in the signature scheme.

The simplest way to make a signature scheme is to begin by hashing the thing you need to sign to a fixed length. Since signature schemes generally aren't also trying to design hash functions, they just assume a random oracle to perform this function and then they demonstrate their security properties assuming a random oracle is used.

Signature algorithms that don't require random oracles don't require you to hash the thing you are signing. They operate on a message of arbitrary length, reducing it to a fixed-length signature as part of their own operation. Because you don't have to substitute a hash function for a random oracle, there is no risk that the hashing function will add new vulnerabilities to the signature scheme.

For example, say you have a signature scheme that requires a random oracle, and the signature scheme has been proven to have no vulnerabilities. You use MD5 as the random oracle. Oops, we can now generate MD5 collisions, so someone can now forge two different messages that have the same signature too easily. All the security properties of the signature algorithm aren't going to help you because the hash function isn't a random oracle and introduced vulnerabilities a random oracle (since it's theoretically perfect) doesn't have.


Lemma KL-Divergence (Differential Privacy)

I don't understand why:

$$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=y])$$
Well the domain is partitioned into $T$ and its complement. So the sum over the full domain of the difference of the two probability distributions is zero.
$$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) +\sum _{y \notin T}(\Pr[Z=y]-\Pr[Y=y])=0,$$
but now you can just move the second term to the right hand side and get the claimed equation.


El Gamal Signature: Attack to recover private key if $k$ is generated as $k_{i+1}=k_{i}+a$ where $a$ is a large unknown constant

Actually, you can recover $g^{-a}$.

You know that $r_i = g^{k_i} \mod p$ and $r_{i+1} = g^{k_i + a} \mod p = r_i \cdot g^a \bmod p$, hence $g^a = r_{i+1} \cdot r_i^{-1} \bmod p$; from there, computing $g^{-a}$ and $g^{-2a}$ is easy.

With that, the linear equations become easy to solve...


It will depend on the exact system.

The cryptosystem of Castelluccia is additively homomorphic and is thus a PHE cipher.

The cipher of Domingo-Ferrer was broken by Wagner and others. Thus, I wouldn't classify it as either.

The cipher of Xiao, et al. is fully homomorphic.

To determine if a symmetric scheme is a PHE or FHE, just look at what operations it supports. If it supports a single operation (say addition), then it is PHE. If it supports both operations (addition and multiplication), then it is FHE.

Update
A recent trend in the HE encryption literature has been something called Somewhat Homomorphic Encryption (SHE). These are ciphers which support both addition and multiplication but not unlimited numbers of operations. E.g., BGN is a SHE cipher as it supports unlimited additions and one multiplication. The current FHE ciphers are all built using SHE ciphers plus a bootstrapping operation (or generating the keys such that enough of each operation can be supported to compute the desired function, making bootstrapping unnecessary).


Is the practice of "security through obscurity" violating Kerckhoffs's second principle?

"It should not require secrecy, and it should not be a problem if it  falls into enemy hands"

Where "it" is the algorithm design itself, and not an input to it...

  But isn't the practice of security through obscurity still violating Kerckhoffs's second principle per definition?

Yes. Obscurity is hardly a defense that demands prohibitive computational cost from an attacker to work around. It makes the problem inconvenient, rather than computationally intractable.

However, it should be noted that "Security through obscurity" and "Security plus obscurity" are not the same thing.

Using algorithms that would be secure even if the adversary knew all about them, but additionally declining to let the adversary know about them is not worse than using a secure algorithm by itself. It is debatable if it is any better, as there is no such thing as "more secure" if it is already "secure".

  And why are people even practicing security through obscurity if it, as stated, doesn't provide more security?

Even the naive realize that secrecy is critical for cryptography to function. But:

They almost certainly don't have the knowledge that has been painstakingly gathered by years of failure and research (history of cryptography and modern research).

e.g. that security through obscurity is not sufficient

They may have never heard of Kerckhoff's principle
They probably have not heard of/do not understand linear/differential cryptanalysis/number theory/group theory and other modern analysis techniques.
They clearly don't understand that concentrating secrecy into a key is far more effective than keeping an entire algorithm a secret.

For a meatspace analogy: Your front door is not secure because attackers don't know that it is locked or what it is locked with, but because they don't have the key*.

They probably don't have the kind of confidence in their setup that comes about as a result of thorough research and analysis.

If you examine the work of a successful cryptographer, for example Daniel J Bernstein, then you will find no obscurity anywhere. All of the details of the designs and implementations are publicly available.

*Disregarding real-world details such as lock picks and lock models that are keyed alike.


EC ECKA-ElGamal Key Agereement availability in Bouncy Castle Java library

Yes, ElGamal indeed is DH with the sender using an ephemeral key and using the group operation for encryption.


Uniform distribution/randomness of characters in the SHA-256 hash?

It may be that you did not actually observe an unexpected deviation from the desired mean of 50.5 for a uniform distribution over integers in [1,100].  However, you say that all combinations of two characters are considered, which I assume to mean that first you look at characters 0 and 1, then characters 1 and 2, and so on.  This means that when you look at characters 1 and 2, since you've already rejected characters 0 and 1, the distribution of character 1 is necessarily biased (there are 156 combinations that lead to rejection, and 16 does not divide this evenly).

To obtain an unbiased sample, you should not reuse any characters.  If you used your same scheme but didn't reuse any characters, you would most of the time generate an unbiased sample but with probability $(156/256)^{32}$ (about 1 in 8 million) you would run out of characters before accepting.  To reduce your chance of running out of characters, you can accept numbers 1 to 200 (but then divide by 2, rounding up).  This reduces your chance of running out of characters to $(56/256)^{32}$ (about 7.56e-22).  You can improve on this by considering blocks of 8 characters (32-bits) or 16 characters (64-bits) at a time.

You can also simplify your method by using the usual hexidecimal convention and relying on existing hex string to integer conversion, or better yet, avoid the conversion completely since the SHA256 hash is always computed as a sequence of bytes, and then converted to a hex string.


Size of IV in AES-GCM according to RFC 4106

kelalaka answered your questions, however I do believe there are things that could use some clarification:

  RFC 4106 specifies about nonce. It contains a salt of size 4 octets and an iv of size 8 octets. Further, RFC specifies that salt is assigned at the beginning of the security associations which is established through Internet Key Exchange (IKE) and salt value is constant. But all most all of the implementations and descriptions found about AES-GCM specifies iv as 12 octets and there is no consideration of salt value.

First, a clarification on terminology (at least, the terminology I'll be using in my answer below):

Nonce - this is the (typically 96 bit) value passed to the GCM routine
IV - this is the value within the packet - IPsec with GCM uses 64 bit IVs
Salt - this is the additional value that is included with the recipe to generate the nonce.

RFC 4106 is specifically about how to use GCM within IPsec; as such, it has a recipe for generating the nonce (which you refer to as an 'iv') that GCM requires.  It does it by talking 8 bytes chosen by the encryptor (which he places in the 'iv field' within the packet, and which the decryptor extracts from the packet), and 4 bytes for the key derivation (the 'salt') and concatenating them.

This is specific to IPsec (actually, TLS's use of GCM does the same thing); other protocols which use GCM may generate (and communicate) their nonces in a different way.  Because a cryptographical routine is typically protocol agnostic, they would not have the IPsec-specific recipe built in.  Instead, they would assume that something protocol specific would generate the nonce, and pass the entire nonce in.

As for why IPsec uses this specific recipe to generate GCM nonces, well, it's to frustrate potential multitarget attacks.  Suppose that the attacker has a large number of GCM encrypted sessions, and that he would like to recover the contents of one of them (and doesn't really care which one it is).  Further suppose that the GCM implementations use the same IVs for each session (e.g. the first encrypted packet might always use an IV of 0).  Then, what the attacker might try to do is guess an AES key, and generate the GCM privacy keystream, and see if that the correct keystream for the initial packet for any session (that turns out to be efficient with plausible assumptions).  If he could do that, that would mean that, for a 128 bit key and $N$ sessions, his expected work effort to break one of the sessions is $2^{128}/N$ trial decryptions, which is less than we want.  However, by including the 32 bit salt (which varies between sessions), this expected work effort increases to $2^{160}/N$ (because he has to guess the salt as well as the key); in particular, this means that this multitarget attack is actually less efficient than a simple brute force attack unless $N > 2^{32}$, which is quite a lot.  Note that this salt doesn't actually help against brute force attacks against a single session; it doesn't hurt either.  And, it doesn't really have to be secret (however, there's no particular reason we have to go out of our way to publish it either...)


How is it possible to detect "unknown SHA-1 cryptanalytic collision attacks given just a single file from a colliding file pair"?

The confusion comes from the following sentence:

  I can analyze an arbitrary file on my hard drive and be told whether
  that file has been the target of a collision attack.

The attack does not target "harmless" files, and generate a collision for them: this would be a second-preimage attack, which is a much harder problem to solve. A collision attack simply produces a pair of files with a collision. But using the current known attack, the pairs produced that way have a very specific structure, which can be easily identified. So, if you check one of your files, it tells whether it has been generated during the process of this attack.

Of course, other attacks can exist, that we are not aware of yet, and the current checker would not be able to tell that your file does not come from such an attack. What it tells you is only whether your files were generated in the process of this particular attack. Another way of saying that is: we have no proof that no second preimage attack exists (even though we have no idea how to build such an attack), but if one existed, it would indeed allow to find collisions for arbitrary files, and so any of your files could have been the subject of an attack of this kind, but no software could see that from your file.


Difference between "Signature Algorithm" and "Signature Hash Algorithm" in X.509

This has more to do with how Microsoft decided to implemented their certificate inspection GUI, than about the actual fields of the certificate. Most signature algorithm identifiers present in contemporary certificates specify both the public key algorithm (RSA in this case) and the digest algorithm (SHA-1 in this case). The identifier "sha1RSA" is most likely inaccurate in so far that Microsoft has decided to use it for an identifier that is known as sha1WithRSAEncryption OBJECT IDENTIFIER ::= {  iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) 5 } in the standard.
The only semi-common standard signature algorithm I am aware of that actually separates the public key algorithm identifier from the digest algorithm identifier in the signature algorithm identifier of certificates, is PKCS#1 v2 RSASSA-PSS.
Edit:
Consequently, Microsoft follows conventions and the X.509 specification by letting "signature algorithm" mean a combination of a signature public key algorithm and signature hash algorithm, but, firstly, the identifiers they use for these combinations are non standard, and, secondly, adding a signature hash algorithm field is in most cases superfluous and doesn't usually reflect the actual X.509 format.


"Conditional decryption" title could be confusing.
A ciphertex verification was demonstrated at Bitcoin workshop Financial Crypto 2016, to be a valid solution of a Sudoku instance. No third (another) party required.
Technically, we prove satisfiability of an R1CS system with a SNARK proof, and "computation on an encrypted value" could be expressed as R1CS equations, leading to just one single proof. One could also create "some secret plaintext is less than parameter AND this ciphertext is valid for that plaintex and some secret key" circuit.
Sure one could make a comparator circuit with a parameter (100 in your example), in hope to get a secret in logarithmic number of verification queries, alledgely rendering encryption useless. However, there is no oracle with SNARKs, only one single snark-proof for specific parameter value (for example, =100). If a prover would create too many comparator snark-proofs himself, he will break his encryption.


cryptographic accumulators: accumulator size vs. max. number of set members?

Disclaimer: I am not a hard-core cryptographer, and I am only familiar with a subset of the various accumulator implementations. So this is a layman's answer.

Accumulators are not attempting to set a bit for every member of the set. The reason they can violate the intuition that they must have at least 1 bit for every potential set member is because they are lossy. Unlike a bit set, accumulators do not provide a 2-way lookup. You can put stuff in, but you can't get stuff out. Specifically, you can't start from the accumulator value and enumerate all members of the set; there is an infinite number of values "in" any given accumulator.

You can think of an accumulator like the hands of a clock. Perhaps the hands say 3:15. If I say to you, "3994 seconds have elapsed" as you look at the clock, your natural response would be, "Since when?" Without a reference start time and knowledge about how many times the hands of the clock have "wrapped", there could be an infinite number of valid assertions about elapsed time. (Accumulators depend on arithmetic in a modular field, which has this same wrapping property. 5 * 7 mod 4 = 35 mod 4 = 3. But I can give you lots of other factors that multiply together to yield 3 in a mod 4 field.)

You might be tempted to say, "Well, if a given accumulator value is compatible with an infinite number of set members, how can it "store" anything?"

To understand the answer, let me alter the clock situation a bit. You are standing in front of a clock that says 3:15 when Alice says, "4 billion 200 million 93 thousand 74 seconds have elapsed" Now you say to Alice, "Since when?" and Alice says, "Since the clock said midnight."

Even though there is an infinite number of explanations for the clock saying 3:15, Alice's assertion is testable. You can do the math that divides clock hand revolutions into the given number of seconds, and see if it's really the case that the clock said midnight at the interval that Alice claims.

Now, you can think of an accumulator as being the product of many numbers multiplied together in a wrapping, modular field. When you test set membership with the accumulator, you can't just assert "X is in the accumulator", any more than you can say "how much time has elapsed?" without a frame of reference. Instead, you have to make a claim that X is "in" the accumulator because X times Y produces that accumulator value in its modular field. That is easy to test. The Y in this example is like picking some other arbitrary reference point in a clock discussion to answer the question, "Since when?"

Notice that for X to be useful, Y must also be given. In information theory, the amount of information that must be known grows with each new set member--but the knowing is distributed to all the owners of the set members; it does not need to be held centrally. The value in the accumulator is the reference against which each set member's claims can be tested by them presenting both X and Y.

It turns out that it is computationally "hard" (meaning there is no practical way to brute-force a correct answer) to explain an accumulator as the product of X and Y, in large modular fields, unless you have been given X and Y. This is due to the irreversibility of modular math (you can't divide, any more than you can look at clock hands and know how many times they've gone around when they say 3:15). Thus, if you "own" a value that is a member of a set represented by an accumulator, and you have been told what the product of all the other set members are, you can show that your value is "in" the accumulator with some very simple math. But if you pick an arbitrary number and want to prove it is in the accumulator, you could compute till the end of the universe, and never find a solution.

It might sound like I'm claiming that accumulators can "hold" an infinite number of values. I believe that's not the case; there's a relationship between accumulator bit size and the number of possible factors (set members) and computational hardness. A mathematician could state it precisely, but I believe a simple summary is, "you can put as many set members into an accumulator as you like, but at some point, you begin to degrade computational hardness." And I think that the point where computational hardness degrades, for the 256-bit accumulators I'm used to, is very, very, very large. Certainly more than billions or trillions (which is a tiny fraction of a 256-bit number).

Cryptographers and mathematicians, is this answer accurate to one or two decimal places? :-)


Asymptotic Hash Function and Concrete Hash Function

An asymptotic formalization cares only about what happens when the security parameter becomes "large enough". Since we use (essentially) one fixed security parameter, it is certainly possible to construct cryptosystems that would be insecure for some fixed security parameters, but secure in an asymptotic formalization.

This means that a non-asymptotic formalization is to be preferred over an asymptotic formalization (although the latter may be "cleaner").

A silly example is the following construction of a compression function (which should exist under reasonable number-theoretic assumptions):

For $n \leq 10000$, let $p_n = 10^n$. For $n > 10000$, let $u_n$ be the integer made up of the first $n$ decimal digits of $\pi$, and let $p_n$ be the smallest safe prime larger than $u_n$. Let $g=4$ and $h_n$ be the integer we get from the first $n$ decimal digits of $e$.

Let $f_n:\{0,1,\dots,\lfloor (p_n-1)/2 \rfloor\}^2 \rightarrow \{0,1,\dots,p_n-1\}$ be defined by
$$f_n(x,y) = g^x h_n^{2y} \bmod p_n .$$

Under reasonable number-theoretic assumptions (that it is asymptotically hard to compute the logarithm of $h_n^2$ to the base $g$ modulo $p_n$), this is asymptotically collision resistant. But for any security parameter $n$ that we would like to use, it is easy to find collisions.

(Note that we can flip this construction around to get a compression function family that is (under reasonable assumptions) collision resistant for any security parameter we care to use, but asymptotically insecure.)


Is it possible to manage an encrypted dataset for face recognition?

If I understand correctly, the setting describe by you is that you want to simulate a scenario where an encrypted dataset is hosted on an untrusted server, then a user can send encrypted image to it, the server blindly match the image with every encrypted image in the set, then return the user the best match. This seems not possible (at least without some carefully thought and design) because the server does not have the private key thus would not know which one is the best match. Of course the server can, for each encrypted image, return a result and the user can decrypt, then the user decide which one is the best match.

Whether the matching can be done in the encrypted domain depends much on what matching algorithm you use. Paillier is only additively homomorphic, meaning that you cannot do multiplication in the encrypted domain (except multiply a constant). The computation is restricted to an integer group, not real numbers. All of those constraints would restrict your choices, possibly only to those simple ones.


How Can I Know the Number of Points on an elliptic curve?

As the astute commenters pointed out, small cases can be done by hand, while Schoof's algorithm can be used for large fields.

By the way, there is the well known bound
$$
q+1-2\sqrt{q}  \leq \#E \leq q+1+2\sqrt{q}
$$
on what you call NPE, due to Hasse-Weil, for curves over $\mathbb{F}_q.$ If $q$ is prime, the inequality is strict.


SHA-256 support for SecretKeyFactory in Java 6 and 7?

With the advent of SHAttered, does Oracle have any plan to support
  later SHA versions for SecretKeyFactory?

First, they don't need to. We are talking about PBKDF with HMAC-SHA1 here, which is a password-based key derivation function.You don't need collision resistance (which is the only property SHAttered broke) for password hashing, in fact it is trivial to find two passwords that hash to the same value with PBKDF2. What you really want from a password hash is one-way-ness / pre-image resistance (ie you can't recover the input from the output) other than using generic attacks.

Second, as of JRE8 you can use any pseudo-random function (PRF) the API knows instead of HMAC-SHA1 already and in fact HMAC-SHA256 is given as  an example in the documentation.

  What are the alternatives?

You don't use PBKDF2 from the standard library but rather use a binding to a more advanced password-based key derivation function such as Argon2, which has at least bindings for Java.


Is it possible to do a known-plaintext attack with this set up of AES CTR mode?

The answer is simply no;

The known-plaintext attack on AES-CTR mode will reveal the encrypted output of the AES
$$c_i = p_i \oplus E_k(ctr+i)$$
$$ c_i \oplus p_i = E_k(ctr+i)$$

and since in the counter mode, we know the counter values (input to the AES in CTR mode), we can see this as known-plaintext attack on ECB mode.

The possibility of known-plaintext attack on AES in ECB mode is given lately as;

  No. This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack. This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.


Has threefish successfully been attacked (practically or theoretically)?

Full disclosure — I'm a Skein/Threefish co-author. Also, when I mention Skein/Threefish without any other qualification, I mean Skein/Threefish-512.

The security proofs we did for Skein prove that if there's a weakness in Skein, it implies an underlying weakness in its components (Threefish or UBI). As Dmitry says above, Threefish is very strong, and there are very few attacks on it. I don't know of one that's better than the 35-round attack we mention in V1.3 of the paper.

Our goal in Skein was that we know a lot more about designing block ciphers than hash functions so we'd build a strong hash function by starting with a strong cipher. Threefish builds on Twofish, (P)Helix, and other things. The philosophy was lots of fast rounds, and that has held up.

Enough time has passed that I'm starting to use Threefish in some of my own work. I think it's a very good way to go because tweakability is a powerful feature. If you are interested, also look at McOE mode which can turn a cipher into an authenticated function, and is designed to be resistant to misuse. It is built with AES and Threefish as examples, and I think Threefish in McOE mode is powerful.


Is it worth hiding an AES encrypted text string in a PNG image for better security?

"Hiding" content in an image (or other medium, it's a general technique called steganography) can be done either in a very obvious way (a dedicated data block, called ancillary chunk, which does not form part of the image), or it can be more effectively hidden in the low order bits of the image, thus very subtly degrading the picture.

Both methods can be discovered by a dedicated analyst, there are even automated tools which can flag images if some telltale statistical anomalies are detected.

This method doesn't add any extra security for the secret message - which is already encrypted anyway. The only thing it provides is a very weak protection of the fact that a secret message existed at all.


Is it OK to encode data using key equal to data

Your scheme turns AES into a one way function. As you already found out from the comments this scheme doesn't preclude collisions. There is a good reason why hash functions have a larger output size than the block size of most block ciphers as the birthday problem is applicable for this newly build PRF and normal hash functions.

The chance of a collision is so low for SHA-2 that it is easily possible to prune some of the rightmost bytes output and still have a large security margin in case you need a smaller output. The number of hashes required a collision using SHA-256 is about $2^{128}$. I.e. that's about the same amount of tries as brute forcing AES-128. In the end you need to end up with at least double the amount of the required strength in bits.

Your key is a problem as well. You say you have 20 character of letters and numbers. That's not a good AES key. If you just encode it using ASCII you have a 20 byte key; 20 byte keys are not acceptable for AES as block cipher. So you can either thing of some weird encoding method, or you could use a KDF. But the KDF is likely made up by a block cipher or hash function...

Finally, a hash can take any size of input, and it has been designed to be a one way function. This is what it was designed for, there is simply no need for a block cipher here. If you have a need for the function to be irreversible you may want to use a password hash such as PBKDF2, to counter the lack of entropy in the input.


md5: is reverse length-extension attack possible?

The short answer is: No, there is no known practical attack in the setup given.

But we do not have an argument/proof that there is not one, and we should be less confident in that than we are in HMAC-MD5, for which we have such an argument.


What is it meant by a "hybrid argument"?

Quoting from "On beating the hybrid argument" (by Bill Fefferman, Ronen Shaltiel, Christopher Umans and Emanuele Viola; 2012):

  The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor $k$ equal to the bit-length of the distributions: $\epsilon$-distinguishability implies $\epsilon/k$-predictability.

As you're looking for a more in-deep and more practical explanation of "hybrid argument", I would like to recommend diving into the PDF "The hybrid argument", which includes a whole bunch of examples to walk through so you can wrap your head around it completely.


Can we quantify strength of encryption scheme ?

Usually cryptographic strength is given as the effective strength in bits of a security primitive. This is related to the amount of tries necessary to break a primitive. So for AES-128 the effective strength is about 126 bits. The number of bits is of course directly related to the number of tries required to perform an attack. This is often given as a power of two as well (e.g. $2^{126}$ for above). This of course directly relates to the number of bits. The time it costs for a single try of course depends on the runtime and is usually not considered significant.

For attacks it is often necessary as well to keep some kind of state. In that case the memory requirements are described as well. Often the memory requirements are particular to a specific primitive (e.g. the amount of encrypted blocks to store in memory), but usually those are easily converted to bits or bytes.

If the strength is related to an algorithm then of course the order $\mathcal{O}$ is most often used. If an attack has a specific order $\mathcal{O}$ then filling in the parameters of the function should return an approximation of the amount of tries.

Background

Cryptographic strength can be tricky to calculate and is highly dependent on the known attacks. It very much depends on the use of the primitive within a protocol or setting if attacks are applicable at all. Because of this the cryptographic strength shown is just the cryptographic strength of the primitive within its mathematical context. So that would be 128 bit effective for AES-128 and SHA-256 (because of the birthday paradox).

Even then it may be hard to clearly identify cryptographic strength. For instance for DH there is no clearly defined key size. Both the size of the modulus as well as the size of the subgroup should be taken into account. Key size and cryptographic strength do not have to be directly related (and key size may not be that well defined in the first place).

To get a clear idea about cryptographic strength there are organizations such as NIST and ECRYPT (II) take a look at keylength.com and the documents linked from that site.


Regarding application of ring signatures

To understand the application, it is useful to contrast this with the use of regular signatures.
Imagine Alice sends a message $m$ to Bob together with a signature $\sigma$ of $m$ under her own public key $\mathsf{pk}_A$. A regular signature scheme now has two important properties:

It's publicly verifiable, i.e., anyone can verify that the $\sigma$ is a valid signature of $m$ under $\mathsf{pk}_A$.
It's unforgeable, i.e., only someone in possession of the corresponding signing key $\mathsf{sk}_A$ could have produced a valid $\sigma$.

The combination of the two, together with the assumption that Alice has a strong incentive to keep her signing key secret¹, leads to a property called non-repudiation. This means that the recipient can prove to a third party that the Alice really did send $m$ simply by producing $(m,\sigma)$.
Now, say $m$ is something legally or morally incriminating. Then, among other things, this opens Alice up to blackmail. Bob can threaten to release $(m,\sigma)$ which would prove to the public or some third party that Alice said $m$.
Alice understandably would like to prevent that. So this is where ring signatures come in. If we replace the signature scheme above with a ring signature scheme, then Alice would be sending $m$ together with a ring signature $\sigma$ of $m$ under the set² of her own public key and Bob's public key $\{\mathsf{pk}_A,\mathsf{pk}_B\}$.
A ring signature is still publicly verifiable, however the unforgeability now only guarantees that the signer must have known one of $\mathsf{pk}_A$ or $\mathsf{pk}_B$. This means that Bob can no longer prove to a third party that Alice sent $m$, since Bob himself could have simply computed $\sigma$ himself.
He can of course still try to blackmail Alice, but he can no longer rely on the security of the signature scheme to do so.

¹ This is where this argument could break down in practice.
² Sometimes also called ring, even though the name ring signature actually comes from the way the first such scheme computed it's signatures.


One of the security guarantees of garbled circuits is that the evaluator doesn't learn anything about the circuit beyond the output on the given input.  Executing more than one input string will break this property.  For instance, if you allow him to evaluate two inputs, $0^n$ and $1^n$, then he can "mix and match" bits on each gate to determine what kind of gate it is.  An AND gate will have three outputs which are the same, but an XOR will only have two, etc.  Additionally, by doing this mix and match, he will be able to calculate the output value of the circuit on new inputs which you have not directly given to him.  Combining these two advantages, it is also very likely that the will be able to recreate some or all of the bits of the input by tracing the circuit, since he learns the final output in plaintext.


Is this method of speeding up a symmetrical algorithm secure? (AES output joining)

The issues here are not so much security wise (that's downstream of this topic) but pragmatism.  The penguin problem rules out ECB mode for most cipher use, so lets look at your requirements:-

  Divide data into n parts

The easy bit

  Run n threads

Not as easy as it sounds.  This is very language dependent.  For example Python doesn't do well with parallel tasks due to it's global interpreter locking system. Java threads can be cumbersome.  And then there is the inter-thread communication - more overhead and slowdown.  Even C/C++ threads will have to talk amongst themselves.  Will you write a thread pool yourself?  I guess there must be an extant library you could use as mitigation.

  Each thread encrypts its part of the data

The crux of the cryptography.  Have a close look through the wiki entry on cipher modes. You cannot hope to achieve parallel operation on all modes as that's fundamentally impossible for some as they're sequential.  CBC mode is a simple example of one ciphertext passing into another subsequent block operation. Yes it can be run with multiple threads, but each thread will be paused waiting for the previous one in the chain to complete. That said, CTR mode seems to be a mode that's suitable for your scheme.

  Take the output of all of the threads and concatenate (join) all of them together

Even in CTR mode the chunks have to come out in the correct order, requiring more thread collaboration. And again inter process communication has to be addressed which will siphon off   speed gains.

So in conclusion, and without even dealing with  specific security problems, this scheme is troublesome.  Since only a few modes are possible in this scenario, and their security issues are mode dependent, it is quite difficult to give more detail.  But just to mention a generic one, clones of the key and plaintexts will be floating around the machine that might open an attack vector.  And the time of complete thread destruction can be uncertain under a garbage collector.

This   falls into the realm of writing your own crypto, with key management, inter process communication and a large case of debugging. With modern CPUs featuring hardware AES circuity, that is clearly the way forward.  I cannot think of any circumstance that warrants this level of cryptographic development, testing (heartache) and security risk.  Remember that time is money if this is a commercial venture, and in that case does dubitable and possibly  marginal performance gains offset just getting a faster CPU?


Understanding fail-stop subliminal channels

Answer to main question: Yes, it is indeed the way they work. Specifically, the rationale that in order to demonstrate whether or not a channel is subliminal-free, one needs to focus only on the instances in which A does not stop, is quite logical. Consider that, if A stops, then W realizes that a subliminal communication is taking place and the channel is not subliminal-free. But similarly, for the cases in which A does not stop, W still needs to decide if there is a subliminal channel. This is more clearly explained in "A Progress Report on Subliminal-Free Channels." (Check specifically Definition 3, although the prevoius sections help understanding the thought process of the authors.)

Answer to follow up question: TLDR; a fail-stop subliminal channel is  practical roughly when only one subliminal bit needs to be transmitted. Thus, it may make sense only in very restricted cases. The example by Desmedt is that in D day, it would have been enough to transmit a subliminal bit of "landing would not take place at Calais." When more bits need to be transmitted, it is very probably not practical, as its probability of going undetected goes down exponentially (and its capacity drops to $0$ just as quickly).

It can be naturally argued that the practicality of a subliminal channel is determined by its capacity, when the subliminal communication goes undetected.
The maximum capacity of a channel (in the absence of communication errors), is determined by its entropy. And given the previous answer, we know that a fail-stop subliminal channel is undetected as long as A does not halt, so we can use conditional entropy.

The condition making A halt may be defined arbitrarily, but for the sake of simplicity, I stick to Desmedt's example (the following calculations are actually sketched in Desmedt's paper, although a bit succinctly...). In Desmedt's example, A stops if the last bit of the r value of the DSA signature matches $b \oplus c$, where $b$ is a secret (uniformly sampled) bit shared by A and B, and c is the subliminal bit to be transmitted. The event in which A does not stop implies that W sees a perfectly valid DSA signature that has been generated according to the protocol. Thus, he cannot differentiate it from a completely legitimate run. This is denoted with $\{w = 0\}$ (i.e., W ouputs "no subliminal information").

Lets generalize and assume that A wants to transmit u bits. I denote the bitstring to transmit subliminally with $c_i$, for every $i \in [0,2^u-1]$.
Then, the capacity of one single execution of the protocol is:

$H(c_u|w = 0) = -\sum_{i\in[0,2^u-1]} p(c_i,w=0) \log \frac{p(c_i,w=0)}{p(w=0)} = -\sum_{i\in[0,2^u-1]} 2^{-2u} \log \frac{2^{-2u}}{2^{-u}}=u2^{-u}$

[Note that $p(c_i,w=0)$ is the event in which $c_i$ equals the $u$ least significant bits of $r$. Then, $p(c_i,w=0)=2^{-u} \cdot 2^{-u}$, as $c_i$ and $w=0$ are independent random variables, given that $b$ is chosen uniformly at random, and $r=(g^{k' \cdot k''} \bmod p) \bmod q$ is also drawn uniformly at random (because $k''$, chosen by W, is.)]

Now, the function $f(u)=u2^{-u}$ has a maximum at $1/\ln2$ and therefore the maximum capacity is $1/\ln2 \cdot 2^{-1/\ln2}=0.5307$.

Note that, if we want to analyze the case in which A tries to transmit t different signatures (restricting to the fail-stop strategy), each including $u$ bits of subliminal information, it is equivalent to having A try to transmit $tu$ bits in a single signature, which is again maximal when $tu = 1/\ln2$.


Can you get two unpredictable hashes from the same message with, e.g. SHA1?

I'd need to know precisely what the "lookup" operation does but I'm pretty worried already by that XOR. Let's remove the lookup operation for now and see what happens.

Suppose we have two hashes that hash to the same length ($L$) and we XOR their outputs. You've now got a much weaker hash that either of them.

Here's how to find a collision. Hash a message $m$ using $H_0(m) \oplus H_1(m)$ to produce an output $h$. We now wish to find a collision on $m$, such that $h=H_0(m') \oplus H_1(m')$

We now create a series of messages $m_i$ that are slightly different to $m$. The goal here is to find a message which has a xor of $H_0(m_i)$ and $H_1(m_i)$ equal to that of $H_0(m)$ and $H_1(m)$.

Let's assume that $H_0$ and $H_1$ behave like random oracles. In that case, the probability of this happening is approximately $2^{L\over2}$. Each oracle will take the message $m_i$ and produce a random bit string of length $L$. The probability that they collide will be $2^{L\over2}$ by the birthday paradox.

There's a slight difference here in that we're not after a precise collision but for them to have a fixed XOR. Even so, this event will happen with the same probability. We're just changing the meaning of the equality.

Note that this attack is not the typical birthday attack against a hash. The typical birthday attack finds a pair of message $m'$ and $m$ that hash to the same value. Here, I'm taking a known fixed hash value for one message and finding collision for it. That should normally take $2^{L-1}$ time but this attack demonstrates it in $2^{L/2}$ time. Thus, this scheme is completely unsafe.


Can string lookups be vulnerable to timing attacks like array lookups are?

Yes, string algorithms can be vulnerable to timing attacks.

A very common example is string comparison. The best performing way to implement it in general is to compare two strings one character (or memory word) at a time and return inequality as soon as they don't match. However, this kind of a routine is vulnerable to timing attacks that can find the (approximate) length of the common prefix. Using such a string comparison routine to compare passwords or hashes has lead to attacks (an early 1970s example, a random 2009 example).

Similarly, when you are using a multibyte encoding, simply looking up a character in a string can allow timing to reveal details about the string before then.


Cracking hashes: With vs without knowing the salts

The point of using salt is not that it's secret. In fact, it's usually stored together with the hashed password. The point of using salt is that it's different for each entry. This has a few major benefits:

Two users who use the same password won't have the same hash. Hence an attacker can't see which users share a (presumably weak) password.
In a dictionary attack, the attacker can't use a precomputed table of bcrypt hashes. Instead, they have to compute each hash for each salt anew. In particular, the use of salt is a pretty good defense against attacks using rainbow tables.


I would explore the GPU option before spending money on specialized hardware.

I have done something similar using CUDA where I was doing many ECC operations in parallel. The GPU was about 30x - 50x faster than the CPU.

You could probably hash the data on the CPU and then use the GPU for the RSA exponentiation.


What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?

The problems:

The Discrete Logarithm problem: Given $y$, find $x$ so that $g^x = y$.
The Computational Diffie-Hellman problem: Given $y_1 = g^{x_1}$ and $y_2 = g^{x_2}$ (but not $x_1$ and $x_2$), find $y = g^{x_1·x_2}$.
The Decisional Diffie-Hellman problem: Given $y_1, y_2, y_3$, decide whether they are of the form $y_1 = g^{x_1}$, $y_2 = g^{x_2}$ and $y_3 = g^{x_1·x_2}$ for some $x_1, x_2$ (which you don't have to find). Assume with 50% probability they are really of this form, and with 50% probability simply randomly selected, and you have to guess right with significantly better probability than 50%.

All three of these are defined in any (multiplicatively written) group, and are hard in some groups, while easy in other ones. (Actually, we don't really need a group, a semigroup with some generator $g$ is enough. But it is more interesting in groups.)

Which one is harder?

Now, if you have a machine (program, oracle) which solves (efficiently) the Discrete Logarithm Problem in some group, you can easily construct a solver for the Computational Diffie-Hellman problem (in the same group):

just compute $x_2$ from $y_2$ and calculate $y = (y_1)^{x_2}$.

There is no (generic) known way for the other direction.

If you have a solver for the Computational Diffie-Hellman problem, you can also decide the Decisional Diffie-Hellman problem:

just compute $y$ to $y_1$ and $y_2$, and checking $y = y_3$.

There is no (generic efficient) known way for the other direction.

This means, DDH is at least as easy (or even easier) as CDH, and CDH is as least as easy as DL. Or, other way around, DL is at least as hard as CDH, and CDH is at least as hard as DDH.

An even another way of looking at it is the "assumption to be hard", where "hard" is defined as "not doable for a reasonable user".

If DDH is hard, then CDH must be hard too (but not necessarily the other way around).
If CDH is hard, then DL must be hard (but not necessarily the other way around).

Thus, the hardness of DDH is a stronger assumption (is valid in fewer groups) than the hardness of CDH, which itself is still stronger than the hardness of DL.

As Thomas Pornin mentioned in a comment, there are some elliptic curve groups where DDH is easy, but CDH and DL are (assumed to be) hard, and which are used in pairing based cryptography. This is a good indication (though not yet a proof) that the DL and CDH problems are really strictly harder than DDH.


Why are the initial states of hashes functions (like SHA-1) often non-zero?

In early years of hash function design it was unclear how to choose constants (not only initial vectors), and it was widely assumed that the more random they look, the more secure the function is. There is still not much research in this direction. However, there have been several attacks (rotational cryptanalysis, slide attacks, internal difference attacks) that exploited similarity between the constants and their low Hamming weight. It may happen that some choice of constants yields a weakness or even a backdoor that allows a faster collision/preimage search.

Recent attacks on Keccak/SHA-3 would have been slower if Keccak state were initialized with some weird constant, not zero as it is now. This is a property of the Keccak permutation, whereas the encompassing sponge construction is invulnerable to the initial vector choice.

Another reason is to choose distinct IVs to differ functions that are identical, but truncate the output to a different number of bits (like SHA-224 and SHA-256).


How to calculate chance of missing an error with overlapping hashes?

The usual way this is performed is through a Merkle tree, of which you will definitely find information on the Internet. What you can do is to separately hash each block (for performance reasons) and then hash the hashes together (in the correct order). Then you can simply store just the resulting hash.

In your scheme you perform a hash with half output. But you only want to trust the block after you've also verified the additional hash. So basically your "half-hashes" over the blocks are pretty useless. You may just as well hash the 4 blocks together or use a Merkle tree as described above.

Note that none of your constructions is likely to have more security than the output of a single hash (the state of both the single block hash and four-block hash would be the same after the first block), even though the output is larger than that. That said, I don't directly see how it could be less than the security of a single hash either.


Given any $n-$bit sequence $(a_1,\ldots,a_n)$ with $a_k \in \{0,1\}$ you can use the Berlekamp Massey algorithm (which is conveniently recursive) to obtain minimal degree characteristic polynomials $C_m(X)$ where $C_m(X)$ is the output polynomial of Berlekamp Massey, when its input is $(a_0,\ldots,a_m)$ with $1\leq m\leq n.$

The linear complexity profile of $(a_1,\ldots,a_n)$ is simply the sequence $d_1,\ldots,d_n$ where $d_m$ is the degree of $C_m(X)$.

If you have $n=2^k,$ then there is a much faster algorithm to compute just $d_n$ due to Richard Games and Agnes Chan, the so-called Chan-Games algorithm, which of course can be used to obtain $d_1,d_2,d_{2^2},\ldots,d_{2^k}$ but not the complete profile. This has complexity $O(n \log n)$ while Berlekamp Massey has complexity $O(n^2).$

There are other fast algorithms for cases such as $n=m 2^k$ where $m$ is odd which use various generalisations of the coding theoretic result also known as Blahut's Theorem, which is that the linear complexity of a sequence is the Hamming weight of an appropriately defined and normalized finite fourier transform of the sequence.


The basic problem seems to be that of canonicalization. If you can't reorder the set, then you will have to choose a commutative, associative, operator to concatenate the values; $a \otimes b = b \otimes a$ and also $a \otimes (b \otimes c) = (a \otimes b) \otimes c$

An immediate candidate for this would be to interpret the elements, $m_i$ as integers and let $\otimes$ be integer multiplication. You could then pass it through a secure hash function $H(\prod m_i)$ to get your final hash.

To improve the collision resistance with this choice of $\otimes$ operation (unfortunately $H(5 \times 4) = H(10 \times 2)$; different sets with the same hash) you might consider associating each message with a unique prime number, and by the fundamental theorem of arithmetic, this product will be unique.