Can AES GCM mode detect an incorrect key and refuse to decrypt?

An AES-GCM-encrypted message is obtained per an encryption key $K_0$. As for any correct implementation of AES-GCM, we assume that legitimate encryption of multiple ciphertexts with $K_0$ uses $\text{IV}$ such that the counters (obtained by increment of the $\text{IV}$) do not overlap; and that the implementation of decryption gives an error message when the authentication check fails.

will AES in GCM mode detect that I am using the wrong key and give me an error message (..) ?

No, with strictly only what's stated. It is possible to exhibit a ciphertext (including $\text{IV}$) and two distinct keys $K_0$ and $K_1$ that both decipher successfully (and a plaintext that, encrypted with key $K_0$ and $\text{IV}$, encrypts to the ciphertext including $\text{IV}$ and authenticator tag, thus matching the wording in the above re-statement of the question).
But yes, if the ciphertext was prepared legitimately (which was my assumption in a first version of this answer). An attack against a given ciphertext, aiming at exhibiting $K_1$, has cost $p\,2^k$ AES encryption for probability $p$ of success and $k$-bit authentication tag, even if multiple ciphertexts are available. Prepared legitimately holds at least if one (or both) of the following holds:

The key $K_0$ is chosen uniformly at random independently of $\text{IV}$ and the plaintext (even if the plaintext, $\text{IV}$, and $K_1$, are chosen maliciously). That includes any case where $K_0$ is kept secret from adversaries at least until production of the plaintext, which is a standard assumption.
The $\text{IV}$ is chosen uniformly at random independently of $K_0$ and the plaintext (as is the case in some but not all legitimate uses of AES-GCM encryption); that's even if the plaintext, $K_0$, and $K_1$, are chosen maliciously.

Argument: from the structure of GCM it can be shown, under a model of AES as an ideal cipher, that the AES-GCM authenticator tag is a PRF of the key and $\text{IV}$, for any fixed message (plaintext, or ciphertext excluding $\text{IV}$ and authenticator tag).

Conclusion: AES-GCM encryption with secret key $K_0$, or with random unpredictable $\text{IV}$, makes it infeasible that later (including if $K_0$ leaks) anyone could find (much less encounter by accident) another key $K_1$ that allows decryption of the unmodified ciphertext (including $\text{IV}$ and authenticator), yielding almost certainly corrupted deciphered plaintext. However, that can be defeated by the party choosing $K_0$/doing the encryption/choosing the message; and the essential unmodified ciphertext hypothesis is artificial, for it goes against the rationale of using authenticated encryption.


Can BPS be used to encrypt a single integer, and restrict the output to a certain range?

This can't be done in a straightforward way with just BPS, since the straightforward way will result in a year greater than the current one for roughly 80% of ciphertexts (since 9999 is the biggest four-digit ciphertext possible). However, using what's called a "rank-then-encipher" scheme, you can specify an input and output format using a regex, then build an FPE scheme on just the strings matching that regex. See this site for details.

EDIT: Also, I don't know BPS that well but I think the "integer of a certain cardinality" can just be a base-10 digit, so you can encrypt a four-digit year as four characters.


CTR vs CBC cycles per byte with OpenSSL EVP

OpenSSL utilizes AES-NI instructions which are pipelineable. Note that CTR encryption and decryption and CBC decryption can all be computed in parallel, whereas CBC encryption is strictly sequential (you need the result of block $i$ in order to encrypt block $i+1$). Thus, CBC encryption cannot utilize the pipeline and you get 4+ times the running time. This is exactly as expected.


Low complexity implementation of a small blocksize cipher (< 64 bit)

This will probably be OK.  It does have some non-trivial side effects/caveats:

The effective key length is reduced to 86 bits.  Only the low 22 bits of each of the 4 key words will matter, so only 88 bits of the key material are relevant.  Then, there are known equivalent-key properties of TEA that further reduce the effective key length to 86 bits.
A 44-bit block width is uncomfortably narrow.  Most modes of operation will have security weaknesses if you encipher more than about $2^{22}$ blocks of data.  Even if you encrypt a fraction of that much data, there's still a chance of problems: if you encipher $b$ blocks of data, there's about a $b^2/2^{45}$ chance of some sort of problem.
Due to the equivalent keys, TEA is not suitable for building hash functions.

Have you considered using something other than a block cipher?  Maybe a stream cipher?  What are your needs?


Why crypto hash functions must be collision resistant and how to find resistant?

If a hash function is not collision-resistant (there is no such thing as collision-free in hash functions because their output has a fixed length) then an adversary can break the function with little effort. More formally (but still quite informally):

You have a set $X$ of possible inputs. For each input $x \in X$ the hash function $F$ will output $h=F(x)$. Note that there are more than one $x$ that will give the same $h$ as a result, and the set of all possible results of $F$ is finite, unlike $X$. The function's job is to make it hard for the attacker to find any $x'$ so that $F(x') =  F(x) = h$.

Edit: I also found this question which is relevant to this one


Are the following functions pseudorandom?

Okay, so now that we've agreed that generalized pseudorandom functions can be of variable length :-D, I'll slightly rephrase your question to meet the definitions I'm working with, and then prove (1).

Given a pseudorandom function $F = \{F_{n}\}_{n \in \mathbb{N}}$, such that for each $k \in \{0,1\}^n$ , $F_k:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, is the function defined by $W_{k_1,k_2}(x) = F_{F_{k_1(0 \ ^n )}}(x) || F_{k_2}(x)$ a generalizable pseudorandom function?

Assume by contradiction that $W$ is not a generalizable pseudorandom function,
then there exists a probabilistic polynomial time (PPT) oracle machine $M'$ and a
polynomial $p(\cdot)$ such that for infinitely many $n$'s,

$$\big|\text{Pr}[M'^{W_{k_1,k_2}}(1^{n}) = 1] - \text{Pr}[M'^{H'_{n}}(1^{n}) = 1]\big| > \frac{1}{p(n)}$$

where $k_1,k_2 \xleftarrow{\$} \{0,1\}^n$ and $H' = \{H'_n\}_{n \in \mathbb{N}}$ with $H'_n$ uniformly distributed over the set of all functions mapping $n$-bit strings to $2n$-bit strings.

We will use $M'$ to construct a PPT oracle machine $M$ to distinguish $F_k$, where $k \xleftarrow{\$} \{0,1\}^n$, from $H = \{H_n\}_{n \in \mathbb N}$, where $H_n$ is uniformly distributed over the set of all functions mapping $n$-bit strings to $n$-bit strings. On input $1^n$, $M$ first queries it's oracle $\mathcal{O}$ with the string $0^n$ and records the result as $k' \leftarrow \mathcal{O}(0^n)$. $M$ then uniformly selects $k'' \xleftarrow{\$} \{0,1\}^n$. Next $M$ runs $M'(1^n)$ and serves as its oracle, returning $F_{k'}(x)||F_{k''}(x)$ whenever $M$ queries with input $x \in \{0,1\}^n$. Whatever output $M'$ returns to $M$, $M$ outputs itself.

If $\mathcal{O} = F_k$, then

$$\text{Pr}[M^{F_k}(1^n) = 1] = \text{Pr}[M'^{F_{k'}||F_{k''}}(1^{n}) = 1] = \text{Pr}[M'^{W_{k_1,k_2}}(1^{n}) = 1]$$

since how we chose $k'$ makes our experiment identical from the point of view of $M'$ to when it's interacting with the oracle $W_{k_1,k_2}$. If $\mathcal{O} = H_n$ we have $\text{Pr}[M^{H_n}(1^n) = 1] = \text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^n) = 1]$. Now, $M'$ is a black box, and was not "designed" to distinguish $W_{k_1,k_2}$ from $F_{H_n(0^n)}||F_{k''}$. That said, we can intuitively see that $F_{H_n(0^n)}||F_{k''}$ should not be distinguishable from $H'_n$ because of our assumption that $F$ is a pseudorandom function. We will now formalize that notion.

Assume that there exists a polynomial $q(\cdot)$ such that for infinitely many $n$'s

$$\big|\text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^{n}) = 1] - \text{Pr}[M'^{H'_n}(1^{n}) = 1]\big| > \frac{1}{q(n)}$$

We can then use $M'$ to construct a PPT oracle machine $M''$ to distinguish $F_k$ from $H_n$. We denote the oracle of $M''$ by $\mathcal{O}'$. On input $1^n$, $M''$ selects $k''' \xleftarrow{\$} \{0,1\}^n$ and runs $M'(1^n)$, acting as its oracle by returning $\mathcal{O}'(x)||F_{k'''}(x)$ for any query $x \in \{0,1\}^n$ that $M'$ makes.

If $\mathcal{O}' = F_k$, then

$$\text{Pr}[M''^{F_k}(1^n) = 1] = \text{Pr}[M'^{F_k||F_{k'''}}(1^n) = 1] = \text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^n) = 1]$$

where the last equality follows because $k$ was chosen uniformly at random and $H_n(0^n)$ is a uniformly distributed random variable over the outputs on input $0^n$ of every function mapping $n$ bits to $n$ bits, and $k'''$ and $k''$ were both chosen uniformly at random. In the case $\mathcal{O} = H_n$ we have $\text{Pr}[M''^{H_n}(1^n) = 1] = \text{Pr}[M'^{H_n||F_{k'''}}(1^n) = 1]$. We must now go just one layer deeper before deriving a direct contradiction, and prove by contradiction that $M'$ cannot $H_n||F_{k'''}$ and $H'_n$.

Assume that there exists a polynomial $r(\cdot)$ such that for infinitely many $n$'s

$$\big|\text{Pr}[M'^{H_n||F_{k'''}}(1^{n}) = 1] - \text{Pr}[M'^{H'_n}(1^{n}) = 1]\big| > \frac{1}{r(n)}$$

Since the first $n$ bits of the output of the two oracles should be uniformly distributed, they cannot provide any useful information to $M'$ to make its decision*. Then $M'$ must be able to distinguish $F_{k'''}$ from the second half of $H'_n$ with more than negligible probability. Since this is equivalent to distinguishing $F_k$ from $H_n$, it contradicts our claim that $F$ is a pseudorandom function.

Now we unfold the argument. Since $M'$ cannot distinguish $H_n||F_{k'''}$ and $H'_n$ with more than negligible probability, this contradicts our assumption that $M'$ can distinguish $F_{H_n(0^n)}||F_{k''}$ from $H'_n$ with more than negligible probability. If that assumption is wrong, then $M$ distinguishes $F_k$ from $H_n$ with only negligible difference in probability from that the which $M'$ distinguishes between $W_{k_1,k_2}$ and $H'_n$. By our hypothesis, this is non-negligible, but because we assume $F$ to be a pseudorandom function, no such $M'$ can exist. Therefore, we conclude that $W$ is a generalizable pseudorandom function.

* You could prove this more rigorously by remembering that polynomial-time unpredicability and pseudorandomness imply each other. Then show that you can replace $M'$ with a PPT oracle machine $M'''$ that never reads less than $n+1$ bits of its input (or more than $2n-1$) before guessing a bit, and that the probability that $M'''$ guesses correctly is no less than $M'$.


Salt and pepper at both client and server sides?

I think the detailed approach you have given can work. To address your specific point:

Rule of thumb: No md5 is never okay, for anything.
I'm not sure what you mean but pretty sure that the answer is: No.
The order doesn't really matter although your point is correct and you should probably add field separators instead of just concatenating.

I think proposing this kind of change requires a consideration of the attacker model. Your connection should be secured by TLS and all this becomes moot.

You can do more advanced things, they are great but work a little different. Maybe looking Password Authenticated Key Exchange (PAKE) will give you some inspiration.


URN for ECDSA signature algorithms (including hash algorithm)

According to the IANA registry at https://www.iana.org/assignments/urn-namespaces/urn-namespaces.xhtml, there is no nist-gov URN namespace.  Outside obscure antisocial protocols like RFC 2802 there is no reason to try to use this URN namespace.  You appear to have gotten these URNs from a defunct internet-draft.  If you're using XML signatures, as you appear to be doing, then you can use use the URI http://www.w3.org/2001/04/xmldsig-more#ecdsa-sha256 like RFC 4051 specifies.

(But consider throwing XML signatures in the garbage—if not XML too.  Just sign binary blobs with a fixed signature scheme baked into your application; using XML signatures is asking for trouble.)


What you (most probably) describe is called a "preimage attack", where the attacker tries to find a message that has a specific hash value.

Some related attacks against reduced/weakened versions of SHA-256 are known, but (as far as I know) no such attack was successful against the standard SHA-256 algorithm up to today. So generally, it can be to be considered safe... but: as Stephen Touset already noted in his comment, the security of your final implementation may be influenced negatively if the overall entropy of hashed data is small enough to render things like brute-force attacks feasible. You should definitely keep a critical eye on that aspect.

In fact, there are - at least - two things you should watch out for in relation to salts in general:
(btw.: just in case you don't know... "salt" is the crypto-term for your TXT part)

The "Salt Reuse" Problem

Depending on your actual implementation, it could be a mistake to use the same salt in each hash.

If - for example - two users use the same salt, they will produce the same hash. This can be pretty ineffective from a security point of view. In such a case, an attacker could use a reverse lookup table attack to run a dictionary attack on every hash at the same time. The attacker would just have to apply the salt to each "message" guess before the attacker hashes it.

Simpler said: if the salt is reused, lookup tables and rainbow tables could be built for that salt and that would make it easier to crack hashes generated by your implementation. That's why - for example - when implementing user-login systems and hashing user passwords, a new random salt must be generated each time a user creates an account or changes their password.
The "Salt Length" Problem

If a salt is too short, an attacker can build a lookup table for every possible salt. Let's take your example and assume it were a real-life implementation where your salt is made up out of the three letters TXT. If an attacker would guess you were only using 3 ASCII characters, then the attacker would merely need to check around and about (95x95x95 =) 857375 possible salts. That may seem like a lot at first glimpse, but creating according lookup tables is rather simple and an according attack pretty manageable with today's hardware.

So, to make it infeasible for an attacker to create a lookup table for every possible salt, the salt must be long.

Personally, I assume it to be a good choice to use salts of the same size as the output of the individually used hash. For example: the output of SHA-256 is 256 bits (= 32 bytes), so I would salt it with (at least) 32 random bytes. But this is more of a personal preference. Others might disagree.

Getting back to your question while pointing at what I noted above: it can be safe, if you implement it correctly - but a small mistake in your implementation may result in a big gain for potential attackers.


Capital passphrases with rainbow tables?

You should first understand that hashing (and modern cryptography in general) usually works with bits and bytes, and not directly with 'characters' such as 'abc'.

Before performing a cryptographic operation such as hashing or encryption, the input (in this case, the passphrase) is converted from it's encoded format (usually unicode or ascii) to bytes.

You can experiment at this website to gain an understanding of how this works. Note that the text 'abc' maps to bytes [61, 62, 63], but 'Abc' maps to [41, 62, 63].

Try calculating the SHA-256 hash of the strings 'abc' and 'Abc' at this website. You'll notice that they're completely different.

Finally, note that the output of most cryptographic functions is also returned in raw bytes, which can then be encoded to hex (such as your example above), base64, or any other number of encodings.

Encodings are completely reversible and don't use any keys, they're just a way of representing/storing binary information. Base64 is more efficient than hex encoding, and accordingly it is case-sensitive. Hex, on the other hand, is case insensitive, so 'cb27b6' and 'CB27B6' still map to the same bytes.

To answer your question, for a rainbow table to be effective, you would need to store the hash of all possible lowercase/uppercase combinations of the passphrase. It's also common to store variations of spelling, like substituting 's' for '$', and 't' for '+'.

Regarding the truncation - rainbow tables are limited by storage. To store the full hash of the many permutations of billions of inputs is expensive. Truncating the hash (ie, chopping off everything but the first 3 or 4 bytes) saves a lot of space, and if a match is found there's a strong likelihood that the full hashes will match, and it's very fast to verify.

Note that using a slow hash and salt will render rainbow tables ineffective.


Are different elliptic curves compatible?

No, it is not possible to mix domain parameters / curves when performing key derivation.
First of all, the implementations are likely to fail if they find curve identifiers. These can be single protocol specific bytes, OID's or named curves or full parameter sets, depending on the protocol.
Second, it is very likely that implementations will reject the public key value if the key value identifies the curve. It might also be that the key is related to the curve field (at least 2x curve field size for uncompressed keys and 1B + 1x curve field size for compressed keys).
Thirdly, it should try and see if the point is actually on the curve, it is very possible that this fails as well, if the implementation is correct. Some curves are designed in such as way that such checks are not necessary.
Finally when the operations are performed then the calculations would result in a non-matching "shared" secret. Subsequent validation that the shared secret is valid would fail (e.g. using an explicit MAC calculated from the shared secret or the first message MAC, usually from derived keys).
So no, you cannot "mix curves" in general, there needs to be some way to make sure that both sender / receiver use the same set of domain parameters / curve. This is rather independent of SubtleCrypto, of which I'm not a full expert (but it is a rather generic cryptographic API, so yeah).


How do decryption algorithms determine whether your attempted passphrase is correct?

An important property of a ciphertext is that it has to be indistinguishable from truly random data. This allows the encryption cipher to produce ciphertext that reveals no information about the plaintext (other than size) or the encryption key. In fact, this property even allows encryption algorithms to act as pseudorandom byte generators by simply making them generate a stream of random ciphertext.

In the case of stream ciphers, decryption is the result of XORing each ciphertext byte with its corresponding keystream byte in sequence. If the keystream byte corresponding to the ciphertext byte is correct, the result of the XOR will yield the original plaintext byte. Since ciphertext cannot be made to provide any information regarding the plaintext, it follows that it also cannot be made to reveal whether the XOR of a certain keystream byte yielded a correct plaintext for the byte or not. Otherwise, the cipher would be clearly broken and allow us to basically query it for information regarding the plaintext.

A similar principle applies to block ciphers such as Blowfish, except those ciphers operate on entire blocks of bytes instead of individual bytes, and also employ other operations such as substitution in tandem with XORs, organized in structures such as Feistel networks.

Therefore, when it's important to be able to inform the user whether a decryption operation has succeeded in yielding the expected data, cryptography engineers use Message Authentication Codes. Hash-based MACs allow a candidate plaintext to be compared against an authenticated hash value. If the check passes, then we know that it is the correct plaintext and are then able to notify the user that the decryption function was successful as intended.

Generally, if you want to verify the integrity of encrypted data as it goes through the wire to reach someone, you would generate a MAC for the ciphertext. But if you also want to verify that the decrypted plaintext is correct (as seems to be your case here,) then you would generate another MAC for the plaintext and send it along with the ciphertext.

While hash-based MACs are probably the preferred way to do this, they aren't the only way to verify successful decryption. For example, TrueCrypt will check the first four bytes of the volume header in order to see if decryption is successful. This approach is likely to be more error-prone than HMACs in most applications, however.

Finally, there are block cipher modes of operation (such as Galois Counter Mode) that grant block ciphers such as Blowfish or AES the ability to self-authenticate. This pretty much allows a ciphertext to verify its own integrity without the need for an external check. Depending on what you're trying to accomplish, you may want to investigate both HMACs and Galois Counter Mode and decide which offers the verification properties you're looking for.


Is there a security problem with this prime generation algorithm?

This is the approach that finally let us factor $N$ for the competition. I believe it completely breaks the given scheme. Let's write down the formula for $N$:

$N = pq = \frac{3s^4+1}{4}\cdot\frac{11t^4+1}{4}$ for some $s, t \in [2^{128}, 2^{129})$

After some rearranging:

$\frac{16}{33}N = (st)^4 + \frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33}$

In our case, we had $\frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33} < (st)^2$ and thus after we substitute $x := (st)^2$:

$x^2 \le \frac{16}{33}N < x^2 + x = x(x+1) < (x+1)^2$

So we could compute $x = \lfloor\sqrt{\frac{16}{33}N}\rfloor$ and then factor $\sqrt x$ (which has only 256 bits) to get $s$ and $t$.

I feel like the above inequality holds generally if $s$ and $t$ have somewhat similar value, but I haven't tried to prove this.


Generating passwords from a master password using rules

The reason reusing passwords is a bad idea is that the security of all your accounts relies on the security of the weakest account which uses the same password. If you sign up for PNC Bank and [favorite show here] Fan Club using the same password, one of them being compromised will compromise them both.

That being said, under the assumption that one of these services will be compromised eventually, the security of them relies on the security of your scheme, rather than the master password itself. If all you're doing is changing the first letter, then it is trivial to guess it given a leaked password.

A better method could be using some variant of HMAC to combine your master password with the website's domain name.

HMAC_MD5("foobarone", "facebook.com") = "b5bda098afd19b1f7992abfa9ab7d710"

You could then use "b5bda098afd19b1f7992abfa9ab7d710" as your password for facebook. For convienience, you could truncate it to "b5bda098afd19b1f" and still have a relatively strong (64 bit) password.

Using LastPass (or some other manager for that matter) is better than using a homemade system, though.


Bits of entropy needed to choose a random element from a list?

One can achieve this with a technique called Knuth Yao sampling. It:

Allows you to sample from any distribution $X$ of finite support (say where the function $f(i, s) = \text{the }i\text{th bit of }\Pr_X[X = s]$ is efficiently computable)
Using on average $\leq H(X) + 2$ bits of entropy, where $H(X)$ is the entropy of the distribution under consideration.

One can then replace $X$ with your distribution (say uniform on $3^n$ elements) to get the result. I'll quickly describe how Knuth-Yao sampling works for the rest of the answer.
Knuth Yao sampling works by constructing a certain (usually infinite) binary tree, and executing an unbiased random walk on it. Leaf nodes of the tree are labelled by elements on the underlying probability distribution, and when you hit a leaf node you terminate the walk and output that that element as your sample.
Why should this work?
The basic idea is to put at leaf labelled $s$ at depth $i$ iff $f(i, s) = 1$.
Then the following facts can be combined to show that the distribution of outputs of the sampler is precisely $X$:

The probability of reaching any particular node during an unbiased walk of a binary tree is $1/2^i$, where $i$ is the depth of the node
Therefore, the probability the sampler ends in a leaf labelled by $s$ at depth $i$ is $f(i, s)/2^i$ (if $f(i, s) = 0$, there are no such leaves, otherwise there is precisely 1).
The sampler can enter at most one leaf (it terminates after), so they form a set of independent events.

Then one has that:
\begin{align*}
\Pr[\text{KY sampler outputs }s]&= \sum_{i = 0}^\infty \Pr[\text{KY sampler outputs }s\text{ in depth }i]\\
&=\sum_{i = 0}^\infty f(i, s) / 2^i\\
&= \Pr[X = s]
\end{align*}
Showing that the average entropy usage is bounded by $H(X)+2$ requires a fairly careful argument, which you can find in Knuth and Yao's intial paper (which is actually quite hard to get ahold of, but can be found in one of Knuth's collections of selected papers (Selected Papers on Analysis of Algorithms, entry 34 The Complexity of Nonuniform Random Number Generation).


On the security definition of password-authenticated key exchange

Let's approach the question from this direction.

PAKE tries to solve this problem: Alice has a password $PW_{a}$, and Bob has a password $PW_{b}$; consider a protocol where Alice and Bob exchange messages, and generate encryption keys $E_{a}, E_{b}$ where $E_{a} = E_{b}$ if $PW_a = PW_b$ (and unrelated if $PW_a \ne PW_b$); if they're the same, Alice and Bob can use the common key to protect traffic.

In this scenario, one thing that an attacker Eve can do is pretend to be Alice, create a guess at the password $PW'$, and then run through the protocol with Bob (who knows the real password); if Eve picked the same password as Bob ($PW' = PW_b$), she knows her guess at the password was correct.

This (and the obvious related one where Eve pretends to be Bob) are inherent within the scenario; what a PAKE attempts to do is ensure that there is no significantly better attack; that going through the plausible passwords, and trying them one-by-one is about Eve's best option.

The formalism $Adv(A) \leq n_{se}/|PW| + neg$ attempts to capture this idea in a manner that we can make mathematical statements about; if Eve gets $n_{se}$ attempts, and she knows the size of the dictionary $|PW|$ of possible passwords, she can try $n_{se}$ entries with her attempts, and succeed with probability $n_{se} / |PW|$ (assuming that each entry in the password is equiprobable); the $neg$ term is there because no real protocol can actually achieve this.

What does this mean to you?  If the risk that an attacker might guess the password successfully is too high for you, then yes, a PAKE in not applicable; you'll need to find some other authentication method that relies on something stronger than a low entropy secret.


... what happens when the server needs to send a message to the client?

The server uses the symmetric key that the client sent to the  server.

  Does the client have a public key?"

Sometimes.


Frequency of letters change by the length of the texts?

Letter frequency checks how often a letter appears in your text.  Depending on your text, the frequency of letters will change.  If your text is short and has the name "Alex" in it a lot, it will make the frequency of the letter X much higher than average.  Generally when discussing the expected letter frequency, people refer to the average letter frequency that appears in the english language (http://en.wikipedia.org/wiki/Letter_frequency).  Though for specific texts the fequency might not be close to the average, and with shorter texts the frequency might be dramatically different, overall the frequency of a long passage should be close to the average.


Is One Time Pad considered Chosen-Plaintext Attack Secure?

Note: In this answer, I stick to a definition of the One Time Pad where the random pad is used only One Time; at least, I've the name of it as support! Otherwise, it is well known that the OTP encryption scheme consisting of XOR with a repeated key is insecure by even the weakest standard (unknown plaintext with redundancy).

Late addition: further, I stick to the definition of IND-CPA given for ciphers in standard literature and quoted below. See this other answer for a different definition, which applies to the OTP, and is met.

INDistinguishability under Chosen Plaintext Attack applies to encryption schemes; there's no way the OTP can be made to match the definition of an encryption scheme, thus the formal definition of IND-CPA does not apply to the OTP.

Specifically, the OTP does not fit definition 3.7 in Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography, first edition (CRC Press, 2008):

  A private-key encryption scheme is a tuple of probabilistic
  polynomial-time algorithms ($\text{Gen}$, $\text{Enc}$, $\text{Dec}$) such that: (..)

  The key-generation algorithm $\text{Gen}$ takes as input the security parameter $1^n$ and outputs a key $k$; (..)
  The encryption algorithm $\text{Enc}$ takes as input a key $k$ and a plaintext message $m\in\{0,1\}^*$, and outputs a ciphertext $c$. (..)
  The decryption algorithm $\text{Dec}$ takes as input a key $k$ and a ciphertext $c$, and outputs a message $m$. (..)

  It is required that for every $n$, every key $k$ output by $\text{Gen}(1^n)$, and every $m\in\{0,1\}^*$, it holds that $\text{Dec}_k(\text{Enc}_k(m))=m$.

where $\{0,1\}^*$ is the set of all (finite-length) binary strings.

There's no way the OTP can fit this framework:

If we try to assimilate the random pad and the key, we hit the problem that in the above definition the same $k$ can be used for several messages (and further that some messages can be larger than the key, but that's secondary); the OTP does not allow that (due to the One Time requirement of OTP).
If we try to fit the random pad into $\text{Enc}$, and still keep the ciphertext as it is in the OTP (including, of the same size as the message), then we have no way to build a working $\text{Dec}$.

Note: some practical encryption schemes use message spaces deviating from $\{0,1\}^*$, like the set of all bytestrings up to some size, or even a fixed-size bytestring, perhaps even shorter than the key (which is common in block ciphers); and it is accepted to twist the definition of an encryption scheme to allow that. However it is an essential point of any encryption scheme that the total size of plaintext enciphered with a given key is allowed to increase significantly above the size of the key; again, the OTP does not allow that.


Does knowledge of SHA256(secret ∥ known constant) in addition to SHA256(secret) give any information about the secret?

In the first case; the attacker has this knowledge

$\operatorname{SHA256}$
$x = \operatorname{SHA256}(\text{secret})$

While brute-forcing this hash value $x$, there is one problem. One cannot determine whether this is the pre-image or it is a second pre-image. For password cracking, that is not really important since you find a valid password for the target. For your case, assuming the secret has to be determined exactly, there is no way for the attacker. Actually, finding more than one break the collision property of SHA256, see in Fgrieu's answer. Therefore, it is hard to find more than one.

In the second case; the attacker has

$\operatorname{SHA256}$
$x = \operatorname{SHA256}(\text{secret})$
$\text{the known constant}$
$y = \operatorname{SHA256}(\text{secret}\mathbin\|\text{the known constant})$

This additional knowledge gives the attacker extra information that can be exploited. While brute-forcing to find the secret, this time the attacker has a new mechanism to distinguish the second pre-images from the secret. Given a secret candidate $candidate_s$ check;

$$ y = \operatorname{SHA256}(candidate_s\mathbin\|\text{the known constant})$$

Apart from the pre-image, the probability of this equality is negligible since
 we expect that SHA-256 has collision resistance.

As a result, this gives extra information about the secret that can be exploited.

Side note: if the entropy of the $secret$ is larger than 128-bit, it is not possible to execute brute-force on-the secret.


Optimal threshold for passive and perfect security

The way to extend the proof to arbitrary $t,n$ and this threshold is as follows. Assume that there exists a protocol for any $n$ parties that withstands a threshold of $t=n/2$ corrupted parties, for computing $f(x_1,\ldots,x_n)=x_1 \wedge x_{n/2+1}$. (If it withstands $t>n/2$ then it also withstands $t=n/2$, so that's fine.) I will now construct a two-party protocol for securely computing AND that is resilient to one corruption. This will contradict the known impossibility result.

The protocol works as follows. The parties simulate an execution of the $n$-party protocol. Party $P_1$ internally runs parties $P_1,\ldots,P_{n/2}$ and party $P_2$ internally runs parties $P_{n/2+1},\ldots,P_n$. Party $P_1$ puts its input as the input of $P_1$ in the $n$-party protocol, and party $P_2$ puts its input as the input of $P_{n/2+1}$ in the $n$-party protocol. The parties output whatever the multiparty protocol says to output.

In order to argue security, all you really need to notice is that if one party is corrupted then this is equivalent to $t=n/2$ in the multiparty protocol. Therefore, security is maintained.


I'm trying to understand which cryptographic algorithm is this

That would appear to be RC4, which is a well known (if not well trusted) cryptographical algorithm, original designed by Ron Rivest.

The part you quoted is the Key Setup Algorithm, which is run before you actually encrypt/decrypt anything.  The part which is written in an unusual (but correct) way is the last 5 lines, which does a swap of cdict[i] and cdict[v1] - more typically, it is written with just 2 reads and 2 writes and two temp variables in the obvious fashion; for some reason they decided to use some 'clever' logic with xors (and two temp variables, 4 reads, 3 writes).


one-pass deterministic authenticated encryption

It is impossible for a one-pass algorithm to achieve the highest nonce-reuse security notion which only leaks equality of messages because the first few bits can't depend on the last few bits.
The best one could hope for is that the length of common prefixes between any two pairs of messages is leaked on nonce-reuse. One can strengthen this to only leaking the length of common prefixes for equal-length messages by prepending the message length before encryption.

If you want to achieve this strongest one-pass security notion, you can't use a paralellizable encryption algorithm because each bit / block has to depend on all previous ones which by definition is not possible for parallelizable schemes.

As for MACs, if you use a PRF-based MAC, like AES-PMAC (which is parallelizable) or AES-CMAC you should get plenty of robustness to nonce re-use, as these are deterministic MACs to begin with.

As for encryption, all the fancy modes are out of the question and I think the best bet you have is actually CBC. This is due to the fact that CBC does block-by-block processing which reduces the accuracy of the "common prefix" to number of totally equal blocks which should prevent an adversary from using an attack that guesses a small amount of bits at once until they get a longer shared prefix to recover a message as the smallest group for this would be 128 bit.

So in total, the best option you probably have is to use (AES-)CBC-then-PRF with AES-PMAC or AES-CMAC as PRFs.


order between adversaries and type of resources given

Can we state that $Adv_{G0} \le Adv_{G_1}$ ?

Absolutely.  Let us call $S0$ the strategy that $A$ can use in game $G0$ to achieve advantage $Adv_{G0}$; we notice that $A$ can also use strategy $S0$ to achieve that exact same advantage in $G1$, and hence we see that the maximum advantage he can achieve in $G1$ must be at least as large as in $G0$

  Can we state that $Adv^{CPA} \le Adv^{CCA}$ ?

No (unless we assume that, in the CCA case, the attacker is also allowed to submit chosen plaintexts as well).

To demonstrate this, construct an encryption method that is secure, except that if the plaintext was the specific message "Open Sesame", it outputs a ciphertext that is the encryption key.

In this case, $Adv^{CPA}$ is quite large (the attacker submits two plaintexts, one "Open Sesame" and one something else, and see if the key he got from the "Open Sesame" message encrypts the other message in the ciphertext he got).

However, there is no obvious way that the attacker can use chosen ciphertexts; he knows that if he submits a ciphertext that happens to be key, he'll get the plaintext "Open Sesame"; however that doesn't help him, as there are other ways to verify a guess on the key.

Hence, in this artificial example, we have $Adv^{CPA} > Adv^{CCA}$


Design a OT-based Private Set Intersection protocol to obtain $A \cap B \cap C$?

I worry that the first problem is harder than your instructor suspects. We had to work a little hard to get a multi party PSI protocol based on efficient OT in our paper

  Practical Multi-party Private Set Intersection from Symmetric-Key Techniques,  by Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, Ni Trieu

If I remember correctly, we may have some optimizations for the 3-party case, but I don't think it falls to the level of a homework assignment.

The real challenge is that the 2-party equality test reveals the outcome of the comparison in the clear to one party. This makes it hard to hide partial intersections. For example, if $x \in A \cap B$ but $x\not\in C$, then Alice must not learn that Bob also has $x$. This suggests that Alice and Bob can't simply use the 2-party equality test on their inputs. In our paper we had to go to extra lengths to hide these intermediate equality test results.


Fast reduction in $GF(2^{128})$ using x86 `PCLMULQDQ`

Basically, to (naïvely) implement modular reduction by M = (1 << 128) + 0x87, you need to:

take the upper 128 bits $x_H$ of the 256-bit (actually, 255-bit, since the high bit can never be set) PCLMULQDQ result $x = x_H \| x_L$,
shift them down by 128 bits,
XOR-multiply them by 0x87,
XOR the result with the lower 128 bits $x_L$ of the 256-bit result, and
repeat (see note below).

Step 3 could be implemented with PCLMULQDQ, but since one of the multiplicands is a small constant, it's probably more efficient to just implement it with discrete shifts and XORs.

Note that the result of step 3 (and thus of step 4) can be longer than 128 bits — up to 6 bits longer, in this case — and may thus need to be reduced a second time.  In this second reduction, $x_H$ is at most 6 bits long (and thus the result of step 3 is at most 13 bits long), so this pass is simpler to implement, and guaranteed not to overflow and require a third pass.

(Also, if you can be sure that one of the original multiplicands is at most 122 bits long, then $x_H$ is at most 121 bits long, and so step 3 cannot overflow 128 bits.  This can simplify the implementation, and in particular, makes the second reduction pass unnecessary.)

What we're really doing here, in steps 2–4, is calculating x' = x - M * x_H, where x_H = x >> 128 and the multiplication and the subtraction are both carryless.  Of course, carryless binary subtraction is just the same as carryless binary addition, i.e. XOR.  Treating it as subtraction here generalizes better, though, and also more clearly explains why this method works: we're effectively just subtracting multiples of M from the result so as to clear the upper half of it.

I have not looked at the Intel paper linked by fgrieu in detail, but I suspect they're doing something smarter and faster than this naïve reduction.  I'll let him summarize the paper, if and when he has more time. :)


The relationship between Spritz's security and the capacity of the internal function, Shuffle, is based on the fact that any generic attack must use on the order of $2^{c/2}$ queries to Shuffle in order to have a non-negligible success probability, where $c$ is Shuffle's capacity. A generic attack does not use any details about Shuffle, meaning the attack holds if you replace Shuffle with any other function. This does not say anything about attacks against Spritz in general, and if you're able to find a special property about Shuffle which is useful for an attack, such as a more efficient description of Shuffle, then you can beat the $2^{c/2}$ minimum requirement on the amount of Shuffle queries for a successful attack.

So the fact that Shuffle can be described more compactly will not change Rivest and Schuldt's security claim since their claim only depends on Shuffle's explicit capacity. In fact, Spritz's effective security could be significantly worse than what they claim, but you'll have to find an attack against Spritz to show this.


Diffe-Helman Exchange result is always 1

For a given prime $p$, there are many choices for the generator $g$, but $g$ cannot be completely arbitrary. As the name hints, $g$ is supposed to be a generator of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ (or at least a large subgroup, more on this later), that is, it must have the property that the set of its powers modulo $p$ $\{g^1 \bmod p, g^2 \bmod p, g^3 \bmod p, \ldots, g^{p-1} \bmod p\}$ is equal to the set of elements $\{1,2,\ldots,p-1\}$.

You happened to pick $g = 47 = 2 \times 23 + 1$, thus $g \equiv 1 \pmod{p}$. The set of powers of $1$ is just $\{1\}$, so it's about as far from a generator as it gets (the only way this could be “worse” would be a number like $46 \equiv 0 \pmod{p}$ which is not in the multiplicative group at all).

With large prime numbers, there's no efficient way to find a primitive root directly, but it's easy to test whether a candidate $g$ is a generator if the factorization of $p-1$ is known. This is because if $g$ is not a generator, its order (the smallest number $k \ge 1$ such that $g^k=1$) will be a multiple of one of the prime factors of $p-1$. The Wikipedia article on primitive roots modulo (“primitive root modulo $n$” is another way to say “generator of $(\mathbb{Z}/p\mathbb{Z})^*$”) and some results on the proportion of candidates that are generators.

In fact, the $g$ parameter in Diffie-Hellman does not have to be a generator of the whole group in order for the protocol to work, in the sense that Alice and Bob end up with the same shared key. In fact, even in your example with $g=1$, the protocol “works”, but it has no security. For security, what matters is that $g$ generates a “large” enough subgroup of $(\mathbb{Z}/p\mathbb{Z})^*$, where “large” means that the order of $g$ (i.e. the smallest $k \ge 1$ such that $g^k \equiv 1 \pmod{p}$) is a multiple of a large prime.

There are several techniques for generating Diffie-Hellman parameters. Typically $p$ is chosen in such a way that a good generator can be chosen easily. A small generator is prefered for a minor performance improvement. There are bad values of $g$ that can lead to practical attacks but it is easy to avoid them. An additional subtlety is that if the order of $g$ has a small prime factor (which is the case if $g$ generates the whole of $(\mathbb{Z}/p\mathbb{Z})^*$, since its order $p-1$ is then a multiple of $2$), there is a practical attack to find one bit of the shared secret, so choosing $g$ such that its order is a large prime is recommended.

Usually, $p$ and $g$ are chosen long in advance; many protocols or applications use built-in constants for $p$ and $g$, or have just a few of them to span different key sizes. There's no need to vary $p$ or $g$ for security, they can be reused.


Choosing between additive or multiplicative group for Diffie-Hellman

From an abstract algebraic point of view the two are one and the same, a group.

However, depending on how that group is defined additional structure may make additional operations possible or easy that are detrimental to your security.

For example:
In a finite field of prime order calculating logarithms is hard but division is easy.

More mathematically the two problems are

calculating $x$ given $g$ and $g^x$
calculating $x'$ given $g$ and $x' \cdot g$

and they have totally different complexities.

Both addition and multiplication in this case define a group but integer multiplication is not hard to invert.

And, the usual disclaimer, please don't design your own crypto unless for exercises. ;)


Is a large random number cryptographically equivalent to the product of multiple smaller ones?

If you choose a number uniformly at random in the range $[0, 31]$, that's $32$ distinct values and thus $log_2(32) = 5$ bits of entropy.  If you choose $8$ such numbers, then you have $5 \times 8 = 40$ bits of entropy total, meaning that there are $2^{40}$ distinct combinations you could get.  It doesn't matter how you combine them, that's already far short of $2^{256}$.

And it gets worse, because you're multiplying numbers that you compute from your eight choices:

  $$\mathit{rand} = 2^{r_1}\cdot 2^{r_2}\cdot 2^{r_3}\cdot 2^{r_4}\cdot 2^{r_5}\cdot 2^{r_6}\cdot 2^{r_7}\cdot 2^{r_8} $$

Since multiplication is commutative ($a \times b = b \times a$) and associative ($a \times (b \times c) = (a \times b) \times c$), it means that many combinations among those $2^{40}$ distinct choices actually yield the same product after the multiplication.  E.g., if two sequences of random choices are permutations of each other their product is the same. In this case, it is even worse, since $\mathit{rand}=2^{r_1+\dots+r_8}$ is always a power of two: This means we are effectively sampling a $256$-bit number that has exactly one bit set, so there's only $256=2^8$ possible outcomes!

  If not, then how to do it, how to generate big random number by combining it from smaller ones?

Basically, by choosing digits at random in some base.  If you have $n$ randomly drawn digits $d_0, ..., d_{n-1}$ in base $b$, then $d_0b^0 + ... + d_{n-1}b^{n-1}$ is a uniform random number in the range $[0, b^n)$.  For example, to generate a 256-bit number at random, you could:

Choose 256 individual bits at random ($n = 256$, $b = 2$);
Choose 32 bytes at random ($n = 32$, $b = 8$);
Choose eight 32-bit machines words at random ($n = 8$, $b = 32$);
Choose four 64-bit machines words at random ($n = 4$, $b = 64$).

In practice, this is done by just concatenating randomly chosen bytes or machine words.


one-way deterministic hash for low entropy input?

I don't think this problem is solvable as specified.

With a small message space, and deterministic hashing (or encryption), a generic attack involves exhaustively searching all likely messages to find one that corresponds to the known hash / ciphertext.

If all of the digits of the ID numbers were random, an exhaustive search would require about $10^{10} \approx 2^{33}$ iterations, and it might be feasible to use key stretching and/or rate-limited hardware to slow down the hashing enough to make such a search unfeasible.

Unfortunately, you say that some of the digits encode a date.  If these ID numbers are anything like the local government IDs around here, I'm assuming something like 6 digits encoding a birthdate (in DDMMYY format, or similar) plus a four-digit sequence number.  This reduces the necessary search space significantly:

Just the date format reduces the search space a lot: since there are only 356 valid dates in a year (or 366 for leap years), the actual number of valid IDs is only about $10^{8.4} \approx 2^{28}$.
If an attacker is targeting a specific person, they'll likely know the target's age to at least within a decade or so.  This cuts the search space further down by a factor of (at least) 10.
In the worst case, the attacker already knows the target's age and birth date, and only needs to determine the last four digits of the ID.  Thus, they only need to search $10^4 \approx 2^{13}$ ID numbers!
To make things even worse, the last four digits might not be random either.  If they're instead assigned sequentially, lower numbers will be much more common, and so a sequential exhaustive search is likely to find the correct ID much sooner than one would expect if they were randomized.

Basically, in the worst-case scenario described above (which, really, isn't that far-fetched at all), no amount of key stretching will help: if your organization wants to be able to legitimately process more than one ID per minute, then a determined attacker with access to the same resources (which is a reasonable assumption, if internal attacks are a concern) and knowledge of the date part of the ID will be able to de-hash the ID in less than one week (= 10,080 minutes).  If you need to be able to process one ID per second, the attacker only needs up to three hours.  That holds regardless of the hashing or encryption method you're using, or the tools you use to implement it.


Does it matter if I append the secret to the salt or pass it in separately?

What you have been doing is unconventional, but is cryptographically safe, and should be fine as long as the implementation of pbkdf2-hmac-sha256 is correct. Things to watch out:

is all the stuff (characters?) in password and salt safely kept by whatever ++ is?
is this secret then converted to octets without entropy loss on entry of pbkdf2-hmac-sha256 ? Changing anything non-ASCII to ? is a goof that has crept; combined with use of a foreign language, overly paranoid user, or an endianness problem, that could degenerate to the length of the secret being the only entropy left! Another issue that can creep is stopping at the first zero octet in secret.
Does the pbkdf2-hmac-sha256 implementation correctly handle the case when secret, converted to octets, exceeds 64 octets? The action pbkdf2-hmac-sha256 should perform in this case is to replace these octets with their 32-octet SHA-256 hash.

Given this, the worst I can think the unconventional use of pbkdf2-hmac-sha256could cause is that timing execution could leak the length of password in an easier manner, but that's a non-issue.

Before that comment, I knew no language where 100_000 is a valid constant. More importantly, a hundred thousands is an insufficient iteration count nowadays for PBKDF2-HMAC-SHA-256, a short memorable password, and protecting a key from exhaustive search. Modern password-based key derivation functions make use of memory, sometime multiple execution threads, to greatly increase their effectiveness at a given execution time or cost, e.g. scrypt, Argon2, Balloon.

Note: implementing the core of PBKDF2-HMAC-SHA-256 in something that ultimately is interpreted rather than somewhat compiled would be a huge (but not rare) design mistake, since it would force using a lower iteration count than would be otherwise possible.


Constant time multiplicative inverse within a word

You can compute $f(x) = x^{\phi(p)-1} \bmod p$ in constant time, using $O(\log p)$ constant time modular multiplies.  If $p$ is prime, this reduces to $f(x) = x^{p-2} \bmod p$

BTW: calling it 'Knuth's' algorithm is, in general, not very helpful; Knuth gives hundreds of different algorithms in 'The Art of Computer Programming'.  I assume you mean the Extended Euclidean algorithm?


Laplace Mechanism Proof: Why this product operator?

The definition of Laplace Mechanism:
$$
\mathcal{M}_L(x, f(\cdot), \varepsilon) = f(x) + (Y_1,\ldots,Y_k)
$$
Once each $Y_i \sim Lap(\Delta f/\varepsilon)$ they are indepedent of each other. So we can calcule the joint probability of them using the product of marginals.

As we know $p_x = \mathcal{M}_L(x,f,\varepsilon)$ and $z \in \mathbb{R}^k$, thus is possible to do:

$$
p_x(z) = \frac{\varepsilon}{2\Delta f} exp\left(-\frac{\varepsilon |f(x) - z|}{\Delta f}\right) = \prod_{i=1}^k \frac{\varepsilon}{2\Delta f} exp\left(-\frac{\varepsilon |f(x)_i - z_i|}{\Delta f}\right)
$$

I think that is the answer.


Here's the next step in the iteration, which should be easy to understand:
Let's call the oracle on 2P and 4P:

Answer (even,even) means, that $P<N/4$ (this is still easy: Otherwise either 2P or 4P would be greater than N).
(even,odd) means $N/4\le P<N/2$.
(odd,even) means $N/2\le P<3N/4$
(odd,odd) means $3/4N\le P<N$.

If you continue with multiplying the factor for P with 2, you get the next round of iteration, where "odd" indicates the upper half of the interval and "even" indicates the lower half.


Is using a broken SHA-1 for password hashing secure?

SHA-1 in itself was never safe for password hashing. The hash algorithm itself doesn't have a work factor parameter nor does it have a salt as input. These are requirements for run-of-the-mill passwords that do not have as much security as a good symmetric key.

For this reason password hash algorithms have been invented, also known as password based key derivation functions (PBKDF). The difference between a password hash and a PBKDF is mainly how the result is used: directly as a password hash to compare with a stored password hash or as symmetric key for input in a symmetric cipher or MAC algorithm.

Well known password hash algorithms are PBKDF2, bcrypt, scrypt and of course the already mentioned Argon2. The latter two also contain options for configuring memory hardness, to overcome hardware based attacks.

The above functions can often be configured using a hash function. For instance PBKDF2 requires a secure hash as configuration parameter, and it (kinda) defaults to SHA-1.

As long as SHA-1 doesn't have direct collisions it could still be secure for this purpose. Even if there were collisions, it is unlikely that this would compromise the security of a password database.

Due to the high number of iterations it is even less likely that a password hash is reversed, i.e. that the one-way property of the total hash doesn't hold. This property is of course the most important one for the password hash.

For this reason it's probably OK to keep SHA-1 as configuration parameter for some specific password hash algorithms that require it.

However attacks just get better, never worse. So if possible, even in the above scenario, you should move away from SHA-1 to SHA-2/SHA-3. Or choose a password hash function that doesn't rely on a secure hash at all.


Each CA has their own revocation list. When your device validates a certificate, it determines what CA was used to sign it, downloads the CRL (whose URL is included in the CA certificate) and checks if the serial number of the certificate is included in it.

Since all certificates have expiration dates, then any certificate in a CRL can be removed from the CRL when it expires. This prevents the CRL from growing forever.

That being said, CRL aren't used anymore by many clients, which now rely on other mechanisms like OCSP stapling.


SHA is related to AES in that they are both US government standards. They are not similar algorithmically.

SHA and AES are cryptographic primitives, TLS is a protocol. As the name describes SHA is a family of hash algorithms. AES is a block cipher. TLS uses many encryption algorithms, including AES in various modes, and several hash algorithms, including those in the SHA family. TLS may also use encryption algorithms not based on a block cipher, such as RC4.

TLS uses hash algorithms in order to provide message authenticity when the encryption algorithm does not provide authenticated encryption, via HMAC. SHA may also be used during client-server key exchange to compute the shared master secret, as a component of some PRF, generally also HMAC. TLS encrypts passwords in transit between client and server using the selected encryption algorithm, which could be AES.

SHA is also used in server certificates in order to verify their authenticity so a TLS connection is not created to an imposter. Verification is apparently not implemented well in a wide variety of systems.

I would suggest reading RFC 5246 in order to get a better idea of how TLS operates.


Origin of the SHA-224 initial hash value?

The SHA-224 initial values are the second 32 bits of the fractional parts of the square roots of the 9th through 16th primes (namely, 23 through 53), or in other words, $\lfloor 2^{64} \sqrt{p} \rfloor \bmod 2^{32}$, for $p = 23, 29, 31, 37, 41, 43, 51, 53$

For example, the hex expansion of $\lfloor 2^{64} \sqrt{23} \rfloor = 4cbbb9d5dc1059ed8_{16}$, and so the initial value for $a$ is the last 8 hex digits,  namely $c1059ed8_{16}$

Similarly, the hex expansion of $\lfloor 2^{64} \sqrt{29} \rfloor = 5629a292a367cd507_{16}$, and so the initial value for $b$ is $367cd507_{16}$

Note that the SHA-224 initial values are the lower 32 bits of the SHA-384 initial values (!).


Memory hard key derivation (password hash) using AES encryption

Your key derivation function is not particularly memory hard.

The second loop walks the array in order, so an optimized implementation which an attacker would use can avoid the whole array, keeping only some elements in memory at a time.

For example, you can halve the memory use by only storing the second half of M initially. Then for the first N/2 iterations of the loop you only need to calculate the i'th element from the i-1'th. Then you would recalculate the first half of M instead and continue as earlier. You need about twice the computation for half the memory use, and can extend the tradeoff further. This is much worse (better for the attacker) than scrypt's tradeoffs.

If you use a salt length longer than 512 bits, the attacker can reduce the size of M[i] by only storing the hash value at that iteration during the first loop. They can then derive the whole value when needed in the result loop because it only depends on the hash and salt. This means a memory savings factor of salt length/512 bits for a computational overhead of less than 3x (since they need to recompute the AES twice in the second loop, but none of the hashing needs to be repeated).

There is probably a way to fix these, but the main issue is that you are rolling your own algorithm. Normally algorithms need to face years of cryptanalysis before they are trusted, at least unless they have a security proof reducing them to something already known/believed to be secure.

Instead, you should if at all possible use an existing algorithm, preferably an existing implementation because there are things that can go wrong implementing one yourself. If you want memory hardness, scrypt is the most accepted and widely available algorithm (tradeoffs exist, but they are expensive), though Argon2 which recently won a competition for password hashing algorithms might be an option soon (you will not find implementations for most languages yet).


The inverse DCT is used to decompress the image, but you do not have to decompress the image.  If you decompress the image, I suppose that you also compress it again for reading the DCT coefficients, and as far as JPEG is a lossy format, some DCT coefficients could change their value.

But JPEG does not work in this way. In JPEG the DCT coefficients are compressed and saved into the file. It is the visualization tool that decompresses the image to show it to the user.


Equivalent security of KMAC and different HMAC instances?

Yep, this is confusing indeed!  I think you're misreading SP 800-107.  If we go back a little bit from the part you refer to, to section 5.3.1, we have this (p. 13):

  The security strength provided by the HMAC algorithm depends on the security strength of the HMAC key, the underlying hash algorithm and the length of the MacTag.

Now, you've focused on section 5.3.4 ("Security Effect of the HMAC Key", my boldface), which says (p. 14, my boldface again):

  The effective security strength of the HMAC key is the minimum of the security strength of $K$ and the value of $2C$.

Reading this in the context of the first quote I provided, I think that this section is saying that if you use HMAC-SHA-512 with a 1024-bit key, then the effort for a key recovery attack is $2^{1024}$.  But there are other attacks on HMAC-SHA-512 than key recovery.  Since the output length is 512 bits, you can always generically forge a (message, tag) pair in $2^{512}$ attempts with guaranteed success.

So even though HMAC-SHA-512 supports a "security key strength" of up to 1024 bits, the output length always allows a cheaper attack than that.

I'm still confused by section 8.4 of the SP 800-185 draft, though.  They talk about the effects of key size and tag length on the security of KMAC, but they just don't explain how the capacity affects the security.  Earlier in section 4.1 (p. 10) they say this:

  [KMAC128 and KMAC256] differ somewhat in their technical security properties. Nonetheless, for most applications, both variants can support any security level up to 256 bits of security, provided that a long enough key is used, as discussed in Sec. 8.4.1 below.

So apparently the 256-bit capacity of KMAC128 doesn't always translate to a 128-bit cap on its security level.  But on the other hand this text would seem to imply that neither can support security levels above 256 bits, where HMAC-SHA-512 does, and then the equivalence table you point out would be false. (Not that it matters practically, of course—$2^{256}$ is a notably large number.)

The other source that might hold some answers is Bertoni et al's "Cryptographic Sponge Functions" paper, which discusses generic attacks against keyed modes of sponge functions (section 5.1, pp. 50ff).

Now, I'm not going to pretend I understand this one, but I'll highlight the bits that jumped out at me.  Section 5.11.2 (p. 51):

  As in the case of stream ciphers, the adversary can attempt state recovery [of the MAC] using tags. In total she needs at least $b$ bits of output to fully determine the state.

Here $b$ is the width of the sponge construction's transformation—in the case of Keccak, this is 1600 bits, which is longer than the 512 bit output size for the HMAC-SHA-512 replacement suggested in the draft.  Does this mean that the state recovery attacks are impossible, or that they become much more difficult?

They also mention in the same paragraph that if the tag length $n$ is smaller than the sponge's bitrate $r$, the state recovery attack's difficulty is unrelated to the capacity, $2^{b - n}/(m - 1)$ instead of $2^c / (m - 1)$.  In the case of KMAC256, the bitrate is 1088, which is larger than 512.

But they do also mention attacks whose effort is related to the capacity $c$ on p. 52.


How can two different passphrases unlock the same content?

Another method to the ones described above would be ID-based encryption where a trusted third party, called the Private Key Generator (PKG), generates the corresponding private key based on the user's identity (whether it be domain name or email address).

Given the master public key, any party can compute a public key corresponding to the identity ID by combining the master public key with the identity value. To obtain a corresponding private key, the party authorized to use the identity ID contacts the PKG, which uses the master private key to generate the private key for identity ID.  If only part of the master private key is used to generate the corresponding private key, then the PKG can generate two private keys by using different parts of the master key.  That way, the user will have one private key, and management the other.

Whether or not this is secure depends on how much you trust the third party PKG.

For further information, have a look at the following link.

ID Based Encryption

Also have a look at the following article:

Identity-Based Encryption from the Weil Pair

If you do a search on the title, you should be able to find the associated PDF.


Creating serial key generator using ECDSA, how to get signature short enough?

Restricting to Elliptic Curve Digital Signature Algorithm and curves as in FIPS 186-4 appendix D:

an $m$-bit curve, that is one over field $GF(2^m)$ with $m$ prime, or over field $GF(p)$ with $\log_2(p)\approx m$ and $p$ prime (and possibly of some special form), allows schemes with $m/2$-bit security (at most, but for well-chosen curves we can largely ignore that as far a we know).
Challenges at the level $m=109$ have been publicly solved circa 2002. I'm not aware of security authorities ever vetting anything less than $m=163$ for any use, but it is technically sound to use $\log_2(p)\approx128$ as in curve secp128k1 for copy-protection (which can likely be broken by other ways than forging a signature).
An ECDSA signature normally contains two components $r$ and $s$ of $m$ bits each (ignoring the overheads of ASN.1 formatting).
It is possible to trim a few bits (say $e=8$) by omitting them from the signature, and compensating for their lack by repeating the signature generation process (with a new random seed) until hitting a signature where these $e$ bits are all zero. That increases the cost of signature generation by a factor of $2^e$ on average, which for small $e$ is often acceptable when a predictable maximum signature generation time is not essential (the distribution of the signature generation time becomes geometric/exponential; the number of attempts to generate a batch of signatures remains quite predictable). There is no loss of security except possibly from side-channel attacks (that we know; for extra confidence we can make the trimmed bits a hash of the others, rather than zero).
It is possible to trim a few more bits (say $f=8$) again by omitting them from the signature, and compensating for their lack by repeating the signature verification process, enumerating the $2^f$ possible values of the missing bits, until a valid signature is found. That increases the cost of signature verification by a factor of at most $2^f$, which for small $f$ is often acceptable (verification time has predictable maximum, and uniform distribution). There is no practical loss of security (private key recovery from the public key still remains the best known mean to forge a signature).
If a signature is keyed-in (rather than copy-pasted), one wants to re-encode the corresponding bitstring as symbols chosen to minimize the risk that a keying mistake renders the signature invalid. The problem is different depending on if you have control of the font used to render the string keyed-in, or not. In the later (worst) case, as a courtesy to the user, we should restrict to decimal digits and roman letters without accents, ignoring case, grouping symbols into equivalence classes based on visual similarity, such as $\{\text{0},\text{O},\text{o}\}\;$, $\{\text{1},\text{l},\text{I},\text{i},\text{L}\}\;$, $\{\text{2},\text{Z},\text{z}\}\;$, $\{\text{3}\}\;$, $\{\text{4}\}\;$, $\{\text{5},\text{S},\text{s}\}\;$,... We end up with perhaps $n\approx28$ of these classes, which could be stretched to $n=32=2^5$ with some extras like $\{\text{-},\text{_}\}\;$ and $\{\text{+}\}\;$ (when $n$ is a power of two, the re-encoding is slightly simplified).

Thus $\lceil(2m-e-f)/\log_2(n)\rceil$ symbols among $n$ allow to encode a signature if we are willing to spent the effort to try an average of $2^e$ signatures for generation and a maximum of $2^f$ for verification.

For secp128k1, 7RPGE 10GVH KX7P1 KPMG8 RABKY 25QWX 9DKHM 35J3H D4DM2 M12MF could be a signature coded as $50$ symbols among $n=28$, $e=9.64$ (an average of 794 signatures computed for each acceptable one) and $f=6$ (64 attempts before concluding that a signature is invalid).

An extra complication of the signature generator is that it might be required to avoid signatures containing politically incorrect text, but it will only moderately complicate the generation.


RFC 4493 (AES-CMAC) algorithm with 256 bit key

AES has 128, 192, and 256 bits key sizes and always 128-bit block size. They are usually written as AES128, AES192, and AES256. The block size is implicit since it is always 128.

The basic function xor_128 is used to support x-or operation of CBC-MAC for the message block, ciphertext blocks, and keys. The block size is always 128 regardless of the key size.

The rfc4493 is not mentioning the AES192 or AES256. This doesn't mean that one cannot use any other than AES128. The rfc4493 only provides a test code for AES128.

The NIST provides test vectors in NIST:  Block Cipher Modes of Operation - CMAC Mode for Authentication for AES128, AES192, and AES256.

The Generate_Subkey algorithm also needs the xor-128 to derive the keys, since the keys are xored with the blocks. This can be seen from the code

  Step 4.  if flag is true
           then M_last := M_n XOR K1;
           else M_last := padding(M_n) XOR K2;

The constants are the same and the standard can be found in  NIST 800-38B: Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication


Von Neumann Extractor - Which bit is retained?

It doesn't matter at all, since both $01$ and $10$ have the same probability $p(1-p).$


How secure is a system that retrieves encrypted private keys from a public database?

A user's private keys are encrypted using the user's password, and stored in a publicly accessible database.

A publicly accessible database like this can be easily corrupted through an offline dictionary attack because passwords often have very low entropy. This can be improved (but still hackable) by adding salts (that are also stored in the public database). This post introduces how to use salts to protect passwords: Can you help me understand what a cryptographic “salt” is?

On the other hand, I don't think encrypting a client's private keys with different keys (derived from the same password) help here because an adversary can easily crack all the derived keys if it finds the correct password.


I am afraid there are no efficient methods of knowing the padding methods deployed unless it is specifically provided by description from whomever authored the original codes. You have to try bruteforcing the padding scheme to estimate what  padding schemes are used.


What does AES round reduce in attacks mean?

The proper statement is usually something like "we demonstrate an attack on 6 rounds of AES of such and such complexity".

Standard 128 bit key length AES is an iteration of 10 rounds, each round uses a round key derived from the randomly chosen AES key and is made up of AddRoundKey, SubBytes, ShiftRows, MixColumns operations.

If AES is run for less than 10, say 6 rounds, it is obviously weaker. So this means the demonstrated attack would fail (typically would require more computational effort than a brute force search for the key) if more rounds were added, and thus the given attack can't break the full cipher.

Such reduced round attacks are still of interest on strong ciphers like the AES since they tell us that some partial cryptanalytic progress has been made.

Edit: There is an attack on the full 10 round 128 bit key length AES with complexity $2^{126.1}$ by Bogdanov et al, where the authors state "In contrast to most shortcut attacks on AES variants, we do not need to assume any related-keys. Most of our attacks only need a very small part of the codebook and have small memory requirements, and are practically verified to a large extent. As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way."


Finding p and q in RSA with a given n, |p-q|<10000

As @fgrieu said, it will work when ${|p-q|< N^{1/4}}$ , where ${\sqrt N}$ and ${A}$ both are very nearer. then we can take ${A = \sqrt N}$ to start with.

Let ${A=(p+q)/2}$ , i.e., A is mid point of p and q, which could be nearer to ${\sqrt N}$

There exist an integer ${x}$ so that, ${A-x=p}$ and ${A+x=q}$

${N=pq}$ ${=}$ ${(A-x)(A+x)=A^2-x^2}$

${x= \sqrt{A^2-N}}$

Since we know A and N we can find x and subsequently p and q.


How many bits of entropy are leaked for every derived password from a master?

From an information-theoretic perspective, and with an ideal password hash function,  with $k=68$ possibilities for each character of derived password, each such character leaks about $\log_2(k)\approx6.1$ bit, but only as long as that remains significantly lower than the entropy in the master password. That's a leak of about $73$ bit per derived password. With $130$ bit of entropy in master password, the entropy leak would be about $73$ bit for one derived password, and just shy of $130$ bit for more.

The example password hello stack exchange good to see you is meaningful English text, uniformly-cased, properly-spaced, without digits or punctuation, with 30 non-space characters. It is doubtful that it is representative of passwords with 130-bit entropy; I'd guesstimate 40 to 90 bit, and would not be surprised if almost no entropy remained after one derived password; or/and if that password was by far the simplest for an english speaker (thus most likely) matching a single domain / derived password pair.

However, assuming that PBKDF2-HMAC-SHA512 is unbroken (as it stands), a complete entropy leak is not enough to find the master password (or a derived password for another site) for a compute-bound adversary, as real adversaries are. The entropy computation is useful only to tell how many derived passwords are necessary to carry an attack (here, two are most likely enough, and one might be enough). The best attack remains trying all the possible master passwords, from most likely to least, against one derived password hash (which will weed out most candidate master passwords), then a second selectively in case of success.

With enough derived passwords, the expected difficulty of attack is mostly dependent on the entropy in the master password, and the parametrization of PBKDF2 (which is untold): $2^n$ iterations stretch the entropy in the master password by about $n$ extra bits.

From an information-theoretic perspective, if the master password is chosen in a finite set with probability $p_i$ for each master password and $1=\sum p_i$, it initially has entropy $H=\sum(p_i\log_2(1/p_i))$. When a derived password for a known site (or a symbol of that) gets known, that makes some master passwords impossible, some probabilities $p_i$ go to zero (and are removed from the sum) and the others are increased to $p'_i$ in proportion, so that $1=\sum p'_i$ still holds. The entropy leak is the difference between initial and residual entropy.

In other words, the entropy leak is
$$\sum_\text{all MPs}p_i\left(\log_2{1\over p_i}\right)\ -\ \sum_\text{remaining MPs}\left({p_i\over\displaystyle\sum_\text{remaining MPs}p_i}\log_2{\displaystyle\sum_\text{remaining MPs}p_i\over p_i}\right)$$

When only one master password remains possible, only the left sum remains, and the entropy leak is that of the master password.

If all master passwords are equally likely, the entropy leak is the base-2 logarithm of the ratio of the number of initially possible master passwords, to the remaining number of possible master passwords. When only one master password remains possible, the entropy leak is the base-2 log of the number of all initially possible master passwords.

Assuming the derivation function is a Pseudo Random Function, knowing one of its output (or a symbol thereof) will rule out passwords irrespective of their initial probability. With each output symbol about uniformly distributed among $k$, it can be shown that the entropy leak for $s$ revealed symbol is expected to be almost $s\log_2(k)$ if that's much less than the initial entropy; and is expected to be almost all the entropy in the initial password if $s\log_2(k)$ is much larger.


The problem with questions that ask for “the fastest” is, that such questions always raise the counter-question: compared to what exactly? Also, your question doesn’t specify if you mean cryptographically secure physical random number generators, or any physical random number generator.

Anyway… 400 Mbps doesn’t really come anywhere near the word “fastest”.

If you take a look at “An optical ultrafast random bit generator”, which was published in Nature Photonics (Volume 4, Issue 1, pp. 58–61) by Kanter et al in 2010, you’ll see that their physical random bit generator operated at a rate of 300 gigabits per second. I’ld say that somewhat fits the word “faster”.

Besides that, you’ll most certainly also will want to check out “Real time demonstration of high bitrate quantum random number generation with coherent laser light”, published by Symul at al (ANU, Appl. Phys,. Lett. 98, 231103) in 2011.
In short: researchers at the Australian National University are generating true random numbers from a physical quantum source.

Currently (meaning: at the time of writing this answer), their Quantum Random Number Generator seems to be the best fit for the word “fastest”.

To learn more about the QRNG, you could either start by reading this ScienceDaily article,  or you can skip that and directly visit the “ANU Quantum Optics – Quantum Random Number Generator” webpage.

An aside: as others already hinted  at in their comments ⁽¹⁾ ⁽²⁾, even simpler RNGs already tend to break the 400 Mbps mark.


Encrypting messages for multiple recipients

Yes, this is possible. The most natural option is to look at identity-based encryption (I point to the wikipedia page, as it gather some links to various schemes), such as the Boneh-Franklin IBE. An IBE allows to encrypt a message with the identity of the user. After interacting with some trusted authority once in a setup phase, each user can receive the secret key associated to this identity, and decrypt all messages encrypted for their identity. The owner of the master secret key (which is used to derive identity-based secret keys) can decrypt all messages, for any identity. Your intuition about looking into attribute-based encryption is essentially correct, as IBE is a special case of attribute-based encryption.
In fact, you do not need the full power of IBE here, so there is an alternative possibility. The exact feature that you are looking for is enjoyed by the Bresson-Catalano-Pointcheval cryptosystem. Close variants of this scheme were invented simultaneously the same year, by Damgа̊rd and Jurik, and by Cramer and Shoup. It allows to perform the following operation:

Generate a pair (master public key, master secret key) $= (\mathsf{mpk},\mathsf{msk})$
Given the master public key $\mathsf{mpk}$, any user $P_i$ can generate a pair public key / secret key $(\mathsf{pk}_i,\mathsf{sk}_i)$
A message encrypted with $\mathsf{pk}_i$ can be decrypted either with the corresponding secret key $\mathsf{sk}_i$, or with the master secret key $\mathsf{msk}$.

Note that unlike IBE, you cannot simply encrypt using the identity of a user in this system. However, generating a pair $(\mathsf{pk}_i,\mathsf{sk}_i)$ can be done by any user, using only the master public key (while in IBE, the mastersecret key is needed to derive the secret key associated to an identity), so you do not need to have a trusted authority at this step. This might make this scheme more suited than IBE for your exact application.
If you are familiar with the Paillier cryptosystem and the ElGamal cryptosystem (otherwise, ignore what follows), the idea of the scheme is quite natural: a ciphertext is of the form $(g^r \bmod n^2,(1+n)^mh^r \bmod n^2)$, where $n$ is a product of two safe prime, and $(g,h)$ is some specific public key. Given the factorization of $n$, one can decrypt this ciphertext exactly as a Paillier ciphertext, by ignoring the first part of the ciphertext (the second part is exactly a Paillier ciphertext). Alternatively, given $s$ such that $h = g^s$, the ciphertext can be decrypted with a standard ElGamal decryption.


How hard to break a cipher if it has a different key for each word?

A Vigenère cypher can be unbreakable if, and only if:

the key is random,
the key is at least as long as the message being encrypted
the key is used only once.

In that case a Vigenère cypher is mathematically equivalent to a One Time Pad, and the same mathematical proof of unbreakability applies.

You proposal is closer to being unbreakable than standard Vigenère, but it is not an OTP either.  Hence your proposal is not unbreakable, but is more difficult to break than a standard Vigenère.


Cryptographically strong pseudo-random seq. generators

With the problem as initially stated (that is x = 1000, y = 100000, n = 128), the main weakness is that knowledge of the 873th to 1000th bits of the sequence is enough to trivially determine its 1001th to 100000th bits. That's because these 873th to 1000th bits are both part of the output and used as seed for the rest of the sequence.

Update: In order to test if a sequence is produced by the stated generator, or uniformly random, a judge/adversary/distinguisher

asks for one sample sequence R;
extracts the first 1000 bits, giving S;
repeat 99 times: seed PRSG with the last 128 bits of S, generate 1000 bits, and append them to S;
announce that R was produced by the stated generator if S equals R (otherwise announces that R was random).

In theory, the judge has odds $2^{-99000}$ of announcing that a sequence was produced by the stated generator when it was uniformly random (and never errs in the other direction). If the judge had enough computing power for an average $2^{127}$ PRSG, he could further reduce these ridiculously low odds to about $2^{-99872}$ (or even lower if the PRSG is extremely poor) by brute-forcing the initial 128-bit seed.


Distinguishing Original VS Fake Products

This problem is well defined for supply chain management, and generally you use a challenge-response.  In RFID, you an use asymmetric or symmetric schemes to verify that a product is authentic.  I give RFID as an example because you should be able find a lot of documentation on them.

In the asymmetric case:

A authentic product public key is on the interrogator and the product sends a unique id  (UID).
The interrogator responds with the created signature
The product sends it's signature

In the symmetric case:

The product sends a UID to the interrogator
The interrogator sends a challenge to the product
The product sends a response.

The asymmetric case allows you verify the authenticity of a class of product without a network to know the key for each device.  The symmetric case requires some method to get the key to the interrogator to verify the response because usually the key and the challenge verification are on a server somewhere.

Grab any notes on verifying a supply chain and these schemes will be described in detail.

Update:  An example from NXP.


Is the idea of a known plaintext attack really that new?

No, the idea is much older. Don't trust the movie too far, Turing actually searched for the word "eins" (one) because it was the most common number used. Far more likely to appear than "Heil Hitler" but it doesn't make good screen drama.


What is the most paranoid way to exchange messages?

RSA is slow to get a decent security... AKA 2048-bit or more.

Well, if you want to be ultra-paranoid, then you'll have to accept some trade-offs.  Suffice to say, a one-time 2048-bit RSA key-exchange shouldn't eat up too much processing time.

Using SSL is the most reliable way to exchange information securely; it not only takes care of the key-exchange and message encryption, but also message authentication (ie, man-in-the-middle attacks).

I don't think you should be concerned about AES being 'broken', but if you really want to be ultra-paranoid, you might take a look at using Serpent - it was the runner-up to Rijndael (AES) in the AES contest, with many people considering it more secure, but slower.

  "Serpent was widely viewed as taking a more conservative approach to security than the other AES finalists, opting for a larger security margin: the designers deemed 16 rounds to be sufficient against known types of attack, but specified 32 rounds as insurance against future discoveries in cryptanalysis."


How are the AES inverse S-Boxes calculated?

You performed the matrix component of the affine tranformation correctly, what you did wrong was the addition of the vector prior to field inversion.

The value 10100010 (0xA2) is the correct result of the inverse affine matrix. The final vector of the inverse affine transform however is 00000101 (0x05).

The resultant 0xA7 is then inverted, which is 0x48, the correct inverse s-box value.


My use case would be something like hashing data with less than 128 bit, but I absolutely cannot spare another 128 bit space to store the hash. I would be able to store maybe a 32 bit hash, if even that.

If you have any kind of security in mind, $32$ bit are definately not enough. Even $128$ bit is not enough today if you need collision resistance due to the birthday paradox.

With just $32$ bit output, everyone can find a preimage on the most basic computer within a very short time (seconds maybe) by just trying out enough possible inputs.

  if it's possible to have a hash whose length is inferior to the data length and still avoid hash collisions"?

I think there is a misunderstanding in the properties of a cryptographic hash function. My first suggestion would be to study the properties collision resistance and preimage resistance in detail (the wiki-link above is a useful starting point). As you can see, the length of the input is not mentioned at all - it does not matter for the security. What is stated is:

It should be hard to find any $m_1,m_2$, such that $h(m_1) = h(m_2), m_1 \neq m_2$ (collision resistance)
Given $h$, it should be hard to find any $m$, s.t. $h(m) = h$ ((first) pre-image resistance)

It is not about:

if collisions are possible (because they always are - that is given by the fact that the input is of arbitrary length)
special treatment of certain lengths for the property in general (including shorter/longer than the input)
any kind of brute force: If you have just two possible messages and know $h(m)$, then it's easy to test just both and see which message was the preimage.

And then, it's important to get a rough idea what is actually feasable in tdoay's world and what is not. A full search over $2^{32}$ bit is easy. A full search over $2^{64}$ is practically possible but far beyond what you can do on a single computer (e.g. that's roughly the number of hashes of the entire bitcoin network in $3.7$ seconds), $2^{128}$ is practically impossible ($2^{100}$ hashes would take the bitcoin network already around $8000$ years at its current rate - $2^{128}$ is around a quarter million times longer).


Concept of "guessed ID" in Authenticated Identity-Based Encryption

"Guessed ID" means ID that the oracle guesses the attacker algorithm $A$ will attack.


Is EC integrated encryption scheme used in practice?

Yes, ECIES is used in practice. That's the simplest way (thus arguably the best) to establish a key or/and encipher using Elliptic Curve Cryptography in contexts including unidirectional data transfer, or data-at-rest like backup with encryption under public key.

As an illustration, it is often listed in the Other algorithms section of FIPS-140-validated cryptographic devices; I count like 28 occurrences.

ECIES is in the de-facto standard SEC 1, IEEE Std 1363a-2004, and ANSI X9.63-2011. It is used e.g. in Intelligent Transport Systems as specified by ETSI TS 103 097. The similar ECIES-KEM is in ISO/IEC 18033-2:2006 following a well-documented proposal by Victor Shoup.


In an adaptive chosen plaintext attack, the adversary is given the opportunity to query an oracle for encryptions of messages of the attacker choice.  In a CPA attack against CBC, for each query the oracle chooses a fresh IV at random, CBC-encrypts the adversary's message with that IV, and returns the IV-prefixed ciphertext.

One consequence of this is that the adversary only learns the IV that was chosen to encrypt their plaintext after they've made the query.  This is what "non-secret but unpredictable" means in this context.

Predictable IVs would mean that the adversary is able to learn what IVs will be used before choosing the messages to query for.  In that case the adversary can cancel the effect of the IVs by XORing their binary complements to the first blocks of the messages they query.  For example, if the adversary knows that the next IV will be $\mathrm{IV}_i$ they can query for the encryptions of $\overline{\mathrm{IV}_i} \oplus P_i$ (for a one-block plaintext $P_i$), and they get:

$$
\begin{align}
C_i &= \mathrm{IV}_i \| E_k(\mathrm{IV}_i \oplus \overline{\mathrm{IV}_i} \oplus P_i) \\
C_i &= \mathrm{IV}_i \| E_k(P_i)
\end{align}
$$

So they've basically tricked the oracle into revealing what $P_i$ encrypts to with an all-zero IV.


This is due to RSA with PKCS#1 v1.5 padding, as defined in section 7.2 of RFC 3447 (PKCS#1 v2.1):

2. EME-PKCS1-v1_5 encoding:

      a. Generate an octet string PS of length k - mLen - 3 consisting
         of pseudo-randomly generated nonzero octets.  The length of PS
         will be at least eight octets.

      b. Concatenate PS, the message M, and other padding to form an
         encoded message EM of length k octets as

            EM = 0x00 || 0x02 || PS || 0x00 || M.

As you can see there are three overhead bytes and a minimum of 8 bytes of random padding.

Without the padding RSA encryption would be deterministic and not secure.

Originally the RSA encryption scheme has mostly been used with PKCS#1 v1.5 defined padding. No other schemes were all that popular at the time. So it is most likely that PKCS#1 v1.5 is implicitly used when no padding scheme is indicated.

Officially the name should be RSAES-PKCS1-V1_5-ENCRYPT of course, but nobody uses the function names directly.

Note that there are other modes of padding such as OAEP (defined in the same RFC), which is more secure. For new protocols PKCS#1 padding should not be used anymore. If you're stuck with an old protocol that requires PKCS#1 unpadding, you should make sure that padding / decryption oracles do not apply.


A feasible approach for AEAD on an ethernet link?

Don't roll your own crypto

So far my approach is: I can install certificates to both sides (for authentication), I do not know if or how I should renew them as time goes by.

This does not provide authentication in a cryptographic sense. A MITM attacker will still be able to modify data on the wire at will if the underlying encryption is not authenticated. Alone, a certificate can only be used to sign a very small value, the size of a symmetric key. It takes more than the presence of a certificate to ensure that data cannot be tampered with on the wire. For example, you would need to sign an HMAC key which ensures integrity of the messages. If this is not obvious to you, then you should not be trying to design your own cryptosystem!

I will XOR the plaintext with symmetric keys on both sides (I guess this is the fastest way).

This is called an XOR cipher and is extremely insecure, requiring just a tiny amount of known plaintext to break (the same amount as the size of the key). When you have known plaintext the same size as the key, you can simply XOR the known plaintext with the observed ciphertext to recover the key itself. Not to mention, it is highly malleable and does not provide any authentication, even if it was secure.

However, I consume keys much faster than I can produce. Somehow I should stretch keys or find a way to produce key streams very fast.

You have just invented a stream cipher. This is a cipher that takes a single key and expands it to a virtually unlimited stream of pseudorandom data called the keystream which is then added to the plaintext or ciphertext, usually via the XOR operation. A raw stream cipher, like ChaCha20 or AES in CTR mode, is malleable and not authenticated, making it insecure for your purposes. It is so malleable, in fact, that toggling a single ciphertext bit will toggle the corresponding plaintext bit. Such tampering would not be detected or prevented without a properly-implemented authentication algorithm like HMAC, GCM, or Poly1305.
Just use MACsec!
All is not lost! There is already a solution, called MACsec (IEEE 802.1ae). This is an extension to the Ethernet protocol which allows end-to-end authenticated encryption at a low computational cost. It uses AES as a cipher, run in the GCM mode for authentication. It is supported by a number of switches, routers, and operating systems, and is considered very secure.
If you are writing the HDL for the FPGAs, you can use pre-designed IP cores for MACsec, for example this FPGA core. You can also implement MACsec yourself from the published standard if you are confident in your FPGA design skills or can hire someone who is.
An additional benefit of MACsec is that, because this is a standard, it will work out-of-the-box with other compatible switches, such as Cisco's Catalyst 4500. You will not be limited to only using in-house custom switches with your own FPGAs and will not need to go through extensive and expensive cryptanalysis of your own protocol.
Any mentions of or links to commercial products should not be construed as an endorsement of the product of company.


Decrypt authenticated cipher while still encrypting

AES-GCM can be used as a as stream cypher by splitting the input to multiple blocks along with a nonce. However using AE for each block may not be an efficient technique.

See this topic
Also read this post.


How to practically find solutions to a discrete logarithm?

256-bit discrete logarithms on a prime field are definitely not of the order of magnitude used in cryptographic applications. Secure sizes for this problem are in the thousands of bits, very much like integer factorization.

To break that example discrete logarithm, you probably want to use Index Calculus, more specifically the Linear Sieve. Resorting to the Number Field Sieve is probably overkill for such a small prime field, and GGNFS is not prepared to solve discrete logarithms, although much of it could be reused to do so.

Note that 256-bit sizes are OK for problems with less structure, where only generic discrete logarithm algorithms, like Pollard's Rho, work --- such as elliptic curves over a 256-bit prime.


What's the purpose of secret message numbers in CAESAR ciphers?

DJB answers this question on the crypto-competions mailing list.

In short, the idea is that using counter as a nonce can leak information that would be better not leaked in real world conditions where an attacker may not have a copy of every message exchanged (or even if they do if e.g. a timestamp is used as counter).  However, using a counter also makes it much easier to reject replays without the protocol designer needing to include a separate counter.


Difference between INT-CTXT and INT-PTXT

My answer is taken from the following paper http://cseweb.ucsd.edu/~mihir/papers/oem.pdf (it is a well-written paper, so if you are interested in this topic I highly recommend you to read it).

Suppose $\mathcal{SE = (K, E, D)}$ is INT-PTXT secure. From $\mathcal{SE}$ we create another scheme $\mathcal{SE}_2 = (\mathcal{K}, \mathcal{E}_2, \mathcal{D}_2)$ which is also INT-PTXT secure, but not INT-CTXT secure. The idea is to add to every ciphertext produced by $\mathcal{E}$ a redundant bit which will be ignored upon decryption. This allows us to easily create new ciphertexts from old ones which still decrypts to the same plaintext. Intuitively, an attacker cannot exploit this against INT-PTXT (which requires it to submit ciphertexts that decrypts to new plaintexts), but it will help us to break INT-CTXT security.

In detail, the definitions of $\mathcal{E}_2$ and $\mathcal{D}_2$ are as follows.

$\underline{\mathcal{E}_2(K, M)}:\\\quad C \gets \mathcal{E}(K, M)\\\quad \text{Return } 0 || C$

$\underline{\mathcal{D}_2(K, C)}:\\\quad\text{Parse $C$ as $b || C'$ where $b$ is a bit (return $\perp$ if the parsing fails)}\\ \quad M \gets \mathcal{D}(K,C') \\ \quad \text{Return } M $

I leave it to you to prove that $\mathcal{SE}_2$ is also INT-PTXT (the reduction can be found in the last paragraph before Section 4 in http://cseweb.ucsd.edu/~mihir/papers/oem.pdf).

Here is a simple attack that shows that $\mathcal{SE}_2$ is not INT-CTXT.

$\text{Adversary $\mathcal{A}$}\\ \quad \text{Let $M$ be any arbitrary plaintext} \\ \quad C \gets \mathbf{EncryptOracle}(M)\\  \quad \text{Parse $C$ as $0 || C'$}\\ \quad \mathbf{VerificationOracle}(1 || C')$

Note that $\mathcal{A}$ is a valid INT-CTXT adversary since it asks for the verification of a ciphertext it did not previously obtain from an encrypt query.
But it is not a valid INT-PTXT adversary since both $0 || C'$ and $1 || C'$ decrypt to the same plaintext $M$ (and $\mathcal{A}$ previously asked for the encryption of $M$).


How resilient to attackers with extreme resources available is this encryption method?

All looks pretty secure except for your auth key derivation. You should use a better key derivation method like HKDF instead of just SHA-512.

I don't think your random nonce is doing anything in this scenario - an attacker who wants to brute-force a weak password wouldn't be slowed down by a nonce transmitted in the clear. Why not just use a randomly-generated AES key and a key exchange scheme? This would really confound an attacker with massive (e.g. nation-state level) resources. The NSA would laugh at your puny attempts to use scrypt to slow down brute-forcing.

EDIT: Wikipedia's article on Diffie-Hellman key exchange should get you started.


What would be a typical value for the security parameter of the Fully Homomorphic Encryption over the Integers scheme?

For the first part of the question, I couldn't find where the authors Quantify their security, what I understood that they build their scheme based on the hardness of GCD problem.

As for the second part, According to NIST recommendation which is a non-regulatory federal agency within the U.S. Commerce Department's Technology Administration. a secure value is estimated to be 112 and this won't be broken before 2030.  For other security estimates according to different schemes you can refer to https://www.keylength.com/